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