.. highlight:: cpp Trie Maps ========= Examples -------- Populating Trie Map ^^^^^^^^^^^^^^^^^^^ This section illustrates how to use :cpp:class:`~mdds::trie_map` to build a database of city populations and perform prefix searches. In this example, we will use the 2013 populations of cities in North Carolina, and use the city names as keys. Let's define the type first:: using trie_map_type = mdds::trie_map; The first template argument specifies the trait of the key. In this example, we are using a pre-defined trait for std::string, which is defined in :cpp:type:`~mdds::trie::std_string_traits`. The second template argument specifies the value type, which in this example is simply an ``int``. Once the type is defined, the next step is instantiation:: trie_map_type nc_cities; It's pretty simple as you don't need to pass any arguments to the constructor. Now, let's populate this data structure with some population data:: // Insert key-value pairs. nc_cities.insert("Charlotte", 792862); nc_cities.insert("Raleigh", 431746); nc_cities.insert("Greensboro", 279639); nc_cities.insert("Durham", 245475); nc_cities.insert("Winston-Salem", 236441); nc_cities.insert("Fayetteville", 204408); nc_cities.insert("Cary", 151088); nc_cities.insert("Wilmington", 112067); nc_cities.insert("High Point", 107741); nc_cities.insert("Greenville", 89130); nc_cities.insert("Asheville", 87236); nc_cities.insert("Concord", 83506); nc_cities.insert("Gastonia", 73209); nc_cities.insert("Jacksonville", 69079); nc_cities.insert("Chapel Hill", 59635); nc_cities.insert("Rocky Mount", 56954); nc_cities.insert("Burlington", 51510); nc_cities.insert("Huntersville", 50458); nc_cities.insert("Wilson", 49628); nc_cities.insert("Kannapolis", 44359); nc_cities.insert("Apex", 42214); nc_cities.insert("Hickory", 40361); nc_cities.insert("Goldsboro", 36306); It's pretty straight-forward. Each :cpp:func:`~mdds::trie_map::insert` call expects a pair of string key and an integer value. You can insert your data in any order regardless of key's sort order. Now that the data is in, let's perform prefix search to query all cities whose name begins with "Cha":: cout << "Cities that start with 'Cha' and their populations:" << endl; auto results = nc_cities.prefix_search("Cha"); for (const auto& kv : results) { cout << " " << kv.first << ": " << kv.second << endl; } You can perform prefix search via :cpp:func:`~mdds::trie_map::prefix_search` method, which returns a results object that can be iterated over using a range-based for loop. Running this code will produce the following output: .. code-block:: none Cities that start with 'Cha' and their populations: Chapel Hill: 59635 Charlotte: 792862 Let's perform another prefix search, this time with a prefix of "W":: cout << "Cities that start with 'W' and their populations:" << endl; results = nc_cities.prefix_search("W"); for (const auto& kv : results) { cout << " " << kv.first << ": " << kv.second << endl; } You'll see the following output when running this code: .. code-block:: none Cities that start with 'W' and their populations: Wilmington: 112067 Wilson: 49628 Winston-Salem: 236441 Note that the results are sorted in key's ascending order. .. note:: Results from the prefix search are sorted in key's ascending order. Creating Packed Trie Map from Trie Map ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ There is also another variant of trie called :cpp:class:`~mdds::packed_trie_map` which is designed to store all its data in contiguous memory region. Unlike :cpp:class:`~mdds::trie_map` which is mutable, :cpp:class:`~mdds::packed_trie_map` is immutable; once populated, you can only perform queries and it is no longer possible to add new entries into the container. One way to create an instance of :cpp:class:`~mdds::packed_trie_map` is from :cpp:class:`~mdds::trie_map` by calling its :cpp:func:`~mdds::trie_map::pack` method:: auto packed = nc_cities.pack(); The query methods of :cpp:class:`~mdds::packed_trie_map` are identical to those of :cpp:class:`~mdds::trie_map`. For instance, performing prefix search to find all entries whose key begins with "C" can be done as follows:: cout << "Cities that start with 'C' and their populations:" << endl; auto packed_results = packed.prefix_search("C"); for (const auto& kv : packed_results) { cout << " " << kv.first << ": " << kv.second << endl; } Running this code will generate the following output: .. code-block:: none Cities that start with 'C' and their populations: Cary: 151088 Chapel Hill: 59635 Charlotte: 792862 Concord: 83506 You can also perform an exact-match query via :cpp:func:`~mdds::packed_trie_map::find` method which returns an iterator associated with the key-value pair entry:: // Individual search. auto it = packed.find("Wilmington"); cout << "Population of Wilmington: " << it->second << endl; You'll see the following output with this code: .. code-block:: none Population of Wilmington: 112067 What if you performed an exact-match query with a key that doesn't exist in the container? You will basically get the end iterator position as its return value. Thus, running this code:: // You get an end position iterator when the container doesn't have the // specified key. it = packed.find("Asheboro"); cout << "Population of Asheboro: "; if (it == packed.end()) cout << "not found"; else cout << it->second; cout << endl; will generate the following output: .. code-block:: none Population of Asheboro: not found The complete source code for the examples in these two sections is available `here `__. Using Packed Trie Map directly ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ In the previous example, we showed a way to create an instance of :cpp:class:`~mdds::packed_trie_map` from a populated instance of :cpp:class:`~mdds::trie_map`. There is also a way to instantiate and populate an instance of :cpp:class:`~mdds::packed_trie_map` directly, and that is what we will cover in this section. First, declare the type:: using trie_map_type = mdds::packed_trie_map; Once again, we are using the pre-defined trait for std::string as its key, and int as its value type. The next step is to prepare its entries ahead of time:: trie_map_type::entry entries[] = { { MDDS_ASCII("Apex"), 42214 }, { MDDS_ASCII("Asheville"), 87236 }, { MDDS_ASCII("Burlington"), 51510 }, { MDDS_ASCII("Cary"), 151088 }, { MDDS_ASCII("Chapel Hill"), 59635 }, { MDDS_ASCII("Charlotte"), 792862 }, { MDDS_ASCII("Concord"), 83506 }, { MDDS_ASCII("Durham"), 245475 }, { MDDS_ASCII("Fayetteville"), 204408 }, { MDDS_ASCII("Gastonia"), 73209 }, { MDDS_ASCII("Goldsboro"), 36306 }, { MDDS_ASCII("Greensboro"), 279639 }, { MDDS_ASCII("Greenville"), 89130 }, { MDDS_ASCII("Hickory"), 40361 }, { MDDS_ASCII("High Point"), 107741 }, { MDDS_ASCII("Huntersville"), 50458 }, { MDDS_ASCII("Jacksonville"), 69079 }, { MDDS_ASCII("Kannapolis"), 44359 }, { MDDS_ASCII("Raleigh"), 431746 }, { MDDS_ASCII("Rocky Mount"), 56954 }, { MDDS_ASCII("Wilmington"), 112067 }, { MDDS_ASCII("Wilson"), 49628 }, { MDDS_ASCII("Winston-Salem"), 236441 }, }; We need to do this since :cpp:class:`~mdds::packed_trie_map` is immutable, and the only time we can populate its content is at instantiation time. Here, we are using the :c:macro:`MDDS_ASCII` macro to expand a string literal to its pointer value and size. Note that you need to ensure that the entries are sorted by the key in ascending order. .. warning:: When instantiating :cpp:class:`~mdds::packed_trie_map` directly with a static set of entries, the entries must be sorted by the key in ascending order. You can then pass this list of entries to construct the instance:: trie_map_type nc_cities(entries, MDDS_N_ELEMENTS(entries)); The :c:macro:`MDDS_N_ELEMENTS` macro will infer the size of a fixed-size array from its static definition. Once it's instantiated, the rest of the example for performing searches will be the same as in the previous section, which we will not repeat here. The complete source code for the example in this section is available `here `__. Saving and loading Packed Trie Map instances ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ There are times when you need to save the state of a :cpp:class:`~mdds::packed_trie_map` instance to a file, or an in-memory buffer, and load it back later. Doing that is now possible by using the :cpp:func:`~mdds::packed_trie_map::save_state` and :cpp:func:`~mdds::packed_trie_map::load_state` member methods of the :cpp:class:`~mdds::packed_trie_map` class. First, let's define the type of use:: using map_type = mdds::packed_trie_map; As with the previous examples, we will use ``std::string`` as the key type and ``int`` as the value type. In this example, we are going to use `the world's largest cities and their 2018 populations `__ as the data to store in the container. The following code defines the entries:: std::vector entries = { { MDDS_ASCII("Ahmedabad"), 7681000 }, { MDDS_ASCII("Alexandria"), 5086000 }, { MDDS_ASCII("Atlanta"), 5572000 }, { MDDS_ASCII("Baghdad"), 6812000 }, { MDDS_ASCII("Bangalore"), 11440000 }, { MDDS_ASCII("Bangkok"), 10156000 }, { MDDS_ASCII("Barcelona"), 5494000 }, { MDDS_ASCII("Beijing"), 19618000 }, { MDDS_ASCII("Belo Horizonte"), 5972000 }, { MDDS_ASCII("Bogota"), 10574000 }, { MDDS_ASCII("Buenos Aires"), 14967000 }, { MDDS_ASCII("Cairo"), 20076000 }, { MDDS_ASCII("Chengdu"), 8813000 }, { MDDS_ASCII("Chennai"), 10456000 }, { MDDS_ASCII("Chicago"), 8864000 }, { MDDS_ASCII("Chongqing"), 14838000 }, { MDDS_ASCII("Dalian"), 5300000 }, { MDDS_ASCII("Dallas"), 6099000 }, { MDDS_ASCII("Dar es Salaam"), 6048000 }, { MDDS_ASCII("Delhi"), 28514000 }, { MDDS_ASCII("Dhaka"), 19578000 }, { MDDS_ASCII("Dongguan"), 7360000 }, { MDDS_ASCII("Foshan"), 7236000 }, { MDDS_ASCII("Fukuoka"), 5551000 }, { MDDS_ASCII("Guadalajara"), 5023000 }, { MDDS_ASCII("Guangzhou"), 12638000 }, { MDDS_ASCII("Hangzhou"), 7236000 }, { MDDS_ASCII("Harbin"), 6115000 }, { MDDS_ASCII("Ho Chi Minh City"), 8145000 }, { MDDS_ASCII("Hong Kong"), 7429000 }, { MDDS_ASCII("Houston"), 6115000 }, { MDDS_ASCII("Hyderabad"), 9482000 }, { MDDS_ASCII("Istanbul"), 14751000 }, { MDDS_ASCII("Jakarta"), 10517000 }, { MDDS_ASCII("Jinan"), 5052000 }, { MDDS_ASCII("Johannesburg"), 5486000 }, { MDDS_ASCII("Karachi"), 15400000 }, { MDDS_ASCII("Khartoum"), 5534000 }, { MDDS_ASCII("Kinshasa"), 13171000 }, { MDDS_ASCII("Kolkata"), 14681000 }, { MDDS_ASCII("Kuala Lumpur"), 7564000 }, { MDDS_ASCII("Lagos"), 13463000 }, { MDDS_ASCII("Lahore"), 11738000 }, { MDDS_ASCII("Lima"), 10391000 }, { MDDS_ASCII("London"), 9046000 }, { MDDS_ASCII("Los Angeles"), 12458000 }, { MDDS_ASCII("Luanda"), 7774000 }, { MDDS_ASCII("Madrid"), 6497000 }, { MDDS_ASCII("Manila"), 13482000 }, { MDDS_ASCII("Mexico City"), 21581000 }, { MDDS_ASCII("Miami"), 6036000 }, { MDDS_ASCII("Moscow"), 12410000 }, { MDDS_ASCII("Mumbai"), 19980000 }, { MDDS_ASCII("Nagoya"), 9507000 }, { MDDS_ASCII("Nanjing"), 8245000 }, { MDDS_ASCII("New York City"), 18819000 }, { MDDS_ASCII("Osaka"), 19281000 }, { MDDS_ASCII("Paris"), 10901000 }, { MDDS_ASCII("Philadelphia"), 5695000 }, { MDDS_ASCII("Pune"), 6276000 }, { MDDS_ASCII("Qingdao"), 5381000 }, { MDDS_ASCII("Rio de Janeiro"), 13293000 }, { MDDS_ASCII("Riyadh"), 6907000 }, { MDDS_ASCII("Saint Petersburg"), 5383000 }, { MDDS_ASCII("Santiago"), 6680000 }, { MDDS_ASCII("Sao Paulo"), 21650000 }, { MDDS_ASCII("Seoul"), 9963000 }, { MDDS_ASCII("Shanghai"), 25582000 }, { MDDS_ASCII("Shenyang"), 6921000 }, { MDDS_ASCII("Shenzhen"), 11908000 }, { MDDS_ASCII("Singapore"), 5792000 }, { MDDS_ASCII("Surat"), 6564000 }, { MDDS_ASCII("Suzhou"), 6339000 }, { MDDS_ASCII("Tehran"), 8896000 }, { MDDS_ASCII("Tianjin"), 13215000 }, { MDDS_ASCII("Tokyo"), 37400068 }, { MDDS_ASCII("Toronto"), 6082000 }, { MDDS_ASCII("Washington, D.C."), 5207000 }, { MDDS_ASCII("Wuhan"), 8176000 }, { MDDS_ASCII("Xi'an"), 7444000 }, { MDDS_ASCII("Yangon"), 5157000 }, }; It's a bit long as it contains entries for 81 cities. We are then going to create an instance of the :cpp:class:`~mdds::packed_trie_map` class directly:: map_type cities(entries.data(), entries.size()); Let's print the size of the container to make sure the container has been successfully populated:: cout << "Number of cities: " << cities.size() << endl; You will see the following output: .. code-block:: none Number of cities: 81 if the container has been successfully populated. Now, let's run a prefix search on names beginning with an 'S':: cout << "Cities that begin with 'S':" << endl; auto results = cities.prefix_search("S"); for (const auto& city : results) cout << " * " << city.first << ": " << city.second << endl; to make sure you get the following ten cities and their populations as the output: .. code-block:: none Cities that begin with 'S': * Saint Petersburg: 5383000 * Santiago: 6680000 * Sao Paulo: 21650000 * Seoul: 9963000 * Shanghai: 25582000 * Shenyang: 6921000 * Shenzhen: 11908000 * Singapore: 5792000 * Surat: 6564000 * Suzhou: 6339000 So far so good. Next, we will use the :cpp:func:`~mdds::packed_trie_map::save_state` method to dump the internal state of this container to a file named **cities.bin**:: std::ofstream outfile("cities.bin", std::ios::binary); cities.save_state(outfile); This will create a file named **cities.bin** which contains a binary blob representing the content of this container in the current working directory. Run the ``ls -l cities.bin`` command to make sure the file has been created: .. code-block:: none -rw-r--r-- 1 kohei kohei 17713 Jun 20 12:49 cities.bin Now that the state of the container has been fully serialized to a file, let's work on restoring its content in another, brand-new instance of :cpp:class:`~mdds::packed_trie_map`. :: map_type cities_loaded; std::ifstream infile("cities.bin", std::ios::binary); cities_loaded.load_state(infile); Here, we used the :cpp:func:`~mdds::packed_trie_map::load_state` method to restore the state from the file we have previously created. Let's make sure that this new instance has content equivalent to that of the original:: cout << "Equal to the original? " << std::boolalpha << (cities == cities_loaded) << endl; If you see the following output: .. code-block:: none Equal to the original? true then this new instance has equivalent contant as the original one. Let's also make sure that it contains the same number of entries as the original:: cout << "Number of cities: " << cities_loaded.size() << endl; Hopefully you will see the following output: .. code-block:: none Number of cities: 81 Lastly, let's run on this new instance the same prefix search we did on the original instance, to make sure we still get the same results:: cout << "Cities that begin with 'S':" << endl; auto results = cities_loaded.prefix_search("S"); for (const auto& city : results) cout << " * " << city.first << ": " << city.second << endl; You should see the following output: .. code-block:: none Cities that begin with 'S': * Saint Petersburg: 5383000 * Santiago: 6680000 * Sao Paulo: 21650000 * Seoul: 9963000 * Shanghai: 25582000 * Shenyang: 6921000 * Shenzhen: 11908000 * Singapore: 5792000 * Surat: 6564000 * Suzhou: 6339000 which is the same output we saw in the first prefix search. The complete source code for this example is found `here `__. Saving Packed Trie Map with custom value type ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ In the previos example, you didn't have to explicitly specify the serializer type to the :cpp:func:`~mdds::packed_trie_map::save_state` and :cpp:func:`~mdds::packed_trie_map::load_state` methods, even though these two methods require the serializer type as their template arguments. That's because the library provides default serializer types for * numeric value types i.e. integers, float and double, * ``std::string``, and * the standard sequence types, such as ``std::vector``, whose elements are of numeric value types, and the previous example used ``int`` as the value type. In this section, we are going to illustrate how you can write your own custom serializer to allow serialization of your own custom value type. In this example, we are going to use `the list of presidents of the United States `__, with the names of the presidents as the keys, and their years of inauguration and political affiliations as the values. We will use the following structure to store the values:: enum affiliated_party_t : uint8_t { unaffiliated = 0, federalist, democratic_republican, democratic, whig, republican, national_union, republican_national_union, }; struct us_president { uint16_t year; affiliated_party_t party; }; Each entry stores the year as a 16-bit integer and the affiliated party as an enum value of 8-bit width. Next, let's define the container type:: using map_type = mdds::packed_trie_map; As with the previous example, the first step is to define the entries that are sorted by the keys, which in this case are the president's names:: std::vector entries = { { MDDS_ASCII("Abraham Lincoln"), { 1861, republican_national_union } }, { MDDS_ASCII("Andrew Jackson"), { 1829, democratic } }, { MDDS_ASCII("Andrew Johnson"), { 1865, national_union } }, { MDDS_ASCII("Barack Obama"), { 2009, democratic } }, { MDDS_ASCII("Benjamin Harrison"), { 1889, republican } }, { MDDS_ASCII("Bill Clinton"), { 1993, democratic } }, { MDDS_ASCII("Calvin Coolidge"), { 1923, republican } }, { MDDS_ASCII("Chester A. Arthur"), { 1881, republican } }, { MDDS_ASCII("Donald Trump"), { 2017, republican } }, { MDDS_ASCII("Dwight D. Eisenhower"), { 1953, republican } }, { MDDS_ASCII("Franklin D. Roosevelt"), { 1933, democratic } }, { MDDS_ASCII("Franklin Pierce"), { 1853, democratic } }, { MDDS_ASCII("George H. W. Bush"), { 1989, republican } }, { MDDS_ASCII("George W. Bush"), { 2001, republican } }, { MDDS_ASCII("George Washington"), { 1789, unaffiliated } }, { MDDS_ASCII("Gerald Ford"), { 1974, republican } }, { MDDS_ASCII("Grover Cleveland 1"), { 1885, democratic } }, { MDDS_ASCII("Grover Cleveland 2"), { 1893, democratic } }, { MDDS_ASCII("Harry S. Truman"), { 1945, democratic } }, { MDDS_ASCII("Herbert Hoover"), { 1929, republican } }, { MDDS_ASCII("James A. Garfield"), { 1881, republican } }, { MDDS_ASCII("James Buchanan"), { 1857, democratic } }, { MDDS_ASCII("James K. Polk"), { 1845, democratic } }, { MDDS_ASCII("James Madison"), { 1809, democratic_republican } }, { MDDS_ASCII("James Monroe"), { 1817, democratic_republican } }, { MDDS_ASCII("Jimmy Carter"), { 1977, democratic } }, { MDDS_ASCII("John Adams"), { 1797, federalist } }, { MDDS_ASCII("John F. Kennedy"), { 1961, democratic } }, { MDDS_ASCII("John Quincy Adams"), { 1825, democratic_republican } }, { MDDS_ASCII("John Tyler"), { 1841, whig } }, { MDDS_ASCII("Lyndon B. Johnson"), { 1963, democratic } }, { MDDS_ASCII("Martin Van Buren"), { 1837, democratic } }, { MDDS_ASCII("Millard Fillmore"), { 1850, whig } }, { MDDS_ASCII("Richard Nixon"), { 1969, republican } }, { MDDS_ASCII("Ronald Reagan"), { 1981, republican } }, { MDDS_ASCII("Rutherford B. Hayes"), { 1877, republican } }, { MDDS_ASCII("Theodore Roosevelt"), { 1901, republican } }, { MDDS_ASCII("Thomas Jefferson"), { 1801, democratic_republican } }, { MDDS_ASCII("Ulysses S. Grant"), { 1869, republican } }, { MDDS_ASCII("Warren G. Harding"), { 1921, republican } }, { MDDS_ASCII("William Henry Harrison"), { 1841, whig } }, { MDDS_ASCII("William Howard Taft"), { 1909, republican } }, { MDDS_ASCII("William McKinley"), { 1897, republican } }, { MDDS_ASCII("Woodrow Wilson"), { 1913, democratic } }, { MDDS_ASCII("Zachary Taylor"), { 1849, whig } }, }; Note that we need to add numeric suffixes to the entries for Grover Cleveland, who became president twice in two separate periods, in order to make the keys for his entries unique. Now, proceed to create an instance of :cpp:class:`~mdds::packed_trie_map`:: map_type us_presidents(entries.data(), entries.size()); and inspect its size to make sure it is instantiated properly:: cout << "Number of entries: " << us_presidents.size() << endl; You should see the following output: .. code-block:: none Number of entries: 45 Before we proceed to save the state of this instance, let's define the custom serializer type first:: struct us_president_serializer { union bin_buffer { char buffer[2]; uint16_t i16; affiliated_party_t party; }; static constexpr bool variable_size = false; static constexpr size_t value_size = 3; static void write(std::ostream& os, const us_president& v) { bin_buffer buf; // Write the year value first. buf.i16 = v.year; os.write(buf.buffer, 2); // Write the affiliated party value. buf.party = v.party; os.write(buf.buffer, 1); } static void read(std::istream& is, size_t n, us_president& v) { // For a fixed-size value type, this should equal the defined value size. assert(n == 3); bin_buffer buf; // Read the year value. is.read(buf.buffer, 2); v.year = buf.i16; // Read the affiliated party value. is.read(buf.buffer, 1); v.party = buf.party; } }; A custom value type can be either variable-size or fixed-size. For a variable-size value type, each value segment is preceded by the byte length of that segment. For a fixed-size value type, the byte length of all of the value segments is written only once up-front, followed by one or more value segments of equal byte length. Since the value type in this example is fixed-size, we set the value of the ``variable_size`` static constant to false, and define the size of the value to 3 (bytes) as the ``value_size`` static constant. Keep in mind that you need to define the ``value_size`` constant *only* for fixed-size value types; if your value type is variable-size, you can leave it out. Additionally, you need to define two static methods - one for writing to the output stream, and one for reading from the input stream. The write method must have the following signature:: static void write(std::ostream& os, const T& v); where the ``T`` is the value type. In the body of this method you write to the output stream the bytes that represent the value. The length of the bytes you write must match the size specified by the ``value_size`` constant. The read method must have the following signature:: static void read(std::istream& is, size_t n, T& v); where the ``T`` is the value type, and the ``n`` specifies the length of the bytes you need to read for the value. For a fixed-size value type, the value of ``n`` should equal the ``value_size`` constant. Your job is to read the bytes off of the input stream for the length specified by the ``n``, and populate the value instance passed to the method as the third argument. Now that we have defined the custom serializer type, let's proceed to save the state to a file:: std::ofstream outfile("us-presidents.bin", std::ios::binary); us_presidents.save_state(outfile); This time around, we are specifying the serializer type explicitly as the template argument to the :cpp:func:`~mdds::packed_trie_map::save_state` method. Otherwise it is no different than what we did in the previous example. Let's create another instance of :cpp:class:`~mdds::packed_trie_map` and restore the state back from the file we just created:: map_type us_presidents_loaded; std::ifstream infile("us-presidents.bin", std::ios::binary); us_presidents_loaded.load_state(infile); Once again, aside from explicitly specifying the serializer type as the template argument to the :cpp:func:`~mdds::packed_trie_map::load_state` method, it is identical to the way we did in the previous example. Let's compare the new instance with the old one to see if the two are equal:: cout << "Equal to the original? " << std::boolalpha << (us_presidents == us_presidents_loaded) << endl; The output says: .. code-block:: none Equal to the original? true They are. While we are at it, let's run a simple prefix search to find out all the US presidents whose first name is 'John':: cout << "Presidents whose first name is 'John':" << endl; auto results = us_presidents_loaded.prefix_search("John"); for (const auto& entry : results) cout << " * " << entry.first << " (" << entry.second.year << "; " << entry.second.party << ")" << endl; Here is the output: .. code-block:: none Presidents whose first name is 'John': * John Adams (1797; Federalist) * John F. Kennedy (1961; Democratic) * John Quincy Adams (1825; Democratic Republican) * John Tyler (1841; Whig) This looks like the correct results! You can find the complete source code for this example `here `__. API Reference ------------- Trie Map ^^^^^^^^ .. doxygenclass:: mdds::trie_map :members: Packed Trie Map ^^^^^^^^^^^^^^^ .. doxygenclass:: mdds::packed_trie_map :members: Traits ^^^^^^ .. doxygenstruct:: mdds::trie::std_container_traits :members: .. doxygentypedef:: mdds::trie::std_string_traits Value Serializers ^^^^^^^^^^^^^^^^^ .. doxygenstruct:: mdds::trie::value_serializer :members: .. doxygenstruct:: mdds::trie::numeric_value_serializer :members: .. doxygenstruct:: mdds::trie::variable_value_serializer :members: .. doxygenstruct:: mdds::trie::numeric_sequence_value_serializer :members: