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 Key extraction reference



Contents

Key Extractors

Key extraction classes are used by ordered indices to obtain the sorting keys from the elements of a multi_index_container. An Assignable class KeyFromValue is said to be a key extractor from a type Type if

  1. the type KeyFromValue::result_type is defined,
  2. k1(ca) is defined and returns a value convertible to const KeyFromValue::result_type&,
  3. if k2 is a copy of k1, k1(ca) is the same value as k2(ca),
for every k1, k2 of type const KeyFromValue, and ca of type const Type&.

Additionally, KeyFromValue is a read/write key extractor if the following extra conditions are met:

  1. k1(a) is defined and returns a value convertible to KeyFromValue::result_type&,
  2. const_cast<const KeyFromValue::result_type&>(k1(a)) is the same value as k1(const_cast<const Type&>(a)),
for every k1 of type const KeyFromValue and a of type Type&.

Boost.MultiIndex provides five general-purpose key extractors:

plus replacements for some of them: that workaround some deficiencies in the support for non-type template parameters by certain compilers.

Chained pointers

The key extractors provided by Boost.MultiIndex are templatized according to the type Type and serve to extract keys not only from objects of type Type, but also from reference wrappers provided by Boost.Ref and from chained pointers to Type (or to reference wrappers of Type): a chained pointer is any type P such that, for an object p of type const P

that is, chained pointers are arbitrary compositions of pointer-like objects ultimately dereferencing to values of Type& or boost::reference_wrapper<Type>.

Header "boost/multi_index/key_extractors.hpp" synopsis

#include <boost/multi_index/identity.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/mem_fun.hpp>
#include <boost/multi_index/composite_key.hpp>

This header includes all the key extractors provided by Boost.MultiIndex.

Header "boost/multi_index/identity.hpp" synopsis

namespace boost{

namespace multi_index{

template<typename T> struct identity;

} // namespace boost::multi_index 

} // namespace boost

Template class identity

identity is a Key Extractor that acts as a do-nothing identity functor.

template<typename Type>
struct identity
{
  typedef Type result_type;

  template<typename ChainedPtr> Type& operator()(const ChainedPtr& x)const;
  const Type& operator()(const Type& x)const; 
  Type&       operator()(Type& x)const; // only provided if Type is non-const

  // only provided if Type is non-const
  const Type& operator()(const reference_wrapper<const Type>& x)const; 

  // only provided if Type is const
  Type& operator()(
    const reference_wrapper<typename remove_const<Type>::type>& x)const; 

  Type& operator()(const reference_wrapper<Type>& x)const;
};

identity<Type> is a model of:

identity members

template<typename ChainedPtr> Type& operator()(const ChainedPtr& x)const;
Requires: ChainedPtr is a chained pointer type to Type.
Returns: a reference to the object chained-pointed to by x.
const Type& operator()(const Type&x)const;
Returns: x.
Type& operator()(Type &x)const;
Returns: x.
const Type& operator()(const reference_wrapper<const Type>& x)const;
Returns: x.get().
Type& operator()(const reference_wrapper<typename remove_const<Type>::type>& x)const;
Returns: x.get().
Type& operator()(const reference_wrapper<Type>& x)const;
Returns: x.get().

Header "boost/multi_index/member.hpp" synopsis

namespace boost{

namespace multi_index{

template<class Class,typename Type,Type Class::*PtrToMember>
struct member;

template<class Class,typename Type,std::size_t OffsetOfMember>
struct member_offset;

#define BOOST_MULTI_INDEX_MEMBER(Class,Type,MemberName) implementation defined

} // namespace boost::multi_index 

} // namespace boost

Template class member

member is a Key Extractor aimed at accessing a given member of a class.

template<class Class,typename Type,Type Class::*PtrToMember>
struct member
{
  typedef Type result_type;

  template<typename ChainedPtr> Type& operator()(const ChainedPtr& x)const;
  const Type& operator()(const Class& x)const;
  Type&       operator()(Class& x)const; // only provided if Type is non-const
  const Type& operator()(const reference_wrapper<const Class>& x)const;
  Type&       operator()(const reference_wrapper<Class>& x)const;
};

The PtrToMember template argument specifies the particular Type Class::* pointer to the member to be extracted. member<Class,Type,PtrToMember> is a model of:

member members

