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



Contents

Header "boost/multi_index_container_fwd.hpp" synopsis

namespace boost{

namespace multi_index{

template<
  typename Value,
  typename IndexSpecifierList=indexed_by<ordered_unique<identity<Value> > >,
  typename Allocator=std::allocator<Value> >
class multi_index_container;

} // namespace boost::multi_index 

using multi_index::multi_index_container;

} // namespace boost

multi_index_container_fwd.hpp forward declares the class template multi_index_container and specifies its default parameters.

Header "boost/multi_index_container.hpp" synopsis

#include <initializer_list>

namespace boost{

namespace multi_index{

template<typename Value,typename IndexSpecifierList,typename Allocator>
class multi_index_container;

// multi_index_container associated global class templates:

template<typename MultiIndexContainer,int N> struct nth_index;
template<typename MultiIndexContainer,typename Tag> struct index;

template<typename MultiIndexContainer,int N>
struct nth_index_iterator;                          // deprecated
template<typename MultiIndexContainer,int N>
struct nth_index_const_iterator;                    // deprecated
template<typename MultiIndexContainer,typename Tag>
struct index_iterator;                              // deprecated
template<typename MultiIndexContainer,typename Tag>
struct index_const_iterator;                        // deprecated

// multi_index_container global functions for index retrieval:

template<
  int N,typename Value,typename IndexSpecifierList,typename Allocator
>
typename nth_index<
  multi_index_container<Value,IndexSpecifierList,Allocator>,N
>::type&
get(multi_index_container<Value,IndexSpecifierList,Allocator>& m);

template<
  int N,typename Value,typename IndexSpecifierList,typename Allocator
>
const typename nth_index<
  multi_index_container<Value,IndexSpecifierList,Allocator>,N
>::type&
get(const multi_index_container<Value,IndexSpecifierList,Allocator>& m);

template<
  typename Tag,typename Value,typename IndexSpecifierList,typename Allocator
>
typename index<
  multi_index_container<Value,IndexSpecifierList,Allocator>,Tag
>::type&
get(multi_index_container<Value,IndexSpecifierList,Allocator>& m);

template<
  typename Tag,typename Value,typename IndexSpecifierList,typename Allocator
>
const typename index<
  multi_index_container<Value,IndexSpecifierList,Allocator>,Tag
>::type&
get(const multi_index_container<Value,IndexSpecifierList,Allocator>& m);

// multi_index_container global functions for projection of iterators:

template<
  int N,typename IteratorType,
  typename Value,typename IndexSpecifierList,typename Allocator
>
typename nth_index<
  multi_index_container<Value,IndexSpecifierList,Allocator>,N
>::type::iterator
project(
  multi_index_container<Value,IndexSpecifierList,Allocator>& m,
  IteratorType it);

template<
  int N,typename IteratorType,
  typename Value,typename IndexSpecifierList,typename Allocator
>
typename nth_index<
  multi_index_container<Value,IndexSpecifierList,Allocator>,N
>::type::const_iterator
project(
  const multi_index_container<Value,IndexSpecifierList,Allocator>& m,
  IteratorType it);

template<
  typename Tag,typename IteratorType,
  typename Value,typename IndexSpecifierList,typename Allocator
>
typename index<
  multi_index_container<Value,IndexSpecifierList,Allocator>,Tag
>::type::iterator
project(
  multi_index_container<Value,IndexSpecifierList,Allocator>& m,
  IteratorType it);

template<
  typename Tag,typename IteratorType,
  typename Value,typename IndexSpecifierList,typename Allocator
>
typename index<
  multi_index_container<Value,IndexSpecifierList,Allocator>,Tag
>::type::const_iterator
project(
  const multi_index_container<Value,IndexSpecifierList,Allocator>& m,
  IteratorType it);

// comparison:

// OP is any of ==,<,!=,>,>=,<=

template<
  typename Value1,typename IndexSpecifierList1,typename Allocator1,
  typename Value2,typename IndexSpecifierList2,typename Allocator2
>
bool operator OP(
  const multi_index_container<Value1,IndexSpecifierList1,Allocator1>& x,
  const multi_index_container<Value2,IndexSpecifierList2,Allocator2>& y);

// specialized algorithms:

template<typename Value,typename IndexSpecifierList,typename Allocator>
void swap(
  multi_index_container<Value,IndexSpecifierList,Allocator>& x,
  multi_index_container<Value,IndexSpecifierList,Allocator>& y);

} // namespace boost::multi_index 

using multi_index::multi_index_container;
using multi_index::get;
using multi_index::project;

} // namespace boost

