ceph/src/boost/libs/multi_index/include/boost/multi_index/random_access_index.hpp

   1 /* Copyright 2003-2015 Joaquin M Lopez Munoz.
   2  * Distributed under the Boost Software License, Version 1.0.
   3  * (See accompanying file LICENSE_1_0.txt or copy at
   4  * http://www.boost.org/LICENSE_1_0.txt)
   5  *
   6  * See http://www.boost.org/libs/multi_index for library home page.
   7  */
   8
   9 #ifndef BOOST_MULTI_INDEX_RANDOM_ACCESS_INDEX_HPP
  10 #define BOOST_MULTI_INDEX_RANDOM_ACCESS_INDEX_HPP
  11
  12 #if defined(_MSC_VER)
  13 #pragma once
  14 #endif
  15
  16 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
  17 #include <algorithm>
  18 #include <boost/bind.hpp>
  19 #include <boost/call_traits.hpp>
  20 #include <boost/detail/no_exceptions_support.hpp>
  21 #include <boost/detail/workaround.hpp>
  22 #include <boost/foreach_fwd.hpp>
  23 #include <boost/iterator/reverse_iterator.hpp>
  24 #include <boost/move/core.hpp>
  25 #include <boost/move/utility.hpp>
  26 #include <boost/mpl/bool.hpp>
  27 #include <boost/mpl/not.hpp>
  28 #include <boost/mpl/push_front.hpp>
  29 #include <boost/multi_index/detail/access_specifier.hpp>
  30 #include <boost/multi_index/detail/do_not_copy_elements_tag.hpp>
  31 #include <boost/multi_index/detail/index_node_base.hpp>
  32 #include <boost/multi_index/detail/rnd_node_iterator.hpp>
  33 #include <boost/multi_index/detail/rnd_index_node.hpp>
  34 #include <boost/multi_index/detail/rnd_index_ops.hpp>
  35 #include <boost/multi_index/detail/rnd_index_ptr_array.hpp>
  36 #include <boost/multi_index/detail/safe_mode.hpp>
  37 #include <boost/multi_index/detail/scope_guard.hpp>
  38 #include <boost/multi_index/detail/vartempl_support.hpp>
  39 #include <boost/multi_index/random_access_index_fwd.hpp>
  40 #include <boost/throw_exception.hpp>
  41 #include <boost/tuple/tuple.hpp>
  42 #include <boost/type_traits/is_integral.hpp>
  43 #include <cstddef>
  44 #include <functional>
  45 #include <stdexcept>
  46 #include <utility>
  47
  48 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
  49 #include<initializer_list>
  50 #endif
  51
  52 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
  53 #include <boost/multi_index/detail/rnd_index_loader.hpp>
  54 #endif
  55
  56 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
  57 #define BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT_OF(x)                    \
  58   detail::scope_guard BOOST_JOIN(check_invariant_,__LINE__)=                 \
  59     detail::make_obj_guard(x,&random_access_index::check_invariant_);        \
  60   BOOST_JOIN(check_invariant_,__LINE__).touch();
  61 #define BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT                          \
  62   BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT_OF(*this)
  63 #else
  64 #define BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT_OF(x)
  65 #define BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT
  66 #endif
  67
  68 namespace boost{
  69
  70 namespace multi_index{
  71
  72 namespace detail{
  73
  74 /* random_access_index adds a layer of random access indexing
  75  * to a given Super
  76  */
  77
  78 template<typename SuperMeta,typename TagList>
  79 class random_access_index:
  80   BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS SuperMeta::type
  81
  82 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
  83   ,public safe_mode::safe_container<
  84     random_access_index<SuperMeta,TagList> >
  85 #endif
  86
  87 {
  88 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
  89     BOOST_WORKAROUND(__MWERKS__,<=0x3003)
  90 /* The "ISO C++ Template Parser" option in CW8.3 has a problem with the
  91  * lifetime of const references bound to temporaries --precisely what
  92  * scopeguards are.
  93  */
  94
  95 #pragma parse_mfunc_templ off
  96 #endif
  97
  98   typedef typename SuperMeta::type                 super;
  99
 100 protected:
 101   typedef random_access_index_node<
 102     typename super::node_type>                     node_type;
 103
 104 private:
 105   typedef typename node_type::impl_type            node_impl_type;
 106   typedef random_access_index_ptr_array<
 107     typename super::final_allocator_type>          ptr_array;
 108   typedef typename ptr_array::pointer              node_impl_ptr_pointer;
 109
 110 public:
 111   /* types */
 112
 113   typedef typename node_type::value_type           value_type;
 114   typedef tuples::null_type                        ctor_args;
 115   typedef typename super::final_allocator_type     allocator_type;
 116   typedef typename allocator_type::reference       reference;
 117   typedef typename allocator_type::const_reference const_reference;
 118
 119 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 120   typedef safe_mode::safe_iterator<
 121     rnd_node_iterator<node_type>,
 122     random_access_index>                           iterator;
 123 #else
 124   typedef rnd_node_iterator<node_type>             iterator;
 125 #endif
 126
 127   typedef iterator                                 const_iterator;
 128
 129   typedef std::size_t                              size_type;
 130   typedef std::ptrdiff_t                           difference_type;
 131   typedef typename allocator_type::pointer         pointer;
 132   typedef typename allocator_type::const_pointer   const_pointer;
 133   typedef typename
 134     boost::reverse_iterator<iterator>              reverse_iterator;
 135   typedef typename
 136     boost::reverse_iterator<const_iterator>        const_reverse_iterator;
 137   typedef TagList                                  tag_list;
 138
 139 protected:
 140   typedef typename super::final_node_type     final_node_type;
 141   typedef tuples::cons<
 142     ctor_args,
 143     typename super::ctor_args_list>           ctor_args_list;
 144   typedef typename mpl::push_front<
 145     typename super::index_type_list,
 146     random_access_index>::type                index_type_list;
 147   typedef typename mpl::push_front<
 148     typename super::iterator_type_list,
 149     iterator>::type                           iterator_type_list;
 150   typedef typename mpl::push_front<
 151     typename super::const_iterator_type_list,
 152     const_iterator>::type                     const_iterator_type_list;
 153   typedef typename super::copy_map_type       copy_map_type;
 154
 155 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
 156   typedef typename super::index_saver_type    index_saver_type;
 157   typedef typename super::index_loader_type   index_loader_type;
 158 #endif
 159
 160 private:
 161 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 162   typedef safe_mode::safe_container<
 163     random_access_index>                      safe_super;
 164 #endif
 165
 166   typedef typename call_traits<
 167     value_type>::param_type                   value_param_type;
 168
 169   /* Needed to avoid commas in BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL
 170    * expansion.
 171    */
 172
 173   typedef std::pair<iterator,bool>            emplace_return_type;
 174
 175 public:
 176
 177   /* construct/copy/destroy
 178    * Default and copy ctors are in the protected section as indices are
 179    * not supposed to be created on their own. No range ctor either.
 180    */
 181
 182   random_access_index<SuperMeta,TagList>& operator=(
 183     const random_access_index<SuperMeta,TagList>& x)
 184   {
 185     this->final()=x.final();
 186     return *this;
 187   }
 188
 189 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
 190   random_access_index<SuperMeta,TagList>& operator=(
 191     std::initializer_list<value_type> list)
 192   {
 193     this->final()=list;
 194     return *this;
 195   }
 196 #endif
 197
 198   template <class InputIterator>
 199   void assign(InputIterator first,InputIterator last)
 200   {
 201     assign_iter(first,last,mpl::not_<is_integral<InputIterator> >());
 202   }
 203
 204 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
 205   void assign(std::initializer_list<value_type> list)
 206   {
 207     assign(list.begin(),list.end());
 208   }
 209 #endif
 210
 211   void assign(size_type n,value_param_type value)
 212   {
 213     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
 214     clear();
 215     for(size_type i=0;i<n;++i)push_back(value);
 216   }
 217
 218   allocator_type get_allocator()const BOOST_NOEXCEPT
 219   {
 220     return this->final().get_allocator();
 221   }
 222
 223   /* iterators */
 224
 225   iterator begin()BOOST_NOEXCEPT
 226     {return make_iterator(node_type::from_impl(*ptrs.begin()));}
 227   const_iterator begin()const BOOST_NOEXCEPT
 228     {return make_iterator(node_type::from_impl(*ptrs.begin()));}
 229   iterator
 230     end()BOOST_NOEXCEPT{return make_iterator(header());}
 231   const_iterator
 232     end()const BOOST_NOEXCEPT{return make_iterator(header());}
 233   reverse_iterator
 234     rbegin()BOOST_NOEXCEPT{return boost::make_reverse_iterator(end());}
 235   const_reverse_iterator
 236     rbegin()const BOOST_NOEXCEPT{return boost::make_reverse_iterator(end());}
 237   reverse_iterator
 238     rend()BOOST_NOEXCEPT{return boost::make_reverse_iterator(begin());}
 239   const_reverse_iterator
 240     rend()const BOOST_NOEXCEPT{return boost::make_reverse_iterator(begin());}
 241   const_iterator
 242     cbegin()const BOOST_NOEXCEPT{return begin();}
 243   const_iterator
 244     cend()const BOOST_NOEXCEPT{return end();}
 245   const_reverse_iterator
 246     crbegin()const BOOST_NOEXCEPT{return rbegin();}
 247   const_reverse_iterator
 248     crend()const BOOST_NOEXCEPT{return rend();}
 249
 250   iterator iterator_to(const value_type& x)
 251   {
 252     return make_iterator(node_from_value<node_type>(&x));
 253   }
 254
 255   const_iterator iterator_to(const value_type& x)const
 256   {
 257     return make_iterator(node_from_value<node_type>(&x));
 258   }
 259
 260   /* capacity */
 261
 262   bool      empty()const BOOST_NOEXCEPT{return this->final_empty_();}
 263   size_type size()const BOOST_NOEXCEPT{return this->final_size_();}
 264   size_type max_size()const BOOST_NOEXCEPT{return this->final_max_size_();}
 265   size_type capacity()const BOOST_NOEXCEPT{return ptrs.capacity();}
 266
 267   void reserve(size_type n)
 268   {
 269     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
 270     ptrs.reserve(n);
 271   }
 272
 273   void shrink_to_fit()
 274   {
 275     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
 276     ptrs.shrink_to_fit();
 277   }
 278
 279   void resize(size_type n)
 280   {
 281     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
 282     if(n>size())
 283       for(size_type m=n-size();m--;)
 284         this->final_emplace_(BOOST_MULTI_INDEX_NULL_PARAM_PACK);
 285     else if(n<size())erase(begin()+n,end());
 286   }
 287
 288   void resize(size_type n,value_param_type x)
 289   {
 290     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
 291     if(n>size())for(size_type m=n-size();m--;)this->final_insert_(x);
 292     else if(n<size())erase(begin()+n,end());
 293   }
 294
 295   /* access: no non-const versions provided as random_access_index
 296    * handles const elements.
 297    */
 298
 299   const_reference operator[](size_type n)const
 300   {
 301     BOOST_MULTI_INDEX_SAFE_MODE_ASSERT(n<size(),safe_mode::out_of_bounds);
 302     return node_type::from_impl(*ptrs.at(n))->value();
 303   }
 304
 305   const_reference at(size_type n)const
 306   {
 307     if(n>=size())throw_exception(std::out_of_range("random access index"));
 308     return node_type::from_impl(*ptrs.at(n))->value();
 309   }
 310
 311   const_reference front()const{return operator[](0);}
 312   const_reference back()const{return operator[](size()-1);}
 313
 314   /* modifiers */
 315
 316   BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL(
 317     emplace_return_type,emplace_front,emplace_front_impl)
 318
 319   std::pair<iterator,bool> push_front(const value_type& x)
 320                              {return insert(begin(),x);}
 321   std::pair<iterator,bool> push_front(BOOST_RV_REF(value_type) x)
 322                              {return insert(begin(),boost::move(x));}
 323   void                     pop_front(){erase(begin());}
 324
 325   BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL(
 326     emplace_return_type,emplace_back,emplace_back_impl)
 327
 328   std::pair<iterator,bool> push_back(const value_type& x)
 329                              {return insert(end(),x);}
 330   std::pair<iterator,bool> push_back(BOOST_RV_REF(value_type) x)
 331                              {return insert(end(),boost::move(x));}
 332   void                     pop_back(){erase(--end());}
 333
 334   BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL_EXTRA_ARG(
 335     emplace_return_type,emplace,emplace_impl,iterator,position)
 336
 337   std::pair<iterator,bool> insert(iterator position,const value_type& x)
 338   {
 339     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 340     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 341     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
 342     std::pair<final_node_type*,bool> p=this->final_insert_(x);
 343     if(p.second&&position.get_node()!=header()){
 344       relocate(position.get_node(),p.first);
 345     }
 346     return std::pair<iterator,bool>(make_iterator(p.first),p.second);
 347   }
 348
 349   std::pair<iterator,bool> insert(iterator position,BOOST_RV_REF(value_type) x)
 350   {
 351     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 352     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 353     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
 354     std::pair<final_node_type*,bool> p=this->final_insert_rv_(x);
 355     if(p.second&&position.get_node()!=header()){
 356       relocate(position.get_node(),p.first);
 357     }
 358     return std::pair<iterator,bool>(make_iterator(p.first),p.second);
 359   }
 360
 361   void insert(iterator position,size_type n,value_param_type x)
 362   {
 363     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 364     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 365     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
 366     size_type s=0;
 367     BOOST_TRY{
 368       while(n--){
 369         if(push_back(x).second)++s;
 370       }
 371     }
 372     BOOST_CATCH(...){
 373       relocate(position,end()-s,end());
 374       BOOST_RETHROW;
 375     }
 376     BOOST_CATCH_END
 377     relocate(position,end()-s,end());
 378   }
 379
 380   template<typename InputIterator>
 381   void insert(iterator position,InputIterator first,InputIterator last)
 382   {
 383     insert_iter(position,first,last,mpl::not_<is_integral<InputIterator> >());
 384   }
 385
 386 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
 387   void insert(iterator position,std::initializer_list<value_type> list)
 388   {
 389     insert(position,list.begin(),list.end());
 390   }
 391 #endif
 392
 393   iterator erase(iterator position)
 394   {
 395     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 396     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
 397     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 398     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
 399     this->final_erase_(static_cast<final_node_type*>(position++.get_node()));
 400     return position;
 401   }
 402
 403   iterator erase(iterator first,iterator last)
 404   {
 405     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first);
 406     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last);
 407     BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,*this);
 408     BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,*this);
 409     BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last);
 410     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
 411     difference_type n=last-first;
 412     relocate(end(),first,last);
 413     while(n--)pop_back();
 414     return last;
 415   }
 416
 417   bool replace(iterator position,const value_type& x)
 418   {
 419     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 420     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
 421     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 422     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
 423     return this->final_replace_(
 424       x,static_cast<final_node_type*>(position.get_node()));
 425   }
 426
 427   bool replace(iterator position,BOOST_RV_REF(value_type) x)
 428   {
 429     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 430     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
 431     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 432     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
 433     return this->final_replace_rv_(
 434       x,static_cast<final_node_type*>(position.get_node()));
 435   }
 436
 437   template<typename Modifier>
 438   bool modify(iterator position,Modifier mod)
 439   {
 440     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 441     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
 442     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 443     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
 444
 445 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 446     /* MSVC++ 6.0 optimizer on safe mode code chokes if this
 447      * this is not added. Left it for all compilers as it does no
 448      * harm.
 449      */
 450
 451     position.detach();
 452 #endif
 453
 454     return this->final_modify_(
 455       mod,static_cast<final_node_type*>(position.get_node()));
 456   }
 457
 458   template<typename Modifier,typename Rollback>
 459   bool modify(iterator position,Modifier mod,Rollback back_)
 460   {
 461     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 462     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
 463     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 464     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
 465
 466 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 467     /* MSVC++ 6.0 optimizer on safe mode code chokes if this
 468      * this is not added. Left it for all compilers as it does no
 469      * harm.
 470      */
 471
 472     position.detach();
 473 #endif
 474
 475     return this->final_modify_(
 476       mod,back_,static_cast<final_node_type*>(position.get_node()));
 477   }
 478
 479   void swap(random_access_index<SuperMeta,TagList>& x)
 480   {
 481     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
 482     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT_OF(x);
 483     this->final_swap_(x.final());
 484   }
 485
 486   void clear()BOOST_NOEXCEPT
 487   {
 488     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
 489     this->final_clear_();
 490   }
 491
 492   /* list operations */
 493
 494   void splice(iterator position,random_access_index<SuperMeta,TagList>& x)
 495   {
 496     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 497     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 498     BOOST_MULTI_INDEX_CHECK_DIFFERENT_CONTAINER(*this,x);
 499     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
 500     iterator  first=x.begin(),last=x.end();
 501     size_type n=0;
 502     BOOST_TRY{
 503       while(first!=last){
 504         if(push_back(*first).second){
 505           first=x.erase(first);
 506           ++n;
 507         }
 508         else ++first;
 509       }
 510     }
 511     BOOST_CATCH(...){
 512       relocate(position,end()-n,end());
 513       BOOST_RETHROW;
 514     }
 515     BOOST_CATCH_END
 516     relocate(position,end()-n,end());
 517   }
 518
 519   void splice(
 520     iterator position,random_access_index<SuperMeta,TagList>& x,iterator i)
 521   {
 522     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 523     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 524     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(i);
 525     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(i);
 526     BOOST_MULTI_INDEX_CHECK_IS_OWNER(i,x);
 527     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
 528     if(&x==this)relocate(position,i);
 529     else{
 530       if(insert(position,*i).second){
 531
 532 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 533     /* MSVC++ 6.0 optimizer has a hard time with safe mode, and the following
 534      * workaround is needed. Left it for all compilers as it does no
 535      * harm.
 536      */
 537         i.detach();
 538         x.erase(x.make_iterator(i.get_node()));
 539 #else
 540         x.erase(i);
 541 #endif
 542
 543       }
 544     }
 545   }
 546
 547   void splice(
 548     iterator position,random_access_index<SuperMeta,TagList>& x,
 549     iterator first,iterator last)
 550   {
 551     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 552     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 553     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first);
 554     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last);
 555     BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,x);
 556     BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,x);
 557     BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last);
 558     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
 559     if(&x==this)relocate(position,first,last);
 560     else{
 561       size_type n=0;
 562       BOOST_TRY{
 563         while(first!=last){
 564           if(push_back(*first).second){
 565             first=x.erase(first);
 566             ++n;
 567           }
 568           else ++first;
 569         }
 570       }
 571       BOOST_CATCH(...){
 572         relocate(position,end()-n,end());
 573         BOOST_RETHROW;
 574       }
 575       BOOST_CATCH_END
 576       relocate(position,end()-n,end());
 577     }
 578   }
 579
 580   void remove(value_param_type value)
 581   {
 582     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
 583     difference_type n=
 584       end()-make_iterator(
 585         random_access_index_remove<node_type>(
 586           ptrs,
 587           ::boost::bind(std::equal_to<value_type>(),::boost::arg<1>(),value)));
 588     while(n--)pop_back();
 589   }
 590
 591   template<typename Predicate>
 592   void remove_if(Predicate pred)
 593   {
 594     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
 595     difference_type n=
 596       end()-make_iterator(random_access_index_remove<node_type>(ptrs,pred));
 597     while(n--)pop_back();
 598   }
 599
 600   void unique()
 601   {
 602     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
 603     difference_type n=
 604       end()-make_iterator(
 605         random_access_index_unique<node_type>(
 606           ptrs,std::equal_to<value_type>()));
 607     while(n--)pop_back();
 608   }
 609
 610   template <class BinaryPredicate>
 611   void unique(BinaryPredicate binary_pred)
 612   {
 613     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
 614     difference_type n=
 615       end()-make_iterator(
 616         random_access_index_unique<node_type>(ptrs,binary_pred));
 617     while(n--)pop_back();
 618   }
 619
 620   void merge(random_access_index<SuperMeta,TagList>& x)
 621   {
 622     if(this!=&x){
 623       BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
 624       size_type s=size();
 625       splice(end(),x);
 626       random_access_index_inplace_merge<node_type>(
 627         get_allocator(),ptrs,ptrs.at(s),std::less<value_type>());
 628     }
 629   }
 630
 631   template <typename Compare>
 632   void merge(random_access_index<SuperMeta,TagList>& x,Compare comp)
 633   {
 634     if(this!=&x){
 635       BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
 636       size_type s=size();
 637       splice(end(),x);
 638       random_access_index_inplace_merge<node_type>(
 639         get_allocator(),ptrs,ptrs.at(s),comp);
 640     }
 641   }
 642
 643   void sort()
 644   {
 645     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
 646     random_access_index_sort<node_type>(
 647       get_allocator(),ptrs,std::less<value_type>());
 648   }
 649
 650   template <typename Compare>
 651   void sort(Compare comp)
 652   {
 653     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
 654     random_access_index_sort<node_type>(
 655       get_allocator(),ptrs,comp);
 656   }
 657
 658   void reverse()BOOST_NOEXCEPT
 659   {
 660     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
 661     node_impl_type::reverse(ptrs.begin(),ptrs.end());
 662   }
 663
 664   /* rearrange operations */
 665
 666   void relocate(iterator position,iterator i)
 667   {
 668     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 669     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 670     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(i);
 671     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(i);
 672     BOOST_MULTI_INDEX_CHECK_IS_OWNER(i,*this);
 673     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
 674     if(position!=i)relocate(position.get_node(),i.get_node());
 675   }
 676
 677   void relocate(iterator position,iterator first,iterator last)
 678   {
 679     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 680     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 681     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first);
 682     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last);
 683     BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,*this);
 684     BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,*this);
 685     BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last);
 686     BOOST_MULTI_INDEX_CHECK_OUTSIDE_RANGE(position,first,last);
 687     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
 688     if(position!=last)relocate(
 689       position.get_node(),first.get_node(),last.get_node());
 690   }
 691
 692   template<typename InputIterator>
 693   void rearrange(InputIterator first)
 694   {
 695     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
 696     for(node_impl_ptr_pointer p0=ptrs.begin(),p0_end=ptrs.end();
 697         p0!=p0_end;++first,++p0){
 698       const value_type& v1=*first;
 699       node_impl_ptr_pointer p1=node_from_value<node_type>(&v1)->up();
 700
 701       std::swap(*p0,*p1);
 702       (*p0)->up()=p0;
 703       (*p1)->up()=p1;
 704     }
 705   }
 706
 707 BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS:
 708   random_access_index(
 709     const ctor_args_list& args_list,const allocator_type& al):
 710     super(args_list.get_tail(),al),
 711     ptrs(al,header()->impl(),0)
 712   {
 713   }
 714
 715   random_access_index(const random_access_index<SuperMeta,TagList>& x):
 716     super(x),
 717
 718 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 719     safe_super(),
 720 #endif
 721
 722     ptrs(x.get_allocator(),header()->impl(),x.size())
 723   {
 724     /* The actual copying takes place in subsequent call to copy_().
 725      */
 726   }
 727
 728   random_access_index(
 729     const random_access_index<SuperMeta,TagList>& x,do_not_copy_elements_tag):
 730     super(x,do_not_copy_elements_tag()),
 731
 732 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 733     safe_super(),
 734 #endif
 735
 736     ptrs(x.get_allocator(),header()->impl(),0)
 737   {
 738   }
 739
 740   ~random_access_index()
 741   {
 742     /* the container is guaranteed to be empty by now */
 743   }
 744
 745 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 746   iterator       make_iterator(node_type* node){return iterator(node,this);}
 747   const_iterator make_iterator(node_type* node)const
 748     {return const_iterator(node,const_cast<random_access_index*>(this));}
 749 #else
 750   iterator       make_iterator(node_type* node){return iterator(node);}
 751   const_iterator make_iterator(node_type* node)const
 752                    {return const_iterator(node);}
 753 #endif
 754
 755   void copy_(
 756     const random_access_index<SuperMeta,TagList>& x,const copy_map_type& map)
 757   {
 758     for(node_impl_ptr_pointer begin_org=x.ptrs.begin(),
 759                               begin_cpy=ptrs.begin(),
 760                               end_org=x.ptrs.end();
 761         begin_org!=end_org;++begin_org,++begin_cpy){
 762       *begin_cpy=
 763          static_cast<node_type*>(
 764            map.find(
 765              static_cast<final_node_type*>(
 766                node_type::from_impl(*begin_org))))->impl();
 767       (*begin_cpy)->up()=begin_cpy;
 768     }
 769
 770     super::copy_(x,map);
 771   }
 772
 773   template<typename Variant>
 774   final_node_type* insert_(
 775     value_param_type v,final_node_type*& x,Variant variant)
 776   {
 777     ptrs.room_for_one();
 778     final_node_type* res=super::insert_(v,x,variant);
 779     if(res==x)ptrs.push_back(static_cast<node_type*>(x)->impl());
 780     return res;
 781   }
 782
 783   template<typename Variant>
 784   final_node_type* insert_(
 785     value_param_type v,node_type* position,final_node_type*& x,Variant variant)
 786   {
 787     ptrs.room_for_one();
 788     final_node_type* res=super::insert_(v,position,x,variant);
 789     if(res==x)ptrs.push_back(static_cast<node_type*>(x)->impl());
 790     return res;
 791   }
 792
 793   void erase_(node_type* x)
 794   {
 795     ptrs.erase(x->impl());
 796     super::erase_(x);
 797
 798 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 799     detach_iterators(x);
 800 #endif
 801   }
 802
 803   void delete_all_nodes_()
 804   {
 805     for(node_impl_ptr_pointer x=ptrs.begin(),x_end=ptrs.end();x!=x_end;++x){
 806       this->final_delete_node_(
 807         static_cast<final_node_type*>(node_type::from_impl(*x)));
 808     }
 809   }
 810
 811   void clear_()
 812   {
 813     super::clear_();
 814     ptrs.clear();
 815
 816 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 817     safe_super::detach_dereferenceable_iterators();
 818 #endif
 819   }
 820
 821   void swap_(random_access_index<SuperMeta,TagList>& x)
 822   {
 823     ptrs.swap(x.ptrs);
 824
 825 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 826     safe_super::swap(x);
 827 #endif
 828
 829     super::swap_(x);
 830   }
 831
 832   void swap_elements_(random_access_index<SuperMeta,TagList>& x)
 833   {
 834     ptrs.swap(x.ptrs);
 835
 836 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 837     safe_super::swap(x);
 838 #endif
 839
 840     super::swap_elements_(x);
 841   }
 842
 843   template<typename Variant>
 844   bool replace_(value_param_type v,node_type* x,Variant variant)
 845   {
 846     return super::replace_(v,x,variant);
 847   }
 848
 849   bool modify_(node_type* x)
 850   {
 851     BOOST_TRY{
 852       if(!super::modify_(x)){
 853         ptrs.erase(x->impl());
 854
 855 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 856         detach_iterators(x);
 857 #endif
 858
 859         return false;
 860       }
 861       else return true;
 862     }
 863     BOOST_CATCH(...){
 864       ptrs.erase(x->impl());
 865
 866 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 867       detach_iterators(x);
 868 #endif
 869
 870       BOOST_RETHROW;
 871     }
 872     BOOST_CATCH_END
 873   }
 874
 875   bool modify_rollback_(node_type* x)
 876   {
 877     return super::modify_rollback_(x);
 878   }
 879
 880 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
 881   /* serialization */
 882
 883   template<typename Archive>
 884   void save_(
 885     Archive& ar,const unsigned int version,const index_saver_type& sm)const
 886   {
 887     sm.save(begin(),end(),ar,version);
 888     super::save_(ar,version,sm);
 889   }
 890
 891   template<typename Archive>
 892   void load_(
 893     Archive& ar,const unsigned int version,const index_loader_type& lm)
 894   {
 895     {
 896       typedef random_access_index_loader<node_type,allocator_type> loader;
 897
 898       loader ld(get_allocator(),ptrs);
 899       lm.load(
 900         ::boost::bind(
 901           &loader::rearrange,&ld,::boost::arg<1>(),::boost::arg<2>()),
 902         ar,version);
 903     } /* exit scope so that ld frees its resources */
 904     super::load_(ar,version,lm);
 905   }
 906 #endif
 907
 908 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
 909   /* invariant stuff */
 910
 911   bool invariant_()const
 912   {
 913     if(size()>capacity())return false;
 914     if(size()==0||begin()==end()){
 915       if(size()!=0||begin()!=end())return false;
 916     }
 917     else{
 918       size_type s=0;
 919       for(const_iterator it=begin(),it_end=end();;++it,++s){
 920         if(*(it.get_node()->up())!=it.get_node()->impl())return false;
 921         if(it==it_end)break;
 922       }
 923       if(s!=size())return false;
 924     }
 925
 926     return super::invariant_();
 927   }
 928
 929   /* This forwarding function eases things for the boost::mem_fn construct
 930    * in BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT. Actually,
 931    * final_check_invariant is already an inherited member function of index.
 932    */
 933   void check_invariant_()const{this->final_check_invariant_();}
 934 #endif
 935
 936 private:
 937   node_type* header()const{return this->final_header();}
 938
 939   static void relocate(node_type* position,node_type* x)
 940   {
 941     node_impl_type::relocate(position->up(),x->up());
 942   }
 943
 944   static void relocate(node_type* position,node_type* first,node_type* last)
 945   {
 946     node_impl_type::relocate(
 947       position->up(),first->up(),last->up());
 948   }
 949
 950 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 951   void detach_iterators(node_type* x)
 952   {
 953     iterator it=make_iterator(x);
 954     safe_mode::detach_equivalent_iterators(it);
 955   }
 956 #endif
 957
 958   template <class InputIterator>
 959   void assign_iter(InputIterator first,InputIterator last,mpl::true_)
 960   {
 961     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
 962     clear();
 963     for(;first!=last;++first)this->final_insert_ref_(*first);
 964   }
 965
 966   void assign_iter(size_type n,value_param_type value,mpl::false_)
 967   {
 968     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
 969     clear();
 970     for(size_type i=0;i<n;++i)push_back(value);
 971   }
 972
 973   template<typename InputIterator>
 974   void insert_iter(
 975     iterator position,InputIterator first,InputIterator last,mpl::true_)
 976   {
 977     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
 978     size_type s=0;
 979     BOOST_TRY{
 980       for(;first!=last;++first){
 981         if(this->final_insert_ref_(*first).second)++s;
 982       }
 983     }
 984     BOOST_CATCH(...){
 985       relocate(position,end()-s,end());
 986       BOOST_RETHROW;
 987     }
 988     BOOST_CATCH_END
 989     relocate(position,end()-s,end());
 990   }
 991
 992   void insert_iter(
 993     iterator position,size_type n,value_param_type x,mpl::false_)
 994   {
 995     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 996     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 997     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
 998     size_type  s=0;
 999     BOOST_TRY{
1000       while(n--){
1001         if(push_back(x).second)++s;
1002       }
1003     }
1004     BOOST_CATCH(...){
1005       relocate(position,end()-s,end());
1006       BOOST_RETHROW;
1007     }
1008     BOOST_CATCH_END
1009     relocate(position,end()-s,end());
1010   }
1011
1012   template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK>
1013   std::pair<iterator,bool> emplace_front_impl(
1014     BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK)
1015   {
1016     return emplace_impl(begin(),BOOST_MULTI_INDEX_FORWARD_PARAM_PACK);
1017   }
1018
1019   template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK>
1020   std::pair<iterator,bool> emplace_back_impl(
1021     BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK)
1022   {
1023     return emplace_impl(end(),BOOST_MULTI_INDEX_FORWARD_PARAM_PACK);
1024   }
1025
1026   template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK>
1027   std::pair<iterator,bool> emplace_impl(
1028     iterator position,BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK)
1029   {
1030     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
1031     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
1032     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
1033     std::pair<final_node_type*,bool> p=
1034       this->final_emplace_(BOOST_MULTI_INDEX_FORWARD_PARAM_PACK);
1035     if(p.second&&position.get_node()!=header()){
1036       relocate(position.get_node(),p.first);
1037     }
1038     return std::pair<iterator,bool>(make_iterator(p.first),p.second);
1039   }
1040
1041   ptr_array ptrs;
1042
1043 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
1044     BOOST_WORKAROUND(__MWERKS__,<=0x3003)
1045 #pragma parse_mfunc_templ reset
1046 #endif
1047 };
1048
1049 /* comparison */
1050
1051 template<
1052   typename SuperMeta1,typename TagList1,
1053   typename SuperMeta2,typename TagList2
1054 >
1055 bool operator==(
1056   const random_access_index<SuperMeta1,TagList1>& x,
1057   const random_access_index<SuperMeta2,TagList2>& y)
1058 {
1059   return x.size()==y.size()&&std::equal(x.begin(),x.end(),y.begin());
1060 }
1061
1062 template<
1063   typename SuperMeta1,typename TagList1,
1064   typename SuperMeta2,typename TagList2
1065 >
1066 bool operator<(
1067   const random_access_index<SuperMeta1,TagList1>& x,
1068   const random_access_index<SuperMeta2,TagList2>& y)
1069 {
1070   return std::lexicographical_compare(x.begin(),x.end(),y.begin(),y.end());
1071 }
1072
1073 template<
1074   typename SuperMeta1,typename TagList1,
1075   typename SuperMeta2,typename TagList2
1076 >
1077 bool operator!=(
1078   const random_access_index<SuperMeta1,TagList1>& x,
1079   const random_access_index<SuperMeta2,TagList2>& y)
1080 {
1081   return !(x==y);
1082 }
1083
1084 template<
1085   typename SuperMeta1,typename TagList1,
1086   typename SuperMeta2,typename TagList2
1087 >
1088 bool operator>(
1089   const random_access_index<SuperMeta1,TagList1>& x,
1090   const random_access_index<SuperMeta2,TagList2>& y)
1091 {
1092   return y<x;
1093 }
1094
1095 template<
1096   typename SuperMeta1,typename TagList1,
1097   typename SuperMeta2,typename TagList2
1098 >
1099 bool operator>=(
1100   const random_access_index<SuperMeta1,TagList1>& x,
1101   const random_access_index<SuperMeta2,TagList2>& y)
1102 {
1103   return !(x<y);
1104 }
1105
1106 template<
1107   typename SuperMeta1,typename TagList1,
1108   typename SuperMeta2,typename TagList2
1109 >
1110 bool operator<=(
1111   const random_access_index<SuperMeta1,TagList1>& x,
1112   const random_access_index<SuperMeta2,TagList2>& y)
1113 {
1114   return !(x>y);
1115 }
1116
1117 /*  specialized algorithms */
1118
1119 template<typename SuperMeta,typename TagList>
1120 void swap(
1121   random_access_index<SuperMeta,TagList>& x,
1122   random_access_index<SuperMeta,TagList>& y)
1123 {
1124   x.swap(y);
1125 }
1126
1127 } /* namespace multi_index::detail */
1128
1129 /* random access index specifier */
1130
1131 template <typename TagList>
1132 struct random_access
1133 {
1134   BOOST_STATIC_ASSERT(detail::is_tag<TagList>::value);
1135
1136   template<typename Super>
1137   struct node_class
1138   {
1139     typedef detail::random_access_index_node<Super> type;
1140   };
1141
1142   template<typename SuperMeta>
1143   struct index_class
1144   {
1145     typedef detail::random_access_index<
1146       SuperMeta,typename TagList::type>  type;
1147   };
1148 };
1149
1150 } /* namespace multi_index */
1151
1152 } /* namespace boost */
1153
1154 /* Boost.Foreach compatibility */
1155
1156 template<typename SuperMeta,typename TagList>
1157 inline boost::mpl::true_* boost_foreach_is_noncopyable(
1158   boost::multi_index::detail::random_access_index<SuperMeta,TagList>*&,
1159   boost_foreach_argument_dependent_lookup_hack)
1160 {
1161   return 0;
1162 }
1163
1164 #undef BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT
1165 #undef BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT_OF
1166
1167 #endif