template<typename ChainedPtr> Type& operator()(const ChainedPtr& x)const;
Requires: ChainedPtr is a chained pointer type to Type.
Returns: a reference to the object chained-pointed to by x.
const Type& operator()(const Class&x)const;
Returns: x.*PtrToMember.
Type& operator()(const Class&x);
Returns: x.*PtrToMember.
const Type& operator()(const reference_wrapper<const Class>& x)const;
Returns: x.get().*PtrToMember.
Type& operator()(const reference_wrapper<Class>& x)const;
Returns: x.get().*PtrToMember.

Template class member_offset

Some compilers do not properly support pointers to members as non-type template arguments. The following have been confirmed to have bugs in this respect:

In this situation, member_offset provides an alternative to member accepting offsets instead of pointers to members. Please note that the use of offsetof on non-POD types is forbidden by the standard; luckily enough, most compilers accept it nevertheless, so member_offset serves as a workaround for most practical purposes.

template<class Class,typename Type,std::size_t OffsetOfMember>
struct member_offset
{
  typedef Type result_type;

  template<typename ChainedPtr> Type& operator()(const ChainedPtr& x)const;
  const Type& operator()(const Class& x)const; 
  Type&       operator()(Class& x)const; // only provided if Type is non-const
  const Type& operator()(const reference_wrapper<const Class>& x)const;
  Type&       operator()(const reference_wrapper<Class>& x)const;
};

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)>.

Macro BOOST_MULTI_INDEX_MEMBER

BOOST_MULTI_INDEX_MEMBER(Class,Type,MemberName)

This macro is provided as an aid for using member and member_offset when writing cross-platform code. In the usual cases, it expands to

::boost::multi_index::member<Class,Type,&Class::MemberName>

but it resolves to

::boost::multi_index::member_offset<Class,Type,offsetof(Class,MemberName)>

if the Boost Configuration Library defect macro BOOST_NO_POINTER_TO_MEMBER_TEMPLATE_PARAMETERS is defined.

Header "boost/multi_index/mem_fun.hpp" synopsis

namespace boost{

namespace multi_index{

template<class Class,typename Type,Type (Class::*PtrToMemberFunction)()const>
struct const_mem_fun;

template<class Class,typename Type,Type (Class::*PtrToMemberFunction)()>
struct mem_fun;

template<
  class Class,typename Type,
  typename PtrToMemberFunctionType,PtrToMemberFunctionType PtrToMemberFunction
>
struct const_mem_fun_explicit;

template<
  class Class,typename Type,
  typename PtrToMemberFunctionType,PtrToMemberFunctionType PtrToMemberFunction
>
struct mem_fun_explicit;

#define BOOST_MULTI_INDEX_CONST_MEM_FUN(Class,Type,MemberFunName) \
implementation defined
#define BOOST_MULTI_INDEX_MEM_FUN(Class,Type,MemberFunName) \
implementation defined

} // namespace boost::multi_index 

} // namespace boost

Template class const_mem_fun

const_mem_fun is a Key Extractor returning as key the result of invoking a given constant member function of a class.

template<class Class,typename Type,Type (Class::*PtrToMemberFunction)()const>
struct const_mem_fun
{
  typedef typename remove_reference<Type>::type result_type;

  template<typename ChainedPtr> Type operator()(const ChainedPtr& x)const;
  Type operator()(const Class& x)const;
  Type operator()(const reference_wrapper<const Class>& x)const;
  Type operator()(const reference_wrapper<Class>& x)const;
};

The PtrToMemberFunction template argument specifies the particular Type (Class::*PtrToMemberFunction)()const pointer to the the constant member function used in the extraction. const_mem_fun<Class,Type,PtrToMemberFunction> is a model of:

const_mem_fun members

template<typename ChainedPtr> Type operator()(const ChainedPtr& x)const;
Requires: ChainedPtr is a chained pointer type to Type.
Returns: (y.*PtrToMemberFunction)(), where y is the object chained-pointed to by x.
Type operator()(const Class& x)const;
Returns: (x.*PtrToMemberFunction)().
Type operator()(const reference_wrapper<const Class>& x)const;
Returns: (x.get().*PtrToMemberFunction)().
Type operator()(const reference_wrapper<Class>& x)const;
Returns: (x.get().*PtrToMemberFunction)().

Template class mem_fun

mem_fun is a Key Extractor returning as key the result of invoking a given member function of a class.

