Re: [boost] [ptr_container] Any plans to add ptr_unordered_set/map?

From: Scott McMurray (me22.ca+boost_at_[hidden])
Date: 2008-01-28 12:31:35

On 28/01/2008, Amit <contact.lipik_at_[hidden]> 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