C++ Trie Library

Features

• Very easy to use, see doxygen documentation for the description of API or example below
• Very efficient to store a trie in memory (contain a factory to perform allocation per bloc)
• Generic implementation to allow association of any type
• ToolBox::Trie<T> is an efficient replacement of std::map<std::string, T>
• You can compile a Trie<T> in a patricia trie that can be stored on disk if T = unsigned or uint64 (you need to use TrieToStr class in C++ String B-Tree package)
• You can use it for non-commercial and commercial purposes, licensed under terms of GNU LGPL license

Download

Download libTrie-0.1.tgz
Doxygen Documentation: view online or download

Example

Here is a simple example that use this library :

#include "src/Trie.hxx"
#include "src/Exception.h"

int main(int argc, char **argv)
{
  /// trie that associates a integer to strings
  /// 0 is the default value I want to receive when there is no match
  /// in trie
  ToolBox::Trie<unsigned>.    trie(0);

  std::cout << "set [First String] = 1" << std::endl;
  trie.addEntry("First String", 12, 1);
  std::cout << "set [Second String] = 2" << std::endl;
  trie.addEntry("Second String", 13, 2);
  std::cout << "set [First Element] = 3" << std::endl;
  trie.addEntry("First Element", 13, 3);
  std::cout << "set [Second Element] = 4" << std::endl;
  trie.addEntry("Second Element", 14, 4);

  std::cout << "get [First String] = " << trie.getEntry("First String", 12) << std::endl;
  std::cout << "get [Second String] = " << trie.getEntry("Second String", 13) << std::endl;
  std::cout << "get [First Element] = " << trie.getEntry("First Element", 13) << std::endl;
  std::cout << "get [Second Element] = " << trie.getEntry("Second Element", 14) << std::endl;

  std::cout << "set [First String] = 10" << std::endl;
  trie.setEntry("First String", 12, 10);
  std::cout << "get [First String] = " << trie.getEntry("First String", 12) << std::endl;

  // no match
  std::cout << "get [No match for this entry] = " << trie.getEntry("No match for this entry", 23) << std::endl;
}

This example produces the following output :

set [First String] = 1
set [Second String] = 2
set [First Element] = 3
set [Second Element] = 4
get [First String] = 1
get [Second String] = 2
get [First Element] = 3
get [Second Element] = 4
set [First String] = 10
get [First String] = 10
get [No match for this entry] = 0