The Fast Lookup Trie

The jdk_fasttree is a c++ class I wrote that is a container object for variable length strings of other objects (typically char). It uses a LOT of memory but is incredibly fast to look up an arbitrary value. It is faster than any hash table. The amount of time it takes to look up a value for a string is bounded by the length of the string - the number of strings in the tree has no bearing on the speed.

For instance, on a PPC processor, the 'find' loop takes 14 instructions per character. If you are trying to find a string that is 10 characters long, the find method will take a maximum of 140 + (function call overhead) instructions. This speed comes at a price, though - It is very very memory hungry.

e-mail me for more info.

Here is the source code for the trie and an example c++ program using it.

There are two forms of the trie here - One is a standalone template class with no regard to STL. The other is an experiment in creating a STL container compliant Trie.

See my discussions on comp.lang.c++.moderated about the issues with STL containers here