» Trie

…is a basic template based implementation of a prefix tree data structure.

The implementation may be found on Github or cgit.

A prefix tree or Trie is a data structure that can be used to store a dynamic set in a manner optimized for retrieving all keys with a specific prefix. While those keys are often plain character strings this template based implementation of the prefix tree data structure allows for usage with different types.

Current features

Usage example

The following example demonstrates the usage of the Trie class template specialized on a key and value type. While the first is obviously required the second may be ommitted if not required. Further usage examples are available as Google-Test based test cases.

Trie<uint8_t, uint8_t> trie;

trie.add({1, 1, 1, 1}, 42);
trie.add({1, 2, 1, 2}, 43);
trie.add({2, 3, 4, 5}, 44);
trie.add({2, 3, 1, 2}, 45);

std::cout << trie.get({1, 1, 1, 1})       << std::endl; // true
std::cout << trie.get({1, 1, 1, 1}).get() << std::endl; // 42
std::cout << trie.get({1, 2})             << std::endl; // false