boost/multi_index_container.hpp

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