1 /////////////////////////////////////////////////////////////////////////////
3 // (C) Copyright Olaf Krzikalla 2004-2006.
4 // (C) Copyright Ion Gaztanaga 2006-2014
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)
10 // See http://www.boost.org/libs/intrusive for documentation.
12 /////////////////////////////////////////////////////////////////////////////
14 #ifndef BOOST_INTRUSIVE_SLIST_HPP
15 #define BOOST_INTRUSIVE_SLIST_HPP
17 #include <boost/intrusive/detail/config_begin.hpp>
18 #include <boost/intrusive/intrusive_fwd.hpp>
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>
41 #include <boost/move/utility_core.hpp>
42 #include <boost/static_assert.hpp>
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
48 #if defined(BOOST_HAS_PRAGMA_ONCE)
57 template<class HeaderHolder, class NodePtr, bool>
58 struct header_holder_plus_last
60 HeaderHolder header_holder_;
64 template<class HeaderHolder, class NodePtr>
65 struct header_holder_plus_last<HeaderHolder, NodePtr, false>
67 HeaderHolder header_holder_;
70 struct default_slist_hook_applier
71 { template <class T> struct apply{ typedef typename T::default_slist_hook type; }; };
74 struct is_default_hook_tag<default_slist_hook_applier>
75 { static const bool value = true; };
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;
87 struct slist_bool_flags
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;
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.
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.
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<>.
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)
121 template<class T, class ...Options>
123 template<class ValueTraits, class SizeType, std::size_t BoolFlags, typename HeaderHolder>
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;
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;
153 typedef typename detail::if_c
155 , linear_slist_algorithms<node_traits>
156 , circular_slist_algorithms<node_traits>
157 >::type node_algorithms;
161 typedef detail::size_holder<constant_time_size, size_type> size_traits;
164 BOOST_MOVABLE_BUT_NOT_COPYABLE(slist_impl)
166 static const bool safemode_or_autounlink = is_safe_autounlink<value_traits::link_mode>::value;
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)));
175 node_ptr get_end_node()
176 { return node_ptr(linear ? node_ptr() : this->get_root_node()); }
178 const_node_ptr get_end_node() const
180 return const_node_ptr
181 (linear ? const_node_ptr() : this->get_root_node()); }
183 node_ptr get_root_node()
184 { return data_.root_plus_size_.header_holder_.get_node(); }
186 const_node_ptr get_root_node() const
187 { return data_.root_plus_size_.header_holder_.get_node(); }
189 node_ptr get_last_node()
190 { return this->get_last_node(detail::bool_<cache_last>()); }
192 const_node_ptr get_last_node() const
193 { return this->get_last_node(detail::bool_<cache_last>()); }
195 void set_last_node(const node_ptr &n)
196 { return this->set_last_node(n, detail::bool_<cache_last>()); }
198 static node_ptr get_last_node(detail::bool_<false>)
200 //This function shall not be used if cache_last is not true
201 BOOST_INTRUSIVE_INVARIANT_ASSERT(cache_last);
205 static void set_last_node(const node_ptr &, detail::bool_<false>)
207 //This function shall not be used if cache_last is not true
208 BOOST_INTRUSIVE_INVARIANT_ASSERT(cache_last);
211 node_ptr get_last_node(detail::bool_<true>)
212 { return node_ptr(data_.root_plus_size_.last_); }
214 const_node_ptr get_last_node(detail::bool_<true>) const
215 { return const_node_ptr(data_.root_plus_size_.last_); }
217 void set_last_node(const node_ptr & n, detail::bool_<true>)
218 { data_.root_plus_size_.last_ = n; }
220 void set_default_constructed_state()
222 node_algorithms::init_header(this->get_root_node());
223 this->priv_size_traits().set_size(size_type(0));
225 this->set_last_node(this->get_root_node());
229 typedef header_holder_plus_last<header_holder_type, node_ptr, cache_last> header_holder_plus_last_t;
230 struct root_plus_size
232 , public header_holder_plus_last_t
236 : public slist_impl::value_traits
238 typedef typename slist_impl::value_traits value_traits;
239 explicit data_t(const value_traits &val_traits)
240 : value_traits(val_traits)
243 root_plus_size root_plus_size_;
246 size_traits &priv_size_traits()
247 { return data_.root_plus_size_; }
249 const size_traits &priv_size_traits() const
250 { return data_.root_plus_size_; }
252 const value_traits &priv_value_traits() const
255 value_traits &priv_value_traits()
258 typedef typename boost::intrusive::value_traits_pointers
259 <ValueTraits>::const_value_traits_ptr const_value_traits_ptr;
261 const_value_traits_ptr priv_value_traits_ptr() const
262 { return pointer_traits<const_value_traits_ptr>::pointer_to(this->priv_value_traits()); }
270 //! <b>Requires</b>: f and before_l belong to another slist.
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.
276 //! <b>Throws</b>: Nothing.
278 //! <b>Complexity</b>: Linear to the number of elements transferred
279 //! if constant_time_size is true. Constant-time otherwise.
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.
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())
290 this->priv_size_traits().set_size(n);
292 this->set_last_node(before_l);
294 node_traits::set_next(this->get_root_node(), f);
295 node_traits::set_next(before_l, this->get_end_node());
298 this->set_default_constructed_state();
304 //! <b>Effects</b>: constructs an empty list.
306 //! <b>Complexity</b>: Constant
308 //! <b>Throws</b>: If value_traits::node_traits::node
309 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks).
311 : data_(value_traits())
312 { this->set_default_constructed_state(); }
314 //! <b>Effects</b>: constructs an empty list.
316 //! <b>Complexity</b>: Constant
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)
322 { this->set_default_constructed_state(); }
324 //! <b>Requires</b>: Dereferencing iterator must yield an lvalue of type value_type.
326 //! <b>Effects</b>: Constructs a list equal to [b ,e).
328 //! <b>Complexity</b>: Linear in distance(b, e). No copy constructors are called.
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())
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);
341 //! <b>Effects</b>: to-do
343 slist_impl(BOOST_RV_REF(slist_impl) x)
344 : data_(::boost::move(x.priv_value_traits()))
346 this->set_default_constructed_state();
347 //nothrow, no need to rollback to release elements on exception
351 //! <b>Effects</b>: to-do
353 slist_impl& operator=(BOOST_RV_REF(slist_impl) x)
354 { this->swap(x); return *this; }
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.
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.
367 if(is_safe_autounlink<ValueTraits::link_mode>::value){
369 node_algorithms::init(this->get_root_node());
373 //! <b>Effects</b>: Erases all the elements of the container.
375 //! <b>Throws</b>: Nothing.
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.
380 //! <b>Note</b>: Invalidates the iterators (but not the references) to the erased elements.
383 if(safemode_or_autounlink){
384 this->clear_and_dispose(detail::null_disposer());
387 this->set_default_constructed_state();
391 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
393 //! <b>Effects</b>: Erases all the elements of the container
394 //! Disposer::operator()(pointer) is called for the removed elements.
396 //! <b>Throws</b>: Nothing.
398 //! <b>Complexity</b>: Linear to the number of elements of the list.
400 //! <b>Note</b>: Invalidates the iterators to the erased elements.
401 template <class Disposer>
402 void clear_and_dispose(Disposer disposer)
404 const_iterator it(this->begin()), itend(this->end());
406 node_ptr to_erase(it.pointed_node());
408 if(safemode_or_autounlink)
409 node_algorithms::init(to_erase);
410 disposer(priv_value_traits().to_value_ptr(to_erase));
412 this->set_default_constructed_state();
415 //! <b>Requires</b>: value must be an lvalue.
417 //! <b>Effects</b>: Inserts the value in the front of the list.
418 //! No copy constructors are called.
420 //! <b>Throws</b>: Nothing.
422 //! <b>Complexity</b>: Constant.
424 //! <b>Note</b>: Does not affect the validity of iterators and references.
425 void push_front(reference value)
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));
431 this->set_last_node(to_insert);
434 node_algorithms::link_after(this->get_root_node(), to_insert);
435 this->priv_size_traits().increment();
438 //! <b>Requires</b>: value must be an lvalue.
440 //! <b>Effects</b>: Inserts the value in the back of the list.
441 //! No copy constructors are called.
443 //! <b>Throws</b>: Nothing.
445 //! <b>Complexity</b>: Constant.
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)
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);
456 this->set_last_node(n);
458 this->priv_size_traits().increment();
461 //! <b>Effects</b>: Erases the first element of the list.
462 //! No destructors are called.
464 //! <b>Throws</b>: Nothing.
466 //! <b>Complexity</b>: Constant.
468 //! <b>Note</b>: Invalidates the iterators (but not the references) to the erased element.
470 { return this->pop_front_and_dispose(detail::null_disposer()); }
472 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
474 //! <b>Effects</b>: Erases the first element of the list.
475 //! Disposer::operator()(pointer) is called for the removed element.
477 //! <b>Throws</b>: Nothing.
479 //! <b>Complexity</b>: Constant.
481 //! <b>Note</b>: Invalidates the iterators to the erased element.
482 template<class Disposer>
483 void pop_front_and_dispose(Disposer disposer)
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));
493 this->set_last_node(this->get_root_node());
498 //! <b>Effects</b>: Returns a reference to the first element of the list.
500 //! <b>Throws</b>: Nothing.
502 //! <b>Complexity</b>: Constant.
504 { return *this->priv_value_traits().to_value_ptr(node_traits::get_next(this->get_root_node())); }
506 //! <b>Effects</b>: Returns a const_reference to the first element of the list.
508 //! <b>Throws</b>: Nothing.
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()))); }
514 //! <b>Effects</b>: Returns a reference to the last element of the list.
516 //! <b>Throws</b>: Nothing.
518 //! <b>Complexity</b>: Constant.
520 //! <b>Note</b>: Does not affect the validity of iterators and references.
521 //! This function is only available is cache_last<> is true.
524 BOOST_STATIC_ASSERT((cache_last));
525 return *this->priv_value_traits().to_value_ptr(this->get_last_node());
528 //! <b>Effects</b>: Returns a const_reference to the last element of the list.
530 //! <b>Throws</b>: Nothing.
532 //! <b>Complexity</b>: Constant.
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
538 BOOST_STATIC_ASSERT((cache_last));
539 return *this->priv_value_traits().to_value_ptr(this->get_last_node());
542 //! <b>Effects</b>: Returns an iterator to the first element contained in the list.
544 //! <b>Throws</b>: Nothing.
546 //! <b>Complexity</b>: Constant.
548 { return iterator (node_traits::get_next(this->get_root_node()), this->priv_value_traits_ptr()); }
550 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the list.
552 //! <b>Throws</b>: Nothing.
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()); }
558 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the list.
560 //! <b>Throws</b>: Nothing.
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()); }
566 //! <b>Effects</b>: Returns an iterator to the end of the list.
568 //! <b>Throws</b>: Nothing.
570 //! <b>Complexity</b>: Constant.
572 { return iterator(this->get_end_node(), this->priv_value_traits_ptr()); }
574 //! <b>Effects</b>: Returns a const_iterator to the end of the list.
576 //! <b>Throws</b>: Nothing.
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()); }
582 //! <b>Effects</b>: Returns a const_iterator to the end of the list.
584 //! <b>Throws</b>: Nothing.
586 //! <b>Complexity</b>: Constant.
587 const_iterator cend() const
588 { return this->end(); }
590 //! <b>Effects</b>: Returns an iterator that points to a position
591 //! before the first element. Equivalent to "end()"
593 //! <b>Throws</b>: Nothing.
595 //! <b>Complexity</b>: Constant.
596 iterator before_begin()
597 { return iterator(this->get_root_node(), this->priv_value_traits_ptr()); }
599 //! <b>Effects</b>: Returns an iterator that points to a position
600 //! before the first element. Equivalent to "end()"
602 //! <b>Throws</b>: Nothing.
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()); }
608 //! <b>Effects</b>: Returns an iterator that points to a position
609 //! before the first element. Equivalent to "end()"
611 //! <b>Throws</b>: Nothing.
613 //! <b>Complexity</b>: Constant.
614 const_iterator cbefore_begin() const
615 { return this->before_begin(); }
617 //! <b>Effects</b>: Returns an iterator to the last element contained in the list.
619 //! <b>Throws</b>: Nothing.
621 //! <b>Complexity</b>: Constant.
623 //! <b>Note</b>: This function is present only if cached_last<> option is true.
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());
631 //! <b>Effects</b>: Returns a const_iterator to the last element contained in the list.
633 //! <b>Throws</b>: Nothing.
635 //! <b>Complexity</b>: Constant.
637 //! <b>Note</b>: This function is present only if cached_last<> option is true.
638 const_iterator last() const
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());
645 //! <b>Effects</b>: Returns a const_iterator to the last element contained in the list.
647 //! <b>Throws</b>: Nothing.
649 //! <b>Complexity</b>: Constant.
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()); }
655 //! <b>Precondition</b>: end_iterator must be a valid end iterator
658 //! <b>Effects</b>: Returns a const reference to the slist associated to the end iterator
660 //! <b>Throws</b>: Nothing.
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); }
666 //! <b>Precondition</b>: end_iterator must be a valid end const_iterator
669 //! <b>Effects</b>: Returns a const reference to the slist associated to the end iterator
671 //! <b>Throws</b>: Nothing.
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); }
677 //! <b>Effects</b>: Returns the number of the elements contained in the list.
679 //! <b>Throws</b>: Nothing.
681 //! <b>Complexity</b>: Linear to the number of elements contained in the list.
682 //! if constant_time_size is false. Constant time otherwise.
684 //! <b>Note</b>: Does not affect the validity of iterators and references.
685 size_type size() const
687 if(constant_time_size)
688 return this->priv_size_traits().get_size();
690 return node_algorithms::count(this->get_root_node()) - 1;
693 //! <b>Effects</b>: Returns true if the list contains no elements.
695 //! <b>Throws</b>: Nothing.
697 //! <b>Complexity</b>: Constant.
699 //! <b>Note</b>: Does not affect the validity of iterators and references.
701 { return node_algorithms::unique(this->get_root_node()); }
703 //! <b>Effects</b>: Swaps the elements of x and *this.
705 //! <b>Throws</b>: Nothing.
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.
710 //! <b>Note</b>: Does not affect the validity of iterators and references.
711 void swap(slist_impl& other)
714 priv_swap_cache_last(this, &other);
717 this->priv_swap_lists(this->get_root_node(), other.get_root_node(), detail::bool_<linear>());
719 this->priv_size_traits().swap(other.priv_size_traits());
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.
726 //! <b>Throws</b>: Nothing.
728 //! <b>Complexity</b>: Linear to the number of elements plus the number shifts.
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>()); }
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.
738 //! <b>Throws</b>: Nothing.
740 //! <b>Complexity</b>: Linear to the number of elements plus the number shifts.
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>()); }
746 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
747 //! Cloner should yield to nodes equivalent to the original nodes.
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.
754 //! If cloner throws, all cloned elements are unlinked and disposed
755 //! calling Disposer::operator()(pointer).
757 //! <b>Complexity</b>: Linear to erased plus inserted elements.
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)
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());
769 prev = this->insert_after(prev, *cloner(*b));
774 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
775 //! Cloner should yield to nodes equivalent to the original nodes.
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.
782 //! If cloner throws, all cloned elements are unlinked and disposed
783 //! calling Disposer::operator()(pointer).
785 //! <b>Complexity</b>: Linear to erased plus inserted elements.
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)
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());
797 prev = this->insert_after(prev, *cloner(*b));
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().
805 //! <b>Effects</b>: Inserts the value after the position pointed by prev_p.
806 //! No copy constructor is called.
808 //! <b>Returns</b>: An iterator to the inserted element.
810 //! <b>Throws</b>: Nothing.
812 //! <b>Complexity</b>: Constant.
814 //! <b>Note</b>: Does not affect the validity of iterators and references.
815 iterator insert_after(const_iterator prev_p, reference value)
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);
824 this->priv_size_traits().increment();
825 return iterator (n, this->priv_value_traits_ptr());
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.
832 //! <b>Effects</b>: Inserts the [f, l)
833 //! after the position prev_p.
835 //! <b>Throws</b>: Nothing.
837 //! <b>Complexity</b>: Linear to the number of elements inserted.
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)
843 //Insert first nodes avoiding cache and size checks
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);
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);
856 if(constant_time_size){
857 this->priv_size_traits().increase(count);
861 //! <b>Requires</b>: value must be an lvalue and p must point to an element
862 //! contained by the list or to end().
864 //! <b>Effects</b>: Inserts the value before the position pointed by p.
865 //! No copy constructor is called.
867 //! <b>Throws</b>: Nothing.
869 //! <b>Complexity</b>: Linear to the number of elements before p.
870 //! Constant-time if cache_last<> is true and p == end().
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); }
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.
880 //! <b>Effects</b>: Inserts the pointed by b and e
881 //! before the position p. No copy constructors are called.
883 //! <b>Throws</b>: Nothing.
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().
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); }
894 //! <b>Effects</b>: Erases the element after the element pointed by prev of
895 //! the list. No destructors are called.
897 //! <b>Returns</b>: the first element remaining beyond the removed elements,
898 //! or end() if no such element exists.
900 //! <b>Throws</b>: Nothing.
902 //! <b>Complexity</b>: Constant.
904 //! <b>Note</b>: Invalidates the iterators (but not the references) to the
906 iterator erase_after(const_iterator prev)
907 { return this->erase_after_and_dispose(prev, detail::null_disposer()); }
909 //! <b>Effects</b>: Erases the range (before_f, l) from
910 //! the list. No destructors are called.
912 //! <b>Returns</b>: the first element remaining beyond the removed elements,
913 //! or end() if no such element exists.
915 //! <b>Throws</b>: Nothing.
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.
920 //! <b>Note</b>: Invalidates the iterators (but not the references) to the
922 iterator erase_after(const_iterator before_f, const_iterator l)
924 if(safemode_or_autounlink || constant_time_size){
925 return this->erase_after_and_dispose(before_f, l, detail::null_disposer());
928 const node_ptr bfp = before_f.pointed_node();
929 const node_ptr lp = l.pointed_node();
931 if(lp == this->get_end_node()){
932 this->set_last_node(bfp);
935 node_algorithms::unlink_after(bfp, lp);
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.
944 //! <b>Returns</b>: the first element remaining beyond the removed elements,
945 //! or end() if no such element exists.
947 //! <b>Throws</b>: Nothing.
949 //! <b>Complexity</b>: constant-time if link_mode is normal_link.
950 //! Linear to the elements (l - before_f) otherwise.
952 //! <b>Note</b>: Invalidates the iterators (but not the references) to the
954 iterator erase_after(const_iterator before_f, const_iterator l, size_type n)
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);
961 const node_ptr bfp = before_f.pointed_node();
962 const node_ptr lp = l.pointed_node();
964 if((lp == this->get_end_node())){
965 this->set_last_node(bfp);
968 node_algorithms::unlink_after(bfp, lp);
969 if(constant_time_size){
970 this->priv_size_traits().decrease(n);
976 //! <b>Effects</b>: Erases the element pointed by i of the list.
977 //! No destructors are called.
979 //! <b>Returns</b>: the first element remaining beyond the removed element,
980 //! or end() if no such element exists.
982 //! <b>Throws</b>: Nothing.
984 //! <b>Complexity</b>: Linear to the elements before i.
986 //! <b>Note</b>: Invalidates the iterators (but not the references) to the
988 iterator erase(const_iterator i)
989 { return this->erase_after(this->previous(i)); }
991 //! <b>Requires</b>: f and l must be valid iterator to elements in *this.
993 //! <b>Effects</b>: Erases the range pointed by b and e.
994 //! No destructors are called.
996 //! <b>Returns</b>: the first element remaining beyond the removed elements,
997 //! or end() if no such element exists.
999 //! <b>Throws</b>: Nothing.
1001 //! <b>Complexity</b>: Linear to the elements before l.
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); }
1008 //! <b>Effects</b>: Erases the range [f, l) from
1009 //! the list. n must be distance(f, l).
1010 //! No destructors are called.
1012 //! <b>Returns</b>: the first element remaining beyond the removed elements,
1013 //! or end() if no such element exists.
1015 //! <b>Throws</b>: Nothing.
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.
1020 //! <b>Note</b>: Invalidates the iterators (but not the references) to the
1022 iterator erase(const_iterator f, const_iterator l, size_type n)
1023 { return this->erase_after(this->previous(f), l, n); }
1025 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
1027 //! <b>Effects</b>: Erases the element after the element pointed by prev of
1029 //! Disposer::operator()(pointer) is called for the removed element.
1031 //! <b>Returns</b>: the first element remaining beyond the removed elements,
1032 //! or end() if no such element exists.
1034 //! <b>Throws</b>: Nothing.
1036 //! <b>Complexity</b>: Constant.
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)
1042 const_iterator it(prev);
1044 node_ptr to_erase(it.pointed_node());
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);
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();
1060 static iterator s_insert_after(const_iterator const prev_p, reference value)
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());
1069 template<class Disposer>
1070 static iterator s_erase_after_and_dispose(const_iterator prev, Disposer disposer)
1072 BOOST_STATIC_ASSERT(((!cache_last)&&(!constant_time_size)&&(!stateful_value_traits)));
1073 const_iterator it(prev);
1075 node_ptr to_erase(it.pointed_node());
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();
1085 template<class Disposer>
1086 static iterator s_erase_after_and_dispose(const_iterator before_f, const_iterator l, Disposer disposer)
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);
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));
1102 static iterator s_erase_after(const_iterator prev)
1103 { return s_erase_after_and_dispose(prev, detail::null_disposer()); }
1107 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
1109 //! <b>Effects</b>: Erases the range (before_f, l) from
1111 //! Disposer::operator()(pointer) is called for the removed elements.
1113 //! <b>Returns</b>: the first element remaining beyond the removed elements,
1114 //! or end() if no such element exists.
1116 //! <b>Throws</b>: Nothing.
1118 //! <b>Complexity</b>: Lineal to the elements (l - before_f + 1).
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)
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);
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();
1135 if(cache_last && (node_traits::get_next(bfp) == this->get_end_node())){
1136 this->set_last_node(bfp);
1141 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
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.
1147 //! <b>Returns</b>: the first element remaining beyond the removed element,
1148 //! or end() if no such element exists.
1150 //! <b>Throws</b>: Nothing.
1152 //! <b>Complexity</b>: Linear to the elements before i.
1154 //! <b>Note</b>: Invalidates the iterators (but not the references) to the
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); }
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); }
1166 //! <b>Requires</b>: f and l must be valid iterator to elements in *this.
1167 //! Disposer::operator()(pointer) shouldn't throw.
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.
1173 //! <b>Returns</b>: the first element remaining beyond the removed elements,
1174 //! or end() if no such element exists.
1176 //! <b>Throws</b>: Nothing.
1178 //! <b>Complexity</b>: Linear to the number of erased elements plus linear
1179 //! to the elements before f.
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); }
1187 //! <b>Requires</b>: Dereferencing iterator must yield
1188 //! an lvalue of type value_type.
1190 //! <b>Effects</b>: Clears the list and inserts the range pointed by b and e.
1191 //! No destructors or copy constructors are called.
1193 //! <b>Throws</b>: Nothing.
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.
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)
1206 this->insert_after(this->cbefore_begin(), b, e);
1209 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
1211 //! <b>Requires</b>: Dereferencing iterator must yield
1212 //! an lvalue of type value_type.
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.
1218 //! <b>Throws</b>: Nothing.
1220 //! <b>Complexity</b>: Linear to the number of elements inserted plus
1221 //! linear to the elements contained in the list.
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)
1228 this->clear_and_dispose(disposer);
1229 this->insert_after(this->cbefore_begin(), b, e, disposer);
1232 //! <b>Requires</b>: prev must point to an element contained by this list or
1233 //! to the before_begin() element
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.
1238 //! <b>Returns</b>: Nothing.
1240 //! <b>Throws</b>: Nothing.
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.
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.
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)
1258 else if(linear && this->empty()){
1260 if(l) *l = this->previous(this->cend());
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());
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);
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));
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().
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.
1286 //! <b>Throws</b>: Nothing.
1288 //! <b>Complexity</b>: Constant.
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)
1294 const_iterator elem = prev_ele;
1295 this->splice_after(prev_pos, x, prev_ele, ++elem, 1);
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().
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.
1306 //! <b>Throws</b>: Nothing.
1308 //! <b>Complexity</b>: Linear to the number of elements transferred
1309 //! if constant_time_size is true. Constant-time otherwise.
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)
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()));
1318 this->priv_splice_after
1319 (prev_pos.pointed_node(), x, before_f.pointed_node(), before_l.pointed_node());
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).
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.
1330 //! <b>Throws</b>: Nothing.
1332 //! <b>Complexity</b>: Constant time.
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)
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);
1347 //! <b>Requires</b>: it is an iterator to an element in *this.
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.
1352 //! <b>Returns</b>: Nothing.
1354 //! <b>Throws</b>: Nothing.
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().
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.
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); }
1371 //! <b>Requires</b>: it p must be a valid iterator of *this.
1372 //! elem must point to an element contained in list
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.
1378 //! <b>Throws</b>: Nothing.
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().
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)); }
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.
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.
1395 //! <b>Throws</b>: Nothing.
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()
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)); }
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).
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.
1416 //! <b>Throws</b>: Nothing.
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().
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); }
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.
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.
1434 //! <b>Complexity</b>: The number of comparisons is approximately N log N, where N
1435 //! is the list's size.
1437 //! <b>Note</b>: Iterators and references are not invalidated
1438 template<class Predicate>
1439 void sort(Predicate p)
1441 if (node_traits::get_next(node_traits::get_next(this->get_root_node()))
1442 != this->get_root_node()) {
1444 slist_impl carry(this->priv_value_traits());
1445 detail::array_initializer<slist_impl, 64> counter(this->priv_value_traits());
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());
1452 while(i < fill && !counter[i].empty()) {
1453 carry.swap(counter[i]);
1454 carry.merge(counter[i++], p, &last_inserted);
1456 BOOST_INTRUSIVE_INVARIANT_ASSERT(counter[i].empty());
1457 const_iterator last_element(carry.previous(last_inserted, carry.end()));
1459 if(constant_time_size){
1460 counter[i].splice_after( counter[i].cbefore_begin(), carry
1461 , carry.cbefore_begin(), last_element
1465 counter[i].splice_after( counter[i].cbefore_begin(), carry
1466 , carry.cbefore_begin(), last_element);
1472 for (int i = 1; i < fill; ++i)
1473 counter[i].merge(counter[i-1], p, &last_inserted);
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());
1481 this->splice_after( cbefore_begin(), counter[fill], counter[fill].cbefore_begin()
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.
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.
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.
1499 //! <b>Complexity</b>: This function is linear time: it performs at most
1500 //! size() + x.size() - 1 comparisons.
1502 //! <b>Note</b>: Iterators and references are not invalidated.
1504 { this->sort(std::less<value_type>()); }
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.
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.
1514 //! <b>Returns</b>: Nothing.
1516 //! <b>Throws</b>: If the predicate throws. Basic guarantee.
1518 //! <b>Complexity</b>: This function is linear time: it performs at most
1519 //! size() + x.size() - 1 comparisons.
1521 //! <b>Note</b>: Iterators and references are not invalidated.
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)
1528 const_iterator e(this->cend()), ex(x.cend()), bb(this->cbefore_begin()),
1530 if(l) *l = e.unconst();
1532 const_iterator ibx_next(x.cbefore_begin()), ibx(ibx_next++);
1533 while (++(bb_next = bb) != e && !p(*ibx_next, *bb_next)){
1537 //Now transfer the rest to the end of the container
1538 this->splice_after(bb, x, l);
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);
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.
1557 //! <b>Throws</b>: if std::less<value_type> throws. Basic guarantee.
1559 //! <b>Complexity</b>: This function is linear time: it performs at most
1560 //! size() + x.size() - 1 comparisons.
1562 //! <b>Note</b>: Iterators and references are not invalidated
1563 void merge(slist_impl& x)
1564 { this->merge(x, std::less<value_type>()); }
1566 //! <b>Effects</b>: Reverses the order of elements in the list.
1568 //! <b>Throws</b>: Nothing.
1570 //! <b>Complexity</b>: This function is linear to the contained elements.
1572 //! <b>Note</b>: Iterators and references are not invalidated
1575 if(cache_last && !this->empty()){
1576 this->set_last_node(node_traits::get_next(this->get_root_node()));
1578 this->priv_reverse(detail::bool_<linear>());
1581 //! <b>Effects</b>: Removes all the elements that compare equal to value.
1582 //! No destructors are called.
1584 //! <b>Throws</b>: If std::equal_to<value_type> throws. Basic guarantee.
1586 //! <b>Complexity</b>: Linear time. It performs exactly size() comparisons for equality.
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)); }
1594 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
1596 //! <b>Effects</b>: Removes all the elements that compare equal to value.
1597 //! Disposer::operator()(pointer) is called for every removed element.
1599 //! <b>Throws</b>: If std::equal_to<value_type> throws. Basic guarantee.
1601 //! <b>Complexity</b>: Linear time. It performs exactly size() comparisons for equality.
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); }
1609 //! <b>Effects</b>: Removes all the elements for which a specified
1610 //! predicate is satisfied. No destructors are called.
1612 //! <b>Throws</b>: If pred throws. Basic guarantee.
1614 //! <b>Complexity</b>: Linear time. It performs exactly size() calls to the predicate.
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)
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...
1627 this->set_last_node(info.new_last_node);
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);
1635 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
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.
1641 //! <b>Throws</b>: If pred throws. Basic guarantee.
1643 //! <b>Complexity</b>: Linear time. It performs exactly size() comparisons for equality.
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)
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...
1656 this->set_last_node(info.new_last_node);
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())
1664 //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent
1665 //! elements that are equal from the list. No destructors are called.
1667 //! <b>Throws</b>: If std::equal_to<value_type> throws. Basic guarantee.
1669 //! <b>Complexity</b>: Linear time (size()-1) comparisons calls to pred()).
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.
1674 { this->unique_and_dispose(std::equal_to<value_type>(), detail::null_disposer()); }
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.
1680 //! <b>Throws</b>: If the predicate throws. Basic guarantee.
1682 //! <b>Complexity</b>: Linear time (size()-1) comparisons equality comparisons.
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()); }
1690 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
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.
1696 //! <b>Throws</b>: If std::equal_to<value_type> throws. Basic guarantee.
1698 //! <b>Complexity</b>: Linear time (size()-1) comparisons equality comparisons.
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); }
1706 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
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.
1712 //! <b>Throws</b>: If the predicate throws. Basic guarantee.
1714 //! <b>Complexity</b>: Linear time (size()-1) comparisons equality comparisons.
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)
1721 const_iterator end_n(this->cend());
1722 const_iterator bcur(this->cbegin());
1724 const_iterator cur(bcur);
1726 while(cur != end_n) {
1727 if (pred(*bcur, *cur)){
1728 cur = this->erase_after_and_dispose(bcur, disposer);
1736 this->set_last_node(bcur.pointed_node());
1741 //! <b>Requires</b>: value must be a reference to a value inserted in a list.
1743 //! <b>Effects</b>: This function returns a const_iterator pointing to the element
1745 //! <b>Throws</b>: Nothing.
1747 //! <b>Complexity</b>: Constant time.
1749 //! <b>Note</b>: Iterators and references are not invalidated.
1750 //! This static function is available only if the <i>value traits</i>
1752 static iterator s_iterator_to(reference value)
1754 BOOST_STATIC_ASSERT((!stateful_value_traits));
1755 return iterator (value_traits::to_node_ptr(value), const_value_traits_ptr());
1758 //! <b>Requires</b>: value must be a const reference to a value inserted in a list.
1760 //! <b>Effects</b>: This function returns an iterator pointing to the element.
1762 //! <b>Throws</b>: Nothing.
1764 //! <b>Complexity</b>: Constant time.
1766 //! <b>Note</b>: Iterators and references are not invalidated.
1767 //! This static function is available only if the <i>value traits</i>
1769 static const_iterator s_iterator_to(const_reference value)
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());
1776 //! <b>Requires</b>: value must be a reference to a value inserted in a list.
1778 //! <b>Effects</b>: This function returns a const_iterator pointing to the element
1780 //! <b>Throws</b>: Nothing.
1782 //! <b>Complexity</b>: Constant time.
1784 //! <b>Note</b>: Iterators and references are not invalidated.
1785 iterator iterator_to(reference value)
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());
1791 //! <b>Requires</b>: value must be a const reference to a value inserted in a list.
1793 //! <b>Effects</b>: This function returns an iterator pointing to the element.
1795 //! <b>Throws</b>: Nothing.
1797 //! <b>Complexity</b>: Constant time.
1799 //! <b>Note</b>: Iterators and references are not invalidated.
1800 const_iterator iterator_to(const_reference value) const
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());
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
1811 //! <b>Throws</b>: Nothing.
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); }
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.
1822 //! <b>Throws</b>: Nothing.
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); }
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
1834 //! <b>Throws</b>: Nothing.
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(); }
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.
1846 //! <b>Throws</b>: Nothing.
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
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());
1855 return const_iterator
1856 (node_algorithms::get_previous_node
1857 (prev_from.pointed_node(), i.pointed_node()), this->priv_value_traits_ptr());
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.
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.
1869 //! <b>Throws</b>: Nothing.
1871 //! <b>Complexity</b>: Linear to the number of elements transferred
1872 //! if constant_time_size is true. Constant-time otherwise.
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.
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)
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);
1883 this->priv_incorporate_after(prev_pos.pointed_node(), f, before_l);
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.
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.
1894 //! <b>Throws</b>: Nothing.
1896 //! <b>Complexity</b>: Constant time.
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.
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)
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())))
1911 this->priv_incorporate_after(prev_pos.pointed_node(), f, before_l);
1912 if(constant_time_size){
1913 this->priv_size_traits().increase(n);
1920 //! <b>Effects</b>: Asserts the integrity of the container.
1922 //! <b>Complexity</b>: Linear time.
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.
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)
1933 if (constant_time_size)
1934 BOOST_INTRUSIVE_INVARIANT_ASSERT(this->priv_size_traits().get_size() == 0);
1937 size_t node_count = 0;
1938 const_node_ptr p = header_ptr;
1941 const_node_ptr next_p = node_traits::get_next(p);
1944 BOOST_INTRUSIVE_INVARIANT_ASSERT(next_p);
1948 BOOST_INTRUSIVE_INVARIANT_ASSERT(next_p != header_ptr);
1950 if ((!linear && next_p == header_ptr) || (linear && !next_p))
1953 BOOST_INTRUSIVE_INVARIANT_ASSERT(get_last_node() == p);
1959 if (constant_time_size)
1960 BOOST_INTRUSIVE_INVARIANT_ASSERT(this->priv_size_traits().get_size() == node_count);
1964 friend bool operator==(const slist_impl &x, const slist_impl &y)
1966 if(constant_time_size && x.size() != y.size()){
1969 return ::boost::intrusive::algo_equal(x.cbegin(), x.cend(), y.cbegin(), y.cend());
1972 friend bool operator!=(const slist_impl &x, const slist_impl &y)
1973 { return !(x == y); }
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()); }
1978 friend bool operator>(const slist_impl &x, const slist_impl &y)
1981 friend bool operator<=(const slist_impl &x, const slist_impl &y)
1982 { return !(y < x); }
1984 friend bool operator>=(const slist_impl &x, const slist_impl &y)
1985 { return !(x < y); }
1987 friend void swap(slist_impl &x, slist_impl &y)
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)
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);
1997 if(&x != this && node_traits::get_next(before_l_n) == x.get_end_node()){
1998 x.set_last_node(before_f_n);
2001 node_algorithms::transfer_after(prev_pos_n, before_f_n, before_l_n);
2004 void priv_incorporate_after(const node_ptr & prev_pos_n, const node_ptr & first_n, const node_ptr & before_l_n)
2007 if(prev_pos_n == this->get_last_node()){
2008 this->set_last_node(before_l_n);
2011 node_algorithms::incorporate_after(prev_pos_n, first_n, before_l_n);
2014 void priv_reverse(detail::bool_<false>)
2015 { node_algorithms::reverse(this->get_root_node()); }
2017 void priv_reverse(detail::bool_<true>)
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);
2024 void priv_shift_backwards(size_type n, detail::bool_<false>)
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);
2032 void priv_shift_backwards(size_type n, detail::bool_<true>)
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));
2038 node_traits::set_next(this->get_root_node(), ret.first);
2040 this->set_last_node(ret.second);
2045 void priv_shift_forward(size_type n, detail::bool_<false>)
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);
2053 void priv_shift_forward(size_type n, detail::bool_<true>)
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));
2059 node_traits::set_next(this->get_root_node(), ret.first);
2061 this->set_last_node(ret.second);
2066 static void priv_swap_cache_last(slist_impl *this_impl, slist_impl *other_impl)
2068 bool other_was_empty = false;
2069 if(this_impl->empty()){
2070 //Check if both are empty or
2071 if(other_impl->empty())
2073 //If this is empty swap pointers
2074 slist_impl *tmp = this_impl;
2075 this_impl = other_impl;
2077 other_was_empty = true;
2080 other_was_empty = other_impl->empty();
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());
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);
2093 if(other_was_empty){
2094 this_impl->set_last_node(this_bfirst);
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);
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); }
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); }
2111 static slist_impl &priv_container_from_end_iterator(const const_iterator &end_iterator)
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_);
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)
2132 template<class T, class ...Options>
2134 template<class T, class O1 = void, class O2 = void, class O3 = void, class O4 = void, class O5 = void, class O6 = void>
2139 typedef typename pack_options
2141 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
2142 O1, O2, O3, O4, O5, O6
2146 >::type packed_options;
2148 typedef typename detail::get_value_traits
2149 <T, typename packed_options::proto_value_traits>::type 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;
2159 typedef implementation_defined type;
2163 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
2165 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
2166 template<class T, class O1, class O2, class O3, class O4, class O5, class O6>
2168 template<class T, class ...Options>
2171 : public make_slist<T,
2172 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
2173 O1, O2, O3, O4, O5, O6
2179 typedef typename make_slist
2181 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
2182 O1, O2, O3, O4, O5, O6
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)
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;
2202 explicit slist(const value_traits &v_traits)
2206 struct incorporate_t{};
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)
2213 template<class Iterator>
2214 slist(Iterator b, Iterator e, const value_traits &v_traits = value_traits())
2215 : Base(b, e, v_traits)
2218 slist(BOOST_RV_REF(slist) x)
2219 : Base(BOOST_MOVE_BASE(Base, x))
2222 slist& operator=(BOOST_RV_REF(slist) x)
2223 { return static_cast<slist &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); }
2225 template <class Cloner, class Disposer>
2226 void clone_from(const slist &src, Cloner cloner, Disposer disposer)
2227 { Base::clone_from(src, cloner, disposer); }
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); }
2233 static slist &container_from_end_iterator(iterator end_iterator)
2234 { return static_cast<slist &>(Base::container_from_end_iterator(end_iterator)); }
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)); }
2242 } //namespace intrusive
2245 #include <boost/intrusive/detail/config_end.hpp>
2247 #endif //BOOST_INTRUSIVE_SLIST_HPP