Trie
Trie is a lightweight and simple autocompletion data structure written in C++11.
Trie is tiny, cross-platform and header-only.
Trie is zlib/libpng licensed.
construct trie<K>
or trie<K,V>
as desired.
.insert(element)
or [element]
to create/access elements.
.has(element)
returns true
if element
is in trie.
.complete(element)
autocompletes partially provided element
then returns vector of candidate pointers.
.list()
returns a vector of hosted pointers in trie.
.size()
returns number of elements in trie.
#include " trie.hpp"
#include < iostream>
#include < string>
#include < cassert>
int main ()
{
trie<std::string> t;
t.insert (" wargame" );
t.insert (" wombat" );
t.insert (" wolfram" );
t.insert (" world" );
t.insert (" work" );
assert ( t.size () == 5 );
assert ( t.has (" war" ) == false );
assert ( t.has (" wargame" ) == true );
auto candidates = t.complete (" wo" );
assert ( candidates.size () == 4 );
candidates = t.complete (" warg" );
assert ( candidates.size () == 1 );
assert ( *candidates[0 ] == " wargame" );
std::cout << " All ok." << std::endl;
}
~/trie>g++ sample.cc trie.cpp -std=c++11
All ok.
~/trie>
v1.0.1 (2015/05/25)
Additional tree implementation.
v1.0.0 (2013/07/18)