Class template multi_index_container

This is the main component of Boost.MultiIndex. A multi_index_container is a container class template holding a compile-time user-defined list of indices. These indices provide different interfaces for the management of the elements of the multi_index_container. By itself, multi_index_container only provides basic functionality for construction and for access to the indices held.

A multi_index_container type is instantiated with the type of the elements contained and a non-empty MPL Forward Sequence specifying which indices conform the class.

For convenience of use, all public methods and types of the first index specified are inherited by multi_index_container. This also includes global operators and functions associated with the index (vg. comparison and swap.)

template<
  typename Value,
  typename IndexSpecifierList=indexed_by<ordered_unique<identity<Value> > >,
  typename Allocator=std::allocator<Value> >
class multi_index_container
{
public:

  // types:

  typedef implementation defined   ctor_args_list;
  typedef implementation defined   index_specifier_type_list;
  typedef implementation defined   index_type_list;
  typedef implementation defined   iterator_type_list;
  typedef implementation defined   const_iterator_type_list;
  typedef Allocator                allocator_type;

  // nested class templates:

  template<int N>
  struct nth_index                {typedef implementation defined type;};
  template<typename Tag>
  struct index                    {typedef implementation defined type;};

  template<int N>
  struct nth_index_iterator        // deprecated
  {typedef implementation defined type;};
  template<int N>
  struct nth_index_const_iterator  // deprecated
  {typedef implementation defined type;};
  template<typename Tag>
  struct index_iterator            // deprecated
  {typedef implementation defined type;};
  template<typename Tag>
  struct index_const_iterator      // deprecated
  {typedef implementation defined type;};
  
  // construct/copy/destroy:

  explicit multi_index_container(
    const ctor_args_list& args_list=ctor_args_list(),
    const allocator_type& al=allocator_type());
  explicit multi_index_container(const allocator_type& al);
  template<typename InputIterator>
  multi_index_container(
    InputIterator first,InputIterator last,
    const ctor_args_list& args_list=ctor_args_list(),
    const allocator_type& al=allocator_type());
  multi_index_container(
    std::initializer_list<Value> list,
    const ctor_args_list& args_list=ctor_args_list(),
    const allocator_type& al=allocator_type());
  multi_index_container(
    const multi_index_container<Value,IndexSpecifierList,Allocator>& x);
  multi_index_container(
    multi_index_container<Value,IndexSpecifierList,Allocator>&& x);

  ~multi_index_container();

  multi_index_container<Value,IndexSpecifierList,Allocator>& operator=(
    const multi_index_container<Value,IndexSpecifierList,Allocator>& x);
  multi_index_container<Value,IndexSpecifierList,Allocator>& operator=(
    multi_index_container<Value,IndexSpecifierList,Allocator>&& x);
  multi_index_container<Value,IndexSpecifierList,Allocator>& operator=(
    std::initializer_list<Value> list)

  allocator_type get_allocator()const;

  // retrieval of indices

  template<int N> typename nth_index<N>::type& get();
  template<int N> const typename nth_index<N>::type& get()const;
  template<typename Tag> typename index<Tag>::type& get()
  template<typename Tag> const typename index<Tag>::type& get()const;

  // projection of iterators

  template<int N,typename IteratorType>
    typename nth_index<N>::type::iterator project(IteratorType it);
  template<int N,typename IteratorType>
    typename nth_index<N>::type::const_iterator project(IteratorType it)const;
  template<typename Tag,typename IteratorType>
    typename index<Tag>::type::iterator project(IteratorType it);
  template<typename Tag,typename IteratorType>
    typename index<Tag>::type::const_iterator project(IteratorType it)const;
};

