Creating packed_trie_map from trie_map

There is also another variant of trie called packed_trie_map which is designed to store all its data in contiguous memory region. Unlike trie_map which is mutable, 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 packed_trie_map is from trie_map by calling its pack() method:

auto packed = nc_cities.pack();

When creating a packed_trie_map instance this way, however, you need to be aware that the values get moved from the original instance to the new instance. As such, it is not advisable to keep the original instance around afterward. If you need to keep the original instance intact, you can first create a copy of it and then call its pack() method to create the packed variant.

Warning

Calling pack() will move all the stored values to the packed variant. Make a copy first if you need to keep the original instance intact.

The query methods of packed_trie_map are identical to those of trie_map. For instance, performing prefix search to find all entries whose key begins with “C” can be done as follows:

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;
}

Running this code will generate the following output:

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 find() method which returns an iterator associated with the key-value pair entry:

// Individual search.
auto it = packed.find("Wilmington");
std::cout << "Population of Wilmington: " << it->second << std::endl;

You’ll see the following output with this code:

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");

std::cout << "Population of Asheboro: ";

if (it == packed.end())
    std::cout << "not found";
else
    std::cout << it->second;

std::cout << std::endl;

will generate the following output:

Population of Asheboro: not found

The complete source code for the examples in these two sections is available here.