template<class Class,typename Type,Type (Class::*PtrToMemberFunction)()>
struct mem_fun
{
  typedef typename remove_reference<Type>::type result_type;

  template<typename ChainedPtr> Type operator()(const ChainedPtr& x)const;
  Type operator()(Class& x)const;
  Type operator()(const reference_wrapper<Class>& x)const;
};

The PtrToMemberFunction template argument specifies the particular Type (Class::*PtrToMemberFunction)() pointer to the the member function used in the extraction. mem_fun<Class,Type,PtrToMemberFunction> is a model of:

mem_fun members

template<typename ChainedPtr> Type operator()(const ChainedPtr& x)const;
Requires: ChainedPtr is a chained pointer type to Type.
Returns: (y.*PtrToMemberFunction)(), where y is the object chained-pointed to by x.
Type operator()(Class& x)const;
Returns: (x.*PtrToMemberFunction)().
Type operator()(const reference_wrapper<Class>& x)const;
Returns: (x.get().*PtrToMemberFunction)().

Template class const_mem_fun_explicit

MSVC++ 6.0 do not properly support pointers to constant member functions as non-type template parameters, thus const_mem_fun cannot be used in this compiler. A simple workaround consists in specifying the type of these pointers as an additional template parameter.

template<
  class Class,typename Type,
  typename PtrToMemberFunctionType,PtrToMemberFunctionType PtrToMemberFunction
>
struct const_mem_fun_explicit
{
  typedef typename remove_reference<Type>::type result_type;

  template<typename ChainedPtr> Type operator()(const ChainedPtr& x)const;
  Type operator()(const Class& x)const;
  Type operator()(const reference_wrapper<const Class>& x)const;
  Type operator()(const reference_wrapper<Class>& x)const;
};

const_mem_fun_explicit provides the very same functionality as its const_mem_fun analogous instantiation. For example, 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>.

Template class mem_fun_explicit

For analogy with const_mem_fun_explicit, a variation of mem_fun is provided accepting an additional parameter with the type of the pointer to non-constant member function used for extraction.

template<
  class Class,typename Type,
  typename PtrToMemberFunctionType,PtrToMemberFunctionType PtrToMemberFunction
>
struct mem_fun_explicit
{
  typedef typename remove_reference<Type>::type result_type;

  template<typename ChainedPtr> Type operator()(const ChainedPtr& x)const;
  Type operator()(Class& x)const;
  Type operator()(const reference_wrapper<Class>& x)const;
};

Macro BOOST_MULTI_INDEX_CONST_MEM_FUN

BOOST_MULTI_INDEX_CONST_MEM_FUN(Class,Type,MemberFunName)

Use this macro when writing cross-platform code selectively using const_mem_fun_explicit in place of const_mem_fun for compilers not supporting the latter. In the usual cases, the macro expands to

::boost::multi_index::const_mem_fun<Class,Type,&Class::MemberFunName>

but it resolves to

::boost::multi_index::const_mem_fun_explicit<
  Class,Type,Type (Class::*)()const,&Class::MemberFunName
>

for MSVC++ 6.0 or lower.

Macro BOOST_MULTI_INDEX_MEM_FUN

BOOST_MULTI_INDEX_MEM_FUN(Class,Type,MemberFunName)

By default, the macro expands to

::boost::multi_index::mem_fun<Class,Type,&Class::MemberFunName>

but it resolves to

::boost::multi_index::mem_fun_explicit<
  Class,Type,Type (Class::*)(),&Class::MemberFunName
>

for MSVC++ 6.0 or lower.

Header "boost/multi_index/composite_key.hpp" synopsis

namespace boost{

namespace multi_index{

template<typename Value,typename KeyFromValue0,...,typename KeyFromValuen>
struct composite_key;

template<typename CompositeKey>
struct composite_key_result;
  
// comparison for composite_key_result:

// OP is any of =,<,!=,>,>=,<=

template<typename CompositeKey1,typename CompositeKey2>
bool operator OP(
  const composite_key_result<CompositeKey1>& x,
  const composite_key_result<CompositeKey2>& y);

template<typename CompositeKey,typename Value0,...,typename Valuen>
bool operator OP(
  const composite_key_result<CompositeKey>& x,
  const tuple<Value0,...,Valuen>& y);

template<typename Value0,...,typename Valuen,typename CompositeKey>
bool operator OP(
  const tuple<Value0,...,Valuen>& x,
  const composite_key_result<CompositeKey>& y);

template<typename Compare0,...,typename Comparen>
struct composite_key_compare;
  
template<typename CompositeKeyResult>
struct composite_key_result_less;

template<typename CompositeKeyResult>
struct composite_key_result_greater;

} // namespace boost::multi_index

} // namespace boost

