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/core/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::index_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::final_node_type         final_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 #include <boost/multi_index/detail/define_if_constexpr_macro.hpp>
 369
 370     BOOST_MULTI_INDEX_IF_CONSTEXPR(
 371       node_alloc_traits::propagate_on_container_move_assignment::value){
 372       swap_(x,boost::true_type() /* swap_allocators */);
 373     }
 374     else if(this->get_allocator()==x.get_allocator()){
 375       swap_(x,boost::false_type() /* swap_allocators */);
 376     }
 377     else{
 378       multi_index_container y(boost::move(x),this->get_allocator());
 379       swap_(y,boost::false_type() /* swap_allocators */);
 380     }
 381     return *this;
 382
 383 #include <boost/multi_index/detail/undef_if_constexpr_macro.hpp>
 384   }
 385
 386 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
 387   multi_index_container<Value,IndexSpecifierList,Allocator>& operator=(
 388     std::initializer_list<Value> list)
 389   {
 390     BOOST_MULTI_INDEX_CHECK_INVARIANT;
 391     typedef const Value* init_iterator;
 392
 393     multi_index_container x(*this,detail::do_not_copy_elements_tag());
 394     iterator hint=x.end();
 395     for(init_iterator first=list.begin(),last=list.end();
 396         first!=last;++first){
 397       hint=x.make_iterator(x.insert_(*first,hint.get_node()).first);
 398       ++hint;
 399     }
 400     x.swap_elements_(*this);
 401     return*this;
 402   }
 403 #endif
 404
 405   allocator_type get_allocator()const BOOST_NOEXCEPT
 406   {
 407     return allocator_type(bfm_allocator::member);
 408   }
 409
 410   /* retrieval of indices by number */
 411
 412 #if !defined(BOOST_NO_MEMBER_TEMPLATES)
 413   template<int N>
 414   struct nth_index
 415   {
 416     BOOST_STATIC_ASSERT(N>=0&&N<mpl::size<index_type_list>::type::value);
 417     typedef typename mpl::at_c<index_type_list,N>::type type;
 418   };
 419
 420   template<int N>
 421   typename nth_index<N>::type& get()BOOST_NOEXCEPT
 422   {
 423     BOOST_STATIC_ASSERT(N>=0&&N<mpl::size<index_type_list>::type::value);
 424     return *this;
 425   }
 426
 427   template<int N>
 428   const typename nth_index<N>::type& get()const BOOST_NOEXCEPT
 429   {
 430     BOOST_STATIC_ASSERT(N>=0&&N<mpl::size<index_type_list>::type::value);
 431     return *this;
 432   }
 433 #endif
 434
 435   /* retrieval of indices by tag */
 436
 437 #if !defined(BOOST_NO_MEMBER_TEMPLATES)
 438   template<typename Tag>
 439   struct index
 440   {
 441     typedef typename mpl::find_if<
 442       index_type_list,
 443       detail::has_tag<Tag>
 444     >::type                                    iter;
 445
 446     BOOST_STATIC_CONSTANT(
 447       bool,index_found=!(is_same<iter,typename mpl::end<index_type_list>::type >::value));
 448     BOOST_STATIC_ASSERT(index_found);
 449
 450     typedef typename mpl::deref<iter>::type    type;
 451   };
 452
 453   template<typename Tag>
 454   typename index<Tag>::type& get()BOOST_NOEXCEPT
 455   {
 456     return *this;
 457   }
 458
 459   template<typename Tag>
 460   const typename index<Tag>::type& get()const BOOST_NOEXCEPT
 461   {
 462     return *this;
 463   }
 464 #endif
 465
 466   /* projection of iterators by number */
 467
 468 #if !defined(BOOST_NO_MEMBER_TEMPLATES)
 469   template<int N>
 470   struct nth_index_iterator
 471   {
 472     typedef typename nth_index<N>::type::iterator type;
 473   };
 474
 475   template<int N>
 476   struct nth_index_const_iterator
 477   {
 478     typedef typename nth_index<N>::type::const_iterator type;
 479   };
 480
 481   template<int N,typename IteratorType>
 482   typename nth_index_iterator<N>::type project(IteratorType it)
 483   {
 484     typedef typename nth_index<N>::type index_type;
 485
 486 #if !defined(__SUNPRO_CC)||!(__SUNPRO_CC<0x580) /* fails in Sun C++ 5.7 */
 487     BOOST_STATIC_ASSERT(
 488       (mpl::contains<iterator_type_list,IteratorType>::value));
 489 #endif
 490
 491     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it);
 492     BOOST_MULTI_INDEX_CHECK_IS_OWNER(
 493       it,static_cast<typename IteratorType::container_type&>(*this));
 494
 495     return index_type::make_iterator(
 496       static_cast<final_node_type*>(it.get_node()));
 497   }
 498
 499   template<int N,typename IteratorType>
 500   typename nth_index_const_iterator<N>::type project(IteratorType it)const
 501   {
 502     typedef typename nth_index<N>::type index_type;
 503
 504 #if !defined(__SUNPRO_CC)||!(__SUNPRO_CC<0x580) /* fails in Sun C++ 5.7 */
 505     BOOST_STATIC_ASSERT((
 506       mpl::contains<iterator_type_list,IteratorType>::value||
 507       mpl::contains<const_iterator_type_list,IteratorType>::value));
 508 #endif
 509
 510     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it);
 511     BOOST_MULTI_INDEX_CHECK_IS_OWNER(
 512       it,static_cast<const typename IteratorType::container_type&>(*this));
 513     return index_type::make_iterator(
 514       static_cast<final_node_type*>(it.get_node()));
 515   }
 516 #endif
 517
 518   /* projection of iterators by tag */
 519
 520 #if !defined(BOOST_NO_MEMBER_TEMPLATES)
 521   template<typename Tag>
 522   struct index_iterator
 523   {
 524     typedef typename index<Tag>::type::iterator type;
 525   };
 526
 527   template<typename Tag>
 528   struct index_const_iterator
 529   {
 530     typedef typename index<Tag>::type::const_iterator type;
 531   };
 532
 533   template<typename Tag,typename IteratorType>
 534   typename index_iterator<Tag>::type project(IteratorType it)
 535   {
 536     typedef typename index<Tag>::type index_type;
 537
 538 #if !defined(__SUNPRO_CC)||!(__SUNPRO_CC<0x580) /* fails in Sun C++ 5.7 */
 539     BOOST_STATIC_ASSERT(
 540       (mpl::contains<iterator_type_list,IteratorType>::value));
 541 #endif
 542
 543     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it);
 544     BOOST_MULTI_INDEX_CHECK_IS_OWNER(
 545       it,static_cast<typename IteratorType::container_type&>(*this));
 546     return index_type::make_iterator(
 547       static_cast<final_node_type*>(it.get_node()));
 548   }
 549
 550   template<typename Tag,typename IteratorType>
 551   typename index_const_iterator<Tag>::type project(IteratorType it)const
 552   {
 553     typedef typename index<Tag>::type index_type;
 554
 555 #if !defined(__SUNPRO_CC)||!(__SUNPRO_CC<0x580) /* fails in Sun C++ 5.7 */
 556     BOOST_STATIC_ASSERT((
 557       mpl::contains<iterator_type_list,IteratorType>::value||
 558       mpl::contains<const_iterator_type_list,IteratorType>::value));
 559 #endif
 560
 561     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it);
 562     BOOST_MULTI_INDEX_CHECK_IS_OWNER(
 563       it,static_cast<const typename IteratorType::container_type&>(*this));
 564     return index_type::make_iterator(
 565       static_cast<final_node_type*>(it.get_node()));
 566   }
 567 #endif
 568
 569 BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS:
 570   typedef typename super::final_node_handle_type final_node_handle_type;
 571   typedef typename super::copy_map_type          copy_map_type;
 572
 573   multi_index_container(
 574     multi_index_container<Value,IndexSpecifierList,Allocator>& x,
 575     const allocator_type& al,
 576     detail::unequal_alloc_move_ctor_tag):
 577     bfm_allocator(al),
 578     bfm_header(),
 579     super(x),
 580     node_count(0)
 581   {
 582     BOOST_MULTI_INDEX_CHECK_INVARIANT_OF(x);
 583     BOOST_TRY{
 584       copy_map_type map(bfm_allocator::member,x.size(),x.header(),header());
 585       for(const_iterator it=x.begin(),it_end=x.end();it!=it_end;++it){
 586         map.move_clone(it.get_node());
 587       }
 588       super::copy_(x,map);
 589       map.release();
 590       node_count=x.size();
 591       x.clear();
 592     }
 593     BOOST_CATCH(...){
 594       x.clear();
 595       BOOST_RETHROW;
 596     }
 597     BOOST_CATCH_END
 598
 599     /* Not until this point are the indices required to be consistent,
 600      * hence the position of the invariant checker.
 601      */
 602
 603     BOOST_MULTI_INDEX_CHECK_INVARIANT;
 604   }
 605
 606 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
 607   multi_index_container(
 608     const multi_index_container<Value,IndexSpecifierList,Allocator>& x,
 609     detail::do_not_copy_elements_tag):
 610     bfm_allocator(x.bfm_allocator::member),
 611     bfm_header(),
 612     super(x,detail::do_not_copy_elements_tag()),
 613     node_count(0)
 614   {
 615     BOOST_MULTI_INDEX_CHECK_INVARIANT;
 616   }
 617 #endif
 618
 619   void copy_construct_from(
 620     const multi_index_container<Value,IndexSpecifierList,Allocator>& x)
 621   {
 622     copy_map_type map(bfm_allocator::member,x.size(),x.header(),header());
 623     for(const_iterator it=x.begin(),it_end=x.end();it!=it_end;++it){
 624       map.copy_clone(it.get_node());
 625     }
 626     super::copy_(x,map);
 627     map.release();
 628     node_count=x.size();
 629
 630     /* Not until this point are the indices required to be consistent,
 631      * hence the position of the invariant checker.
 632      */
 633
 634     BOOST_MULTI_INDEX_CHECK_INVARIANT;
 635   }
 636
 637   final_node_type* header()const
 638   {
 639     return &*bfm_header::member;
 640   }
 641
 642   final_node_type* allocate_node()
 643   {
 644     return &*node_alloc_traits::allocate(bfm_allocator::member,1);
 645   }
 646
 647   void deallocate_node(final_node_type* x)
 648   {
 649     node_alloc_traits::deallocate(
 650       bfm_allocator::member,static_cast<node_pointer>(x),1);
 651   }
 652
 653   void construct_value(final_node_type* x,const Value& v)
 654   {
 655     node_alloc_traits::construct(
 656       bfm_allocator::member,boost::addressof(x->value()),v);
 657   }
 658
 659   void construct_value(final_node_type* x,BOOST_RV_REF(Value) v)
 660   {
 661     node_alloc_traits::construct(
 662       bfm_allocator::member,boost::addressof(x->value()),boost::move(v));
 663   }
 664
 665   BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL_EXTRA_ARG(
 666     void,construct_value,vartempl_construct_value_impl,final_node_type*,x)
 667
 668   void destroy_value(final_node_type* x)
 669   {
 670     node_alloc_traits::destroy(
 671       bfm_allocator::member,boost::addressof(x->value()));
 672   }
 673
 674   bool empty_()const
 675   {
 676     return node_count==0;
 677   }
 678
 679   size_type size_()const
 680   {
 681     return node_count;
 682   }
 683
 684   size_type max_size_()const
 685   {
 686     return static_cast<size_type>(-1);
 687   }
 688
 689   template<typename Variant>
 690   std::pair<final_node_type*,bool> insert_(const Value& v,Variant variant)
 691   {
 692     final_node_type* x=0;
 693     final_node_type* res=super::insert_(v,x,variant);
 694     if(res==x){
 695       ++node_count;
 696       return std::pair<final_node_type*,bool>(res,true);
 697     }
 698     else{
 699       return std::pair<final_node_type*,bool>(res,false);
 700     }
 701   }
 702
 703   std::pair<final_node_type*,bool> insert_(const Value& v)
 704   {
 705     return insert_(v,detail::lvalue_tag());
 706   }
 707
 708   std::pair<final_node_type*,bool> insert_rv_(const Value& v)
 709   {
 710     return insert_(v,detail::rvalue_tag());
 711   }
 712
 713   template<typename T>
 714   std::pair<final_node_type*,bool> insert_ref_(T& t)
 715   {
 716     final_node_type* x=allocate_node();
 717     BOOST_TRY{
 718       construct_value(x,t);
 719       BOOST_TRY{
 720         final_node_type* res=super::insert_(
 721           x->value(),x,detail::emplaced_tag());
 722         if(res==x){
 723           ++node_count;
 724           return std::pair<final_node_type*,bool>(res,true);
 725         }
 726         else{
 727           delete_node_(x);
 728           return std::pair<final_node_type*,bool>(res,false);
 729         }
 730       }
 731       BOOST_CATCH(...){
 732         destroy_value(x);
 733         BOOST_RETHROW;
 734       }
 735       BOOST_CATCH_END
 736     }
 737     BOOST_CATCH(...){
 738       deallocate_node(x);
 739       BOOST_RETHROW;
 740     }
 741     BOOST_CATCH_END
 742   }
 743
 744   std::pair<final_node_type*,bool> insert_ref_(const value_type& x)
 745   {
 746     return insert_(x);
 747   }
 748
 749   std::pair<final_node_type*,bool> insert_ref_(value_type& x)
 750   {
 751     return insert_(x);
 752   }
 753
 754   std::pair<final_node_type*,bool> insert_nh_(final_node_handle_type& nh)
 755   {
 756     if(!nh)return std::pair<final_node_type*,bool>(header(),false);
 757     else{
 758       final_node_type* x=nh.node;
 759       final_node_type* res=super::insert_(
 760         x->value(),x,detail::emplaced_tag());
 761       if(res==x){
 762         nh.release_node();
 763         ++node_count;
 764         return std::pair<final_node_type*,bool>(res,true);
 765       }
 766       else return std::pair<final_node_type*,bool>(res,false);
 767     }
 768   }
 769
 770   template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK>
 771   std::pair<final_node_type*,bool> emplace_(
 772     BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK)
 773   {
 774     final_node_type* x=allocate_node();
 775     BOOST_TRY{
 776       construct_value(x,BOOST_MULTI_INDEX_FORWARD_PARAM_PACK);
 777       BOOST_TRY{
 778         final_node_type* res=super::insert_(
 779           x->value(),x,detail::emplaced_tag());
 780         if(res==x){
 781           ++node_count;
 782           return std::pair<final_node_type*,bool>(res,true);
 783         }
 784         else{
 785           delete_node_(x);
 786           return std::pair<final_node_type*,bool>(res,false);
 787         }
 788       }
 789       BOOST_CATCH(...){
 790         destroy_value(x);
 791         BOOST_RETHROW;
 792       }
 793       BOOST_CATCH_END
 794     }
 795     BOOST_CATCH(...){
 796       deallocate_node(x);
 797       BOOST_RETHROW;
 798     }
 799     BOOST_CATCH_END
 800   }
 801
 802   template<typename Variant>
 803   std::pair<final_node_type*,bool> insert_(
 804     const Value& v,final_node_type* position,Variant variant)
 805   {
 806     final_node_type* x=0;
 807     final_node_type* res=super::insert_(v,position,x,variant);
 808     if(res==x){
 809       ++node_count;
 810       return std::pair<final_node_type*,bool>(res,true);
 811     }
 812     else{
 813       return std::pair<final_node_type*,bool>(res,false);
 814     }
 815   }
 816
 817   std::pair<final_node_type*,bool> insert_(
 818     const Value& v,final_node_type* position)
 819   {
 820     return insert_(v,position,detail::lvalue_tag());
 821   }
 822
 823   std::pair<final_node_type*,bool> insert_rv_(
 824     const Value& v,final_node_type* position)
 825   {
 826     return insert_(v,position,detail::rvalue_tag());
 827   }
 828
 829   template<typename T>
 830   std::pair<final_node_type*,bool> insert_ref_(
 831     T& t,final_node_type* position)
 832   {
 833     final_node_type* x=allocate_node();
 834     BOOST_TRY{
 835       construct_value(x,t);
 836       BOOST_TRY{
 837         final_node_type* res=super::insert_(
 838           x->value(),position,x,detail::emplaced_tag());
 839         if(res==x){
 840           ++node_count;
 841           return std::pair<final_node_type*,bool>(res,true);
 842         }
 843         else{
 844           delete_node_(x);
 845           return std::pair<final_node_type*,bool>(res,false);
 846         }
 847       }
 848       BOOST_CATCH(...){
 849         destroy_value(x);
 850         BOOST_RETHROW;
 851       }
 852       BOOST_CATCH_END
 853     }
 854     BOOST_CATCH(...){
 855       deallocate_node(x);
 856       BOOST_RETHROW;
 857     }
 858     BOOST_CATCH_END
 859   }
 860
 861   std::pair<final_node_type*,bool> insert_ref_(
 862     const value_type& x,final_node_type* position)
 863   {
 864     return insert_(x,position);
 865   }
 866
 867   std::pair<final_node_type*,bool> insert_ref_(
 868     value_type& x,final_node_type* position)
 869   {
 870     return insert_(x,position);
 871   }
 872
 873   std::pair<final_node_type*,bool> insert_nh_(
 874     final_node_handle_type& nh,final_node_type* position)
 875   {
 876     if(!nh)return std::pair<final_node_type*,bool>(header(),false);
 877     else{
 878       final_node_type* x=nh.node;
 879       final_node_type* res=super::insert_(
 880         x->value(),position,x,detail::emplaced_tag());
 881       if(res==x){
 882         nh.release_node();
 883         ++node_count;
 884         return std::pair<final_node_type*,bool>(res,true);
 885       }
 886       else return std::pair<final_node_type*,bool>(res,false);
 887     }
 888   }
 889
 890   template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK>
 891   std::pair<final_node_type*,bool> emplace_hint_(
 892     final_node_type* position,
 893     BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK)
 894   {
 895     final_node_type* x=allocate_node();
 896     BOOST_TRY{
 897       construct_value(x,BOOST_MULTI_INDEX_FORWARD_PARAM_PACK);
 898       BOOST_TRY{
 899         final_node_type* res=super::insert_(
 900           x->value(),position,x,detail::emplaced_tag());
 901         if(res==x){
 902           ++node_count;
 903           return std::pair<final_node_type*,bool>(res,true);
 904         }
 905         else{
 906           delete_node_(x);
 907           return std::pair<final_node_type*,bool>(res,false);
 908         }
 909       }
 910       BOOST_CATCH(...){
 911         destroy_value(x);
 912         BOOST_RETHROW;
 913       }
 914       BOOST_CATCH_END
 915     }
 916     BOOST_CATCH(...){
 917       deallocate_node(x);
 918       BOOST_RETHROW;
 919     }
 920     BOOST_CATCH_END
 921   }
 922
 923   final_node_handle_type extract_(final_node_type* x)
 924   {
 925     --node_count;
 926     super::extract_(x);
 927     return final_node_handle_type(x,get_allocator());
 928   }
 929
 930   void erase_(final_node_type* x)
 931   {
 932     --node_count;
 933     super::extract_(x);
 934     delete_node_(x);
 935   }
 936
 937   void delete_node_(final_node_type* x)
 938   {
 939     destroy_value(x);
 940     deallocate_node(x);
 941   }
 942
 943   void delete_all_nodes_()
 944   {
 945     super::delete_all_nodes_();
 946   }
 947
 948   void clear_()
 949   {
 950     delete_all_nodes_();
 951     super::clear_();
 952     node_count=0;
 953   }
 954
 955   void swap_(multi_index_container<Value,IndexSpecifierList,Allocator>& x)
 956   {
 957     swap_(
 958       x,
 959       boost::integral_constant<
 960         bool,node_alloc_traits::propagate_on_container_swap::value>());
 961   }
 962
 963   void swap_(
 964     multi_index_container<Value,IndexSpecifierList,Allocator>& x,
 965     boost::true_type swap_allocators)
 966   {
 967     detail::adl_swap(bfm_allocator::member,x.bfm_allocator::member);
 968     std::swap(bfm_header::member,x.bfm_header::member);
 969     super::swap_(x,swap_allocators);
 970     std::swap(node_count,x.node_count);
 971   }
 972
 973   void swap_(
 974     multi_index_container<Value,IndexSpecifierList,Allocator>& x,
 975     boost::false_type swap_allocators)
 976   {
 977     std::swap(bfm_header::member,x.bfm_header::member);
 978     super::swap_(x,swap_allocators);
 979     std::swap(node_count,x.node_count);
 980   }
 981
 982   void swap_elements_(
 983     multi_index_container<Value,IndexSpecifierList,Allocator>& x)
 984   {
 985     std::swap(bfm_header::member,x.bfm_header::member);
 986     super::swap_elements_(x);
 987     std::swap(node_count,x.node_count);
 988   }
 989
 990   bool replace_(const Value& k,final_node_type* x)
 991   {
 992     return super::replace_(k,x,detail::lvalue_tag());
 993   }
 994
 995   bool replace_rv_(const Value& k,final_node_type* x)
 996   {
 997     return super::replace_(k,x,detail::rvalue_tag());
 998   }
 999
