Boost.MultiIndex `multi_index_container` reference

Header "boost/multi_index_container_fwd.hpp" synopsis
Header "boost/multi_index_container.hpp" synopsis
- Class template multi_index_container

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:

Value is the Assignable type of the elements contained.
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.
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<C₀,...,C_I-1>, where C_i 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<C₀,...,C_I-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_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.

Boost.MultiIndex reference

Index reference

Revised November 6th 2008

Boost.MultiIndex multi_index_container reference

Contents

Header "boost/multi_index_container_fwd.hpp" synopsis

Header "boost/multi_index_container.hpp" synopsis

Boost.MultiIndex `multi_index_container` reference

Header `"boost/multi_index_container_fwd.hpp"` synopsis

Header `"boost/multi_index_container.hpp"` synopsis