1 /* Copyright 2003-2006 Joaquín M López Muñoz.
2 * Distributed under the Boost Software License, Version 1.0.
3 * (See accompanying file LICENSE_1_0.txt or copy at
4 * http://www.boost.org/LICENSE_1_0.txt)
6 * See http://www.boost.org/libs/multi_index for library home page.
9 #ifndef BOOST_MULTI_INDEX_COMPOSITE_KEY_HPP
10 #define BOOST_MULTI_INDEX_COMPOSITE_KEY_HPP
12 #if defined(_MSC_VER)&&(_MSC_VER>=1200)
16 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
17 #include <boost/multi_index/detail/access_specifier.hpp>
18 #include <boost/multi_index/detail/prevent_eti.hpp>
19 #include <boost/mpl/eval_if.hpp>
20 #include <boost/mpl/identity.hpp>
21 #include <boost/mpl/if.hpp>
22 #include <boost/mpl/or.hpp>
23 #include <boost/mpl/aux_/nttp_decl.hpp>
24 #include <boost/preprocessor/cat.hpp>
25 #include <boost/preprocessor/control/expr_if.hpp>
26 #include <boost/preprocessor/list/at.hpp>
27 #include <boost/preprocessor/repetition/enum.hpp>
28 #include <boost/preprocessor/repetition/enum_params.hpp>
29 #include <boost/static_assert.hpp>
30 #include <boost/tuple/tuple.hpp>
31 #include <boost/type_traits/is_same.hpp>
32 #include <boost/utility/enable_if.hpp>
35 #if !defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING)
36 #include <boost/ref.hpp>
39 #if !defined(BOOST_NO_SFINAE)
40 #include <boost/type_traits/is_convertible.hpp>
43 /* A composite key stores n key extractors and "computes" the
44 * result on a given value as a packed reference to the value and
45 * the composite key itself. Actual invocations to the component
46 * key extractors are lazily performed when executing an operation
47 * on composite_key results (equality, comparison, hashing.)
48 * As the other key extractors in Boost.MultiIndex, composite_key<T,...>
49 * is overloaded to work on chained pointers to T and reference_wrappers
53 /* This user_definable macro limits the number of elements of a composite
54 * key; useful for shortening resulting symbol names (MSVC++ 6.0, for
55 * instance has problems coping with very long symbol names.)
56 * NB: This cannot exceed the maximum number of arguments of
57 * boost::tuple. In Boost 1.32, the limit is 10.
60 #if !defined(BOOST_MULTI_INDEX_LIMIT_COMPOSITE_KEY_SIZE)
61 #if defined(BOOST_MSVC)&&(BOOST_MSVC<1300)
62 #define BOOST_MULTI_INDEX_LIMIT_COMPOSITE_KEY_SIZE 5
64 #define BOOST_MULTI_INDEX_LIMIT_COMPOSITE_KEY_SIZE 10
68 /* maximum number of key extractors in a composite key */
70 #if BOOST_MULTI_INDEX_LIMIT_COMPOSITE_KEY_SIZE<10 /* max length of a tuple */
71 #define BOOST_MULTI_INDEX_COMPOSITE_KEY_SIZE \
72 BOOST_MULTI_INDEX_LIMIT_COMPOSITE_KEY_SIZE
74 #define BOOST_MULTI_INDEX_COMPOSITE_KEY_SIZE 10
77 /* BOOST_PP_ENUM of BOOST_MULTI_INDEX_COMPOSITE_KEY_SIZE elements */
79 #define BOOST_MULTI_INDEX_CK_ENUM(macro,data) \
80 BOOST_PP_ENUM(BOOST_MULTI_INDEX_COMPOSITE_KEY_SIZE,macro,data)
82 /* BOOST_PP_ENUM_PARAMS of BOOST_MULTI_INDEX_COMPOSITE_KEY_SIZE elements */
84 #define BOOST_MULTI_INDEX_CK_ENUM_PARAMS(param) \
85 BOOST_PP_ENUM_PARAMS(BOOST_MULTI_INDEX_COMPOSITE_KEY_SIZE,param)
88 * otherwise -> textn=tuples::null_type
91 #define BOOST_MULTI_INDEX_CK_TEMPLATE_PARM(z,n,text) \
92 typename BOOST_PP_CAT(text,n) BOOST_PP_EXPR_IF(n,=tuples::null_type)
94 /* const textn& kn=textn() */
96 #define BOOST_MULTI_INDEX_CK_CTOR_ARG(z,n,text) \
97 const BOOST_PP_CAT(text,n)& BOOST_PP_CAT(k,n) = BOOST_PP_CAT(text,n)()
99 /* typename list(0)<list(1),n>::type */
101 #define BOOST_MULTI_INDEX_CK_APPLY_METAFUNCTION_N(z,n,list) \
102 BOOST_DEDUCED_TYPENAME BOOST_PP_LIST_AT(list,0)< \
103 BOOST_PP_LIST_AT(list,1),n \
108 template<class T> class reference_wrapper; /* fwd decl. */
109 template<class T> struct hash; /* fwd decl. */
111 namespace multi_index{
115 /* n-th key extractor of a composite key */
117 template<typename CompositeKey,BOOST_MPL_AUX_NTTP_DECL(int, N)>
118 struct nth_key_from_value
120 typedef typename CompositeKey::key_extractor_tuple key_extractor_tuple;
121 typedef typename prevent_eti<
122 tuples::element<N,key_extractor_tuple>,
123 typename mpl::eval_if_c<
124 N<tuples::length<key_extractor_tuple>::value,
125 tuples::element<N,key_extractor_tuple>,
126 mpl::identity<tuples::null_type>
131 /* nth_composite_key_##name<CompositeKey,N>::type yields
132 * functor<nth_key_from_value<CompositeKey,N> >, or tuples::null_type
133 * if N exceeds the length of the composite key.
136 #define BOOST_MULTI_INDEX_CK_NTH_COMPOSITE_KEY_FUNCTOR(name,functor) \
137 template<typename KeyFromValue> \
138 struct BOOST_PP_CAT(key_,name) \
140 typedef functor<typename KeyFromValue::result_type> type; \
144 struct BOOST_PP_CAT(key_,name)<tuples::null_type> \
146 typedef tuples::null_type type; \
149 template<typename CompositeKey,BOOST_MPL_AUX_NTTP_DECL(int, N)> \
150 struct BOOST_PP_CAT(nth_composite_key_,name) \
152 typedef typename nth_key_from_value<CompositeKey,N>::type key_from_value; \
153 typedef typename BOOST_PP_CAT(key_,name)<key_from_value>::type type; \
156 /* nth_composite_key_equal_to
157 * nth_composite_key_less
158 * nth_composite_key_greater
159 * nth_composite_key_hash
162 BOOST_MULTI_INDEX_CK_NTH_COMPOSITE_KEY_FUNCTOR(equal_to,std::equal_to)
163 BOOST_MULTI_INDEX_CK_NTH_COMPOSITE_KEY_FUNCTOR(less,std::less)
164 BOOST_MULTI_INDEX_CK_NTH_COMPOSITE_KEY_FUNCTOR(greater,std::greater)
165 BOOST_MULTI_INDEX_CK_NTH_COMPOSITE_KEY_FUNCTOR(hash,boost::hash)
167 /* used for defining equality and comparison ops of composite_key_result */
169 #define BOOST_MULTI_INDEX_CK_IDENTITY_ENUM_MACRO(z,n,text) text
171 struct generic_operator_equal
173 template<typename T,typename Q>
174 bool operator()(const T& x,const Q& y)const{return x==y;}
178 BOOST_MULTI_INDEX_CK_ENUM(
179 BOOST_MULTI_INDEX_CK_IDENTITY_ENUM_MACRO,
180 detail::generic_operator_equal)> generic_operator_equal_tuple;
182 struct generic_operator_less
184 template<typename T,typename Q>
185 bool operator()(const T& x,const Q& y)const{return x<y;}
189 BOOST_MULTI_INDEX_CK_ENUM(
190 BOOST_MULTI_INDEX_CK_IDENTITY_ENUM_MACRO,
191 detail::generic_operator_less)> generic_operator_less_tuple;
193 /* Metaprogramming machinery for implementing equality, comparison and
194 * hashing operations of composite_key_result.
196 * equal_* checks for equality between composite_key_results and
197 * between those and tuples, accepting a tuple of basic equality functors.
198 * compare_* does lexicographical comparison.
199 * hash_* computes a combination of elementwise hash values.
204 typename KeyCons1,typename Value1,
205 typename KeyCons2, typename Value2,
208 struct equal_ckey_ckey; /* fwd decl. */
212 typename KeyCons1,typename Value1,
213 typename KeyCons2, typename Value2,
216 struct equal_ckey_ckey_terminal
219 const KeyCons1&,const Value1&,
220 const KeyCons2&,const Value2&,
229 typename KeyCons1,typename Value1,
230 typename KeyCons2, typename Value2,
233 struct equal_ckey_ckey_normal
236 const KeyCons1& c0,const Value1& v0,
237 const KeyCons2& c1,const Value2& v1,
240 if(!eq.get_head()(c0.get_head()(v0),c1.get_head()(v1)))return false;
241 return equal_ckey_ckey<
242 BOOST_DEDUCED_TYPENAME KeyCons1::tail_type,Value1,
243 BOOST_DEDUCED_TYPENAME KeyCons2::tail_type,Value2,
244 BOOST_DEDUCED_TYPENAME EqualCons::tail_type
245 >::compare(c0.get_tail(),v0,c1.get_tail(),v1,eq.get_tail());
251 typename KeyCons1,typename Value1,
252 typename KeyCons2, typename Value2,
255 struct equal_ckey_ckey:
258 is_same<KeyCons1,tuples::null_type>,
259 is_same<KeyCons2,tuples::null_type>
261 equal_ckey_ckey_terminal<KeyCons1,Value1,KeyCons2,Value2,EqualCons>,
262 equal_ckey_ckey_normal<KeyCons1,Value1,KeyCons2,Value2,EqualCons>
269 typename KeyCons,typename Value,
270 typename ValCons,typename EqualCons
272 struct equal_ckey_cval; /* fwd decl. */
276 typename KeyCons,typename Value,
277 typename ValCons,typename EqualCons
279 struct equal_ckey_cval_terminal
282 const KeyCons&,const Value&,const ValCons&,const EqualCons&)
288 const ValCons&,const KeyCons&,const Value&,const EqualCons&)
296 typename KeyCons,typename Value,
297 typename ValCons,typename EqualCons
299 struct equal_ckey_cval_normal
302 const KeyCons& c,const Value& v,const ValCons& vc,
305 if(!eq.get_head()(c.get_head()(v),vc.get_head()))return false;
306 return equal_ckey_cval<
307 BOOST_DEDUCED_TYPENAME KeyCons::tail_type,Value,
308 BOOST_DEDUCED_TYPENAME ValCons::tail_type,
309 BOOST_DEDUCED_TYPENAME EqualCons::tail_type
310 >::compare(c.get_tail(),v,vc.get_tail(),eq.get_tail());
314 const ValCons& vc,const KeyCons& c,const Value& v,
317 if(!eq.get_head()(vc.get_head(),c.get_head()(v)))return false;
318 return equal_ckey_cval<
319 BOOST_DEDUCED_TYPENAME KeyCons::tail_type,Value,
320 BOOST_DEDUCED_TYPENAME ValCons::tail_type,
321 BOOST_DEDUCED_TYPENAME EqualCons::tail_type
322 >::compare(vc.get_tail(),c.get_tail(),v,eq.get_tail());
328 typename KeyCons,typename Value,
329 typename ValCons,typename EqualCons
331 struct equal_ckey_cval:
334 is_same<KeyCons,tuples::null_type>,
335 is_same<ValCons,tuples::null_type>
337 equal_ckey_cval_terminal<KeyCons,Value,ValCons,EqualCons>,
338 equal_ckey_cval_normal<KeyCons,Value,ValCons,EqualCons>
345 typename KeyCons1,typename Value1,
346 typename KeyCons2, typename Value2,
349 struct compare_ckey_ckey; /* fwd decl. */
353 typename KeyCons1,typename Value1,
354 typename KeyCons2, typename Value2,
357 struct compare_ckey_ckey_terminal
360 const KeyCons1&,const Value1&,
361 const KeyCons2&,const Value2&,
370 typename KeyCons1,typename Value1,
371 typename KeyCons2, typename Value2,
374 struct compare_ckey_ckey_normal
377 const KeyCons1& c0,const Value1& v0,
378 const KeyCons2& c1,const Value2& v1,
379 const CompareCons& comp)
381 if(comp.get_head()(c0.get_head()(v0),c1.get_head()(v1)))return true;
382 if(comp.get_head()(c1.get_head()(v1),c0.get_head()(v0)))return false;
383 return compare_ckey_ckey<
384 BOOST_DEDUCED_TYPENAME KeyCons1::tail_type,Value1,
385 BOOST_DEDUCED_TYPENAME KeyCons2::tail_type,Value2,
386 BOOST_DEDUCED_TYPENAME CompareCons::tail_type
387 >::compare(c0.get_tail(),v0,c1.get_tail(),v1,comp.get_tail());
393 typename KeyCons1,typename Value1,
394 typename KeyCons2, typename Value2,
397 struct compare_ckey_ckey:
400 is_same<KeyCons1,tuples::null_type>,
401 is_same<KeyCons2,tuples::null_type>
403 compare_ckey_ckey_terminal<KeyCons1,Value1,KeyCons2,Value2,CompareCons>,
404 compare_ckey_ckey_normal<KeyCons1,Value1,KeyCons2,Value2,CompareCons>
411 typename KeyCons,typename Value,
412 typename ValCons,typename CompareCons
414 struct compare_ckey_cval; /* fwd decl. */
418 typename KeyCons,typename Value,
419 typename ValCons,typename CompareCons
421 struct compare_ckey_cval_terminal
424 const KeyCons&,const Value&,const ValCons&,const CompareCons&)
430 const ValCons&,const KeyCons&,const Value&,const CompareCons&)
438 typename KeyCons,typename Value,
439 typename ValCons,typename CompareCons
441 struct compare_ckey_cval_normal
444 const KeyCons& c,const Value& v,const ValCons& vc,
445 const CompareCons& comp)
447 if(comp.get_head()(c.get_head()(v),vc.get_head()))return true;
448 if(comp.get_head()(vc.get_head(),c.get_head()(v)))return false;
449 return compare_ckey_cval<
450 BOOST_DEDUCED_TYPENAME KeyCons::tail_type,Value,
451 BOOST_DEDUCED_TYPENAME ValCons::tail_type,
452 BOOST_DEDUCED_TYPENAME CompareCons::tail_type
453 >::compare(c.get_tail(),v,vc.get_tail(),comp.get_tail());
457 const ValCons& vc,const KeyCons& c,const Value& v,
458 const CompareCons& comp)
460 if(comp.get_head()(vc.get_head(),c.get_head()(v)))return true;
461 if(comp.get_head()(c.get_head()(v),vc.get_head()))return false;
462 return compare_ckey_cval<
463 BOOST_DEDUCED_TYPENAME KeyCons::tail_type,Value,
464 BOOST_DEDUCED_TYPENAME ValCons::tail_type,
465 BOOST_DEDUCED_TYPENAME CompareCons::tail_type
466 >::compare(vc.get_tail(),c.get_tail(),v,comp.get_tail());
472 typename KeyCons,typename Value,
473 typename ValCons,typename CompareCons
475 struct compare_ckey_cval:
478 is_same<KeyCons,tuples::null_type>,
479 is_same<ValCons,tuples::null_type>
481 compare_ckey_cval_terminal<KeyCons,Value,ValCons,CompareCons>,
482 compare_ckey_cval_normal<KeyCons,Value,ValCons,CompareCons>
487 template<typename KeyCons,typename Value,typename HashCons>
488 struct hash_ckey; /* fwd decl. */
490 template<typename KeyCons,typename Value,typename HashCons>
491 struct hash_ckey_terminal
493 static std::size_t hash(
494 const KeyCons&,const Value&,const HashCons&,std::size_t carry)
500 template<typename KeyCons,typename Value,typename HashCons>
501 struct hash_ckey_normal
503 static std::size_t hash(
504 const KeyCons& c,const Value& v,const HashCons& h,std::size_t carry=0)
506 /* same hashing formula as boost::hash_combine */
508 carry^=h.get_head()(c.get_head()(v))+0x9e3779b9+(carry<<6)+(carry>>2);
510 BOOST_DEDUCED_TYPENAME KeyCons::tail_type,Value,
511 BOOST_DEDUCED_TYPENAME HashCons::tail_type
512 >::hash(c.get_tail(),v,h.get_tail(),carry);
516 template<typename KeyCons,typename Value,typename HashCons>
519 is_same<KeyCons,tuples::null_type>,
520 hash_ckey_terminal<KeyCons,Value,HashCons>,
521 hash_ckey_normal<KeyCons,Value,HashCons>
526 template<typename ValCons,typename HashCons>
527 struct hash_cval; /* fwd decl. */
529 template<typename ValCons,typename HashCons>
530 struct hash_cval_terminal
532 static std::size_t hash(const ValCons&,const HashCons&,std::size_t carry)
538 template<typename ValCons,typename HashCons>
539 struct hash_cval_normal
541 static std::size_t hash(
542 const ValCons& vc,const HashCons& h,std::size_t carry=0)
544 carry^=h.get_head()(vc.get_head())+0x9e3779b9+(carry<<6)+(carry>>2);
546 BOOST_DEDUCED_TYPENAME ValCons::tail_type,
547 BOOST_DEDUCED_TYPENAME HashCons::tail_type
548 >::hash(vc.get_tail(),h.get_tail(),carry);
552 template<typename ValCons,typename HashCons>
555 is_same<ValCons,tuples::null_type>,
556 hash_cval_terminal<ValCons,HashCons>,
557 hash_cval_normal<ValCons,HashCons>
562 } /* namespace multi_index::detail */
564 /* composite_key_result */
566 template<typename CompositeKey>
567 struct composite_key_result
569 typedef CompositeKey composite_key_type;
570 typedef typename composite_key_type::value_type value_type;
572 composite_key_result(
573 const composite_key_type& composite_key_,const value_type& value_):
574 composite_key(composite_key_),value(value_)
577 const composite_key_type& composite_key;
578 const value_type& value;
583 /* NB. Some overloads of operator() have an extra dummy parameter int=0.
584 * This disambiguator serves several purposes:
585 * - Without it, MSVC++ 6.0 incorrectly regards some overloads as
586 * specializations of a previous member function template.
587 * - MSVC++ 6.0/7.0 seem to incorrectly treat some different memfuns
588 * as if they have the same signature.
589 * - If remove_const is broken due to lack of PTS, int=0 avoids the
590 * declaration of memfuns with identical signature.
595 BOOST_MULTI_INDEX_CK_ENUM(BOOST_MULTI_INDEX_CK_TEMPLATE_PARM,KeyFromValue)
597 struct composite_key:
598 private tuple<BOOST_MULTI_INDEX_CK_ENUM_PARAMS(KeyFromValue)>
601 typedef tuple<BOOST_MULTI_INDEX_CK_ENUM_PARAMS(KeyFromValue)> super;
604 typedef super key_extractor_tuple;
605 typedef Value value_type;
606 typedef composite_key_result<composite_key> result_type;
609 BOOST_MULTI_INDEX_CK_ENUM(BOOST_MULTI_INDEX_CK_CTOR_ARG,KeyFromValue)):
610 super(BOOST_MULTI_INDEX_CK_ENUM_PARAMS(k))
613 composite_key(const key_extractor_tuple& x):super(x){}
615 const key_extractor_tuple& key_extractors()const{return *this;}
616 key_extractor_tuple& key_extractors(){return *this;}
618 template<typename ChainedPtr>
620 #if !defined(BOOST_NO_SFINAE)
622 is_convertible<const ChainedPtr&,const value_type&>,result_type>::type
627 operator()(const ChainedPtr& x)const
629 return operator()(*x);
632 result_type operator()(const value_type& x)const
634 return result_type(*this,x);
637 result_type operator()(const reference_wrapper<const value_type>& x)const
639 return result_type(*this,x.get());
642 result_type operator()(const reference_wrapper<value_type>& x,int=0)const
644 return result_type(*this,x.get());
648 /* comparison operators */
652 template<typename CompositeKey1,typename CompositeKey2>
653 inline bool operator==(
654 const composite_key_result<CompositeKey1>& x,
655 const composite_key_result<CompositeKey2>& y)
657 typedef typename CompositeKey1::key_extractor_tuple key_extractor_tuple1;
658 typedef typename CompositeKey1::value_type value_type1;
659 typedef typename CompositeKey2::key_extractor_tuple key_extractor_tuple2;
660 typedef typename CompositeKey2::value_type value_type2;
663 tuples::length<key_extractor_tuple1>::value==
664 tuples::length<key_extractor_tuple2>::value);
666 return detail::equal_ckey_ckey<
667 key_extractor_tuple1,value_type1,
668 key_extractor_tuple2,value_type2,
669 detail::generic_operator_equal_tuple
671 x.composite_key.key_extractors(),x.value,
672 y.composite_key.key_extractors(),y.value,
673 detail::generic_operator_equal_tuple());
677 typename CompositeKey,
678 BOOST_MULTI_INDEX_CK_ENUM_PARAMS(typename Value)
680 inline bool operator==(
681 const composite_key_result<CompositeKey>& x,
682 const tuple<BOOST_MULTI_INDEX_CK_ENUM_PARAMS(Value)>& y)
684 typedef typename CompositeKey::key_extractor_tuple key_extractor_tuple;
685 typedef typename CompositeKey::value_type value_type;
686 typedef tuple<BOOST_MULTI_INDEX_CK_ENUM_PARAMS(Value)> key_tuple;
689 tuples::length<key_extractor_tuple>::value==
690 tuples::length<key_tuple>::value);
692 return detail::equal_ckey_cval<
693 key_extractor_tuple,value_type,
694 key_tuple,detail::generic_operator_equal_tuple
696 x.composite_key.key_extractors(),x.value,
697 y,detail::generic_operator_equal_tuple());
702 BOOST_MULTI_INDEX_CK_ENUM_PARAMS(typename Value),
703 typename CompositeKey
705 inline bool operator==(
706 const tuple<BOOST_MULTI_INDEX_CK_ENUM_PARAMS(Value)>& x,
707 const composite_key_result<CompositeKey>& y)
709 typedef typename CompositeKey::key_extractor_tuple key_extractor_tuple;
710 typedef typename CompositeKey::value_type value_type;
711 typedef tuple<BOOST_MULTI_INDEX_CK_ENUM_PARAMS(Value)> key_tuple;
714 tuples::length<key_extractor_tuple>::value==
715 tuples::length<key_tuple>::value);
717 return detail::equal_ckey_cval<
718 key_extractor_tuple,value_type,
719 key_tuple,detail::generic_operator_equal_tuple
721 x,y.composite_key.key_extractors(),
722 y.value,detail::generic_operator_equal_tuple());
727 template<typename CompositeKey1,typename CompositeKey2>
728 inline bool operator<(
729 const composite_key_result<CompositeKey1>& x,
730 const composite_key_result<CompositeKey2>& y)
732 typedef typename CompositeKey1::key_extractor_tuple key_extractor_tuple1;
733 typedef typename CompositeKey1::value_type value_type1;
734 typedef typename CompositeKey2::key_extractor_tuple key_extractor_tuple2;
735 typedef typename CompositeKey2::value_type value_type2;
737 return detail::compare_ckey_ckey<
738 key_extractor_tuple1,value_type1,
739 key_extractor_tuple2,value_type2,
740 detail::generic_operator_less_tuple
742 x.composite_key.key_extractors(),x.value,
743 y.composite_key.key_extractors(),y.value,
744 detail::generic_operator_less_tuple());
749 typename CompositeKey,
750 BOOST_MULTI_INDEX_CK_ENUM_PARAMS(typename Value)
752 inline bool operator<(
753 const composite_key_result<CompositeKey>& x,
754 const tuple<BOOST_MULTI_INDEX_CK_ENUM_PARAMS(Value)>& y)
756 typedef typename CompositeKey::key_extractor_tuple key_extractor_tuple;
757 typedef typename CompositeKey::value_type value_type;
758 typedef tuple<BOOST_MULTI_INDEX_CK_ENUM_PARAMS(Value)> key_tuple;
760 return detail::compare_ckey_cval<
761 key_extractor_tuple,value_type,
762 key_tuple,detail::generic_operator_less_tuple
764 x.composite_key.key_extractors(),x.value,
765 y,detail::generic_operator_less_tuple());
770 BOOST_MULTI_INDEX_CK_ENUM_PARAMS(typename Value),
771 typename CompositeKey
773 inline bool operator<(
774 const tuple<BOOST_MULTI_INDEX_CK_ENUM_PARAMS(Value)>& x,
775 const composite_key_result<CompositeKey>& y)
777 typedef typename CompositeKey::key_extractor_tuple key_extractor_tuple;
778 typedef typename CompositeKey::value_type value_type;
779 typedef tuple<BOOST_MULTI_INDEX_CK_ENUM_PARAMS(Value)> key_tuple;
781 return detail::compare_ckey_cval<
782 key_extractor_tuple,value_type,
783 key_tuple,detail::generic_operator_less_tuple
785 x,y.composite_key.key_extractors(),
786 y.value,detail::generic_operator_less_tuple());
789 /* rest of comparison operators */
791 #define BOOST_MULTI_INDEX_CK_COMPLETE_COMP_OPS(t1,t2,a1,a2) \
792 template<t1,t2> inline bool operator!=(const a1& x,const a2& y) \
797 template<t1,t2> inline bool operator>(const a1& x,const a2& y) \
802 template<t1,t2> inline bool operator>=(const a1& x,const a2& y) \
807 template<t1,t2> inline bool operator<=(const a1& x,const a2& y) \
812 BOOST_MULTI_INDEX_CK_COMPLETE_COMP_OPS(
813 typename CompositeKey1,
814 typename CompositeKey2,
815 composite_key_result<CompositeKey1>,
816 composite_key_result<CompositeKey2>
819 BOOST_MULTI_INDEX_CK_COMPLETE_COMP_OPS(
820 typename CompositeKey,
821 BOOST_MULTI_INDEX_CK_ENUM_PARAMS(typename Value),
822 composite_key_result<CompositeKey>,
823 tuple<BOOST_MULTI_INDEX_CK_ENUM_PARAMS(Value)>
826 BOOST_MULTI_INDEX_CK_COMPLETE_COMP_OPS(
827 BOOST_MULTI_INDEX_CK_ENUM_PARAMS(typename Value),
828 typename CompositeKey,
829 tuple<BOOST_MULTI_INDEX_CK_ENUM_PARAMS(Value)>,
830 composite_key_result<CompositeKey>
833 /* composite_key_equal_to */
837 BOOST_MULTI_INDEX_CK_ENUM(BOOST_MULTI_INDEX_CK_TEMPLATE_PARM,Pred)
839 struct composite_key_equal_to:
840 private tuple<BOOST_MULTI_INDEX_CK_ENUM_PARAMS(Pred)>
843 typedef tuple<BOOST_MULTI_INDEX_CK_ENUM_PARAMS(Pred)> super;
846 typedef super key_eq_tuple;
848 composite_key_equal_to(
849 BOOST_MULTI_INDEX_CK_ENUM(BOOST_MULTI_INDEX_CK_CTOR_ARG,Pred)):
850 super(BOOST_MULTI_INDEX_CK_ENUM_PARAMS(k))
853 composite_key_equal_to(const key_eq_tuple& x):super(x){}
855 const key_eq_tuple& key_eqs()const{return *this;}
856 key_eq_tuple& key_eqs(){return *this;}
858 template<typename CompositeKey1,typename CompositeKey2>
860 const composite_key_result<CompositeKey1> & x,
861 const composite_key_result<CompositeKey2> & y)const
863 typedef typename CompositeKey1::key_extractor_tuple key_extractor_tuple1;
864 typedef typename CompositeKey1::value_type value_type1;
865 typedef typename CompositeKey2::key_extractor_tuple key_extractor_tuple2;
866 typedef typename CompositeKey2::value_type value_type2;
869 tuples::length<key_extractor_tuple1>::value<=
870 tuples::length<key_eq_tuple>::value&&
871 tuples::length<key_extractor_tuple1>::value==
872 tuples::length<key_extractor_tuple2>::value);
874 return detail::equal_ckey_ckey<
875 key_extractor_tuple1,value_type1,
876 key_extractor_tuple2,value_type2,
879 x.composite_key.key_extractors(),x.value,
880 y.composite_key.key_extractors(),y.value,
886 typename CompositeKey,
887 BOOST_MULTI_INDEX_CK_ENUM_PARAMS(typename Value)
890 const composite_key_result<CompositeKey>& x,
891 const tuple<BOOST_MULTI_INDEX_CK_ENUM_PARAMS(Value)>& y)const
893 typedef typename CompositeKey::key_extractor_tuple key_extractor_tuple;
894 typedef typename CompositeKey::value_type value_type;
895 typedef tuple<BOOST_MULTI_INDEX_CK_ENUM_PARAMS(Value)> key_tuple;
898 tuples::length<key_extractor_tuple>::value<=
899 tuples::length<key_eq_tuple>::value&&
900 tuples::length<key_extractor_tuple>::value==
901 tuples::length<key_tuple>::value);
903 return detail::equal_ckey_cval<
904 key_extractor_tuple,value_type,
905 key_tuple,key_eq_tuple
906 >::compare(x.composite_key.key_extractors(),x.value,y,key_eqs());
911 BOOST_MULTI_INDEX_CK_ENUM_PARAMS(typename Value),
912 typename CompositeKey
915 const tuple<BOOST_MULTI_INDEX_CK_ENUM_PARAMS(Value)>& x,
916 const composite_key_result<CompositeKey>& y)const
918 typedef typename CompositeKey::key_extractor_tuple key_extractor_tuple;
919 typedef typename CompositeKey::value_type value_type;
920 typedef tuple<BOOST_MULTI_INDEX_CK_ENUM_PARAMS(Value)> key_tuple;
923 tuples::length<key_tuple>::value<=
924 tuples::length<key_eq_tuple>::value&&
925 tuples::length<key_tuple>::value==
926 tuples::length<key_extractor_tuple>::value);
928 return detail::equal_ckey_cval<
929 key_extractor_tuple,value_type,
930 key_tuple,key_eq_tuple
931 >::compare(x,y.composite_key.key_extractors(),y.value,key_eqs());
935 /* composite_key_compare */
939 BOOST_MULTI_INDEX_CK_ENUM(BOOST_MULTI_INDEX_CK_TEMPLATE_PARM,Compare)
941 struct composite_key_compare:
942 private tuple<BOOST_MULTI_INDEX_CK_ENUM_PARAMS(Compare)>
945 typedef tuple<BOOST_MULTI_INDEX_CK_ENUM_PARAMS(Compare)> super;
948 typedef super key_comp_tuple;
950 composite_key_compare(
951 BOOST_MULTI_INDEX_CK_ENUM(BOOST_MULTI_INDEX_CK_CTOR_ARG,Compare)):
952 super(BOOST_MULTI_INDEX_CK_ENUM_PARAMS(k))
955 composite_key_compare(const key_comp_tuple& x):super(x){}
957 const key_comp_tuple& key_comps()const{return *this;}
958 key_comp_tuple& key_comps(){return *this;}
960 template<typename CompositeKey1,typename CompositeKey2>
962 const composite_key_result<CompositeKey1> & x,
963 const composite_key_result<CompositeKey2> & y)const
965 typedef typename CompositeKey1::key_extractor_tuple key_extractor_tuple1;
966 typedef typename CompositeKey1::value_type value_type1;
967 typedef typename CompositeKey2::key_extractor_tuple key_extractor_tuple2;
968 typedef typename CompositeKey2::value_type value_type2;
971 tuples::length<key_extractor_tuple1>::value<=
972 tuples::length<key_comp_tuple>::value||
973 tuples::length<key_extractor_tuple2>::value<=
974 tuples::length<key_comp_tuple>::value);
976 return detail::compare_ckey_ckey<
977 key_extractor_tuple1,value_type1,
978 key_extractor_tuple2,value_type2,
981 x.composite_key.key_extractors(),x.value,
982 y.composite_key.key_extractors(),y.value,
986 #if !defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING)
987 template<typename CompositeKey,typename Value>
989 const composite_key_result<CompositeKey>& x,
992 return operator()(x,make_tuple(cref(y)));
998 typename CompositeKey,
999 BOOST_MULTI_INDEX_CK_ENUM_PARAMS(typename Value)
1002 const composite_key_result<CompositeKey>& x,
1003 const tuple<BOOST_MULTI_INDEX_CK_ENUM_PARAMS(Value)>& y)const
1005 typedef typename CompositeKey::key_extractor_tuple key_extractor_tuple;
1006 typedef typename CompositeKey::value_type value_type;
1007 typedef tuple<BOOST_MULTI_INDEX_CK_ENUM_PARAMS(Value)> key_tuple;
1009 BOOST_STATIC_ASSERT(
1010 tuples::length<key_extractor_tuple>::value<=
1011 tuples::length<key_comp_tuple>::value||
1012 tuples::length<key_tuple>::value<=
1013 tuples::length<key_comp_tuple>::value);
1015 return detail::compare_ckey_cval<
1016 key_extractor_tuple,value_type,
1017 key_tuple,key_comp_tuple
1018 >::compare(x.composite_key.key_extractors(),x.value,y,key_comps());
1021 #if !defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING)
1022 template<typename Value,typename CompositeKey>
1025 const composite_key_result<CompositeKey>& y)const
1027 return operator()(make_tuple(cref(x)),y);
1033 BOOST_MULTI_INDEX_CK_ENUM_PARAMS(typename Value),
1034 typename CompositeKey
1037 const tuple<BOOST_MULTI_INDEX_CK_ENUM_PARAMS(Value)>& x,
1038 const composite_key_result<CompositeKey>& y)const
1040 typedef typename CompositeKey::key_extractor_tuple key_extractor_tuple;
1041 typedef typename CompositeKey::value_type value_type;
1042 typedef tuple<BOOST_MULTI_INDEX_CK_ENUM_PARAMS(Value)> key_tuple;
1044 BOOST_STATIC_ASSERT(
1045 tuples::length<key_tuple>::value<=
1046 tuples::length<key_comp_tuple>::value||
1047 tuples::length<key_extractor_tuple>::value<=
1048 tuples::length<key_comp_tuple>::value);
1050 return detail::compare_ckey_cval<
1051 key_extractor_tuple,value_type,
1052 key_tuple,key_comp_tuple
1053 >::compare(x,y.composite_key.key_extractors(),y.value,key_comps());
1057 /* composite_key_hash */
1061 BOOST_MULTI_INDEX_CK_ENUM(BOOST_MULTI_INDEX_CK_TEMPLATE_PARM,Hash)
1063 struct composite_key_hash:
1064 private tuple<BOOST_MULTI_INDEX_CK_ENUM_PARAMS(Hash)>
1067 typedef tuple<BOOST_MULTI_INDEX_CK_ENUM_PARAMS(Hash)> super;
1070 typedef super key_hasher_tuple;
1073 BOOST_MULTI_INDEX_CK_ENUM(BOOST_MULTI_INDEX_CK_CTOR_ARG,Hash)):
1074 super(BOOST_MULTI_INDEX_CK_ENUM_PARAMS(k))
1077 composite_key_hash(const key_hasher_tuple& x):super(x){}
1079 const key_hasher_tuple& key_hash_functions()const{return *this;}
1080 key_hasher_tuple& key_hash_functions(){return *this;}
1082 template<typename CompositeKey>
1083 std::size_t operator()(const composite_key_result<CompositeKey> & x)const
1085 typedef typename CompositeKey::key_extractor_tuple key_extractor_tuple;
1086 typedef typename CompositeKey::value_type value_type;
1088 BOOST_STATIC_ASSERT(
1089 tuples::length<key_extractor_tuple>::value==
1090 tuples::length<key_hasher_tuple>::value);
1092 return detail::hash_ckey<
1093 key_extractor_tuple,value_type,
1095 >::hash(x.composite_key.key_extractors(),x.value,key_hash_functions());
1098 template<BOOST_MULTI_INDEX_CK_ENUM_PARAMS(typename Value)>
1099 std::size_t operator()(
1100 const tuple<BOOST_MULTI_INDEX_CK_ENUM_PARAMS(Value)>& x)const
1102 typedef tuple<BOOST_MULTI_INDEX_CK_ENUM_PARAMS(Value)> key_tuple;
1104 BOOST_STATIC_ASSERT(
1105 tuples::length<key_tuple>::value==
1106 tuples::length<key_hasher_tuple>::value);
1108 return detail::hash_cval<
1109 key_tuple,key_hasher_tuple
1110 >::hash(x,key_hash_functions());
1114 /* Instantiations of the former functors with "natural" basic components:
1115 * composite_key_result_equal_to uses std::equal_to of the values.
1116 * composite_key_result_less uses std::less.
1117 * composite_key_result_greater uses std::greater.
1118 * composite_key_result_hash uses boost::hash.
1121 #define BOOST_MULTI_INDEX_CK_RESULT_EQUAL_TO_SUPER \
1122 composite_key_equal_to< \
1123 BOOST_MULTI_INDEX_CK_ENUM( \
1124 BOOST_MULTI_INDEX_CK_APPLY_METAFUNCTION_N, \
1125 /* the argument is a PP list */ \
1126 (detail::nth_composite_key_equal_to, \
1127 (BOOST_DEDUCED_TYPENAME CompositeKeyResult::composite_key_type, \
1131 template<typename CompositeKeyResult>
1132 struct composite_key_result_equal_to:
1133 BOOST_MULTI_INDEX_PRIVATE_IF_USING_DECL_FOR_TEMPL_FUNCTIONS
1134 BOOST_MULTI_INDEX_CK_RESULT_EQUAL_TO_SUPER
1137 typedef BOOST_MULTI_INDEX_CK_RESULT_EQUAL_TO_SUPER super;
1140 typedef CompositeKeyResult first_argument_type;
1141 typedef first_argument_type second_argument_type;
1142 typedef bool result_type;
1144 using super::operator();
1147 #define BOOST_MULTI_INDEX_CK_RESULT_LESS_SUPER \
1148 composite_key_compare< \
1149 BOOST_MULTI_INDEX_CK_ENUM( \
1150 BOOST_MULTI_INDEX_CK_APPLY_METAFUNCTION_N, \
1151 /* the argument is a PP list */ \
1152 (detail::nth_composite_key_less, \
1153 (BOOST_DEDUCED_TYPENAME CompositeKeyResult::composite_key_type, \
1157 template<typename CompositeKeyResult>
1158 struct composite_key_result_less:
1159 BOOST_MULTI_INDEX_PRIVATE_IF_USING_DECL_FOR_TEMPL_FUNCTIONS
1160 BOOST_MULTI_INDEX_CK_RESULT_LESS_SUPER
1163 typedef BOOST_MULTI_INDEX_CK_RESULT_LESS_SUPER super;
1166 typedef CompositeKeyResult first_argument_type;
1167 typedef first_argument_type second_argument_type;
1168 typedef bool result_type;
1170 using super::operator();
1173 #define BOOST_MULTI_INDEX_CK_RESULT_GREATER_SUPER \
1174 composite_key_compare< \
1175 BOOST_MULTI_INDEX_CK_ENUM( \
1176 BOOST_MULTI_INDEX_CK_APPLY_METAFUNCTION_N, \
1177 /* the argument is a PP list */ \
1178 (detail::nth_composite_key_greater, \
1179 (BOOST_DEDUCED_TYPENAME CompositeKeyResult::composite_key_type, \
1183 template<typename CompositeKeyResult>
1184 struct composite_key_result_greater:
1185 BOOST_MULTI_INDEX_PRIVATE_IF_USING_DECL_FOR_TEMPL_FUNCTIONS
1186 BOOST_MULTI_INDEX_CK_RESULT_GREATER_SUPER
1189 typedef BOOST_MULTI_INDEX_CK_RESULT_GREATER_SUPER super;
1192 typedef CompositeKeyResult first_argument_type;
1193 typedef first_argument_type second_argument_type;
1194 typedef bool result_type;
1196 using super::operator();
1199 #define BOOST_MULTI_INDEX_CK_RESULT_HASH_SUPER \
1200 composite_key_hash< \
1201 BOOST_MULTI_INDEX_CK_ENUM( \
1202 BOOST_MULTI_INDEX_CK_APPLY_METAFUNCTION_N, \
1203 /* the argument is a PP list */ \
1204 (detail::nth_composite_key_hash, \
1205 (BOOST_DEDUCED_TYPENAME CompositeKeyResult::composite_key_type, \
1209 template<typename CompositeKeyResult>
1210 struct composite_key_result_hash:
1211 BOOST_MULTI_INDEX_PRIVATE_IF_USING_DECL_FOR_TEMPL_FUNCTIONS
1212 BOOST_MULTI_INDEX_CK_RESULT_HASH_SUPER
1215 typedef BOOST_MULTI_INDEX_CK_RESULT_HASH_SUPER super;
1218 typedef CompositeKeyResult argument_type;
1219 typedef std::size_t result_type;
1221 using super::operator();
1224 } /* namespace multi_index */
1226 } /* namespace boost */
1228 /* Specializations of std::equal_to, std::less, std::greater and boost::hash
1229 * for composite_key_results enabling interoperation with tuples of values.
1232 #if !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION)
1235 template<typename CompositeKey>
1236 struct equal_to<boost::multi_index::composite_key_result<CompositeKey> >:
1237 boost::multi_index::composite_key_result_equal_to<
1238 boost::multi_index::composite_key_result<CompositeKey>
1243 template<typename CompositeKey>
1244 struct less<boost::multi_index::composite_key_result<CompositeKey> >:
1245 boost::multi_index::composite_key_result_less<
1246 boost::multi_index::composite_key_result<CompositeKey>
1251 template<typename CompositeKey>
1252 struct greater<boost::multi_index::composite_key_result<CompositeKey> >:
1253 boost::multi_index::composite_key_result_greater<
1254 boost::multi_index::composite_key_result<CompositeKey>
1259 } /* namespace std */
1263 template<typename CompositeKey>
1264 struct hash<boost::multi_index::composite_key_result<CompositeKey> >:
1265 boost::multi_index::composite_key_result_hash<
1266 boost::multi_index::composite_key_result<CompositeKey>
1271 } /* namespace boost */
1273 /* Lacking template partial specialization, std::equal_to, std::less and
1274 * std::greater will still work for composite_key_results although without
1275 * tuple interoperability. To achieve the same graceful degrading with
1276 * boost::hash, we define the appropriate hash_value overload.
1281 #if !defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
1282 namespace multi_index{
1285 template<typename CompositeKey>
1286 inline std::size_t hash_value(
1287 const boost::multi_index::composite_key_result<CompositeKey>& x)
1289 boost::multi_index::composite_key_result_hash<
1290 boost::multi_index::composite_key_result<CompositeKey> > h;
1294 #if !defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
1295 } /* namespace multi_index */
1298 } /* namespace boost */
1301 #undef BOOST_MULTI_INDEX_CK_RESULT_HASH_SUPER
1302 #undef BOOST_MULTI_INDEX_CK_RESULT_GREATER_SUPER
1303 #undef BOOST_MULTI_INDEX_CK_RESULT_LESS_SUPER
1304 #undef BOOST_MULTI_INDEX_CK_RESULT_EQUAL_TO_SUPER
1305 #undef BOOST_MULTI_INDEX_CK_COMPLETE_COMP_OPS
1306 #undef BOOST_MULTI_INDEX_CK_IDENTITY_ENUM_MACRO
1307 #undef BOOST_MULTI_INDEX_CK_NTH_COMPOSITE_KEY_FUNCTOR
1308 #undef BOOST_MULTI_INDEX_CK_APPLY_METAFUNCTION_N
1309 #undef BOOST_MULTI_INDEX_CK_CTOR_ARG
1310 #undef BOOST_MULTI_INDEX_CK_TEMPLATE_PARM
1311 #undef BOOST_MULTI_INDEX_CK_ENUM_PARAMS
1312 #undef BOOST_MULTI_INDEX_CK_ENUM
1313 #undef BOOST_MULTI_INDEX_COMPOSITE_KEY_SIZE