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