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
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
multi_index_container
Academic movitations aside, there is a practical interest in emulating standard
associative containers by means of multi_index_container, namely to take
advantage of extended functionalities provided by multi_index_container for
lookup, range querying and updating.
In order to emulate a std::set one can follow the substitution
rule:
std::set<Key,Compare,Allocator> -> multi_index_container< Key, indexed_by<ordered_unique<identity<Key>,Compare> >, Allocator >
In the default case where Compare=std::less<Key> and
Allocator=std::allocator<Key>, the substitution rule is
simplified as
std::set<Key> -> multi_index_container<Key>
The substitution of multi_index_container for std::set keeps
the whole set of functionality provided by std::set, so in
principle it is a drop-in replacement needing no further adjustments.
std::multiset can be emulated in a similar manner, according to the
following rule:
std::multiset<Key,Compare,Allocator> -> multi_index_container< Key, indexed_by<ordered_non_unique<identity<Key>,Compare> >, Allocator >
When default values are taken into consideration, the rule takes the form
std::multiset<Key> -> multi_index_container< Key, indexed_by<ordered_non_unique<identity<Key> > > >
The emulation of std::multisets with multi_index_container
results in a slight difference with respect to the interface offered: the member
function insert(const value_type&) does not return an
iterator as in std::multisets, but rather a
std::pair<iterator,bool> in the spirit of std::sets.
In this particular case, however, the bool member of the returned
pair is always true.
The case of std::maps and std::multimaps does not lend
itself to such a direct emulation by means of multi_index_container. The main
problem lies in the fact that elements of a multi_index_container are treated
as constant, while the std::map and std::multimap handle
objects of type std::pair<const Key,T>, thus allowing for free
modification of the value part. To overcome this difficulty we need to create an ad
hoc pair class:
template <typename T1,typename T2> struct mutable_pair { typedef T1 first_type; typedef T2 second_type; mutable_pair():first(T1()),second(T2()){} mutable_pair(const T1& f,const T2& s):first(f),second(s){} mutable_pair(const std::pair<T1,T2>& p):first(p.first),second(p.second){} T1 first; mutable T2 second; };
and so the substitution rules are:
std::map<Key,T,Compare,Allocator> -> multi_index_container< Element, indexed_by< ordered_unique<member<Element,Key,&Element::first>,Compare> >, typename Allocator::template rebind<Element>::other > std::multimap<Key,T,Compare,Allocator> -> multi_index_container< Element, indexed_by< ordered_non_unique<member<Element,Key,&Element::first>,Compare> >, typename Allocator::template rebind<Element>::other > (with Element=mutable_pair<Key,T>)
If default values are considered, the rules take the form:
std::map<Key,T> -> multi_index_container< Element, indexed_by<ordered_unique<member<Element,Key,&Element::first> > > > std::multimap<Key,T> -> multi_index_container< Element, indexed_by<ordered_non_unique<member<Element,Key,&Element::first> > > > (with Element=mutable_pair<Key,T>)
Unlike as with standard sets, the interface of these multi_index_container-emulated
maps does not exactly conform to that of std::maps and
std::multimaps. The most obvious difference is the lack of
operator [], either in read or write mode; this, however, can be
emulated with appropriate use of find and insert.
These emulations of standard associative containers with multi_index_container
are comparable to the original constructs in terms of space and time efficiency.
See the performance section for further details.
std::list
Unlike the case of associative containers, emulating std::list
in Boost.MultiIndex does not add any significant functionality, so the following
is presented merely for completeness sake.
Much as with standard maps, the main difficulty to overcome when emulating
std::list derives from the constant nature of elements of a
multi_index_container. Again, some sort of adaption class is needed, like
for instance the following:
template <typename T> struct mutable_value { mutable_value(const T& t):t(t){} operator T&()const{return t;} private: mutable T t; };
which allows us to use the substitution rule:
std::list<T,Allocator> -> multi_index_container< Element, indexed_by<sequenced<> >, typename Allocator::template rebind<Element>::other > (with Element=mutable_value<T>)
or, if the default value Allocator=std::allocator<T> is used:
std::list<T> -> multi_index_container<mutable_value<T>,indexed_by<sequenced<> > >
multi_index_container
Boost.MultiIndex provides a number of facilities intended to allow the analysis and
synthesis of multi_index_container instantiations by
MPL metaprograms.
Given a multi_index_container instantiation, the following nested types are
provided for compile-time inspection of the various types occurring in the
definition of the multi_index_container:
index_specifier_type_list,index_type_list,iterator_type_list,const_iterator_type_list.multi_index_container: for instance, the n-th
element of iterator_type_list is the same as
nth_index<n>::type::iterator.
A subtle but important distinction exists between
index_specifier_type_list and index_type_list:
the former typelist holds the index specifiers
with which the multi_index_container instantiation was defined,
while the latter gives access to the actual implementation classes
corresponding to each specifier. An example will help to clarify
this distinction. Given the instantiation:
typedef multi_index_container< int, indexed_by< ordered_unique<identity<int> >, sequenced<> > > indexed_t;
indexed_t::index_specifier_type_list is a type list with
elements
ordered_unique<identity<int> > sequenced<>
while indexed_t::index_type_list holds the types
multi_index_container::nth_type<0>::type multi_index_container::nth_type<1>::type
so the typelists are radically different. Check the reference for the exact MPL sequence concepts modeled by these type lists.
Although typically indices are specified by means of the
indexed_by construct, actually any MPL sequence of
index specifiers can be provided instead:
typedef mpl::vector<ordered_unique<identity<int> >,sequenced<> > index_list_t; typedef multi_index_container< int, index_list_t > indexed_t;
This possibility enables the synthesis of instantiations of
multi_index_container through MPL metaprograms, as the following
example shows:
// original multi_index_container instantiation typedef multi_index_container< int, indexed_by< ordered_unique<identity<int> > > > indexed_t1; // we take its index list and add an index typedef boost::mpl::push_front< indexed_t1::index_specifier_type_list, sequenced<> >::type index_list_t; // augmented multi_index_container typedef multi_index_container< int, index_list_t > indexed_t2;
Revised November 7th 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)