// multi_index_container associated global class templates:

template<typename MultiIndexContainer,int N> struct nth_index
{
  typedef typename MultiIndexContainer::nth_index<N>::type type;
};

template<typename MultiIndexContainer,typename Tag> struct index
{
  typedef typename MultiIndexContainer::index<Tag>::type type;
};

template<typename MultiIndexContainer,int N>
struct nth_index_iterator       // deprecated
{
  typedef typename MultiIndexContainer::nth_index_iterator<N>::type type;
};

template<typename MultiIndexContainer,int N>
struct nth_index_const_iterator // deprecated
{
  typedef typename MultiIndexContainer::nth_index_const_iterator<N>::type type;
};

template<typename MultiIndexContainer,typename Tag>
struct index_iterator           // deprecated
{
  typedef typename MultiIndexContainer::index_iterator<Tag>::type type;
};

template<typename MultiIndexContainer,typename Tag>
struct index_const_iterator     // deprecated
{
  typedef typename MultiIndexContainer::index_const_iterator<Tag>::type type;
};

// multi_index_container global functions for index retrieval:

template<
  int N,typename Value,typename IndexSpecifierList,typename Allocator
>
typename nth_index<
  multi_index_container<Value,IndexSpecifierList,Allocator>,N
>::type&
get(multi_index_container<Value,IndexSpecifierList,Allocator>& m)
{
  return m.get<N>();
}

template<
  int N,typename Value,typename IndexSpecifierList,typename Allocator
>
const typename nth_index<
  multi_index_container<Value,IndexSpecifierList,Allocator>,N
>::type&
get(const multi_index_container<Value,IndexSpecifierList,Allocator>& m)
{
  return m.get<N>();
}

template<
  typename Tag,typename Value,typename IndexSpecifierList,typename Allocator
>
typename index<
  multi_index_container<Value,IndexSpecifierList,Allocator>,Tag
>::type&
get(multi_index_container<Value,IndexSpecifierList,Allocator>& m)
{
  return m.get<Tag>();
}

template<
  typename Tag,typename Value,typename IndexSpecifierList,typename Allocator
>
const typename index<
  multi_index_container<Value,IndexSpecifierList,Allocator>,Tag
>::type&
get(const multi_index_container<Value,IndexSpecifierList,Allocator>& m)
{
  return m.get<Tag>();
}

// multi_index_container global functions for projection of iterators:

template<
  int N,typename IteratorType,
  typename Value,typename IndexSpecifierList,typename Allocator
>
typename nth_index<
  multi_index_container<Value,IndexSpecifierList,Allocator>,N
>::type::iterator
project(
  multi_index_container<Value,IndexSpecifierList,Allocator>& m,
  IteratorType it)
{
  return m.template project<N>(it);
}

template<
  int N,typename IteratorType,
  typename Value,typename IndexSpecifierList,typename Allocator
>
typename nth_index<
  multi_index_container<Value,IndexSpecifierList,Allocator>,N
>::type::const_iterator
project(
  const multi_index_container<Value,IndexSpecifierList,Allocator>& m,
  IteratorType it)
{
  return m.template project<N>(it);
}

template<
  typename Tag,typename IteratorType,
  typename Value,typename IndexSpecifierList,typename Allocator
>
typename index<
  multi_index_container<Value,IndexSpecifierList,Allocator>,Tag
>::type::iterator
project(
  multi_index_container<Value,IndexSpecifierList,Allocator>& m,
  IteratorType it)
{
  return m.template project<Tag>(it);
}

template<
  typename Tag,typename IteratorType,
  typename Value,typename IndexSpecifierList,typename Allocator
>
typename index<
  multi_index_container<Value,IndexSpecifierList,Allocator>,Tag
>::type::const_iterator
project(
  const multi_index_container<Value,IndexSpecifierList,Allocator>& m,
  IteratorType it)
{
  return m.template project<Tag>(it);
}