namespace std{

template<typename CompositeKey>
struct less<boost::multi_index::composite_key_result<CompositeKey> >;

template<typename CompositeKey>
struct greater<boost::multi_index::composite_key_result<CompositeKey> >;

} // namespace std

Template class composite_key

composite_key is a Key Extractor returning the combined value of several key extractors whose type is specified at compile time. The returned object is of type composite_key_result<composite_key>.

template<typename Value,typename KeyFromValue0,...,typename KeyFromValuen>
struct composite_key
{
  typedef tuple<KeyFromValue0,...,KeyFromValuen> key_extractor_tuple;
  typedef Value                                  value_type;
  typedef composite_key_result<composite_key>    result_type;

  composite_key(
    const KeyFromValue0& k0=KeyFromValue0(),
    ...
    const KeyFromValuen& kn=KeyFromValuen());

  composite_key(const key_extractor_tuple& x);

  const key_extractor_tuple& key_extractors()const;
  key_extractor_tuple&       key_extractors()

  template<typename ChainedPtr>
  result_type operator()(const ChainedPtr& x)const;
  
  result_type operator()(const value_type& x)const;
  result_type operator()(const reference_wrapper<const value_type>& x)const;
  result_type operator()(const reference_wrapper<value_type>& x)const;
};

KeyFromValue0, ... , KeyFromValuen are the types of the key extractors combined into the composite key. Each of these types must be a Key Extractor from Value. At least a key extractor must be provided. The maximum number of key extractors of a composite_key instantiation is implementation defined. composite_key internally stores an object of every constituent key extractor type. composite_key<Value,KeyFromValue0,...,KeyFromValuen> is a model of:

composite_key members

composite_key(
  const KeyFromValue0& k0=KeyFromValue0(),
  ...
  const KeyFromValuen& kn=KeyFromValuen());
Effects: Constructs a composite_key that stores copies of the key extractor objects supplied.
composite_key(const key_extractor_tuple& x);
Effects: Constructs a composite_key that stores copies of the key extractor objects supplied in x.
const key_extractor_tuple& key_extractors()const;
Returns: a constant reference to a tuple holding the key extractors internally stored by the composite_key.
key_extractor_tuple& key_extractors();
Returns: a reference to a tuple holding the key extractors internally stored by the composite_key.
template<typename ChainedPtr>
result_type operator()(const ChainedPtr& x)const;
Requires: ChainedPtr is a chained pointer type to result_type.
Returns: a result_type object dependent on *this and y, where y is the object chained-pointed to by x.
result_type operator()(const value_type& x)const;
Returns: a result_type object dependent on *this and x.
result_type operator()(const reference_wrapper<const value_type>& x)const;
Returns: a result_type object dependent on *this and x.get().
result_type operator()(const reference_wrapper<value_type>& x)const;
Returns: a result_type object dependent on *this and x.get().

Template class composite_key_result

This is an opaque type returned by composite_key instantiations as their extracted key.

template<typename CompositeKey>
struct composite_key_result
{
  no public interface available
};

// comparison:
  
// OP is any of =,<,!=,>,>=,<=

template<typename CompositeKey1,typename CompositeKey2>
bool operator OP(
  const composite_key_result<CompositeKey1>& x,
  const composite_key_result<CompositeKey2>& y);

template<typename CompositeKey,typename Value0,...,typename Valuen>
bool operator OP(
  const composite_key_result<CompositeKey>& x,
  const tuple<Value0,...,Valuen>& y);

template<typename Value0,...,typename Valuen,typename CompositeKey>
bool operator OP(
  const tuple<Value0,...,Valuen>& x,
  const composite_key_result<CompositeKey>& y);
CompositeKey is the composite_key instantiation to which the composite_key_result type is associated. Objects of type composite_key_result returned by a composite key must be always treated as temporary, i.e. they should not be stored or copied. composite_key_result is not guaranteed to be a model of Default Constructible or Assignable. Every object of type composite_key_result<CompositeKey> is internally asociated to the CompositeKey from which it is returned and the object of type CompositeKey::result_type to which the composite key was applied.

