Boost logo

Boost Users :

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

> 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 - 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

and formally described at (ordered indices) (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

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

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at