On 28/01/2008, Amit <contact.lipik@gmail.com> wrote:
As an aside, my usage exposes a case where unordered lose miserably to ordered:
I have a lexicon of words (wstring). Typically it has 20K entries (words in a given language, so well distributed), and is looked up often. Storing this as an unordered_map (with either boost:hash or Hsieh's hash) results in significantly lower lookup performance than in an ordered container.
[...]
Just thought I'd share in case anyone is contemplating using unordered_sets for dictionaries :)
Have you compared it to some sort of trie-based lookup? A TST patricia trie (I'm not sure if it's technically a patricia tree, but it's close enough) ought to have similar lookup speed properties, but slightly reduce the number of character comparisons. For that matter, has anyone written a generic container_map based on that kind of data structure? I don't think lookup on non-string container keys is frequent, but it could be a nice project. Goes off to contemplate how to make iterators work in that, ~ Scott