ceph/src/boost/boost/multi_index_container.hpp

   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
 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
 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>
 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)
 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
 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
 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
 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
 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
 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
 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)
 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
 347   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>
 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>
 370   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>
 396   typename index<Tag>::type& get()BOOST_NOEXCEPT
 397   {
 398     return *this;
 399   }
 400
 401   template<typename Tag>
 402   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>
 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>
 441   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>
 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>
 490   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)
 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
 523   node_type* header()const
 524   {
 525     return &*bfm_header::member;
 526   }
 527
 528   node_type* allocate_node()
 529   {
 530     return &*bfm_allocator::member.allocate(1);
 531   }
 532
 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
 539   bool empty_()const
 540   {
 541     return node_count==0;
 542   }
 543
 544   std::size_t size_()const
 545   {
 546     return node_count;
 547   }
 548
 549   std::size_t max_size_()const
 550   {
 551     return static_cast<std::size_t >(-1);
 552   }
 553
 554   template<typename 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
 568   std::pair<node_type*,bool> insert_(const Value& v)
 569   {
 570     return insert_(v,detail::lvalue_tag());
 571   }
 572
 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>
 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
 609   std::pair<node_type*,bool> insert_ref_(const value_type& x)
 610   {
 611     return insert_(x);
 612   }
 613
 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>
 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>
 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
 667   std::pair<node_type*,bool> insert_(const Value& v,node_type* position)
 668   {
 669     return insert_(v,position,detail::lvalue_tag());
 670   }
 671
 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>
 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
 710   std::pair<node_type*,bool> insert_ref_(
 711     const value_type& x,node_type* position)
 712   {
 713     return insert_(x,position);
 714   }
 715
 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>
 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
 757   void erase_(node_type* x)
 758   {
 759     --node_count;
 760     super::erase_(x);
 761     deallocate_node(x);
 762   }
 763
 764   void delete_node_(node_type* x)
 765   {
 766     super::delete_node_(x);
 767     deallocate_node(x);
 768   }
 769
 770   void delete_all_nodes_()
 771   {
 772     super::delete_all_nodes_();
 773   }
 774
 775   void clear_()
 776   {
 777     delete_all_nodes_();
 778     super::clear_();
 779     node_count=0;
 780   }
 781
 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
 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
 800   bool replace_(const Value& k,node_type* x)
 801   {
 802     return super::replace_(k,x,detail::lvalue_tag());
 803   }
 804
 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>
 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>
 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>
 894   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>
 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
 957   bool invariant_()const
 958   {
 959     return super::invariant_();
 960   }
 961
 962   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&
 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&
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&
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&
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
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
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
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
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 >
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 >
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 >
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 >
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 >
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 >
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>
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