----- Mensaje original ----- De: bert hubert <bert.hubert@netherlabs.nl> 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