Re: [Boost-users] Question about proper container/algorithm to use for fast dictionary lookup

From: Nathan E. Moore (nate_at_[hidden])
Date: 2005-09-17 01:12:30

>> 2) Would its performance be much better than a general purpose
>> associative container?
>
> Performance-wise, it should be about the same as a hash_map.
> Memory-wise, a trie should be much better.
>
> AFAIK there is nothing resembling a trie in Boost, but there are other
> free implementations available.
>

Spirit has a TST as a internal class. It is used in boost::spirit::symbols 
class.

For information about TST see <http://www.cs.princeton.edu/%7Ers/strings/> 
or a recent copy of Sedgewick's "Algorithms" book.

Memory-wise a trie could be much worse than a hash_map, it depends on the 
data set.  If enough of your keys are prefixes of one another then memory 
usage is not that bad. However if your keys are unique or the end of the 
key is the common part then an excessive amount of memory can be used. 
Since for a TST a typical node will be at least 16 bytes on a 32bit 
machine.  That is 16 bytes per character, not per string.

Nathan E. Moore