ceph/src/boost/boost/multi_index_container.hpp

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