boost/multi_index/random_access_index.hpp

0001 /* Copyright 2003-2023 Joaquin M Lopez Munoz.
0002  * Distributed under the Boost Software License, Version 1.0.
0003  * (See accompanying file LICENSE_1_0.txt or copy at
0004  * http://www.boost.org/LICENSE_1_0.txt)
0005  *
0006  * See http://www.boost.org/libs/multi_index for library home page.
0007  */
0008
0009 #ifndef BOOST_MULTI_INDEX_RANDOM_ACCESS_INDEX_HPP
0010 #define BOOST_MULTI_INDEX_RANDOM_ACCESS_INDEX_HPP
0011
0012 #if defined(_MSC_VER)
0013 #pragma once
0014 #endif
0015
0016 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
0017 #include <algorithm>
0018 #include <boost/bind/bind.hpp>
0019 #include <boost/call_traits.hpp>
0020 #include <boost/core/addressof.hpp>
0021 #include <boost/core/no_exceptions_support.hpp>
0022 #include <boost/detail/workaround.hpp>
0023 #include <boost/iterator/reverse_iterator.hpp>
0024 #include <boost/move/core.hpp>
0025 #include <boost/move/utility_core.hpp>
0026 #include <boost/mpl/bool.hpp>
0027 #include <boost/mpl/not.hpp>
0028 #include <boost/mpl/push_front.hpp>
0029 #include <boost/multi_index/detail/access_specifier.hpp>
0030 #include <boost/multi_index/detail/allocator_traits.hpp>
0031 #include <boost/multi_index/detail/do_not_copy_elements_tag.hpp>
0032 #include <boost/multi_index/detail/index_node_base.hpp>
0033 #include <boost/multi_index/detail/node_handle.hpp>
0034 #include <boost/multi_index/detail/rnd_node_iterator.hpp>
0035 #include <boost/multi_index/detail/rnd_index_node.hpp>
0036 #include <boost/multi_index/detail/rnd_index_ops.hpp>
0037 #include <boost/multi_index/detail/rnd_index_ptr_array.hpp>
0038 #include <boost/multi_index/detail/safe_mode.hpp>
0039 #include <boost/multi_index/detail/scope_guard.hpp>
0040 #include <boost/multi_index/detail/vartempl_support.hpp>
0041 #include <boost/multi_index/random_access_index_fwd.hpp>
0042 #include <boost/throw_exception.hpp>
0043 #include <boost/tuple/tuple.hpp>
0044 #include <boost/type_traits/is_copy_constructible.hpp>
0045 #include <boost/type_traits/is_integral.hpp>
0046 #include <functional>
0047 #include <stdexcept>
0048 #include <utility>
0049
0050 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
0051 #include<initializer_list>
0052 #endif
0053
0054 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
0055 #include <boost/multi_index/detail/rnd_index_loader.hpp>
0056 #endif
0057
0058 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
0059 #define BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT_OF(x)                    \
0060   detail::scope_guard BOOST_JOIN(check_invariant_,__LINE__)=                 \
0061     detail::make_obj_guard(x,&random_access_index::check_invariant_);        \
0062   BOOST_JOIN(check_invariant_,__LINE__).touch();
0063 #define BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT                          \
0064   BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT_OF(*this)
0065 #else
0066 #define BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT_OF(x)
0067 #define BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT
0068 #endif
0069
0070 namespace boost{
0071
0072 namespace multi_index{
0073
0074 namespace detail{
0075
0076 /* random_access_index adds a layer of random access indexing
0077  * to a given Super
0078  */
0079
0080 #if defined(BOOST_MSVC)
0081 #pragma warning(push)
0082 #pragma warning(disable:4355) /* this used in base member initializer list */
0083 #endif
0084
0085 template<typename SuperMeta,typename TagList>
0086 class random_access_index:
0087   BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS SuperMeta::type
0088 {
0089 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
0090     BOOST_WORKAROUND(__MWERKS__,<=0x3003)
0091 /* The "ISO C++ Template Parser" option in CW8.3 has a problem with the
0092  * lifetime of const references bound to temporaries --precisely what
0093  * scopeguards are.
0094  */
0095
0096 #pragma parse_mfunc_templ off
0097 #endif
0098
0099 #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
0100   /* cross-index access */
0101
0102   template <typename,typename,typename> friend class index_base;
0103 #endif
0104
0105   typedef typename SuperMeta::type               super;
0106
0107 protected:
0108   typedef random_access_index_node<
0109     typename super::index_node_type>             index_node_type;
0110
0111 private:
0112   typedef typename index_node_type::impl_type    node_impl_type;
0113   typedef random_access_index_ptr_array<
0114     typename super::final_allocator_type>        ptr_array;
0115   typedef typename ptr_array::pointer            node_impl_ptr_pointer;
0116
0117 public:
0118   /* types */
0119
0120   typedef typename index_node_type::value_type   value_type;
0121   typedef tuples::null_type                      ctor_args;
0122   typedef typename super::final_allocator_type   allocator_type;
0123   typedef value_type&                            reference;
0124   typedef const value_type&                      const_reference;
0125
0126 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
0127   typedef safe_mode::safe_iterator<
0128     rnd_node_iterator<index_node_type> >        iterator;
0129 #else
0130   typedef rnd_node_iterator<index_node_type>    iterator;
0131 #endif
0132
0133   typedef iterator                               const_iterator;
0134
0135 private:
0136   typedef allocator_traits<allocator_type>       alloc_traits;
0137
0138 public:
0139   typedef typename alloc_traits::pointer         pointer;
0140   typedef typename alloc_traits::const_pointer   const_pointer;
0141   typedef typename alloc_traits::size_type       size_type;
0142   typedef typename alloc_traits::difference_type difference_type;
0143   typedef typename
0144     boost::reverse_iterator<iterator>            reverse_iterator;
0145   typedef typename
0146     boost::reverse_iterator<const_iterator>      const_reverse_iterator;
0147   typedef typename super::final_node_handle_type node_type;
0148   typedef detail::insert_return_type<
0149     iterator,node_type>                          insert_return_type;
0150   typedef TagList                                tag_list;
0151
0152 protected:
0153   typedef typename super::final_node_type     final_node_type;
0154   typedef tuples::cons<
0155     ctor_args,
0156     typename super::ctor_args_list>           ctor_args_list;
0157   typedef typename mpl::push_front<
0158     typename super::index_type_list,
0159     random_access_index>::type                index_type_list;
0160   typedef typename mpl::push_front<
0161     typename super::iterator_type_list,
0162     iterator>::type                           iterator_type_list;
0163   typedef typename mpl::push_front<
0164     typename super::const_iterator_type_list,
0165     const_iterator>::type                     const_iterator_type_list;
0166   typedef typename super::copy_map_type       copy_map_type;
0167
0168 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
0169   typedef typename super::index_saver_type    index_saver_type;
0170   typedef typename super::index_loader_type   index_loader_type;
0171 #endif
0172
0173 private:
0174 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
0175   typedef safe_mode::safe_container<iterator> safe_container;
0176 #endif
0177
0178   typedef typename call_traits<
0179     value_type>::param_type                   value_param_type;
0180
0181   /* needed to avoid commas in some macros */
0182
0183   typedef std::pair<iterator,bool>            pair_return_type;
0184
0185 public:
0186
0187   /* construct/copy/destroy
0188    * Default and copy ctors are in the protected section as indices are
0189    * not supposed to be created on their own. No range ctor either.
0190    */
0191
0192   random_access_index<SuperMeta,TagList>& operator=(
0193     const random_access_index<SuperMeta,TagList>& x)
0194   {
0195     this->final()=x.final();
0196     return *this;
0197   }
0198
0199 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
0200   random_access_index<SuperMeta,TagList>& operator=(
0201     std::initializer_list<value_type> list)
0202   {
0203     this->final()=list;
0204     return *this;
0205   }
0206 #endif
0207
0208   template <class InputIterator>
0209   void assign(InputIterator first,InputIterator last)
0210   {
0211     assign_iter(first,last,mpl::not_<is_integral<InputIterator> >());
0212   }
0213
0214 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
0215   void assign(std::initializer_list<value_type> list)
0216   {
0217     assign(list.begin(),list.end());
0218   }
0219 #endif
0220
0221   void assign(size_type n,value_param_type value)
0222   {
0223     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
0224     clear();
0225     for(size_type i=0;i<n;++i)push_back(value);
0226   }
0227
0228   allocator_type get_allocator()const BOOST_NOEXCEPT
0229   {
0230     return this->final().get_allocator();
0231   }
0232
0233   /* iterators */
0234
0235   iterator begin()BOOST_NOEXCEPT
0236     {return make_iterator(index_node_type::from_impl(*ptrs.begin()));}
0237   const_iterator begin()const BOOST_NOEXCEPT
0238     {return make_iterator(index_node_type::from_impl(*ptrs.begin()));}
0239   iterator
0240     end()BOOST_NOEXCEPT{return make_iterator(header());}
0241   const_iterator
0242     end()const BOOST_NOEXCEPT{return make_iterator(header());}
0243   reverse_iterator
0244     rbegin()BOOST_NOEXCEPT{return boost::make_reverse_iterator(end());}
0245   const_reverse_iterator
0246     rbegin()const BOOST_NOEXCEPT{return boost::make_reverse_iterator(end());}
0247   reverse_iterator
0248     rend()BOOST_NOEXCEPT{return boost::make_reverse_iterator(begin());}
0249   const_reverse_iterator
0250     rend()const BOOST_NOEXCEPT{return boost::make_reverse_iterator(begin());}
0251   const_iterator
0252     cbegin()const BOOST_NOEXCEPT{return begin();}
0253   const_iterator
0254     cend()const BOOST_NOEXCEPT{return end();}
0255   const_reverse_iterator
0256     crbegin()const BOOST_NOEXCEPT{return rbegin();}
0257   const_reverse_iterator
0258     crend()const BOOST_NOEXCEPT{return rend();}
0259
0260   iterator iterator_to(const value_type& x)
0261   {
0262     return make_iterator(
0263       node_from_value<index_node_type>(boost::addressof(x)));
0264   }
0265
0266   const_iterator iterator_to(const value_type& x)const
0267   {
0268     return make_iterator(
0269       node_from_value<index_node_type>(boost::addressof(x)));
0270   }
0271
0272   /* capacity */
0273
0274   bool      empty()const BOOST_NOEXCEPT{return this->final_empty_();}
0275   size_type size()const BOOST_NOEXCEPT{return this->final_size_();}
0276   size_type max_size()const BOOST_NOEXCEPT{return this->final_max_size_();}
0277   size_type capacity()const BOOST_NOEXCEPT{return ptrs.capacity();}
0278
0279   void reserve(size_type n)
0280   {
0281     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
0282     ptrs.reserve(n);
0283   }
0284
0285   void shrink_to_fit()
0286   {
0287     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
0288     ptrs.shrink_to_fit();
0289   }
0290
0291   void resize(size_type n)
0292   {
0293     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
0294     if(n>size())
0295       for(size_type m=n-size();m--;)
0296         this->final_emplace_(BOOST_MULTI_INDEX_NULL_PARAM_PACK);
0297     else if(n<size())erase(begin()+n,end());
0298   }
0299
0300   void resize(size_type n,value_param_type x)
0301   {
0302     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
0303     if(n>size())for(size_type m=n-size();m--;)this->final_insert_(x);
0304     else if(n<size())erase(begin()+n,end());
0305   }
0306
0307   /* access: no non-const versions provided as random_access_index
0308    * handles const elements.
0309    */
0310
0311   const_reference operator[](size_type n)const
0312   {
0313     BOOST_MULTI_INDEX_SAFE_MODE_ASSERT(n<size(),safe_mode::out_of_bounds);
0314     return index_node_type::from_impl(*ptrs.at(n))->value();
0315   }
0316
0317   const_reference at(size_type n)const
0318   {
0319     if(n>=size())throw_exception(std::out_of_range("random access index"));
0320     return index_node_type::from_impl(*ptrs.at(n))->value();
0321   }
0322
0323   const_reference front()const{return operator[](0);}
0324   const_reference back()const{return operator[](size()-1);}
0325
0326   /* modifiers */
0327
0328   BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL(
0329     pair_return_type,emplace_front,emplace_front_impl)
0330
0331   std::pair<iterator,bool> push_front(const value_type& x)
0332                              {return insert(begin(),x);}
0333   std::pair<iterator,bool> push_front(BOOST_RV_REF(value_type) x)
0334                              {return insert(begin(),boost::move(x));}
0335   void                     pop_front(){erase(begin());}
0336
0337   BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL(
0338     pair_return_type,emplace_back,emplace_back_impl)
0339
0340   std::pair<iterator,bool> push_back(const value_type& x)
0341                              {return insert(end(),x);}
0342   std::pair<iterator,bool> push_back(BOOST_RV_REF(value_type) x)
0343                              {return insert(end(),boost::move(x));}
0344   void                     pop_back(){erase(--end());}
0345
0346   BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL_EXTRA_ARG(
0347     pair_return_type,emplace,emplace_impl,iterator,position)
0348
0349   std::pair<iterator,bool> insert(iterator position,const value_type& x)
0350   {
0351     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
0352     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
0353     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
0354     std::pair<final_node_type*,bool> p=this->final_insert_(x);
0355     if(p.second&&position.get_node()!=header()){
0356       relocate(position.get_node(),p.first);
0357     }
0358     return std::pair<iterator,bool>(make_iterator(p.first),p.second);
0359   }
0360
0361   std::pair<iterator,bool> insert(iterator position,BOOST_RV_REF(value_type) x)
0362   {
0363     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
0364     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
0365     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
0366     std::pair<final_node_type*,bool> p=this->final_insert_rv_(x);
0367     if(p.second&&position.get_node()!=header()){
0368       relocate(position.get_node(),p.first);
0369     }
0370     return std::pair<iterator,bool>(make_iterator(p.first),p.second);
0371   }
0372
0373   void insert(iterator position,size_type n,value_param_type x)
0374   {
0375     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
0376     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
0377     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
0378     size_type s=0;
0379     BOOST_TRY{
0380       while(n--){
0381         if(push_back(x).second)++s;
0382       }
0383     }
0384     BOOST_CATCH(...){
0385       relocate(position,end()-s,end());
0386       BOOST_RETHROW;
0387     }
0388     BOOST_CATCH_END
0389     relocate(position,end()-s,end());
0390   }
0391
0392   template<typename InputIterator>
0393   void insert(iterator position,InputIterator first,InputIterator last)
0394   {
0395     insert_iter(position,first,last,mpl::not_<is_integral<InputIterator> >());
0396   }
0397
0398 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
0399   void insert(iterator position,std::initializer_list<value_type> list)
0400   {
0401     insert(position,list.begin(),list.end());
0402   }
0403 #endif
0404
0405   insert_return_type insert(const_iterator position,BOOST_RV_REF(node_type) nh)
0406   {
0407     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
0408     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
0409     if(nh)BOOST_MULTI_INDEX_CHECK_EQUAL_ALLOCATORS(*this,nh);
0410     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
0411     std::pair<final_node_type*,bool> p=this->final_insert_nh_(nh);
0412     if(p.second&&position.get_node()!=header()){
0413       relocate(position.get_node(),p.first);
0414     }
0415     return insert_return_type(make_iterator(p.first),p.second,boost::move(nh));
0416   }
0417
0418   node_type extract(const_iterator position)
0419   {
0420     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
0421     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
0422     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
0423     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
0424     return this->final_extract_(
0425       static_cast<final_node_type*>(position.get_node()));
0426   }
0427
0428   iterator erase(iterator position)
0429   {
0430     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
0431     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
0432     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
0433     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
0434     this->final_erase_(static_cast<final_node_type*>(position++.get_node()));
0435     return position;
0436   }
0437
0438   iterator erase(iterator first,iterator last)
0439   {
0440     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first);
0441     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last);
0442     BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,*this);
0443     BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,*this);
0444     BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last);
0445     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
0446     difference_type n=static_cast<difference_type>(last-first);
0447     relocate(end(),first,last);
0448     while(n--)pop_back();
0449     return last;
0450   }
0451
0452   bool replace(iterator position,const value_type& x)
0453   {
0454     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
0455     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
0456     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
0457     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
0458     return this->final_replace_(
0459       x,static_cast<final_node_type*>(position.get_node()));
0460   }
0461
0462   bool replace(iterator position,BOOST_RV_REF(value_type) x)
0463   {
0464     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
0465     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
0466     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
0467     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
0468     return this->final_replace_rv_(
0469       x,static_cast<final_node_type*>(position.get_node()));
0470   }
0471
0472   template<typename Modifier>
0473   bool modify(iterator position,Modifier mod)
0474   {
0475     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
0476     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
0477     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
0478     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
0479
0480 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
0481     /* MSVC++ 6.0 optimizer on safe mode code chokes if this
0482      * this is not added. Left it for all compilers as it does no
0483      * harm.
0484      */
0485
0486     position.detach();
0487 #endif
0488
0489     return this->final_modify_(
0490       mod,static_cast<final_node_type*>(position.get_node()));
0491   }
0492
0493   template<typename Modifier,typename Rollback>
0494   bool modify(iterator position,Modifier mod,Rollback back_)
0495   {
0496     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
0497     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
0498     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
0499     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
0500
0501 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
0502     /* MSVC++ 6.0 optimizer on safe mode code chokes if this
0503      * this is not added. Left it for all compilers as it does no
0504      * harm.
0505      */
0506
0507     position.detach();
0508 #endif
0509
0510     return this->final_modify_(
0511       mod,back_,static_cast<final_node_type*>(position.get_node()));
0512   }
0513
0514   void swap(random_access_index<SuperMeta,TagList>& x)
0515   {
0516     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
0517     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT_OF(x);
0518     this->final_swap_(x.final());
0519   }
0520
0521   void clear()BOOST_NOEXCEPT
0522   {
0523     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
0524     this->final_clear_();
0525   }
0526
0527   /* list operations */
0528
0529   template<typename Index>
0530   BOOST_MULTI_INDEX_ENABLE_IF_MERGEABLE(random_access_index,Index,void)
0531   splice(iterator position,Index& x)
0532   {
0533     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
0534     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
0535     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
0536     if(x.end().get_node()==this->header()){ /* same container */
0537       BOOST_MULTI_INDEX_SAFE_MODE_ASSERT(
0538         position==end(),safe_mode::inside_range);
0539     }
0540     else{
0541       external_splice(
0542         position,x,x.begin(),x.end(),
0543         boost::is_copy_constructible<value_type>());
0544     }
0545   }
0546
0547   template<typename Index>
0548   BOOST_MULTI_INDEX_ENABLE_IF_MERGEABLE(random_access_index,Index,void)
0549   splice(iterator position,BOOST_RV_REF(Index) x)
0550   {
0551     splice(position,static_cast<Index&>(x));
0552   }
0553
0554   template<typename Index>
0555   BOOST_MULTI_INDEX_ENABLE_IF_MERGEABLE(
0556     random_access_index,Index,pair_return_type)
0557   splice(
0558     iterator position,Index& x,BOOST_DEDUCED_TYPENAME Index::iterator i)
0559   {
0560     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
0561     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
0562     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(i);
0563     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(i);
0564     BOOST_MULTI_INDEX_CHECK_IS_OWNER(i,x);
0565     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
0566     if(x.end().get_node()==this->header()){ /* same container */
0567       index_node_type* pn=position.get_node();
0568       index_node_type* in=static_cast<index_node_type*>(i.get_node());
0569       if(pn!=in)relocate(pn,in);
0570       return std::pair<iterator,bool>(make_iterator(in),true);
0571     }
0572     else{
0573       std::pair<final_node_type*,bool> p=
0574         external_splice(
0575           position,x,i,boost::is_copy_constructible<value_type>());
0576       return std::pair<iterator,bool>(make_iterator(p.first),p.second);
0577     }
0578   }
0579
0580   template<typename Index>
0581   BOOST_MULTI_INDEX_ENABLE_IF_MERGEABLE(
0582     random_access_index,Index,pair_return_type)
0583   splice(
0584     iterator position,BOOST_RV_REF(Index) x,
0585     BOOST_DEDUCED_TYPENAME Index::iterator i)
0586   {
0587     return splice(position,static_cast<Index&>(x),i);
0588   }
0589
0590   template<typename Index>
0591   BOOST_MULTI_INDEX_ENABLE_IF_MERGEABLE(random_access_index,Index,void)
0592   splice(
0593     iterator position,Index& x,
0594     BOOST_DEDUCED_TYPENAME Index::iterator first,
0595     BOOST_DEDUCED_TYPENAME Index::iterator last)
0596   {
0597     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
0598     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
0599     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first);
0600     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last);
0601     BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,x);
0602     BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,x);
0603     BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last);
0604     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
0605     if(x.end().get_node()==this->header()){ /* same container */
0606       BOOST_MULTI_INDEX_CHECK_OUTSIDE_RANGE(position,first,last);
0607       internal_splice(position,first,last);
0608     }
0609     else{
0610       external_splice(
0611         position,x,first,last,boost::is_copy_constructible<value_type>());
0612     }
0613   }
0614
0615   template<typename Index>
0616   BOOST_MULTI_INDEX_ENABLE_IF_MERGEABLE(random_access_index,Index,void)
0617   splice(
0618     iterator position,BOOST_RV_REF(Index) x,
0619     BOOST_DEDUCED_TYPENAME Index::iterator first,
0620     BOOST_DEDUCED_TYPENAME Index::iterator last)
0621   {
0622     splice(position,static_cast<Index&>(x),first,last);
0623   }
0624
0625   void remove(value_param_type value)
0626   {
0627     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
0628     difference_type n=
0629       end()-make_iterator(
0630         random_access_index_remove<index_node_type>(
0631           ptrs,
0632           ::boost::bind<bool>(
0633             std::equal_to<value_type>(),::boost::arg<1>(),value)));
0634     while(n--)pop_back();
0635   }
0636
0637   template<typename Predicate>
0638   void remove_if(Predicate pred)
0639   {
0640     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
0641     difference_type n=
0642       end()-make_iterator(
0643         random_access_index_remove<index_node_type>(ptrs,pred));
0644     while(n--)pop_back();
0645   }
0646
0647   void unique()
0648   {
0649     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
0650     difference_type n=
0651       end()-make_iterator(
0652         random_access_index_unique<index_node_type>(
0653           ptrs,std::equal_to<value_type>()));
0654     while(n--)pop_back();
0655   }
0656
0657   template <class BinaryPredicate>
0658   void unique(BinaryPredicate binary_pred)
0659   {
0660     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
0661     difference_type n=
0662       end()-make_iterator(
0663         random_access_index_unique<index_node_type>(ptrs,binary_pred));
0664     while(n--)pop_back();
0665   }
0666
0667   void merge(random_access_index<SuperMeta,TagList>& x)
0668   {
0669     if(this!=&x){
0670       BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
0671       size_type s=size();
0672       splice(end(),x);
0673       random_access_index_inplace_merge<index_node_type>(
0674         get_allocator(),ptrs,ptrs.at(s),std::less<value_type>());
0675     }
0676   }
0677
0678   template <typename Compare>
0679   void merge(random_access_index<SuperMeta,TagList>& x,Compare comp)
0680   {
0681     if(this!=&x){
0682       BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
0683       size_type s=size();
0684       splice(end(),x);
0685       random_access_index_inplace_merge<index_node_type>(
0686         get_allocator(),ptrs,ptrs.at(s),comp);
0687     }
0688   }
0689
0690   void sort()
0691   {
0692     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
0693     random_access_index_sort<index_node_type>(
0694       get_allocator(),ptrs,std::less<value_type>());
0695   }
0696
0697   template <typename Compare>
0698   void sort(Compare comp)
0699   {
0700     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
0701     random_access_index_sort<index_node_type>(
0702       get_allocator(),ptrs,comp);
0703   }
0704
0705   void reverse()BOOST_NOEXCEPT
0706   {
0707     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
0708     node_impl_type::reverse(ptrs.begin(),ptrs.end());
0709   }
0710
0711   /* rearrange operations */
0712
0713   void relocate(iterator position,iterator i)
0714   {
0715     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
0716     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
0717     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(i);
0718     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(i);
0719     BOOST_MULTI_INDEX_CHECK_IS_OWNER(i,*this);
0720     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
0721     if(position!=i)relocate(position.get_node(),i.get_node());
0722   }
0723
0724   void relocate(iterator position,iterator first,iterator last)
0725   {
0726     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
0727     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
0728     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first);
0729     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last);
0730     BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,*this);
0731     BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,*this);
0732     BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last);
0733     BOOST_MULTI_INDEX_CHECK_OUTSIDE_RANGE(position,first,last);
0734     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
0735     if(position!=last)relocate(
0736       position.get_node(),first.get_node(),last.get_node());
0737   }
0738
0739   template<typename InputIterator>
0740   void rearrange(InputIterator first)
0741   {
0742     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
0743     for(node_impl_ptr_pointer p0=ptrs.begin(),p0_end=ptrs.end();
0744         p0!=p0_end;++first,++p0){
0745       const value_type& v1=*first;
0746       node_impl_ptr_pointer p1=node_from_value<index_node_type>(&v1)->up();
0747
0748       std::swap(*p0,*p1);
0749       (*p0)->up()=p0;
0750       (*p1)->up()=p1;
0751     }
0752   }
0753
0754 BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS:
0755   random_access_index(
0756     const ctor_args_list& args_list,const allocator_type& al):
0757     super(args_list.get_tail(),al),
0758     ptrs(al,header()->impl(),0)
0759
0760 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
0761     ,safe(*this)
0762 #endif
0763
0764   {
0765   }
0766
0767   random_access_index(const random_access_index<SuperMeta,TagList>& x):
0768     super(x),
0769     ptrs(x.get_allocator(),header()->impl(),x.size())
0770
0771 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
0772     ,safe(*this)
0773 #endif
0774
0775   {
0776     /* The actual copying takes place in subsequent call to copy_().
0777      */
0778   }
0779
0780   random_access_index(
0781     const random_access_index<SuperMeta,TagList>& x,do_not_copy_elements_tag):
0782     super(x,do_not_copy_elements_tag()),
0783     ptrs(x.get_allocator(),header()->impl(),0)
0784
0785 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
0786     ,safe(*this)
0787 #endif
0788
0789   {
0790   }
0791
0792   ~random_access_index()
0793   {
0794     /* the container is guaranteed to be empty by now */
0795   }
0796
0797 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
0798   iterator       make_iterator(index_node_type* node)
0799     {return iterator(node,&safe);}
0800   const_iterator make_iterator(index_node_type* node)const
0801     {return const_iterator(node,const_cast<safe_container*>(&safe));}
0802 #else
0803   iterator       make_iterator(index_node_type* node){return iterator(node);}
0804   const_iterator make_iterator(index_node_type* node)const
0805                    {return const_iterator(node);}
0806 #endif
0807
0808   void copy_(
0809     const random_access_index<SuperMeta,TagList>& x,const copy_map_type& map)
0810   {
0811     for(node_impl_ptr_pointer begin_org=x.ptrs.begin(),
0812                               begin_cpy=ptrs.begin(),
0813                               end_org=x.ptrs.end();
0814         begin_org!=end_org;++begin_org,++begin_cpy){
0815       *begin_cpy=
0816          static_cast<index_node_type*>(
0817            map.find(
0818              static_cast<final_node_type*>(
0819                index_node_type::from_impl(*begin_org))))->impl();
0820       (*begin_cpy)->up()=begin_cpy;
0821     }
0822
0823     super::copy_(x,map);
0824   }
0825
0826   template<typename Variant>
0827   final_node_type* insert_(
0828     value_param_type v,final_node_type*& x,Variant variant)
0829   {
0830     ptrs.room_for_one();
0831     final_node_type* res=super::insert_(v,x,variant);
0832     if(res==x)ptrs.push_back(static_cast<index_node_type*>(x)->impl());
0833     return res;
0834   }
0835
0836   template<typename Variant>
0837   final_node_type* insert_(
0838     value_param_type v,index_node_type* position,
0839     final_node_type*& x,Variant variant)
0840   {
0841     ptrs.room_for_one();
0842     final_node_type* res=super::insert_(v,position,x,variant);
0843     if(res==x)ptrs.push_back(static_cast<index_node_type*>(x)->impl());
0844     return res;
0845   }
0846
0847   template<typename Dst>
0848   void extract_(index_node_type* x,Dst dst)
0849   {
0850     ptrs.erase(x->impl());
0851     super::extract_(x,dst.next());
0852
0853 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
0854     transfer_iterators(dst.get(),x);
0855 #endif
0856   }
0857
0858   void delete_all_nodes_()
0859   {
0860     for(node_impl_ptr_pointer x=ptrs.begin(),x_end=ptrs.end();x!=x_end;++x){
0861       this->final_delete_node_(
0862         static_cast<final_node_type*>(index_node_type::from_impl(*x)));
0863     }
0864   }
0865
0866   void clear_()
0867   {
0868     super::clear_();
0869     ptrs.clear();
0870
0871 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
0872     safe.detach_dereferenceable_iterators();
0873 #endif
0874   }
0875
0876   template<typename BoolConstant>
0877   void swap_(
0878     random_access_index<SuperMeta,TagList>& x,BoolConstant swap_allocators)
0879   {
0880     ptrs.swap(x.ptrs,swap_allocators);
0881
0882 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
0883     safe.swap(x.safe);
0884 #endif
0885
0886     super::swap_(x,swap_allocators);
0887   }
0888
0889   void swap_elements_(random_access_index<SuperMeta,TagList>& x)
0890   {
0891     ptrs.swap(x.ptrs);
0892
0893 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
0894     safe.swap(x.safe);
0895 #endif
0896
0897     super::swap_elements_(x);
0898   }
0899
0900   template<typename Variant>
0901   bool replace_(value_param_type v,index_node_type* x,Variant variant)
0902   {
0903     return super::replace_(v,x,variant);
0904   }
0905
0906   bool modify_(index_node_type* x)
0907   {
0908     BOOST_TRY{
0909       if(!super::modify_(x)){
0910         ptrs.erase(x->impl());
0911
0912 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
0913         detach_iterators(x);
0914 #endif
0915
0916         return false;
0917       }
0918       else return true;
0919     }
0920     BOOST_CATCH(...){
0921       ptrs.erase(x->impl());
0922
0923 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
0924       detach_iterators(x);
0925 #endif
0926
0927       BOOST_RETHROW;
0928     }
0929     BOOST_CATCH_END
0930   }
0931
0932   bool modify_rollback_(index_node_type* x)
0933   {
0934     return super::modify_rollback_(x);
0935   }
0936
0937   bool check_rollback_(index_node_type* x)const
0938   {
0939     return super::check_rollback_(x);
0940   }
0941
0942 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
0943   /* serialization */
0944
0945   template<typename Archive>
0946   void save_(
0947     Archive& ar,const unsigned int version,const index_saver_type& sm)const
0948   {
0949     sm.save(begin(),end(),ar,version);
0950     super::save_(ar,version,sm);
0951   }
0952
0953   template<typename Archive>
0954   void load_(
0955     Archive& ar,const unsigned int version,const index_loader_type& lm)
0956   {
0957     {
0958       typedef random_access_index_loader<
0959         index_node_type,allocator_type> loader;
0960
0961       loader ld(get_allocator(),ptrs);
0962       lm.load(
0963         ::boost::bind(
0964           &loader::rearrange,&ld,::boost::arg<1>(),::boost::arg<2>()),
0965         ar,version);
0966     } /* exit scope so that ld frees its resources */
0967     super::load_(ar,version,lm);
0968   }
0969 #endif
0970
0971 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
0972   /* invariant stuff */
0973
0974   bool invariant_()const
0975   {
0976     if(size()>capacity())return false;
0977     if(size()==0||begin()==end()){
0978       if(size()!=0||begin()!=end())return false;
0979     }
0980     else{
0981       size_type s=0;
0982       for(const_iterator it=begin(),it_end=end();;++it,++s){
0983         if(*(it.get_node()->up())!=it.get_node()->impl())return false;
0984         if(it==it_end)break;
0985       }
0986       if(s!=size())return false;
0987     }
0988
0989     return super::invariant_();
0990   }
0991
0992   /* This forwarding function eases things for the boost::mem_fn construct
0993    * in BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT. Actually,
0994    * final_check_invariant is already an inherited member function of index.
0995    */
0996   void check_invariant_()const{this->final_check_invariant_();}
0997 #endif
0998
0999 private:
1000   index_node_type* header()const{return this->final_header();}
1001
1002   static void relocate(index_node_type* position,index_node_type* x)
1003   {
1004     node_impl_type::relocate(position->up(),x->up());
1005   }
1006
1007   static void relocate(
1008     index_node_type* position,index_node_type* first,index_node_type* last)
1009   {
1010     node_impl_type::relocate(
1011       position->up(),first->up(),last->up());
1012   }
1013
1014 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1015   void detach_iterators(index_node_type* x)
1016   {
1017     iterator it=make_iterator(x);
1018     safe_mode::detach_equivalent_iterators(it);
1019   }
1020
1021   template<typename Dst>
1022   void transfer_iterators(Dst& dst,index_node_type* x)
1023   {
1024     iterator it=make_iterator(x);
1025     safe_mode::transfer_equivalent_iterators(dst,it);
1026   }
1027 #endif
1028
1029   template <class InputIterator>
1030   void assign_iter(InputIterator first,InputIterator last,mpl::true_)
1031   {
1032     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
1033     clear();
1034     for(;first!=last;++first)this->final_insert_ref_(*first);
1035   }
1036
1037   void assign_iter(size_type n,value_param_type value,mpl::false_)
1038   {
1039     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
1040     clear();
1041     for(size_type i=0;i<n;++i)push_back(value);
1042   }
1043
1044   template<typename InputIterator>
1045   void insert_iter(
1046     iterator position,InputIterator first,InputIterator last,mpl::true_)
1047   {
1048     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
1049     size_type s=0;
1050     BOOST_TRY{
1051       for(;first!=last;++first){
1052         if(this->final_insert_ref_(*first).second)++s;
1053       }
1054     }
1055     BOOST_CATCH(...){
1056       relocate(position,end()-s,end());
1057       BOOST_RETHROW;
1058     }
1059     BOOST_CATCH_END
1060     relocate(position,end()-s,end());
1061   }
1062
1063   void insert_iter(
1064     iterator position,size_type n,value_param_type x,mpl::false_)
1065   {
1066     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
1067     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
1068     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
1069     size_type  s=0;
1070     BOOST_TRY{
1071       while(n--){
1072         if(push_back(x).second)++s;
1073       }
1074     }
1075     BOOST_CATCH(...){
1076       relocate(position,end()-s,end());
1077       BOOST_RETHROW;
1078     }
1079     BOOST_CATCH_END
1080     relocate(position,end()-s,end());
1081   }
1082
1083   template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK>
1084   std::pair<iterator,bool> emplace_front_impl(
1085     BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK)
1086   {
1087     return emplace_impl(begin(),BOOST_MULTI_INDEX_FORWARD_PARAM_PACK);
1088   }
1089
1090   template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK>
1091   std::pair<iterator,bool> emplace_back_impl(
1092     BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK)
1093   {
1094     return emplace_impl(end(),BOOST_MULTI_INDEX_FORWARD_PARAM_PACK);
1095   }
1096
1097   template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK>
1098   std::pair<iterator,bool> emplace_impl(
1099     iterator position,BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK)
1100   {
1101     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
1102     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
1103     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
1104     std::pair<final_node_type*,bool> p=
1105       this->final_emplace_(BOOST_MULTI_INDEX_FORWARD_PARAM_PACK);
1106     if(p.second&&position.get_node()!=header()){
1107       relocate(position.get_node(),p.first);
1108     }
1109     return std::pair<iterator,bool>(make_iterator(p.first),p.second);
1110   }
1111
1112   template<typename Index>
1113   std::pair<final_node_type*,bool> external_splice(
1114     iterator position,Index& x,BOOST_DEDUCED_TYPENAME Index::iterator i,
1115     boost::true_type /* copy-constructible value */)
1116   {
1117     if(get_allocator()==x.get_allocator()){
1118       return external_splice(position,x,i,boost::false_type());
1119     }
1120     else{
1121       /* backwards compatibility with old, non-transfer-based splice */
1122
1123       std::pair<iterator,bool> p=insert(position,*i);
1124       if(p.second)x.erase(i);
1125       return std::pair<final_node_type*,bool>(
1126         static_cast<final_node_type*>(p.first.get_node()),p.second);
1127     }
1128   }
1129
1130   template<typename Index>
1131   std::pair<final_node_type*,bool> external_splice(
1132     iterator position,Index& x,BOOST_DEDUCED_TYPENAME Index::iterator i,
1133     boost::false_type /* copy-constructible value */)
1134   {
1135     BOOST_MULTI_INDEX_CHECK_EQUAL_ALLOCATORS(*this,x);
1136     std::pair<final_node_type*,bool> p=this->final_transfer_(
1137       x,static_cast<final_node_type*>(i.get_node()));
1138     if(p.second&&position.get_node()!=header()){
1139       relocate(position.get_node(),p.first);
1140     }
1141     return p;
1142   }
1143
1144   template<typename Iterator>
1145   void internal_splice(iterator position,Iterator first,Iterator last)
1146   {
1147     /* null out [first, last) positions in ptrs array */
1148
1149     for(Iterator it=first;it!=last;++it){
1150       *(static_cast<index_node_type*>(it.get_node())->up())=0;
1151     }
1152
1153     node_impl_ptr_pointer pp=node_impl_type::gather_nulls(
1154       ptrs.begin(),ptrs.end(),
1155       static_cast<index_node_type*>(position.get_node())->up());
1156
1157     /* relink [first, last) */
1158
1159     for(Iterator it=first;it!=last;++it,++pp){
1160       *pp=static_cast<index_node_type*>(it.get_node());
1161       (*pp)->up()=pp;
1162     }
1163   }
1164
1165   void internal_splice(iterator position,iterator first,iterator last)
1166   {
1167     index_node_type* pn=position.get_node();
1168     index_node_type* fn=static_cast<index_node_type*>(first.get_node());
1169     index_node_type* ln=static_cast<index_node_type*>(last.get_node());
1170     if(pn!=ln)relocate(pn,fn,ln);
1171   }
1172
1173   template<typename Index>
1174   void external_splice(
1175     iterator position,Index& x,
1176     BOOST_DEDUCED_TYPENAME Index::iterator first,
1177     BOOST_DEDUCED_TYPENAME Index::iterator last,
1178     boost::true_type /* copy-constructible value */)
1179   {
1180     if(get_allocator()==x.get_allocator()){
1181       external_splice(position,x,first,last,boost::false_type());
1182     }
1183     else{
1184       /* backwards compatibility with old, non-transfer-based splice */
1185
1186       size_type n=size();
1187       BOOST_TRY{
1188         while(first!=last){
1189           if(push_back(*first).second)first=x.erase(first);
1190           else ++first;
1191         }
1192       }
1193       BOOST_CATCH(...){
1194         relocate(position,begin()+n,end());
1195         BOOST_RETHROW;
1196       }
1197       BOOST_CATCH_END
1198       relocate(position,begin()+n,end());
1199     }
1200   }
1201
1202   template<typename Index>
1203   void external_splice(
1204     iterator position,Index& x,
1205     BOOST_DEDUCED_TYPENAME Index::iterator first,
1206     BOOST_DEDUCED_TYPENAME Index::iterator last,
1207     boost::false_type /* copy-constructible value */)
1208   {
1209     BOOST_MULTI_INDEX_CHECK_EQUAL_ALLOCATORS(*this,x);
1210     size_type n=size();
1211     BOOST_TRY{
1212       this->final_transfer_range_(x,first,last);
1213     }
1214     BOOST_CATCH(...){
1215       relocate(position,begin()+n,end());
1216       BOOST_RETHROW;
1217     }
1218     BOOST_CATCH_END
1219     relocate(position,begin()+n,end());
1220   }
1221
1222   ptr_array      ptrs;
1223
1224 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1225   safe_container safe;
1226 #endif
1227
1228 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
1229     BOOST_WORKAROUND(__MWERKS__,<=0x3003)
1230 #pragma parse_mfunc_templ reset
1231 #endif
1232 };
1233
1234 #if defined(BOOST_MSVC)
1235 #pragma warning(pop) /* C4355 */
1236 #endif
1237
1238 /* comparison */
1239
1240 template<
1241   typename SuperMeta1,typename TagList1,
1242   typename SuperMeta2,typename TagList2
1243 >
1244 bool operator==(
1245   const random_access_index<SuperMeta1,TagList1>& x,
1246   const random_access_index<SuperMeta2,TagList2>& y)
1247 {
1248   return x.size()==y.size()&&std::equal(x.begin(),x.end(),y.begin());
1249 }
1250
1251 template<
1252   typename SuperMeta1,typename TagList1,
1253   typename SuperMeta2,typename TagList2
1254 >
1255 bool operator<(
1256   const random_access_index<SuperMeta1,TagList1>& x,
1257   const random_access_index<SuperMeta2,TagList2>& y)
1258 {
1259   return std::lexicographical_compare(x.begin(),x.end(),y.begin(),y.end());
1260 }
1261
1262 template<
1263   typename SuperMeta1,typename TagList1,
1264   typename SuperMeta2,typename TagList2
1265 >
1266 bool operator!=(
1267   const random_access_index<SuperMeta1,TagList1>& x,
1268   const random_access_index<SuperMeta2,TagList2>& y)
1269 {
1270   return !(x==y);
1271 }
1272
1273 template<
1274   typename SuperMeta1,typename TagList1,
1275   typename SuperMeta2,typename TagList2
1276 >
1277 bool operator>(
1278   const random_access_index<SuperMeta1,TagList1>& x,
1279   const random_access_index<SuperMeta2,TagList2>& y)
1280 {
1281   return y<x;
1282 }
1283
1284 template<
1285   typename SuperMeta1,typename TagList1,
1286   typename SuperMeta2,typename TagList2
1287 >
1288 bool operator>=(
1289   const random_access_index<SuperMeta1,TagList1>& x,
1290   const random_access_index<SuperMeta2,TagList2>& y)
1291 {
1292   return !(x<y);
1293 }
1294
1295 template<
1296   typename SuperMeta1,typename TagList1,
1297   typename SuperMeta2,typename TagList2
1298 >
1299 bool operator<=(
1300   const random_access_index<SuperMeta1,TagList1>& x,
1301   const random_access_index<SuperMeta2,TagList2>& y)
1302 {
1303   return !(x>y);
1304 }
1305
1306 /*  specialized algorithms */
1307
1308 template<typename SuperMeta,typename TagList>
1309 void swap(
1310   random_access_index<SuperMeta,TagList>& x,
1311   random_access_index<SuperMeta,TagList>& y)
1312 {
1313   x.swap(y);
1314 }
1315
1316 } /* namespace multi_index::detail */
1317
1318 /* random access index specifier */
1319
1320 template <typename TagList>
1321 struct random_access
1322 {
1323   BOOST_STATIC_ASSERT(detail::is_tag<TagList>::value);
1324
1325   template<typename Super>
1326   struct node_class
1327   {
1328     typedef detail::random_access_index_node<Super> type;
1329   };
1330
1331   template<typename SuperMeta>
1332   struct index_class
1333   {
1334     typedef detail::random_access_index<
1335       SuperMeta,typename TagList::type>  type;
1336   };
1337 };
1338
1339 } /* namespace multi_index */
1340
1341 } /* namespace boost */
1342
1343 /* Boost.Foreach compatibility */
1344
1345 namespace boost{
1346 namespace foreach{
1347
1348 template<typename>
1349 struct is_noncopyable;
1350
1351 template<typename SuperMeta,typename TagList>
1352 struct is_noncopyable<
1353   boost::multi_index::detail::random_access_index<SuperMeta,TagList>
1354 >:boost::mpl::true_{};
1355
1356 }
1357 }
1358
1359 #undef BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT
1360 #undef BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT_OF
1361
1362 #endif