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/bool.hpp>
23 #include <boost/mpl/not.hpp>
24 #include <boost/mpl/push_front.hpp>
25 #include <boost/multi_index/detail/access_specifier.hpp>
26 #include <boost/multi_index/detail/index_node_base.hpp>
27 #include <boost/multi_index/detail/rnd_node_iterator.hpp>
28 #include <boost/multi_index/detail/rnd_index_node.hpp>
29 #include <boost/multi_index/detail/rnd_index_ops.hpp>
30 #include <boost/multi_index/detail/rnd_index_ptr_array.hpp>
31 #include <boost/multi_index/detail/safe_ctr_proxy.hpp>
32 #include <boost/multi_index/detail/safe_mode.hpp>
33 #include <boost/multi_index/detail/scope_guard.hpp>
34 #include <boost/multi_index/random_access_index_fwd.hpp>
35 #include <boost/throw_exception.hpp>
36 #include <boost/tuple/tuple.hpp>
37 #include <boost/type_traits/is_integral.hpp>
43 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
44 #include <boost/bind.hpp>
45 #include <boost/multi_index/detail/rnd_index_loader.hpp>
48 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
49 #define BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT \
50 detail::scope_guard BOOST_JOIN(check_invariant_,__LINE__)= \
51 detail::make_obj_guard(*this,&random_access_index::check_invariant_); \
52 BOOST_JOIN(check_invariant_,__LINE__).touch();
54 #define BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT
59 namespace multi_index{
63 /* random_access_index adds a layer of random access indexing
67 template<typename SuperMeta,typename TagList>
68 class random_access_index:
69 BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS SuperMeta::type
71 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
72 #if BOOST_WORKAROUND(BOOST_MSVC,<1300)
73 ,public safe_ctr_proxy_impl<
75 random_access_index_node<typename SuperMeta::type::node_type> >,
76 random_access_index<SuperMeta,TagList> >
78 ,public safe_mode::safe_container<
79 random_access_index<SuperMeta,TagList> >
84 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
85 BOOST_WORKAROUND(__MWERKS__,<=0x3003)
86 /* The "ISO C++ Template Parser" option in CW8.3 has a problem with the
87 * lifetime of const references bound to temporaries --precisely what
91 #pragma parse_mfunc_templ off
94 typedef typename SuperMeta::type super;
97 typedef random_access_index_node<
98 typename super::node_type> node_type;
101 typedef typename node_type::impl_type node_impl_type;
102 typedef random_access_index_ptr_array<
103 typename super::final_allocator_type> ptr_array;
104 typedef typename ptr_array::pointer node_impl_ptr_pointer;
109 typedef typename node_type::value_type value_type;
110 typedef tuples::null_type ctor_args;
111 typedef typename super::final_allocator_type allocator_type;
112 typedef typename allocator_type::reference reference;
113 typedef typename allocator_type::const_reference const_reference;
115 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
116 #if BOOST_WORKAROUND(BOOST_MSVC,<1300)
117 typedef safe_mode::safe_iterator<
118 rnd_node_iterator<node_type>,
120 rnd_node_iterator<node_type> > > iterator;
122 typedef safe_mode::safe_iterator<
123 rnd_node_iterator<node_type>,
124 random_access_index> iterator;
127 typedef rnd_node_iterator<node_type> iterator;
130 typedef iterator const_iterator;
132 typedef std::size_t size_type;
133 typedef std::ptrdiff_t difference_type;
134 typedef typename allocator_type::pointer pointer;
135 typedef typename allocator_type::const_pointer const_pointer;
137 boost::reverse_iterator<iterator> reverse_iterator;
139 boost::reverse_iterator<const_iterator> const_reverse_iterator;
140 typedef TagList tag_list;
143 typedef typename super::final_node_type final_node_type;
144 typedef tuples::cons<
146 typename super::ctor_args_list> ctor_args_list;
147 typedef typename mpl::push_front<
148 typename super::index_type_list,
149 random_access_index>::type index_type_list;
150 typedef typename mpl::push_front<
151 typename super::iterator_type_list,
152 iterator>::type iterator_type_list;
153 typedef typename mpl::push_front<
154 typename super::const_iterator_type_list,
155 const_iterator>::type const_iterator_type_list;
156 typedef typename super::copy_map_type copy_map_type;
158 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
159 typedef typename super::index_saver_type index_saver_type;
160 typedef typename super::index_loader_type index_loader_type;
164 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
165 #if BOOST_WORKAROUND(BOOST_MSVC,<1300)
166 typedef safe_ctr_proxy_impl<
167 rnd_node_iterator<node_type>,
168 random_access_index> safe_super;
170 typedef safe_mode::safe_container<
171 random_access_index> safe_super;
175 typedef typename call_traits<
176 value_type>::param_type value_param_type;
180 /* construct/copy/destroy
181 * Default and copy ctors are in the protected section as indices are
182 * not supposed to be created on their own. No range ctor either.
185 random_access_index<SuperMeta,TagList>& operator=(
186 const random_access_index<SuperMeta,TagList>& x)
188 this->final()=x.final();
192 template <class InputIterator>
193 void assign(InputIterator first,InputIterator last)
195 assign_iter(first,last,mpl::not_<is_integral<InputIterator> >());
198 void assign(size_type n,value_param_type value)
200 BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
202 for(size_type i=0;i<n;++i)push_back(value);
205 allocator_type get_allocator()const
207 return this->final().get_allocator();
213 {return make_iterator(node_type::from_impl(*ptrs.begin()));}
214 const_iterator begin()const
215 {return make_iterator(node_type::from_impl(*ptrs.begin()));}
216 iterator end(){return make_iterator(header());}
217 const_iterator end()const{return make_iterator(header());}
218 reverse_iterator rbegin(){return make_reverse_iterator(end());}
219 const_reverse_iterator rbegin()const{return make_reverse_iterator(end());}
220 reverse_iterator rend(){return make_reverse_iterator(begin());}
221 const_reverse_iterator rend()const{return make_reverse_iterator(begin());}
222 const_iterator cbegin()const{return begin();}
223 const_iterator cend()const{return end();}
224 const_reverse_iterator crbegin()const{return rbegin();}
225 const_reverse_iterator crend()const{return rend();}
227 iterator iterator_to(const value_type& x)
229 return make_iterator(node_from_value<node_type>(&x));
232 const_iterator iterator_to(const value_type& x)const
234 return make_iterator(node_from_value<node_type>(&x));
239 bool empty()const{return this->final_empty_();}
240 size_type size()const{return this->final_size_();}
241 size_type max_size()const{return this->final_max_size_();}
242 size_type capacity()const{return ptrs.capacity();}
243 void reserve(size_type n){ptrs.reserve(n);}
245 void resize(size_type n,value_param_type x=value_type())
247 BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
248 if(n>size())insert(end(),n-size(),x);
249 else if(n<size())erase(begin()+n,end());
252 /* access: no non-const versions provided as random_access_index
253 * handles const elements.
256 const_reference operator[](size_type n)const
258 BOOST_MULTI_INDEX_SAFE_MODE_ASSERT(n<size(),safe_mode::out_of_bounds);
259 return node_type::from_impl(*ptrs.at(n))->value();
262 const_reference at(size_type n)const
264 if(n>=size())throw_exception(std::out_of_range("random access index"));
265 return node_type::from_impl(*ptrs.at(n))->value();
268 const_reference front()const{return operator[](0);}
269 const_reference back()const{return operator[](size()-1);}
273 std::pair<iterator,bool> push_front(value_param_type x)
274 {return insert(begin(),x);}
275 void pop_front(){erase(begin());}
276 std::pair<iterator,bool> push_back(value_param_type x)
277 {return insert(end(),x);}
278 void pop_back(){erase(--end());}
280 std::pair<iterator,bool> insert(iterator position,value_param_type x)
282 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
283 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
284 BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
285 std::pair<final_node_type*,bool> p=this->final_insert_(x);
286 if(p.second&&position.get_node()!=header()){
287 relocate(position.get_node(),p.first);
289 return std::pair<iterator,bool>(make_iterator(p.first),p.second);
292 void insert(iterator position,size_type n,value_param_type x)
294 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
295 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
296 BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
300 if(push_back(x).second)++s;
304 relocate(position,end()-s,end());
308 relocate(position,end()-s,end());
311 template<typename InputIterator>
312 void insert(iterator position,InputIterator first,InputIterator last)
314 insert_iter(position,first,last,mpl::not_<is_integral<InputIterator> >());
317 iterator erase(iterator position)
319 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
320 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
321 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
322 BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
323 this->final_erase_(static_cast<final_node_type*>(position++.get_node()));
327 iterator erase(iterator first,iterator last)
329 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first);
330 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last);
331 BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,*this);
332 BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,*this);
333 BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last);
334 BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
335 difference_type n=last-first;
336 relocate(end(),first,last);
337 while(n--)pop_back();
341 bool replace(iterator position,value_param_type x)
343 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
344 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
345 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
346 BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
347 return this->final_replace_(
348 x,static_cast<final_node_type*>(position.get_node()));
351 template<typename Modifier>
352 bool modify(iterator position,Modifier mod)
354 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
355 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
356 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
357 BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
359 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
360 /* MSVC++ 6.0 optimizer on safe mode code chokes if this
361 * this is not added. Left it for all compilers as it does no
368 return this->final_modify_(
369 mod,static_cast<final_node_type*>(position.get_node()));
372 template<typename Modifier,typename Rollback>
373 bool modify(iterator position,Modifier mod,Rollback back)
375 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
376 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
377 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
378 BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
380 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
381 /* MSVC++ 6.0 optimizer on safe mode code chokes if this
382 * this is not added. Left it for all compilers as it does no
389 return this->final_modify_(
390 mod,back,static_cast<final_node_type*>(position.get_node()));
393 void swap(random_access_index<SuperMeta,TagList>& x)
395 BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
396 this->final_swap_(x.final());
401 BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
402 this->final_clear_();
405 /* list operations */
407 void splice(iterator position,random_access_index<SuperMeta,TagList>& x)
409 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
410 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
411 BOOST_MULTI_INDEX_CHECK_DIFFERENT_CONTAINER(*this,x);
412 BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
413 iterator first=x.begin(),last=x.end();
417 if(push_back(*first).second){
418 first=x.erase(first);
425 relocate(position,end()-n,end());
429 relocate(position,end()-n,end());
433 iterator position,random_access_index<SuperMeta,TagList>& x,iterator i)
435 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
436 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
437 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(i);
438 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(i);
439 BOOST_MULTI_INDEX_CHECK_IS_OWNER(i,x);
440 BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
441 if(&x==this)relocate(position,i);
443 if(insert(position,*i).second){
445 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
446 /* MSVC++ 6.0 optimizer has a hard time with safe mode, and the following
447 * workaround is needed. Left it for all compilers as it does no
451 x.erase(x.make_iterator(i.get_node()));
461 iterator position,random_access_index<SuperMeta,TagList>& x,
462 iterator first,iterator last)
464 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
465 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
466 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first);
467 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last);
468 BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,x);
469 BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,x);
470 BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last);
471 BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
472 if(&x==this)relocate(position,first,last);
477 if(push_back(*first).second){
478 first=x.erase(first);
485 relocate(position,end()-n,end());
489 relocate(position,end()-n,end());
493 void remove(value_param_type value)
495 BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
498 random_access_index_remove<node_type>(
499 ptrs,std::bind2nd(std::equal_to<value_type>(),value)));
500 while(n--)pop_back();
503 template<typename Predicate>
504 void remove_if(Predicate pred)
506 BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
508 end()-make_iterator(random_access_index_remove<node_type>(ptrs,pred));
509 while(n--)pop_back();
514 BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
517 random_access_index_unique<node_type>(
518 ptrs,std::equal_to<value_type>()));
519 while(n--)pop_back();
522 template <class BinaryPredicate>
523 void unique(BinaryPredicate binary_pred)
525 BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
528 random_access_index_unique<node_type>(ptrs,binary_pred));
529 while(n--)pop_back();
532 void merge(random_access_index<SuperMeta,TagList>& x)
535 BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
538 random_access_index_inplace_merge<node_type>(
539 get_allocator(),ptrs,ptrs.at(s),std::less<value_type>());
543 template <typename Compare>
544 void merge(random_access_index<SuperMeta,TagList>& x,Compare comp)
547 BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
550 random_access_index_inplace_merge<node_type>(
551 get_allocator(),ptrs,ptrs.at(s),comp);
557 BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
558 random_access_index_sort<node_type>(
559 get_allocator(),ptrs,std::less<value_type>());
562 template <typename Compare>
563 void sort(Compare comp)
565 BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
566 random_access_index_sort<node_type>(
567 get_allocator(),ptrs,comp);
572 BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
573 node_impl_type::reverse(ptrs.begin(),ptrs.end());
576 /* rearrange operations */
578 void relocate(iterator position,iterator i)
580 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
581 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
582 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(i);
583 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(i);
584 BOOST_MULTI_INDEX_CHECK_IS_OWNER(i,*this);
585 BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
586 if(position!=i)relocate(position.get_node(),i.get_node());
589 void relocate(iterator position,iterator first,iterator last)
591 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
592 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
593 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first);
594 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last);
595 BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,*this);
596 BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,*this);
597 BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last);
598 BOOST_MULTI_INDEX_CHECK_OUTSIDE_RANGE(position,first,last);
599 BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
600 if(position!=last)relocate(
601 position.get_node(),first.get_node(),last.get_node());
604 template<typename InputIterator>
605 void rearrange(InputIterator first)
607 BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
608 for(node_impl_ptr_pointer p0=ptrs.begin(),p0_end=ptrs.end();
609 p0!=p0_end;++first,++p0){
610 const value_type& v1=*first;
611 node_impl_ptr_pointer p1=node_from_value<node_type>(&v1)->up();
619 BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS:
621 const ctor_args_list& args_list,const allocator_type& al):
622 super(args_list.get_tail(),al),
623 ptrs(al,header()->impl(),0)
627 random_access_index(const random_access_index<SuperMeta,TagList>& x):
630 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
634 ptrs(x.get_allocator(),header()->impl(),x.size())
636 /* The actual copying takes place in subsequent call to copy_().
640 ~random_access_index()
642 /* the container is guaranteed to be empty by now */
645 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
646 iterator make_iterator(node_type* node){return iterator(node,this);}
647 const_iterator make_iterator(node_type* node)const
648 {return const_iterator(node,const_cast<random_access_index*>(this));}
650 iterator make_iterator(node_type* node){return iterator(node);}
651 const_iterator make_iterator(node_type* node)const
652 {return const_iterator(node);}
656 const random_access_index<SuperMeta,TagList>& x,const copy_map_type& map)
658 for(node_impl_ptr_pointer begin_org=x.ptrs.begin(),
659 begin_cpy=ptrs.begin(),
660 end_org=x.ptrs.end();
661 begin_org!=end_org;++begin_org,++begin_cpy){
663 static_cast<node_type*>(
665 static_cast<final_node_type*>(
666 node_type::from_impl(*begin_org))))->impl();
667 (*begin_cpy)->up()=begin_cpy;
673 node_type* insert_(value_param_type v,node_type* x)
676 node_type* res=static_cast<node_type*>(super::insert_(v,x));
677 if(res==x)ptrs.push_back(x->impl());
681 node_type* insert_(value_param_type v,node_type* position,node_type* x)
684 node_type* res=static_cast<node_type*>(super::insert_(v,position,x));
685 if(res==x)ptrs.push_back(x->impl());
689 void erase_(node_type* x)
691 ptrs.erase(x->impl());
694 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
699 void delete_all_nodes_()
701 for(node_impl_ptr_pointer x=ptrs.begin(),x_end=ptrs.end();x!=x_end;++x){
702 this->final_delete_node_(
703 static_cast<final_node_type*>(node_type::from_impl(*x)));
712 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
713 safe_super::detach_dereferenceable_iterators();
717 void swap_(random_access_index<SuperMeta,TagList>& x)
721 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
728 bool replace_(value_param_type v,node_type* x)
730 return super::replace_(v,x);
733 bool modify_(node_type* x)
736 if(!super::modify_(x)){
737 ptrs.erase(x->impl());
739 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
748 ptrs.erase(x->impl());
750 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
759 bool modify_rollback_(node_type* x)
761 return super::modify_rollback_(x);
764 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
767 template<typename Archive>
769 Archive& ar,const unsigned int version,const index_saver_type& sm)const
771 sm.save(begin(),end(),ar,version);
772 super::save_(ar,version,sm);
775 template<typename Archive>
777 Archive& ar,const unsigned int version,const index_loader_type& lm)
780 typedef random_access_index_loader<node_type,allocator_type> loader;
782 loader ld(get_allocator(),ptrs);
783 lm.load(::boost::bind(&loader::rearrange,&ld,_1,_2),ar,version);
784 } /* exit scope so that ld frees its resources */
785 super::load_(ar,version,lm);
789 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
790 /* invariant stuff */
792 bool invariant_()const
794 if(size()>capacity())return false;
795 if(size()==0||begin()==end()){
796 if(size()!=0||begin()!=end())return false;
800 for(const_iterator it=begin(),it_end=end();;++it,++s){
801 if(*(it.get_node()->up())!=it.get_node()->impl())return false;
804 if(s!=size())return false;
807 return super::invariant_();
810 /* This forwarding function eases things for the boost::mem_fn construct
811 * in BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT. Actually,
812 * final_check_invariant is already an inherited member function of index.
814 void check_invariant_()const{this->final_check_invariant_();}
818 node_type* header()const{return this->final_header();}
820 static void relocate(node_type* position,node_type* x)
822 node_impl_type::relocate(position->up(),x->up());
825 static void relocate(node_type* position,node_type* first,node_type* last)
827 node_impl_type::relocate(
828 position->up(),first->up(),last->up());
831 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
832 void detach_iterators(node_type* x)
834 iterator it=make_iterator(x);
835 safe_mode::detach_equivalent_iterators(it);
839 template <class InputIterator>
840 void assign_iter(InputIterator first,InputIterator last,mpl::true_)
842 BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
844 for(;first!=last;++first)push_back(*first);
847 void assign_iter(size_type n,value_param_type value,mpl::false_)
849 BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
851 for(size_type i=0;i<n;++i)push_back(value);
854 template<typename InputIterator>
856 iterator position,InputIterator first,InputIterator last,mpl::true_)
858 BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
861 for(;first!=last;++first){
862 if(push_back(*first).second)++s;
866 relocate(position,end()-s,end());
870 relocate(position,end()-s,end());
874 iterator position,size_type n,value_param_type x,mpl::false_)
876 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
877 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
878 BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
882 if(push_back(x).second)++s;
886 relocate(position,end()-s,end());
890 relocate(position,end()-s,end());
895 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
896 BOOST_WORKAROUND(__MWERKS__,<=0x3003)
897 #pragma parse_mfunc_templ reset
904 typename SuperMeta1,typename TagList1,
905 typename SuperMeta2,typename TagList2
908 const random_access_index<SuperMeta1,TagList1>& x,
909 const random_access_index<SuperMeta2,TagList2>& y)
911 return x.size()==y.size()&&std::equal(x.begin(),x.end(),y.begin());
915 typename SuperMeta1,typename TagList1,
916 typename SuperMeta2,typename TagList2
919 const random_access_index<SuperMeta1,TagList1>& x,
920 const random_access_index<SuperMeta2,TagList2>& y)
922 return std::lexicographical_compare(x.begin(),x.end(),y.begin(),y.end());
926 typename SuperMeta1,typename TagList1,
927 typename SuperMeta2,typename TagList2
930 const random_access_index<SuperMeta1,TagList1>& x,
931 const random_access_index<SuperMeta2,TagList2>& y)
937 typename SuperMeta1,typename TagList1,
938 typename SuperMeta2,typename TagList2
941 const random_access_index<SuperMeta1,TagList1>& x,
942 const random_access_index<SuperMeta2,TagList2>& y)
948 typename SuperMeta1,typename TagList1,
949 typename SuperMeta2,typename TagList2
952 const random_access_index<SuperMeta1,TagList1>& x,
953 const random_access_index<SuperMeta2,TagList2>& y)
959 typename SuperMeta1,typename TagList1,
960 typename SuperMeta2,typename TagList2
963 const random_access_index<SuperMeta1,TagList1>& x,
964 const random_access_index<SuperMeta2,TagList2>& y)
969 /* specialized algorithms */
971 template<typename SuperMeta,typename TagList>
973 random_access_index<SuperMeta,TagList>& x,
974 random_access_index<SuperMeta,TagList>& y)
979 } /* namespace multi_index::detail */
981 /* random access index specifier */
983 template <typename TagList>
986 BOOST_STATIC_ASSERT(detail::is_tag<TagList>::value);
988 template<typename Super>
991 typedef detail::random_access_index_node<Super> type;
994 template<typename SuperMeta>
997 typedef detail::random_access_index<
998 SuperMeta,typename TagList::type> type;
1002 } /* namespace multi_index */
1004 } /* namespace boost */
1006 #undef BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT