C++20 STL Cookbook/

...

/

Create a Trie Class for Search Suggestions

Create a Trie Class for Search Suggestions

Learn to create a trie class for search suggestions.

We'll cover the following...

A trie, sometimes called a prefix tree, is a type of search tree, commonly used for predictive text and other search applications. A trie is a recursive structure designed for depth-first searches, where each node is both a key and another trie.

A common use case is a trie of strings, where each node is a string in a sentence. For example:

Press + to interact
A trie of strings
A trie of strings

We often start a search at the head of a trie, looking for sentences that begin with a specific word. In this example, when we search for all, we get three nodes: you, the, and along. If we search for love, we get me and is.

A string trie is commonly used for creating search suggestions. Here we will implement a string trie using std::map for the trie structure.

How to do it

In this recipe, we create a recursive trie class that stores nodes in a std::map container. It's a simple solution for a small in-memory trie. This is a rather large class, so we'll only show the important parts here.

  • We have one convenience alias:

using ilcstr = initializer_list<const char *>;

We use ilcstr for searching the trie.

  • We'll put this class in a private namespace to avoid collisions:

namespace bw {
    using std::map;
    using std::deque;
    using std::initializer_list;

We have a few using ...

Ask