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.