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