Quick Start

Let’s go over how to use sorted_string_map with a code example. In this example, we will define an enum type that includes all 50 US states, and associate them with their names as string keys.

Let’s include some headers first:

#include <mdds/sorted_string_map.hpp>
#include <iostream>

We include <mdds/sorted_string_map.hpp> to make the sorted_string_map class available, and <iostream> so that we can print some debug statements.

Next, let’s define the enum type for the US states:

enum class us_state_t
{
    unknown,
    alabama,
    alaska,
    arizona,
    arkansas,
    california,
    colorado,
    connecticut,
    delaware,
    florida,
    georgia,
    hawaii,
    idaho,
    illinois,
    indiana,
    iowa,
    kansas,
    kentucky,
    louisiana,
    maine,
    maryland,
    massachusetts,
    michigan,
    minnesota,
    mississippi,
    missouri,
    montana,
    nebraska,
    nevada,
    new_hampshire,
    new_jersey,
    new_mexico,
    new_york,
    north_carolina,
    north_dakota,
    ohio,
    oklahoma,
    oregon,
    pennsylvania,
    rhode_island,
    south_carolina,
    south_dakota,
    tennessee,
    texas,
    utah,
    vermont,
    virginia,
    washington,
    west_virginia,
    wisconsin,
    wyoming,
};

This enum type enumerates values for all 50 states plus unknown as its first member. This value is inplicitly assigned the value of 0 by virtue of it being the first member, and we will be using it as the null value for the container. A null value is the value returned by the find() method when it fails to find an associated value for the key passed by the caller. It is required during construction.

The next step is to define a concrete type:

using us_state_map_type = mdds::sorted_string_map<us_state_t>;

We are defining a type alias named us_state_map_type that uses sorted_string_map with us_state_t as its value type.

Once the concrete type is defined, we can then define the key-value entries as a static array of type mdds::sorted_string_map::entry_type:

// Keys must be sorted in ascending order.
constexpr us_state_map_type::entry_type us_state_entries[] = {
    { "Alabama", us_state_t::alabama },
    { "Alaska", us_state_t::alaska },
    { "Arizona", us_state_t::arizona },
    { "Arkansas", us_state_t::arkansas },
    { "California", us_state_t::california },
    { "Colorado", us_state_t::colorado },
    { "Connecticut", us_state_t::connecticut },
    { "Delaware", us_state_t::delaware },
    { "Florida", us_state_t::florida },
    { "Georgia", us_state_t::georgia },
    { "Hawaii", us_state_t::hawaii },
    { "Idaho", us_state_t::idaho },
    { "Illinois", us_state_t::illinois },
    { "Indiana", us_state_t::indiana },
    { "Iowa", us_state_t::iowa },
    { "Kansas", us_state_t::kansas },
    { "Kentucky", us_state_t::kentucky },
    { "Louisiana", us_state_t::louisiana },
    { "Maine", us_state_t::maine },
    { "Maryland", us_state_t::maryland },
    { "Massachusetts", us_state_t::massachusetts },
    { "Michigan", us_state_t::michigan },
    { "Minnesota", us_state_t::minnesota },
    { "Mississippi", us_state_t::mississippi },
    { "Missouri", us_state_t::missouri },
    { "Montana", us_state_t::montana },
    { "Nebraska", us_state_t::nebraska },
    { "Nevada", us_state_t::nevada },
    { "New Hampshire", us_state_t::new_hampshire },
    { "New Jersey", us_state_t::new_jersey },
    { "New Mexico", us_state_t::new_mexico },
    { "New York", us_state_t::new_york },
    { "North Carolina", us_state_t::north_carolina },
    { "North Dakota", us_state_t::north_dakota },
    { "Ohio", us_state_t::ohio },
    { "Oklahoma", us_state_t::oklahoma },
    { "Oregon", us_state_t::oregon },
    { "Pennsylvania", us_state_t::pennsylvania },
    { "Rhode Island", us_state_t::rhode_island },
    { "South Carolina", us_state_t::south_carolina },
    { "South Dakota", us_state_t::south_dakota },
    { "Tennessee", us_state_t::tennessee },
    { "Texas", us_state_t::texas },
    { "Utah", us_state_t::utah },
    { "Vermont", us_state_t::vermont },
    { "Virginia", us_state_t::virginia },
    { "Washington", us_state_t::washington },
    { "West Virginia", us_state_t::west_virginia },
    { "Wisconsin", us_state_t::wisconsin },
    { "Wyoming", us_state_t::wyoming },
};

Each entry contains two members of types std::string_view and mdds::sorted_string_map::value_type, respectively. Here, you must ensure that these entries are sorted alphabetically by the keys in ascending order.

Now we can construct an instance of this container. To create an instance, you must pass the pointer to the key-value entries array, the size of the array, and the null value:

const us_state_map_type state_map(us_state_entries, std::size(us_state_entries), us_state_t::unknown);

We are marking it as a const instance since it’s immutable; its state won’t change once it is constructed.

Now we can perform some lookups by calling the find() method:

auto state = state_map.find("Virginia");
std::cout << "virginia? " << std::boolalpha << (state == us_state_t::virginia) << std::endl;
state = state_map.find("North Carolina");
std::cout << "north_carolina? " << std::boolalpha << (state == us_state_t::north_carolina) << std::endl;

Running this code generates the following output:

virginia? true
north_carolina? true

When calling find() with a string key not included in the pre-defined entries, it will return the null value:

state = state_map.find("Alberta");
std::cout << "unknown? " << std::boolalpha << (state == us_state_t::unknown) << std::endl;

Running this code generates the following output:

unknown? true

You can also perform reverse lookup of finding a key from a value by calling the find_key() method:

auto key = state_map.find_key(us_state_t::rhode_island);
std::cout << "key for rhode_island: " << key << std::endl;

Running this code generates the following output:

key for rhode_island: Rhode Island

Note however, that find_key() by default performs linear search through the pre-defined entries to find the key from the value, so its runtime performance is not as efficient as that of find(), which performs binary search.

The algorithm used in find_key() depends on the second template argument passed to the sorted_string_map class, which by default is assigned the type mdds::ssmap::linear_key_finder. In case linear search is not desirable, one can specify mdds::ssmap::hash_key_finder as the second template argument to switch to a hash-table based lookup algorithm instead.