boost_ext/boost/multi_index_container.hpp

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