Create a Trie Class for Search Suggestions
Learn to create a trie class for search suggestions.
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:
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;
Get hands-on with 1400+ tech skills courses.