Implementing a trie class using STL algorithms
The so-called trie data structure poses an interesting way to store data in an easily searchable manner. When segmenting sentences of text into lists of words, it is often possible to combine the first few words that some sentences have in common.
Let's have a look at the following diagram, where the sentences "hi how are you" and "hi how do you do" are saved in a tree-like data structure. The first words they have in common are "hi how", and then they differ and split up like a tree:
Because the trie data structure combines common prefixes, it is also called prefix tree. It is very easy to implement such a data structure with what the STL gives us already. This section concentrates on implementing our own trie class.
How to do it...
In this section, we will implement our own prefix tree only made from STL data structures and algorithms.
- We will include all the headers from the STL parts we use and declare that we use the
stdnamespace by default...
