boost/multi_index_container.hpp

   1 /* Multiply indexed container.
   2  *
   3  * Copyright 2003-2014 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     mod(const_cast<value_type&>(x->value()));
 814
 815     BOOST_TRY{
 816       if(!super::modify_(x)){
 817         deallocate_node(x);
 818         --node_count;
 819         return false;
 820       }
 821       else return true;
 822     }
 823     BOOST_CATCH(...){
 824       deallocate_node(x);
 825       --node_count;
 826       BOOST_RETHROW;
 827     }
 828     BOOST_CATCH_END
 829   }
 830
 831   template<typename Modifier,typename Rollback>
 832   bool modify_(Modifier& mod,Rollback& back_,node_type* x)
 833   {
 834     mod(const_cast<value_type&>(x->value()));
 835
 836     bool b;
 837     BOOST_TRY{
 838       b=super::modify_rollback_(x);
 839     }
 840     BOOST_CATCH(...){
 841       BOOST_TRY{
 842         back_(const_cast<value_type&>(x->value()));
 843         BOOST_RETHROW;
 844       }
 845       BOOST_CATCH(...){
 846         this->erase_(x);
 847         BOOST_RETHROW;
 848       }
 849       BOOST_CATCH_END
 850     }
 851     BOOST_CATCH_END
 852
 853     BOOST_TRY{
 854       if(!b){
 855         back_(const_cast<value_type&>(x->value()));
 856         return false;
 857       }
 858       else return true;
 859     }
 860     BOOST_CATCH(...){
 861       this->erase_(x);
 862       BOOST_RETHROW;
 863     }
 864     BOOST_CATCH_END
 865   }
 866
 867 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
 868   /* serialization */
 869
 870   friend class boost::serialization::access;
 871
 872   BOOST_SERIALIZATION_SPLIT_MEMBER()
 873
 874   typedef typename super::index_saver_type        index_saver_type;
 875   typedef typename super::index_loader_type       index_loader_type;
 876
 877   template<class Archive>
 878   void save(Archive& ar,const unsigned int version)const
 879   {
 880     const serialization::collection_size_type       s(size_());
 881     const detail::serialization_version<value_type> value_version;
 882     ar<<serialization::make_nvp("count",s);
 883     ar<<serialization::make_nvp("value_version",value_version);
 884
 885     index_saver_type sm(bfm_allocator::member,s);
 886
 887     for(iterator it=super::begin(),it_end=super::end();it!=it_end;++it){
 888       serialization::save_construct_data_adl(ar,&*it,value_version);
 889       ar<<serialization::make_nvp("item",*it);
 890       sm.add(it.get_node(),ar,version);
 891     }
 892     sm.add_track(header(),ar,version);
 893
 894     super::save_(ar,version,sm);
 895   }
 896
 897   template<class Archive>
 898   void load(Archive& ar,const unsigned int version)
 899   {
 900     BOOST_MULTI_INDEX_CHECK_INVARIANT;
 901
 902     clear_();
 903     serialization::collection_size_type       s;
 904     detail::serialization_version<value_type> value_version;
 905     if(version<1){
 906       std::size_t sz;
 907       ar>>serialization::make_nvp("count",sz);
 908       s=static_cast<serialization::collection_size_type>(sz);
 909     }
 910     else{
 911       ar>>serialization::make_nvp("count",s);
 912     }
 913     if(version<2){
 914       value_version=0;
 915     }
 916     else{
 917       ar>>serialization::make_nvp("value_version",value_version);
 918     }
 919
 920     index_loader_type lm(bfm_allocator::member,s);
 921
 922     for(std::size_t n=0;n<s;++n){
 923       detail::archive_constructed<Value> value("item",ar,value_version);
 924       std::pair<node_type*,bool> p=insert_(
 925         value.get(),super::end().get_node());
 926       if(!p.second)throw_exception(
 927         archive::archive_exception(
 928           archive::archive_exception::other_exception));
 929       ar.reset_object_address(&p.first->value(),&value.get());
 930       lm.add(p.first,ar,version);
 931     }
 932     lm.add_track(header(),ar,version);
 933
 934     super::load_(ar,version,lm);
 935   }
 936 #endif
 937
 938 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
 939   /* invariant stuff */
 940
 941   bool invariant_()const
 942   {
 943     return super::invariant_();
 944   }
 945
 946   void check_invariant_()const
 947   {
 948     BOOST_MULTI_INDEX_INVARIANT_ASSERT(invariant_());
 949   }
 950 #endif
 951
 952 private:
 953   std::size_t node_count;
 954
 955 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
 956     BOOST_WORKAROUND(__MWERKS__,<=0x3003)
 957 #pragma parse_mfunc_templ reset
 958 #endif
 959 };
 960
 961 #if BOOST_WORKAROUND(BOOST_MSVC,BOOST_TESTED_AT(1500))
 962 #pragma warning(pop) /* C4522 */
 963 #endif
 964
 965 /* retrieval of indices by number */
 966
 967 template<typename MultiIndexContainer,int N>
 968 struct nth_index
 969 {
 970   BOOST_STATIC_CONSTANT(
 971     int,
 972     M=mpl::size<typename MultiIndexContainer::index_type_list>::type::value);
 973   BOOST_STATIC_ASSERT(N>=0&&N<M);
 974   typedef typename mpl::at_c<
 975     typename MultiIndexContainer::index_type_list,N>::type type;
 976 };
 977
 978 template<int N,typename Value,typename IndexSpecifierList,typename Allocator>
 979 typename nth_index<
 980   multi_index_container<Value,IndexSpecifierList,Allocator>,N>::type&
 981 get(
 982   multi_index_container<Value,IndexSpecifierList,Allocator>& m)BOOST_NOEXCEPT
 983 {
 984   typedef multi_index_container<
 985     Value,IndexSpecifierList,Allocator>    multi_index_type;
 986   typedef typename nth_index<
 987     multi_index_container<
 988       Value,IndexSpecifierList,Allocator>,
 989     N
 990   >::type                                  index_type;
 991
 992   BOOST_STATIC_ASSERT(N>=0&&
 993     N<
 994     mpl::size<
 995       BOOST_DEDUCED_TYPENAME multi_index_type::index_type_list
 996     >::type::value);
 997
 998   return detail::converter<multi_index_type,index_type>::index(m);
 999 }
