src/thirdparty/boost_1_47_0/boost/multi_index_container.hpp

   1 /* Multiply indexed container.
   2  *
   3  * Copyright 2003-2010 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)&&(_MSC_VER>=1200)
  15 #pragma once
  16 #endif
  17
  18 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
  19 #include <algorithm>
  20 #include <boost/detail/allocator_utilities.hpp>
  21 #include <boost/detail/no_exceptions_support.hpp>
  22 #include <boost/detail/workaround.hpp>
  23 #include <boost/mpl/at.hpp>
  24 #include <boost/mpl/contains.hpp>
  25 #include <boost/mpl/find_if.hpp>
  26 #include <boost/mpl/identity.hpp>
  27 #include <boost/mpl/int.hpp>
  28 #include <boost/mpl/size.hpp>
  29 #include <boost/mpl/deref.hpp>
  30 #include <boost/multi_index_container_fwd.hpp>
  31 #include <boost/multi_index/detail/access_specifier.hpp>
  32 #include <boost/multi_index/detail/adl_swap.hpp>
  33 #include <boost/multi_index/detail/base_type.hpp>
  34 #include <boost/multi_index/detail/converter.hpp>
  35 #include <boost/multi_index/detail/header_holder.hpp>
  36 #include <boost/multi_index/detail/has_tag.hpp>
  37 #include <boost/multi_index/detail/no_duplicate_tags.hpp>
  38 #include <boost/multi_index/detail/prevent_eti.hpp>
  39 #include <boost/multi_index/detail/safe_mode.hpp>
  40 #include <boost/multi_index/detail/scope_guard.hpp>
  41 #include <boost/static_assert.hpp>
  42 #include <boost/type_traits/is_same.hpp>
  43 #include <boost/utility/base_from_member.hpp>
  44
  45 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
  46 #include <boost/multi_index/detail/archive_constructed.hpp>
  47 #include <boost/multi_index/detail/serialization_version.hpp>
  48 #include <boost/serialization/collection_size_type.hpp>
  49 #include <boost/serialization/nvp.hpp>
  50 #include <boost/serialization/split_member.hpp>
  51 #include <boost/serialization/version.hpp>
  52 #include <boost/throw_exception.hpp>
  53 #endif
  54
  55 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
  56 #include <boost/multi_index/detail/invariant_assert.hpp>
  57 #define BOOST_MULTI_INDEX_CHECK_INVARIANT                                    \
  58   detail::scope_guard BOOST_JOIN(check_invariant_,__LINE__)=                 \
  59     detail::make_obj_guard(*this,&multi_index_container::check_invariant_);  \
  60   BOOST_JOIN(check_invariant_,__LINE__).touch();
  61 #else
  62 #define BOOST_MULTI_INDEX_CHECK_INVARIANT
  63 #endif
  64
  65 namespace boost{
  66
  67 namespace multi_index{
  68
  69 template<typename Value,typename IndexSpecifierList,typename Allocator>
  70 class multi_index_container:
  71   private ::boost::base_from_member<
  72     typename boost::detail::allocator::rebind_to<
  73       Allocator,
  74       typename detail::multi_index_node_type<
  75         Value,IndexSpecifierList,Allocator>::type
  76     >::type>,
  77   BOOST_MULTI_INDEX_PRIVATE_IF_MEMBER_TEMPLATE_FRIENDS detail::header_holder<
  78     typename detail::prevent_eti<
  79       Allocator,
  80       typename boost::detail::allocator::rebind_to<
  81         Allocator,
  82         typename detail::multi_index_node_type<
  83           Value,IndexSpecifierList,Allocator>::type
  84       >::type
  85     >::type::pointer,
  86     multi_index_container<Value,IndexSpecifierList,Allocator> >,
  87   public detail::multi_index_base_type<
  88     Value,IndexSpecifierList,Allocator>::type
  89 {
  90 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
  91     BOOST_WORKAROUND(__MWERKS__,<=0x3003)
  92 /* The "ISO C++ Template Parser" option in CW8.3 has a problem with the
  93  * lifetime of const references bound to temporaries --precisely what
  94  * scopeguards are.
  95  */
  96
  97 #pragma parse_mfunc_templ off
  98 #endif
  99
 100 private:
 101 #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
 102   template <typename,typename,typename> friend class  detail::index_base;
 103   template <typename,typename>          friend struct detail::header_holder;
 104   template <typename,typename>          friend struct detail::converter;
 105 #endif
 106
 107   typedef typename detail::multi_index_base_type<
 108       Value,IndexSpecifierList,Allocator>::type   super;
 109   typedef typename
 110   boost::detail::allocator::rebind_to<
 111       Allocator,
 112       typename super::node_type
 113   >::type                                         node_allocator;
 114   typedef ::boost::base_from_member<
 115     node_allocator>                               bfm_allocator;
 116   typedef detail::header_holder<
 117     typename detail::prevent_eti<
 118       Allocator,
 119       node_allocator
 120     >::type::pointer,
 121     multi_index_container>                        bfm_header;
 122
 123 #if BOOST_WORKAROUND(BOOST_MSVC,<1300)
 124   /* see definition of index_type_list below */
 125   typedef typename super::index_type_list         super_index_type_list;
 126 #endif
 127
 128 public:
 129   /* All types are inherited from super, a few are explicitly
 130    * brought forward here to save us some typename's.
 131    */
 132
 133   typedef typename super::ctor_args_list          ctor_args_list;
 134   typedef IndexSpecifierList                      index_specifier_type_list;
 135
 136 #if BOOST_WORKAROUND(BOOST_MSVC,<1300)
 137   /* MSVC++ 6.0 chokes on moderately long index lists (around 6 indices
 138    * or more), with errors ranging from corrupt exes to duplicate
 139    * comdats. The following type hiding hack alleviates this condition;
 140    * best results combined with type hiding of the indexed_by construct
 141    * itself, as explained in the "Compiler specifics" section of
 142    * the documentation.
 143    */
 144
 145   struct index_type_list:super_index_type_list
 146   {
 147     typedef index_type_list                      type;
 148     typedef typename super_index_type_list::back back;
 149     typedef mpl::v_iter<type,0>                  begin;
 150     typedef mpl::v_iter<
 151       type,
 152       mpl::size<super_index_type_list>::value>   end;
 153   };
 154 #else
 155   typedef typename super::index_type_list          index_type_list;
 156 #endif
 157
 158   typedef typename super::iterator_type_list       iterator_type_list;
 159   typedef typename super::const_iterator_type_list const_iterator_type_list;
 160   typedef typename super::value_type               value_type;
 161   typedef typename super::final_allocator_type     allocator_type;
 162   typedef typename super::iterator                 iterator;
 163   typedef typename super::const_iterator           const_iterator;
 164
 165   BOOST_STATIC_ASSERT(
 166     detail::no_duplicate_tags_in_index_list<index_type_list>::value);
 167
 168   /* global project() needs to see this publicly */
 169
 170   typedef typename super::node_type node_type;
 171
 172   /* construct/copy/destroy */
 173
 174   explicit multi_index_container(
 175
 176 #if BOOST_WORKAROUND(__IBMCPP__,<=600)
 177     /* VisualAge seems to have an ETI issue with the default values
 178      * for arguments args_list and al.
 179      */
 180
 181     const ctor_args_list& args_list=
 182       typename mpl::identity<multi_index_container>::type::
 183         ctor_args_list(),
 184     const allocator_type& al=
 185       typename mpl::identity<multi_index_container>::type::
 186         allocator_type()):
 187 #else
 188     const ctor_args_list& args_list=ctor_args_list(),
 189     const allocator_type& al=allocator_type()):
 190 #endif
 191
 192     bfm_allocator(al),
 193     super(args_list,bfm_allocator::member),
 194     node_count(0)
 195   {
 196     BOOST_MULTI_INDEX_CHECK_INVARIANT;
 197   }
 198
 199   explicit multi_index_container(const allocator_type& al):
 200     bfm_allocator(al),
 201     super(ctor_args_list(),bfm_allocator::member),
 202     node_count(0)
 203   {
 204     BOOST_MULTI_INDEX_CHECK_INVARIANT;
 205   }
 206
 207   template<typename InputIterator>
 208   multi_index_container(
 209     InputIterator first,InputIterator last,
 210
 211 #if BOOST_WORKAROUND(__IBMCPP__,<=600)
 212     /* VisualAge seems to have an ETI issue with the default values
 213      * for arguments args_list and al.
 214      */
 215
 216     const ctor_args_list& args_list=
 217       typename mpl::identity<multi_index_container>::type::
 218         ctor_args_list(),
 219     const allocator_type& al=
 220       typename mpl::identity<multi_index_container>::type::
 221         allocator_type()):
 222 #else
 223     const ctor_args_list& args_list=ctor_args_list(),
 224     const allocator_type& al=allocator_type()):
 225 #endif
 226
 227     bfm_allocator(al),
 228     super(args_list,bfm_allocator::member),
 229     node_count(0)
 230   {
 231     BOOST_MULTI_INDEX_CHECK_INVARIANT;
 232     BOOST_TRY{
 233       iterator hint=super::end();
 234       for(;first!=last;++first){
 235         hint=super::make_iterator(insert_(*first,hint.get_node()).first);
 236       }
 237     }
 238     BOOST_CATCH(...){
 239       clear_();
 240       BOOST_RETHROW;
 241     }
 242     BOOST_CATCH_END
 243   }
 244
 245   multi_index_container(
 246     const multi_index_container<Value,IndexSpecifierList,Allocator>& x):
 247     bfm_allocator(x.bfm_allocator::member),
 248     bfm_header(),
 249     super(x),
 250     node_count(0)
 251   {
 252     copy_map_type map(bfm_allocator::member,x.size(),x.header(),header());
 253     for(const_iterator it=x.begin(),it_end=x.end();it!=it_end;++it){
 254       map.clone(it.get_node());
 255     }
 256     super::copy_(x,map);
 257     map.release();
 258     node_count=x.size();
 259
 260     /* Not until this point are the indices required to be consistent,
 261      * hence the position of the invariant checker.
 262      */
 263
 264     BOOST_MULTI_INDEX_CHECK_INVARIANT;
 265   }
 266
 267   ~multi_index_container()
 268   {
 269     delete_all_nodes_();
 270   }
 271
 272   multi_index_container<Value,IndexSpecifierList,Allocator>& operator=(
 273     multi_index_container<Value,IndexSpecifierList,Allocator> x)
 274   {
 275     BOOST_MULTI_INDEX_CHECK_INVARIANT;
 276     this->swap(x);
 277     return *this;
 278   }
 279
 280   allocator_type get_allocator()const
 281   {
 282     return allocator_type(bfm_allocator::member);
 283   }
 284
 285   /* retrieval of indices by number */
 286
 287 #if !defined(BOOST_NO_MEMBER_TEMPLATES)
 288   template<int N>
 289   struct nth_index
 290   {
 291     BOOST_STATIC_ASSERT(N>=0&&N<mpl::size<index_type_list>::type::value);
 292     typedef typename mpl::at_c<index_type_list,N>::type type;
 293   };
 294
 295   template<int N>
 296   typename nth_index<N>::type& get(BOOST_EXPLICIT_TEMPLATE_NON_TYPE(int,N))
 297   {
 298     BOOST_STATIC_ASSERT(N>=0&&N<mpl::size<index_type_list>::type::value);
 299     return *this;
 300   }
 301
 302   template<int N>
 303   const typename nth_index<N>::type& get(
 304     BOOST_EXPLICIT_TEMPLATE_NON_TYPE(int,N))const
 305   {
 306     BOOST_STATIC_ASSERT(N>=0&&N<mpl::size<index_type_list>::type::value);
 307     return *this;
 308   }
 309 #endif
 310
 311   /* retrieval of indices by tag */
 312
 313 #if !defined(BOOST_NO_MEMBER_TEMPLATES)
 314   template<typename Tag>
 315   struct index
 316   {
 317     typedef typename mpl::find_if<
 318       index_type_list,
 319       detail::has_tag<Tag>
 320     >::type                                    iter;
 321
 322     BOOST_STATIC_CONSTANT(
 323       bool,index_found=!(is_same<iter,typename mpl::end<index_type_list>::type >::value));
 324     BOOST_STATIC_ASSERT(index_found);
 325
 326     typedef typename mpl::deref<iter>::type    type;
 327   };
 328
 329   template<typename Tag>
 330   typename index<Tag>::type& get(BOOST_EXPLICIT_TEMPLATE_TYPE(Tag))
 331   {
 332     return *this;
 333   }
 334
 335   template<typename Tag>
 336   const typename index<Tag>::type& get(
 337     BOOST_EXPLICIT_TEMPLATE_TYPE(Tag))const
 338   {
 339     return *this;
 340   }
 341 #endif
 342
 343   /* projection of iterators by number */
 344
 345 #if !defined(BOOST_NO_MEMBER_TEMPLATES)
 346   template<int N>
 347   struct nth_index_iterator
 348   {
 349     typedef typename nth_index<N>::type::iterator type;
 350   };
 351
 352   template<int N>
 353   struct nth_index_const_iterator
 354   {
 355     typedef typename nth_index<N>::type::const_iterator type;
 356   };
 357
 358   template<int N,typename IteratorType>
 359   typename nth_index_iterator<N>::type project(
 360     IteratorType it
 361     BOOST_APPEND_EXPLICIT_TEMPLATE_NON_TYPE(int,N))
 362   {
 363     typedef typename nth_index<N>::type index;
 364
 365 #if !defined(__SUNPRO_CC)||!(__SUNPRO_CC<0x580) /* fails in Sun C++ 5.7 */
 366     BOOST_STATIC_ASSERT(
 367       (mpl::contains<iterator_type_list,IteratorType>::value));
 368 #endif
 369
 370     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it);
 371     BOOST_MULTI_INDEX_CHECK_IS_OWNER(
 372       it,static_cast<typename IteratorType::container_type&>(*this));
 373
 374     return index::make_iterator(static_cast<node_type*>(it.get_node()));
 375   }
 376
 377   template<int N,typename IteratorType>
 378   typename nth_index_const_iterator<N>::type project(
 379     IteratorType it
 380     BOOST_APPEND_EXPLICIT_TEMPLATE_NON_TYPE(int,N))const
 381   {
 382     typedef typename nth_index<N>::type index;
 383
 384 #if !defined(__SUNPRO_CC)||!(__SUNPRO_CC<0x580) /* fails in Sun C++ 5.7 */
 385     BOOST_STATIC_ASSERT((
 386       mpl::contains<iterator_type_list,IteratorType>::value||
 387       mpl::contains<const_iterator_type_list,IteratorType>::value));
 388 #endif
 389
 390     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it);
 391     BOOST_MULTI_INDEX_CHECK_IS_OWNER(
 392       it,static_cast<const typename IteratorType::container_type&>(*this));
 393     return index::make_iterator(static_cast<node_type*>(it.get_node()));
 394   }
 395 #endif
 396
 397   /* projection of iterators by tag */
 398
 399 #if !defined(BOOST_NO_MEMBER_TEMPLATES)
 400   template<typename Tag>
 401   struct index_iterator
 402   {
 403     typedef typename index<Tag>::type::iterator type;
 404   };
 405
 406   template<typename Tag>
 407   struct index_const_iterator
 408   {
 409     typedef typename index<Tag>::type::const_iterator type;
 410   };
 411
 412   template<typename Tag,typename IteratorType>
 413   typename index_iterator<Tag>::type project(
 414     IteratorType it
 415     BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(Tag))
 416   {
 417     typedef typename index<Tag>::type index;
 418
 419 #if !defined(__SUNPRO_CC)||!(__SUNPRO_CC<0x580) /* fails in Sun C++ 5.7 */
 420     BOOST_STATIC_ASSERT(
 421       (mpl::contains<iterator_type_list,IteratorType>::value));
 422 #endif
 423
 424     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it);
 425     BOOST_MULTI_INDEX_CHECK_IS_OWNER(
 426       it,static_cast<typename IteratorType::container_type&>(*this));
 427     return index::make_iterator(static_cast<node_type*>(it.get_node()));
 428   }
 429
 430   template<typename Tag,typename IteratorType>
 431   typename index_const_iterator<Tag>::type project(
 432     IteratorType it
 433     BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(Tag))const
 434   {
 435     typedef typename index<Tag>::type index;
 436
 437 #if !defined(__SUNPRO_CC)||!(__SUNPRO_CC<0x580) /* fails in Sun C++ 5.7 */
 438     BOOST_STATIC_ASSERT((
 439       mpl::contains<iterator_type_list,IteratorType>::value||
 440       mpl::contains<const_iterator_type_list,IteratorType>::value));
 441 #endif
 442
 443     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it);
 444     BOOST_MULTI_INDEX_CHECK_IS_OWNER(
 445       it,static_cast<const typename IteratorType::container_type&>(*this));
 446     return index::make_iterator(static_cast<node_type*>(it.get_node()));
 447   }
 448 #endif
 449
 450 BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS:
 451   typedef typename super::copy_map_type copy_map_type;
 452
 453   node_type* header()const
 454   {
 455     return &*bfm_header::member;
 456   }
 457
 458   node_type* allocate_node()
 459   {
 460     return &*bfm_allocator::member.allocate(1);
 461   }
 462
 463   void deallocate_node(node_type* x)
 464   {
 465     typedef typename node_allocator::pointer node_pointer;
 466     bfm_allocator::member.deallocate(static_cast<node_pointer>(x),1);
 467   }
 468
 469   bool empty_()const
 470   {
 471     return node_count==0;
 472   }
 473
 474   std::size_t size_()const
 475   {
 476     return node_count;
 477   }
 478
 479   std::size_t max_size_()const
 480   {
 481     return static_cast<std::size_t >(-1);
 482   }
 483
 484   std::pair<node_type*,bool> insert_(const Value& v)
 485   {
 486     node_type* x=allocate_node();
 487     BOOST_TRY{
 488       node_type* res=super::insert_(v,x);
 489       if(res==x){
 490         ++node_count;
 491         return std::pair<node_type*,bool>(res,true);
 492       }
 493       else{
 494         deallocate_node(x);
 495         return std::pair<node_type*,bool>(res,false);
 496       }
 497     }
 498     BOOST_CATCH(...){
 499       deallocate_node(x);
 500       BOOST_RETHROW;
 501     }
 502     BOOST_CATCH_END
 503   }
 504
 505   std::pair<node_type*,bool> insert_(const Value& v,node_type* position)
 506   {
 507     node_type* x=allocate_node();
 508     BOOST_TRY{
 509       node_type* res=super::insert_(v,position,x);
 510       if(res==x){
 511         ++node_count;
 512         return std::pair<node_type*,bool>(res,true);
 513       }
 514       else{
 515         deallocate_node(x);
 516         return std::pair<node_type*,bool>(res,false);
 517       }
 518     }
 519     BOOST_CATCH(...){
 520       deallocate_node(x);
 521       BOOST_RETHROW;
 522     }
 523     BOOST_CATCH_END
 524   }
 525
 526   void erase_(node_type* x)
 527   {
 528     --node_count;
 529     super::erase_(x);
 530     deallocate_node(x);
 531   }
 532
 533   void delete_node_(node_type* x)
 534   {
 535     super::delete_node_(x);
 536     deallocate_node(x);
 537   }
 538
 539   void delete_all_nodes_()
 540   {
 541     super::delete_all_nodes_();
 542   }
 543
 544   void clear_()
 545   {
 546     delete_all_nodes_();
 547     super::clear_();
 548     node_count=0;
 549   }
 550
 551   void swap_(multi_index_container<Value,IndexSpecifierList,Allocator>& x)
 552   {
 553     if(bfm_allocator::member!=x.bfm_allocator::member){
 554       detail::adl_swap(bfm_allocator::member,x.bfm_allocator::member);
 555     }
 556     std::swap(bfm_header::member,x.bfm_header::member);
 557     super::swap_(x);
 558     std::swap(node_count,x.node_count);
 559   }
 560
 561   bool replace_(const Value& k,node_type* x)
 562   {
 563     return super::replace_(k,x);
 564   }
 565
 566   template<typename Modifier>
 567   bool modify_(Modifier& mod,node_type* x)
 568   {
 569     mod(const_cast<value_type&>(x->value()));
 570
 571     BOOST_TRY{
 572       if(!super::modify_(x)){
 573         deallocate_node(x);
 574         --node_count;
 575         return false;
 576       }
 577       else return true;
 578     }
 579     BOOST_CATCH(...){
 580       deallocate_node(x);
 581       --node_count;
 582       BOOST_RETHROW;
 583     }
 584     BOOST_CATCH_END
 585   }
 586
 587   template<typename Modifier,typename Rollback>
 588   bool modify_(Modifier& mod,Rollback& back,node_type* x)
 589   {
 590     mod(const_cast<value_type&>(x->value()));
 591
 592     bool b;
 593     BOOST_TRY{
 594       b=super::modify_rollback_(x);
 595     }
 596     BOOST_CATCH(...){
 597       BOOST_TRY{
 598         back(const_cast<value_type&>(x->value()));
 599         BOOST_RETHROW;
 600       }
 601       BOOST_CATCH(...){
 602         this->erase_(x);
 603         BOOST_RETHROW;
 604       }
 605       BOOST_CATCH_END
 606     }
 607     BOOST_CATCH_END
 608
 609     BOOST_TRY{
 610       if(!b){
 611         back(const_cast<value_type&>(x->value()));
 612         return false;
 613       }
 614       else return true;
 615     }
 616     BOOST_CATCH(...){
 617       this->erase_(x);
 618       BOOST_RETHROW;
 619     }
 620     BOOST_CATCH_END
 621   }
 622
 623 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
 624   /* serialization */
 625
 626   friend class boost::serialization::access;
 627
 628   BOOST_SERIALIZATION_SPLIT_MEMBER()
 629
 630   typedef typename super::index_saver_type        index_saver_type;
 631   typedef typename super::index_loader_type       index_loader_type;
 632
 633   template<class Archive>
 634   void save(Archive& ar,const unsigned int version)const
 635   {
 636
 637 #if !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION)
 638     const serialization::collection_size_type       s(size_());
 639     const detail::serialization_version<value_type> value_version;
 640     ar<<serialization::make_nvp("count",s);
 641     ar<<serialization::make_nvp("value_version",value_version);
 642 #else
 643     const std::size_t  s=size_();
 644     const unsigned int value_version=0;
 645     ar<<serialization::make_nvp("count",s);
 646 #endif
 647
 648     index_saver_type sm(bfm_allocator::member,s);
 649
 650     for(iterator it=super::begin(),it_end=super::end();it!=it_end;++it){
 651       serialization::save_construct_data_adl(ar,&*it,value_version);
 652       ar<<serialization::make_nvp("item",*it);
 653       sm.add(it.get_node(),ar,version);
 654     }
 655     sm.add_track(header(),ar,version);
 656
 657     super::save_(ar,version,sm);
 658   }
 659
 660   template<class Archive>
 661   void load(Archive& ar,const unsigned int version)
 662   {
 663     BOOST_MULTI_INDEX_CHECK_INVARIANT;
 664
 665     clear_();
 666
 667 #if !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION)
 668     serialization::collection_size_type       s;
 669     detail::serialization_version<value_type> value_version;
 670     if(version<1){
 671       std::size_t sz;
 672       ar>>serialization::make_nvp("count",sz);
 673       s=sz;
 674     }
 675     else{
 676       ar>>serialization::make_nvp("count",s);
 677     }
 678     if(version<2){
 679       value_version=0;
 680     }
 681     else{
 682       ar>>serialization::make_nvp("value_version",value_version);
 683     }
 684 #else
 685     std::size_t  s;
 686     unsigned int value_version=0;
 687     ar>>serialization::make_nvp("count",s);
 688 #endif
 689
 690     index_loader_type lm(bfm_allocator::member,s);
 691
 692     for(std::size_t n=0;n<s;++n){
 693       detail::archive_constructed<Value> value("item",ar,value_version);
 694       std::pair<node_type*,bool> p=insert_(
 695         value.get(),super::end().get_node());
 696       if(!p.second)throw_exception(
 697         archive::archive_exception(
 698           archive::archive_exception::other_exception));
 699       ar.reset_object_address(&p.first->value(),&value.get());
 700       lm.add(p.first,ar,version);
 701     }
 702     lm.add_track(header(),ar,version);
 703
 704     super::load_(ar,version,lm);
 705   }
 706 #endif
 707
 708 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
 709   /* invariant stuff */
 710
 711   bool invariant_()const
 712   {
 713     return super::invariant_();
 714   }
 715
 716   void check_invariant_()const
 717   {
 718     BOOST_MULTI_INDEX_INVARIANT_ASSERT(invariant_());
 719   }
 720 #endif
 721
 722 private:
 723   std::size_t node_count;
 724
 725 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
 726     BOOST_WORKAROUND(__MWERKS__,<=0x3003)
 727 #pragma parse_mfunc_templ reset
 728 #endif
 729 };
 730
 731 /* retrieval of indices by number */
 732
 733 template<typename MultiIndexContainer,int N>
 734 struct nth_index
 735 {
 736   BOOST_STATIC_CONSTANT(
 737     int,
 738     M=mpl::size<typename MultiIndexContainer::index_type_list>::type::value);
 739   BOOST_STATIC_ASSERT(N>=0&&N<M);
 740   typedef typename mpl::at_c<
 741     typename MultiIndexContainer::index_type_list,N>::type type;
 742 };
 743
 744 template<int N,typename Value,typename IndexSpecifierList,typename Allocator>
 745 typename nth_index<
 746   multi_index_container<Value,IndexSpecifierList,Allocator>,N>::type&
 747 get(
 748   multi_index_container<Value,IndexSpecifierList,Allocator>& m
 749   BOOST_APPEND_EXPLICIT_TEMPLATE_NON_TYPE(int,N))
 750 {
 751   typedef multi_index_container<
 752     Value,IndexSpecifierList,Allocator>    multi_index_type;
 753   typedef typename nth_index<
 754     multi_index_container<
 755       Value,IndexSpecifierList,Allocator>,
 756     N
 757   >::type                                  index;
 758
 759   BOOST_STATIC_ASSERT(N>=0&&
 760     N<
 761     mpl::size<
 762       BOOST_DEDUCED_TYPENAME multi_index_type::index_type_list
 763     >::type::value);
 764
 765   return detail::converter<multi_index_type,index>::index(m);
 766 }
 767
 768 template<int N,typename Value,typename IndexSpecifierList,typename Allocator>
 769 const typename nth_index<
 770   multi_index_container<Value,IndexSpecifierList,Allocator>,N>::type&
 771 get(
 772   const multi_index_container<Value,IndexSpecifierList,Allocator>& m
 773   BOOST_APPEND_EXPLICIT_TEMPLATE_NON_TYPE(int,N))
 774 {
 775   typedef multi_index_container<
 776     Value,IndexSpecifierList,Allocator>    multi_index_type;
 777   typedef typename nth_index<
 778     multi_index_container<
 779       Value,IndexSpecifierList,Allocator>,
 780     N
 781   >::type                                  index;
 782
 783   BOOST_STATIC_ASSERT(N>=0&&
 784     N<
 785     mpl::size<
 786       BOOST_DEDUCED_TYPENAME multi_index_type::index_type_list
 787     >::type::value);
 788
 789   return detail::converter<multi_index_type,index>::index(m);
 790 }
 791
 792 /* retrieval of indices by tag */
 793
 794 template<typename MultiIndexContainer,typename Tag>
 795 struct index
 796 {
 797   typedef typename MultiIndexContainer::index_type_list index_type_list;
 798
 799   typedef typename mpl::find_if<
 800     index_type_list,
 801     detail::has_tag<Tag>
 802   >::type                                      iter;
 803
 804   BOOST_STATIC_CONSTANT(
 805     bool,index_found=!(is_same<iter,typename mpl::end<index_type_list>::type >::value));
 806   BOOST_STATIC_ASSERT(index_found);
 807
 808   typedef typename mpl::deref<iter>::type       type;
 809 };
 810
 811 template<
 812   typename Tag,typename Value,typename IndexSpecifierList,typename Allocator
 813 >
 814 typename ::boost::multi_index::index<
 815   multi_index_container<Value,IndexSpecifierList,Allocator>,Tag>::type&
 816 get(
 817   multi_index_container<Value,IndexSpecifierList,Allocator>& m
 818   BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(Tag))
 819 {
 820   typedef multi_index_container<
 821     Value,IndexSpecifierList,Allocator>         multi_index_type;
 822   typedef typename ::boost::multi_index::index<
 823     multi_index_container<
 824       Value,IndexSpecifierList,Allocator>,
 825     Tag
 826   >::type                                       index;
 827
 828   return detail::converter<multi_index_type,index>::index(m);
 829 }
 830
 831 template<
 832   typename Tag,typename Value,typename IndexSpecifierList,typename Allocator
 833 >
 834 const typename ::boost::multi_index::index<
 835   multi_index_container<Value,IndexSpecifierList,Allocator>,Tag>::type&
 836 get(
 837   const multi_index_container<Value,IndexSpecifierList,Allocator>& m
 838   BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(Tag))
 839 {
 840   typedef multi_index_container<
 841     Value,IndexSpecifierList,Allocator>         multi_index_type;
 842   typedef typename ::boost::multi_index::index<
 843     multi_index_container<
 844       Value,IndexSpecifierList,Allocator>,
 845     Tag
 846   >::type                                       index;
 847
 848   return detail::converter<multi_index_type,index>::index(m);
 849 }
 850
 851 /* projection of iterators by number */
 852
 853 template<typename MultiIndexContainer,int N>
 854 struct nth_index_iterator
 855 {
 856   typedef typename detail::prevent_eti<
 857     nth_index<MultiIndexContainer,N>,
 858     typename nth_index<MultiIndexContainer,N>::type>::type::iterator type;
 859 };
 860
 861 template<typename MultiIndexContainer,int N>
 862 struct nth_index_const_iterator
 863 {
 864   typedef typename detail::prevent_eti<
 865     nth_index<MultiIndexContainer,N>,
 866     typename nth_index<MultiIndexContainer,N>::type
 867   >::type::const_iterator type;
 868 };
 869
 870 template<
 871   int N,typename IteratorType,
 872   typename Value,typename IndexSpecifierList,typename Allocator>
 873 typename nth_index_iterator<
 874   multi_index_container<Value,IndexSpecifierList,Allocator>,N>::type
 875 project(
 876   multi_index_container<Value,IndexSpecifierList,Allocator>& m,
 877   IteratorType it
 878   BOOST_APPEND_EXPLICIT_TEMPLATE_NON_TYPE(int,N))
 879 {
 880   typedef multi_index_container<
 881     Value,IndexSpecifierList,Allocator>                multi_index_type;
 882   typedef typename nth_index<multi_index_type,N>::type index;
 883
 884 #if (!defined(BOOST_MSVC)||!(BOOST_MSVC<1310))&&  /* MSVC++ 6.0/7.0 fails */\
 885     (!defined(__SUNPRO_CC)||!(__SUNPRO_CC<0x580)) /* as does Sun C++ 5.7  */
 886   BOOST_STATIC_ASSERT((
 887     mpl::contains<
 888       BOOST_DEDUCED_TYPENAME multi_index_type::iterator_type_list,
 889       IteratorType>::value));
 890 #endif
 891
 892   BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it);
 893
 894 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 895   typedef detail::converter<
 896     multi_index_type,
 897     BOOST_DEDUCED_TYPENAME IteratorType::container_type> converter;
 898   BOOST_MULTI_INDEX_CHECK_IS_OWNER(it,converter::index(m));
 899 #endif
 900
 901   return detail::converter<multi_index_type,index>::iterator(
 902     m,static_cast<typename multi_index_type::node_type*>(it.get_node()));
 903 }
 904
 905 template<
 906   int N,typename IteratorType,
 907   typename Value,typename IndexSpecifierList,typename Allocator>
 908 typename nth_index_const_iterator<
 909   multi_index_container<Value,IndexSpecifierList,Allocator>,N>::type
 910 project(
 911   const multi_index_container<Value,IndexSpecifierList,Allocator>& m,
 912   IteratorType it
 913   BOOST_APPEND_EXPLICIT_TEMPLATE_NON_TYPE(int,N))
 914 {
 915   typedef multi_index_container<
 916     Value,IndexSpecifierList,Allocator>                multi_index_type;
 917   typedef typename nth_index<multi_index_type,N>::type index;
 918
 919 #if (!defined(BOOST_MSVC)||!(BOOST_MSVC<1310))&&  /* MSVC++ 6.0/7.0 fails */\
 920     (!defined(__SUNPRO_CC)||!(__SUNPRO_CC<0x580)) /* as does Sun C++ 5.7  */
 921   BOOST_STATIC_ASSERT((
 922     mpl::contains<
 923       BOOST_DEDUCED_TYPENAME multi_index_type::iterator_type_list,
 924       IteratorType>::value||
 925     mpl::contains<
 926       BOOST_DEDUCED_TYPENAME multi_index_type::const_iterator_type_list,
 927       IteratorType>::value));
 928 #endif
 929
 930   BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it);
 931
 932 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 933   typedef detail::converter<
 934     multi_index_type,
 935     BOOST_DEDUCED_TYPENAME IteratorType::container_type> converter;
 936   BOOST_MULTI_INDEX_CHECK_IS_OWNER(it,converter::index(m));
 937 #endif
 938
 939   return detail::converter<multi_index_type,index>::const_iterator(
 940     m,static_cast<typename multi_index_type::node_type*>(it.get_node()));
 941 }
 942
 943 /* projection of iterators by tag */
 944
 945 template<typename MultiIndexContainer,typename Tag>
 946 struct index_iterator
 947 {
 948   typedef typename ::boost::multi_index::index<
 949     MultiIndexContainer,Tag>::type::iterator    type;
 950 };
 951
 952 template<typename MultiIndexContainer,typename Tag>
 953 struct index_const_iterator
 954 {
 955   typedef typename ::boost::multi_index::index<
 956     MultiIndexContainer,Tag>::type::const_iterator type;
 957 };
 958
 959 template<
 960   typename Tag,typename IteratorType,
 961   typename Value,typename IndexSpecifierList,typename Allocator>
 962 typename index_iterator<
 963   multi_index_container<Value,IndexSpecifierList,Allocator>,Tag>::type
 964 project(
 965   multi_index_container<Value,IndexSpecifierList,Allocator>& m,
 966   IteratorType it
 967   BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(Tag))
 968 {
 969   typedef multi_index_container<
 970     Value,IndexSpecifierList,Allocator>         multi_index_type;
 971   typedef typename ::boost::multi_index::index<
 972     multi_index_type,Tag>::type                 index;
 973
 974 #if (!defined(BOOST_MSVC)||!(BOOST_MSVC<1310))&&  /* MSVC++ 6.0/7.0 fails */\
 975     (!defined(__SUNPRO_CC)||!(__SUNPRO_CC<0x580)) /* as does Sun C++ 5.7  */
 976   BOOST_STATIC_ASSERT((
 977     mpl::contains<
 978       BOOST_DEDUCED_TYPENAME multi_index_type::iterator_type_list,
 979       IteratorType>::value));
 980 #endif
 981
 982   BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it);
 983
 984 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 985   typedef detail::converter<
 986     multi_index_type,
 987     BOOST_DEDUCED_TYPENAME IteratorType::container_type> converter;
 988   BOOST_MULTI_INDEX_CHECK_IS_OWNER(it,converter::index(m));
 989 #endif
 990
 991   return detail::converter<multi_index_type,index>::iterator(
 992     m,static_cast<typename multi_index_type::node_type*>(it.get_node()));
 993 }
 994
 995 template<
 996   typename Tag,typename IteratorType,
 997   typename Value,typename IndexSpecifierList,typename Allocator>
 998 typename index_const_iterator<
 999   multi_index_container<Value,IndexSpecifierList,Allocator>,Tag>::type
