# Boost.MultiIndex `multi_index_container` reference

Boost.MultiIndex reference
Boost.MultiIndex reference
Index reference

## Contents

- Header `"boost/multi_index_container_fwd.hpp"` synopsis
- Header `"boost/multi_index_container.hpp"` synopsis
  - Class template `multi_index_container`
    - Complexity
    - Instantiation types
    - Nested types
    - Nested class templates
    - Constructors, copy and assignment
    - Index retrieval operations
    - Projection operations
    - Serialization

## 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

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

>       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(
>         const 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);

>       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 `Assignable` type of the elements contained.
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 [lib.allocator.requirements]. The following relaxations to the standard requirements are allowed:
   - Non-equal allocator instances are supported: swapping two non-equal instances must not throw any exception.
   - For every type `T`, the type `Allocator::rebind<T>::other::pointer` can be any kind of `Random Access Iterator`, provided that it is explicitly constructible from the literal `0` (standing here as the null pointer) or from any `p` of type `T*` pointing into an area allocated by some instance of `Allocator` or some other allocator type rebound from `Allocator`. A `pointer` constructed from `p` shall dereference to `*p`.

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 `Default Constructible`, provided that all `ctor_args` types involved are default constructible.

`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& comp=ctor_args_list(),
const allocator_type& al=allocator_type());`

> Requires: `InputIterator` is a model of `Input Iterator` over elements of type `Value` or a type convertible to `Value`. `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(
const multi_index_container<Value,IndexSpecifierList,Allocator>& x);`

> Effects: Constructs a copy of `x`, copying its elements as well as its internal objects (key extractors, comparison objects, 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()`

> 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);`

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

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

- `it1==i1.end()` AND `it2==i2.end()`,
- OR `it1` and `it2` point to the same element.

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

Boost.MultiIndex reference
Boost.MultiIndex reference
Index reference

Revised November 6th 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)