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