Populating trie_map

This section illustrates how to use 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<std::string, int>;

The first template argument specifies the key type, while the second template argument specifies the value type. In this example we are using std::string and int, respectively.

Once the type is defined, the next step is instantiation:

// Cities in North Carolina and their populations in 2013.
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 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”:

std::cout << "Cities that start with 'Cha' and their populations:" << std::endl;
auto results = nc_cities.prefix_search("Cha");
for (const auto& kv : results)
{
    std::cout << "  " << kv.first << ": " << kv.second << std::endl;
}

You can perform prefix search via 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:

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”:

std::cout << "Cities that start with 'W' and their populations:" << std::endl;
results = nc_cities.prefix_search("W");
for (const auto& kv : results)
{
    std::cout << "  " << kv.first << ": " << kv.second << std::endl;
}

You’ll see the following output when running this code:

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.