Notation

Given an x of type composite_key_result<CompositeKey>, we use the following notation:

Also, if y is a tuple of values, we define:

Comparison operators

template<typename CompositeKey1,typename CompositeKey2>
bool operator==(
  const composite_key_result<CompositeKey1>& x,
  const composite_key_result<CompositeKey2>& y);
template<typename CompositeKey,typename Value0,...,typename Valuen>
bool operator==(
  const composite_key_result<CompositeKey>& x,
  const tuple<Value0,...,Valuen>& y);
template<typename Value0,...,typename Valuen,typename CompositeKey>
bool operator==(
  const tuple<Value0,...,Valuen>& x,
  const composite_key_result<CompositeKey>& y);
Requires: length(x)==length(y). The expression xi==yi is valid for all i in [0,length(x)).
Returns: true if and only if
xi==yi for all i in [0,length(x)).
Complexity: No more key extraction operations and comparisons are performed than those necessary for the evaluation of the expression above, starting at i==0. The evaluation is short-circuited as soon as the result is determined to be false.
template<typename CompositeKey1,typename CompositeKey2>
bool operator<(
  const composite_key_result<CompositeKey1>& x,
  const composite_key_result<CompositeKey2>& y);
template<typename CompositeKey,typename Value0,...,typename Valuen>
bool operator<(
  const composite_key_result<CompositeKey>& x,
  const tuple<Value0,...,Valuen>& y);
template<typename Value0,...,typename Valuen,typename CompositeKey>
bool operator<(
  const tuple<Value0,...,Valuen>& x,
  const composite_key_result<CompositeKey>& y);
Requires: The expressions xi<yi and yi<xi are valid for all i in [0,min(length(x),length(y))).
Returns: true if and only if there exists some j in the range [0,min(length(x),length(y))) such that
!(xi<yi) && !(yi<xi) for all i in [0,j),
  xj<yj.
Complexity: No more key extraction operations and comparisons are performed than those necessary for the evaluation of the expression above, starting at i==0. The evaluation is short-circuited as soon as the result is determined to be false.
template<typename CompositeKey1,typename CompositeKey2>
bool operator OP(
  const composite_key_result<CompositeKey1>& x,
  const composite_key_result<CompositeKey2>& y);
template<typename CompositeKey,typename Value0,...,typename Valuen>
bool operator OP(
  const composite_key_result<CompositeKey>& x,
  const tuple<Value0,...,Valuen>& y);
template<typename Value0,...,typename Valuen,typename CompositeKey>
bool operator OP(
  const tuple<Value0,...,Valuen>& x,
  const composite_key_result<CompositeKey>& y);

(OP is any of !=, >, >=, <=.)

Requires: The expressions given below are valid (for the particular OP considered.)
Returns: true if and only if
!(x==y) (OP is !=),
  y< x  (OP is ),
!(x< y) (OP is >=),
!(y< x) (OP is <=).

Template class composite_key_compare

composite_key_compare compares composite_key_result instantiations between them and with tuples of values using an internally stored collection of elementary comparison predicates.

template<typename Compare0,...,typename Comparen>
struct composite_key_compare
{
  typedef tuple<Compare0,...,Comparen> key_comp_tuple;

  composite_key_compare(
    const Compare0& co=Compare0(),
    ...
    const Comparen& cn=Comparen());

  composite_key_compare(const key_comp_tuple& x);

  const key_comp_tuple& key_comps()const{return *this;}
  key_comp_tuple&       key_comps(){return *this;}

  template<typename CompositeKey1,typename CompositeKey2>
  bool operator()(
    const composite_key_result<CompositeKey1> & x,
    const composite_key_result<CompositeKey2> & y)const;
  
  template<typename CompositeKey,typename Value0,...,typename Valuen>
  bool operator()(
    const composite_key_result<CompositeKey>& x,
    const tuple<Value0,...,Valuen>& y)const;

  template<typename Value0,...,typename Valuen,typename CompositeKey>
  bool operator()(
    const tuple<Value0,...,Valuen>& x,
    const composite_key_result<CompositeKey>& y)const;
};

Compare0, ... , Compare0 are the types of the comparison predicates stored by composite_key_compare. Each of these types must be a Binary Predicate. At least a comparison predicate must be provided. The maximum number of comparison predicates of a composite_key_compare instantiation is implementation defined. composite_key_compare is Assignable. It is also Default Constructible if each Comparei is Default Constructible.

