...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
multi_index_container
reference"boost/multi_index_container_fwd.hpp"
synopsis"boost/multi_index_container.hpp"
synopsis
"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.
"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
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
In the descriptions of operations of multi_index_container
, we adopt the
scheme outlined in the
complexity signature section.
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:
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
.
multi_index_container
instantiation cannot have
duplicate tags, either within a single
index or in two different indices.
ctor_args_list
Although the exact definition ofctor_args_list
is implementation defined, from the user point of view this type can be treated as equivalent to::boost::tuple<C0,...,CI-1>
, whereCi
is thector_args
type of thei
-th index held by themulti_index_container
, in the same order as they were specified. Strictly speaking, there is an implicit conversion fromconst ::boost::tuple<C0,...,CI-1>&
toconst ctor_args_list&
. This type is used for providing the construction arguments of the indices of themulti_index_container
.ctor_args_list
isDefault Constructible
, provided that allctor_args
types involved are default constructible.
index_specifier_type_list
Same type as IndexSpecifierList
.
index_type_list
Model ofMPL Random Access Sequence
andMPL Extensible Sequence
containing the types of the indices held by themulti_index_container
, in the same order as they were specified.
iterator_type_list
Model ofMPL Random Access Sequence
andMPL Extensible Sequence
containing the types of the iterators of the indices held by themulti_index_container
, in the same order as they were specified.
const_iterator_type_list
Model ofMPL Random Access Sequence
andMPL Extensible Sequence
containing the types of the constant iterators of the indices held by themulti_index_container
, in the same order as they were specified.
template<int N> struct nth_index
nth_index<N>::type
yields the type of theN
-th (0-based) index held by themulti_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 hasTag
as an associated tag type.
Requires: Some index of themulti_index_container
hasTag
as an associated tag type.
template<int N> struct nth_index_iterator
nth_index_iterator<N>::type
is equivalent tonth_index<N>::type::iterator
.
Note: The use ofnth_index_iterator
is deprecated.
template<int N> struct nth_index_const_iterator
nth_index_const_iterator<N>::type
is equivalent tonth_index<N>::type::const_iterator
.
Note: The use ofnth_index_const_iterator
is deprecated.
template<typename Tag> struct index_iterator
index_iterator<Tag>::type
is equivalent toindex<Tag>::type::iterator
.
Note: The use ofindex_iterator
is deprecated.
template<typename Tag> struct index_const_iterator
index_const_iterator<Tag>::type
is equivalent toindex<Tag>::type::const_iterator
.
Note: The use ofindex_const_iterator
is deprecated.
explicit multi_index_container(
const ctor_args_list& args_list=ctor_args_list(),
const allocator_type& al=allocator_type());
Effects: Constructs an emptymulti_index_container
using the specified argument list and allocator.
Complexity: Constant.
explicit multi_index_container(const allocator_type& al);
Effects: Constructs an emptymulti_index_container
using the specified allocator and the default value ofctor_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 ofInput Iterator
over elements of typeValue
or a type convertible toValue
.last
is reachable fromfirst
.
Effects: Constructs and emptymulti_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 themulti_index_container
.
Complexity:O(m*H(m))
, wherem
is the number of elements in [first
,last
).
multi_index_container(
const multi_index_container<Value,IndexSpecifierList,Allocator>& x);
Effects: Constructs a copy ofx
, copying its elements as well as its internal objects (key extractors, comparison objects, allocator.)
Postconditions:*this==x
. The order on every index of themulti_index_container
is preserved as well.
Complexity:O(x.size()*log(x.size()) + C(x.size()))
.
~multi_index_container()
Effects: Destroys themulti_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 themulti_index_container
with copies fromx
.
Postconditions:*this==x
. The order on every index of themulti_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 ofctor_args_list
do not throw.
allocator_type get_allocator()const;
Returns a copy of theallocator_type
object used to construct themulti_index_container
.
Complexity: Constant.
template<int N> typename nth_index<N>::type& get();
Requires:0 <= N < I
.
Effects: Returns a reference to thenth_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 aconst
reference to thenth_index<N>::type
index held by*this
.
Complexity: Constant.
Exception safety:nothrow
.
template<typename Tag> typename index<Tag>::type& get()
Requires:Tag
is such thatindex<Tag>::type
is valid.
Effects: Returns a reference to theindex<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 thatindex<Tag>::type
is valid.
Effects: Returns aconst
reference to theindex<Tag>::type
index held by*this
.
Complexity: Constant.
Exception safety:nothrow
.
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()
,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 toiterator_type_list
.it
is a valid iterator of some index of*this
(i.e. does not refer to some othermulti_index_container
.)
Effects: Returns annth_index<N>::type::iterator
equivalent toit
.
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 toconst_iterator_type_list
oriterator_type_list
.it
is a valid (constant or non-constant) iterator of some index of*this
(i.e. does not refer to some othermulti_index_container
.)
Effects: Returns annth_index<N>::type::const_iterator
equivalent toit
.
Complexity: Constant.
Exception safety:nothrow
.
template<typename Tag,typename IteratorType>
typename index<Tag>::type::iterator project(IteratorType it);
Requires:Tag
is such thatindex<Tag>::type
is valid.IteratorType
belongs toiterator_type_list
.it
is a valid iterator of some index of*this
(i.e. does not refer to some othermulti_index_container
.)
Effects: Returns anindex<Tag>::type::iterator
equivalent toit
.
Complexity: Constant.
Exception safety:nothrow
.
template<typename Tag,typename IteratorType>
typename index<Tag>::type::const_iterator project(IteratorType it)const;
Requires:Tag
is such thatindex<Tag>::type
is valid.IteratorType
belongs toconst_iterator_type_list
oriterator_type_list
.it
is a valid (constant or non-constant) iterator of some index of*this
(i.e. does not refer to some othermulti_index_container
.)
Effects: Returns anindex<Tag>::type::const_iterator
iterator equivalent toit
.
Complexity: Constant.
Exception safety:nothrow
.
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:Operation: loading of aValue
is serializable (XML-serializable). Additionally, each of the indices ofm
can impose another requirements.
Exception safety: Strong with respect tom
. If an exception is thrown,ar
may be left in an inconsistent state.
multi_index_container
m'
from an
input archive (XML archive) ar
.
Requires:Value
is serializable (XML-serializable). Additionally, each of the indices ofm'
can impose another requirements.
Exception safety: Basic. If an exception is thrown,ar
may be left in an inconsistent state.
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)