Classes |
struct | trie_node |
| Node of our trie. Left subtree will be other suggestions for the current position, right subtree will be following items for the word seen from the root to here.
|
Public Types |
typedef const T | value_type |
typedef Comp | value_equal_to |
Public Member Functions |
| trie () |
| Trie constructor.
|
| trie (const trie< T, Comp > &that) |
| ~trie () |
| Trie destructor.
|
unsigned int | size () const |
| Gets size (words count) of the structure.
|
bool | empty () const |
| Tell if the structure is empty or not.
|
void | clear () |
| Clear the trie.
|
template<class InputIterator > |
void | insert (InputIterator first, InputIterator last) |
| Add a word to the structure.
|
template<class InputIterator > |
unsigned int | count (InputIterator first, InputIterator last) |
| Gets a word count.
|
template<class T, class Comp = std::equal_to<T>>
class claw::trie< T, Comp >
This class is a trie tree.
Trie trees are used for storage and count of linear datas with similar prefixes, typically words. For example, if you insert words
- ant
- antagonize
- antagonism
- ant It will use as much memory space as
- antagonize
- antagonism Nodes for "ant" are shared between words, likewise for "antagoni" for the two last word, and a counter is set for each word. So "ant" will have a count of 2.
- Invariant:
- empty <=> (size()==0)
- Author:
- Julien Jorge
Definition at line 62 of file trie.hpp.