// comparison:

// OP is any of ==,<,!=,>,>=,<=

template<
  typename Value1,typename IndexSpecifierList1,typename Allocator1,
  typename Value2,typename IndexSpecifierList2,typename Allocator2
>
bool operator OP(
  const multi_index_container<Value1,IndexSpecifierList1,Allocator1>& x,
  const multi_index_container<Value2,IndexSpecifierList2,Allocator2>& y)
  {
    return get<0>(x) OP get<0>(y);
  }

// specialized algorithms:

template<typename Value,typename IndexSpecifierList,typename Allocator>
void swap(
  multi_index_container<Value,IndexSpecifierList,Allocator>& x,
  multi_index_container<Value,IndexSpecifierList,Allocator>& y)
  {
    x.swap(y);
  }

} // namespace boost::multi_index 

} // namespace boost

Complexity

In the descriptions of operations of multi_index_container, we adopt the scheme outlined in the complexity signature section.

Instantiation types

multi_index_container is instantiated with the following types:

  1. Value is the type of the elements contained. Value must be Erasable from multi_index_container.
  2. IndexSpecifierList specifies the indices that the multi_index_container is composed of. It must be a non-empty MPL Forward Sequence (and, preferrably, an MPL Random Access Sequence) of index specifiers. For syntactic convenience, the indexed_by MPL sequence can be used.
  3. Allocator must be an allocator of Value objects satisfying the associated C++ requirements at [allocator.requirements]. The following relaxations to the standard requirements are allowed:
Indices of a given multi_index_container instantiation cannot have duplicate tags, either within a single index or in two different indices.

Nested types

ctor_args_list
Although the exact definition of ctor_args_list is implementation defined, from the user point of view this type can be treated as equivalent to ::boost::tuple<C0,...,CI-1>, where Ci is the ctor_args type of the i-th index held by the multi_index_container, in the same order as they were specified. Strictly speaking, there is an implicit conversion from const ::boost::tuple<C0,...,CI-1>& to const ctor_args_list&. This type is used for providing the construction arguments of the indices of the multi_index_container. ctor_args_list is DefaultConstructible, provided that all ctor_args types involved are DefaultConstructible.
index_specifier_type_list
Same type as IndexSpecifierList.
index_type_list
Model of MPL Random Access Sequence and MPL Extensible Sequence containing the types of the indices held by the multi_index_container, in the same order as they were specified.
iterator_type_list
Model of MPL Random Access Sequence and MPL Extensible Sequence containing the types of the iterators of the indices held by the multi_index_container, in the same order as they were specified.
const_iterator_type_list
Model of MPL Random Access Sequence and MPL Extensible Sequence containing the types of the constant iterators of the indices held by the multi_index_container, in the same order as they were specified.

Nested class templates

template<int N> struct nth_index
nth_index<N>::type yields the type of the N-th (0-based) index held by the multi_index_container, in the same order as they were specified.
Requires: 0 <= N < I.
template<typename Tag> struct index
index<Tag>::type yields the type of the index which has Tag as an associated tag type.
Requires: Some index of the multi_index_container has Tag as an associated tag type.
template<int N> struct nth_index_iterator
nth_index_iterator<N>::type is equivalent to nth_index<N>::type::iterator.
Note: The use of nth_index_iterator is deprecated.
template<int N> struct nth_index_const_iterator
nth_index_const_iterator<N>::type is equivalent to nth_index<N>::type::const_iterator.
Note: The use of nth_index_const_iterator is deprecated.
template<typename Tag> struct index_iterator
index_iterator<Tag>::type is equivalent to index<Tag>::type::iterator.
Note: The use of index_iterator is deprecated.
template<typename Tag> struct index_const_iterator
index_const_iterator<Tag>::type is equivalent to index<Tag>::type::const_iterator.
Note: The use of index_const_iterator is deprecated.

Constructors, copy and assignment

explicit multi_index_container(
  const ctor_args_list& args_list=ctor_args_list(),
  const allocator_type& al=allocator_type());
