Boost.MultiIndex Index referenceBoost.MultiIndex Index reference
"boost/multi_index/indexed_by.hpp" synopsis
"boost/multi_index/tag.hpp" synopsis
multi_index_container instantiations comprise one or more indices
specified at compile time. Each index allows read/write access to the elements
contained in a definite manner. For instance,
ordered indices
provide a set-like interface to the elements, whereas
sequenced indices mimic the functionality
of std::list.
Indices are not isolated objects, and so cannot be constructed on their
own. Rather they are embedded into a multi_index_container as specified by
means of an index specifier. The name of
the index class implementation proper is never directly exposed to the user, who
has only access to the associated index specifier.
Insertion and erasing of elements are always performed through the
appropriate interface of some index of the multi_index_container;
these operations, however, do have an impact on all other indices as
well: for instance, insertion through a given index may fail because
there exists another index which bans the operation in order to preserve
its invariant (like uniqueness of elements.) This circumstance, rather
than an obstacle, yields much of the power of Boost.MultiIndex:
equivalent constructions based on manual composition of standard
containers would have to add a fair amount of code in order to
globally preserve the invariants of each container while guaranteeing
that all of them are synchronized. The global operations performed
in a joint manner among the various indices can be reduced to
six primitives:
multi_index_container are not mutable.
To overcome this restriction, indices expose member functions
for updating and modifying, which allow for the mutation of elements
in a controlled fashion. Immutability of elements does not significantly
impact the interface of ordered indices, as it is based upon that of
std::set and std:multiset, and these containers
also have non-mutable elements; but it may come as a surprise when dealing
with sequenced indices, which are designed upon the functionality provided
by std::list.
These global operations are not directly exposed to the user, but rather
they are wrapped as appropriate by each index (for instance, ordered indices
provide a set-like suite of insertion member functions, whereas sequenced
indices do have push_back and push_front
operations.) Boost.MultiIndex poses no particular conditions on
the interface of indices, save that they must model
Container (without the requirement of being
Assignable.)
Some member functions of an index interface are implemented by
global primitives from the list above. Complexity of these operations
thus depends on all indices of a given multi_index_container, not just
the currently used index.
In order to establish complexity estimates, an index is characterized by its complexity signature, consisting of the following associated functions on the number of elements:
c(n): copying,
i(n): insertion,
h(n): hinted insertion,
d(n): deletion,
r(n): replacement,
m(n): modifying.
multi_index_container
with N indices labelled 0,...,N-1
whose complexity signatures are
(ci,ii,hi,di,ri,mi);
the insertion of an element in such a container is then of complexity
O(i0(n)+···+iN-1(n)) where n
is the number of elements. To abbreviate notation, we adopt the
following definitions:
C(n)=c0(n)+···+cN-1(n),I(n)=i0(n)+···+iN-1(n),H(n)=h0(n)+···+hN-1(n),D(n)=d0(n)+···+dN-1(n),R(n)=r0(n)+···+rN-1(n),M(n)=m0(n)+···+mN-1(n).multi_index_container with two ordered indices,
for which i(n)=log(n), and a sequenced index with i(n)=1
(constant time insertion). Insertion of an element into this multi_index_container
is then of complexity
O(I(n))=O(2*log(n)+1)=O(log(n)).
Index specifiers are passed as instantiation arguments to
multi_index_container and provide the information needed to incorporate
the corresponding indices. Future releases of Boost.MultiIndex may allow for
specification of user-defined indices. Meanwhile, the requirements for an index
specifier remain implementation defined. Currently, Boost.MultiIndex provides the
index specifiers
ordered_unique and
ordered_non_unique for
ordered indices,hashed_unique and
hashed_non_unique for
hashed indices,sequenced for
sequenced indices."boost/multi_index/indexed_by.hpp" synopsisnamespace boost{ namespace multi_index{ template<typename T0,...,typename Tn> struct indexed_by; } // namespace boost::multi_index } // namespace boost
indexed_by
indexed_by is a model of
MPL Random Access Sequence and
MPL Extensible Sequence meant to be used to specify a
compile-time list of indices as the IndexSpecifierList of
multi_index_container.
template<typename T0,...,typename Tn> struct indexed_by;
Each user-provided element of indexed_list must be an index
specifier. At least an element must be provided. The maximum number of elements
of an indexed_by sequence is implementation defined.
Tags are just conventional types used as mnemonics for indices of an
multi_index_container, as for instance in member function get.
Each index can have none, one or more tags associated. The way tags are assigned
to a given index is dependent on the particular index specifier. However,
for convenience all indices of Boost.MultiIndex support tagging through the
class template tag.
"boost/multi_index/tag.hpp" synopsisnamespace boost{ namespace multi_index{ template<typename T0,...,typename Tn> struct tag; } // namespace boost::multi_index } // namespace boost
tag
tag is a typelist construct used to specify a compile-time
sequence of tags to be assigned to an index in instantiation time.
template<typename T0,...,typename Tn> struct tag;
Elements of tag can be any type, though the user is expected
to provide classes with mnemonic names. Duplicate elements are not allowed.
The maximum number of elements of a tag instantiation is
implementation defined.
Indices of this type are organized around keys obtained from the elements, as described in the key extraction reference.
Revised May 30th 2005
© Copyright 2003-2005 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)