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