Effects: Constructs an empty multi_index_container using the specified argument list and allocator.
Complexity: Constant.
explicit multi_index_container(const allocator_type& al);
Effects: Constructs an empty multi_index_container using the specified allocator and the default value of ctor_args_list.
Complexity: Constant.
template<typename InputIterator>
multi_index_container(
  InputIterator first,InputIterator last,
  const ctor_args_list& args_list=ctor_args_list(),
  const allocator_type& al=allocator_type());
Requires: InputIterator is an input iterator. Value is EmplaceConstructible into multi_index_container from *first. last is reachable from first.
Effects: Constructs and empty multi_index_container using the specified argument list and allocator and fills it with the elements in the range [first,last). Insertion of each element may or may not succeed depending on the acceptance by all the indices of the multi_index_container.
Complexity: O(m*H(m)), where m is the number of elements in [first,last).
multi_index_container(
  std::initializer_list<Value> list,
  const ctor_args_list& args_list=ctor_args_list(),
  const allocator_type& al=allocator_type());
Effects: Equivalent to multi_index_container(list.begin(),list.end(),args_list,al).
multi_index_container(
  const multi_index_container<Value,IndexSpecifierList,Allocator>& x);
Requires: Value is CopyInsertable into multi_index_container.
Effects: Constructs a copy of x, copying its elements as well as its internal objects (those specified in ctor_args_list and the allocator.)
Postconditions: *this==x. The order on every index of the multi_index_container is preserved as well.
Complexity: O(x.size()*log(x.size()) + C(x.size())).
multi_index_container(
  multi_index_container<Value,IndexSpecifierList,Allocator>&& x);
Effects: Constructs a multi_index_container by moving the elements of x and copying its internal objects (those specified in ctor_args_list and the allocator.)
Postconditions: If x==y just before the movement, *this==y. The order on every index of the multi_index_container is preserved as well.
Complexity: Constant.
~multi_index_container()
Effects: Destroys the multi_index_container and all the elements contained. The order in which the elements are destroyed is not specified.
Complexity: O(n).
multi_index_container<Value,IndexSpecifierList,Allocator>& operator=(
  const multi_index_container<Value,IndexSpecifierList,Allocator>& x);
Requires: Value is CopyInsertable into multi_index_container.
Effects: Replaces the elements and internal objects of the multi_index_container with copies from x.
Postconditions: *this==x. The order on every index of the multi_index_container is preserved as well.
Returns: *this.
Complexity: O(n + x.size()*log(x.size()) + C(x.size())).
Exception safety: Strong, provided the copy and assignment operations of the types of ctor_args_list do not throw.
multi_index_container<Value,IndexSpecifierList,Allocator>& operator=(
  multi_index_container<Value,IndexSpecifierList,Allocator>&& x);
Effects: Replaces the elements of multi_index_container with those of x and its internal objects with copies from the corresponding objects in x.
Postconditions: If x==y just before the movement, *this==y. The order on every index of the multi_index_container is preserved as well.
Returns: *this.
Complexity: O(n).
Exception safety: Strong, provided the copy and assignment operations of the types of ctor_args_list do not throw.
multi_index_container<Value,IndexSpecifierList,Allocator>& operator=(
  std::initializer_list<Value> list);
Requires: Value is CopyInsertable into multi_index_container.
Effects: Replaces the elements the multi_index_container with copies of the elements of list, inserted in the specified order. Insertion of each element may or may not succeed depending on the acceptance by all the indices of the multi_index_container.
Returns: *this.
Complexity: O(n + I(m)), where m is the number of elements of list.
Exception safety: Strong, provided the copy and assignment operations of the types of ctor_args_list do not throw.
allocator_type get_allocator()const;
Returns a copy of the allocator_type object used to construct the multi_index_container.
Complexity: Constant.

Index retrieval operations