1000
1001 template<int N,typename Value,typename IndexSpecifierList,typename Allocator>
1002 const typename nth_index<
1003   multi_index_container<Value,IndexSpecifierList,Allocator>,N>::type&
1004 get(
1005   const multi_index_container<Value,IndexSpecifierList,Allocator>& m
1006 )BOOST_NOEXCEPT
1007 {
1008   typedef multi_index_container<
1009     Value,IndexSpecifierList,Allocator>    multi_index_type;
1010   typedef typename nth_index<
1011     multi_index_container<
1012       Value,IndexSpecifierList,Allocator>,
1013     N
1014   >::type                                  index_type;
1015
1016   BOOST_STATIC_ASSERT(N>=0&&
1017     N<
1018     mpl::size<
1019       BOOST_DEDUCED_TYPENAME multi_index_type::index_type_list
1020     >::type::value);
1021
1022   return detail::converter<multi_index_type,index_type>::index(m);
1023 }
1024
1025 /* retrieval of indices by tag */
1026
1027 template<typename MultiIndexContainer,typename Tag>
1028 struct index
1029 {
1030   typedef typename MultiIndexContainer::index_type_list index_type_list;
1031
1032   typedef typename mpl::find_if<
1033     index_type_list,
1034     detail::has_tag<Tag>
1035   >::type                                      iter;
1036
1037   BOOST_STATIC_CONSTANT(
1038     bool,index_found=!(is_same<iter,typename mpl::end<index_type_list>::type >::value));
1039   BOOST_STATIC_ASSERT(index_found);
1040
1041   typedef typename mpl::deref<iter>::type       type;
1042 };
1043
1044 template<
1045   typename Tag,typename Value,typename IndexSpecifierList,typename Allocator
1046 >
1047 typename ::boost::multi_index::index<
1048   multi_index_container<Value,IndexSpecifierList,Allocator>,Tag>::type&
1049 get(
1050   multi_index_container<Value,IndexSpecifierList,Allocator>& m)BOOST_NOEXCEPT
1051 {
1052   typedef multi_index_container<
1053     Value,IndexSpecifierList,Allocator>         multi_index_type;
1054   typedef typename ::boost::multi_index::index<
1055     multi_index_container<
1056       Value,IndexSpecifierList,Allocator>,
1057     Tag
1058   >::type                                       index_type;
1059
1060   return detail::converter<multi_index_type,index_type>::index(m);
1061 }
1062
1063 template<
1064   typename Tag,typename Value,typename IndexSpecifierList,typename Allocator
1065 >
1066 const typename ::boost::multi_index::index<
1067   multi_index_container<Value,IndexSpecifierList,Allocator>,Tag>::type&
1068 get(
1069   const multi_index_container<Value,IndexSpecifierList,Allocator>& m
1070 )BOOST_NOEXCEPT
1071 {
1072   typedef multi_index_container<
1073     Value,IndexSpecifierList,Allocator>         multi_index_type;
1074   typedef typename ::boost::multi_index::index<
1075     multi_index_container<
1076       Value,IndexSpecifierList,Allocator>,
1077     Tag
1078   >::type                                       index_type;
1079
1080   return detail::converter<multi_index_type,index_type>::index(m);
1081 }
1082
1083 /* projection of iterators by number */
1084
1085 template<typename MultiIndexContainer,int N>
1086 struct nth_index_iterator
1087 {
1088   typedef typename nth_index<MultiIndexContainer,N>::type::iterator type;
1089 };
1090
1091 template<typename MultiIndexContainer,int N>
1092 struct nth_index_const_iterator
1093 {
1094   typedef typename nth_index<MultiIndexContainer,N>::type::const_iterator type;
1095 };
1096
1097 template<
1098   int N,typename IteratorType,
1099   typename Value,typename IndexSpecifierList,typename Allocator>
1100 typename nth_index_iterator<
1101   multi_index_container<Value,IndexSpecifierList,Allocator>,N>::type
1102 project(
1103   multi_index_container<Value,IndexSpecifierList,Allocator>& m,
1104   IteratorType it)
1105 {
1106   typedef multi_index_container<
1107     Value,IndexSpecifierList,Allocator>                multi_index_type;
1108   typedef typename nth_index<multi_index_type,N>::type index_type;
1109
1110 #if !defined(__SUNPRO_CC)||!(__SUNPRO_CC<0x580) /* Sun C++ 5.7 fails */
1111   BOOST_STATIC_ASSERT((
1112     mpl::contains<
1113       BOOST_DEDUCED_TYPENAME multi_index_type::iterator_type_list,
1114       IteratorType>::value));
1115 #endif
1116
1117   BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it);
1118
1119 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1120   typedef detail::converter<
1121     multi_index_type,
1122     BOOST_DEDUCED_TYPENAME IteratorType::container_type> converter;
1123   BOOST_MULTI_INDEX_CHECK_IS_OWNER(it,converter::index(m));
1124 #endif
1125
1126   return detail::converter<multi_index_type,index_type>::iterator(
1127     m,static_cast<typename multi_index_type::node_type*>(it.get_node()));
1128 }
1129
1130 template<
1131   int N,typename IteratorType,
1132   typename Value,typename IndexSpecifierList,typename Allocator>
1133 typename nth_index_const_iterator<
1134   multi_index_container<Value,IndexSpecifierList,Allocator>,N>::type
1135 project(
1136   const multi_index_container<Value,IndexSpecifierList,Allocator>& m,
1137   IteratorType it)
1138 {
1139   typedef multi_index_container<
1140     Value,IndexSpecifierList,Allocator>                multi_index_type;
1141   typedef typename nth_index<multi_index_type,N>::type index_type;
1142
1143 #if !defined(__SUNPRO_CC)||!(__SUNPRO_CC<0x580) /* Sun C++ 5.7 fails */
1144   BOOST_STATIC_ASSERT((
1145     mpl::contains<
1146       BOOST_DEDUCED_TYPENAME multi_index_type::iterator_type_list,
1147       IteratorType>::value||
1148     mpl::contains<
1149       BOOST_DEDUCED_TYPENAME multi_index_type::const_iterator_type_list,
1150       IteratorType>::value));
1151 #endif
1152
1153   BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it);
1154
1155 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1156   typedef detail::converter<
1157     multi_index_type,
1158     BOOST_DEDUCED_TYPENAME IteratorType::container_type> converter;
1159   BOOST_MULTI_INDEX_CHECK_IS_OWNER(it,converter::index(m));
1160 #endif
1161
1162   return detail::converter<multi_index_type,index_type>::const_iterator(
1163     m,static_cast<typename multi_index_type::node_type*>(it.get_node()));
1164 }
1165
1166 /* projection of iterators by tag */
1167
1168 template<typename MultiIndexContainer,typename Tag>
1169 struct index_iterator
1170 {
1171   typedef typename ::boost::multi_index::index<
1172     MultiIndexContainer,Tag>::type::iterator    type;
1173 };
1174
1175 template<typename MultiIndexContainer,typename Tag>
1176 struct index_const_iterator
1177 {
1178   typedef typename ::boost::multi_index::index<
1179     MultiIndexContainer,Tag>::type::const_iterator type;
1180 };
1181
1182 template<
1183   typename Tag,typename IteratorType,
1184   typename Value,typename IndexSpecifierList,typename Allocator>
1185 typename index_iterator<
1186   multi_index_container<Value,IndexSpecifierList,Allocator>,Tag>::type
1187 project(
1188   multi_index_container<Value,IndexSpecifierList,Allocator>& m,
1189   IteratorType it)
1190 {
1191   typedef multi_index_container<
1192     Value,IndexSpecifierList,Allocator>         multi_index_type;
1193   typedef typename ::boost::multi_index::index<
1194     multi_index_type,Tag>::type                 index_type;
1195
1196 #if !defined(__SUNPRO_CC)||!(__SUNPRO_CC<0x580) /* Sun C++ 5.7 fails */
1197   BOOST_STATIC_ASSERT((
1198     mpl::contains<
1199       BOOST_DEDUCED_TYPENAME multi_index_type::iterator_type_list,
1200       IteratorType>::value));
1201 #endif
1202
1203   BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it);
1204
1205 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1206   typedef detail::converter<
1207     multi_index_type,
1208     BOOST_DEDUCED_TYPENAME IteratorType::container_type> converter;
1209   BOOST_MULTI_INDEX_CHECK_IS_OWNER(it,converter::index(m));
1210 #endif
1211
1212   return detail::converter<multi_index_type,index_type>::iterator(
1213     m,static_cast<typename multi_index_type::node_type*>(it.get_node()));
1214 }
1215
1216 template<
1217   typename Tag,typename IteratorType,
1218   typename Value,typename IndexSpecifierList,typename Allocator>
1219 typename index_const_iterator<
1220   multi_index_container<Value,IndexSpecifierList,Allocator>,Tag>::type
1221 project(
1222   const multi_index_container<Value,IndexSpecifierList,Allocator>& m,
1223   IteratorType it)
1224 {
1225   typedef multi_index_container<
1226     Value,IndexSpecifierList,Allocator>         multi_index_type;
1227   typedef typename ::boost::multi_index::index<
1228     multi_index_type,Tag>::type                 index_type;
1229
1230 #if !defined(__SUNPRO_CC)||!(__SUNPRO_CC<0x580) /* Sun C++ 5.7 fails */
1231   BOOST_STATIC_ASSERT((
1232     mpl::contains<
1233       BOOST_DEDUCED_TYPENAME multi_index_type::iterator_type_list,
1234       IteratorType>::value||
1235     mpl::contains<
1236       BOOST_DEDUCED_TYPENAME multi_index_type::const_iterator_type_list,
1237       IteratorType>::value));
1238 #endif
1239
1240   BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it);
1241
1242 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1243   typedef detail::converter<
1244     multi_index_type,
1245     BOOST_DEDUCED_TYPENAME IteratorType::container_type> converter;
1246   BOOST_MULTI_INDEX_CHECK_IS_OWNER(it,converter::index(m));
1247 #endif
1248
1249   return detail::converter<multi_index_type,index_type>::const_iterator(
1250     m,static_cast<typename multi_index_type::node_type*>(it.get_node()));
1251 }
1252
1253 /* Comparison. Simple forward to first index. */
1254
1255 template<
1256   typename Value1,typename IndexSpecifierList1,typename Allocator1,
1257   typename Value2,typename IndexSpecifierList2,typename Allocator2
1258 >
1259 bool operator==(
1260   const multi_index_container<Value1,IndexSpecifierList1,Allocator1>& x,
1261   const multi_index_container<Value2,IndexSpecifierList2,Allocator2>& y)
1262 {
1263   return get<0>(x)==get<0>(y);
1264 }
1265
1266 template<
1267   typename Value1,typename IndexSpecifierList1,typename Allocator1,
1268   typename Value2,typename IndexSpecifierList2,typename Allocator2
1269 >
1270 bool operator<(
1271   const multi_index_container<Value1,IndexSpecifierList1,Allocator1>& x,
1272   const multi_index_container<Value2,IndexSpecifierList2,Allocator2>& y)
1273 {
1274   return get<0>(x)<get<0>(y);
1275 }
1276
1277 template<
1278   typename Value1,typename IndexSpecifierList1,typename Allocator1,
1279   typename Value2,typename IndexSpecifierList2,typename Allocator2
1280 >
1281 bool operator!=(
1282   const multi_index_container<Value1,IndexSpecifierList1,Allocator1>& x,
1283   const multi_index_container<Value2,IndexSpecifierList2,Allocator2>& y)
1284 {
1285   return get<0>(x)!=get<0>(y);
1286 }
1287
1288 template<
1289   typename Value1,typename IndexSpecifierList1,typename Allocator1,
1290   typename Value2,typename IndexSpecifierList2,typename Allocator2
1291 >
1292 bool operator>(
1293   const multi_index_container<Value1,IndexSpecifierList1,Allocator1>& x,
1294   const multi_index_container<Value2,IndexSpecifierList2,Allocator2>& y)
1295 {
1296   return get<0>(x)>get<0>(y);
1297 }
1298
1299 template<
1300   typename Value1,typename IndexSpecifierList1,typename Allocator1,
1301   typename Value2,typename IndexSpecifierList2,typename Allocator2
1302 >
1303 bool operator>=(
1304   const multi_index_container<Value1,IndexSpecifierList1,Allocator1>& x,
1305   const multi_index_container<Value2,IndexSpecifierList2,Allocator2>& y)
1306 {
1307   return get<0>(x)>=get<0>(y);
1308 }
1309
1310 template<
1311   typename Value1,typename IndexSpecifierList1,typename Allocator1,
1312   typename Value2,typename IndexSpecifierList2,typename Allocator2
1313 >
1314 bool operator<=(
1315   const multi_index_container<Value1,IndexSpecifierList1,Allocator1>& x,
1316   const multi_index_container<Value2,IndexSpecifierList2,Allocator2>& y)
1317 {
1318   return get<0>(x)<=get<0>(y);
1319 }
1320
1321 /*  specialized algorithms */
1322
1323 template<typename Value,typename IndexSpecifierList,typename Allocator>
1324 void swap(
1325   multi_index_container<Value,IndexSpecifierList,Allocator>& x,
1326   multi_index_container<Value,IndexSpecifierList,Allocator>& y)
1327 {
1328   x.swap(y);
1329 }
1330
1331 } /* namespace multi_index */
1332
1333 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
1334 /* class version = 1 : we now serialize the size through
1335  * boost::serialization::collection_size_type.
1336  * class version = 2 : proper use of {save|load}_construct_data.
1337  */
1338
1339 namespace serialization {
1340 template<typename Value,typename IndexSpecifierList,typename Allocator>
1341 struct version<
1342   boost::multi_index_container<Value,IndexSpecifierList,Allocator>
1343 >
1344 {
1345   BOOST_STATIC_CONSTANT(int,value=2);
1346 };
1347 } /* namespace serialization */
1348 #endif
1349
1350 /* Associated global functions are promoted to namespace boost, except
1351  * comparison operators and swap, which are meant to be Koenig looked-up.
1352  */
1353
1354 using multi_index::get;
1355 using multi_index::project;
1356
1357 } /* namespace boost */
1358
1359 #undef BOOST_MULTI_INDEX_CHECK_INVARIANT
1360 #undef BOOST_MULTI_INDEX_CHECK_INVARIANT_OF
1361
1362 #endif