# Boost.MultiIndex Tutorial: Techniques

Debugging support
Boost.MultiIndex tutorial
Boost.MultiIndex reference

## Contents

- Emulating standard containers with `multi_index_container`
  - Emulation of associative containers
  - Emulation of `std::list`
- Metaprogramming and `multi_index_container`
  - MPL analysis
  - MPL synthesis

## Emulating standard containers with `multi_index_container`

### Emulation of associative containers

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.

### Emulation of `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<> > >

## Metaprogramming and `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.

### MPL analysis

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

Each of these types is an MPL sequence with as many elements as indices comprise the `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.

### MPL synthesis

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;

Debugging support
Boost.MultiIndex tutorial
Boost.MultiIndex reference

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)