Boost.MultiIndex Documentation - Key extraction reference

# Boost.MultiIndex Key extraction reference

Sequenced indices
Boost.MultiIndex reference
Compiler specifics

## Contents

- Key Extractors
  - Chained pointers
- Header `"boost/multi_index/key_extractors.hpp"` synopsis
- Header `"boost/multi_index/identity.hpp"` synopsis
  - Template class `identity`
- Header `"boost/multi_index/member.hpp"` synopsis
  - Template class `member`
  - Template class `member_offset`
  - Macro `BOOST_MULTI_INDEX_MEMBER`
- Header `"boost/multi_index/mem_fun.hpp"` synopsis
  - Template class `const_mem_fun`
  - Template class `mem_fun`
  - Template class `const_mem_fun_explicit`
  - Template class `mem_fun_explicit`
  - Macro `BOOST_MULTI_INDEX_CONST_MEM_FUN`
  - Macro `BOOST_MULTI_INDEX_MEM_FUN`
- Header `"boost/multi_index/composite_key.hpp"` synopsis
  - Template class `composite_key`
  - Template class `composite_key_result`
  - Template class `composite_key_compare`
  - Template class `composite_key_result_less`
  - Template class `composite_key_result_greater`
  - Specialization of `std::less` for `composite_key` results
  - Specialization of `std::greater` for `composite_key` results
  - Ordering semantics

## 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:

- `identity`,
- `member`,
- `const_mem_fun`,
- `mem_fun` and
- `composite_key`,

plus replacements for some of them:

- `member_offset`,
- `const_mem_fun_explicit` and
- `mem_fun_explicit`,

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`

- `*p` yields an object of type `Type&` or `boost::reference_wrapper<Type>`, OR
- `*p` yields a chained pointer to `Type`,

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:

- read/write `Key Extractor` from `Type`,
- `Key Extractor` from `reference_wrapper<const Type>`,
- read/write `Key Extractor` from `reference_wrapper<Type>`,
- `Key Extractor` from any chained pointer to `const Type`,
- read/write `Key Extractor` from any chained pointer to `Type`.

#### `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:

- read/write `Key Extractor` from `Class`,
- `Key Extractor` from `reference_wrapper<const Class>`,
- read/write `Key Extractor` from `reference_wrapper<Class>`,
- `Key Extractor` from any chained pointer to `const Class`,
- read/write `Key Extractor` from any chained pointer to `Class`.

#### `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:

- MSVC++ 6.0 (see Microsoft Knowledge Base article #249045),
- MSVC++ 7.0 (not officially confirmed by Microsoft),
- Intel C++ 7.0/7.1 for Windows (support issue #207321),
- VisualAge 6.0 for AIX (internal defect #288539.)

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:

- `Key Extractor` from `Class`,
- `Key Extractor` from `reference_wrapper<const Class>`,
- `Key Extractor` from `reference_wrapper<Class>`,
- `Key Extractor` from any chained pointer to `const Class`,
- `Key Extractor` from any chained pointer to `Class`.

#### `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:

- `Key Extractor` from `reference_wrapper<Class>`,
- `Key Extractor` from any chained pointer to `Class`.

#### `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:

- `Key Extractor` from `Value`,
- `Key Extractor` from `reference_wrapper<const Value>`,
- `Key Extractor` from `reference_wrapper<Value>`,
- `Key Extractor` from any chained pointer to `const Value`,
- `Key Extractor` from any chained pointer to `Value`.

#### `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:

- `ck(x)` is the `CompositeKey` object associated to `x`,
- `v(x)` is the object of type `CompositeKey::value_type` associated to `x`,
- `ki(x) = ck(x).key_extractors().get<i>()`, that is, is the `i`-th key extractor of `ck(x)`,
- `xi = ki(x)(v(x))`, that is, the key extracted from `v(x)` by the `i`-th key extractor,
- `length(x)` is the number of key extractors of `ck(x)`.

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

- `yi=y.get<i>()`,
- `length(y)` is the number of elements of `y`.

#### 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_result`s 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)`.

Sequenced indices
Boost.MultiIndex reference
Compiler specifics

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)