...one of the most highly
regarded and expertly designed C++ library projects in the
world.

— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards

`multi_index_container`

Academic movitations aside, there is a practical interest in emulating standard
associative containers by means of `multi_index_container`

, namely to take
advantage of extended functionalities provided by `multi_index_container`

for
lookup, range querying and updating.

In order to emulate a `std::set`

one can follow the substitution
rule:

std::set<Key,Compare,Allocator> -> multi_index_container< Key, indexed_by<ordered_unique<identity<Key>,Compare> >, Allocator >

In the default case where `Compare=std::less<Key>`

and
`Allocator=std::allocator<Key>`

, the substitution rule is
simplified as

std::set<Key> -> multi_index_container<Key>

The substitution of `multi_index_container`

for `std::set`

keeps
the whole set of functionality provided by `std::set`

, so in
principle it is a drop-in replacement needing no further adjustments.

`std::multiset`

can be emulated in a similar manner, according to the
following rule:

std::multiset<Key,Compare,Allocator> -> multi_index_container< Key, indexed_by<ordered_non_unique<identity<Key>,Compare> >, Allocator >

When default values are taken into consideration, the rule takes the form

std::multiset<Key> -> multi_index_container< Key, indexed_by<ordered_non_unique<identity<Key> > > >

The emulation of `std::multiset`

s with `multi_index_container`

results in a slight difference with respect to the interface offered: the member
function `insert(const value_type&)`

does not return an
`iterator`

as in `std::multiset`

s, but rather a
`std::pair<iterator,bool>`

in the spirit of `std::set`

s.
In this particular case, however, the `bool`

member of the returned
pair is always `true`

.

The case of `std::map`

s and `std::multimap`

s does not lend
itself to such a direct emulation by means of `multi_index_container`

. The main
problem lies in the fact that elements of a `multi_index_container`

are treated
as constant, while the `std::map`

and `std::multimap`

handle
objects of type `std::pair<const Key,T>`

, thus allowing for free
modification of the value part. To overcome this difficulty we need to create an ad
hoc pair class:

template <typename T1,typename T2> struct mutable_pair { typedef T1 first_type; typedef T2 second_type; mutable_pair():first(T1()),second(T2()){} mutable_pair(const T1& f,const T2& s):first(f),second(s){} mutable_pair(const std::pair<T1,T2>& p):first(p.first),second(p.second){} T1 first; mutable T2 second; };

and so the substitution rules are:

std::map<Key,T,Compare,Allocator> -> multi_index_container< Element, indexed_by< ordered_unique<member<Element,Key,&Element::first>,Compare> >, typename Allocator::template rebind<Element>::other > std::multimap<Key,T,Compare,Allocator> -> multi_index_container< Element, indexed_by< ordered_non_unique<member<Element,Key,&Element::first>,Compare> >, typename Allocator::template rebind<Element>::other > (with Element=mutable_pair<Key,T>)

If default values are considered, the rules take the form:

std::map<Key,T> -> multi_index_container< Element, indexed_by<ordered_unique<member<Element,Key,&Element::first> > > > std::multimap<Key,T> -> multi_index_container< Element, indexed_by<ordered_non_unique<member<Element,Key,&Element::first> > > > (with Element=mutable_pair<Key,T>)

Unlike as with standard sets, the interface of these `multi_index_container`

-emulated
maps does not exactly conform to that of `std::map`

s and
`std::multimap`

s. The most obvious difference is the lack of
`operator []`

, either in read or write mode; this, however, can be
emulated with appropriate use of `find`

and `insert`

.

These emulations of standard associative containers with `multi_index_container`

are comparable to the original constructs in terms of space and time efficiency.
See the performance section for further details.

`std::list`

Unlike the case of associative containers, emulating `std::list`

in Boost.MultiIndex does not add any significant functionality, so the following
is presented merely for completeness sake.

Much as with standard maps, the main difficulty to overcome when emulating
`std::list`

derives from the constant nature of elements of a
`multi_index_container`

. Again, some sort of adaption class is needed, like
for instance the following:

template <typename T> struct mutable_value { mutable_value(const T& t):t(t){} operator T&()const{return t;} private: mutable T t; };

which allows us to use the substitution rule:

std::list<T,Allocator> -> multi_index_container< Element, indexed_by<sequenced<> >, typename Allocator::template rebind<Element>::other > (with Element=mutable_value<T>)

or, if the default value `Allocator=std::allocator<T>`

is used:

std::list<T> -> multi_index_container<mutable_value<T>,indexed_by<sequenced<> > >

`multi_index_container`

Boost.MultiIndex provides a number of facilities intended to allow the analysis and
synthesis of `multi_index_container`

instantiations by
MPL metaprograms.

Given a `multi_index_container`

instantiation, the following nested types are
provided for compile-time inspection of the various types occurring in the
definition of the `multi_index_container`

:

`index_specifier_type_list`

,`index_type_list`

,`iterator_type_list`

,`const_iterator_type_list`

.

`multi_index_container`

: for instance, the `n`

-th
element of `iterator_type_list`

is the same as
`nth_index<n>::type::iterator`

.
A subtle but important distinction exists between
`index_specifier_type_list`

and `index_type_list`

:
the former typelist holds the index *specifiers*
with which the `multi_index_container`

instantiation was defined,
while the latter gives access to the actual implementation classes
corresponding to each specifier. An example will help to clarify
this distinction. Given the instantiation:

typedef multi_index_container< int, indexed_by< ordered_unique<identity<int> >, sequenced<> > > indexed_t;

`indexed_t::index_specifier_type_list`

is a type list with
elements

ordered_unique<identity<int> > sequenced<>

while `indexed_t::index_type_list`

holds the types

multi_index_container::nth_type<0>::type multi_index_container::nth_type<1>::type

so the typelists are radically different. Check the reference for the exact MPL sequence concepts modeled by these type lists.

Although typically indices are specified by means of the
`indexed_by`

construct, actually any MPL sequence of
index specifiers can be provided instead:

typedef mpl::vector<ordered_unique<identity<int> >,sequenced<> > index_list_t; typedef multi_index_container< int, index_list_t > indexed_t;

This possibility enables the synthesis of instantiations of
`multi_index_container`

through MPL metaprograms, as the following
example shows:

// original multi_index_container instantiation typedef multi_index_container< int, indexed_by< ordered_unique<identity<int> > > > indexed_t1; // we take its index list and add an index typedef boost::mpl::push_front< indexed_t1::index_specifier_type_list, sequenced<> >::type index_list_t; // augmented multi_index_container typedef multi_index_container< int, index_list_t > indexed_t2;

Revised November 7th 2008

© Copyright 2003-2008 Joaquín M López Muñoz. Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)