1000 project(
1001   const multi_index_container<Value,IndexSpecifierList,Allocator>& m,
1002   IteratorType it
1003   BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(Tag))
1004 {
1005   typedef multi_index_container<
1006     Value,IndexSpecifierList,Allocator>         multi_index_type;
1007   typedef typename ::boost::multi_index::index<
1008     multi_index_type,Tag>::type                 index;
1009
1010 #if (!defined(BOOST_MSVC)||!(BOOST_MSVC<1310))&&  /* MSVC++ 6.0/7.0 fails */\
1011     (!defined(__SUNPRO_CC)||!(__SUNPRO_CC<0x580)) /* as does Sun C++ 5.7  */
1012   BOOST_STATIC_ASSERT((
1013     mpl::contains<
1014       BOOST_DEDUCED_TYPENAME multi_index_type::iterator_type_list,
1015       IteratorType>::value||
1016     mpl::contains<
1017       BOOST_DEDUCED_TYPENAME multi_index_type::const_iterator_type_list,
1018       IteratorType>::value));
1019 #endif
1020
1021   BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it);
1022
1023 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1024   typedef detail::converter<
1025     multi_index_type,
1026     BOOST_DEDUCED_TYPENAME IteratorType::container_type> converter;
1027   BOOST_MULTI_INDEX_CHECK_IS_OWNER(it,converter::index(m));
1028 #endif
1029
1030   return detail::converter<multi_index_type,index>::const_iterator(
1031     m,static_cast<typename multi_index_type::node_type*>(it.get_node()));
1032 }
1033
1034 /* Comparison. Simple forward to first index. */
1035
1036 template<
1037   typename Value1,typename IndexSpecifierList1,typename Allocator1,
1038   typename Value2,typename IndexSpecifierList2,typename Allocator2
1039 >
1040 bool operator==(
1041   const multi_index_container<Value1,IndexSpecifierList1,Allocator1>& x,
1042   const multi_index_container<Value2,IndexSpecifierList2,Allocator2>& y)
1043 {
1044   return get<0>(x)==get<0>(y);
1045 }
1046
1047 template<
1048   typename Value1,typename IndexSpecifierList1,typename Allocator1,
1049   typename Value2,typename IndexSpecifierList2,typename Allocator2
1050 >
1051 bool operator<(
1052   const multi_index_container<Value1,IndexSpecifierList1,Allocator1>& x,
1053   const multi_index_container<Value2,IndexSpecifierList2,Allocator2>& y)
1054 {
1055   return get<0>(x)<get<0>(y);
1056 }
1057
1058 template<
1059   typename Value1,typename IndexSpecifierList1,typename Allocator1,
1060   typename Value2,typename IndexSpecifierList2,typename Allocator2
1061 >
1062 bool operator!=(
1063   const multi_index_container<Value1,IndexSpecifierList1,Allocator1>& x,
1064   const multi_index_container<Value2,IndexSpecifierList2,Allocator2>& y)
1065 {
1066   return get<0>(x)!=get<0>(y);
1067 }
1068
1069 template<
1070   typename Value1,typename IndexSpecifierList1,typename Allocator1,
1071   typename Value2,typename IndexSpecifierList2,typename Allocator2
1072 >
1073 bool operator>(
1074   const multi_index_container<Value1,IndexSpecifierList1,Allocator1>& x,
1075   const multi_index_container<Value2,IndexSpecifierList2,Allocator2>& y)
1076 {
1077   return get<0>(x)>get<0>(y);
1078 }
1079
1080 template<
1081   typename Value1,typename IndexSpecifierList1,typename Allocator1,
1082   typename Value2,typename IndexSpecifierList2,typename Allocator2
1083 >
1084 bool operator>=(
1085   const multi_index_container<Value1,IndexSpecifierList1,Allocator1>& x,
1086   const multi_index_container<Value2,IndexSpecifierList2,Allocator2>& y)
1087 {
1088   return get<0>(x)>=get<0>(y);
1089 }
1090
1091 template<
1092   typename Value1,typename IndexSpecifierList1,typename Allocator1,
1093   typename Value2,typename IndexSpecifierList2,typename Allocator2
1094 >
1095 bool operator<=(
1096   const multi_index_container<Value1,IndexSpecifierList1,Allocator1>& x,
1097   const multi_index_container<Value2,IndexSpecifierList2,Allocator2>& y)
1098 {
1099   return get<0>(x)<=get<0>(y);
1100 }
1101
1102 /*  specialized algorithms */
1103
1104 template<typename Value,typename IndexSpecifierList,typename Allocator>
1105 void swap(
1106   multi_index_container<Value,IndexSpecifierList,Allocator>& x,
1107   multi_index_container<Value,IndexSpecifierList,Allocator>& y)
1108 {
1109   x.swap(y);
1110 }
1111
1112 } /* namespace multi_index */
1113
1114 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)&&\
1115     !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION)
1116 /* class version = 1 : we now serialize the size through
1117  * boost::serialization::collection_size_type.
1118  * class version = 2 : proper use of {save|load}_construct_data.
1119  */
1120
1121 namespace serialization {
1122 template<typename Value,typename IndexSpecifierList,typename Allocator>
1123 struct version<
1124   boost::multi_index_container<Value,IndexSpecifierList,Allocator>
1125 >
1126 {
1127   BOOST_STATIC_CONSTANT(int,value=2);
1128 };
1129 } /* namespace serialization */
1130 #endif
1131
1132 /* Associated global functions are promoted to namespace boost, except
1133  * comparison operators and swap, which are meant to be Koenig looked-up.
1134  */
1135
1136 using multi_index::get;
1137 using multi_index::project;
1138
1139 } /* namespace boost */
1140
1141 #undef BOOST_MULTI_INDEX_CHECK_INVARIANT
1142
1143 #endif