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