Re: [Boost-users] [Unordered] [Multi-Index] Set lookup from something else than key_type

Subject: Re: [Boost-users] [Unordered] [Multi-Index] Set lookup from something else than key_type
From: Joaquin M Lopez Munoz (joaquin_at_[hidden])
Date: 2009-09-01 15:44:12

Dominique Devienne <ddevienne <at> gmail.com> writes:

> 
> We currently have a unordered_map< Uid, shared_ptr<Identity> >,
> where Identity already contains the Uid.
> 
> So I thought I could avoid the duplicated Uid by using an
> unordered_set< shared_ptr<Identity>, MyHash, MyPred >
> to hash/compare by the internal Uid, but unlike a Multi-Index
> hashed_index [1],unordered doesn't seem to provide:
> 
>     "lookup operations accepting search keys different from the
>     key_type of the index, which is a specially useful facility
>     when key_type object are expensive to create."
> 
> Any reason why unordered cannot allow similar "compatible key" lookups?

There is no technical reason why Boost.Unordered couldn't
provide the compatible key functionality. It just happens not
to be a feature condidered in the standard, but if you
convince the author to add it as an extension implementing it
should be trivial.

> What kind of overhead is there (memory use, runtime), if any, in using
> Multi-Index as opposed to unordered_set in this scenario?

No memory overhead, both data structures are equivalent in
terms of their internal data structures (for the unique keys
case). Speedwise both they should also perform approximately
the same, my advice is that you do some profiling to make
sure.

As you say, Boost.MultiIndex is a heavier library and compile
times will reflect that.

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo