1 | ///////////////////////////////////////////////////////////////////////////// |
2 | // |
3 | // (C) Copyright Olaf Krzikalla 2004-2006. |
4 | // (C) Copyright Ion Gaztanaga 2006-2014 |
5 | // |
6 | // Distributed under the Boost Software License, Version 1.0. |
7 | // (See accompanying file LICENSE_1_0.txt or copy at |
8 | // http://www.boost.org/LICENSE_1_0.txt) |
9 | // |
10 | // See http://www.boost.org/libs/intrusive for documentation. |
11 | // |
12 | ///////////////////////////////////////////////////////////////////////////// |
13 | |
14 | #ifndef BOOST_INTRUSIVE_LIST_HPP |
15 | #define BOOST_INTRUSIVE_LIST_HPP |
16 | |
17 | #include <boost/intrusive/detail/config_begin.hpp> |
18 | #include <boost/intrusive/intrusive_fwd.hpp> |
19 | #include <boost/intrusive/detail/assert.hpp> |
20 | #include <boost/intrusive/list_hook.hpp> |
21 | #include <boost/intrusive/circular_list_algorithms.hpp> |
22 | #include <boost/intrusive/pointer_traits.hpp> |
23 | #include <boost/intrusive/detail/mpl.hpp> |
24 | #include <boost/intrusive/link_mode.hpp> |
25 | #include <boost/intrusive/detail/get_value_traits.hpp> |
26 | #include <boost/intrusive/detail/is_stateful_value_traits.hpp> |
27 | #include <boost/intrusive/detail/default_header_holder.hpp> |
28 | #include <boost/intrusive/detail/reverse_iterator.hpp> |
29 | #include <boost/intrusive/detail/uncast.hpp> |
30 | #include <boost/intrusive/detail/list_iterator.hpp> |
31 | #include <boost/intrusive/detail/array_initializer.hpp> |
32 | #include <boost/intrusive/detail/exception_disposer.hpp> |
33 | #include <boost/intrusive/detail/equal_to_value.hpp> |
34 | #include <boost/intrusive/detail/key_nodeptr_comp.hpp> |
35 | #include <boost/intrusive/detail/simple_disposers.hpp> |
36 | #include <boost/intrusive/detail/size_holder.hpp> |
37 | #include <boost/intrusive/detail/algorithm.hpp> |
38 | |
39 | #include <boost/move/utility_core.hpp> |
40 | #include <boost/static_assert.hpp> |
41 | |
42 | #include <boost/intrusive/detail/minimal_less_equal_header.hpp>//std::less |
43 | #include <cstddef> //std::size_t, etc. |
44 | |
45 | #if defined(BOOST_HAS_PRAGMA_ONCE) |
46 | # pragma once |
47 | #endif |
48 | |
49 | namespace boost { |
50 | namespace intrusive { |
51 | |
52 | /// @cond |
53 | |
54 | struct default_list_hook_applier |
55 | { template <class T> struct apply{ typedef typename T::default_list_hook type; }; }; |
56 | |
57 | template<> |
58 | struct is_default_hook_tag<default_list_hook_applier> |
59 | { static const bool value = true; }; |
60 | |
61 | struct list_defaults |
62 | { |
63 | typedef default_list_hook_applier proto_value_traits; |
64 | static const bool constant_time_size = true; |
65 | typedef std::size_t size_type; |
66 | typedef void ; |
67 | }; |
68 | |
69 | /// @endcond |
70 | |
71 | //! The class template list is an intrusive container that mimics most of the |
72 | //! interface of std::list as described in the C++ standard. |
73 | //! |
74 | //! The template parameter \c T is the type to be managed by the container. |
75 | //! The user can specify additional options and if no options are provided |
76 | //! default options are used. |
77 | //! |
78 | //! The container supports the following options: |
79 | //! \c base_hook<>/member_hook<>/value_traits<>, |
80 | //! \c constant_time_size<> and \c size_type<>. |
81 | #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) |
82 | template<class T, class ...Options> |
83 | #else |
84 | template <class ValueTraits, class SizeType, bool ConstantTimeSize, typename HeaderHolder> |
85 | #endif |
86 | class list_impl |
87 | { |
88 | //Public typedefs |
89 | public: |
90 | typedef ValueTraits value_traits; |
91 | typedef typename value_traits::pointer pointer; |
92 | typedef typename value_traits::const_pointer const_pointer; |
93 | typedef typename pointer_traits<pointer>::element_type value_type; |
94 | typedef typename pointer_traits<pointer>::reference reference; |
95 | typedef typename pointer_traits<const_pointer>::reference const_reference; |
96 | typedef typename pointer_traits<pointer>::difference_type difference_type; |
97 | typedef SizeType size_type; |
98 | typedef list_iterator<value_traits, false> iterator; |
99 | typedef list_iterator<value_traits, true> const_iterator; |
100 | typedef boost::intrusive::reverse_iterator<iterator> reverse_iterator; |
101 | typedef boost::intrusive::reverse_iterator<const_iterator> const_reverse_iterator; |
102 | typedef typename value_traits::node_traits node_traits; |
103 | typedef typename node_traits::node node; |
104 | typedef typename node_traits::node_ptr node_ptr; |
105 | typedef typename node_traits::const_node_ptr const_node_ptr; |
106 | typedef circular_list_algorithms<node_traits> node_algorithms; |
107 | typedef typename detail::get_header_holder_type |
108 | < value_traits, HeaderHolder >::type ; |
109 | |
110 | static const bool constant_time_size = ConstantTimeSize; |
111 | static const bool stateful_value_traits = detail::is_stateful_value_traits<value_traits>::value; |
112 | static const bool has_container_from_iterator = |
113 | detail::is_same< header_holder_type, detail::default_header_holder< node_traits > >::value; |
114 | |
115 | /// @cond |
116 | |
117 | private: |
118 | typedef detail::size_holder<constant_time_size, size_type> size_traits; |
119 | |
120 | //noncopyable |
121 | BOOST_MOVABLE_BUT_NOT_COPYABLE(list_impl) |
122 | |
123 | static const bool safemode_or_autounlink = is_safe_autounlink<value_traits::link_mode>::value; |
124 | |
125 | //Constant-time size is incompatible with auto-unlink hooks! |
126 | BOOST_STATIC_ASSERT(!(constant_time_size && |
127 | ((int)value_traits::link_mode == (int)auto_unlink) |
128 | )); |
129 | |
130 | node_ptr get_root_node() |
131 | { return data_.root_plus_size_.m_header.get_node(); } |
132 | |
133 | const_node_ptr get_root_node() const |
134 | { return data_.root_plus_size_.m_header.get_node(); } |
135 | |
136 | struct root_plus_size : public size_traits |
137 | { |
138 | header_holder_type ; |
139 | }; |
140 | |
141 | struct data_t : public value_traits |
142 | { |
143 | typedef typename list_impl::value_traits value_traits; |
144 | explicit data_t(const value_traits &val_traits) |
145 | : value_traits(val_traits) |
146 | {} |
147 | |
148 | root_plus_size root_plus_size_; |
149 | } data_; |
150 | |
151 | size_traits &priv_size_traits() |
152 | { return data_.root_plus_size_; } |
153 | |
154 | const size_traits &priv_size_traits() const |
155 | { return data_.root_plus_size_; } |
156 | |
157 | const value_traits &priv_value_traits() const |
158 | { return data_; } |
159 | |
160 | value_traits &priv_value_traits() |
161 | { return data_; } |
162 | |
163 | typedef typename boost::intrusive::value_traits_pointers |
164 | <ValueTraits>::const_value_traits_ptr const_value_traits_ptr; |
165 | |
166 | const_value_traits_ptr priv_value_traits_ptr() const |
167 | { return pointer_traits<const_value_traits_ptr>::pointer_to(this->priv_value_traits()); } |
168 | |
169 | /// @endcond |
170 | |
171 | public: |
172 | |
173 | //! <b>Effects</b>: constructs an empty list. |
174 | //! |
175 | //! <b>Complexity</b>: Constant |
176 | //! |
177 | //! <b>Throws</b>: If value_traits::node_traits::node |
178 | //! constructor throws (this does not happen with predefined Boost.Intrusive hooks). |
179 | explicit list_impl(const value_traits &v_traits = value_traits()) |
180 | : data_(v_traits) |
181 | { |
182 | this->priv_size_traits().set_size(size_type(0)); |
183 | node_algorithms::init_header(this->get_root_node()); |
184 | } |
185 | |
186 | //! <b>Requires</b>: Dereferencing iterator must yield an lvalue of type value_type. |
187 | //! |
188 | //! <b>Effects</b>: Constructs a list equal to the range [first,last). |
189 | //! |
190 | //! <b>Complexity</b>: Linear in distance(b, e). No copy constructors are called. |
191 | //! |
192 | //! <b>Throws</b>: If value_traits::node_traits::node |
193 | //! constructor throws (this does not happen with predefined Boost.Intrusive hooks). |
194 | template<class Iterator> |
195 | list_impl(Iterator b, Iterator e, const value_traits &v_traits = value_traits()) |
196 | : data_(v_traits) |
197 | { |
198 | //nothrow, no need to rollback to release elements on exception |
199 | this->priv_size_traits().set_size(size_type(0)); |
200 | node_algorithms::init_header(this->get_root_node()); |
201 | //nothrow, no need to rollback to release elements on exception |
202 | this->insert(this->cend(), b, e); |
203 | } |
204 | |
205 | //! <b>Effects</b>: to-do |
206 | //! |
207 | list_impl(BOOST_RV_REF(list_impl) x) |
208 | : data_(::boost::move(x.priv_value_traits())) |
209 | { |
210 | this->priv_size_traits().set_size(size_type(0)); |
211 | node_algorithms::init_header(this->get_root_node()); |
212 | //nothrow, no need to rollback to release elements on exception |
213 | this->swap(x); |
214 | } |
215 | |
216 | //! <b>Effects</b>: to-do |
217 | //! |
218 | list_impl& operator=(BOOST_RV_REF(list_impl) x) |
219 | { this->swap(x); return *this; } |
220 | |
221 | //! <b>Effects</b>: If it's not a safe-mode or an auto-unlink value_type |
222 | //! the destructor does nothing |
223 | //! (ie. no code is generated). Otherwise it detaches all elements from this. |
224 | //! In this case the objects in the list are not deleted (i.e. no destructors |
225 | //! are called), but the hooks according to the ValueTraits template parameter |
226 | //! are set to their default value. |
227 | //! |
228 | //! <b>Complexity</b>: Linear to the number of elements in the list, if |
229 | //! it's a safe-mode or auto-unlink value . Otherwise constant. |
230 | ~list_impl() |
231 | { |
232 | if(is_safe_autounlink<ValueTraits::link_mode>::value){ |
233 | this->clear(); |
234 | node_algorithms::init(this->get_root_node()); |
235 | } |
236 | } |
237 | |
238 | //! <b>Requires</b>: value must be an lvalue. |
239 | //! |
240 | //! <b>Effects</b>: Inserts the value in the back of the list. |
241 | //! No copy constructors are called. |
242 | //! |
243 | //! <b>Throws</b>: Nothing. |
244 | //! |
245 | //! <b>Complexity</b>: Constant. |
246 | //! |
247 | //! <b>Note</b>: Does not affect the validity of iterators and references. |
248 | void push_back(reference value) |
249 | { |
250 | node_ptr to_insert = priv_value_traits().to_node_ptr(value); |
251 | BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::inited(to_insert)); |
252 | node_algorithms::link_before(this->get_root_node(), to_insert); |
253 | this->priv_size_traits().increment(); |
254 | } |
255 | |
256 | //! <b>Requires</b>: value must be an lvalue. |
257 | //! |
258 | //! <b>Effects</b>: Inserts the value in the front of the list. |
259 | //! No copy constructors are called. |
260 | //! |
261 | //! <b>Throws</b>: Nothing. |
262 | //! |
263 | //! <b>Complexity</b>: Constant. |
264 | //! |
265 | //! <b>Note</b>: Does not affect the validity of iterators and references. |
266 | void push_front(reference value) |
267 | { |
268 | node_ptr to_insert = priv_value_traits().to_node_ptr(value); |
269 | BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::inited(to_insert)); |
270 | node_algorithms::link_before(node_traits::get_next(this->get_root_node()), to_insert); |
271 | this->priv_size_traits().increment(); |
272 | } |
273 | |
274 | //! <b>Effects</b>: Erases the last element of the list. |
275 | //! No destructors are called. |
276 | //! |
277 | //! <b>Throws</b>: Nothing. |
278 | //! |
279 | //! <b>Complexity</b>: Constant. |
280 | //! |
281 | //! <b>Note</b>: Invalidates the iterators (but not the references) to the erased element. |
282 | void pop_back() |
283 | { return this->pop_back_and_dispose(detail::null_disposer()); } |
284 | |
285 | //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. |
286 | //! |
287 | //! <b>Effects</b>: Erases the last element of the list. |
288 | //! No destructors are called. |
289 | //! Disposer::operator()(pointer) is called for the removed element. |
290 | //! |
291 | //! <b>Throws</b>: Nothing. |
292 | //! |
293 | //! <b>Complexity</b>: Constant. |
294 | //! |
295 | //! <b>Note</b>: Invalidates the iterators to the erased element. |
296 | template<class Disposer> |
297 | void pop_back_and_dispose(Disposer disposer) |
298 | { |
299 | node_ptr to_erase = node_traits::get_previous(this->get_root_node()); |
300 | node_algorithms::unlink(to_erase); |
301 | this->priv_size_traits().decrement(); |
302 | if(safemode_or_autounlink) |
303 | node_algorithms::init(to_erase); |
304 | disposer(priv_value_traits().to_value_ptr(to_erase)); |
305 | } |
306 | |
307 | //! <b>Effects</b>: Erases the first element of the list. |
308 | //! No destructors are called. |
309 | //! |
310 | //! <b>Throws</b>: Nothing. |
311 | //! |
312 | //! <b>Complexity</b>: Constant. |
313 | //! |
314 | //! <b>Note</b>: Invalidates the iterators (but not the references) to the erased element. |
315 | void pop_front() |
316 | { return this->pop_front_and_dispose(detail::null_disposer()); } |
317 | |
318 | //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. |
319 | //! |
320 | //! <b>Effects</b>: Erases the first element of the list. |
321 | //! No destructors are called. |
322 | //! Disposer::operator()(pointer) is called for the removed element. |
323 | //! |
324 | //! <b>Throws</b>: Nothing. |
325 | //! |
326 | //! <b>Complexity</b>: Constant. |
327 | //! |
328 | //! <b>Note</b>: Invalidates the iterators to the erased element. |
329 | template<class Disposer> |
330 | void pop_front_and_dispose(Disposer disposer) |
331 | { |
332 | node_ptr to_erase = node_traits::get_next(this->get_root_node()); |
333 | node_algorithms::unlink(to_erase); |
334 | this->priv_size_traits().decrement(); |
335 | if(safemode_or_autounlink) |
336 | node_algorithms::init(to_erase); |
337 | disposer(priv_value_traits().to_value_ptr(to_erase)); |
338 | } |
339 | |
340 | //! <b>Effects</b>: Returns a reference to the first element of the list. |
341 | //! |
342 | //! <b>Throws</b>: Nothing. |
343 | //! |
344 | //! <b>Complexity</b>: Constant. |
345 | reference front() |
346 | { return *priv_value_traits().to_value_ptr(node_traits::get_next(this->get_root_node())); } |
347 | |
348 | //! <b>Effects</b>: Returns a const_reference to the first element of the list. |
349 | //! |
350 | //! <b>Throws</b>: Nothing. |
351 | //! |
352 | //! <b>Complexity</b>: Constant. |
353 | const_reference front() const |
354 | { return *priv_value_traits().to_value_ptr(node_traits::get_next(this->get_root_node())); } |
355 | |
356 | //! <b>Effects</b>: Returns a reference to the last element of the list. |
357 | //! |
358 | //! <b>Throws</b>: Nothing. |
359 | //! |
360 | //! <b>Complexity</b>: Constant. |
361 | reference back() |
362 | { return *priv_value_traits().to_value_ptr(node_traits::get_previous(this->get_root_node())); } |
363 | |
364 | //! <b>Effects</b>: Returns a const_reference to the last element of the list. |
365 | //! |
366 | //! <b>Throws</b>: Nothing. |
367 | //! |
368 | //! <b>Complexity</b>: Constant. |
369 | const_reference back() const |
370 | { return *priv_value_traits().to_value_ptr(detail::uncast(node_traits::get_previous(this->get_root_node()))); } |
371 | |
372 | //! <b>Effects</b>: Returns an iterator to the first element contained in the list. |
373 | //! |
374 | //! <b>Throws</b>: Nothing. |
375 | //! |
376 | //! <b>Complexity</b>: Constant. |
377 | iterator begin() |
378 | { return iterator(node_traits::get_next(this->get_root_node()), this->priv_value_traits_ptr()); } |
379 | |
380 | //! <b>Effects</b>: Returns a const_iterator to the first element contained in the list. |
381 | //! |
382 | //! <b>Throws</b>: Nothing. |
383 | //! |
384 | //! <b>Complexity</b>: Constant. |
385 | const_iterator begin() const |
386 | { return this->cbegin(); } |
387 | |
388 | //! <b>Effects</b>: Returns a const_iterator to the first element contained in the list. |
389 | //! |
390 | //! <b>Throws</b>: Nothing. |
391 | //! |
392 | //! <b>Complexity</b>: Constant. |
393 | const_iterator cbegin() const |
394 | { return const_iterator(node_traits::get_next(this->get_root_node()), this->priv_value_traits_ptr()); } |
395 | |
396 | //! <b>Effects</b>: Returns an iterator to the end of the list. |
397 | //! |
398 | //! <b>Throws</b>: Nothing. |
399 | //! |
400 | //! <b>Complexity</b>: Constant. |
401 | iterator end() |
402 | { return iterator(this->get_root_node(), this->priv_value_traits_ptr()); } |
403 | |
404 | //! <b>Effects</b>: Returns a const_iterator to the end of the list. |
405 | //! |
406 | //! <b>Throws</b>: Nothing. |
407 | //! |
408 | //! <b>Complexity</b>: Constant. |
409 | const_iterator end() const |
410 | { return this->cend(); } |
411 | |
412 | //! <b>Effects</b>: Returns a constant iterator to the end of the list. |
413 | //! |
414 | //! <b>Throws</b>: Nothing. |
415 | //! |
416 | //! <b>Complexity</b>: Constant. |
417 | const_iterator cend() const |
418 | { return const_iterator(detail::uncast(this->get_root_node()), this->priv_value_traits_ptr()); } |
419 | |
420 | //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning |
421 | //! of the reversed list. |
422 | //! |
423 | //! <b>Throws</b>: Nothing. |
424 | //! |
425 | //! <b>Complexity</b>: Constant. |
426 | reverse_iterator rbegin() |
427 | { return reverse_iterator(this->end()); } |
428 | |
429 | //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning |
430 | //! of the reversed list. |
431 | //! |
432 | //! <b>Throws</b>: Nothing. |
433 | //! |
434 | //! <b>Complexity</b>: Constant. |
435 | const_reverse_iterator rbegin() const |
436 | { return this->crbegin(); } |
437 | |
438 | //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning |
439 | //! of the reversed list. |
440 | //! |
441 | //! <b>Throws</b>: Nothing. |
442 | //! |
443 | //! <b>Complexity</b>: Constant. |
444 | const_reverse_iterator crbegin() const |
445 | { return const_reverse_iterator(end()); } |
446 | |
447 | //! <b>Effects</b>: Returns a reverse_iterator pointing to the end |
448 | //! of the reversed list. |
449 | //! |
450 | //! <b>Throws</b>: Nothing. |
451 | //! |
452 | //! <b>Complexity</b>: Constant. |
453 | reverse_iterator rend() |
454 | { return reverse_iterator(begin()); } |
455 | |
456 | //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end |
457 | //! of the reversed list. |
458 | //! |
459 | //! <b>Throws</b>: Nothing. |
460 | //! |
461 | //! <b>Complexity</b>: Constant. |
462 | const_reverse_iterator rend() const |
463 | { return this->crend(); } |
464 | |
465 | //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end |
466 | //! of the reversed list. |
467 | //! |
468 | //! <b>Throws</b>: Nothing. |
469 | //! |
470 | //! <b>Complexity</b>: Constant. |
471 | const_reverse_iterator crend() const |
472 | { return const_reverse_iterator(this->begin()); } |
473 | |
474 | //! <b>Precondition</b>: end_iterator must be a valid end iterator |
475 | //! of list. |
476 | //! |
477 | //! <b>Effects</b>: Returns a const reference to the list associated to the end iterator |
478 | //! |
479 | //! <b>Throws</b>: Nothing. |
480 | //! |
481 | //! <b>Complexity</b>: Constant. |
482 | static list_impl &container_from_end_iterator(iterator end_iterator) |
483 | { return list_impl::priv_container_from_end_iterator(end_iterator); } |
484 | |
485 | //! <b>Precondition</b>: end_iterator must be a valid end const_iterator |
486 | //! of list. |
487 | //! |
488 | //! <b>Effects</b>: Returns a const reference to the list associated to the end iterator |
489 | //! |
490 | //! <b>Throws</b>: Nothing. |
491 | //! |
492 | //! <b>Complexity</b>: Constant. |
493 | static const list_impl &container_from_end_iterator(const_iterator end_iterator) |
494 | { return list_impl::priv_container_from_end_iterator(end_iterator); } |
495 | |
496 | //! <b>Effects</b>: Returns the number of the elements contained in the list. |
497 | //! |
498 | //! <b>Throws</b>: Nothing. |
499 | //! |
500 | //! <b>Complexity</b>: Linear to the number of elements contained in the list. |
501 | //! if constant-time size option is disabled. Constant time otherwise. |
502 | //! |
503 | //! <b>Note</b>: Does not affect the validity of iterators and references. |
504 | size_type size() const |
505 | { |
506 | if(constant_time_size) |
507 | return this->priv_size_traits().get_size(); |
508 | else |
509 | return node_algorithms::count(this->get_root_node()) - 1; |
510 | } |
511 | |
512 | //! <b>Effects</b>: Returns true if the list contains no elements. |
513 | //! |
514 | //! <b>Throws</b>: Nothing. |
515 | //! |
516 | //! <b>Complexity</b>: Constant. |
517 | //! |
518 | //! <b>Note</b>: Does not affect the validity of iterators and references. |
519 | bool empty() const |
520 | { return node_algorithms::unique(this->get_root_node()); } |
521 | |
522 | //! <b>Effects</b>: Swaps the elements of x and *this. |
523 | //! |
524 | //! <b>Throws</b>: Nothing. |
525 | //! |
526 | //! <b>Complexity</b>: Constant. |
527 | //! |
528 | //! <b>Note</b>: Does not affect the validity of iterators and references. |
529 | void swap(list_impl& other) |
530 | { |
531 | node_algorithms::swap_nodes(this->get_root_node(), other.get_root_node()); |
532 | if(constant_time_size){ |
533 | size_type backup = this->priv_size_traits().get_size(); |
534 | this->priv_size_traits().set_size(other.priv_size_traits().get_size()); |
535 | other.priv_size_traits().set_size(backup); |
536 | } |
537 | } |
538 | |
539 | //! <b>Effects</b>: Moves backwards all the elements, so that the first |
540 | //! element becomes the second, the second becomes the third... |
541 | //! the last element becomes the first one. |
542 | //! |
543 | //! <b>Throws</b>: Nothing. |
544 | //! |
545 | //! <b>Complexity</b>: Linear to the number of shifts. |
546 | //! |
547 | //! <b>Note</b>: Does not affect the validity of iterators and references. |
548 | void shift_backwards(size_type n = 1) |
549 | { node_algorithms::move_forward(this->get_root_node(), n); } |
550 | |
551 | //! <b>Effects</b>: Moves forward all the elements, so that the second |
552 | //! element becomes the first, the third becomes the second... |
553 | //! the first element becomes the last one. |
554 | //! |
555 | //! <b>Throws</b>: Nothing. |
556 | //! |
557 | //! <b>Complexity</b>: Linear to the number of shifts. |
558 | //! |
559 | //! <b>Note</b>: Does not affect the validity of iterators and references. |
560 | void shift_forward(size_type n = 1) |
561 | { node_algorithms::move_backwards(this->get_root_node(), n); } |
562 | |
563 | //! <b>Effects</b>: Erases the element pointed by i of the list. |
564 | //! No destructors are called. |
565 | //! |
566 | //! <b>Returns</b>: the first element remaining beyond the removed element, |
567 | //! or end() if no such element exists. |
568 | //! |
569 | //! <b>Throws</b>: Nothing. |
570 | //! |
571 | //! <b>Complexity</b>: Constant. |
572 | //! |
573 | //! <b>Note</b>: Invalidates the iterators (but not the references) to the |
574 | //! erased element. |
575 | iterator erase(const_iterator i) |
576 | { return this->erase_and_dispose(i, detail::null_disposer()); } |
577 | |
578 | //! <b>Requires</b>: b and e must be valid iterators to elements in *this. |
579 | //! |
580 | //! <b>Effects</b>: Erases the element range pointed by b and e |
581 | //! No destructors are called. |
582 | //! |
583 | //! <b>Returns</b>: the first element remaining beyond the removed elements, |
584 | //! or end() if no such element exists. |
585 | //! |
586 | //! <b>Throws</b>: Nothing. |
587 | //! |
588 | //! <b>Complexity</b>: Linear to the number of erased elements if it's a safe-mode |
589 | //! or auto-unlink value, or constant-time size is enabled. Constant-time otherwise. |
590 | //! |
591 | //! <b>Note</b>: Invalidates the iterators (but not the references) to the |
592 | //! erased elements. |
593 | iterator erase(const_iterator b, const_iterator e) |
594 | { |
595 | if(safemode_or_autounlink || constant_time_size){ |
596 | return this->erase_and_dispose(b, e, detail::null_disposer()); |
597 | } |
598 | else{ |
599 | node_algorithms::unlink(b.pointed_node(), e.pointed_node()); |
600 | return e.unconst(); |
601 | } |
602 | } |
603 | |
604 | //! <b>Requires</b>: b and e must be valid iterators to elements in *this. |
605 | //! n must be distance(b, e). |
606 | //! |
607 | //! <b>Effects</b>: Erases the element range pointed by b and e |
608 | //! No destructors are called. |
609 | //! |
610 | //! <b>Returns</b>: the first element remaining beyond the removed elements, |
611 | //! or end() if no such element exists. |
612 | //! |
613 | //! <b>Throws</b>: Nothing. |
614 | //! |
615 | //! <b>Complexity</b>: Linear to the number of erased elements if it's a safe-mode |
616 | //! or auto-unlink value is enabled. Constant-time otherwise. |
617 | //! |
618 | //! <b>Note</b>: Invalidates the iterators (but not the references) to the |
619 | //! erased elements. |
620 | iterator erase(const_iterator b, const_iterator e, size_type n) |
621 | { |
622 | BOOST_INTRUSIVE_INVARIANT_ASSERT(node_algorithms::distance(b.pointed_node(), e.pointed_node()) == n); |
623 | if(safemode_or_autounlink || constant_time_size){ |
624 | return this->erase_and_dispose(b, e, detail::null_disposer()); |
625 | } |
626 | else{ |
627 | if(constant_time_size){ |
628 | this->priv_size_traits().decrease(n); |
629 | } |
630 | node_algorithms::unlink(b.pointed_node(), e.pointed_node()); |
631 | return e.unconst(); |
632 | } |
633 | } |
634 | |
635 | //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. |
636 | //! |
637 | //! <b>Effects</b>: Erases the element pointed by i of the list. |
638 | //! No destructors are called. |
639 | //! Disposer::operator()(pointer) is called for the removed element. |
640 | //! |
641 | //! <b>Returns</b>: the first element remaining beyond the removed element, |
642 | //! or end() if no such element exists. |
643 | //! |
644 | //! <b>Throws</b>: Nothing. |
645 | //! |
646 | //! <b>Complexity</b>: Constant. |
647 | //! |
648 | //! <b>Note</b>: Invalidates the iterators to the erased element. |
649 | template <class Disposer> |
650 | iterator erase_and_dispose(const_iterator i, Disposer disposer) |
651 | { |
652 | node_ptr to_erase(i.pointed_node()); |
653 | ++i; |
654 | node_algorithms::unlink(to_erase); |
655 | this->priv_size_traits().decrement(); |
656 | if(safemode_or_autounlink) |
657 | node_algorithms::init(to_erase); |
658 | disposer(this->priv_value_traits().to_value_ptr(to_erase)); |
659 | return i.unconst(); |
660 | } |
661 | |
662 | #if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) |
663 | template<class Disposer> |
664 | iterator erase_and_dispose(iterator i, Disposer disposer) |
665 | { return this->erase_and_dispose(const_iterator(i), disposer); } |
666 | #endif |
667 | |
668 | //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. |
669 | //! |
670 | //! <b>Effects</b>: Erases the element range pointed by b and e |
671 | //! No destructors are called. |
672 | //! Disposer::operator()(pointer) is called for the removed elements. |
673 | //! |
674 | //! <b>Returns</b>: the first element remaining beyond the removed elements, |
675 | //! or end() if no such element exists. |
676 | //! |
677 | //! <b>Throws</b>: Nothing. |
678 | //! |
679 | //! <b>Complexity</b>: Linear to the number of elements erased. |
680 | //! |
681 | //! <b>Note</b>: Invalidates the iterators to the erased elements. |
682 | template <class Disposer> |
683 | iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer) |
684 | { |
685 | node_ptr bp(b.pointed_node()), ep(e.pointed_node()); |
686 | node_algorithms::unlink(bp, ep); |
687 | while(bp != ep){ |
688 | node_ptr to_erase(bp); |
689 | bp = node_traits::get_next(bp); |
690 | if(safemode_or_autounlink) |
691 | node_algorithms::init(to_erase); |
692 | disposer(priv_value_traits().to_value_ptr(to_erase)); |
693 | this->priv_size_traits().decrement(); |
694 | } |
695 | return e.unconst(); |
696 | } |
697 | |
698 | //! <b>Effects</b>: Erases all the elements of the container. |
699 | //! No destructors are called. |
700 | //! |
701 | //! <b>Throws</b>: Nothing. |
702 | //! |
703 | //! <b>Complexity</b>: Linear to the number of elements of the list. |
704 | //! if it's a safe-mode or auto-unlink value_type. Constant time otherwise. |
705 | //! |
706 | //! <b>Note</b>: Invalidates the iterators (but not the references) to the erased elements. |
707 | void clear() |
708 | { |
709 | if(safemode_or_autounlink){ |
710 | this->clear_and_dispose(detail::null_disposer()); |
711 | } |
712 | else{ |
713 | node_algorithms::init_header(this->get_root_node()); |
714 | this->priv_size_traits().set_size(size_type(0)); |
715 | } |
716 | } |
717 | |
718 | //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. |
719 | //! |
720 | //! <b>Effects</b>: Erases all the elements of the container. |
721 | //! No destructors are called. |
722 | //! Disposer::operator()(pointer) is called for the removed elements. |
723 | //! |
724 | //! <b>Throws</b>: Nothing. |
725 | //! |
726 | //! <b>Complexity</b>: Linear to the number of elements of the list. |
727 | //! |
728 | //! <b>Note</b>: Invalidates the iterators to the erased elements. |
729 | template <class Disposer> |
730 | void clear_and_dispose(Disposer disposer) |
731 | { |
732 | const_iterator it(this->begin()), itend(this->end()); |
733 | while(it != itend){ |
734 | node_ptr to_erase(it.pointed_node()); |
735 | ++it; |
736 | if(safemode_or_autounlink) |
737 | node_algorithms::init(to_erase); |
738 | disposer(priv_value_traits().to_value_ptr(to_erase)); |
739 | } |
740 | node_algorithms::init_header(this->get_root_node()); |
741 | this->priv_size_traits().set_size(0); |
742 | } |
743 | |
744 | //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. |
745 | //! Cloner should yield to nodes equivalent to the original nodes. |
746 | //! |
747 | //! <b>Effects</b>: Erases all the elements from *this |
748 | //! calling Disposer::operator()(pointer), clones all the |
749 | //! elements from src calling Cloner::operator()(const_reference ) |
750 | //! and inserts them on *this. |
751 | //! |
752 | //! If cloner throws, all cloned elements are unlinked and disposed |
753 | //! calling Disposer::operator()(pointer). |
754 | //! |
755 | //! <b>Complexity</b>: Linear to erased plus inserted elements. |
756 | //! |
757 | //! <b>Throws</b>: If cloner throws. Basic guarantee. |
758 | template <class Cloner, class Disposer> |
759 | void clone_from(const list_impl &src, Cloner cloner, Disposer disposer) |
760 | { |
761 | this->clear_and_dispose(disposer); |
762 | detail::exception_disposer<list_impl, Disposer> |
763 | rollback(*this, disposer); |
764 | const_iterator b(src.begin()), e(src.end()); |
765 | for(; b != e; ++b){ |
766 | this->push_back(*cloner(*b)); |
767 | } |
768 | rollback.release(); |
769 | } |
770 | |
771 | //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. |
772 | //! Cloner should yield to nodes equivalent to the original nodes. |
773 | //! |
774 | //! <b>Effects</b>: Erases all the elements from *this |
775 | //! calling Disposer::operator()(pointer), clones all the |
776 | //! elements from src calling Cloner::operator()(reference) |
777 | //! and inserts them on *this. |
778 | //! |
779 | //! If cloner throws, all cloned elements are unlinked and disposed |
780 | //! calling Disposer::operator()(pointer). |
781 | //! |
782 | //! <b>Complexity</b>: Linear to erased plus inserted elements. |
783 | //! |
784 | //! <b>Throws</b>: If cloner throws. Basic guarantee. |
785 | template <class Cloner, class Disposer> |
786 | void clone_from(BOOST_RV_REF(list_impl) src, Cloner cloner, Disposer disposer) |
787 | { |
788 | this->clear_and_dispose(disposer); |
789 | detail::exception_disposer<list_impl, Disposer> |
790 | rollback(*this, disposer); |
791 | iterator b(src.begin()), e(src.end()); |
792 | for(; b != e; ++b){ |
793 | this->push_back(*cloner(*b)); |
794 | } |
795 | rollback.release(); |
796 | } |
797 | |
798 | //! <b>Requires</b>: value must be an lvalue and p must be a valid iterator of *this. |
799 | //! |
800 | //! <b>Effects</b>: Inserts the value before the position pointed by p. |
801 | //! |
802 | //! <b>Returns</b>: An iterator to the inserted element. |
803 | //! |
804 | //! <b>Throws</b>: Nothing. |
805 | //! |
806 | //! <b>Complexity</b>: Constant time. No copy constructors are called. |
807 | //! |
808 | //! <b>Note</b>: Does not affect the validity of iterators and references. |
809 | iterator insert(const_iterator p, reference value) |
810 | { |
811 | node_ptr to_insert = this->priv_value_traits().to_node_ptr(value); |
812 | BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::inited(to_insert)); |
813 | node_algorithms::link_before(p.pointed_node(), to_insert); |
814 | this->priv_size_traits().increment(); |
815 | return iterator(to_insert, this->priv_value_traits_ptr()); |
816 | } |
817 | |
818 | //! <b>Requires</b>: Dereferencing iterator must yield |
819 | //! an lvalue of type value_type and p must be a valid iterator of *this. |
820 | //! |
821 | //! <b>Effects</b>: Inserts the range pointed by b and e before the position p. |
822 | //! No copy constructors are called. |
823 | //! |
824 | //! <b>Throws</b>: Nothing. |
825 | //! |
826 | //! <b>Complexity</b>: Linear to the number of elements inserted. |
827 | //! |
828 | //! <b>Note</b>: Does not affect the validity of iterators and references. |
829 | template<class Iterator> |
830 | void insert(const_iterator p, Iterator b, Iterator e) |
831 | { |
832 | for (; b != e; ++b) |
833 | this->insert(p, *b); |
834 | } |
835 | |
836 | //! <b>Requires</b>: Dereferencing iterator must yield |
837 | //! an lvalue of type value_type. |
838 | //! |
839 | //! <b>Effects</b>: Clears the list and inserts the range pointed by b and e. |
840 | //! No destructors or copy constructors are called. |
841 | //! |
842 | //! <b>Throws</b>: Nothing. |
843 | //! |
844 | //! <b>Complexity</b>: Linear to the number of elements inserted plus |
845 | //! linear to the elements contained in the list if it's a safe-mode |
846 | //! or auto-unlink value. |
847 | //! Linear to the number of elements inserted in the list otherwise. |
848 | //! |
849 | //! <b>Note</b>: Invalidates the iterators (but not the references) |
850 | //! to the erased elements. |
851 | template<class Iterator> |
852 | void assign(Iterator b, Iterator e) |
853 | { |
854 | this->clear(); |
855 | this->insert(this->cend(), b, e); |
856 | } |
857 | |
858 | //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. |
859 | //! |
860 | //! <b>Requires</b>: Dereferencing iterator must yield |
861 | //! an lvalue of type value_type. |
862 | //! |
863 | //! <b>Effects</b>: Clears the list and inserts the range pointed by b and e. |
864 | //! No destructors or copy constructors are called. |
865 | //! Disposer::operator()(pointer) is called for the removed elements. |
866 | //! |
867 | //! <b>Throws</b>: Nothing. |
868 | //! |
869 | //! <b>Complexity</b>: Linear to the number of elements inserted plus |
870 | //! linear to the elements contained in the list. |
871 | //! |
872 | //! <b>Note</b>: Invalidates the iterators (but not the references) |
873 | //! to the erased elements. |
874 | template<class Iterator, class Disposer> |
875 | void dispose_and_assign(Disposer disposer, Iterator b, Iterator e) |
876 | { |
877 | this->clear_and_dispose(disposer); |
878 | this->insert(this->cend(), b, e); |
879 | } |
880 | |
881 | //! <b>Requires</b>: p must be a valid iterator of *this. |
882 | //! |
883 | //! <b>Effects</b>: Transfers all the elements of list x to this list, before the |
884 | //! the element pointed by p. No destructors or copy constructors are called. |
885 | //! |
886 | //! <b>Throws</b>: Nothing. |
887 | //! |
888 | //! <b>Complexity</b>: Constant. |
889 | //! |
890 | //! <b>Note</b>: Iterators of values obtained from list x now point to elements of |
891 | //! this list. Iterators of this list and all the references are not invalidated. |
892 | void splice(const_iterator p, list_impl& x) |
893 | { |
894 | if(!x.empty()){ |
895 | node_algorithms::transfer |
896 | (p.pointed_node(), x.begin().pointed_node(), x.end().pointed_node()); |
897 | size_traits &thist = this->priv_size_traits(); |
898 | size_traits &xt = x.priv_size_traits(); |
899 | thist.increase(xt.get_size()); |
900 | xt.set_size(size_type(0)); |
901 | } |
902 | } |
903 | |
904 | //! <b>Requires</b>: p must be a valid iterator of *this. |
905 | //! new_ele must point to an element contained in list x. |
906 | //! |
907 | //! <b>Effects</b>: Transfers the value pointed by new_ele, from list x to this list, |
908 | //! before the element pointed by p. No destructors or copy constructors are called. |
909 | //! If p == new_ele or p == ++new_ele, this function is a null operation. |
910 | //! |
911 | //! <b>Throws</b>: Nothing. |
912 | //! |
913 | //! <b>Complexity</b>: Constant. |
914 | //! |
915 | //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this |
916 | //! list. Iterators of this list and all the references are not invalidated. |
917 | void splice(const_iterator p, list_impl&x, const_iterator new_ele) |
918 | { |
919 | node_algorithms::transfer(p.pointed_node(), new_ele.pointed_node()); |
920 | x.priv_size_traits().decrement(); |
921 | this->priv_size_traits().increment(); |
922 | } |
923 | |
924 | //! <b>Requires</b>: p must be a valid iterator of *this. |
925 | //! f and e must point to elements contained in list x. |
926 | //! |
927 | //! <b>Effects</b>: Transfers the range pointed by f and e from list x to this list, |
928 | //! before the element pointed by p. No destructors or copy constructors are called. |
929 | //! |
930 | //! <b>Throws</b>: Nothing. |
931 | //! |
932 | //! <b>Complexity</b>: Linear to the number of elements transferred |
933 | //! if constant-time size option is enabled. Constant-time otherwise. |
934 | //! |
935 | //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this |
936 | //! list. Iterators of this list and all the references are not invalidated. |
937 | void splice(const_iterator p, list_impl&x, const_iterator f, const_iterator e) |
938 | { |
939 | if(constant_time_size) |
940 | this->splice(p, x, f, e, node_algorithms::distance(f.pointed_node(), e.pointed_node())); |
941 | else |
942 | this->splice(p, x, f, e, 1);//intrusive::iterator_distance is a dummy value |
943 | } |
944 | |
945 | //! <b>Requires</b>: p must be a valid iterator of *this. |
946 | //! f and e must point to elements contained in list x. |
947 | //! n == distance(f, e) |
948 | //! |
949 | //! <b>Effects</b>: Transfers the range pointed by f and e from list x to this list, |
950 | //! before the element pointed by p. No destructors or copy constructors are called. |
951 | //! |
952 | //! <b>Throws</b>: Nothing. |
953 | //! |
954 | //! <b>Complexity</b>: Constant. |
955 | //! |
956 | //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this |
957 | //! list. Iterators of this list and all the references are not invalidated. |
958 | void splice(const_iterator p, list_impl&x, const_iterator f, const_iterator e, size_type n) |
959 | { |
960 | if(n){ |
961 | if(constant_time_size){ |
962 | BOOST_INTRUSIVE_INVARIANT_ASSERT(n == node_algorithms::distance(f.pointed_node(), e.pointed_node())); |
963 | node_algorithms::transfer(p.pointed_node(), f.pointed_node(), e.pointed_node()); |
964 | size_traits &thist = this->priv_size_traits(); |
965 | size_traits &xt = x.priv_size_traits(); |
966 | thist.increase(n); |
967 | xt.decrease(n); |
968 | } |
969 | else{ |
970 | node_algorithms::transfer(p.pointed_node(), f.pointed_node(), e.pointed_node()); |
971 | } |
972 | } |
973 | } |
974 | |
975 | //! <b>Effects</b>: This function sorts the list *this according to std::less<value_type>. |
976 | //! The sort is stable, that is, the relative order of equivalent elements is preserved. |
977 | //! |
978 | //! <b>Throws</b>: If value_traits::node_traits::node |
979 | //! constructor throws (this does not happen with predefined Boost.Intrusive hooks) |
980 | //! or std::less<value_type> throws. Basic guarantee. |
981 | //! |
982 | //! <b>Notes</b>: Iterators and references are not invalidated. |
983 | //! |
984 | //! <b>Complexity</b>: The number of comparisons is approximately N log N, where N |
985 | //! is the list's size. |
986 | void sort() |
987 | { this->sort(std::less<value_type>()); } |
988 | |
989 | //! <b>Requires</b>: p must be a comparison function that induces a strict weak ordering |
990 | //! |
991 | //! <b>Effects</b>: This function sorts the list *this according to p. The sort is |
992 | //! stable, that is, the relative order of equivalent elements is preserved. |
993 | //! |
994 | //! <b>Throws</b>: If value_traits::node_traits::node |
995 | //! constructor throws (this does not happen with predefined Boost.Intrusive hooks) |
996 | //! or the predicate throws. Basic guarantee. |
997 | //! |
998 | //! <b>Notes</b>: This won't throw if list_base_hook<> or |
999 | //! list_member_hook are used. |
1000 | //! Iterators and references are not invalidated. |
1001 | //! |
1002 | //! <b>Complexity</b>: The number of comparisons is approximately N log N, where N |
1003 | //! is the list's size. |
1004 | template<class Predicate> |
1005 | void sort(Predicate p) |
1006 | { |
1007 | if(node_traits::get_next(this->get_root_node()) |
1008 | != node_traits::get_previous(this->get_root_node())){ |
1009 | list_impl carry(this->priv_value_traits()); |
1010 | detail::array_initializer<list_impl, 64> counter(this->priv_value_traits()); |
1011 | int fill = 0; |
1012 | while(!this->empty()){ |
1013 | carry.splice(carry.cbegin(), *this, this->cbegin()); |
1014 | int i = 0; |
1015 | while(i < fill && !counter[i].empty()) { |
1016 | counter[i].merge(carry, p); |
1017 | carry.swap(counter[i++]); |
1018 | } |
1019 | carry.swap(counter[i]); |
1020 | if(i == fill) |
1021 | ++fill; |
1022 | } |
1023 | for (int i = 1; i < fill; ++i) |
1024 | counter[i].merge(counter[i-1], p); |
1025 | this->swap(counter[fill-1]); |
1026 | } |
1027 | } |
1028 | |
1029 | //! <b>Effects</b>: This function removes all of x's elements and inserts them |
1030 | //! in order into *this according to std::less<value_type>. The merge is stable; |
1031 | //! that is, if an element from *this is equivalent to one from x, then the element |
1032 | //! from *this will precede the one from x. |
1033 | //! |
1034 | //! <b>Throws</b>: If std::less<value_type> throws. Basic guarantee. |
1035 | //! |
1036 | //! <b>Complexity</b>: This function is linear time: it performs at most |
1037 | //! size() + x.size() - 1 comparisons. |
1038 | //! |
1039 | //! <b>Note</b>: Iterators and references are not invalidated |
1040 | void merge(list_impl& x) |
1041 | { this->merge(x, std::less<value_type>()); } |
1042 | |
1043 | //! <b>Requires</b>: p must be a comparison function that induces a strict weak |
1044 | //! ordering and both *this and x must be sorted according to that ordering |
1045 | //! The lists x and *this must be distinct. |
1046 | //! |
1047 | //! <b>Effects</b>: This function removes all of x's elements and inserts them |
1048 | //! in order into *this. The merge is stable; that is, if an element from *this is |
1049 | //! equivalent to one from x, then the element from *this will precede the one from x. |
1050 | //! |
1051 | //! <b>Throws</b>: If the predicate throws. Basic guarantee. |
1052 | //! |
1053 | //! <b>Complexity</b>: This function is linear time: it performs at most |
1054 | //! size() + x.size() - 1 comparisons. |
1055 | //! |
1056 | //! <b>Note</b>: Iterators and references are not invalidated. |
1057 | template<class Predicate> |
1058 | void merge(list_impl& x, Predicate p) |
1059 | { |
1060 | const_iterator e(this->cend()), ex(x.cend()); |
1061 | const_iterator b(this->cbegin()); |
1062 | while(!x.empty()){ |
1063 | const_iterator ix(x.cbegin()); |
1064 | while (b != e && !p(*ix, *b)){ |
1065 | ++b; |
1066 | } |
1067 | if(b == e){ |
1068 | //Now transfer the rest to the end of the container |
1069 | this->splice(e, x); |
1070 | break; |
1071 | } |
1072 | else{ |
1073 | size_type n(0); |
1074 | do{ |
1075 | ++ix; ++n; |
1076 | } while(ix != ex && p(*ix, *b)); |
1077 | this->splice(b, x, x.begin(), ix, n); |
1078 | } |
1079 | } |
1080 | } |
1081 | |
1082 | //! <b>Effects</b>: Reverses the order of elements in the list. |
1083 | //! |
1084 | //! <b>Throws</b>: Nothing. |
1085 | //! |
1086 | //! <b>Complexity</b>: This function is linear time. |
1087 | //! |
1088 | //! <b>Note</b>: Iterators and references are not invalidated |
1089 | void reverse() |
1090 | { node_algorithms::reverse(this->get_root_node()); } |
1091 | |
1092 | //! <b>Effects</b>: Removes all the elements that compare equal to value. |
1093 | //! No destructors are called. |
1094 | //! |
1095 | //! <b>Throws</b>: If std::equal_to<value_type> throws. Basic guarantee. |
1096 | //! |
1097 | //! <b>Complexity</b>: Linear time. It performs exactly size() comparisons for equality. |
1098 | //! |
1099 | //! <b>Note</b>: The relative order of elements that are not removed is unchanged, |
1100 | //! and iterators to elements that are not removed remain valid. |
1101 | void remove(const_reference value) |
1102 | { this->remove_if(detail::equal_to_value<const_reference>(value)); } |
1103 | |
1104 | //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. |
1105 | //! |
1106 | //! <b>Effects</b>: Removes all the elements that compare equal to value. |
1107 | //! Disposer::operator()(pointer) is called for every removed element. |
1108 | //! |
1109 | //! <b>Throws</b>: If std::equal_to<value_type> throws. Basic guarantee. |
1110 | //! |
1111 | //! <b>Complexity</b>: Linear time. It performs exactly size() comparisons for equality. |
1112 | //! |
1113 | //! <b>Note</b>: The relative order of elements that are not removed is unchanged, |
1114 | //! and iterators to elements that are not removed remain valid. |
1115 | template<class Disposer> |
1116 | void remove_and_dispose(const_reference value, Disposer disposer) |
1117 | { this->remove_and_dispose_if(detail::equal_to_value<const_reference>(value), disposer); } |
1118 | |
1119 | //! <b>Effects</b>: Removes all the elements for which a specified |
1120 | //! predicate is satisfied. No destructors are called. |
1121 | //! |
1122 | //! <b>Throws</b>: If pred throws. Basic guarantee. |
1123 | //! |
1124 | //! <b>Complexity</b>: Linear time. It performs exactly size() calls to the predicate. |
1125 | //! |
1126 | //! <b>Note</b>: The relative order of elements that are not removed is unchanged, |
1127 | //! and iterators to elements that are not removed remain valid. |
1128 | template<class Pred> |
1129 | void remove_if(Pred pred) |
1130 | { |
1131 | const node_ptr root_node = this->get_root_node(); |
1132 | typename node_algorithms::stable_partition_info info; |
1133 | node_algorithms::stable_partition |
1134 | (node_traits::get_next(root_node), root_node, detail::key_nodeptr_comp<Pred, value_traits>(pred, &this->priv_value_traits()), info); |
1135 | //Invariants preserved by stable_partition so erase can be safely called |
1136 | //The first element might have changed so calculate it again |
1137 | this->erase( const_iterator(node_traits::get_next(root_node), this->priv_value_traits_ptr()) |
1138 | , const_iterator(info.beg_2st_partition, this->priv_value_traits_ptr()) |
1139 | , info.num_1st_partition); |
1140 | } |
1141 | |
1142 | //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. |
1143 | //! |
1144 | //! <b>Effects</b>: Removes all the elements for which a specified |
1145 | //! predicate is satisfied. |
1146 | //! Disposer::operator()(pointer) is called for every removed element. |
1147 | //! |
1148 | //! <b>Throws</b>: If pred throws. Basic guarantee. |
1149 | //! |
1150 | //! <b>Complexity</b>: Linear time. It performs exactly size() comparisons for equality. |
1151 | //! |
1152 | //! <b>Note</b>: The relative order of elements that are not removed is unchanged, |
1153 | //! and iterators to elements that are not removed remain valid. |
1154 | template<class Pred, class Disposer> |
1155 | void remove_and_dispose_if(Pred pred, Disposer disposer) |
1156 | { |
1157 | const node_ptr root_node = this->get_root_node(); |
1158 | typename node_algorithms::stable_partition_info info; |
1159 | node_algorithms::stable_partition |
1160 | (node_traits::get_next(root_node), root_node, detail::key_nodeptr_comp<Pred, value_traits>(pred, &this->priv_value_traits()), info); |
1161 | //Invariants preserved by stable_partition so erase can be safely called |
1162 | //The first element might have changed so calculate it again |
1163 | this->erase_and_dispose( const_iterator(node_traits::get_next(root_node), this->priv_value_traits_ptr()) |
1164 | , const_iterator(info.beg_2st_partition, this->priv_value_traits_ptr()) |
1165 | , disposer); |
1166 | } |
1167 | |
1168 | //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent |
1169 | //! elements that are equal from the list. No destructors are called. |
1170 | //! |
1171 | //! <b>Throws</b>: If std::equal_to<value_type throws. Basic guarantee. |
1172 | //! |
1173 | //! <b>Complexity</b>: Linear time (size()-1 comparisons calls to pred()). |
1174 | //! |
1175 | //! <b>Note</b>: The relative order of elements that are not removed is unchanged, |
1176 | //! and iterators to elements that are not removed remain valid. |
1177 | void unique() |
1178 | { this->unique_and_dispose(std::equal_to<value_type>(), detail::null_disposer()); } |
1179 | |
1180 | //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent |
1181 | //! elements that satisfy some binary predicate from the list. |
1182 | //! No destructors are called. |
1183 | //! |
1184 | //! <b>Throws</b>: If pred throws. Basic guarantee. |
1185 | //! |
1186 | //! <b>Complexity</b>: Linear time (size()-1 comparisons equality comparisons). |
1187 | //! |
1188 | //! <b>Note</b>: The relative order of elements that are not removed is unchanged, |
1189 | //! and iterators to elements that are not removed remain valid. |
1190 | template<class BinaryPredicate> |
1191 | void unique(BinaryPredicate pred) |
1192 | { this->unique_and_dispose(pred, detail::null_disposer()); } |
1193 | |
1194 | //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. |
1195 | //! |
1196 | //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent |
1197 | //! elements that are equal from the list. |
1198 | //! Disposer::operator()(pointer) is called for every removed element. |
1199 | //! |
1200 | //! <b>Throws</b>: If std::equal_to<value_type throws. Basic guarantee. |
1201 | //! |
1202 | //! <b>Complexity</b>: Linear time (size()-1) comparisons equality comparisons. |
1203 | //! |
1204 | //! <b>Note</b>: The relative order of elements that are not removed is unchanged, |
1205 | //! and iterators to elements that are not removed remain valid. |
1206 | template<class Disposer> |
1207 | void unique_and_dispose(Disposer disposer) |
1208 | { this->unique_and_dispose(std::equal_to<value_type>(), disposer); } |
1209 | |
1210 | //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. |
1211 | //! |
1212 | //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent |
1213 | //! elements that satisfy some binary predicate from the list. |
1214 | //! Disposer::operator()(pointer) is called for every removed element. |
1215 | //! |
1216 | //! <b>Throws</b>: If pred throws. Basic guarantee. |
1217 | //! |
1218 | //! <b>Complexity</b>: Linear time (size()-1) comparisons equality comparisons. |
1219 | //! |
1220 | //! <b>Note</b>: The relative order of elements that are not removed is unchanged, |
1221 | //! and iterators to elements that are not removed remain valid. |
1222 | template<class BinaryPredicate, class Disposer> |
1223 | void unique_and_dispose(BinaryPredicate pred, Disposer disposer) |
1224 | { |
1225 | const_iterator itend(this->cend()); |
1226 | const_iterator cur(this->cbegin()); |
1227 | |
1228 | if(cur != itend){ |
1229 | const_iterator after(cur); |
1230 | ++after; |
1231 | while(after != itend){ |
1232 | if(pred(*cur, *after)){ |
1233 | after = this->erase_and_dispose(after, disposer); |
1234 | } |
1235 | else{ |
1236 | cur = after; |
1237 | ++after; |
1238 | } |
1239 | } |
1240 | } |
1241 | } |
1242 | |
1243 | //! <b>Requires</b>: value must be a reference to a value inserted in a list. |
1244 | //! |
1245 | //! <b>Effects</b>: This function returns a const_iterator pointing to the element |
1246 | //! |
1247 | //! <b>Throws</b>: Nothing. |
1248 | //! |
1249 | //! <b>Complexity</b>: Constant time. |
1250 | //! |
1251 | //! <b>Note</b>: Iterators and references are not invalidated. |
1252 | //! This static function is available only if the <i>value traits</i> |
1253 | //! is stateless. |
1254 | static iterator s_iterator_to(reference value) |
1255 | { |
1256 | BOOST_STATIC_ASSERT((!stateful_value_traits)); |
1257 | BOOST_INTRUSIVE_INVARIANT_ASSERT(!node_algorithms::inited(value_traits::to_node_ptr(value))); |
1258 | return iterator(value_traits::to_node_ptr(value), const_value_traits_ptr()); |
1259 | } |
1260 | |
1261 | //! <b>Requires</b>: value must be a const reference to a value inserted in a list. |
1262 | //! |
1263 | //! <b>Effects</b>: This function returns an iterator pointing to the element. |
1264 | //! |
1265 | //! <b>Throws</b>: Nothing. |
1266 | //! |
1267 | //! <b>Complexity</b>: Constant time. |
1268 | //! |
1269 | //! <b>Note</b>: Iterators and references are not invalidated. |
1270 | //! This static function is available only if the <i>value traits</i> |
1271 | //! is stateless. |
1272 | static const_iterator s_iterator_to(const_reference value) |
1273 | { |
1274 | BOOST_STATIC_ASSERT((!stateful_value_traits)); |
1275 | reference r =*detail::uncast(pointer_traits<const_pointer>::pointer_to(value)); |
1276 | BOOST_INTRUSIVE_INVARIANT_ASSERT(!node_algorithms::inited(value_traits::to_node_ptr(r))); |
1277 | return const_iterator(value_traits::to_node_ptr(r), const_value_traits_ptr()); |
1278 | } |
1279 | |
1280 | //! <b>Requires</b>: value must be a reference to a value inserted in a list. |
1281 | //! |
1282 | //! <b>Effects</b>: This function returns a const_iterator pointing to the element |
1283 | //! |
1284 | //! <b>Throws</b>: Nothing. |
1285 | //! |
1286 | //! <b>Complexity</b>: Constant time. |
1287 | //! |
1288 | //! <b>Note</b>: Iterators and references are not invalidated. |
1289 | iterator iterator_to(reference value) |
1290 | { |
1291 | BOOST_INTRUSIVE_INVARIANT_ASSERT(!node_algorithms::inited(this->priv_value_traits().to_node_ptr(value))); |
1292 | return iterator(this->priv_value_traits().to_node_ptr(value), this->priv_value_traits_ptr()); |
1293 | } |
1294 | |
1295 | //! <b>Requires</b>: value must be a const reference to a value inserted in a list. |
1296 | //! |
1297 | //! <b>Effects</b>: This function returns an iterator pointing to the element. |
1298 | //! |
1299 | //! <b>Throws</b>: Nothing. |
1300 | //! |
1301 | //! <b>Complexity</b>: Constant time. |
1302 | //! |
1303 | //! <b>Note</b>: Iterators and references are not invalidated. |
1304 | const_iterator iterator_to(const_reference value) const |
1305 | { |
1306 | reference r = *detail::uncast(pointer_traits<const_pointer>::pointer_to(value)); |
1307 | BOOST_INTRUSIVE_INVARIANT_ASSERT(!node_algorithms::inited(this->priv_value_traits().to_node_ptr(r))); |
1308 | return const_iterator(this->priv_value_traits().to_node_ptr(r), this->priv_value_traits_ptr()); |
1309 | } |
1310 | |
1311 | //! <b>Effects</b>: Asserts the integrity of the container. |
1312 | //! |
1313 | //! <b>Complexity</b>: Linear time. |
1314 | //! |
1315 | //! <b>Note</b>: The method has no effect when asserts are turned off (e.g., with NDEBUG). |
1316 | //! Experimental function, interface might change in future versions. |
1317 | void check() const |
1318 | { |
1319 | const_node_ptr = get_root_node(); |
1320 | // header's next and prev are never null |
1321 | BOOST_INTRUSIVE_INVARIANT_ASSERT(node_traits::get_next(header_ptr)); |
1322 | BOOST_INTRUSIVE_INVARIANT_ASSERT(node_traits::get_previous(header_ptr)); |
1323 | // header's next and prev either both point to header (empty list) or neither does |
1324 | BOOST_INTRUSIVE_INVARIANT_ASSERT((node_traits::get_next(header_ptr) == header_ptr) |
1325 | == (node_traits::get_previous(header_ptr) == header_ptr)); |
1326 | if (node_traits::get_next(header_ptr) == header_ptr) |
1327 | { |
1328 | if (constant_time_size) |
1329 | BOOST_INTRUSIVE_INVARIANT_ASSERT(this->priv_size_traits().get_size() == 0); |
1330 | return; |
1331 | } |
1332 | size_t node_count = 0; |
1333 | const_node_ptr p = header_ptr; |
1334 | while (true) |
1335 | { |
1336 | const_node_ptr next_p = node_traits::get_next(p); |
1337 | BOOST_INTRUSIVE_INVARIANT_ASSERT(next_p); |
1338 | BOOST_INTRUSIVE_INVARIANT_ASSERT(node_traits::get_previous(next_p) == p); |
1339 | p = next_p; |
1340 | if (p == header_ptr) break; |
1341 | ++node_count; |
1342 | } |
1343 | if (constant_time_size) |
1344 | BOOST_INTRUSIVE_INVARIANT_ASSERT(this->priv_size_traits().get_size() == node_count); |
1345 | } |
1346 | |
1347 | friend bool operator==(const list_impl &x, const list_impl &y) |
1348 | { |
1349 | if(constant_time_size && x.size() != y.size()){ |
1350 | return false; |
1351 | } |
1352 | return ::boost::intrusive::algo_equal(x.cbegin(), x.cend(), y.cbegin(), y.cend()); |
1353 | } |
1354 | |
1355 | friend bool operator!=(const list_impl &x, const list_impl &y) |
1356 | { return !(x == y); } |
1357 | |
1358 | friend bool operator<(const list_impl &x, const list_impl &y) |
1359 | { return ::boost::intrusive::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); } |
1360 | |
1361 | friend bool operator>(const list_impl &x, const list_impl &y) |
1362 | { return y < x; } |
1363 | |
1364 | friend bool operator<=(const list_impl &x, const list_impl &y) |
1365 | { return !(y < x); } |
1366 | |
1367 | friend bool operator>=(const list_impl &x, const list_impl &y) |
1368 | { return !(x < y); } |
1369 | |
1370 | friend void swap(list_impl &x, list_impl &y) |
1371 | { x.swap(y); } |
1372 | |
1373 | /// @cond |
1374 | |
1375 | private: |
1376 | static list_impl &priv_container_from_end_iterator(const const_iterator &end_iterator) |
1377 | { |
1378 | BOOST_STATIC_ASSERT((has_container_from_iterator)); |
1379 | node_ptr p = end_iterator.pointed_node(); |
1380 | header_holder_type* h = header_holder_type::get_holder(p); |
1381 | root_plus_size* r = detail::parent_from_member |
1382 | < root_plus_size, header_holder_type>(h, &root_plus_size::m_header); |
1383 | data_t *d = detail::parent_from_member<data_t, root_plus_size> |
1384 | ( r, &data_t::root_plus_size_); |
1385 | list_impl *s = detail::parent_from_member<list_impl, data_t>(d, &list_impl::data_); |
1386 | return *s; |
1387 | } |
1388 | /// @endcond |
1389 | }; |
1390 | |
1391 | |
1392 | //! Helper metafunction to define a \c list that yields to the same type when the |
1393 | //! same options (either explicitly or implicitly) are used. |
1394 | #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) |
1395 | template<class T, class ...Options> |
1396 | #else |
1397 | template<class T, class O1 = void, class O2 = void, class O3 = void, class O4 = void> |
1398 | #endif |
1399 | struct make_list |
1400 | { |
1401 | /// @cond |
1402 | typedef typename pack_options |
1403 | < list_defaults, |
1404 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) |
1405 | O1, O2, O3, O4 |
1406 | #else |
1407 | Options... |
1408 | #endif |
1409 | >::type packed_options; |
1410 | |
1411 | typedef typename detail::get_value_traits |
1412 | <T, typename packed_options::proto_value_traits>::type value_traits; |
1413 | typedef list_impl |
1414 | < |
1415 | value_traits, |
1416 | typename packed_options::size_type, |
1417 | packed_options::constant_time_size, |
1418 | typename packed_options::header_holder_type |
1419 | > implementation_defined; |
1420 | /// @endcond |
1421 | typedef implementation_defined type; |
1422 | }; |
1423 | |
1424 | |
1425 | #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
1426 | |
1427 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) |
1428 | template<class T, class O1, class O2, class O3, class O4> |
1429 | #else |
1430 | template<class T, class ...Options> |
1431 | #endif |
1432 | class list |
1433 | : public make_list<T, |
1434 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) |
1435 | O1, O2, O3, O4 |
1436 | #else |
1437 | Options... |
1438 | #endif |
1439 | >::type |
1440 | { |
1441 | typedef typename make_list |
1442 | <T, |
1443 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) |
1444 | O1, O2, O3, O4 |
1445 | #else |
1446 | Options... |
1447 | #endif |
1448 | >::type Base; |
1449 | //Assert if passed value traits are compatible with the type |
1450 | BOOST_STATIC_ASSERT((detail::is_same<typename Base::value_traits::value_type, T>::value)); |
1451 | BOOST_MOVABLE_BUT_NOT_COPYABLE(list) |
1452 | |
1453 | public: |
1454 | typedef typename Base::value_traits value_traits; |
1455 | typedef typename Base::iterator iterator; |
1456 | typedef typename Base::const_iterator const_iterator; |
1457 | |
1458 | explicit list(const value_traits &v_traits = value_traits()) |
1459 | : Base(v_traits) |
1460 | {} |
1461 | |
1462 | template<class Iterator> |
1463 | list(Iterator b, Iterator e, const value_traits &v_traits = value_traits()) |
1464 | : Base(b, e, v_traits) |
1465 | {} |
1466 | |
1467 | list(BOOST_RV_REF(list) x) |
1468 | : Base(BOOST_MOVE_BASE(Base, x)) |
1469 | {} |
1470 | |
1471 | list& operator=(BOOST_RV_REF(list) x) |
1472 | { return static_cast<list &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); } |
1473 | |
1474 | template <class Cloner, class Disposer> |
1475 | void clone_from(const list &src, Cloner cloner, Disposer disposer) |
1476 | { Base::clone_from(src, cloner, disposer); } |
1477 | |
1478 | template <class Cloner, class Disposer> |
1479 | void clone_from(BOOST_RV_REF(list) src, Cloner cloner, Disposer disposer) |
1480 | { Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer); } |
1481 | |
1482 | static list &container_from_end_iterator(iterator end_iterator) |
1483 | { return static_cast<list &>(Base::container_from_end_iterator(end_iterator)); } |
1484 | |
1485 | static const list &container_from_end_iterator(const_iterator end_iterator) |
1486 | { return static_cast<const list &>(Base::container_from_end_iterator(end_iterator)); } |
1487 | }; |
1488 | |
1489 | #endif |
1490 | |
1491 | } //namespace intrusive |
1492 | } //namespace boost |
1493 | |
1494 | #include <boost/intrusive/detail/config_end.hpp> |
1495 | |
1496 | #endif //BOOST_INTRUSIVE_LIST_HPP |
1497 | |