Note that formally it is not required that the Comparei types behave as comparison predicates in any definite way. However, the semantics of composite_key_compare are well defined if this is the case, as explained in the ordering semantics section.

Notation

In what follows we use the same notation introduced for composite_key_result.

composite_key_compare members

composite_key_compare(
  const Compare0& c0=Compare0(),
  ...
  const Comparen& kn=Comparen());
Effects: Constructs a composite_key_compare that stores copies of the comparison predicates supplied.
composite_key_compare(const key_comp_tuple& x);
Effects: Constructs a composite_key_compare that stores copies of the comparison predicate objects supplied in x.
const key_comp_tuple& key_comps()const;
Returns: a constant reference to a tuple holding the comparison predicate objects internally stored by the composite_key_compare.
key_comp_tuple& key_comps();
Returns: a reference to a tuple holding the comparison predicate objects internally stored by the composite_key_compare.
template<typename CompositeKey1,typename CompositeKey2>
bool operator()(
  const composite_key_result<CompositeKey1> & x,
  const composite_key_result<CompositeKey2> & y)const;
template<typename CompositeKey,typename Value0,...,typename Valuen>
bool operator()(
  const composite_key_result<CompositeKey>& x,
  const tuple<Value0,...,Valuen>& y)const;
template<typename Value0,...,typename Valuen,typename CompositeKey>
bool operator()(
  const tuple<Value0,...,Valuen>& x,
  const composite_key_result<CompositeKey>& y)const;
Requires: The expressions key_comps().get<i>()(xi,yi) and key_comps().get<i>()(yi,xi) are valid for all i in [0,min(length(x),length(y))).
Returns: true if and only if there exists some j in the range [0,min(length(x),length(y))) such that
!key_comps().get<i>()(xi,yi) && !key_comps().get<i>()(yi,xi) for all i in [0,j),
 key_comps().get<j>()(xj,yj).
Complexity: No more key extraction operations and comparisons are performed than those necessary for the evaluation of the expression above, starting at i==0. The evaluation is short-circuited as soon as the result is determined to be false.

Template class composite_key_result_less

composite_key_result acts as a particularization of composite_key_compare where all the comparison predicates supplied are instantiations of std::less.

template<typename CompositeKeyResult>
struct composite_key_result_less
{
  typedef CompositeKeyResult  first_argument_type;
  typedef first_argument_type second_argument_type;
  typedef bool                result_type;

  template<typename CompositeKey1,typename CompositeKey2>
  bool operator()(
    const composite_key_result<CompositeKey1> & x,
    const composite_key_result<CompositeKey2> & y)const;
  
  template<typename CompositeKey,typename Value0,...,typename Valuen>
  bool operator()(
    const composite_key_result<CompositeKey>& x,
    const tuple<Value0,...,Valuen>& y)const;

  template<typename Value0,...,typename Valuen,typename CompositeKey>
  bool operator()(
    const tuple<Value0,...,Valuen>& x,
    const composite_key_result<CompositeKey>& y)const;
};

CompositeKeyResult must be an instantiation of composite_key_result for some type composite_key<KeyFromValue0,...,KeyFromValuen>. composite_key_result_less<CompositeKeyResult>::operator() is then equivalent to composite_key_compare<Compare0,...,Comparen>::operator(), taking

Comparei = std::less<KeyFromValuei::result_type> for all i = 0,...,n.

In addition to the requirements on Comparei imposed by composite_key_compare, each of these types must be Default Constructible. composite_key_result_less is Default Constructible and Assignable.

Template class composite_key_result_greater

composite_key_result acts as a particularization of composite_key_compare where all the comparison predicates supplied are instantiations of std::greater.

template<typename CompositeKeyResult>
struct composite_key_result_greater
{
  typedef CompositeKeyResult  first_argument_type;
  typedef first_argument_type second_argument_type;
  typedef bool                result_type;

  template<typename CompositeKey1,typename CompositeKey2>
  bool operator()(
    const composite_key_result<CompositeKey1> & x,
    const composite_key_result<CompositeKey2> & y)const;
  
  template<typename CompositeKey,typename Value0,...,typename Valuen>
  bool operator()(
    const composite_key_result<CompositeKey>& x,
    const tuple<Value0,...,Valuen>& y)const;

