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
ctor_args_listmulti_index_container
multi_index_container
In relational databases, composite keys depend on two or more fields of a given table.
The analogous concept in Boost.MultiIndex is modeled by means of
composite_key, as shown in the example:
struct phonebook_entry { std::string family_name; std::string given_name; std::string phone_number; phonebook_entry( std::string family_name, std::string given_name, std::string phone_number): family_name(family_name),given_name(given_name),phone_number(phone_number) {} }; // define a multi_index_container with a composite key on // (family_name,given_name) typedef multi_index_container< phonebook_entry, indexed_by< //non-unique as some subscribers might have more than one number ordered_non_unique< composite_key< phonebook_entry, member<phonebook_entry,std::string,&phonebook_entry::family_name>, member<phonebook_entry,std::string,&phonebook_entry::given_name> > >, ordered_unique< // unique as numbers belong to only one subscriber member<phonebook_entry,std::string,&phonebook_entry::phone_number> > > > phonebook;
composite_key accepts two or more key extractors on the same
value (here, phonebook_entry). Lookup operations on a composite
key are accomplished by passing tuples with the values searched:
phonebook pb; ... // search for Dorothea White's number phonebook::iterator it=pb.find( boost::make_tuple(std::string("White"),std::string("Dorothea"))); std::string number=it->phone_number;
Composite keys are sorted by lexicographical order, i.e. sorting is performed by the first key, then the second key if the first one is equal, etc. This order allows for partial searches where only the first keys are specified:
phonebook pb; ... // look for all Whites std::pair<phonebook::iterator,phonebook::iterator> p= pb.equal_range(boost::make_tuple(std::string("White")));
On the other hand, partial searches without specifying the first keys are not allowed.
By default, the corresponding std::less predicate is used
for each subkey of a composite key. Alternate comparison predicates can
be specified with
composite_key_compare:
// phonebook with given names in reverse order typedef multi_index_container< phonebook_entry, indexed_by< ordered_non_unique< composite_key< phonebook_entry, member<phonebook_entry,std::string,&phonebook_entry::family_name>, member<phonebook_entry,std::string,&phonebook_entry::given_name> >, composite_key_compare< std::less<std::string>, // family names sorted as by default std::greater<std::string> // given names reversed > >, ordered_unique< member<phonebook_entry,std::string,&phonebook_entry::phone_number> > > > phonebook;
See Example 7 in the examples section
for an application of composite_key.
The Key Extractor
concept allows the same object to extract keys from several different types,
possibly through suitably defined overloads of operator():
// example of a name extractor from employee and employee * struct name_extractor { const std::string& operator()(const employee& e)const{return e.name;} std::string& operator()(employee& e)const{return e.name;} std::string& operator()(employee* e)const{return e->name;} };
This possibility is fully exploited by predefined key extractors provided
by Boost.MultiIndex, making it simpler to define multi_index_containers
where elements are pointers or references to the actual objects. The following
specifies a multi_index_container of pointers to employees sorted by their
names.
typedef multi_index_container< employee *, indexed_by< ordered_non_unique<member<employee,std::string,&employee::name> > > > employee_set;
Note that this is specified in exactly the same manner as a multi_index_container
of actual employee objects: member takes care of the
extra dereferencing needed to gain access to employee::name. A similar
functionality is provided for interoperability with reference wrappers from
Boost.Ref:
typedef multi_index_container< boost::reference_wrapper<const employee>, indexed_by< ordered_non_unique<member<employee,std::string,&employee::name> > > > employee_set;
In fact, support for pointers is further extended to accept what we call
chained pointers. Such a chained pointer is defined by induction as a raw or
smart pointer or iterator to the actual element, to a reference wrapper of the
element or to another chained pointer; that is, chained pointers are arbitrary
compositions of pointer-like types ultimately dereferencing
to the element from where the key is to be extracted. Examples of chained
pointers to employee are:
employee *,const employee *,std::auto_ptr<employee>,std::list<boost::reference_wrapper<employee> >::iterator,employee **,boost::shared_ptr<const employee *>.multi_index_containers from preexisting
multi_index_containers.
In order to present a short summary of the different usages of Boost.MultiIndex key extractors in the presence of reference wrappers and pointers, consider the following final type:
struct T { int i; const int j; int f()const; int g(); };
The table below lists the appropriate key extractors to be used for
different pointer and reference wrapper types based on T, for
each of its members.
| element type | sorted by | key extractor | applicable toconst elements? |
read/write? |
|---|---|---|---|---|
T |
i |
member<T,int,&T::i> |
yes | yes |
j |
member<T,const int,&T::j> |
yes | no | |
f() |
const_mem_fun<T,int,&T::f> |
yes | no | |
g() |
mem_fun<T,int,&T::g> |
no | no | |
reference_wrapper<T> |
i |
member<T,int,&T::i> |
yes | yes |
j |
member<T,const int,&T::j> |
yes | no | |
f() |
const_mem_fun<T,int,&T::f> |
yes | no | |
g() |
mem_fun<T,int,&T::g> |
yes | no | |
reference_wrapper<const T> |
i |
member<T,const int,&T::i> |
yes | no |
j |
member<T,const int,&T::j> |
yes | no | |
f() |
const_mem_fun<T,int,&T::f> |
yes | no | |
g() |
||||
chained pointer to Tor to reference_wrapper<T> |
i |
member<T,int,&T::i> |
yes | yes |
j |
member<T,const int,&T::j> |
yes | no | |
f() |
const_mem_fun<T,int,&T::f> |
yes | no | |
g() |
mem_fun<T,int,&T::g> |
yes | no | |
chained pointer to const Tor to reference_wrapper<const T> |
i |
member<T,const int,&T::i> |
yes | no |
j |
member<T,const int,&T::j> |
yes | no | |
f() |
const_mem_fun<T,int,&T::f> |
yes | no | |
g() |
||||
The column "applicable to const elements?" states whether the
corresponding key extractor can be used when passed constant elements (this
relates to the elements specified in the first column, not the referenced
T objects). The only negative case is for T::g when
the elements are raw T objects, which make sense as we are dealing
with a non-constant member function: this also implies that multi_index_containers
of elements of T cannot be sorted by T::g, because
elements contained within a multi_index_container are treated as constant.
A key extractor is called read/write if it returns a non-constant reference
to the key when passed a non-constant element, and it is called read-only
otherwise. In order to use multi_index_container::modify_key, the associated
key extractor must be read/write. The column "read/write?" shows that most
combinations yield read-only extractors.
Some care has to be taken to preserve const-correctness in the
specification of the key extractors: in some sense, the const
qualifier is carried along to the member part, even if that particular
member is not defined as const. For instance, if the elements
are of type const T *, sorting by T::i is not
specified as member<const T,int,&T::i>, but rather as
member<T,const int,&T::i>.
For practical demonstrations of use of these key extractors, refer to example 2 and example 6 in the examples section.
member_offset
The member key extractor poses some problems in compilers
that do not properly support pointers to members as non-type
template arguments, as indicated by the
Boost Configuration Library
defect macro BOOST_NO_POINTER_TO_MEMBER_TEMPLATE_PARAMETERS.
The following compilers have been confirmed not
to work correctly with member:
#include <iostream> struct pair { int x,y; pair(int x_,int y_):x(x_),y(y_){} }; template<int pair::* PtrToPairMember> struct foo { int bar(pair& p){return p.*PtrToPairMember;} }; int main() { pair p(0,1); foo<&pair::x> fx; foo<&pair::y> fy; if(fx.bar(p)!=0||fy.bar(p)!=1)std::cout<<"KO"<<std::endl; else std::cout<<"OK"<<std::endl; return 0; }
If you find a compiler that does not pass the test, and for which
BOOST_NO_POINTER_TO_MEMBER_TEMPLATE_PARAMETERS is not defined,
please report to the Boost developers mailing list.
To overcome this defect, a replacement utility
member_offset
has been provided that does the work of member at the
expense of less convenient notation and the possibility of
non-conformance with the standard. Please consult
the reference for further information on member_offset.
As an example of use, given the class
class A { int x; }
the instantiation member<A,int,&A::x> can be simulated then
as member_offset<A,int,offsetof(A,x)>.
For those writing portable code, Boost.MultiIndex provides the ternary macro
BOOST_MULTI_INDEX_MEMBER. Continuing with the example above, the
expression
BOOST_MULTI_INDEX_MEMBER(A,int,x)
expands by default to
member<A,int,&A::x>
or alternatively to
member_offset<A,int,offsetof(A,x)>
if BOOST_NO_POINTER_TO_MEMBER_TEMPLATE_PARAMETERS is defined.
const_mem_fun_explicit and
mem_fun_explicit
MSVC++ 6.0 has problems with const member functions as non-type
template parameters, and thus does not accept the const_mem_fun
key extractor. A simple workaround, fortunately, has been found, consisting
in specifying the type of these pointers as an additional template
parameter. The alternative const_mem_fun_explicit extractor
adopts this solution; for instance, given the type
struct A { int f()const; };
the extractor const_mem_fun<A,int,&A::f> can be replaced by
const_mem_fun_explicit<A,int,int (A::*)()const,&A::f>. A similar
mem_fun_explicit class template is provided for non-constant
member functions.
If you are writing cross-platform code, the selection of either key extractor
is transparently handled by the macro BOOST_MULTI_INDEX_CONST_MEM_FUN,
so that
BOOST_MULTI_INDEX_CONST_MEM_FUN(A,int,f)
expands by default to
const_mem_fun<A,int,&A::f>
but resolves to
const_mem_fun_explicit<A,int,int (A::*)()const,&A::f>
in MSVC++ 6.0. An analogous macro BOOST_MULTI_INDEX_MEM_FUN is
provided as well.
composite_key in compilers
without partial template specialization
Much of the power of composite_key derives from the ability
to perform searches when only the first elements of the compound key are
given. In order to enable this functionality, std::less and
std::greater are specialized for
composite_key_result instantiations to provide
overloads accepting tuples of values.
In those compilers that do not support partial template specialization,
tuple-based comparisons are not available by default. In this case,
multi_index_container instantiations using composite keys
will work as expected (elements are sorted lexicographically on the
results of the combined keys), except that lookup operations will not
accept tuples as an argument. The most obvious workaround
to this deficiency involves explicitly specifying the comparison
predicate with composite_key_compare: this is tedious as
the comparison predicates for all the element key extractors must be
explicitly typed. For this reason, Boost.MultiIndex provides the replacement
class template
composite_key_result_less, that
acts as the missing specialization of std::less for
composite_key_results:
typedef composite_key< phonebook_entry, member<phonebook_entry,std::string,&phonebook_entry::family_name>, member<phonebook_entry,std::string,&phonebook_entry::given_name> > ckey_t; typedef multi_index_container< phonebook_entry, indexed_by< ordered_non_unique< ckey_t, // composite_key_result_less plays the role of // std::less<ckey_t::result_type> composite_key_result_less<ckey_t::result_type> >, ordered_unique< member<phonebook_entry,std::string,&phonebook_entry::phone_number> > > > phonebook;
There is also an analogous
composite_key_result_greater class to substitute for
specializations of std::greater.
ctor_args_list
Although in most cases multi_index_containers will be default constructed
(or copied from a preexisting multi_index_container), sometimes it is
necessary to specify particular values for the internal objects used (key extractors,
comparison predicates, allocator), for instance if some of these objects do not have
a default constructor. The same situation can arise with standard STL containers,
which allow for the optional specification of such objects:
// example of non-default constructed std::set template<typename IntegralType> struct modulo_less { modulo_less(IntegralType m):modulo(m){} bool operator()(IntegralType x,IntegralType y)const { return (x%modulo)<(y%modulo); } private: IntegralType modulo; }; typedef std::set<unsigned int,modulo_less<unsigned int> > modulo_set; modulo_set m(modulo_less<unsigned int>(10));
multi_index_container does also provide this functionality, though in a
considerably more complex fashion, due to the fact that the constructor
of a multi_index_container has to accept values for all the internal
objects of its indices. The full form of multi_index_container constructor
is
explicit multi_index_container( const ctor_args_list& args_list=ctor_args_list(), const allocator_type& al=allocator_type());
The specification of the allocator object poses no particular problems;
as for the ctor_args_list, this object is designed so as to hold
the necessary construction values for every index in the multi_index_container.
From the point of view of the user, ctor_args_list is equivalent
to the type
boost::tuple<C0,...,CI-1>
where I is the number of indices, and Ci is
nth_index<i>::type::ctor_args
that is, the nested type ctor_args of the i-th index. Each
ctor_args type is in turn a tuple holding values for constructor
arguments of the associated index: so, ordered indices demand a key extractor object
and a comparison predicate, while sequenced indices do not need any construction
argument. For instance, given the definition
typedef multi_index_container< unsigned int, indexed_by< ordered_unique<identity<unsigned int> >, ordered_non_unique<identity<unsigned int>, modulo_less<unsigned int> >, sequenced<> > > modulo_indexed_set;
the corresponding ctor_args_list type is equivalent to
boost::tuple< // ctr_args of index #0 boost::tuple<identity<unsigned int>,std::less<unsigned int> >, // ctr_args of index #1 boost::tuple<identity<unsigned int>,modulo_less<unsigned int> >, // sequenced indices do not have any construction argument boost::tuple<> >
Such a modulo_indexed_set cannot be default constructed, because
modulo_less does not provide a default constructor. The following shows
how the construction can be done:
modulo_indexed_set::ctor_args_list args_list= boost::make_tuple( // ctor_args for index #0 is default constructible modulo_indexed_set::nth_index<0>::type::ctor_args(), boost::make_tuple(identity<unsigned int>(),modulo_less<unsigned int>(10)), // this is also default constructible (actually, an empty tuple) modulo_indexed_set::nth_index<2>::type::ctor_args(), ); modulo_indexed_set m(args_list);
A program is provided in the examples section that puts in practise these concepts.
The concept of Design by Contract, originally developed as part
of Bertrand Meyer's Eiffel language,
revolves around the formulation of a contract between the user
of a library and the implementor, by which the first is required to
respect some preconditions on the values passed when invoking
methods of the library, and the implementor guarantees in return
that certain constraints on the results are met (postconditions),
as well as the honoring of specified internal consistency rules, called
invariants. Eiffel natively supports the three parts of the
contract just described by means of constructs require,
ensure and invariant, respectively.
C++ does not enjoy direct support for Design by Contract techniques: these are customarily implemented as assertion code, often turned off in release mode for performance reasons. Following this approach, Boost.MultiIndex provides two distinct debugging modes:
The idea of adding precondition checking facilities to STL as a debugging aid was first introduced by Cay S. Horstmann in his Safe STL library and later adopted by STLport Debug Mode. Similarly, Boost.MultiIndex features the so-called safe mode in which all sorts of preconditions are checked when dealing with iterators and functions of the library.
Boost.MultiIndex safe mode is set by globally defining the macro
BOOST_MULTI_INDEX_ENABLE_SAFE_MODE. Error conditions
are checked via the macro BOOST_MULTI_INDEX_SAFE_MODE_ASSERT, which
by default resolves to a call to
BOOST_ASSERT.
If the user decides to define her own version of
BOOST_MULTI_INDEX_SAFE_MODE_ASSERT, it has to take the form
BOOST_MULTI_INDEX_SAFE_MODE_ASSERT(expr,error_code)
where expr is the condition checked and error_code
is one value of the safe_mode::error_code enumeration:
namespace boost{ namespace multi_index{ namespace safe_mode{ enum error_code { invalid_iterator, // default initialized iterator not_dereferenceable_iterator, // iterator is not dereferenceable not_incrementable_iterator, // iterator points to end of sequence not_decrementable_iterator, // iterator points to beginning of sequence not_owner, // iterator does not belong to the container not_same_owner, // iterators belong to different containers invalid_range, // last not reachable from first inside_range, // iterator lies within a range (and it mustn't) same_container // containers ought to be different }; } // namespace multi_index::safe_mode } // namespace multi_index } // namespace boost
For instance, the following replacement of
BOOST_MULTI_INDEX_SAFE_MODE_ASSERT throws an exception instead of
asserting:
#include <boost/multi_index_container/safe_mode_errors.hpp> struct safe_mode_exception { safe_mode_exception(boost::multi_index::safe_mode::error_code error_code): error_code(error_code) {} boost::multi_index::safe_mode::error_code error_code; }; #define BOOST_MULTI_INDEX_SAFE_MODE_ASSERT(expr,error_code) \ if(!(expr)){throw safe_mode_exception(error_code);} // This has to go before the inclusion of any header from Boost.MultiIndex, // except possibly safe_error_codes.hpp.
Other possibilites, like outputting to a log or firing some kind of alert, are also implementable.
Warning: Safe mode adds a very important overhead to the program
both in terms of space and time used, so in general it should not be set for
NDEBUG builds. Also, this mode is intended solely as a debugging aid,
and programs must not rely on it as part of their normal execution flow: in
particular, no guarantee is made that all possible precondition errors are diagnosed,
or that the checks remain stable across different versions of the library.
The so called invariant-checking mode of Boost.MultiIndex can be
set by globally defining the macro
BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING.
When this mode is in effect, all public functions of Boost.MultiIndex
will perform post-execution tests aimed at ensuring that the basic
internal invariants of the data structures managed are preserved.
If an invariant test fails, Boost.MultiIndex will indicate the failure
by means of the unary macro BOOST_MULTI_INDEX_INVARIANT_ASSERT.
Unless the user provides a definition for this macro, it defaults to
BOOST_ASSERT. Any assertion of this kind should
be regarded in principle as a bug in the library. Please report such
problems, along with as much contextual information as possible, to the
maintainer of the library.
It is recommended that users of Boost.MultiIndex always set the invariant-checking mode in debug builds.
multi_index_container
Academic movitations aside, there is a practical interest in simulating 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 simulate 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 simulated 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 simulation 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 simulation 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-simulated
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
simulated with appropriate use of find and insert.
These simulations 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, simulating 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 simulating
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.MPL Forward Sequence with as many elements as indices
comprise the multi_index_container: for instance, the n-nth
element of iterator_type_list is the same as
nth_index_iterator<n>::type.
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.
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 June 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)