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

    • 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;
template<typename MultiIndexContainer,int N> struct nth_index_const_iterator;
template<typename MultiIndexContainer,typename Tag> struct index_iterator;
template<typename MultiIndexContainer,typename Tag> struct index_const_iterator;

// 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_iterator<
  multi_index_container<Value,IndexSpecifierList,Allocator>,N
>::type
project(
  multi_index_container<Value,IndexSpecifierList,Allocator>& m,
  IteratorType it);

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

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

template<
  typename Tag,typename IteratorType,
  typename Value,typename IndexSpecifierList,typename Allocator
>
typename index_const_iterator<
  multi_index_container<Value,IndexSpecifierList,Allocator>,Tag
>::type
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       {typedef implementation defined type;};
  template<int N>
  struct nth_index_const_iterator {typedef implementation defined type;};
  template<typename Tag>
  struct index_iterator           {typedef implementation defined type;};
  template<typename Tag>
  struct index_const_iterator     {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());
  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_iterator<N>::type project(IteratorType it);
  template<int N,typename IteratorType>
    typename nth_index_const_iterator<N>::type project(IteratorType it)const;
  template<typename Tag,typename IteratorType>
    typename index_iterator<Tag>::type project(IteratorType it);
  template<typename Tag,typename IteratorType>
    typename index_const_iterator<Tag>::type 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
{
  typedef typename MultiIndexContainer::nth_index_iterator<N>::type type;
};

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

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

template<typename MultiIndexContainer,typename Tag> struct index_const_iterator
{
  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_iterator<
  multi_index_container<Value,IndexSpecifierList,Allocator>,N
>::type
project(
  multi_index_container<Value,IndexSpecifierList,Allocator>& m,
  IteratorType it)
{
  return m.project<N>(it);
}

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

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

template<
  typename Tag,typename IteratorType,
  typename Value,typename IndexSpecifierList,typename Allocator
>
typename index_const_iterator<
  multi_index_container<Value,IndexSpecifierList,Allocator>,Tag
>::type
project(
  const multi_index_container<Value,IndexSpecifierList,Allocator>& m,
  IteratorType it)
{
  return m.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, 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 comply with the C++ requirements for allocators [lib.allocator.requirements].

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.

template<int N> struct nth_index_const_iterator

nth_index_const_iterator<N>::type is equivalent to nth_index<N>::type::const_iterator.

template<typename Tag> struct index_iterator

index_iterator<Tag>::type is equivalent to index<Tag>::type::iterator.

template<typename Tag> struct index_const_iterator

index_const_iterator<Tag>::type is equivalent to index<Tag>::type::const_iterator.

Constructors, copy and assignment

explicit multi_index_container(
 &nbs  const allocator_type& al=allocator_type()); 

Effects: Constructs an empty multi_index_container using the specified argument list and allocator.
Complexity: Constant.

template<typename InputIterator>
multi_index_container(
  InputIterator first,InputIterator last,
  const ctor_args_list& comp=ctor_a  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).

mu  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,Index  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_iterator<N>::type 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_iterator<N>::type iterator equivalent to it.
Complexity: Constant.
Exception safety: nothrow.

template<int N,typename IteratorType>
typename nth_index_const_iterator<N>::type 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_const_iterator<N>::type iterator equivalent to it.
Complexity: Constant.
Exception safety: nothrow.

template<typename Tag,typename IteratorType>
typename index_iterator<Tag>::type project(IteratorType it); 

Requires: Tag is such that index_iterator<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_iterator<Tag>::type iterator equivalent to it.
Complexity: Constant.
Exception safety: nothrow.

template<typename Tag,typename IteratorType>
typename index_const_iterator<Tag>::type project(IteratorType it)const; 

Requires: Tag is such that index_const_iterator<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_const_iterator<Tag>::type 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, 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, 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.