boost/multi_index/random_access_index.hpp

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