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)
6 * See http://www.boost.org/libs/multi_index for library home page.
9 #ifndef BOOST_MULTI_INDEX_RANDOM_ACCESS_INDEX_HPP
10 #define BOOST_MULTI_INDEX_RANDOM_ACCESS_INDEX_HPP
12 #if defined(_MSC_VER)&&(_MSC_VER>=1200)
16 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
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>
40 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
41 #include <boost/bind.hpp>
42 #include <boost/multi_index/detail/rnd_index_loader.hpp>
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();
51 #define BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT
56 namespace multi_index{
60 /* random_access_index adds a layer of random access indexing
64 template<typename SuperMeta,typename TagList>
65 class random_access_index:
66 BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS SuperMeta::type
68 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
69 #if BOOST_WORKAROUND(BOOST_MSVC,<1300)
70 ,public safe_ctr_proxy_impl<
72 random_access_index_node<typename SuperMeta::type::node_type> >,
73 random_access_index<SuperMeta,TagList> >
75 ,public safe_mode::safe_container<
76 random_access_index<SuperMeta,TagList> >
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
88 #pragma parse_mfunc_templ off
91 typedef typename SuperMeta::type super;
94 typedef random_access_index_node<
95 typename super::node_type> node_type;
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;
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>,
111 rnd_node_iterator<node_type> > > iterator;
113 typedef safe_mode::safe_iterator<
114 rnd_node_iterator<node_type>,
115 random_access_index> iterator;
118 typedef rnd_node_iterator<node_type> iterator;
121 typedef iterator const_iterator;
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;
128 boost::reverse_iterator<iterator> reverse_iterator;
130 boost::reverse_iterator<const_iterator> const_reverse_iterator;
131 typedef TagList tag_list;
134 typedef typename super::final_node_type final_node_type;
135 typedef tuples::cons<
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;
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;
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;
161 typedef safe_mode::safe_container<
162 random_access_index> safe_super;
166 typedef typename call_traits<
167 value_type>::param_type value_param_type;
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.
176 random_access_index<SuperMeta,TagList>& operator=(
177 const random_access_index<SuperMeta,TagList>& x)
179 this->final()=x.final();
183 template <class InputIterator>
184 void assign(InputIterator first,InputIterator last)
186 BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
188 for(;first!=last;++first)push_back(*first);
191 void assign(size_type n,value_param_type value)
193 BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
195 for(size_type i=0;i<n;++i)push_back(value);
198 allocator_type get_allocator()const
200 return this->final().get_allocator();
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());}
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);}
224 void resize(size_type n,value_param_type x=value_type())
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());
231 /* access: no non-const versions provided as random_access_index
232 * handles const elements.
235 const_reference operator[](size_type n)const
237 BOOST_MULTI_INDEX_SAFE_MODE_ASSERT(n<size(),safe_mode::out_of_bounds);
238 return node_type::from_impl(*ptrs.at(n))->value();
241 const_reference at(size_type n)const
243 if(n>=size())throw_exception(std::out_of_range("random access index"));
244 return node_type::from_impl(*ptrs.at(n))->value();
247 const_reference front()const{return operator[](0);}
248 const_reference back()const{return operator[](size()-1);}
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());}
259 std::pair<iterator,bool> insert(iterator position,value_param_type x)
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);
268 return std::pair<iterator,bool>(make_iterator(p.first),p.second);
271 void insert(iterator position,size_type n,value_param_type x)
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;
279 if(push_back(x).second)++s;
283 relocate(position,end()-s,end());
287 relocate(position,end()-s,end());
290 template<typename InputIterator>
291 void insert(iterator position,InputIterator first,InputIterator last)
293 BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
296 for(;first!=last;++first){
297 if(push_back(*first).second)++s;
301 relocate(position,end()-s,end());
305 relocate(position,end()-s,end());
308 iterator erase(iterator position)
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()));
318 iterator erase(iterator first,iterator last)
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();
332 bool replace(iterator position,value_param_type x)
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()));
342 template<typename Modifier>
343 bool modify(iterator position,Modifier mod)
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;
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
359 return this->final_modify_(
360 mod,static_cast<final_node_type*>(position.get_node()));
363 void swap(random_access_index<SuperMeta,TagList>& x)
365 BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
366 this->final_swap_(x.final());
371 BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
372 this->final_clear_();
375 /* list operations */
377 void splice(iterator position,random_access_index<SuperMeta,TagList>& x)
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();
387 if(push_back(*first).second){
388 first=x.erase(first);
395 relocate(position,end()-n,end());
399 relocate(position,end()-n,end());
403 iterator position,random_access_index<SuperMeta,TagList>& x,iterator i)
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);
413 if(insert(position,*i).second){
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
421 x.erase(x.make_iterator(i.get_node()));
431 iterator position,random_access_index<SuperMeta,TagList>& x,
432 iterator first,iterator last)
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);
447 if(push_back(*first).second){
448 first=x.erase(first);
455 relocate(position,end()-n,end());
459 relocate(position,end()-n,end());
463 void remove(value_param_type value)
465 BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
468 random_access_index_remove<node_type>(
469 ptrs,std::bind2nd(std::equal_to<value_type>(),value)));
470 while(n--)pop_back();
473 template<typename Predicate>
474 void remove_if(Predicate pred)
476 BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
478 end()-make_iterator(random_access_index_remove<node_type>(ptrs,pred));
479 while(n--)pop_back();
484 BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
487 random_access_index_unique<node_type>(
488 ptrs,std::equal_to<value_type>()));
489 while(n--)pop_back();
492 template <class BinaryPredicate>
493 void unique(BinaryPredicate binary_pred)
495 BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
498 random_access_index_unique<node_type>(ptrs,binary_pred));
499 while(n--)pop_back();
502 void merge(random_access_index<SuperMeta,TagList>& x)
505 BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
508 random_access_index_inplace_merge<node_type>(
509 get_allocator(),ptrs,ptrs.at(s),std::less<value_type>());
513 template <typename Compare>
514 void merge(random_access_index<SuperMeta,TagList>& x,Compare comp)
517 BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
520 random_access_index_inplace_merge<node_type>(
521 get_allocator(),ptrs,ptrs.at(s),comp);
527 BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
528 random_access_index_sort<node_type>(
529 get_allocator(),ptrs,std::less<value_type>());
532 template <typename Compare>
533 void sort(Compare comp)
535 BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
536 random_access_index_sort<node_type>(
537 get_allocator(),ptrs,comp);
542 BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
543 random_access_index_node_impl::reverse(ptrs.begin(),ptrs.end());
546 /* rearrange operations */
548 void relocate(iterator position,iterator i)
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());
559 void relocate(iterator position,iterator first,iterator last)
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());
574 template<typename InputIterator>
575 void rearrange(InputIterator first)
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();
589 BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS:
591 const ctor_args_list& args_list,const allocator_type& al):
592 super(args_list.get_tail(),al),
593 ptrs(al,header()->impl(),0)
597 random_access_index(const random_access_index<SuperMeta,TagList>& x):
600 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
604 ptrs(x.get_allocator(),header()->impl(),x.size())
606 /* The actual copying takes place in subsequent call to copy_().
610 ~random_access_index()
612 /* the container is guaranteed to be empty by now */
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));}
620 iterator make_iterator(node_type* node){return iterator(node);}
621 const_iterator make_iterator(node_type* node)const
622 {return const_iterator(node);}
626 const random_access_index<SuperMeta,TagList>& x,const copy_map_type& map)
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){
633 static_cast<node_type*>(
635 static_cast<final_node_type*>(
636 node_type::from_impl(*begin_org))))->impl();
637 (*begin_cpy)->up()=begin_cpy;
643 node_type* insert_(value_param_type v,node_type* x)
646 node_type* res=static_cast<node_type*>(super::insert_(v,x));
647 if(res==x)ptrs.push_back(x->impl());
651 node_type* insert_(value_param_type v,node_type* position,node_type* x)
654 node_type* res=static_cast<node_type*>(super::insert_(v,position,x));
655 if(res==x)ptrs.push_back(x->impl());
659 void erase_(node_type* x)
661 ptrs.erase(x->impl());
664 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
669 void delete_all_nodes_()
671 for(random_access_index_node_impl** x=ptrs.begin(),**x_end=ptrs.end();
673 this->final_delete_node_(
674 static_cast<final_node_type*>(node_type::from_impl(*x)));
683 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
684 safe_super::detach_dereferenceable_iterators();
688 void swap_(random_access_index<SuperMeta,TagList>& x)
692 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
699 bool replace_(value_param_type v,node_type* x)
701 return super::replace_(v,x);
704 bool modify_(node_type* x)
707 if(!super::modify_(x)){
708 ptrs.erase(x->impl());
710 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
719 ptrs.erase(x->impl());
721 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
730 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
733 template<typename Archive>
735 Archive& ar,const unsigned int version,const index_saver_type& sm)const
737 sm.save(begin(),end(),ar,version);
738 super::save_(ar,version,sm);
741 template<typename Archive>
743 Archive& ar,const unsigned int version,const index_loader_type& lm)
746 typedef random_access_index_loader<node_type,allocator_type> loader;
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);
755 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
756 /* invariant stuff */
758 bool invariant_()const
760 if(size()>capacity())return false;
761 if(size()==0||begin()==end()){
762 if(size()!=0||begin()!=end())return false;
766 for(const_iterator it=begin(),it_end=end();;++it,++s){
767 if(*(it.get_node()->up())!=it.get_node()->impl())return false;
770 if(s!=size())return false;
773 return super::invariant_();
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.
780 void check_invariant_()const{this->final_check_invariant_();}
784 node_type* header()const{return this->final_header();}
786 static void relocate(node_type* position,node_type* x)
788 random_access_index_node_impl::relocate(position->up(),x->up());
791 static void relocate(node_type* position,node_type* first,node_type* last)
793 random_access_index_node_impl::relocate(
794 position->up(),first->up(),last->up());
797 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
798 void detach_iterators(node_type* x)
800 iterator it=make_iterator(x);
801 safe_mode::detach_equivalent_iterators(it);
805 random_access_index_ptr_array<typename super::final_allocator_type> ptrs;
807 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
808 BOOST_WORKAROUND(__MWERKS__,<=0x3003)
809 #pragma parse_mfunc_templ reset
816 typename SuperMeta1,typename TagList1,
817 typename SuperMeta2,typename TagList2
820 const random_access_index<SuperMeta1,TagList1>& x,
821 const random_access_index<SuperMeta2,TagList2>& y)
823 return x.size()==y.size()&&std::equal(x.begin(),x.end(),y.begin());
827 typename SuperMeta1,typename TagList1,
828 typename SuperMeta2,typename TagList2
831 const random_access_index<SuperMeta1,TagList1>& x,
832 const random_access_index<SuperMeta2,TagList2>& y)
834 return std::lexicographical_compare(x.begin(),x.end(),y.begin(),y.end());
838 typename SuperMeta1,typename TagList1,
839 typename SuperMeta2,typename TagList2
842 const random_access_index<SuperMeta1,TagList1>& x,
843 const random_access_index<SuperMeta2,TagList2>& y)
849 typename SuperMeta1,typename TagList1,
850 typename SuperMeta2,typename TagList2
853 const random_access_index<SuperMeta1,TagList1>& x,
854 const random_access_index<SuperMeta2,TagList2>& y)
860 typename SuperMeta1,typename TagList1,
861 typename SuperMeta2,typename TagList2
864 const random_access_index<SuperMeta1,TagList1>& x,
865 const random_access_index<SuperMeta2,TagList2>& y)
871 typename SuperMeta1,typename TagList1,
872 typename SuperMeta2,typename TagList2
875 const random_access_index<SuperMeta1,TagList1>& x,
876 const random_access_index<SuperMeta2,TagList2>& y)
881 /* specialized algorithms */
883 template<typename SuperMeta,typename TagList>
885 random_access_index<SuperMeta,TagList>& x,
886 random_access_index<SuperMeta,TagList>& y)
891 } /* namespace multi_index::detail */
893 /* random access index specifier */
895 template <typename TagList>
898 BOOST_STATIC_ASSERT(detail::is_tag<TagList>::value);
900 template<typename Super>
903 typedef detail::random_access_index_node<Super> type;
906 template<typename SuperMeta>
909 typedef detail::random_access_index<
910 SuperMeta,typename TagList::type> type;
914 } /* namespace multi_index */
916 } /* namespace boost */
918 #undef BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT