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

Click here to view the latest version of this page.

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

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

Template class 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, 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 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
MPL Forward Sequence containing the types of the index specifiers used in the instantiation of the multi_index_container, in the same order as they were provided.
index_type_list
MPL Forward Sequence containing the types of the indices held by the multi_index_container, in the same order as they were specified.
iterator_type_list
MPL Forward 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
MPL Forward 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(
  const ctor_args_list& comp=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.
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*D(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*D(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:

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.



Revised May 28th 2004

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