Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

Boost.MultiIndex Tutorial: Techniques



Contents

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::multisets 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::multisets, but rather a std::pair<iterator,bool> in the spirit of std::sets. In this particular case, however, the bool member of the returned pair is always true.

The case of std::maps and std::multimaps 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::maps and std::multimaps. 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:

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;



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)