  template<typename Value0,...,typename Valuen,typename CompositeKey>
  bool operator()(
    const tuple<Value0,...,Valuen>& x,
    const composite_key_result<CompositeKey>& y)const;
};

CompositeKeyResult must be an instantiation of composite_key_result for some type composite_key<KeyFromValue0,...,KeyFromValuen>. composite_key_result_greater<CompositeKeyResult>::operator() is then equivalent to composite_key_compare<Compare0,...,Comparen>::operator(), taking

Comparei = std::greater<KeyFromValuei::result_type> for all i = 0,...,n.

In addition to the requirements on Comparei imposed by composite_key_compare, each of these types must be Default Constructible. composite_key_result_greater is Default Constructible and Assignable.

Specialization of std::less for composite_key results

std::less<CompositeKeyResult>, for CompositeKeyResult being an instantiation of composite_key_result, has the same interface and functionality that composite_key_result_less<CompositeKeyResult>.

namespace std{

template<typename CompositeKey>
struct less<boost::multi_index::composite_key_result<CompositeKey> >
{
  typedef CompositeKeyResult  first_argument_type;
  typedef first_argument_type second_argument_type;
  typedef bool                result_type;

  template<typename CompositeKey1,typename CompositeKey2>
  bool operator()(
    const composite_key_result<CompositeKey1> & x,
    const composite_key_result<CompositeKey2> & y)const;
  
  template<typename CompositeKey,typename Value0,...,typename Valuen>
  bool operator()(
    const composite_key_result<CompositeKey>& x,
    const tuple<Value0,...,Valuen>& y)const;

  template<typename Value0,...,typename Valuen,typename CompositeKey>
  bool operator()(
    const tuple<Value0,...,Valuen>& x,
    const composite_key_result<CompositeKey>& y)const;
};

} // namespace std

Specialization of std::greater for composite_key results

std::greater<CompositeKeyResult>, for CompositeKeyResult being an instantiation of composite_key_result, has the same interface and functionality that composite_key_result_greater<CompositeKeyResult>.

namespace std{

template<typename CompositeKey>
struct greater<boost::multi_index::composite_key_result<CompositeKey> >
{
  typedef CompositeKeyResult  first_argument_type;
  typedef first_argument_type second_argument_type;
  typedef bool                result_type;

  template<typename CompositeKey1,typename CompositeKey2>
  bool operator()(
    const composite_key_result<CompositeKey1> & x,
    const composite_key_result<CompositeKey2> & y)const;
  
  template<typename CompositeKey,typename Value0,...,typename Valuen>
  bool operator()(
    const composite_key_result<CompositeKey>& x,
    const tuple<Value0,...,Valuen>& y)const;

  template<typename Value0,...,typename Valuen,typename CompositeKey>
  bool operator()(
    const tuple<Value0,...,Valuen>& x,
    const composite_key_result<CompositeKey>& y)const;
};

} // namespace std

Ordering semantics

Consider an instantiation of composite_key_compare with types Compare0, ... , Comparen such that each Comparei is a Strict Weak Ordering on a certain type Ti. Then the following properties hold.

Let CompositeKey be a type of the form composite_key<Value,KeyFromValue0,...,KeyFromValuej>, with j <= n, such that

KeyFromValuei::result_type = Ti, for all i = 0,...,j.
Then, composite_key_compare is a Strict Weak Ordering on elements of type composite_key_result<CompositeKey>, and the order induced is lexicographical. Also, the following types are Compatible Keys of composite_key_compare with respect to composite_key_result<CompositeKey>:
tuple<Q0,...,Qk>, k <= n
composite_key_result<composite_key<K0,...,Kk> >, with Ki::result_type = Qi for all i = 0,...,k.
provided that each Qi is either Ti or a Compatible Key of Comparei. In this case, the comparison is done lexicographically only on the first 1+min(j,k) elements.

The rationale of this design is simple: composite_key_results are regarded as "virtual" tuples with each element being the result of the corresponding elementary key extractor. Accordingly, these objects and actual tuples are compared lexicographically taking the minimum length of the operands considered.

Analogous properties hold for composite_key_result::operator<. As for operator==, the semantics is compatible with that of less-than comparison, with the additional constraint that only objects of the same length can be tested for equality. In this regard, the equivalence classes induced by x==y are subsets of those associated to !(x<y)&&!(y<x).




Revised September 3rd 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)