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_SLIST_HPP
15#define BOOST_INTRUSIVE_SLIST_HPP
16
17#include <boost/intrusive/detail/config_begin.hpp>
18#include <boost/intrusive/intrusive_fwd.hpp>
19
20#include <boost/intrusive/detail/assert.hpp>
21#include <boost/intrusive/slist_hook.hpp>
22#include <boost/intrusive/circular_slist_algorithms.hpp>
23#include <boost/intrusive/linear_slist_algorithms.hpp>
24#include <boost/intrusive/pointer_traits.hpp>
25#include <boost/intrusive/link_mode.hpp>
26#include <boost/intrusive/detail/get_value_traits.hpp>
27#include <boost/intrusive/detail/is_stateful_value_traits.hpp>
28#include <boost/intrusive/detail/default_header_holder.hpp>
29#include <boost/intrusive/detail/uncast.hpp>
30#include <boost/intrusive/detail/mpl.hpp>
31#include <boost/intrusive/detail/iterator.hpp>
32#include <boost/intrusive/detail/slist_iterator.hpp>
33#include <boost/intrusive/detail/array_initializer.hpp>
34#include <boost/intrusive/detail/exception_disposer.hpp>
35#include <boost/intrusive/detail/equal_to_value.hpp>
36#include <boost/intrusive/detail/key_nodeptr_comp.hpp>
37#include <boost/intrusive/detail/simple_disposers.hpp>
38#include <boost/intrusive/detail/size_holder.hpp>
39#include <boost/intrusive/detail/algorithm.hpp>
40
41#include <boost/move/utility_core.hpp>
42#include <boost/static_assert.hpp>
43
44#include <boost/intrusive/detail/minimal_less_equal_header.hpp>//std::less
45#include <cstddef> //std::size_t
46#include <boost/intrusive/detail/minimal_pair_header.hpp> //std::pair
47
48#if defined(BOOST_HAS_PRAGMA_ONCE)
49# pragma once
50#endif
51
52namespace boost {
53namespace intrusive {
54
55/// @cond
56
57template<class HeaderHolder, class NodePtr, bool>
58struct header_holder_plus_last
59{
60 HeaderHolder header_holder_;
61 NodePtr last_;
62};
63
64template<class HeaderHolder, class NodePtr>
65struct header_holder_plus_last<HeaderHolder, NodePtr, false>
66{
67 HeaderHolder header_holder_;
68};
69
70struct default_slist_hook_applier
71{ template <class T> struct apply{ typedef typename T::default_slist_hook type; }; };
72
73template<>
74struct is_default_hook_tag<default_slist_hook_applier>
75{ static const bool value = true; };
76
77struct slist_defaults
78{
79 typedef default_slist_hook_applier proto_value_traits;
80 static const bool constant_time_size = true;
81 static const bool linear = false;
82 typedef std::size_t size_type;
83 static const bool cache_last = false;
84 typedef void header_holder_type;
85};
86
87struct slist_bool_flags
88{
89 static const std::size_t linear_pos = 1u;
90 static const std::size_t constant_time_size_pos = 2u;
91 static const std::size_t cache_last_pos = 4u;
92};
93
94
95/// @endcond
96
97//! The class template slist is an intrusive container, that encapsulates
98//! a singly-linked list. You can use such a list to squeeze the last bit
99//! of performance from your application. Unfortunately, the little gains
100//! come with some huge drawbacks. A lot of member functions can't be
101//! implemented as efficiently as for standard containers. To overcome
102//! this limitation some other member functions with rather unusual semantics
103//! have to be introduced.
104//!
105//! The template parameter \c T is the type to be managed by the container.
106//! The user can specify additional options and if no options are provided
107//! default options are used.
108//!
109//! The container supports the following options:
110//! \c base_hook<>/member_hook<>/value_traits<>,
111//! \c constant_time_size<>, \c size_type<>,
112//! \c linear<> and \c cache_last<>.
113//!
114//! The iterators of slist are forward iterators. slist provides a static
115//! function called "previous" to compute the previous iterator of a given iterator.
116//! This function has linear complexity. To improve the usability esp. with
117//! the '*_after' functions, ++end() == begin() and previous(begin()) == end()
118//! are defined. An new special function "before_begin()" is defined, which returns
119//! an iterator that points one less the beginning of the list: ++before_begin() == begin()
120#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
121template<class T, class ...Options>
122#else
123template<class ValueTraits, class SizeType, std::size_t BoolFlags, typename HeaderHolder>
124#endif
125class slist_impl
126{
127 //Public typedefs
128 public:
129 typedef ValueTraits value_traits;
130 typedef typename value_traits::pointer pointer;
131 typedef typename value_traits::const_pointer const_pointer;
132 typedef typename pointer_traits<pointer>::element_type value_type;
133 typedef typename pointer_traits<pointer>::reference reference;
134 typedef typename pointer_traits<const_pointer>::reference const_reference;
135 typedef typename pointer_traits<pointer>::difference_type difference_type;
136 typedef SizeType size_type;
137 typedef slist_iterator<value_traits, false> iterator;
138 typedef slist_iterator<value_traits, true> const_iterator;
139 typedef typename value_traits::node_traits node_traits;
140 typedef typename node_traits::node node;
141 typedef typename node_traits::node_ptr node_ptr;
142 typedef typename node_traits::const_node_ptr const_node_ptr;
143 typedef typename detail::get_header_holder_type
144 < value_traits, HeaderHolder >::type header_holder_type;
145
146 static const bool constant_time_size = 0 != (BoolFlags & slist_bool_flags::constant_time_size_pos);
147 static const bool stateful_value_traits = detail::is_stateful_value_traits<value_traits>::value;
148 static const bool linear = 0 != (BoolFlags & slist_bool_flags::linear_pos);
149 static const bool cache_last = 0 != (BoolFlags & slist_bool_flags::cache_last_pos);
150 static const bool has_container_from_iterator =
151 detail::is_same< header_holder_type, detail::default_header_holder< node_traits > >::value;
152
153 typedef typename detail::if_c
154 < linear
155 , linear_slist_algorithms<node_traits>
156 , circular_slist_algorithms<node_traits>
157 >::type node_algorithms;
158
159 /// @cond
160 private:
161 typedef detail::size_holder<constant_time_size, size_type> size_traits;
162
163 //noncopyable
164 BOOST_MOVABLE_BUT_NOT_COPYABLE(slist_impl)
165
166 static const bool safemode_or_autounlink = is_safe_autounlink<value_traits::link_mode>::value;
167
168 //Constant-time size is incompatible with auto-unlink hooks!
169 BOOST_STATIC_ASSERT(!(constant_time_size && ((int)value_traits::link_mode == (int)auto_unlink)));
170 //Linear singly linked lists are incompatible with auto-unlink hooks!
171 BOOST_STATIC_ASSERT(!(linear && ((int)value_traits::link_mode == (int)auto_unlink)));
172 //A list with cached last node is incompatible with auto-unlink hooks!
173 BOOST_STATIC_ASSERT(!(cache_last && ((int)value_traits::link_mode == (int)auto_unlink)));
174
175 node_ptr get_end_node()
176 { return node_ptr(linear ? node_ptr() : this->get_root_node()); }
177
178 const_node_ptr get_end_node() const
179 {
180 return const_node_ptr
181 (linear ? const_node_ptr() : this->get_root_node()); }
182
183 node_ptr get_root_node()
184 { return data_.root_plus_size_.header_holder_.get_node(); }
185
186 const_node_ptr get_root_node() const
187 { return data_.root_plus_size_.header_holder_.get_node(); }
188
189 node_ptr get_last_node()
190 { return this->get_last_node(detail::bool_<cache_last>()); }
191
192 const_node_ptr get_last_node() const
193 { return this->get_last_node(detail::bool_<cache_last>()); }
194
195 void set_last_node(const node_ptr &n)
196 { return this->set_last_node(n, detail::bool_<cache_last>()); }
197
198 static node_ptr get_last_node(detail::bool_<false>)
199 {
200 //This function shall not be used if cache_last is not true
201 BOOST_INTRUSIVE_INVARIANT_ASSERT(cache_last);
202 return node_ptr();
203 }
204
205 static void set_last_node(const node_ptr &, detail::bool_<false>)
206 {
207 //This function shall not be used if cache_last is not true
208 BOOST_INTRUSIVE_INVARIANT_ASSERT(cache_last);
209 }
210
211 node_ptr get_last_node(detail::bool_<true>)
212 { return node_ptr(data_.root_plus_size_.last_); }
213
214 const_node_ptr get_last_node(detail::bool_<true>) const
215 { return const_node_ptr(data_.root_plus_size_.last_); }
216
217 void set_last_node(const node_ptr & n, detail::bool_<true>)
218 { data_.root_plus_size_.last_ = n; }
219
220 void set_default_constructed_state()
221 {
222 node_algorithms::init_header(this->get_root_node());
223 this->priv_size_traits().set_size(size_type(0));
224 if(cache_last){
225 this->set_last_node(this->get_root_node());
226 }
227 }
228
229 typedef header_holder_plus_last<header_holder_type, node_ptr, cache_last> header_holder_plus_last_t;
230 struct root_plus_size
231 : public size_traits
232 , public header_holder_plus_last_t
233 {};
234
235 struct data_t
236 : public slist_impl::value_traits
237 {
238 typedef typename slist_impl::value_traits value_traits;
239 explicit data_t(const value_traits &val_traits)
240 : value_traits(val_traits)
241 {}
242
243 root_plus_size root_plus_size_;
244 } data_;
245
246 size_traits &priv_size_traits()
247 { return data_.root_plus_size_; }
248
249 const size_traits &priv_size_traits() const
250 { return data_.root_plus_size_; }
251
252 const value_traits &priv_value_traits() const
253 { return data_; }
254
255 value_traits &priv_value_traits()
256 { return data_; }
257
258 typedef typename boost::intrusive::value_traits_pointers
259 <ValueTraits>::const_value_traits_ptr const_value_traits_ptr;
260
261 const_value_traits_ptr priv_value_traits_ptr() const
262 { return pointer_traits<const_value_traits_ptr>::pointer_to(this->priv_value_traits()); }
263
264 /// @endcond
265
266 public:
267
268 ///@cond
269
270 //! <b>Requires</b>: f and before_l belong to another slist.
271 //!
272 //! <b>Effects</b>: Transfers the range [f, before_l] to this
273 //! list, after the element pointed by prev_pos.
274 //! No destructors or copy constructors are called.
275 //!
276 //! <b>Throws</b>: Nothing.
277 //!
278 //! <b>Complexity</b>: Linear to the number of elements transferred
279 //! if constant_time_size is true. Constant-time otherwise.
280 //!
281 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this
282 //! list. Iterators of this list and all the references are not invalidated.
283 //!
284 //! <b>Warning</b>: Experimental function, don't use it!
285 slist_impl( const node_ptr & f, const node_ptr & before_l
286 , size_type n, const value_traits &v_traits = value_traits())
287 : data_(v_traits)
288 {
289 if(n){
290 this->priv_size_traits().set_size(n);
291 if(cache_last){
292 this->set_last_node(before_l);
293 }
294 node_traits::set_next(this->get_root_node(), f);
295 node_traits::set_next(before_l, this->get_end_node());
296 }
297 else{
298 this->set_default_constructed_state();
299 }
300 }
301
302 ///@endcond
303
304 //! <b>Effects</b>: constructs an empty list.
305 //!
306 //! <b>Complexity</b>: Constant
307 //!
308 //! <b>Throws</b>: If value_traits::node_traits::node
309 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks).
310 slist_impl()
311 : data_(value_traits())
312 { this->set_default_constructed_state(); }
313
314 //! <b>Effects</b>: constructs an empty list.
315 //!
316 //! <b>Complexity</b>: Constant
317 //!
318 //! <b>Throws</b>: If value_traits::node_traits::node
319 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks).
320 explicit slist_impl(const value_traits &v_traits)
321 : data_(v_traits)
322 { this->set_default_constructed_state(); }
323
324 //! <b>Requires</b>: Dereferencing iterator must yield an lvalue of type value_type.
325 //!
326 //! <b>Effects</b>: Constructs a list equal to [b ,e).
327 //!
328 //! <b>Complexity</b>: Linear in distance(b, e). No copy constructors are called.
329 //!
330 //! <b>Throws</b>: If value_traits::node_traits::node
331 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks).
332 template<class Iterator>
333 slist_impl(Iterator b, Iterator e, const value_traits &v_traits = value_traits())
334 : data_(v_traits)
335 {
336 this->set_default_constructed_state();
337 //nothrow, no need to rollback to release elements on exception
338 this->insert_after(this->cbefore_begin(), b, e);
339 }
340
341 //! <b>Effects</b>: to-do
342 //!
343 slist_impl(BOOST_RV_REF(slist_impl) x)
344 : data_(::boost::move(x.priv_value_traits()))
345 {
346 this->set_default_constructed_state();
347 //nothrow, no need to rollback to release elements on exception
348 this->swap(x);
349 }
350
351 //! <b>Effects</b>: to-do
352 //!
353 slist_impl& operator=(BOOST_RV_REF(slist_impl) x)
354 { this->swap(x); return *this; }
355
356 //! <b>Effects</b>: If it's a safe-mode
357 //! or auto-unlink value, the destructor does nothing
358 //! (ie. no code is generated). Otherwise it detaches all elements from this.
359 //! In this case the objects in the list are not deleted (i.e. no destructors
360 //! are called), but the hooks according to the value_traits template parameter
361 //! are set to their default value.
362 //!
363 //! <b>Complexity</b>: Linear to the number of elements in the list, if
364 //! it's a safe-mode or auto-unlink value. Otherwise constant.
365 ~slist_impl()
366 {
367 if(is_safe_autounlink<ValueTraits::link_mode>::value){
368 this->clear();
369 node_algorithms::init(this->get_root_node());
370 }
371 }
372
373 //! <b>Effects</b>: Erases all the elements of the container.
374 //!
375 //! <b>Throws</b>: Nothing.
376 //!
377 //! <b>Complexity</b>: Linear to the number of elements of the list.
378 //! if it's a safe-mode or auto-unlink value_type. Constant time otherwise.
379 //!
380 //! <b>Note</b>: Invalidates the iterators (but not the references) to the erased elements.
381 void clear()
382 {
383 if(safemode_or_autounlink){
384 this->clear_and_dispose(detail::null_disposer());
385 }
386 else{
387 this->set_default_constructed_state();
388 }
389 }
390
391 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
392 //!
393 //! <b>Effects</b>: Erases all the elements of the container
394 //! Disposer::operator()(pointer) is called for the removed elements.
395 //!
396 //! <b>Throws</b>: Nothing.
397 //!
398 //! <b>Complexity</b>: Linear to the number of elements of the list.
399 //!
400 //! <b>Note</b>: Invalidates the iterators to the erased elements.
401 template <class Disposer>
402 void clear_and_dispose(Disposer disposer)
403 {
404 const_iterator it(this->begin()), itend(this->end());
405 while(it != itend){
406 node_ptr to_erase(it.pointed_node());
407 ++it;
408 if(safemode_or_autounlink)
409 node_algorithms::init(to_erase);
410 disposer(priv_value_traits().to_value_ptr(to_erase));
411 }
412 this->set_default_constructed_state();
413 }
414
415 //! <b>Requires</b>: value must be an lvalue.
416 //!
417 //! <b>Effects</b>: Inserts the value in the front of the list.
418 //! No copy constructors are called.
419 //!
420 //! <b>Throws</b>: Nothing.
421 //!
422 //! <b>Complexity</b>: Constant.
423 //!
424 //! <b>Note</b>: Does not affect the validity of iterators and references.
425 void push_front(reference value)
426 {
427 node_ptr to_insert = priv_value_traits().to_node_ptr(value);
428 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::inited(to_insert));
429 if(cache_last){
430 if(this->empty()){
431 this->set_last_node(to_insert);
432 }
433 }
434 node_algorithms::link_after(this->get_root_node(), to_insert);
435 this->priv_size_traits().increment();
436 }
437
438 //! <b>Requires</b>: value must be an lvalue.
439 //!
440 //! <b>Effects</b>: Inserts the value in the back of the list.
441 //! No copy constructors are called.
442 //!
443 //! <b>Throws</b>: Nothing.
444 //!
445 //! <b>Complexity</b>: Constant.
446 //!
447 //! <b>Note</b>: Does not affect the validity of iterators and references.
448 //! This function is only available is cache_last<> is true.
449 void push_back(reference value)
450 {
451 BOOST_STATIC_ASSERT((cache_last));
452 node_ptr n = priv_value_traits().to_node_ptr(value);
453 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::inited(n));
454 node_algorithms::link_after(this->get_last_node(), n);
455 if(cache_last){
456 this->set_last_node(n);
457 }
458 this->priv_size_traits().increment();
459 }
460
461 //! <b>Effects</b>: Erases the first element of the list.
462 //! No destructors are called.
463 //!
464 //! <b>Throws</b>: Nothing.
465 //!
466 //! <b>Complexity</b>: Constant.
467 //!
468 //! <b>Note</b>: Invalidates the iterators (but not the references) to the erased element.
469 void pop_front()
470 { return this->pop_front_and_dispose(detail::null_disposer()); }
471
472 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
473 //!
474 //! <b>Effects</b>: Erases the first element of the list.
475 //! Disposer::operator()(pointer) is called for the removed element.
476 //!
477 //! <b>Throws</b>: Nothing.
478 //!
479 //! <b>Complexity</b>: Constant.
480 //!
481 //! <b>Note</b>: Invalidates the iterators to the erased element.
482 template<class Disposer>
483 void pop_front_and_dispose(Disposer disposer)
484 {
485 node_ptr to_erase = node_traits::get_next(this->get_root_node());
486 node_algorithms::unlink_after(this->get_root_node());
487 this->priv_size_traits().decrement();
488 if(safemode_or_autounlink)
489 node_algorithms::init(to_erase);
490 disposer(priv_value_traits().to_value_ptr(to_erase));
491 if(cache_last){
492 if(this->empty()){
493 this->set_last_node(this->get_root_node());
494 }
495 }
496 }
497
498 //! <b>Effects</b>: Returns a reference to the first element of the list.
499 //!
500 //! <b>Throws</b>: Nothing.
501 //!
502 //! <b>Complexity</b>: Constant.
503 reference front()
504 { return *this->priv_value_traits().to_value_ptr(node_traits::get_next(this->get_root_node())); }
505
506 //! <b>Effects</b>: Returns a const_reference to the first element of the list.
507 //!
508 //! <b>Throws</b>: Nothing.
509 //!
510 //! <b>Complexity</b>: Constant.
511 const_reference front() const
512 { return *this->priv_value_traits().to_value_ptr(detail::uncast(node_traits::get_next(this->get_root_node()))); }
513
514 //! <b>Effects</b>: Returns a reference to the last element of the list.
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 //! This function is only available is cache_last<> is true.
522 reference back()
523 {
524 BOOST_STATIC_ASSERT((cache_last));
525 return *this->priv_value_traits().to_value_ptr(this->get_last_node());
526 }
527
528 //! <b>Effects</b>: Returns a const_reference to the last element of the list.
529 //!
530 //! <b>Throws</b>: Nothing.
531 //!
532 //! <b>Complexity</b>: Constant.
533 //!
534 //! <b>Note</b>: Does not affect the validity of iterators and references.
535 //! This function is only available is cache_last<> is true.
536 const_reference back() const
537 {
538 BOOST_STATIC_ASSERT((cache_last));
539 return *this->priv_value_traits().to_value_ptr(this->get_last_node());
540 }
541
542 //! <b>Effects</b>: Returns an iterator to the first element contained in the list.
543 //!
544 //! <b>Throws</b>: Nothing.
545 //!
546 //! <b>Complexity</b>: Constant.
547 iterator begin()
548 { return iterator (node_traits::get_next(this->get_root_node()), this->priv_value_traits_ptr()); }
549
550 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the list.
551 //!
552 //! <b>Throws</b>: Nothing.
553 //!
554 //! <b>Complexity</b>: Constant.
555 const_iterator begin() const
556 { return const_iterator (node_traits::get_next(this->get_root_node()), this->priv_value_traits_ptr()); }
557
558 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the list.
559 //!
560 //! <b>Throws</b>: Nothing.
561 //!
562 //! <b>Complexity</b>: Constant.
563 const_iterator cbegin() const
564 { return const_iterator(node_traits::get_next(this->get_root_node()), this->priv_value_traits_ptr()); }
565
566 //! <b>Effects</b>: Returns an iterator to the end of the list.
567 //!
568 //! <b>Throws</b>: Nothing.
569 //!
570 //! <b>Complexity</b>: Constant.
571 iterator end()
572 { return iterator(this->get_end_node(), this->priv_value_traits_ptr()); }
573
574 //! <b>Effects</b>: Returns a const_iterator to the end of the list.
575 //!
576 //! <b>Throws</b>: Nothing.
577 //!
578 //! <b>Complexity</b>: Constant.
579 const_iterator end() const
580 { return const_iterator(detail::uncast(this->get_end_node()), this->priv_value_traits_ptr()); }
581
582 //! <b>Effects</b>: Returns a const_iterator to the end of the list.
583 //!
584 //! <b>Throws</b>: Nothing.
585 //!
586 //! <b>Complexity</b>: Constant.
587 const_iterator cend() const
588 { return this->end(); }
589
590 //! <b>Effects</b>: Returns an iterator that points to a position
591 //! before the first element. Equivalent to "end()"
592 //!
593 //! <b>Throws</b>: Nothing.
594 //!
595 //! <b>Complexity</b>: Constant.
596 iterator before_begin()
597 { return iterator(this->get_root_node(), this->priv_value_traits_ptr()); }
598
599 //! <b>Effects</b>: Returns an iterator that points to a position
600 //! before the first element. Equivalent to "end()"
601 //!
602 //! <b>Throws</b>: Nothing.
603 //!
604 //! <b>Complexity</b>: Constant.
605 const_iterator before_begin() const
606 { return const_iterator(detail::uncast(this->get_root_node()), this->priv_value_traits_ptr()); }
607
608 //! <b>Effects</b>: Returns an iterator that points to a position
609 //! before the first element. Equivalent to "end()"
610 //!
611 //! <b>Throws</b>: Nothing.
612 //!
613 //! <b>Complexity</b>: Constant.
614 const_iterator cbefore_begin() const
615 { return this->before_begin(); }
616
617 //! <b>Effects</b>: Returns an iterator to the last element contained in the list.
618 //!
619 //! <b>Throws</b>: Nothing.
620 //!
621 //! <b>Complexity</b>: Constant.
622 //!
623 //! <b>Note</b>: This function is present only if cached_last<> option is true.
624 iterator last()
625 {
626 //This function shall not be used if cache_last is not true
627 BOOST_INTRUSIVE_INVARIANT_ASSERT(cache_last);
628 return iterator (this->get_last_node(), this->priv_value_traits_ptr());
629 }
630
631 //! <b>Effects</b>: Returns a const_iterator to the last element contained in the list.
632 //!
633 //! <b>Throws</b>: Nothing.
634 //!
635 //! <b>Complexity</b>: Constant.
636 //!
637 //! <b>Note</b>: This function is present only if cached_last<> option is true.
638 const_iterator last() const
639 {
640 //This function shall not be used if cache_last is not true
641 BOOST_INTRUSIVE_INVARIANT_ASSERT(cache_last);
642 return const_iterator (this->get_last_node(), this->priv_value_traits_ptr());
643 }
644
645 //! <b>Effects</b>: Returns a const_iterator to the last element contained in the list.
646 //!
647 //! <b>Throws</b>: Nothing.
648 //!
649 //! <b>Complexity</b>: Constant.
650 //!
651 //! <b>Note</b>: This function is present only if cached_last<> option is true.
652 const_iterator clast() const
653 { return const_iterator(this->get_last_node(), this->priv_value_traits_ptr()); }
654
655 //! <b>Precondition</b>: end_iterator must be a valid end iterator
656 //! of slist.
657 //!
658 //! <b>Effects</b>: Returns a const reference to the slist associated to the end iterator
659 //!
660 //! <b>Throws</b>: Nothing.
661 //!
662 //! <b>Complexity</b>: Constant.
663 static slist_impl &container_from_end_iterator(iterator end_iterator)
664 { return slist_impl::priv_container_from_end_iterator(end_iterator); }
665
666 //! <b>Precondition</b>: end_iterator must be a valid end const_iterator
667 //! of slist.
668 //!
669 //! <b>Effects</b>: Returns a const reference to the slist associated to the end iterator
670 //!
671 //! <b>Throws</b>: Nothing.
672 //!
673 //! <b>Complexity</b>: Constant.
674 static const slist_impl &container_from_end_iterator(const_iterator end_iterator)
675 { return slist_impl::priv_container_from_end_iterator(end_iterator); }
676
677 //! <b>Effects</b>: Returns the number of the elements contained in the list.
678 //!
679 //! <b>Throws</b>: Nothing.
680 //!
681 //! <b>Complexity</b>: Linear to the number of elements contained in the list.
682 //! if constant_time_size is false. Constant time otherwise.
683 //!
684 //! <b>Note</b>: Does not affect the validity of iterators and references.
685 size_type size() const
686 {
687 if(constant_time_size)
688 return this->priv_size_traits().get_size();
689 else
690 return node_algorithms::count(this->get_root_node()) - 1;
691 }
692
693 //! <b>Effects</b>: Returns true if the list contains no elements.
694 //!
695 //! <b>Throws</b>: Nothing.
696 //!
697 //! <b>Complexity</b>: Constant.
698 //!
699 //! <b>Note</b>: Does not affect the validity of iterators and references.
700 bool empty() const
701 { return node_algorithms::unique(this->get_root_node()); }
702
703 //! <b>Effects</b>: Swaps the elements of x and *this.
704 //!
705 //! <b>Throws</b>: Nothing.
706 //!
707 //! <b>Complexity</b>: Linear to the number of elements of both lists.
708 //! Constant-time if linear<> and/or cache_last<> options are used.
709 //!
710 //! <b>Note</b>: Does not affect the validity of iterators and references.
711 void swap(slist_impl& other)
712 {
713 if(cache_last){
714 priv_swap_cache_last(this, &other);
715 }
716 else{
717 this->priv_swap_lists(this->get_root_node(), other.get_root_node(), detail::bool_<linear>());
718 }
719 this->priv_size_traits().swap(other.priv_size_traits());
720 }
721
722 //! <b>Effects</b>: Moves backwards all the elements, so that the first
723 //! element becomes the second, the second becomes the third...
724 //! the last element becomes the first one.
725 //!
726 //! <b>Throws</b>: Nothing.
727 //!
728 //! <b>Complexity</b>: Linear to the number of elements plus the number shifts.
729 //!
730 //! <b>Note</b>: Iterators Does not affect the validity of iterators and references.
731 void shift_backwards(size_type n = 1)
732 { this->priv_shift_backwards(n, detail::bool_<linear>()); }
733
734 //! <b>Effects</b>: Moves forward all the elements, so that the second
735 //! element becomes the first, the third becomes the second...
736 //! the first element becomes the last one.
737 //!
738 //! <b>Throws</b>: Nothing.
739 //!
740 //! <b>Complexity</b>: Linear to the number of elements plus the number shifts.
741 //!
742 //! <b>Note</b>: Does not affect the validity of iterators and references.
743 void shift_forward(size_type n = 1)
744 { this->priv_shift_forward(n, detail::bool_<linear>()); }
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.
760 template <class Cloner, class Disposer>
761 void clone_from(const slist_impl &src, Cloner cloner, Disposer disposer)
762 {
763 this->clear_and_dispose(disposer);
764 detail::exception_disposer<slist_impl, Disposer>
765 rollback(*this, disposer);
766 const_iterator prev(this->cbefore_begin());
767 const_iterator b(src.begin()), e(src.end());
768 for(; b != e; ++b){
769 prev = this->insert_after(prev, *cloner(*b));
770 }
771 rollback.release();
772 }
773
774 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
775 //! Cloner should yield to nodes equivalent to the original nodes.
776 //!
777 //! <b>Effects</b>: Erases all the elements from *this
778 //! calling Disposer::operator()(pointer), clones all the
779 //! elements from src calling Cloner::operator()(reference)
780 //! and inserts them on *this.
781 //!
782 //! If cloner throws, all cloned elements are unlinked and disposed
783 //! calling Disposer::operator()(pointer).
784 //!
785 //! <b>Complexity</b>: Linear to erased plus inserted elements.
786 //!
787 //! <b>Throws</b>: If cloner throws.
788 template <class Cloner, class Disposer>
789 void clone_from(BOOST_RV_REF(slist_impl) src, Cloner cloner, Disposer disposer)
790 {
791 this->clear_and_dispose(disposer);
792 detail::exception_disposer<slist_impl, Disposer>
793 rollback(*this, disposer);
794 iterator prev(this->cbefore_begin());
795 iterator b(src.begin()), e(src.end());
796 for(; b != e; ++b){
797 prev = this->insert_after(prev, *cloner(*b));
798 }
799 rollback.release();
800 }
801
802 //! <b>Requires</b>: value must be an lvalue and prev_p must point to an element
803 //! contained by the list or to end().
804 //!
805 //! <b>Effects</b>: Inserts the value after the position pointed by prev_p.
806 //! No copy constructor is called.
807 //!
808 //! <b>Returns</b>: An iterator to the inserted element.
809 //!
810 //! <b>Throws</b>: Nothing.
811 //!
812 //! <b>Complexity</b>: Constant.
813 //!
814 //! <b>Note</b>: Does not affect the validity of iterators and references.
815 iterator insert_after(const_iterator prev_p, reference value)
816 {
817 node_ptr n = priv_value_traits().to_node_ptr(value);
818 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::inited(n));
819 node_ptr prev_n(prev_p.pointed_node());
820 node_algorithms::link_after(prev_n, n);
821 if(cache_last && (this->get_last_node() == prev_n)){
822 this->set_last_node(n);
823 }
824 this->priv_size_traits().increment();
825 return iterator (n, this->priv_value_traits_ptr());
826 }
827
828 //! <b>Requires</b>: Dereferencing iterator must yield
829 //! an lvalue of type value_type and prev_p must point to an element
830 //! contained by the list or to the end node.
831 //!
832 //! <b>Effects</b>: Inserts the [f, l)
833 //! after the position prev_p.
834 //!
835 //! <b>Throws</b>: Nothing.
836 //!
837 //! <b>Complexity</b>: Linear to the number of elements inserted.
838 //!
839 //! <b>Note</b>: Does not affect the validity of iterators and references.
840 template<class Iterator>
841 void insert_after(const_iterator prev_p, Iterator f, Iterator l)
842 {
843 //Insert first nodes avoiding cache and size checks
844 size_type count = 0;
845 node_ptr prev_n(prev_p.pointed_node());
846 for (; f != l; ++f, ++count){
847 const node_ptr n = priv_value_traits().to_node_ptr(*f);
848 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::inited(n));
849 node_algorithms::link_after(prev_n, n);
850 prev_n = n;
851 }
852 //Now fix special cases if needed
853 if(cache_last && (this->get_last_node() == prev_p.pointed_node())){
854 this->set_last_node(prev_n);
855 }
856 if(constant_time_size){
857 this->priv_size_traits().increase(count);
858 }
859 }
860
861 //! <b>Requires</b>: value must be an lvalue and p must point to an element
862 //! contained by the list or to end().
863 //!
864 //! <b>Effects</b>: Inserts the value before the position pointed by p.
865 //! No copy constructor is called.
866 //!
867 //! <b>Throws</b>: Nothing.
868 //!
869 //! <b>Complexity</b>: Linear to the number of elements before p.
870 //! Constant-time if cache_last<> is true and p == end().
871 //!
872 //! <b>Note</b>: Does not affect the validity of iterators and references.
873 iterator insert(const_iterator p, reference value)
874 { return this->insert_after(this->previous(p), value); }
875
876 //! <b>Requires</b>: Dereferencing iterator must yield
877 //! an lvalue of type value_type and p must point to an element
878 //! contained by the list or to the end node.
879 //!
880 //! <b>Effects</b>: Inserts the pointed by b and e
881 //! before the position p. No copy constructors are called.
882 //!
883 //! <b>Throws</b>: Nothing.
884 //!
885 //! <b>Complexity</b>: Linear to the number of elements inserted plus linear
886 //! to the elements before b.
887 //! Linear to the number of elements to insert if cache_last<> option is true and p == end().
888 //!
889 //! <b>Note</b>: Does not affect the validity of iterators and references.
890 template<class Iterator>
891 void insert(const_iterator p, Iterator b, Iterator e)
892 { return this->insert_after(this->previous(p), b, e); }
893
894 //! <b>Effects</b>: Erases the element after the element pointed by prev of
895 //! the list. No destructors are called.
896 //!
897 //! <b>Returns</b>: the first element remaining beyond the removed elements,
898 //! or end() if no such element exists.
899 //!
900 //! <b>Throws</b>: Nothing.
901 //!
902 //! <b>Complexity</b>: Constant.
903 //!
904 //! <b>Note</b>: Invalidates the iterators (but not the references) to the
905 //! erased element.
906 iterator erase_after(const_iterator prev)
907 { return this->erase_after_and_dispose(prev, detail::null_disposer()); }
908
909 //! <b>Effects</b>: Erases the range (before_f, l) from
910 //! the list. No destructors are called.
911 //!
912 //! <b>Returns</b>: the first element remaining beyond the removed elements,
913 //! or end() if no such element exists.
914 //!
915 //! <b>Throws</b>: Nothing.
916 //!
917 //! <b>Complexity</b>: Linear to the number of erased elements if it's a safe-mode
918 //! , auto-unlink value or constant-time size is activated. Constant time otherwise.
919 //!
920 //! <b>Note</b>: Invalidates the iterators (but not the references) to the
921 //! erased element.
922 iterator erase_after(const_iterator before_f, const_iterator l)
923 {
924 if(safemode_or_autounlink || constant_time_size){
925 return this->erase_after_and_dispose(before_f, l, detail::null_disposer());
926 }
927 else{
928 const node_ptr bfp = before_f.pointed_node();
929 const node_ptr lp = l.pointed_node();
930 if(cache_last){
931 if(lp == this->get_end_node()){
932 this->set_last_node(bfp);
933 }
934 }
935 node_algorithms::unlink_after(bfp, lp);
936 return l.unconst();
937 }
938 }
939
940 //! <b>Effects</b>: Erases the range (before_f, l) from
941 //! the list. n must be distance(before_f, l) - 1.
942 //! No destructors are called.
943 //!
944 //! <b>Returns</b>: the first element remaining beyond the removed elements,
945 //! or end() if no such element exists.
946 //!
947 //! <b>Throws</b>: Nothing.
948 //!
949 //! <b>Complexity</b>: constant-time if link_mode is normal_link.
950 //! Linear to the elements (l - before_f) otherwise.
951 //!
952 //! <b>Note</b>: Invalidates the iterators (but not the references) to the
953 //! erased element.
954 iterator erase_after(const_iterator before_f, const_iterator l, size_type n)
955 {
956 BOOST_INTRUSIVE_INVARIANT_ASSERT(node_algorithms::distance((++const_iterator(before_f)).pointed_node(), l.pointed_node()) == n);
957 if(safemode_or_autounlink){
958 return this->erase_after(before_f, l);
959 }
960 else{
961 const node_ptr bfp = before_f.pointed_node();
962 const node_ptr lp = l.pointed_node();
963 if(cache_last){
964 if((lp == this->get_end_node())){
965 this->set_last_node(bfp);
966 }
967 }
968 node_algorithms::unlink_after(bfp, lp);
969 if(constant_time_size){
970 this->priv_size_traits().decrease(n);
971 }
972 return l.unconst();
973 }
974 }
975
976 //! <b>Effects</b>: Erases the element pointed by i of the list.
977 //! No destructors are called.
978 //!
979 //! <b>Returns</b>: the first element remaining beyond the removed element,
980 //! or end() if no such element exists.
981 //!
982 //! <b>Throws</b>: Nothing.
983 //!
984 //! <b>Complexity</b>: Linear to the elements before i.
985 //!
986 //! <b>Note</b>: Invalidates the iterators (but not the references) to the
987 //! erased element.
988 iterator erase(const_iterator i)
989 { return this->erase_after(this->previous(i)); }
990
991 //! <b>Requires</b>: f and l must be valid iterator to elements in *this.
992 //!
993 //! <b>Effects</b>: Erases the range pointed by b and e.
994 //! No destructors are called.
995 //!
996 //! <b>Returns</b>: the first element remaining beyond the removed elements,
997 //! or end() if no such element exists.
998 //!
999 //! <b>Throws</b>: Nothing.
1000 //!
1001 //! <b>Complexity</b>: Linear to the elements before l.
1002 //!
1003 //! <b>Note</b>: Invalidates the iterators (but not the references) to the
1004 //! erased elements.
1005 iterator erase(const_iterator f, const_iterator l)
1006 { return this->erase_after(this->previous(f), l); }
1007
1008 //! <b>Effects</b>: Erases the range [f, l) from
1009 //! the list. n must be distance(f, l).
1010 //! No destructors are called.
1011 //!
1012 //! <b>Returns</b>: the first element remaining beyond the removed elements,
1013 //! or end() if no such element exists.
1014 //!
1015 //! <b>Throws</b>: Nothing.
1016 //!
1017 //! <b>Complexity</b>: linear to the elements before f if link_mode is normal_link
1018 //! and constant_time_size is activated. Linear to the elements before l otherwise.
1019 //!
1020 //! <b>Note</b>: Invalidates the iterators (but not the references) to the
1021 //! erased element.
1022 iterator erase(const_iterator f, const_iterator l, size_type n)
1023 { return this->erase_after(this->previous(f), l, n); }
1024
1025 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
1026 //!
1027 //! <b>Effects</b>: Erases the element after the element pointed by prev of
1028 //! the list.
1029 //! Disposer::operator()(pointer) is called for the removed element.
1030 //!
1031 //! <b>Returns</b>: the first element remaining beyond the removed elements,
1032 //! or end() if no such element exists.
1033 //!
1034 //! <b>Throws</b>: Nothing.
1035 //!
1036 //! <b>Complexity</b>: Constant.
1037 //!
1038 //! <b>Note</b>: Invalidates the iterators to the erased element.
1039 template<class Disposer>
1040 iterator erase_after_and_dispose(const_iterator prev, Disposer disposer)
1041 {
1042 const_iterator it(prev);
1043 ++it;
1044 node_ptr to_erase(it.pointed_node());
1045 ++it;
1046 node_ptr prev_n(prev.pointed_node());
1047 node_algorithms::unlink_after(prev_n);
1048 if(cache_last && (to_erase == this->get_last_node())){
1049 this->set_last_node(prev_n);
1050 }
1051 if(safemode_or_autounlink)
1052 node_algorithms::init(to_erase);
1053 disposer(priv_value_traits().to_value_ptr(to_erase));
1054 this->priv_size_traits().decrement();
1055 return it.unconst();
1056 }
1057
1058 /// @cond
1059
1060 static iterator s_insert_after(const_iterator const prev_p, reference value)
1061 {
1062 BOOST_STATIC_ASSERT(((!cache_last)&&(!constant_time_size)&&(!stateful_value_traits)));
1063 node_ptr const n = value_traits::to_node_ptr(value);
1064 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::inited(n));
1065 node_algorithms::link_after(prev_p.pointed_node(), n);
1066 return iterator (n, const_value_traits_ptr());
1067 }
1068
1069 template<class Disposer>
1070 static iterator s_erase_after_and_dispose(const_iterator prev, Disposer disposer)
1071 {
1072 BOOST_STATIC_ASSERT(((!cache_last)&&(!constant_time_size)&&(!stateful_value_traits)));
1073 const_iterator it(prev);
1074 ++it;
1075 node_ptr to_erase(it.pointed_node());
1076 ++it;
1077 node_ptr prev_n(prev.pointed_node());
1078 node_algorithms::unlink_after(prev_n);
1079 if(safemode_or_autounlink)
1080 node_algorithms::init(to_erase);
1081 disposer(value_traits::to_value_ptr(to_erase));
1082 return it.unconst();
1083 }
1084
1085 template<class Disposer>
1086 static iterator s_erase_after_and_dispose(const_iterator before_f, const_iterator l, Disposer disposer)
1087 {
1088 BOOST_STATIC_ASSERT(((!cache_last)&&(!constant_time_size)&&(!stateful_value_traits)));
1089 node_ptr bfp(before_f.pointed_node()), lp(l.pointed_node());
1090 node_ptr fp(node_traits::get_next(bfp));
1091 node_algorithms::unlink_after(bfp, lp);
1092 while(fp != lp){
1093 node_ptr to_erase(fp);
1094 fp = node_traits::get_next(fp);
1095 if(safemode_or_autounlink)
1096 node_algorithms::init(to_erase);
1097 disposer(value_traits::to_value_ptr(to_erase));
1098 }
1099 return l.unconst();
1100 }
1101
1102 static iterator s_erase_after(const_iterator prev)
1103 { return s_erase_after_and_dispose(prev, detail::null_disposer()); }
1104
1105 /// @endcond
1106
1107 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
1108 //!
1109 //! <b>Effects</b>: Erases the range (before_f, l) from
1110 //! the list.
1111 //! Disposer::operator()(pointer) is called for the removed elements.
1112 //!
1113 //! <b>Returns</b>: the first element remaining beyond the removed elements,
1114 //! or end() if no such element exists.
1115 //!
1116 //! <b>Throws</b>: Nothing.
1117 //!
1118 //! <b>Complexity</b>: Linear to the elements (l - before_f + 1).
1119 //!
1120 //! <b>Note</b>: Invalidates the iterators to the erased element.
1121 template<class Disposer>
1122 iterator erase_after_and_dispose(const_iterator before_f, const_iterator l, Disposer disposer)
1123 {
1124 node_ptr bfp(before_f.pointed_node()), lp(l.pointed_node());
1125 node_ptr fp(node_traits::get_next(bfp));
1126 node_algorithms::unlink_after(bfp, lp);
1127 while(fp != lp){
1128 node_ptr to_erase(fp);
1129 fp = node_traits::get_next(fp);
1130 if(safemode_or_autounlink)
1131 node_algorithms::init(to_erase);
1132 disposer(priv_value_traits().to_value_ptr(to_erase));
1133 this->priv_size_traits().decrement();
1134 }
1135 if(cache_last && (node_traits::get_next(bfp) == this->get_end_node())){
1136 this->set_last_node(bfp);
1137 }
1138 return l.unconst();
1139 }
1140
1141 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
1142 //!
1143 //! <b>Effects</b>: Erases the element pointed by i of the list.
1144 //! No destructors are called.
1145 //! Disposer::operator()(pointer) is called for the removed element.
1146 //!
1147 //! <b>Returns</b>: the first element remaining beyond the removed element,
1148 //! or end() if no such element exists.
1149 //!
1150 //! <b>Throws</b>: Nothing.
1151 //!
1152 //! <b>Complexity</b>: Linear to the elements before i.
1153 //!
1154 //! <b>Note</b>: Invalidates the iterators (but not the references) to the
1155 //! erased element.
1156 template<class Disposer>
1157 iterator erase_and_dispose(const_iterator i, Disposer disposer)
1158 { return this->erase_after_and_dispose(this->previous(i), disposer); }
1159
1160 #if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1161 template<class Disposer>
1162 iterator erase_and_dispose(iterator i, Disposer disposer)
1163 { return this->erase_and_dispose(const_iterator(i), disposer); }
1164 #endif
1165
1166 //! <b>Requires</b>: f and l must be valid iterator to elements in *this.
1167 //! Disposer::operator()(pointer) shouldn't throw.
1168 //!
1169 //! <b>Effects</b>: Erases the range pointed by b and e.
1170 //! No destructors are called.
1171 //! Disposer::operator()(pointer) is called for the removed elements.
1172 //!
1173 //! <b>Returns</b>: the first element remaining beyond the removed elements,
1174 //! or end() if no such element exists.
1175 //!
1176 //! <b>Throws</b>: Nothing.
1177 //!
1178 //! <b>Complexity</b>: Linear to the number of erased elements plus linear
1179 //! to the elements before f.
1180 //!
1181 //! <b>Note</b>: Invalidates the iterators (but not the references) to the
1182 //! erased elements.
1183 template<class Disposer>
1184 iterator erase_and_dispose(const_iterator f, const_iterator l, Disposer disposer)
1185 { return this->erase_after_and_dispose(this->previous(f), l, disposer); }
1186
1187 //! <b>Requires</b>: Dereferencing iterator must yield
1188 //! an lvalue of type value_type.
1189 //!
1190 //! <b>Effects</b>: Clears the list and inserts the range pointed by b and e.
1191 //! No destructors or copy constructors are called.
1192 //!
1193 //! <b>Throws</b>: Nothing.
1194 //!
1195 //! <b>Complexity</b>: Linear to the number of elements inserted plus
1196 //! linear to the elements contained in the list if it's a safe-mode
1197 //! or auto-unlink value.
1198 //! Linear to the number of elements inserted in the list otherwise.
1199 //!
1200 //! <b>Note</b>: Invalidates the iterators (but not the references)
1201 //! to the erased elements.
1202 template<class Iterator>
1203 void assign(Iterator b, Iterator e)
1204 {
1205 this->clear();
1206 this->insert_after(this->cbefore_begin(), b, e);
1207 }
1208
1209 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
1210 //!
1211 //! <b>Requires</b>: Dereferencing iterator must yield
1212 //! an lvalue of type value_type.
1213 //!
1214 //! <b>Effects</b>: Clears the list and inserts the range pointed by b and e.
1215 //! No destructors or copy constructors are called.
1216 //! Disposer::operator()(pointer) is called for the removed elements.
1217 //!
1218 //! <b>Throws</b>: Nothing.
1219 //!
1220 //! <b>Complexity</b>: Linear to the number of elements inserted plus
1221 //! linear to the elements contained in the list.
1222 //!
1223 //! <b>Note</b>: Invalidates the iterators (but not the references)
1224 //! to the erased elements.
1225 template<class Iterator, class Disposer>
1226 void dispose_and_assign(Disposer disposer, Iterator b, Iterator e)
1227 {
1228 this->clear_and_dispose(disposer);
1229 this->insert_after(this->cbefore_begin(), b, e, disposer);
1230 }
1231
1232 //! <b>Requires</b>: prev must point to an element contained by this list or
1233 //! to the before_begin() element
1234 //!
1235 //! <b>Effects</b>: Transfers all the elements of list x to this list, after the
1236 //! the element pointed by prev. No destructors or copy constructors are called.
1237 //!
1238 //! <b>Returns</b>: Nothing.
1239 //!
1240 //! <b>Throws</b>: Nothing.
1241 //!
1242 //! <b>Complexity</b>: In general, linear to the elements contained in x.
1243 //! Constant-time if cache_last<> option is true and also constant-time if
1244 //! linear<> option is true "this" is empty and "l" is not used.
1245 //!
1246 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this
1247 //! list. Iterators of this list and all the references are not invalidated.
1248 //!
1249 //! <b>Additional note</b>: If the optional parameter "l" is provided, it will be
1250 //! assigned to the last spliced element or prev if x is empty.
1251 //! This iterator can be used as new "prev" iterator for a new splice_after call.
1252 //! that will splice new values after the previously spliced values.
1253 void splice_after(const_iterator prev, slist_impl &x, const_iterator *l = 0)
1254 {
1255 if(x.empty()){
1256 if(l) *l = prev;
1257 }
1258 else if(linear && this->empty()){
1259 this->swap(x);
1260 if(l) *l = this->previous(this->cend());
1261 }
1262 else{
1263 const_iterator last_x(x.previous(x.end())); //constant time if cache_last is active
1264 node_ptr prev_n(prev.pointed_node());
1265 node_ptr last_x_n(last_x.pointed_node());
1266 if(cache_last){
1267 x.set_last_node(x.get_root_node());
1268 if(node_traits::get_next(prev_n) == this->get_end_node()){
1269 this->set_last_node(last_x_n);
1270 }
1271 }
1272 node_algorithms::transfer_after( prev_n, x.before_begin().pointed_node(), last_x_n);
1273 this->priv_size_traits().increase(x.priv_size_traits().get_size());
1274 x.priv_size_traits().set_size(size_type(0));
1275 if(l) *l = last_x;
1276 }
1277 }
1278
1279 //! <b>Requires</b>: prev must point to an element contained by this list or
1280 //! to the before_begin() element. prev_ele must point to an element contained in list
1281 //! x or must be x.before_begin().
1282 //!
1283 //! <b>Effects</b>: Transfers the element after prev_ele, from list x to this list,
1284 //! after the element pointed by prev. No destructors or copy constructors are called.
1285 //!
1286 //! <b>Throws</b>: Nothing.
1287 //!
1288 //! <b>Complexity</b>: Constant.
1289 //!
1290 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this
1291 //! list. Iterators of this list and all the references are not invalidated.
1292 void splice_after(const_iterator prev_pos, slist_impl &x, const_iterator prev_ele)
1293 {
1294 const_iterator elem = prev_ele;
1295 this->splice_after(prev_pos, x, prev_ele, ++elem, 1);
1296 }
1297
1298 //! <b>Requires</b>: prev_pos must be a dereferenceable iterator in *this or be
1299 //! before_begin(), and before_f and before_l belong to x and
1300 //! ++before_f != x.end() && before_l != x.end().
1301 //!
1302 //! <b>Effects</b>: Transfers the range (before_f, before_l] from list x to this
1303 //! list, after the element pointed by prev_pos.
1304 //! No destructors or copy constructors are called.
1305 //!
1306 //! <b>Throws</b>: Nothing.
1307 //!
1308 //! <b>Complexity</b>: Linear to the number of elements transferred
1309 //! if constant_time_size is true. Constant-time otherwise.
1310 //!
1311 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this
1312 //! list. Iterators of this list and all the references are not invalidated.
1313 void splice_after(const_iterator prev_pos, slist_impl &x, const_iterator before_f, const_iterator before_l)
1314 {
1315 if(constant_time_size)
1316 this->splice_after(prev_pos, x, before_f, before_l, node_algorithms::distance(before_f.pointed_node(), before_l.pointed_node()));
1317 else
1318 this->priv_splice_after
1319 (prev_pos.pointed_node(), x, before_f.pointed_node(), before_l.pointed_node());
1320 }
1321
1322 //! <b>Requires</b>: prev_pos must be a dereferenceable iterator in *this or be
1323 //! before_begin(), and before_f and before_l belong to x and
1324 //! ++before_f != x.end() && before_l != x.end() and
1325 //! n == distance(before_f, before_l).
1326 //!
1327 //! <b>Effects</b>: Transfers the range (before_f, before_l] from list x to this
1328 //! list, after the element pointed by p. No destructors or copy constructors are called.
1329 //!
1330 //! <b>Throws</b>: Nothing.
1331 //!
1332 //! <b>Complexity</b>: Constant time.
1333 //!
1334 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this
1335 //! list. Iterators of this list and all the references are not invalidated.
1336 void splice_after(const_iterator prev_pos, slist_impl &x, const_iterator before_f, const_iterator before_l, size_type n)
1337 {
1338 BOOST_INTRUSIVE_INVARIANT_ASSERT(node_algorithms::distance(before_f.pointed_node(), before_l.pointed_node()) == n);
1339 this->priv_splice_after
1340 (prev_pos.pointed_node(), x, before_f.pointed_node(), before_l.pointed_node());
1341 if(constant_time_size){
1342 this->priv_size_traits().increase(n);
1343 x.priv_size_traits().decrease(n);
1344 }
1345 }
1346
1347 //! <b>Requires</b>: it is an iterator to an element in *this.
1348 //!
1349 //! <b>Effects</b>: Transfers all the elements of list x to this list, before the
1350 //! the element pointed by it. No destructors or copy constructors are called.
1351 //!
1352 //! <b>Returns</b>: Nothing.
1353 //!
1354 //! <b>Throws</b>: Nothing.
1355 //!
1356 //! <b>Complexity</b>: Linear to the elements contained in x plus linear to
1357 //! the elements before it.
1358 //! Linear to the elements before it if cache_last<> option is true.
1359 //! Constant-time if cache_last<> option is true and it == end().
1360 //!
1361 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this
1362 //! list. Iterators of this list and all the references are not invalidated.
1363 //!
1364 //! <b>Additional note</b>: If the optional parameter "l" is provided, it will be
1365 //! assigned to the last spliced element or prev if x is empty.
1366 //! This iterator can be used as new "prev" iterator for a new splice_after call.
1367 //! that will splice new values after the previously spliced values.
1368 void splice(const_iterator it, slist_impl &x, const_iterator *l = 0)
1369 { this->splice_after(this->previous(it), x, l); }
1370
1371 //! <b>Requires</b>: it p must be a valid iterator of *this.
1372 //! elem must point to an element contained in list
1373 //! x.
1374 //!
1375 //! <b>Effects</b>: Transfers the element elem, from list x to this list,
1376 //! before the element pointed by pos. No destructors or copy constructors are called.
1377 //!
1378 //! <b>Throws</b>: Nothing.
1379 //!
1380 //! <b>Complexity</b>: Linear to the elements before pos and before elem.
1381 //! Linear to the elements before elem if cache_last<> option is true and pos == end().
1382 //!
1383 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this
1384 //! list. Iterators of this list and all the references are not invalidated.
1385 void splice(const_iterator pos, slist_impl &x, const_iterator elem)
1386 { return this->splice_after(this->previous(pos), x, x.previous(elem)); }
1387
1388 //! <b>Requires</b>: pos must be a dereferenceable iterator in *this
1389 //! and f and f belong to x and f and f a valid range on x.
1390 //!
1391 //! <b>Effects</b>: Transfers the range [f, l) from list x to this
1392 //! list, before the element pointed by pos.
1393 //! No destructors or copy constructors are called.
1394 //!
1395 //! <b>Throws</b>: Nothing.
1396 //!
1397 //! <b>Complexity</b>: Linear to the sum of elements before pos, f, and l
1398 //! plus linear to the number of elements transferred if constant_time_size is true.
1399 //! Linear to the sum of elements before f, and l
1400 //! plus linear to the number of elements transferred if constant_time_size is true
1401 //! if cache_last<> is true and pos == end()
1402 //!
1403 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this
1404 //! list. Iterators of this list and all the references are not invalidated.
1405 void splice(const_iterator pos, slist_impl &x, const_iterator f, const_iterator l)
1406 { return this->splice_after(this->previous(pos), x, x.previous(f), x.previous(l)); }
1407
1408 //! <b>Requires</b>: pos must be a dereferenceable iterator in *this
1409 //! and f and l belong to x and f and l a valid range on x.
1410 //! n == distance(f, l).
1411 //!
1412 //! <b>Effects</b>: Transfers the range [f, l) from list x to this
1413 //! list, before the element pointed by pos.
1414 //! No destructors or copy constructors are called.
1415 //!
1416 //! <b>Throws</b>: Nothing.
1417 //!
1418 //! <b>Complexity</b>: Linear to the sum of elements before pos, f, and l.
1419 //! Linear to the sum of elements before f and l
1420 //! if cache_last<> is true and pos == end().
1421 //!
1422 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this
1423 //! list. Iterators of this list and all the references are not invalidated.
1424 void splice(const_iterator pos, slist_impl &x, const_iterator f, const_iterator l, size_type n)
1425 { return this->splice_after(this->previous(pos), x, x.previous(f), x.previous(l), n); }
1426
1427 //! <b>Effects</b>: This function sorts the list *this according to std::less<value_type>.
1428 //! The sort is stable, that is, the relative order of equivalent elements is preserved.
1429 //!
1430 //! <b>Throws</b>: If value_traits::node_traits::node
1431 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks)
1432 //! or the predicate throws. Basic guarantee.
1433 //!
1434 //! <b>Complexity</b>: The number of comparisons is approximately N log N, where N
1435 //! is the list's size.
1436 //!
1437 //! <b>Note</b>: Iterators and references are not invalidated
1438 template<class Predicate>
1439 void sort(Predicate p)
1440 {
1441 if (node_traits::get_next(node_traits::get_next(this->get_root_node()))
1442 != this->get_root_node()) {
1443
1444 slist_impl carry(this->priv_value_traits());
1445 detail::array_initializer<slist_impl, 64> counter(this->priv_value_traits());
1446 int fill = 0;
1447 const_iterator last_inserted;
1448 while(!this->empty()){
1449 last_inserted = this->cbegin();
1450 carry.splice_after(carry.cbefore_begin(), *this, this->cbefore_begin());
1451 int i = 0;
1452 while(i < fill && !counter[i].empty()) {
1453 carry.swap(counter[i]);
1454 carry.merge(counter[i++], p, &last_inserted);
1455 }
1456 BOOST_INTRUSIVE_INVARIANT_ASSERT(counter[i].empty());
1457 const_iterator last_element(carry.previous(last_inserted, carry.end()));
1458
1459 if(constant_time_size){
1460 counter[i].splice_after( counter[i].cbefore_begin(), carry
1461 , carry.cbefore_begin(), last_element
1462 , carry.size());
1463 }
1464 else{
1465 counter[i].splice_after( counter[i].cbefore_begin(), carry
1466 , carry.cbefore_begin(), last_element);
1467 }
1468 if(i == fill)
1469 ++fill;
1470 }
1471
1472 for (int i = 1; i < fill; ++i)
1473 counter[i].merge(counter[i-1], p, &last_inserted);
1474 --fill;
1475 const_iterator last_element(counter[fill].previous(last_inserted, counter[fill].end()));
1476 if(constant_time_size){
1477 this->splice_after( cbefore_begin(), counter[fill], counter[fill].cbefore_begin()
1478 , last_element, counter[fill].size());
1479 }
1480 else{
1481 this->splice_after( cbefore_begin(), counter[fill], counter[fill].cbefore_begin()
1482 , last_element);
1483 }
1484 }
1485 }
1486
1487 //! <b>Requires</b>: p must be a comparison function that induces a strict weak
1488 //! ordering and both *this and x must be sorted according to that ordering
1489 //! The lists x and *this must be distinct.
1490 //!
1491 //! <b>Effects</b>: This function removes all of x's elements and inserts them
1492 //! in order into *this. The merge is stable; that is, if an element from *this is
1493 //! equivalent to one from x, then the element from *this will precede the one from x.
1494 //!
1495 //! <b>Throws</b>: If value_traits::node_traits::node
1496 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks)
1497 //! or std::less<value_type> throws. Basic guarantee.
1498 //!
1499 //! <b>Complexity</b>: This function is linear time: it performs at most
1500 //! size() + x.size() - 1 comparisons.
1501 //!
1502 //! <b>Note</b>: Iterators and references are not invalidated.
1503 void sort()
1504 { this->sort(std::less<value_type>()); }
1505
1506 //! <b>Requires</b>: p must be a comparison function that induces a strict weak
1507 //! ordering and both *this and x must be sorted according to that ordering
1508 //! The lists x and *this must be distinct.
1509 //!
1510 //! <b>Effects</b>: This function removes all of x's elements and inserts them
1511 //! in order into *this. The merge is stable; that is, if an element from *this is
1512 //! equivalent to one from x, then the element from *this will precede the one from x.
1513 //!
1514 //! <b>Returns</b>: Nothing.
1515 //!
1516 //! <b>Throws</b>: If the predicate throws. Basic guarantee.
1517 //!
1518 //! <b>Complexity</b>: This function is linear time: it performs at most
1519 //! size() + x.size() - 1 comparisons.
1520 //!
1521 //! <b>Note</b>: Iterators and references are not invalidated.
1522 //!
1523 //! <b>Additional note</b>: If optional "l" argument is passed, it is assigned
1524 //! to an iterator to the last transferred value or end() is x is empty.
1525 template<class Predicate>
1526 void merge(slist_impl& x, Predicate p, const_iterator *l = 0)
1527 {
1528 const_iterator e(this->cend()), ex(x.cend()), bb(this->cbefore_begin()),
1529 bb_next;
1530 if(l) *l = e.unconst();
1531 while(!x.empty()){
1532 const_iterator ibx_next(x.cbefore_begin()), ibx(ibx_next++);
1533 while (++(bb_next = bb) != e && !p(*ibx_next, *bb_next)){
1534 bb = bb_next;
1535 }
1536 if(bb_next == e){
1537 //Now transfer the rest to the end of the container
1538 this->splice_after(bb, x, l);
1539 break;
1540 }
1541 else{
1542 size_type n(0);
1543 do{
1544 ibx = ibx_next; ++n;
1545 } while(++(ibx_next = ibx) != ex && p(*ibx_next, *bb_next));
1546 this->splice_after(bb, x, x.before_begin(), ibx, n);
1547 if(l) *l = ibx;
1548 }
1549 }
1550 }
1551
1552 //! <b>Effects</b>: This function removes all of x's elements and inserts them
1553 //! in order into *this according to std::less<value_type>. The merge is stable;
1554 //! that is, if an element from *this is equivalent to one from x, then the element
1555 //! from *this will precede the one from x.
1556 //!
1557 //! <b>Throws</b>: if std::less<value_type> throws. Basic guarantee.
1558 //!
1559 //! <b>Complexity</b>: This function is linear time: it performs at most
1560 //! size() + x.size() - 1 comparisons.
1561 //!
1562 //! <b>Note</b>: Iterators and references are not invalidated
1563 void merge(slist_impl& x)
1564 { this->merge(x, std::less<value_type>()); }
1565
1566 //! <b>Effects</b>: Reverses the order of elements in the list.
1567 //!
1568 //! <b>Throws</b>: Nothing.
1569 //!
1570 //! <b>Complexity</b>: This function is linear to the contained elements.
1571 //!
1572 //! <b>Note</b>: Iterators and references are not invalidated
1573 void reverse()
1574 {
1575 if(cache_last && !this->empty()){
1576 this->set_last_node(node_traits::get_next(this->get_root_node()));
1577 }
1578 this->priv_reverse(detail::bool_<linear>());
1579 }
1580
1581 //! <b>Effects</b>: Removes all the elements that compare equal to value.
1582 //! No destructors are called.
1583 //!
1584 //! <b>Throws</b>: If std::equal_to<value_type> throws. Basic guarantee.
1585 //!
1586 //! <b>Complexity</b>: Linear time. It performs exactly size() comparisons for equality.
1587 //!
1588 //! <b>Note</b>: The relative order of elements that are not removed is unchanged,
1589 //! and iterators to elements that are not removed remain valid. This function is
1590 //! linear time: it performs exactly size() comparisons for equality.
1591 void remove(const_reference value)
1592 { this->remove_if(detail::equal_to_value<const_reference>(value)); }
1593
1594 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
1595 //!
1596 //! <b>Effects</b>: Removes all the elements that compare equal to value.
1597 //! Disposer::operator()(pointer) is called for every removed element.
1598 //!
1599 //! <b>Throws</b>: If std::equal_to<value_type> throws. Basic guarantee.
1600 //!
1601 //! <b>Complexity</b>: Linear time. It performs exactly size() comparisons for equality.
1602 //!
1603 //! <b>Note</b>: The relative order of elements that are not removed is unchanged,
1604 //! and iterators to elements that are not removed remain valid.
1605 template<class Disposer>
1606 void remove_and_dispose(const_reference value, Disposer disposer)
1607 { this->remove_and_dispose_if(detail::equal_to_value<const_reference>(value), disposer); }
1608
1609 //! <b>Effects</b>: Removes all the elements for which a specified
1610 //! predicate is satisfied. No destructors are called.
1611 //!
1612 //! <b>Throws</b>: If pred throws. Basic guarantee.
1613 //!
1614 //! <b>Complexity</b>: Linear time. It performs exactly size() calls to the predicate.
1615 //!
1616 //! <b>Note</b>: The relative order of elements that are not removed is unchanged,
1617 //! and iterators to elements that are not removed remain valid.
1618 template<class Pred>
1619 void remove_if(Pred pred)
1620 {
1621 const node_ptr bbeg = this->get_root_node();
1622 typename node_algorithms::stable_partition_info info;
1623 node_algorithms::stable_partition
1624 (bbeg, this->get_end_node(), detail::key_nodeptr_comp<Pred, value_traits>(pred, &this->priv_value_traits()), info);
1625 //After cache last is set, slist invariants are preserved...
1626 if(cache_last){
1627 this->set_last_node(info.new_last_node);
1628 }
1629 //...so erase can be safely called
1630 this->erase_after( const_iterator(bbeg, this->priv_value_traits_ptr())
1631 , const_iterator(info.beg_2st_partition, this->priv_value_traits_ptr())
1632 , info.num_1st_partition);
1633 }
1634
1635 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
1636 //!
1637 //! <b>Effects</b>: Removes all the elements for which a specified
1638 //! predicate is satisfied.
1639 //! Disposer::operator()(pointer) is called for every removed element.
1640 //!
1641 //! <b>Throws</b>: If pred throws. Basic guarantee.
1642 //!
1643 //! <b>Complexity</b>: Linear time. It performs exactly size() comparisons for equality.
1644 //!
1645 //! <b>Note</b>: The relative order of elements that are not removed is unchanged,
1646 //! and iterators to elements that are not removed remain valid.
1647 template<class Pred, class Disposer>
1648 void remove_and_dispose_if(Pred pred, Disposer disposer)
1649 {
1650 const node_ptr bbeg = this->get_root_node();
1651 typename node_algorithms::stable_partition_info info;
1652 node_algorithms::stable_partition
1653 (bbeg, this->get_end_node(), detail::key_nodeptr_comp<Pred, value_traits>(pred, &this->priv_value_traits()), info);
1654 //After cache last is set, slist invariants are preserved...
1655 if(cache_last){
1656 this->set_last_node(info.new_last_node);
1657 }
1658 //...so erase can be safely called
1659 this->erase_after_and_dispose( const_iterator(bbeg, this->priv_value_traits_ptr())
1660 , const_iterator(info.beg_2st_partition, this->priv_value_traits_ptr())
1661 , disposer);
1662 }
1663
1664 //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent
1665 //! elements that are equal from the list. No destructors are called.
1666 //!
1667 //! <b>Throws</b>: If std::equal_to<value_type> throws. Basic guarantee.
1668 //!
1669 //! <b>Complexity</b>: Linear time (size()-1) comparisons calls to pred()).
1670 //!
1671 //! <b>Note</b>: The relative order of elements that are not removed is unchanged,
1672 //! and iterators to elements that are not removed remain valid.
1673 void unique()
1674 { this->unique_and_dispose(std::equal_to<value_type>(), detail::null_disposer()); }
1675
1676 //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent
1677 //! elements that satisfy some binary predicate from the list.
1678 //! No destructors are called.
1679 //!
1680 //! <b>Throws</b>: If the predicate throws. Basic guarantee.
1681 //!
1682 //! <b>Complexity</b>: Linear time (size()-1) comparisons equality comparisons.
1683 //!
1684 //! <b>Note</b>: The relative order of elements that are not removed is unchanged,
1685 //! and iterators to elements that are not removed remain valid.
1686 template<class BinaryPredicate>
1687 void unique(BinaryPredicate pred)
1688 { this->unique_and_dispose(pred, detail::null_disposer()); }
1689
1690 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
1691 //!
1692 //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent
1693 //! elements that satisfy some binary predicate from the list.
1694 //! Disposer::operator()(pointer) is called for every removed element.
1695 //!
1696 //! <b>Throws</b>: If std::equal_to<value_type> throws. Basic guarantee.
1697 //!
1698 //! <b>Complexity</b>: Linear time (size()-1) comparisons equality comparisons.
1699 //!
1700 //! <b>Note</b>: The relative order of elements that are not removed is unchanged,
1701 //! and iterators to elements that are not removed remain valid.
1702 template<class Disposer>
1703 void unique_and_dispose(Disposer disposer)
1704 { this->unique(std::equal_to<value_type>(), disposer); }
1705
1706 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
1707 //!
1708 //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent
1709 //! elements that satisfy some binary predicate from the list.
1710 //! Disposer::operator()(pointer) is called for every removed element.
1711 //!
1712 //! <b>Throws</b>: If the predicate throws. Basic guarantee.
1713 //!
1714 //! <b>Complexity</b>: Linear time (size()-1) comparisons equality comparisons.
1715 //!
1716 //! <b>Note</b>: The relative order of elements that are not removed is unchanged,
1717 //! and iterators to elements that are not removed remain valid.
1718 template<class BinaryPredicate, class Disposer>
1719 void unique_and_dispose(BinaryPredicate pred, Disposer disposer)
1720 {
1721 const_iterator end_n(this->cend());
1722 const_iterator bcur(this->cbegin());
1723 if(bcur != end_n){
1724 const_iterator cur(bcur);
1725 ++cur;
1726 while(cur != end_n) {
1727 if (pred(*bcur, *cur)){
1728 cur = this->erase_after_and_dispose(bcur, disposer);
1729 }
1730 else{
1731 bcur = cur;
1732 ++cur;
1733 }
1734 }
1735 if(cache_last){
1736 this->set_last_node(bcur.pointed_node());
1737 }
1738 }
1739 }
1740
1741 //! <b>Requires</b>: value must be a reference to a value inserted in a list.
1742 //!
1743 //! <b>Effects</b>: This function returns a const_iterator pointing to the element
1744 //!
1745 //! <b>Throws</b>: Nothing.
1746 //!
1747 //! <b>Complexity</b>: Constant time.
1748 //!
1749 //! <b>Note</b>: Iterators and references are not invalidated.
1750 //! This static function is available only if the <i>value traits</i>
1751 //! is stateless.
1752 static iterator s_iterator_to(reference value)
1753 {
1754 BOOST_STATIC_ASSERT((!stateful_value_traits));
1755 return iterator (value_traits::to_node_ptr(value), const_value_traits_ptr());
1756 }
1757
1758 //! <b>Requires</b>: value must be a const reference to a value inserted in a list.
1759 //!
1760 //! <b>Effects</b>: This function returns an iterator pointing to the element.
1761 //!
1762 //! <b>Throws</b>: Nothing.
1763 //!
1764 //! <b>Complexity</b>: Constant time.
1765 //!
1766 //! <b>Note</b>: Iterators and references are not invalidated.
1767 //! This static function is available only if the <i>value traits</i>
1768 //! is stateless.
1769 static const_iterator s_iterator_to(const_reference value)
1770 {
1771 BOOST_STATIC_ASSERT((!stateful_value_traits));
1772 reference r =*detail::uncast(pointer_traits<const_pointer>::pointer_to(value));
1773 return const_iterator(value_traits::to_node_ptr(r), const_value_traits_ptr());
1774 }
1775
1776 //! <b>Requires</b>: value must be a reference to a value inserted in a list.
1777 //!
1778 //! <b>Effects</b>: This function returns a const_iterator pointing to the element
1779 //!
1780 //! <b>Throws</b>: Nothing.
1781 //!
1782 //! <b>Complexity</b>: Constant time.
1783 //!
1784 //! <b>Note</b>: Iterators and references are not invalidated.
1785 iterator iterator_to(reference value)
1786 {
1787 BOOST_INTRUSIVE_INVARIANT_ASSERT(linear || !node_algorithms::inited(this->priv_value_traits().to_node_ptr(value)));
1788 return iterator (this->priv_value_traits().to_node_ptr(value), this->priv_value_traits_ptr());
1789 }
1790
1791 //! <b>Requires</b>: value must be a const reference to a value inserted in a list.
1792 //!
1793 //! <b>Effects</b>: This function returns an iterator pointing to the element.
1794 //!
1795 //! <b>Throws</b>: Nothing.
1796 //!
1797 //! <b>Complexity</b>: Constant time.
1798 //!
1799 //! <b>Note</b>: Iterators and references are not invalidated.
1800 const_iterator iterator_to(const_reference value) const
1801 {
1802 reference r =*detail::uncast(pointer_traits<const_pointer>::pointer_to(value));
1803 BOOST_INTRUSIVE_INVARIANT_ASSERT (linear || !node_algorithms::inited(this->priv_value_traits().to_node_ptr(r)));
1804 return const_iterator(this->priv_value_traits().to_node_ptr(r), this->priv_value_traits_ptr());
1805 }
1806
1807 //! <b>Returns</b>: The iterator to the element before i in the list.
1808 //! Returns the end-iterator, if either i is the begin-iterator or the
1809 //! list is empty.
1810 //!
1811 //! <b>Throws</b>: Nothing.
1812 //!
1813 //! <b>Complexity</b>: Linear to the number of elements before i.
1814 //! Constant if cache_last<> is true and i == end().
1815 iterator previous(iterator i)
1816 { return this->previous(this->cbefore_begin(), i); }
1817
1818 //! <b>Returns</b>: The const_iterator to the element before i in the list.
1819 //! Returns the end-const_iterator, if either i is the begin-const_iterator or
1820 //! the list is empty.
1821 //!
1822 //! <b>Throws</b>: Nothing.
1823 //!
1824 //! <b>Complexity</b>: Linear to the number of elements before i.
1825 //! Constant if cache_last<> is true and i == end().
1826 const_iterator previous(const_iterator i) const
1827 { return this->previous(this->cbefore_begin(), i); }
1828
1829 //! <b>Returns</b>: The iterator to the element before i in the list,
1830 //! starting the search on element after prev_from.
1831 //! Returns the end-iterator, if either i is the begin-iterator or the
1832 //! list is empty.
1833 //!
1834 //! <b>Throws</b>: Nothing.
1835 //!
1836 //! <b>Complexity</b>: Linear to the number of elements before i.
1837 //! Constant if cache_last<> is true and i == end().
1838 iterator previous(const_iterator prev_from, iterator i)
1839 { return this->previous(prev_from, const_iterator(i)).unconst(); }
1840
1841 //! <b>Returns</b>: The const_iterator to the element before i in the list,
1842 //! starting the search on element after prev_from.
1843 //! Returns the end-const_iterator, if either i is the begin-const_iterator or
1844 //! the list is empty.
1845 //!
1846 //! <b>Throws</b>: Nothing.
1847 //!
1848 //! <b>Complexity</b>: Linear to the number of elements before i.
1849 //! Constant if cache_last<> is true and i == end().
1850 const_iterator previous(const_iterator prev_from, const_iterator i) const
1851 {
1852 if(cache_last && (i.pointed_node() == this->get_end_node())){
1853 return const_iterator(detail::uncast(this->get_last_node()), this->priv_value_traits_ptr());
1854 }
1855 return const_iterator
1856 (node_algorithms::get_previous_node
1857 (prev_from.pointed_node(), i.pointed_node()), this->priv_value_traits_ptr());
1858 }
1859
1860 ///@cond
1861
1862 //! <b>Requires</b>: prev_pos must be a dereferenceable iterator in *this or be
1863 //! before_begin(), and f and before_l belong to another slist.
1864 //!
1865 //! <b>Effects</b>: Transfers the range [f, before_l] to this
1866 //! list, after the element pointed by prev_pos.
1867 //! No destructors or copy constructors are called.
1868 //!
1869 //! <b>Throws</b>: Nothing.
1870 //!
1871 //! <b>Complexity</b>: Linear to the number of elements transferred
1872 //! if constant_time_size is true. Constant-time otherwise.
1873 //!
1874 //! <b>Note</b>: Iterators of values obtained from the list that owned f and before_l now
1875 //! point to elements of this list. Iterators of this list and all the references are not invalidated.
1876 //!
1877 //! <b>Warning</b>: Experimental function, don't use it!
1878 void incorporate_after(const_iterator prev_pos, const node_ptr & f, const node_ptr & before_l)
1879 {
1880 if(constant_time_size)
1881 this->incorporate_after(prev_pos, f, before_l, node_algorithms::distance(f.pointed_node(), before_l.pointed_node())+1);
1882 else
1883 this->priv_incorporate_after(prev_pos.pointed_node(), f, before_l);
1884 }
1885
1886 //! <b>Requires</b>: prev_pos must be a dereferenceable iterator in *this or be
1887 //! before_begin(), and f and before_l belong to another slist.
1888 //! n == distance(f, before_l) + 1.
1889 //!
1890 //! <b>Effects</b>: Transfers the range [f, before_l] to this
1891 //! list, after the element pointed by prev_pos.
1892 //! No destructors or copy constructors are called.
1893 //!
1894 //! <b>Throws</b>: Nothing.
1895 //!
1896 //! <b>Complexity</b>: Constant time.
1897 //!
1898 //! <b>Note</b>: Iterators of values obtained from the list that owned f and before_l now
1899 //! point to elements of this list. Iterators of this list and all the references are not invalidated.
1900 //!
1901 //! <b>Warning</b>: Experimental function, don't use it!
1902 void incorporate_after(const_iterator prev_pos, const node_ptr & f, const node_ptr & before_l, size_type n)
1903 {
1904 if(n){
1905 BOOST_INTRUSIVE_INVARIANT_ASSERT(n > 0);
1906 BOOST_INTRUSIVE_INVARIANT_ASSERT
1907 (size_type(boost::intrusive::iterator_distance
1908 ( iterator(f, this->priv_value_traits_ptr())
1909 , iterator(before_l, this->priv_value_traits_ptr())))
1910 +1 == n);
1911 this->priv_incorporate_after(prev_pos.pointed_node(), f, before_l);
1912 if(constant_time_size){
1913 this->priv_size_traits().increase(n);
1914 }
1915 }
1916 }
1917
1918 ///@endcond
1919
1920 //! <b>Effects</b>: Asserts the integrity of the container.
1921 //!
1922 //! <b>Complexity</b>: Linear time.
1923 //!
1924 //! <b>Note</b>: The method has no effect when asserts are turned off (e.g., with NDEBUG).
1925 //! Experimental function, interface might change in future versions.
1926 void check() const
1927 {
1928 const_node_ptr header_ptr = get_root_node();
1929 // header's next is never null
1930 BOOST_INTRUSIVE_INVARIANT_ASSERT(node_traits::get_next(header_ptr));
1931 if (node_traits::get_next(header_ptr) == header_ptr)
1932 {
1933 if (constant_time_size)
1934 BOOST_INTRUSIVE_INVARIANT_ASSERT(this->priv_size_traits().get_size() == 0);
1935 return;
1936 }
1937 size_t node_count = 0;
1938 const_node_ptr p = header_ptr;
1939 while (true)
1940 {
1941 const_node_ptr next_p = node_traits::get_next(p);
1942 if (!linear)
1943 {
1944 BOOST_INTRUSIVE_INVARIANT_ASSERT(next_p);
1945 }
1946 else
1947 {
1948 BOOST_INTRUSIVE_INVARIANT_ASSERT(next_p != header_ptr);
1949 }
1950 if ((!linear && next_p == header_ptr) || (linear && !next_p))
1951 {
1952 if (cache_last)
1953 BOOST_INTRUSIVE_INVARIANT_ASSERT(get_last_node() == p);
1954 break;
1955 }
1956 p = next_p;
1957 ++node_count;
1958 }
1959 if (constant_time_size)
1960 BOOST_INTRUSIVE_INVARIANT_ASSERT(this->priv_size_traits().get_size() == node_count);
1961 }
1962
1963
1964 friend bool operator==(const slist_impl &x, const slist_impl &y)
1965 {
1966 if(constant_time_size && x.size() != y.size()){
1967 return false;
1968 }
1969 return ::boost::intrusive::algo_equal(x.cbegin(), x.cend(), y.cbegin(), y.cend());
1970 }
1971
1972 friend bool operator!=(const slist_impl &x, const slist_impl &y)
1973 { return !(x == y); }
1974
1975 friend bool operator<(const slist_impl &x, const slist_impl &y)
1976 { return ::boost::intrusive::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); }
1977
1978 friend bool operator>(const slist_impl &x, const slist_impl &y)
1979 { return y < x; }
1980
1981 friend bool operator<=(const slist_impl &x, const slist_impl &y)
1982 { return !(y < x); }
1983
1984 friend bool operator>=(const slist_impl &x, const slist_impl &y)
1985 { return !(x < y); }
1986
1987 friend void swap(slist_impl &x, slist_impl &y)
1988 { x.swap(y); }
1989
1990 private:
1991 void priv_splice_after(const node_ptr & prev_pos_n, slist_impl &x, const node_ptr & before_f_n, const node_ptr & before_l_n)
1992 {
1993 if (cache_last && (before_f_n != before_l_n)){
1994 if(prev_pos_n == this->get_last_node()){
1995 this->set_last_node(before_l_n);
1996 }
1997 if(&x != this && node_traits::get_next(before_l_n) == x.get_end_node()){
1998 x.set_last_node(before_f_n);
1999 }
2000 }
2001 node_algorithms::transfer_after(prev_pos_n, before_f_n, before_l_n);
2002 }
2003
2004 void priv_incorporate_after(const node_ptr & prev_pos_n, const node_ptr & first_n, const node_ptr & before_l_n)
2005 {
2006 if(cache_last){
2007 if(prev_pos_n == this->get_last_node()){
2008 this->set_last_node(before_l_n);
2009 }
2010 }
2011 node_algorithms::incorporate_after(prev_pos_n, first_n, before_l_n);
2012 }
2013
2014 void priv_reverse(detail::bool_<false>)
2015 { node_algorithms::reverse(this->get_root_node()); }
2016
2017 void priv_reverse(detail::bool_<true>)
2018 {
2019 node_ptr new_first = node_algorithms::reverse
2020 (node_traits::get_next(this->get_root_node()));
2021 node_traits::set_next(this->get_root_node(), new_first);
2022 }
2023
2024 void priv_shift_backwards(size_type n, detail::bool_<false>)
2025 {
2026 node_ptr l = node_algorithms::move_forward(this->get_root_node(), (std::size_t)n);
2027 if(cache_last && l){
2028 this->set_last_node(l);
2029 }
2030 }
2031
2032 void priv_shift_backwards(size_type n, detail::bool_<true>)
2033 {
2034 std::pair<node_ptr, node_ptr> ret(
2035 node_algorithms::move_first_n_forward
2036 (node_traits::get_next(this->get_root_node()), (std::size_t)n));
2037 if(ret.first){
2038 node_traits::set_next(this->get_root_node(), ret.first);
2039 if(cache_last){
2040 this->set_last_node(ret.second);
2041 }
2042 }
2043 }
2044
2045 void priv_shift_forward(size_type n, detail::bool_<false>)
2046 {
2047 node_ptr l = node_algorithms::move_backwards(this->get_root_node(), (std::size_t)n);
2048 if(cache_last && l){
2049 this->set_last_node(l);
2050 }
2051 }
2052
2053 void priv_shift_forward(size_type n, detail::bool_<true>)
2054 {
2055 std::pair<node_ptr, node_ptr> ret(
2056 node_algorithms::move_first_n_backwards
2057 (node_traits::get_next(this->get_root_node()), (std::size_t)n));
2058 if(ret.first){
2059 node_traits::set_next(this->get_root_node(), ret.first);
2060 if(cache_last){
2061 this->set_last_node(ret.second);
2062 }
2063 }
2064 }
2065
2066 static void priv_swap_cache_last(slist_impl *this_impl, slist_impl *other_impl)
2067 {
2068 bool other_was_empty = false;
2069 if(this_impl->empty()){
2070 //Check if both are empty or
2071 if(other_impl->empty())
2072 return;
2073 //If this is empty swap pointers
2074 slist_impl *tmp = this_impl;
2075 this_impl = other_impl;
2076 other_impl = tmp;
2077 other_was_empty = true;
2078 }
2079 else{
2080 other_was_empty = other_impl->empty();
2081 }
2082
2083 //Precondition: this is not empty
2084 node_ptr other_old_last(other_impl->get_last_node());
2085 node_ptr other_bfirst(other_impl->get_root_node());
2086 node_ptr this_bfirst(this_impl->get_root_node());
2087 node_ptr this_old_last(this_impl->get_last_node());
2088
2089 //Move all nodes from this to other's beginning
2090 node_algorithms::transfer_after(other_bfirst, this_bfirst, this_old_last);
2091 other_impl->set_last_node(this_old_last);
2092
2093 if(other_was_empty){
2094 this_impl->set_last_node(this_bfirst);
2095 }
2096 else{
2097 //Move trailing nodes from other to this
2098 node_algorithms::transfer_after(this_bfirst, this_old_last, other_old_last);
2099 this_impl->set_last_node(other_old_last);
2100 }
2101 }
2102
2103 //circular version
2104 static void priv_swap_lists(const node_ptr & this_node, const node_ptr & other_node, detail::bool_<false>)
2105 { node_algorithms::swap_nodes(this_node, other_node); }
2106
2107 //linear version
2108 static void priv_swap_lists(const node_ptr & this_node, const node_ptr & other_node, detail::bool_<true>)
2109 { node_algorithms::swap_trailing_nodes(this_node, other_node); }
2110
2111 static slist_impl &priv_container_from_end_iterator(const const_iterator &end_iterator)
2112 {
2113 //Obtaining the container from the end iterator is not possible with linear
2114 //singly linked lists (because "end" is represented by the null pointer)
2115 BOOST_STATIC_ASSERT(!linear);
2116 BOOST_STATIC_ASSERT((has_container_from_iterator));
2117 node_ptr p = end_iterator.pointed_node();
2118 header_holder_type* h = header_holder_type::get_holder(p);
2119 header_holder_plus_last_t* hpl = detail::parent_from_member< header_holder_plus_last_t, header_holder_type>
2120 (h, &header_holder_plus_last_t::header_holder_);
2121 root_plus_size* r = static_cast< root_plus_size* >(hpl);
2122 data_t *d = detail::parent_from_member<data_t, root_plus_size>
2123 ( r, &data_t::root_plus_size_);
2124 slist_impl *s = detail::parent_from_member<slist_impl, data_t>(d, &slist_impl::data_);
2125 return *s;
2126 }
2127};
2128
2129//! Helper metafunction to define a \c slist that yields to the same type when the
2130//! same options (either explicitly or implicitly) are used.
2131#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
2132template<class T, class ...Options>
2133#else
2134template<class T, class O1 = void, class O2 = void, class O3 = void, class O4 = void, class O5 = void, class O6 = void>
2135#endif
2136struct make_slist
2137{
2138 /// @cond
2139 typedef typename pack_options
2140 < slist_defaults,
2141 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
2142 O1, O2, O3, O4, O5, O6
2143 #else
2144 Options...
2145 #endif
2146 >::type packed_options;
2147
2148 typedef typename detail::get_value_traits
2149 <T, typename packed_options::proto_value_traits>::type value_traits;
2150 typedef slist_impl
2151 < value_traits
2152 , typename packed_options::size_type
2153 , (std::size_t(packed_options::linear)*slist_bool_flags::linear_pos)
2154 |(std::size_t(packed_options::constant_time_size)*slist_bool_flags::constant_time_size_pos)
2155 |(std::size_t(packed_options::cache_last)*slist_bool_flags::cache_last_pos)
2156 , typename packed_options::header_holder_type
2157 > implementation_defined;
2158 /// @endcond
2159 typedef implementation_defined type;
2160};
2161
2162
2163#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
2164
2165#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
2166template<class T, class O1, class O2, class O3, class O4, class O5, class O6>
2167#else
2168template<class T, class ...Options>
2169#endif
2170class slist
2171 : public make_slist<T,
2172 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
2173 O1, O2, O3, O4, O5, O6
2174 #else
2175 Options...
2176 #endif
2177 >::type
2178{
2179 typedef typename make_slist
2180 <T,
2181 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
2182 O1, O2, O3, O4, O5, O6
2183 #else
2184 Options...
2185 #endif
2186 >::type Base;
2187 //Assert if passed value traits are compatible with the type
2188 BOOST_STATIC_ASSERT((detail::is_same<typename Base::value_traits::value_type, T>::value));
2189 BOOST_MOVABLE_BUT_NOT_COPYABLE(slist)
2190
2191 public:
2192 typedef typename Base::value_traits value_traits;
2193 typedef typename Base::iterator iterator;
2194 typedef typename Base::const_iterator const_iterator;
2195 typedef typename Base::size_type size_type;
2196 typedef typename Base::node_ptr node_ptr;
2197
2198 slist()
2199 : Base()
2200 {}
2201
2202 explicit slist(const value_traits &v_traits)
2203 : Base(v_traits)
2204 {}
2205
2206 struct incorporate_t{};
2207
2208 slist( const node_ptr & f, const node_ptr & before_l
2209 , size_type n, const value_traits &v_traits = value_traits())
2210 : Base(f, before_l, n, v_traits)
2211 {}
2212
2213 template<class Iterator>
2214 slist(Iterator b, Iterator e, const value_traits &v_traits = value_traits())
2215 : Base(b, e, v_traits)
2216 {}
2217
2218 slist(BOOST_RV_REF(slist) x)
2219 : Base(BOOST_MOVE_BASE(Base, x))
2220 {}
2221
2222 slist& operator=(BOOST_RV_REF(slist) x)
2223 { return static_cast<slist &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); }
2224
2225 template <class Cloner, class Disposer>
2226 void clone_from(const slist &src, Cloner cloner, Disposer disposer)
2227 { Base::clone_from(src, cloner, disposer); }
2228
2229 template <class Cloner, class Disposer>
2230 void clone_from(BOOST_RV_REF(slist) src, Cloner cloner, Disposer disposer)
2231 { Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer); }
2232
2233 static slist &container_from_end_iterator(iterator end_iterator)
2234 { return static_cast<slist &>(Base::container_from_end_iterator(end_iterator)); }
2235
2236 static const slist &container_from_end_iterator(const_iterator end_iterator)
2237 { return static_cast<const slist &>(Base::container_from_end_iterator(end_iterator)); }
2238};
2239
2240#endif
2241
2242} //namespace intrusive
2243} //namespace boost
2244
2245#include <boost/intrusive/detail/config_end.hpp>
2246
2247#endif //BOOST_INTRUSIVE_SLIST_HPP
2248