1000   template<typename Modifier>
1001   bool modify_(Modifier& mod,final_node_type* x)
1002   {
1003     BOOST_TRY{
1004       mod(const_cast<value_type&>(x->value()));
1005     }
1006     BOOST_CATCH(...){
1007       this->erase_(x);
1008       BOOST_RETHROW;
1009     }
1010     BOOST_CATCH_END
1011
1012     BOOST_TRY{
1013       if(!super::modify_(x)){
1014         delete_node_(x);
1015         --node_count;
1016         return false;
1017       }
1018       else return true;
1019     }
1020     BOOST_CATCH(...){
1021       delete_node_(x);
1022       --node_count;
1023       BOOST_RETHROW;
1024     }
1025     BOOST_CATCH_END
1026   }
1027
1028   template<typename Modifier,typename Rollback>
1029   bool modify_(Modifier& mod,Rollback& back_,final_node_type* x)
1030   {
1031     BOOST_TRY{
1032       mod(const_cast<value_type&>(x->value()));
1033     }
1034     BOOST_CATCH(...){
1035       this->erase_(x);
1036       BOOST_RETHROW;
1037     }
1038     BOOST_CATCH_END
1039
1040     bool b;
1041     BOOST_TRY{
1042       b=super::modify_rollback_(x);
1043     }
1044     BOOST_CATCH(...){
1045       BOOST_TRY{
1046         back_(const_cast<value_type&>(x->value()));
1047         if(!super::check_rollback_(x))this->erase_(x);
1048         BOOST_RETHROW;
1049       }
1050       BOOST_CATCH(...){
1051         this->erase_(x);
1052         BOOST_RETHROW;
1053       }
1054       BOOST_CATCH_END
1055     }
1056     BOOST_CATCH_END
1057
1058     BOOST_TRY{
1059       if(!b){
1060         back_(const_cast<value_type&>(x->value()));
1061         if(!super::check_rollback_(x))this->erase_(x);
1062         return false;
1063       }
1064       else return true;
1065     }
1066     BOOST_CATCH(...){
1067       this->erase_(x);
1068       BOOST_RETHROW;
1069     }
1070     BOOST_CATCH_END
1071   }
1072
1073 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
1074   /* serialization */
1075
1076   friend class boost::serialization::access;
1077
1078   BOOST_SERIALIZATION_SPLIT_MEMBER()
1079
1080   typedef typename super::index_saver_type        index_saver_type;
1081   typedef typename super::index_loader_type       index_loader_type;
1082
1083   template<class Archive>
1084   void save(Archive& ar,const unsigned int version)const
1085   {
1086     const serialization::collection_size_type       s(size_());
1087     const detail::serialization_version<value_type> value_version;
1088     ar<<serialization::make_nvp("count",s);
1089     ar<<serialization::make_nvp("value_version",value_version);
1090
1091     index_saver_type sm(bfm_allocator::member,s);
1092
1093     for(iterator it=super::begin(),it_end=super::end();it!=it_end;++it){
1094       serialization::save_construct_data_adl(
1095         ar,boost::addressof(*it),value_version);
1096       ar<<serialization::make_nvp("item",*it);
1097       sm.add(it.get_node(),ar,version);
1098     }
1099     sm.add_track(header(),ar,version);
1100
1101     super::save_(ar,version,sm);
1102   }
1103
1104   template<class Archive>
1105   void load(Archive& ar,const unsigned int version)
1106   {
1107     BOOST_MULTI_INDEX_CHECK_INVARIANT;
1108
1109     clear_();
1110     serialization::collection_size_type       s;
1111     detail::serialization_version<value_type> value_version;
1112     if(version<1){
1113       std::size_t sz;
1114       ar>>serialization::make_nvp("count",sz);
1115       s=static_cast<serialization::collection_size_type>(sz);
1116     }
1117     else{
1118       ar>>serialization::make_nvp("count",s);
1119     }
1120     if(version<2){
1121       value_version=0;
1122     }
1123     else{
1124       ar>>serialization::make_nvp("value_version",value_version);
1125     }
1126
1127     index_loader_type lm(bfm_allocator::member,s);
1128
1129     for(std::size_t n=0;n<s;++n){
1130       detail::archive_constructed<Value> value("item",ar,value_version);
1131       std::pair<final_node_type*,bool> p=insert_rv_(
1132         value.get(),super::end().get_node());
1133       if(!p.second)throw_exception(
1134         archive::archive_exception(
1135           archive::archive_exception::other_exception));
1136       ar.reset_object_address(
1137         boost::addressof(p.first->value()),boost::addressof(value.get()));
1138       lm.add(p.first,ar,version);
1139     }
1140     lm.add_track(header(),ar,version);
1141
1142     super::load_(ar,version,lm);
1143   }
1144 #endif
1145
1146 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
1147   /* invariant stuff */
1148
1149   bool invariant_()const
1150   {
1151     return super::invariant_();
1152   }
1153
1154   void check_invariant_()const
1155   {
1156     BOOST_MULTI_INDEX_INVARIANT_ASSERT(invariant_());
1157   }
1158 #endif
1159
1160 private:
1161   template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK>
1162   void vartempl_construct_value_impl(
1163     final_node_type* x,BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK)
1164   {
1165     node_alloc_traits::construct(
1166       bfm_allocator::member,boost::addressof(x->value()),
1167       BOOST_MULTI_INDEX_FORWARD_PARAM_PACK);
1168   }
1169
1170   size_type node_count;
1171
1172 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
1173     BOOST_WORKAROUND(__MWERKS__,<=0x3003)
1174 #pragma parse_mfunc_templ reset
1175 #endif
1176 };
1177
1178 #if BOOST_WORKAROUND(BOOST_MSVC,BOOST_TESTED_AT(1500))
1179 #pragma warning(pop) /* C4522 */
1180 #endif
1181
1182 /* retrieval of indices by number */
1183
1184 template<typename MultiIndexContainer,int N>
1185 struct nth_index
1186 {
1187   BOOST_STATIC_CONSTANT(
1188     int,
1189     M=mpl::size<typename MultiIndexContainer::index_type_list>::type::value);
1190   BOOST_STATIC_ASSERT(N>=0&&N<M);
1191   typedef typename mpl::at_c<
1192     typename MultiIndexContainer::index_type_list,N>::type type;
1193 };
1194
1195 template<int N,typename Value,typename IndexSpecifierList,typename Allocator>
1196 typename nth_index<
1197   multi_index_container<Value,IndexSpecifierList,Allocator>,N>::type&
1198 get(
1199   multi_index_container<Value,IndexSpecifierList,Allocator>& m)BOOST_NOEXCEPT
1200 {
1201   typedef multi_index_container<
1202     Value,IndexSpecifierList,Allocator>    multi_index_type;
1203   typedef typename nth_index<
1204     multi_index_container<
1205       Value,IndexSpecifierList,Allocator>,
1206     N
1207   >::type                                  index_type;
1208
1209   BOOST_STATIC_ASSERT(N>=0&&
1210     N<
1211     mpl::size<
1212       BOOST_DEDUCED_TYPENAME multi_index_type::index_type_list
1213     >::type::value);
1214
1215   return detail::converter<multi_index_type,index_type>::index(m);
1216 }
1217
1218 template<int N,typename Value,typename IndexSpecifierList,typename Allocator>
1219 const typename nth_index<
1220   multi_index_container<Value,IndexSpecifierList,Allocator>,N>::type&
1221 get(
1222   const multi_index_container<Value,IndexSpecifierList,Allocator>& m
1223 )BOOST_NOEXCEPT
1224 {
1225   typedef multi_index_container<
1226     Value,IndexSpecifierList,Allocator>    multi_index_type;
1227   typedef typename nth_index<
1228     multi_index_container<
1229       Value,IndexSpecifierList,Allocator>,
1230     N
1231   >::type                                  index_type;
1232
1233   BOOST_STATIC_ASSERT(N>=0&&
1234     N<
1235     mpl::size<
1236       BOOST_DEDUCED_TYPENAME multi_index_type::index_type_list
1237     >::type::value);
1238
1239   return detail::converter<multi_index_type,index_type>::index(m);
1240 }
1241
1242 /* retrieval of indices by tag */
1243
1244 template<typename MultiIndexContainer,typename Tag>
1245 struct index
1246 {
1247   typedef typename MultiIndexContainer::index_type_list index_type_list;
1248
1249   typedef typename mpl::find_if<
1250     index_type_list,
1251     detail::has_tag<Tag>
1252   >::type                                      iter;
1253
1254   BOOST_STATIC_CONSTANT(
1255     bool,index_found=!(is_same<iter,typename mpl::end<index_type_list>::type >::value));
1256   BOOST_STATIC_ASSERT(index_found);
1257
1258   typedef typename mpl::deref<iter>::type       type;
1259 };
1260
1261 template<
1262   typename Tag,typename Value,typename IndexSpecifierList,typename Allocator
1263 >
1264 typename ::boost::multi_index::index<
1265   multi_index_container<Value,IndexSpecifierList,Allocator>,Tag>::type&
1266 get(
1267   multi_index_container<Value,IndexSpecifierList,Allocator>& m)BOOST_NOEXCEPT
1268 {
1269   typedef multi_index_container<
1270     Value,IndexSpecifierList,Allocator>         multi_index_type;
1271   typedef typename ::boost::multi_index::index<
1272     multi_index_container<
1273       Value,IndexSpecifierList,Allocator>,
1274     Tag
1275   >::type                                       index_type;
1276
1277   return detail::converter<multi_index_type,index_type>::index(m);
1278 }
1279
1280 template<
1281   typename Tag,typename Value,typename IndexSpecifierList,typename Allocator
1282 >
1283 const typename ::boost::multi_index::index<
1284   multi_index_container<Value,IndexSpecifierList,Allocator>,Tag>::type&
1285 get(
1286   const multi_index_container<Value,IndexSpecifierList,Allocator>& m
1287 )BOOST_NOEXCEPT
1288 {
1289   typedef multi_index_container<
1290     Value,IndexSpecifierList,Allocator>         multi_index_type;
1291   typedef typename ::boost::multi_index::index<
1292     multi_index_container<
1293       Value,IndexSpecifierList,Allocator>,
1294     Tag
1295   >::type                                       index_type;
1296
1297   return detail::converter<multi_index_type,index_type>::index(m);
1298 }
1299
1300 /* projection of iterators by number */
1301
1302 template<typename MultiIndexContainer,int N>
1303 struct nth_index_iterator
1304 {
1305   typedef typename nth_index<MultiIndexContainer,N>::type::iterator type;
1306 };
1307
1308 template<typename MultiIndexContainer,int N>
1309 struct nth_index_const_iterator
1310 {
1311   typedef typename nth_index<MultiIndexContainer,N>::type::const_iterator type;
1312 };
1313
1314 template<
1315   int N,typename IteratorType,
1316   typename Value,typename IndexSpecifierList,typename Allocator>
1317 typename nth_index_iterator<
1318   multi_index_container<Value,IndexSpecifierList,Allocator>,N>::type
1319 project(
1320   multi_index_container<Value,IndexSpecifierList,Allocator>& m,
1321   IteratorType it)
1322 {
1323   typedef multi_index_container<
1324     Value,IndexSpecifierList,Allocator>                multi_index_type;
1325   typedef typename nth_index<multi_index_type,N>::type index_type;
1326
1327 #if !defined(__SUNPRO_CC)||!(__SUNPRO_CC<0x580) /* Sun C++ 5.7 fails */
1328   BOOST_STATIC_ASSERT((
1329     mpl::contains<
1330       BOOST_DEDUCED_TYPENAME multi_index_type::iterator_type_list,
1331       IteratorType>::value));
1332 #endif
1333
1334   BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it);
1335
1336 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1337   typedef detail::converter<
1338     multi_index_type,
1339     BOOST_DEDUCED_TYPENAME IteratorType::container_type> converter;
1340   BOOST_MULTI_INDEX_CHECK_IS_OWNER(it,converter::index(m));
1341 #endif
1342
1343   return detail::converter<multi_index_type,index_type>::iterator(
1344     m,static_cast<typename multi_index_type::final_node_type*>(it.get_node()));
1345 }
1346
1347 template<
1348   int N,typename IteratorType,
1349   typename Value,typename IndexSpecifierList,typename Allocator>
1350 typename nth_index_const_iterator<
1351   multi_index_container<Value,IndexSpecifierList,Allocator>,N>::type
1352 project(
1353   const multi_index_container<Value,IndexSpecifierList,Allocator>& m,
1354   IteratorType it)
1355 {
1356   typedef multi_index_container<
1357     Value,IndexSpecifierList,Allocator>                multi_index_type;
1358   typedef typename nth_index<multi_index_type,N>::type index_type;
1359
1360 #if !defined(__SUNPRO_CC)||!(__SUNPRO_CC<0x580) /* Sun C++ 5.7 fails */
1361   BOOST_STATIC_ASSERT((
1362     mpl::contains<
1363       BOOST_DEDUCED_TYPENAME multi_index_type::iterator_type_list,
1364       IteratorType>::value||
1365     mpl::contains<
1366       BOOST_DEDUCED_TYPENAME multi_index_type::const_iterator_type_list,
1367       IteratorType>::value));
1368 #endif
1369
1370   BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it);
1371
1372 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1373   typedef detail::converter<
1374     multi_index_type,
1375     BOOST_DEDUCED_TYPENAME IteratorType::container_type> converter;
1376   BOOST_MULTI_INDEX_CHECK_IS_OWNER(it,converter::index(m));
1377 #endif
1378
1379   return detail::converter<multi_index_type,index_type>::const_iterator(
1380     m,static_cast<typename multi_index_type::final_node_type*>(it.get_node()));
1381 }
1382
1383 /* projection of iterators by tag */
1384
1385 template<typename MultiIndexContainer,typename Tag>
1386 struct index_iterator
1387 {
1388   typedef typename ::boost::multi_index::index<
1389     MultiIndexContainer,Tag>::type::iterator    type;
1390 };
1391
1392 template<typename MultiIndexContainer,typename Tag>
1393 struct index_const_iterator
1394 {
1395   typedef typename ::boost::multi_index::index<
1396     MultiIndexContainer,Tag>::type::const_iterator type;
1397 };
1398
1399 template<
1400   typename Tag,typename IteratorType,
1401   typename Value,typename IndexSpecifierList,typename Allocator>
1402 typename index_iterator<
1403   multi_index_container<Value,IndexSpecifierList,Allocator>,Tag>::type
1404 project(
1405   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 #endif
1419
1420   BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it);
1421
1422 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1423   typedef detail::converter<
1424     multi_index_type,
1425     BOOST_DEDUCED_TYPENAME IteratorType::container_type> converter;
1426   BOOST_MULTI_INDEX_CHECK_IS_OWNER(it,converter::index(m));
1427 #endif
1428
1429   return detail::converter<multi_index_type,index_type>::iterator(
1430     m,static_cast<typename multi_index_type::final_node_type*>(it.get_node()));
1431 }
1432
1433 template<
1434   typename Tag,typename IteratorType,
1435   typename Value,typename IndexSpecifierList,typename Allocator>
1436 typename index_const_iterator<
1437   multi_index_container<Value,IndexSpecifierList,Allocator>,Tag>::type
1438 project(
1439   const multi_index_container<Value,IndexSpecifierList,Allocator>& m,
1440   IteratorType it)
1441 {
1442   typedef multi_index_container<
1443     Value,IndexSpecifierList,Allocator>         multi_index_type;
1444   typedef typename ::boost::multi_index::index<
1445     multi_index_type,Tag>::type                 index_type;
1446
1447 #if !defined(__SUNPRO_CC)||!(__SUNPRO_CC<0x580) /* Sun C++ 5.7 fails */
1448   BOOST_STATIC_ASSERT((
1449     mpl::contains<
1450       BOOST_DEDUCED_TYPENAME multi_index_type::iterator_type_list,
1451       IteratorType>::value||
1452     mpl::contains<
1453       BOOST_DEDUCED_TYPENAME multi_index_type::const_iterator_type_list,
1454       IteratorType>::value));
1455 #endif
1456
1457   BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it);
1458
1459 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1460   typedef detail::converter<
1461     multi_index_type,
1462     BOOST_DEDUCED_TYPENAME IteratorType::container_type> converter;
1463   BOOST_MULTI_INDEX_CHECK_IS_OWNER(it,converter::index(m));
1464 #endif
1465
1466   return detail::converter<multi_index_type,index_type>::const_iterator(
1467     m,static_cast<typename multi_index_type::final_node_type*>(it.get_node()));
1468 }
1469
1470 /* Comparison. Simple forward to first index. */
1471
1472 template<
1473   typename Value1,typename IndexSpecifierList1,typename Allocator1,
1474   typename Value2,typename IndexSpecifierList2,typename Allocator2
1475 >
1476 bool operator==(
1477   const multi_index_container<Value1,IndexSpecifierList1,Allocator1>& x,
1478   const multi_index_container<Value2,IndexSpecifierList2,Allocator2>& y)
1479 {
1480   return get<0>(x)==get<0>(y);
1481 }
1482
1483 template<
1484   typename Value1,typename IndexSpecifierList1,typename Allocator1,
1485   typename Value2,typename IndexSpecifierList2,typename Allocator2
1486 >
1487 bool operator<(
1488   const multi_index_container<Value1,IndexSpecifierList1,Allocator1>& x,
1489   const multi_index_container<Value2,IndexSpecifierList2,Allocator2>& y)
1490 {
1491   return get<0>(x)<get<0>(y);
1492 }
1493
1494 template<
1495   typename Value1,typename IndexSpecifierList1,typename Allocator1,
1496   typename Value2,typename IndexSpecifierList2,typename Allocator2
1497 >
1498 bool operator!=(
1499   const multi_index_container<Value1,IndexSpecifierList1,Allocator1>& x,
1500   const multi_index_container<Value2,IndexSpecifierList2,Allocator2>& y)
1501 {
1502   return get<0>(x)!=get<0>(y);
1503 }
1504
1505 template<
1506   typename Value1,typename IndexSpecifierList1,typename Allocator1,
1507   typename Value2,typename IndexSpecifierList2,typename Allocator2
1508 >
1509 bool operator>(
1510   const multi_index_container<Value1,IndexSpecifierList1,Allocator1>& x,
1511   const multi_index_container<Value2,IndexSpecifierList2,Allocator2>& y)
1512 {
1513   return get<0>(x)>get<0>(y);
1514 }
1515
1516 template<
1517   typename Value1,typename IndexSpecifierList1,typename Allocator1,
1518   typename Value2,typename IndexSpecifierList2,typename Allocator2
1519 >
1520 bool operator>=(
1521   const multi_index_container<Value1,IndexSpecifierList1,Allocator1>& x,
1522   const multi_index_container<Value2,IndexSpecifierList2,Allocator2>& y)
1523 {
1524   return get<0>(x)>=get<0>(y);
1525 }
1526
1527 template<
1528   typename Value1,typename IndexSpecifierList1,typename Allocator1,
1529   typename Value2,typename IndexSpecifierList2,typename Allocator2
1530 >
1531 bool operator<=(
1532   const multi_index_container<Value1,IndexSpecifierList1,Allocator1>& x,
1533   const multi_index_container<Value2,IndexSpecifierList2,Allocator2>& y)
1534 {
1535   return get<0>(x)<=get<0>(y);
1536 }
1537
1538 /*  specialized algorithms */
1539
1540 template<typename Value,typename IndexSpecifierList,typename Allocator>
1541 void swap(
1542   multi_index_container<Value,IndexSpecifierList,Allocator>& x,
1543   multi_index_container<Value,IndexSpecifierList,Allocator>& y)
1544 {
1545   x.swap(y);
1546 }
1547
1548 } /* namespace multi_index */
1549
1550 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
1551 /* class version = 1 : we now serialize the size through
1552  * boost::serialization::collection_size_type.
1553  * class version = 2 : proper use of {save|load}_construct_data.
1554  */
1555
1556 namespace serialization {
1557 template<typename Value,typename IndexSpecifierList,typename Allocator>
1558 struct version<
1559   boost::multi_index_container<Value,IndexSpecifierList,Allocator>
1560 >
1561 {
1562   BOOST_STATIC_CONSTANT(int,value=2);
1563 };
1564 } /* namespace serialization */
1565 #endif
1566
1567 /* Associated global functions are promoted to namespace boost, except
1568  * comparison operators and swap, which are meant to be Koenig looked-up.
1569  */
1570
1571 using multi_index::get;
1572 using multi_index::project;
1573
1574 } /* namespace boost */
1575
1576 #undef BOOST_MULTI_INDEX_CHECK_INVARIANT
1577 #undef BOOST_MULTI_INDEX_CHECK_INVARIANT_OF
1578
1579 #endif