1 /* Multiply indexed container.
2  *
3  * Copyright 2003-2017 Joaquin M Lopez Munoz.
4  * Distributed under the Boost Software License, Version 1.0.
5  * (See accompanying file LICENSE_1_0.txt or copy at
6  * http://www.boost.org/LICENSE_1_0.txt)
7  *
8  * See http://www.boost.org/libs/multi_index for library home page.
9  */
10 
11 #ifndef BOOST_MULTI_INDEX_HPP
12 #define BOOST_MULTI_INDEX_HPP
13 
14 #if defined(_MSC_VER)
15 #pragma once
16 #endif
17 
18 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
19 #include <algorithm>
20 #include <boost/detail/allocator_utilities.hpp>
21 #include <boost/detail/no_exceptions_support.hpp>
22 #include <boost/detail/workaround.hpp>
23 #include <boost/move/core.hpp>
24 #include <boost/mpl/at.hpp>
25 #include <boost/mpl/contains.hpp>
26 #include <boost/mpl/find_if.hpp>
27 #include <boost/mpl/identity.hpp>
28 #include <boost/mpl/int.hpp>
29 #include <boost/mpl/size.hpp>
30 #include <boost/mpl/deref.hpp>
31 #include <boost/multi_index_container_fwd.hpp>
32 #include <boost/multi_index/detail/access_specifier.hpp>
33 #include <boost/multi_index/detail/adl_swap.hpp>
34 #include <boost/multi_index/detail/base_type.hpp>
35 #include <boost/multi_index/detail/do_not_copy_elements_tag.hpp>
36 #include <boost/multi_index/detail/converter.hpp>
37 #include <boost/multi_index/detail/header_holder.hpp>
38 #include <boost/multi_index/detail/has_tag.hpp>
39 #include <boost/multi_index/detail/no_duplicate_tags.hpp>
40 #include <boost/multi_index/detail/safe_mode.hpp>
41 #include <boost/multi_index/detail/scope_guard.hpp>
42 #include <boost/multi_index/detail/vartempl_support.hpp>
43 #include <boost/static_assert.hpp>
44 #include <boost/type_traits/is_same.hpp>
45 #include <boost/utility/base_from_member.hpp>
46 
47 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
48 #include <initializer_list>
49 #endif
50 
51 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
52 #include <boost/multi_index/detail/archive_constructed.hpp>
53 #include <boost/multi_index/detail/serialization_version.hpp>
54 #include <boost/serialization/collection_size_type.hpp>
55 #include <boost/serialization/nvp.hpp>
56 #include <boost/serialization/split_member.hpp>
57 #include <boost/serialization/version.hpp>
58 #include <boost/throw_exception.hpp>
59 #endif
60 
61 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
62 #include <boost/multi_index/detail/invariant_assert.hpp>
63 #define BOOST_MULTI_INDEX_CHECK_INVARIANT_OF(x)                              \
64   detail::scope_guard BOOST_JOIN(check_invariant_,__LINE__)=                 \
65     detail::make_obj_guard(x,&multi_index_container::check_invariant_);      \
66   BOOST_JOIN(check_invariant_,__LINE__).touch();
67 #define BOOST_MULTI_INDEX_CHECK_INVARIANT                                    \
68   BOOST_MULTI_INDEX_CHECK_INVARIANT_OF(*this)
69 #else
70 #define BOOST_MULTI_INDEX_CHECK_INVARIANT_OF(x)
71 #define BOOST_MULTI_INDEX_CHECK_INVARIANT
72 #endif
73 
74 namespace boost{
75 
76 namespace multi_index{
77 
78 #if BOOST_WORKAROUND(BOOST_MSVC,BOOST_TESTED_AT(1500))
79 #pragma warning(push)
80 #pragma warning(disable:4522) /* spurious warning on multiple operator=()'s */
81 #endif
82 
83 template<typename Value,typename IndexSpecifierList,typename Allocator>
84 class multi_index_container:
85   private ::boost::base_from_member<
86     typename boost::detail::allocator::rebind_to<
87       Allocator,
88       typename detail::multi_index_node_type<
89         Value,IndexSpecifierList,Allocator>::type
90     >::type>,
91   BOOST_MULTI_INDEX_PRIVATE_IF_MEMBER_TEMPLATE_FRIENDS detail::header_holder<
92     typename boost::detail::allocator::rebind_to<
93       Allocator,
94       typename detail::multi_index_node_type<
95         Value,IndexSpecifierList,Allocator>::type
96     >::type::pointer,
97     multi_index_container<Value,IndexSpecifierList,Allocator> >,
98   public detail::multi_index_base_type<
99     Value,IndexSpecifierList,Allocator>::type
100 {
101 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
102     BOOST_WORKAROUND(__MWERKS__,<=0x3003)
103 /* The "ISO C++ Template Parser" option in CW8.3 has a problem with the
104  * lifetime of const references bound to temporaries --precisely what
105  * scopeguards are.
106  */
107 
108 #pragma parse_mfunc_templ off
109 #endif
110 
111 private:
112   BOOST_COPYABLE_AND_MOVABLE(multi_index_container)
113 
114 #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
115   template <typename,typename,typename> friend class  detail::index_base;
116   template <typename,typename>          friend struct detail::header_holder;
117   template <typename,typename>          friend struct detail::converter;
118 #endif
119 
120   typedef typename detail::multi_index_base_type<
121       Value,IndexSpecifierList,Allocator>::type   super;
122   typedef typename
123   boost::detail::allocator::rebind_to<
124     Allocator,
125     typename super::node_type
126   >::type                                         node_allocator;
127   typedef ::boost::base_from_member<
128     node_allocator>                               bfm_allocator;
129   typedef detail::header_holder<
130     typename node_allocator::pointer,
131     multi_index_container>                        bfm_header;
132 
133 
134 public:
135   /* All types are inherited from super, a few are explicitly
136    * brought forward here to save us some typename's.
137    */
138 
139   typedef typename super::ctor_args_list           ctor_args_list;
140   typedef IndexSpecifierList                       index_specifier_type_list;
141 
142   typedef typename super::index_type_list          index_type_list;
143 
144   typedef typename super::iterator_type_list       iterator_type_list;
145   typedef typename super::const_iterator_type_list const_iterator_type_list;
146   typedef typename super::value_type               value_type;
147   typedef typename super::final_allocator_type     allocator_type;
148   typedef typename super::iterator                 iterator;
149   typedef typename super::const_iterator           const_iterator;
150 
151   BOOST_STATIC_ASSERT(
152     detail::no_duplicate_tags_in_index_list<index_type_list>::value);
153 
154   /* global project() needs to see this publicly */
155 
156   typedef typename super::node_type node_type;
157 
158   /* construct/copy/destroy */
159 
multi_index_container(const ctor_args_list & args_list=typename mpl::identity<multi_index_container>::type::ctor_args_list (),const allocator_type & al=typename mpl::identity<multi_index_container>::type::allocator_type ())160   explicit multi_index_container(
161 
162 #if BOOST_WORKAROUND(__IBMCPP__,<=600)
163     /* VisualAge seems to have an ETI issue with the default values
164      * for arguments args_list and al.
165      */
166 
167     const ctor_args_list& args_list=
168       typename mpl::identity<multi_index_container>::type::
169         ctor_args_list(),
170     const allocator_type& al=
171       typename mpl::identity<multi_index_container>::type::
172         allocator_type()):
173 #else
174     const ctor_args_list& args_list=ctor_args_list(),
175     const allocator_type& al=allocator_type()):
176 #endif
177 
178     bfm_allocator(al),
179     super(args_list,bfm_allocator::member),
180     node_count(0)
181   {
182     BOOST_MULTI_INDEX_CHECK_INVARIANT;
183   }
184 
multi_index_container(const allocator_type & al)185   explicit multi_index_container(const allocator_type& al):
186     bfm_allocator(al),
187     super(ctor_args_list(),bfm_allocator::member),
188     node_count(0)
189   {
190     BOOST_MULTI_INDEX_CHECK_INVARIANT;
191   }
192 
193   template<typename InputIterator>
multi_index_container(InputIterator first,InputIterator last,const ctor_args_list & args_list=typename mpl::identity<multi_index_container>::type::ctor_args_list (),const allocator_type & al=typename mpl::identity<multi_index_container>::type::allocator_type ())194   multi_index_container(
195     InputIterator first,InputIterator last,
196 
197 #if BOOST_WORKAROUND(__IBMCPP__,<=600)
198     /* VisualAge seems to have an ETI issue with the default values
199      * for arguments args_list and al.
200      */
201 
202     const ctor_args_list& args_list=
203       typename mpl::identity<multi_index_container>::type::
204         ctor_args_list(),
205     const allocator_type& al=
206       typename mpl::identity<multi_index_container>::type::
207         allocator_type()):
208 #else
209     const ctor_args_list& args_list=ctor_args_list(),
210     const allocator_type& al=allocator_type()):
211 #endif
212 
213     bfm_allocator(al),
214     super(args_list,bfm_allocator::member),
215     node_count(0)
216   {
217     BOOST_MULTI_INDEX_CHECK_INVARIANT;
218     BOOST_TRY{
219       iterator hint=super::end();
220       for(;first!=last;++first){
221         hint=super::make_iterator(
222           insert_ref_(*first,hint.get_node()).first);
223         ++hint;
224       }
225     }
226     BOOST_CATCH(...){
227       clear_();
228       BOOST_RETHROW;
229     }
230     BOOST_CATCH_END
231   }
232 
233 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
multi_index_container(std::initializer_list<Value> list,const ctor_args_list & args_list=ctor_args_list (),const allocator_type & al=allocator_type ())234   multi_index_container(
235     std::initializer_list<Value> list,
236     const ctor_args_list& args_list=ctor_args_list(),
237     const allocator_type& al=allocator_type()):
238     bfm_allocator(al),
239     super(args_list,bfm_allocator::member),
240     node_count(0)
241   {
242     BOOST_MULTI_INDEX_CHECK_INVARIANT;
243     BOOST_TRY{
244       typedef const Value* init_iterator;
245 
246       iterator hint=super::end();
247       for(init_iterator first=list.begin(),last=list.end();
248           first!=last;++first){
249         hint=super::make_iterator(insert_(*first,hint.get_node()).first);
250         ++hint;
251       }
252     }
253     BOOST_CATCH(...){
254       clear_();
255       BOOST_RETHROW;
256     }
257     BOOST_CATCH_END
258   }
259 #endif
260 
multi_index_container(const multi_index_container<Value,IndexSpecifierList,Allocator> & x)261   multi_index_container(
262     const multi_index_container<Value,IndexSpecifierList,Allocator>& x):
263     bfm_allocator(x.bfm_allocator::member),
264     bfm_header(),
265     super(x),
266     node_count(0)
267   {
268     copy_map_type map(bfm_allocator::member,x.size(),x.header(),header());
269     for(const_iterator it=x.begin(),it_end=x.end();it!=it_end;++it){
270       map.clone(it.get_node());
271     }
272     super::copy_(x,map);
273     map.release();
274     node_count=x.size();
275 
276     /* Not until this point are the indices required to be consistent,
277      * hence the position of the invariant checker.
278      */
279 
280     BOOST_MULTI_INDEX_CHECK_INVARIANT;
281   }
282 
multi_index_container(BOOST_RV_REF (multi_index_container)x)283   multi_index_container(BOOST_RV_REF(multi_index_container) x):
284     bfm_allocator(x.bfm_allocator::member),
285     bfm_header(),
286     super(x,detail::do_not_copy_elements_tag()),
287     node_count(0)
288   {
289     BOOST_MULTI_INDEX_CHECK_INVARIANT;
290     BOOST_MULTI_INDEX_CHECK_INVARIANT_OF(x);
291     swap_elements_(x);
292   }
293 
~multi_index_container()294   ~multi_index_container()
295   {
296     delete_all_nodes_();
297   }
298 
299 #if defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
300   /* As per http://www.boost.org/doc/html/move/emulation_limitations.html
301    * #move.emulation_limitations.assignment_operator
302    */
303 
operator =(const multi_index_container<Value,IndexSpecifierList,Allocator> & x)304   multi_index_container<Value,IndexSpecifierList,Allocator>& operator=(
305     const multi_index_container<Value,IndexSpecifierList,Allocator>& x)
306   {
307     multi_index_container y(x);
308     this->swap(y);
309     return *this;
310   }
311 #endif
312 
operator =(BOOST_COPY_ASSIGN_REF (multi_index_container)x)313   multi_index_container<Value,IndexSpecifierList,Allocator>& operator=(
314     BOOST_COPY_ASSIGN_REF(multi_index_container) x)
315   {
316     multi_index_container y(x);
317     this->swap(y);
318     return *this;
319   }
320 
operator =(BOOST_RV_REF (multi_index_container)x)321   multi_index_container<Value,IndexSpecifierList,Allocator>& operator=(
322     BOOST_RV_REF(multi_index_container) x)
323   {
324     this->swap(x);
325     return *this;
326   }
327 
328 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
operator =(std::initializer_list<Value> list)329   multi_index_container<Value,IndexSpecifierList,Allocator>& operator=(
330     std::initializer_list<Value> list)
331   {
332     BOOST_MULTI_INDEX_CHECK_INVARIANT;
333     typedef const Value* init_iterator;
334 
335     multi_index_container x(*this,detail::do_not_copy_elements_tag());
336     iterator hint=x.end();
337     for(init_iterator first=list.begin(),last=list.end();
338         first!=last;++first){
339       hint=x.make_iterator(x.insert_(*first,hint.get_node()).first);
340       ++hint;
341     }
342     x.swap_elements_(*this);
343     return*this;
344   }
345 #endif
346 
get_allocator() const347   allocator_type get_allocator()const BOOST_NOEXCEPT
348   {
349     return allocator_type(bfm_allocator::member);
350   }
351 
352   /* retrieval of indices by number */
353 
354 #if !defined(BOOST_NO_MEMBER_TEMPLATES)
355   template<int N>
356   struct nth_index
357   {
358     BOOST_STATIC_ASSERT(N>=0&&N<mpl::size<index_type_list>::type::value);
359     typedef typename mpl::at_c<index_type_list,N>::type type;
360   };
361 
362   template<int N>
get()363   typename nth_index<N>::type& get()BOOST_NOEXCEPT
364   {
365     BOOST_STATIC_ASSERT(N>=0&&N<mpl::size<index_type_list>::type::value);
366     return *this;
367   }
368 
369   template<int N>
get() const370   const typename nth_index<N>::type& get()const BOOST_NOEXCEPT
371   {
372     BOOST_STATIC_ASSERT(N>=0&&N<mpl::size<index_type_list>::type::value);
373     return *this;
374   }
375 #endif
376 
377   /* retrieval of indices by tag */
378 
379 #if !defined(BOOST_NO_MEMBER_TEMPLATES)
380   template<typename Tag>
381   struct index
382   {
383     typedef typename mpl::find_if<
384       index_type_list,
385       detail::has_tag<Tag>
386     >::type                                    iter;
387 
388     BOOST_STATIC_CONSTANT(
389       bool,index_found=!(is_same<iter,typename mpl::end<index_type_list>::type >::value));
390     BOOST_STATIC_ASSERT(index_found);
391 
392     typedef typename mpl::deref<iter>::type    type;
393   };
394 
395   template<typename Tag>
get()396   typename index<Tag>::type& get()BOOST_NOEXCEPT
397   {
398     return *this;
399   }
400 
401   template<typename Tag>
get() const402   const typename index<Tag>::type& get()const BOOST_NOEXCEPT
403   {
404     return *this;
405   }
406 #endif
407 
408   /* projection of iterators by number */
409 
410 #if !defined(BOOST_NO_MEMBER_TEMPLATES)
411   template<int N>
412   struct nth_index_iterator
413   {
414     typedef typename nth_index<N>::type::iterator type;
415   };
416 
417   template<int N>
418   struct nth_index_const_iterator
419   {
420     typedef typename nth_index<N>::type::const_iterator type;
421   };
422 
423   template<int N,typename IteratorType>
project(IteratorType it)424   typename nth_index_iterator<N>::type project(IteratorType it)
425   {
426     typedef typename nth_index<N>::type index_type;
427 
428 #if !defined(__SUNPRO_CC)||!(__SUNPRO_CC<0x580) /* fails in Sun C++ 5.7 */
429     BOOST_STATIC_ASSERT(
430       (mpl::contains<iterator_type_list,IteratorType>::value));
431 #endif
432 
433     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it);
434     BOOST_MULTI_INDEX_CHECK_IS_OWNER(
435       it,static_cast<typename IteratorType::container_type&>(*this));
436 
437     return index_type::make_iterator(static_cast<node_type*>(it.get_node()));
438   }
439 
440   template<int N,typename IteratorType>
project(IteratorType it) const441   typename nth_index_const_iterator<N>::type project(IteratorType it)const
442   {
443     typedef typename nth_index<N>::type index_type;
444 
445 #if !defined(__SUNPRO_CC)||!(__SUNPRO_CC<0x580) /* fails in Sun C++ 5.7 */
446     BOOST_STATIC_ASSERT((
447       mpl::contains<iterator_type_list,IteratorType>::value||
448       mpl::contains<const_iterator_type_list,IteratorType>::value));
449 #endif
450 
451     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it);
452     BOOST_MULTI_INDEX_CHECK_IS_OWNER(
453       it,static_cast<const typename IteratorType::container_type&>(*this));
454     return index_type::make_iterator(static_cast<node_type*>(it.get_node()));
455   }
456 #endif
457 
458   /* projection of iterators by tag */
459 
460 #if !defined(BOOST_NO_MEMBER_TEMPLATES)
461   template<typename Tag>
462   struct index_iterator
463   {
464     typedef typename index<Tag>::type::iterator type;
465   };
466 
467   template<typename Tag>
468   struct index_const_iterator
469   {
470     typedef typename index<Tag>::type::const_iterator type;
471   };
472 
473   template<typename Tag,typename IteratorType>
project(IteratorType it)474   typename index_iterator<Tag>::type project(IteratorType it)
475   {
476     typedef typename index<Tag>::type index_type;
477 
478 #if !defined(__SUNPRO_CC)||!(__SUNPRO_CC<0x580) /* fails in Sun C++ 5.7 */
479     BOOST_STATIC_ASSERT(
480       (mpl::contains<iterator_type_list,IteratorType>::value));
481 #endif
482 
483     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it);
484     BOOST_MULTI_INDEX_CHECK_IS_OWNER(
485       it,static_cast<typename IteratorType::container_type&>(*this));
486     return index_type::make_iterator(static_cast<node_type*>(it.get_node()));
487   }
488 
489   template<typename Tag,typename IteratorType>
project(IteratorType it) const490   typename index_const_iterator<Tag>::type project(IteratorType it)const
491   {
492     typedef typename index<Tag>::type index_type;
493 
494 #if !defined(__SUNPRO_CC)||!(__SUNPRO_CC<0x580) /* fails in Sun C++ 5.7 */
495     BOOST_STATIC_ASSERT((
496       mpl::contains<iterator_type_list,IteratorType>::value||
497       mpl::contains<const_iterator_type_list,IteratorType>::value));
498 #endif
499 
500     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it);
501     BOOST_MULTI_INDEX_CHECK_IS_OWNER(
502       it,static_cast<const typename IteratorType::container_type&>(*this));
503     return index_type::make_iterator(static_cast<node_type*>(it.get_node()));
504   }
505 #endif
506 
507 BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS:
508   typedef typename super::copy_map_type copy_map_type;
509 
510 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
multi_index_container(const multi_index_container<Value,IndexSpecifierList,Allocator> & x,detail::do_not_copy_elements_tag)511   multi_index_container(
512     const multi_index_container<Value,IndexSpecifierList,Allocator>& x,
513     detail::do_not_copy_elements_tag):
514     bfm_allocator(x.bfm_allocator::member),
515     bfm_header(),
516     super(x,detail::do_not_copy_elements_tag()),
517     node_count(0)
518   {
519     BOOST_MULTI_INDEX_CHECK_INVARIANT;
520   }
521 #endif
522 
header() const523   node_type* header()const
524   {
525     return &*bfm_header::member;
526   }
527 
allocate_node()528   node_type* allocate_node()
529   {
530     return &*bfm_allocator::member.allocate(1);
531   }
532 
deallocate_node(node_type * x)533   void deallocate_node(node_type* x)
534   {
535     typedef typename node_allocator::pointer node_pointer;
536     bfm_allocator::member.deallocate(static_cast<node_pointer>(x),1);
537   }
538 
empty_() const539   bool empty_()const
540   {
541     return node_count==0;
542   }
543 
size_() const544   std::size_t size_()const
545   {
546     return node_count;
547   }
548 
max_size_() const549   std::size_t max_size_()const
550   {
551     return static_cast<std::size_t >(-1);
552   }
553 
554   template<typename Variant>
insert_(const Value & v,Variant variant)555   std::pair<node_type*,bool> insert_(const Value& v,Variant variant)
556   {
557     node_type* x=0;
558     node_type* res=super::insert_(v,x,variant);
559     if(res==x){
560       ++node_count;
561       return std::pair<node_type*,bool>(res,true);
562     }
563     else{
564       return std::pair<node_type*,bool>(res,false);
565     }
566   }
567 
insert_(const Value & v)568   std::pair<node_type*,bool> insert_(const Value& v)
569   {
570     return insert_(v,detail::lvalue_tag());
571   }
572 
insert_rv_(const Value & v)573   std::pair<node_type*,bool> insert_rv_(const Value& v)
574   {
575     return insert_(v,detail::rvalue_tag());
576   }
577 
578   template<typename T>
insert_ref_(T & t)579   std::pair<node_type*,bool> insert_ref_(T& t)
580   {
581     node_type* x=allocate_node();
582     BOOST_TRY{
583       new(&x->value()) value_type(t);
584       BOOST_TRY{
585         node_type* res=super::insert_(x->value(),x,detail::emplaced_tag());
586         if(res==x){
587           ++node_count;
588           return std::pair<node_type*,bool>(res,true);
589         }
590         else{
591           boost::detail::allocator::destroy(&x->value());
592           deallocate_node(x);
593           return std::pair<node_type*,bool>(res,false);
594         }
595       }
596       BOOST_CATCH(...){
597         boost::detail::allocator::destroy(&x->value());
598         BOOST_RETHROW;
599       }
600       BOOST_CATCH_END
601     }
602     BOOST_CATCH(...){
603       deallocate_node(x);
604       BOOST_RETHROW;
605     }
606     BOOST_CATCH_END
607   }
608 
insert_ref_(const value_type & x)609   std::pair<node_type*,bool> insert_ref_(const value_type& x)
610   {
611     return insert_(x);
612   }
613 
insert_ref_(value_type & x)614   std::pair<node_type*,bool> insert_ref_(value_type& x)
615   {
616     return insert_(x);
617   }
618 
619   template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK>
emplace_(BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK)620   std::pair<node_type*,bool> emplace_(
621     BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK)
622   {
623     node_type* x=allocate_node();
624     BOOST_TRY{
625       detail::vartempl_placement_new(
626         &x->value(),BOOST_MULTI_INDEX_FORWARD_PARAM_PACK);
627       BOOST_TRY{
628         node_type* res=super::insert_(x->value(),x,detail::emplaced_tag());
629         if(res==x){
630           ++node_count;
631           return std::pair<node_type*,bool>(res,true);
632         }
633         else{
634           boost::detail::allocator::destroy(&x->value());
635           deallocate_node(x);
636           return std::pair<node_type*,bool>(res,false);
637         }
638       }
639       BOOST_CATCH(...){
640         boost::detail::allocator::destroy(&x->value());
641         BOOST_RETHROW;
642       }
643       BOOST_CATCH_END
644     }
645     BOOST_CATCH(...){
646       deallocate_node(x);
647       BOOST_RETHROW;
648     }
649     BOOST_CATCH_END
650   }
651 
652   template<typename Variant>
insert_(const Value & v,node_type * position,Variant variant)653   std::pair<node_type*,bool> insert_(
654     const Value& v,node_type* position,Variant variant)
655   {
656     node_type* x=0;
657     node_type* res=super::insert_(v,position,x,variant);
658     if(res==x){
659       ++node_count;
660       return std::pair<node_type*,bool>(res,true);
661     }
662     else{
663       return std::pair<node_type*,bool>(res,false);
664     }
665   }
666 
insert_(const Value & v,node_type * position)667   std::pair<node_type*,bool> insert_(const Value& v,node_type* position)
668   {
669     return insert_(v,position,detail::lvalue_tag());
670   }
671 
insert_rv_(const Value & v,node_type * position)672   std::pair<node_type*,bool> insert_rv_(const Value& v,node_type* position)
673   {
674     return insert_(v,position,detail::rvalue_tag());
675   }
676 
677   template<typename T>
insert_ref_(T & t,node_type * position)678   std::pair<node_type*,bool> insert_ref_(
679     T& t,node_type* position)
680   {
681     node_type* x=allocate_node();
682     BOOST_TRY{
683       new(&x->value()) value_type(t);
684       BOOST_TRY{
685         node_type* res=super::insert_(
686           x->value(),position,x,detail::emplaced_tag());
687         if(res==x){
688           ++node_count;
689           return std::pair<node_type*,bool>(res,true);
690         }
691         else{
692           boost::detail::allocator::destroy(&x->value());
693           deallocate_node(x);
694           return std::pair<node_type*,bool>(res,false);
695         }
696       }
697       BOOST_CATCH(...){
698         boost::detail::allocator::destroy(&x->value());
699         BOOST_RETHROW;
700       }
701       BOOST_CATCH_END
702     }
703     BOOST_CATCH(...){
704       deallocate_node(x);
705       BOOST_RETHROW;
706     }
707     BOOST_CATCH_END
708   }
709 
insert_ref_(const value_type & x,node_type * position)710   std::pair<node_type*,bool> insert_ref_(
711     const value_type& x,node_type* position)
712   {
713     return insert_(x,position);
714   }
715 
insert_ref_(value_type & x,node_type * position)716   std::pair<node_type*,bool> insert_ref_(
717     value_type& x,node_type* position)
718   {
719     return insert_(x,position);
720   }
721 
722   template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK>
emplace_hint_(node_type * position,BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK)723   std::pair<node_type*,bool> emplace_hint_(
724     node_type* position,
725     BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK)
726   {
727     node_type* x=allocate_node();
728     BOOST_TRY{
729       detail::vartempl_placement_new(
730         &x->value(),BOOST_MULTI_INDEX_FORWARD_PARAM_PACK);
731       BOOST_TRY{
732         node_type* res=super::insert_(
733           x->value(),position,x,detail::emplaced_tag());
734         if(res==x){
735           ++node_count;
736           return std::pair<node_type*,bool>(res,true);
737         }
738         else{
739           boost::detail::allocator::destroy(&x->value());
740           deallocate_node(x);
741           return std::pair<node_type*,bool>(res,false);
742         }
743       }
744       BOOST_CATCH(...){
745         boost::detail::allocator::destroy(&x->value());
746         BOOST_RETHROW;
747       }
748       BOOST_CATCH_END
749     }
750     BOOST_CATCH(...){
751       deallocate_node(x);
752       BOOST_RETHROW;
753     }
754     BOOST_CATCH_END
755   }
756 
erase_(node_type * x)757   void erase_(node_type* x)
758   {
759     --node_count;
760     super::erase_(x);
761     deallocate_node(x);
762   }
763 
delete_node_(node_type * x)764   void delete_node_(node_type* x)
765   {
766     super::delete_node_(x);
767     deallocate_node(x);
768   }
769 
delete_all_nodes_()770   void delete_all_nodes_()
771   {
772     super::delete_all_nodes_();
773   }
774 
clear_()775   void clear_()
776   {
777     delete_all_nodes_();
778     super::clear_();
779     node_count=0;
780   }
781 
swap_(multi_index_container<Value,IndexSpecifierList,Allocator> & x)782   void swap_(multi_index_container<Value,IndexSpecifierList,Allocator>& x)
783   {
784     if(bfm_allocator::member!=x.bfm_allocator::member){
785       detail::adl_swap(bfm_allocator::member,x.bfm_allocator::member);
786     }
787     std::swap(bfm_header::member,x.bfm_header::member);
788     super::swap_(x);
789     std::swap(node_count,x.node_count);
790   }
791 
swap_elements_(multi_index_container<Value,IndexSpecifierList,Allocator> & x)792   void swap_elements_(
793     multi_index_container<Value,IndexSpecifierList,Allocator>& x)
794   {
795     std::swap(bfm_header::member,x.bfm_header::member);
796     super::swap_elements_(x);
797     std::swap(node_count,x.node_count);
798   }
799 
replace_(const Value & k,node_type * x)800   bool replace_(const Value& k,node_type* x)
801   {
802     return super::replace_(k,x,detail::lvalue_tag());
803   }
804 
replace_rv_(const Value & k,node_type * x)805   bool replace_rv_(const Value& k,node_type* x)
806   {
807     return super::replace_(k,x,detail::rvalue_tag());
808   }
809 
810   template<typename Modifier>
modify_(Modifier & mod,node_type * x)811   bool modify_(Modifier& mod,node_type* x)
812   {
813     BOOST_TRY{
814       mod(const_cast<value_type&>(x->value()));
815     }
816     BOOST_CATCH(...){
817       this->erase_(x);
818       BOOST_RETHROW;
819     }
820     BOOST_CATCH_END
821 
822     BOOST_TRY{
823       if(!super::modify_(x)){
824         deallocate_node(x);
825         --node_count;
826         return false;
827       }
828       else return true;
829     }
830     BOOST_CATCH(...){
831       deallocate_node(x);
832       --node_count;
833       BOOST_RETHROW;
834     }
835     BOOST_CATCH_END
836   }
837 
838   template<typename Modifier,typename Rollback>
modify_(Modifier & mod,Rollback & back_,node_type * x)839   bool modify_(Modifier& mod,Rollback& back_,node_type* x)
840   {
841     BOOST_TRY{
842       mod(const_cast<value_type&>(x->value()));
843     }
844     BOOST_CATCH(...){
845       this->erase_(x);
846       BOOST_RETHROW;
847     }
848     BOOST_CATCH_END
849 
850     bool b;
851     BOOST_TRY{
852       b=super::modify_rollback_(x);
853     }
854     BOOST_CATCH(...){
855       BOOST_TRY{
856         back_(const_cast<value_type&>(x->value()));
857         if(!super::check_rollback_(x))this->erase_(x);
858         BOOST_RETHROW;
859       }
860       BOOST_CATCH(...){
861         this->erase_(x);
862         BOOST_RETHROW;
863       }
864       BOOST_CATCH_END
865     }
866     BOOST_CATCH_END
867 
868     BOOST_TRY{
869       if(!b){
870         back_(const_cast<value_type&>(x->value()));
871         if(!super::check_rollback_(x))this->erase_(x);
872         return false;
873       }
874       else return true;
875     }
876     BOOST_CATCH(...){
877       this->erase_(x);
878       BOOST_RETHROW;
879     }
880     BOOST_CATCH_END
881   }
882 
883 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
884   /* serialization */
885 
886   friend class boost::serialization::access;
887 
888   BOOST_SERIALIZATION_SPLIT_MEMBER()
889 
890   typedef typename super::index_saver_type        index_saver_type;
891   typedef typename super::index_loader_type       index_loader_type;
892 
893   template<class Archive>
save(Archive & ar,const unsigned int version) const894   void save(Archive& ar,const unsigned int version)const
895   {
896     const serialization::collection_size_type       s(size_());
897     const detail::serialization_version<value_type> value_version;
898     ar<<serialization::make_nvp("count",s);
899     ar<<serialization::make_nvp("value_version",value_version);
900 
901     index_saver_type sm(bfm_allocator::member,s);
902 
903     for(iterator it=super::begin(),it_end=super::end();it!=it_end;++it){
904       serialization::save_construct_data_adl(ar,&*it,value_version);
905       ar<<serialization::make_nvp("item",*it);
906       sm.add(it.get_node(),ar,version);
907     }
908     sm.add_track(header(),ar,version);
909 
910     super::save_(ar,version,sm);
911   }
912 
913   template<class Archive>
load(Archive & ar,const unsigned int version)914   void load(Archive& ar,const unsigned int version)
915   {
916     BOOST_MULTI_INDEX_CHECK_INVARIANT;
917 
918     clear_();
919     serialization::collection_size_type       s;
920     detail::serialization_version<value_type> value_version;
921     if(version<1){
922       std::size_t sz;
923       ar>>serialization::make_nvp("count",sz);
924       s=static_cast<serialization::collection_size_type>(sz);
925     }
926     else{
927       ar>>serialization::make_nvp("count",s);
928     }
929     if(version<2){
930       value_version=0;
931     }
932     else{
933       ar>>serialization::make_nvp("value_version",value_version);
934     }
935 
936     index_loader_type lm(bfm_allocator::member,s);
937 
938     for(std::size_t n=0;n<s;++n){
939       detail::archive_constructed<Value> value("item",ar,value_version);
940       std::pair<node_type*,bool> p=insert_(
941         value.get(),super::end().get_node());
942       if(!p.second)throw_exception(
943         archive::archive_exception(
944           archive::archive_exception::other_exception));
945       ar.reset_object_address(&p.first->value(),&value.get());
946       lm.add(p.first,ar,version);
947     }
948     lm.add_track(header(),ar,version);
949 
950     super::load_(ar,version,lm);
951   }
952 #endif
953 
954 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
955   /* invariant stuff */
956 
invariant_() const957   bool invariant_()const
958   {
959     return super::invariant_();
960   }
961 
check_invariant_() const962   void check_invariant_()const
963   {
964     BOOST_MULTI_INDEX_INVARIANT_ASSERT(invariant_());
965   }
966 #endif
967 
968 private:
969   std::size_t node_count;
970 
971 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
972     BOOST_WORKAROUND(__MWERKS__,<=0x3003)
973 #pragma parse_mfunc_templ reset
974 #endif
975 };
976 
977 #if BOOST_WORKAROUND(BOOST_MSVC,BOOST_TESTED_AT(1500))
978 #pragma warning(pop) /* C4522 */
979 #endif
980 
981 /* retrieval of indices by number */
982 
983 template<typename MultiIndexContainer,int N>
984 struct nth_index
985 {
986   BOOST_STATIC_CONSTANT(
987     int,
988     M=mpl::size<typename MultiIndexContainer::index_type_list>::type::value);
989   BOOST_STATIC_ASSERT(N>=0&&N<M);
990   typedef typename mpl::at_c<
991     typename MultiIndexContainer::index_type_list,N>::type type;
992 };
993 
994 template<int N,typename Value,typename IndexSpecifierList,typename Allocator>
995 typename nth_index<
996   multi_index_container<Value,IndexSpecifierList,Allocator>,N>::type&
get(multi_index_container<Value,IndexSpecifierList,Allocator> & m)997 get(
998   multi_index_container<Value,IndexSpecifierList,Allocator>& m)BOOST_NOEXCEPT
999 {
1000   typedef multi_index_container<
1001     Value,IndexSpecifierList,Allocator>    multi_index_type;
1002   typedef typename nth_index<
1003     multi_index_container<
1004       Value,IndexSpecifierList,Allocator>,
1005     N
1006   >::type                                  index_type;
1007 
1008   BOOST_STATIC_ASSERT(N>=0&&
1009     N<
1010     mpl::size<
1011       BOOST_DEDUCED_TYPENAME multi_index_type::index_type_list
1012     >::type::value);
1013 
1014   return detail::converter<multi_index_type,index_type>::index(m);
1015 }
1016 
1017 template<int N,typename Value,typename IndexSpecifierList,typename Allocator>
1018 const typename nth_index<
1019   multi_index_container<Value,IndexSpecifierList,Allocator>,N>::type&
get(const multi_index_container<Value,IndexSpecifierList,Allocator> & m)1020 get(
1021   const multi_index_container<Value,IndexSpecifierList,Allocator>& m
1022 )BOOST_NOEXCEPT
1023 {
1024   typedef multi_index_container<
1025     Value,IndexSpecifierList,Allocator>    multi_index_type;
1026   typedef typename nth_index<
1027     multi_index_container<
1028       Value,IndexSpecifierList,Allocator>,
1029     N
1030   >::type                                  index_type;
1031 
1032   BOOST_STATIC_ASSERT(N>=0&&
1033     N<
1034     mpl::size<
1035       BOOST_DEDUCED_TYPENAME multi_index_type::index_type_list
1036     >::type::value);
1037 
1038   return detail::converter<multi_index_type,index_type>::index(m);
1039 }
1040 
1041 /* retrieval of indices by tag */
1042 
1043 template<typename MultiIndexContainer,typename Tag>
1044 struct index
1045 {
1046   typedef typename MultiIndexContainer::index_type_list index_type_list;
1047 
1048   typedef typename mpl::find_if<
1049     index_type_list,
1050     detail::has_tag<Tag>
1051   >::type                                      iter;
1052 
1053   BOOST_STATIC_CONSTANT(
1054     bool,index_found=!(is_same<iter,typename mpl::end<index_type_list>::type >::value));
1055   BOOST_STATIC_ASSERT(index_found);
1056 
1057   typedef typename mpl::deref<iter>::type       type;
1058 };
1059 
1060 template<
1061   typename Tag,typename Value,typename IndexSpecifierList,typename Allocator
1062 >
1063 typename ::boost::multi_index::index<
1064   multi_index_container<Value,IndexSpecifierList,Allocator>,Tag>::type&
get(multi_index_container<Value,IndexSpecifierList,Allocator> & m)1065 get(
1066   multi_index_container<Value,IndexSpecifierList,Allocator>& m)BOOST_NOEXCEPT
1067 {
1068   typedef multi_index_container<
1069     Value,IndexSpecifierList,Allocator>         multi_index_type;
1070   typedef typename ::boost::multi_index::index<
1071     multi_index_container<
1072       Value,IndexSpecifierList,Allocator>,
1073     Tag
1074   >::type                                       index_type;
1075 
1076   return detail::converter<multi_index_type,index_type>::index(m);
1077 }
1078 
1079 template<
1080   typename Tag,typename Value,typename IndexSpecifierList,typename Allocator
1081 >
1082 const typename ::boost::multi_index::index<
1083   multi_index_container<Value,IndexSpecifierList,Allocator>,Tag>::type&
get(const multi_index_container<Value,IndexSpecifierList,Allocator> & m)1084 get(
1085   const multi_index_container<Value,IndexSpecifierList,Allocator>& m
1086 )BOOST_NOEXCEPT
1087 {
1088   typedef multi_index_container<
1089     Value,IndexSpecifierList,Allocator>         multi_index_type;
1090   typedef typename ::boost::multi_index::index<
1091     multi_index_container<
1092       Value,IndexSpecifierList,Allocator>,
1093     Tag
1094   >::type                                       index_type;
1095 
1096   return detail::converter<multi_index_type,index_type>::index(m);
1097 }
1098 
1099 /* projection of iterators by number */
1100 
1101 template<typename MultiIndexContainer,int N>
1102 struct nth_index_iterator
1103 {
1104   typedef typename nth_index<MultiIndexContainer,N>::type::iterator type;
1105 };
1106 
1107 template<typename MultiIndexContainer,int N>
1108 struct nth_index_const_iterator
1109 {
1110   typedef typename nth_index<MultiIndexContainer,N>::type::const_iterator type;
1111 };
1112 
1113 template<
1114   int N,typename IteratorType,
1115   typename Value,typename IndexSpecifierList,typename Allocator>
1116 typename nth_index_iterator<
1117   multi_index_container<Value,IndexSpecifierList,Allocator>,N>::type
project(multi_index_container<Value,IndexSpecifierList,Allocator> & m,IteratorType it)1118 project(
1119   multi_index_container<Value,IndexSpecifierList,Allocator>& m,
1120   IteratorType it)
1121 {
1122   typedef multi_index_container<
1123     Value,IndexSpecifierList,Allocator>                multi_index_type;
1124   typedef typename nth_index<multi_index_type,N>::type index_type;
1125 
1126 #if !defined(__SUNPRO_CC)||!(__SUNPRO_CC<0x580) /* Sun C++ 5.7 fails */
1127   BOOST_STATIC_ASSERT((
1128     mpl::contains<
1129       BOOST_DEDUCED_TYPENAME multi_index_type::iterator_type_list,
1130       IteratorType>::value));
1131 #endif
1132 
1133   BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it);
1134 
1135 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1136   typedef detail::converter<
1137     multi_index_type,
1138     BOOST_DEDUCED_TYPENAME IteratorType::container_type> converter;
1139   BOOST_MULTI_INDEX_CHECK_IS_OWNER(it,converter::index(m));
1140 #endif
1141 
1142   return detail::converter<multi_index_type,index_type>::iterator(
1143     m,static_cast<typename multi_index_type::node_type*>(it.get_node()));
1144 }
1145 
1146 template<
1147   int N,typename IteratorType,
1148   typename Value,typename IndexSpecifierList,typename Allocator>
1149 typename nth_index_const_iterator<
1150   multi_index_container<Value,IndexSpecifierList,Allocator>,N>::type
project(const multi_index_container<Value,IndexSpecifierList,Allocator> & m,IteratorType it)1151 project(
1152   const multi_index_container<Value,IndexSpecifierList,Allocator>& m,
1153   IteratorType it)
1154 {
1155   typedef multi_index_container<
1156     Value,IndexSpecifierList,Allocator>                multi_index_type;
1157   typedef typename nth_index<multi_index_type,N>::type index_type;
1158 
1159 #if !defined(__SUNPRO_CC)||!(__SUNPRO_CC<0x580) /* Sun C++ 5.7 fails */
1160   BOOST_STATIC_ASSERT((
1161     mpl::contains<
1162       BOOST_DEDUCED_TYPENAME multi_index_type::iterator_type_list,
1163       IteratorType>::value||
1164     mpl::contains<
1165       BOOST_DEDUCED_TYPENAME multi_index_type::const_iterator_type_list,
1166       IteratorType>::value));
1167 #endif
1168 
1169   BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it);
1170 
1171 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1172   typedef detail::converter<
1173     multi_index_type,
1174     BOOST_DEDUCED_TYPENAME IteratorType::container_type> converter;
1175   BOOST_MULTI_INDEX_CHECK_IS_OWNER(it,converter::index(m));
1176 #endif
1177 
1178   return detail::converter<multi_index_type,index_type>::const_iterator(
1179     m,static_cast<typename multi_index_type::node_type*>(it.get_node()));
1180 }
1181 
1182 /* projection of iterators by tag */
1183 
1184 template<typename MultiIndexContainer,typename Tag>
1185 struct index_iterator
1186 {
1187   typedef typename ::boost::multi_index::index<
1188     MultiIndexContainer,Tag>::type::iterator    type;
1189 };
1190 
1191 template<typename MultiIndexContainer,typename Tag>
1192 struct index_const_iterator
1193 {
1194   typedef typename ::boost::multi_index::index<
1195     MultiIndexContainer,Tag>::type::const_iterator type;
1196 };
1197 
1198 template<
1199   typename Tag,typename IteratorType,
1200   typename Value,typename IndexSpecifierList,typename Allocator>
1201 typename index_iterator<
1202   multi_index_container<Value,IndexSpecifierList,Allocator>,Tag>::type
project(multi_index_container<Value,IndexSpecifierList,Allocator> & m,IteratorType it)1203 project(
1204   multi_index_container<Value,IndexSpecifierList,Allocator>& m,
1205   IteratorType it)
1206 {
1207   typedef multi_index_container<
1208     Value,IndexSpecifierList,Allocator>         multi_index_type;
1209   typedef typename ::boost::multi_index::index<
1210     multi_index_type,Tag>::type                 index_type;
1211 
1212 #if !defined(__SUNPRO_CC)||!(__SUNPRO_CC<0x580) /* Sun C++ 5.7 fails */
1213   BOOST_STATIC_ASSERT((
1214     mpl::contains<
1215       BOOST_DEDUCED_TYPENAME multi_index_type::iterator_type_list,
1216       IteratorType>::value));
1217 #endif
1218 
1219   BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it);
1220 
1221 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1222   typedef detail::converter<
1223     multi_index_type,
1224     BOOST_DEDUCED_TYPENAME IteratorType::container_type> converter;
1225   BOOST_MULTI_INDEX_CHECK_IS_OWNER(it,converter::index(m));
1226 #endif
1227 
1228   return detail::converter<multi_index_type,index_type>::iterator(
1229     m,static_cast<typename multi_index_type::node_type*>(it.get_node()));
1230 }
1231 
1232 template<
1233   typename Tag,typename IteratorType,
1234   typename Value,typename IndexSpecifierList,typename Allocator>
1235 typename index_const_iterator<
1236   multi_index_container<Value,IndexSpecifierList,Allocator>,Tag>::type
project(const multi_index_container<Value,IndexSpecifierList,Allocator> & m,IteratorType it)1237 project(
1238   const multi_index_container<Value,IndexSpecifierList,Allocator>& m,
1239   IteratorType it)
1240 {
1241   typedef multi_index_container<
1242     Value,IndexSpecifierList,Allocator>         multi_index_type;
1243   typedef typename ::boost::multi_index::index<
1244     multi_index_type,Tag>::type                 index_type;
1245 
1246 #if !defined(__SUNPRO_CC)||!(__SUNPRO_CC<0x580) /* Sun C++ 5.7 fails */
1247   BOOST_STATIC_ASSERT((
1248     mpl::contains<
1249       BOOST_DEDUCED_TYPENAME multi_index_type::iterator_type_list,
1250       IteratorType>::value||
1251     mpl::contains<
1252       BOOST_DEDUCED_TYPENAME multi_index_type::const_iterator_type_list,
1253       IteratorType>::value));
1254 #endif
1255 
1256   BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it);
1257 
1258 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1259   typedef detail::converter<
1260     multi_index_type,
1261     BOOST_DEDUCED_TYPENAME IteratorType::container_type> converter;
1262   BOOST_MULTI_INDEX_CHECK_IS_OWNER(it,converter::index(m));
1263 #endif
1264 
1265   return detail::converter<multi_index_type,index_type>::const_iterator(
1266     m,static_cast<typename multi_index_type::node_type*>(it.get_node()));
1267 }
1268 
1269 /* Comparison. Simple forward to first index. */
1270 
1271 template<
1272   typename Value1,typename IndexSpecifierList1,typename Allocator1,
1273   typename Value2,typename IndexSpecifierList2,typename Allocator2
1274 >
operator ==(const multi_index_container<Value1,IndexSpecifierList1,Allocator1> & x,const multi_index_container<Value2,IndexSpecifierList2,Allocator2> & y)1275 bool operator==(
1276   const multi_index_container<Value1,IndexSpecifierList1,Allocator1>& x,
1277   const multi_index_container<Value2,IndexSpecifierList2,Allocator2>& y)
1278 {
1279   return get<0>(x)==get<0>(y);
1280 }
1281 
1282 template<
1283   typename Value1,typename IndexSpecifierList1,typename Allocator1,
1284   typename Value2,typename IndexSpecifierList2,typename Allocator2
1285 >
operator <(const multi_index_container<Value1,IndexSpecifierList1,Allocator1> & x,const multi_index_container<Value2,IndexSpecifierList2,Allocator2> & y)1286 bool operator<(
1287   const multi_index_container<Value1,IndexSpecifierList1,Allocator1>& x,
1288   const multi_index_container<Value2,IndexSpecifierList2,Allocator2>& y)
1289 {
1290   return get<0>(x)<get<0>(y);
1291 }
1292 
1293 template<
1294   typename Value1,typename IndexSpecifierList1,typename Allocator1,
1295   typename Value2,typename IndexSpecifierList2,typename Allocator2
1296 >
operator !=(const multi_index_container<Value1,IndexSpecifierList1,Allocator1> & x,const multi_index_container<Value2,IndexSpecifierList2,Allocator2> & y)1297 bool operator!=(
1298   const multi_index_container<Value1,IndexSpecifierList1,Allocator1>& x,
1299   const multi_index_container<Value2,IndexSpecifierList2,Allocator2>& y)
1300 {
1301   return get<0>(x)!=get<0>(y);
1302 }
1303 
1304 template<
1305   typename Value1,typename IndexSpecifierList1,typename Allocator1,
1306   typename Value2,typename IndexSpecifierList2,typename Allocator2
1307 >
operator >(const multi_index_container<Value1,IndexSpecifierList1,Allocator1> & x,const multi_index_container<Value2,IndexSpecifierList2,Allocator2> & y)1308 bool operator>(
1309   const multi_index_container<Value1,IndexSpecifierList1,Allocator1>& x,
1310   const multi_index_container<Value2,IndexSpecifierList2,Allocator2>& y)
1311 {
1312   return get<0>(x)>get<0>(y);
1313 }
1314 
1315 template<
1316   typename Value1,typename IndexSpecifierList1,typename Allocator1,
1317   typename Value2,typename IndexSpecifierList2,typename Allocator2
1318 >
operator >=(const multi_index_container<Value1,IndexSpecifierList1,Allocator1> & x,const multi_index_container<Value2,IndexSpecifierList2,Allocator2> & y)1319 bool operator>=(
1320   const multi_index_container<Value1,IndexSpecifierList1,Allocator1>& x,
1321   const multi_index_container<Value2,IndexSpecifierList2,Allocator2>& y)
1322 {
1323   return get<0>(x)>=get<0>(y);
1324 }
1325 
1326 template<
1327   typename Value1,typename IndexSpecifierList1,typename Allocator1,
1328   typename Value2,typename IndexSpecifierList2,typename Allocator2
1329 >
operator <=(const multi_index_container<Value1,IndexSpecifierList1,Allocator1> & x,const multi_index_container<Value2,IndexSpecifierList2,Allocator2> & y)1330 bool operator<=(
1331   const multi_index_container<Value1,IndexSpecifierList1,Allocator1>& x,
1332   const multi_index_container<Value2,IndexSpecifierList2,Allocator2>& y)
1333 {
1334   return get<0>(x)<=get<0>(y);
1335 }
1336 
1337 /*  specialized algorithms */
1338 
1339 template<typename Value,typename IndexSpecifierList,typename Allocator>
swap(multi_index_container<Value,IndexSpecifierList,Allocator> & x,multi_index_container<Value,IndexSpecifierList,Allocator> & y)1340 void swap(
1341   multi_index_container<Value,IndexSpecifierList,Allocator>& x,
1342   multi_index_container<Value,IndexSpecifierList,Allocator>& y)
1343 {
1344   x.swap(y);
1345 }
1346 
1347 } /* namespace multi_index */
1348 
1349 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
1350 /* class version = 1 : we now serialize the size through
1351  * boost::serialization::collection_size_type.
1352  * class version = 2 : proper use of {save|load}_construct_data.
1353  */
1354 
1355 namespace serialization {
1356 template<typename Value,typename IndexSpecifierList,typename Allocator>
1357 struct version<
1358   boost::multi_index_container<Value,IndexSpecifierList,Allocator>
1359 >
1360 {
1361   BOOST_STATIC_CONSTANT(int,value=2);
1362 };
1363 } /* namespace serialization */
1364 #endif
1365 
1366 /* Associated global functions are promoted to namespace boost, except
1367  * comparison operators and swap, which are meant to be Koenig looked-up.
1368  */
1369 
1370 using multi_index::get;
1371 using multi_index::project;
1372 
1373 } /* namespace boost */
1374 
1375 #undef BOOST_MULTI_INDEX_CHECK_INVARIANT
1376 #undef BOOST_MULTI_INDEX_CHECK_INVARIANT_OF
1377 
1378 #endif
1379