template<int N> typename nth_index<N>::type& get();
Requires: 0 <= N < I.
Effects: Returns a reference to the nth_index<N>::type index held by *this.
Complexity: Constant.
Exception safety: nothrow.
template<int N> const typename nth_index<N>::type& get()const;
Requires: 0 <= N < I.
Effects: Returns a const reference to the nth_index<N>::type index held by *this.
Complexity: Constant.
Exception safety: nothrow.
template<typename Tag> typename index<Tag>::type& get()
Requires: Tag is such that index<Tag>::type is valid.
Effects: Returns a reference to the index<Tag>::type index held by *this.
Complexity: Constant.
Exception safety: nothrow.
template<typename Tag> const typename index<Tag>::type& get()const;
Requires: Tag is such that index<Tag>::type is valid.
Effects: Returns a const reference to the index<Tag>::type index held by *this.
Complexity: Constant.
Exception safety: nothrow.

Projection operations

Given a multi_index_container with indices i1 and i2, we say than an i1-iterator it1 and an i2-iterator it2 are equivalent if:

template<int N,typename IteratorType>
typename nth_index<N>::type::iterator project(IteratorType it);
Requires: 0 <= N < I. IteratorType belongs to iterator_type_list. it is a valid iterator of some index of *this (i.e. does not refer to some other multi_index_container.)
Effects: Returns an nth_index<N>::type::iterator equivalent to it.
Complexity: Constant.
Exception safety: nothrow.
template<int N,typename IteratorType>
typename nth_index<N>::type::const_iterator project(IteratorType it)const;
Requires: 0 <= N < I. IteratorType belongs to const_iterator_type_list or iterator_type_list. it is a valid (constant or non-constant) iterator of some index of *this (i.e. does not refer to some other multi_index_container.)
Effects: Returns an nth_index<N>::type::const_iterator equivalent to it.
Complexity: Constant.
Exception safety: nothrow.
template<typename Tag,typename IteratorType>
typename index<Tag>::type::iterator project(IteratorType it);
Requires: Tag is such that index<Tag>::type is valid. IteratorType belongs to iterator_type_list. it is a valid iterator of some index of *this (i.e. does not refer to some other multi_index_container.)
Effects: Returns an index<Tag>::type::iterator equivalent to it.
Complexity: Constant.
Exception safety: nothrow.
template<typename Tag,typename IteratorType>
typename index<Tag>::type::const_iterator project(IteratorType it)const;
Requires: Tag is such that index<Tag>::type is valid. IteratorType belongs to const_iterator_type_list or iterator_type_list. it is a valid (constant or non-constant) iterator of some index of *this (i.e. does not refer to some other multi_index_container.)
Effects: Returns an index<Tag>::type::const_iterator iterator equivalent to it.
Complexity: Constant.
Exception safety: nothrow.

Serialization

multi_index_containers can be archived/retrieved by means of Boost.Serialization. Boost.MultiIndex does not expose a public serialization interface, as this is provided by Boost.Serialization itself. Both regular and XML archives are supported.

Each of the indices comprising a given multi_index_container contributes its own preconditions as well as guarantees on the retrieved containers. In describing these, the following concepts are used. A type T is serializable (resp. XML-serializable) if any object of type T can be saved to an output archive (XML archive) and later retrieved from an input archive (XML archive) associated to the same storage. If x' of type T is loaded from the serialization information saved from another object x, we say that x' is a restored copy of x. Given a binary predicate Pred over (T, T), and objects p and q of type Pred, we say that q is serialization-compatible with p if

p(x,y) == q(x',y')
for every x and y of type T and x' and y' being restored copies of x and y, respectively.

Operation: saving of a multi_index_container m to an output archive (XML archive) ar.
Requires: Value is serializable (XML-serializable). Additionally, each of the indices of m can impose another requirements.
Exception safety: Strong with respect to m. If an exception is thrown, ar may be left in an inconsistent state.
Operation: loading of a multi_index_container m' from an input archive (XML archive) ar.
Requires: Value is serializable (XML-serializable). Additionally, each of the indices of m' can impose another requirements.
Exception safety: Basic. If an exception is thrown, ar may be left in an inconsistent state.



Revised July 3rd 2013

© Copyright 2003-2013 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)