Re: [Boost-users] boost::multi_index_container different search key type

From: JOAQUIN LOPEZ MU?Z (joaquin_at_[hidden])
Date: 2006-05-03 17:26:26

----- Mensaje original -----
De: bert hubert <bert.hubert_at_[hidden]>
Fecha: Miércoles, Mayo 3, 2006 8:15 pm
Asunto: [Boost-users] boost::multi_index_container different search key
        type

> Joaquin, list,
> 
> In one of the last issues of the C/C++ User's Journal, Andrei 
> Alexandrescu described the need for something better than std::map 
> when using expensive
> keys:
> 
[...]
> 
> More on http://www.ddj.com/dept/cpp/184402065 - might this be 
> something boost::multi_index_container could be made to do?
> 

Hello Bert, I'm glad you asked, because multi_index_container
already provides this, and I would dare say in a more powerful
fashion. Ordered and hashed indices lookup member functions
(find, equal_range, etc.) are overloaded to accept *compatible
keys*, which can be used to pass alternate representations of
keys in exactly the same manner as described in Andrei's
article. Compatible keys are introduced at

http://tinyurl.com/rouet

and formally described at

http://tinyurl.com/hp9j4 (ordered indices)
http://tinyurl.com/ze5od (hashed indices)

But there is more: in the case of ordered indices, compatible
keys need not be in a 1-to-1 relation with the original keys,
but can be "coarser", in a sense. An example can help clarify
this: Suppose we've got an index ordered by a date, with
millisecond precision, then the index is certainly ordered
by year; compatible key support can be thus used to perform
lookup by year if only we provide the appropriate
comparison semantics between full dates and years, so
that "year" is a compatible key of "date".

Although it might not be apparent, composite keys take
full advantage of all of this:

  * When you pass a tuple to lookup on some composite_key-
  enabled index, the tuple is *not* the index key_type, but
  merely a more convenient representation.
  * Compatible key support (in the "coarser key" sense) is
  used when you do "partial searches" in which only the first
  tuple values are specified: see http://tinyurl.com/hdf3q.

When Andrei's article first came out, I contacted him to discuss
these concepts and the similarities between his ÜberContainers
and compatible key support as provided by B.MI: IMHO it is not
unusual that these sort of ideas come up recurrently.

Thanks for your active interest in Boost.MultiIndex!

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