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
21 #include <boost/intrusive/detail/config_begin.hpp>
22 #include <boost/intrusive/intrusive_fwd.hpp>
24 #include <boost/intrusive/detail/assert.hpp>
25 #include <boost/intrusive/slist_hook.hpp>
26 #include <boost/intrusive/circular_slist_algorithms.hpp>
27 #include <boost/intrusive/linear_slist_algorithms.hpp>
28 #include <boost/intrusive/pointer_traits.hpp>
29 #include <boost/intrusive/link_mode.hpp>
30 #include <boost/intrusive/detail/get_value_traits.hpp>
31 #include <boost/intrusive/detail/is_stateful_value_traits.hpp>
32 #include <boost/intrusive/detail/default_header_holder.hpp>
33 #include <boost/intrusive/detail/uncast.hpp>
34 #include <boost/intrusive/detail/mpl.hpp>
35 #include <boost/intrusive/detail/slist_iterator.hpp>
36 #include <boost/intrusive/detail/array_initializer.hpp>
37 #include <boost/intrusive/detail/exception_disposer.hpp>
38 #include <boost/intrusive/detail/equal_to_value.hpp>
39 #include <boost/intrusive/detail/key_nodeptr_comp.hpp>
40 #include <boost/intrusive/detail/simple_disposers.hpp>
41 #include <boost/intrusive/detail/size_holder.hpp>
43 #include <boost/move/utility_core.hpp>
44 #include <boost/static_assert.hpp>
48 #include <cstddef> //std::size_t
49 #include <utility> //std::pair
56 template<class HeaderHolder, class NodePtr, bool>
57 struct header_holder_plus_last
59 HeaderHolder header_holder_;
63 template<class HeaderHolder, class NodePtr>
64 struct header_holder_plus_last<HeaderHolder, NodePtr, false>
66 HeaderHolder header_holder_;
69 struct default_slist_hook_applier
70 { template <class T> struct apply{ typedef typename T::default_slist_hook type; }; };
73 struct is_default_hook_tag<default_slist_hook_applier>
74 { static const bool value = true; };
78 typedef default_slist_hook_applier proto_value_traits;
79 static const bool constant_time_size = true;
80 static const bool linear = false;
81 typedef std::size_t size_type;
82 static const bool cache_last = false;
83 typedef void header_holder_type;
86 struct slist_bool_flags
88 static const std::size_t linear_pos = 1u;
89 static const std::size_t constant_time_size_pos = 2u;
90 static const std::size_t cache_last_pos = 4u;
96 //! The class template slist is an intrusive container, that encapsulates
97 //! a singly-linked list. You can use such a list to squeeze the last bit
98 //! of performance from your application. Unfortunately, the little gains
99 //! come with some huge drawbacks. A lot of member functions can't be
100 //! implemented as efficiently as for standard containers. To overcome
101 //! this limitation some other member functions with rather unusual semantics
102 //! have to be introduced.
104 //! The template parameter \c T is the type to be managed by the container.
105 //! The user can specify additional options and if no options are provided
106 //! default options are used.
108 //! The container supports the following options:
109 //! \c base_hook<>/member_hook<>/value_traits<>,
110 //! \c constant_time_size<>, \c size_type<>,
111 //! \c linear<> and \c cache_last<>.
113 //! The iterators of slist are forward iterators. slist provides a static
114 //! function called "previous" to compute the previous iterator of a given iterator.
115 //! This function has linear complexity. To improve the usability esp. with
116 //! the '*_after' functions, ++end() == begin() and previous(begin()) == end()
117 //! are defined. An new special function "before_begin()" is defined, which returns
118 //! an iterator that points one less the beginning of the list: ++before_begin() == begin()
119 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
120 template<class T, class ...Options>
122 template<class ValueTraits, class SizeType, std::size_t BoolFlags, typename HeaderHolder>
128 typedef ValueTraits value_traits;
129 typedef typename value_traits::pointer pointer;
130 typedef typename value_traits::const_pointer const_pointer;
131 typedef typename pointer_traits<pointer>::element_type value_type;
132 typedef typename pointer_traits<pointer>::reference reference;
133 typedef typename pointer_traits<const_pointer>::reference const_reference;
134 typedef typename pointer_traits<pointer>::difference_type difference_type;
135 typedef SizeType size_type;
136 typedef slist_iterator<value_traits, false> iterator;
137 typedef slist_iterator<value_traits, true> const_iterator;
138 typedef typename value_traits::node_traits node_traits;
139 typedef typename node_traits::node node;
140 typedef typename node_traits::node_ptr node_ptr;
141 typedef typename node_traits::const_node_ptr const_node_ptr;
142 typedef HeaderHolder header_holder_type;
144 static const bool constant_time_size = 0 != (BoolFlags & slist_bool_flags::constant_time_size_pos);
145 static const bool stateful_value_traits = detail::is_stateful_value_traits<value_traits>::value;
146 static const bool linear = 0 != (BoolFlags & slist_bool_flags::linear_pos);
147 static const bool cache_last = 0 != (BoolFlags & slist_bool_flags::cache_last_pos);
148 static const bool has_container_from_iterator =
149 detail::is_same< header_holder_type, detail::default_header_holder< node_traits > >::value;
151 typedef typename detail::if_c
153 , linear_slist_algorithms<node_traits>
154 , circular_slist_algorithms<node_traits>
155 >::type node_algorithms;
159 typedef detail::size_holder<constant_time_size, size_type> size_traits;
162 BOOST_MOVABLE_BUT_NOT_COPYABLE(slist_impl)
164 static const bool safemode_or_autounlink = is_safe_autounlink<value_traits::link_mode>::value;
166 //Constant-time size is incompatible with auto-unlink hooks!
167 BOOST_STATIC_ASSERT(!(constant_time_size && ((int)value_traits::link_mode == (int)auto_unlink)));
168 //Linear singly linked lists are incompatible with auto-unlink hooks!
169 BOOST_STATIC_ASSERT(!(linear && ((int)value_traits::link_mode == (int)auto_unlink)));
170 //A list with cached last node is incompatible with auto-unlink hooks!
171 BOOST_STATIC_ASSERT(!(cache_last && ((int)value_traits::link_mode == (int)auto_unlink)));
173 node_ptr get_end_node()
174 { return node_ptr(linear ? node_ptr() : this->get_root_node()); }
176 const_node_ptr get_end_node() const
178 return const_node_ptr
179 (linear ? const_node_ptr() : this->get_root_node()); }
181 node_ptr get_root_node()
182 { return data_.root_plus_size_.header_holder_.get_node(); }
184 const_node_ptr get_root_node() const
185 { return data_.root_plus_size_.header_holder_.get_node(); }
187 node_ptr get_last_node()
188 { return this->get_last_node(detail::bool_<cache_last>()); }
190 const_node_ptr get_last_node() const
191 { return this->get_last_node(detail::bool_<cache_last>()); }
193 void set_last_node(const node_ptr &n)
194 { return this->set_last_node(n, detail::bool_<cache_last>()); }
196 static node_ptr get_last_node(detail::bool_<false>)
198 //This function shall not be used if cache_last is not true
199 BOOST_INTRUSIVE_INVARIANT_ASSERT(cache_last);
203 static void set_last_node(const node_ptr &, detail::bool_<false>)
205 //This function shall not be used if cache_last is not true
206 BOOST_INTRUSIVE_INVARIANT_ASSERT(cache_last);
209 node_ptr get_last_node(detail::bool_<true>)
210 { return node_ptr(data_.root_plus_size_.last_); }
212 const_node_ptr get_last_node(detail::bool_<true>) const
213 { return const_node_ptr(data_.root_plus_size_.last_); }
215 void set_last_node(const node_ptr & n, detail::bool_<true>)
216 { data_.root_plus_size_.last_ = n; }
218 void set_default_constructed_state()
220 node_algorithms::init_header(this->get_root_node());
221 this->priv_size_traits().set_size(size_type(0));
223 this->set_last_node(this->get_root_node());
227 typedef header_holder_plus_last<header_holder_type, node_ptr, cache_last> header_holder_plus_last_t;
228 struct root_plus_size
230 , public header_holder_plus_last_t
234 : public slist_impl::value_traits
236 typedef typename slist_impl::value_traits value_traits;
237 explicit data_t(const value_traits &val_traits)
238 : value_traits(val_traits)
241 root_plus_size root_plus_size_;
244 size_traits &priv_size_traits()
245 { return data_.root_plus_size_; }
247 const size_traits &priv_size_traits() const
248 { return data_.root_plus_size_; }
250 const value_traits &priv_value_traits() const
253 value_traits &priv_value_traits()
256 typedef typename boost::intrusive::value_traits_pointers
257 <ValueTraits>::const_value_traits_ptr const_value_traits_ptr;
259 const_value_traits_ptr priv_value_traits_ptr() const
260 { return pointer_traits<const_value_traits_ptr>::pointer_to(this->priv_value_traits()); }
268 //! <b>Requires</b>: f and before_l belong to another slist.
270 //! <b>Effects</b>: Transfers the range [f, before_l] to this
271 //! list, after the element pointed by prev_pos.
272 //! No destructors or copy constructors are called.
274 //! <b>Throws</b>: Nothing.
276 //! <b>Complexity</b>: Linear to the number of elements transferred
277 //! if constant_time_size is true. Constant-time otherwise.
279 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this
280 //! list. Iterators of this list and all the references are not invalidated.
282 //! <b>Warning</b>: Experimental function, don't use it!
283 slist_impl( const node_ptr & f, const node_ptr & before_l
284 , size_type n, const value_traits &v_traits = value_traits())
288 this->priv_size_traits().set_size(n);
290 this->set_last_node(before_l);
292 node_traits::set_next(this->get_root_node(), f);
293 node_traits::set_next(before_l, this->get_end_node());
296 this->set_default_constructed_state();
302 //! <b>Effects</b>: constructs an empty list.
304 //! <b>Complexity</b>: Constant
306 //! <b>Throws</b>: If value_traits::node_traits::node
307 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks).
308 explicit slist_impl(const value_traits &v_traits = value_traits())
310 { this->set_default_constructed_state(); }
312 //! <b>Requires</b>: Dereferencing iterator must yield an lvalue of type value_type.
314 //! <b>Effects</b>: Constructs a list equal to [b ,e).
316 //! <b>Complexity</b>: Linear in std::distance(b, e). No copy constructors are called.
318 //! <b>Throws</b>: If value_traits::node_traits::node
319 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks).
320 template<class Iterator>
321 slist_impl(Iterator b, Iterator e, const value_traits &v_traits = value_traits())
324 this->set_default_constructed_state();
325 //nothrow, no need to rollback to release elements on exception
326 this->insert_after(this->cbefore_begin(), b, e);
329 //! <b>Effects</b>: to-do
331 slist_impl(BOOST_RV_REF(slist_impl) x)
332 : data_(::boost::move(x.priv_value_traits()))
334 this->priv_size_traits().set_size(size_type(0));
335 node_algorithms::init_header(this->get_root_node());
336 //nothrow, no need to rollback to release elements on exception
340 //! <b>Effects</b>: to-do
342 slist_impl& operator=(BOOST_RV_REF(slist_impl) x)
343 { this->swap(x); return *this; }
345 //! <b>Effects</b>: If it's a safe-mode
346 //! or auto-unlink value, the destructor does nothing
347 //! (ie. no code is generated). Otherwise it detaches all elements from this.
348 //! In this case the objects in the list are not deleted (i.e. no destructors
349 //! are called), but the hooks according to the value_traits template parameter
350 //! are set to their default value.
352 //! <b>Complexity</b>: Linear to the number of elements in the list, if
353 //! it's a safe-mode or auto-unlink value. Otherwise constant.
356 if(is_safe_autounlink<ValueTraits::link_mode>::value){
358 node_algorithms::init(this->get_root_node());
362 //! <b>Effects</b>: Erases all the elements of the container.
364 //! <b>Throws</b>: Nothing.
366 //! <b>Complexity</b>: Linear to the number of elements of the list.
367 //! if it's a safe-mode or auto-unlink value_type. Constant time otherwise.
369 //! <b>Note</b>: Invalidates the iterators (but not the references) to the erased elements.
372 if(safemode_or_autounlink){
373 this->clear_and_dispose(detail::null_disposer());
376 this->set_default_constructed_state();
380 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
382 //! <b>Effects</b>: Erases all the elements of the container
383 //! Disposer::operator()(pointer) is called for the removed elements.
385 //! <b>Throws</b>: Nothing.
387 //! <b>Complexity</b>: Linear to the number of elements of the list.
389 //! <b>Note</b>: Invalidates the iterators to the erased elements.
390 template <class Disposer>
391 void clear_and_dispose(Disposer disposer)
393 const_iterator it(this->begin()), itend(this->end());
395 node_ptr to_erase(it.pointed_node());
397 if(safemode_or_autounlink)
398 node_algorithms::init(to_erase);
399 disposer(priv_value_traits().to_value_ptr(to_erase));
401 this->set_default_constructed_state();
404 //! <b>Requires</b>: value must be an lvalue.
406 //! <b>Effects</b>: Inserts the value in the front of the list.
407 //! No copy constructors are called.
409 //! <b>Throws</b>: Nothing.
411 //! <b>Complexity</b>: Constant.
413 //! <b>Note</b>: Does not affect the validity of iterators and references.
414 void push_front(reference value)
416 node_ptr to_insert = priv_value_traits().to_node_ptr(value);
417 if(safemode_or_autounlink)
418 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::inited(to_insert));
421 this->set_last_node(to_insert);
424 node_algorithms::link_after(this->get_root_node(), to_insert);
425 this->priv_size_traits().increment();
428 //! <b>Requires</b>: value must be an lvalue.
430 //! <b>Effects</b>: Inserts the value in the back of the list.
431 //! No copy constructors are called.
433 //! <b>Throws</b>: Nothing.
435 //! <b>Complexity</b>: Constant.
437 //! <b>Note</b>: Does not affect the validity of iterators and references.
438 //! This function is only available is cache_last<> is true.
439 void push_back(reference value)
441 BOOST_STATIC_ASSERT((cache_last));
442 node_ptr n = priv_value_traits().to_node_ptr(value);
443 if(safemode_or_autounlink)
444 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::inited(n));
445 node_algorithms::link_after(this->get_last_node(), n);
447 this->set_last_node(n);
449 this->priv_size_traits().increment();
452 //! <b>Effects</b>: Erases the first element of the list.
453 //! No destructors are called.
455 //! <b>Throws</b>: Nothing.
457 //! <b>Complexity</b>: Constant.
459 //! <b>Note</b>: Invalidates the iterators (but not the references) to the erased element.
461 { return this->pop_front_and_dispose(detail::null_disposer()); }
463 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
465 //! <b>Effects</b>: Erases the first element of the list.
466 //! Disposer::operator()(pointer) is called for the removed element.
468 //! <b>Throws</b>: Nothing.
470 //! <b>Complexity</b>: Constant.
472 //! <b>Note</b>: Invalidates the iterators to the erased element.
473 template<class Disposer>
474 void pop_front_and_dispose(Disposer disposer)
476 node_ptr to_erase = node_traits::get_next(this->get_root_node());
477 node_algorithms::unlink_after(this->get_root_node());
478 this->priv_size_traits().decrement();
479 if(safemode_or_autounlink)
480 node_algorithms::init(to_erase);
481 disposer(priv_value_traits().to_value_ptr(to_erase));
484 this->set_last_node(this->get_root_node());
489 //! <b>Effects</b>: Returns a reference to the first element of the list.
491 //! <b>Throws</b>: Nothing.
493 //! <b>Complexity</b>: Constant.
495 { return *this->priv_value_traits().to_value_ptr(node_traits::get_next(this->get_root_node())); }
497 //! <b>Effects</b>: Returns a const_reference to the first element of the list.
499 //! <b>Throws</b>: Nothing.
501 //! <b>Complexity</b>: Constant.
502 const_reference front() const
503 { return *this->priv_value_traits().to_value_ptr(detail::uncast(node_traits::get_next(this->get_root_node()))); }
505 //! <b>Effects</b>: Returns a reference to the last element of the list.
507 //! <b>Throws</b>: Nothing.
509 //! <b>Complexity</b>: Constant.
511 //! <b>Note</b>: Does not affect the validity of iterators and references.
512 //! This function is only available is cache_last<> is true.
515 BOOST_STATIC_ASSERT((cache_last));
516 return *this->priv_value_traits().to_value_ptr(this->get_last_node());
519 //! <b>Effects</b>: Returns a const_reference to the last element of the list.
521 //! <b>Throws</b>: Nothing.
523 //! <b>Complexity</b>: Constant.
525 //! <b>Note</b>: Does not affect the validity of iterators and references.
526 //! This function is only available is cache_last<> is true.
527 const_reference back() const
529 BOOST_STATIC_ASSERT((cache_last));
530 return *this->priv_value_traits().to_value_ptr(this->get_last_node());
533 //! <b>Effects</b>: Returns an iterator to the first element contained in the list.
535 //! <b>Throws</b>: Nothing.
537 //! <b>Complexity</b>: Constant.
539 { return iterator (node_traits::get_next(this->get_root_node()), this->priv_value_traits_ptr()); }
541 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the list.
543 //! <b>Throws</b>: Nothing.
545 //! <b>Complexity</b>: Constant.
546 const_iterator begin() const
547 { return const_iterator (node_traits::get_next(this->get_root_node()), this->priv_value_traits_ptr()); }
549 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the list.
551 //! <b>Throws</b>: Nothing.
553 //! <b>Complexity</b>: Constant.
554 const_iterator cbegin() const
555 { return const_iterator(node_traits::get_next(this->get_root_node()), this->priv_value_traits_ptr()); }
557 //! <b>Effects</b>: Returns an iterator to the end of the list.
559 //! <b>Throws</b>: Nothing.
561 //! <b>Complexity</b>: Constant.
563 { return iterator(this->get_end_node(), this->priv_value_traits_ptr()); }
565 //! <b>Effects</b>: Returns a const_iterator to the end of the list.
567 //! <b>Throws</b>: Nothing.
569 //! <b>Complexity</b>: Constant.
570 const_iterator end() const
571 { return const_iterator(detail::uncast(this->get_end_node()), this->priv_value_traits_ptr()); }
573 //! <b>Effects</b>: Returns a const_iterator to the end of the list.
575 //! <b>Throws</b>: Nothing.
577 //! <b>Complexity</b>: Constant.
578 const_iterator cend() const
579 { return this->end(); }
581 //! <b>Effects</b>: Returns an iterator that points to a position
582 //! before the first element. Equivalent to "end()"
584 //! <b>Throws</b>: Nothing.
586 //! <b>Complexity</b>: Constant.
587 iterator before_begin()
588 { return iterator(this->get_root_node(), this->priv_value_traits_ptr()); }
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 const_iterator before_begin() const
597 { return const_iterator(detail::uncast(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 cbefore_begin() const
606 { return this->before_begin(); }
608 //! <b>Effects</b>: Returns an iterator to the last element contained in the list.
610 //! <b>Throws</b>: Nothing.
612 //! <b>Complexity</b>: Constant.
614 //! <b>Note</b>: This function is present only if cached_last<> option is true.
617 //This function shall not be used if cache_last is not true
618 BOOST_INTRUSIVE_INVARIANT_ASSERT(cache_last);
619 return iterator (this->get_last_node(), this->priv_value_traits_ptr());
622 //! <b>Effects</b>: Returns a const_iterator to the last element contained in the list.
624 //! <b>Throws</b>: Nothing.
626 //! <b>Complexity</b>: Constant.
628 //! <b>Note</b>: This function is present only if cached_last<> option is true.
629 const_iterator last() const
631 //This function shall not be used if cache_last is not true
632 BOOST_INTRUSIVE_INVARIANT_ASSERT(cache_last);
633 return const_iterator (this->get_last_node(), this->priv_value_traits_ptr());
636 //! <b>Effects</b>: Returns a const_iterator to the last element contained in the list.
638 //! <b>Throws</b>: Nothing.
640 //! <b>Complexity</b>: Constant.
642 //! <b>Note</b>: This function is present only if cached_last<> option is true.
643 const_iterator clast() const
644 { return const_iterator(this->get_last_node(), this->priv_value_traits_ptr()); }
646 //! <b>Precondition</b>: end_iterator must be a valid end iterator
649 //! <b>Effects</b>: Returns a const reference to the slist associated to the end iterator
651 //! <b>Throws</b>: Nothing.
653 //! <b>Complexity</b>: Constant.
654 static slist_impl &container_from_end_iterator(iterator end_iterator)
655 { return slist_impl::priv_container_from_end_iterator(end_iterator); }
657 //! <b>Precondition</b>: end_iterator must be a valid end const_iterator
660 //! <b>Effects</b>: Returns a const reference to the slist associated to the end iterator
662 //! <b>Throws</b>: Nothing.
664 //! <b>Complexity</b>: Constant.
665 static const slist_impl &container_from_end_iterator(const_iterator end_iterator)
666 { return slist_impl::priv_container_from_end_iterator(end_iterator); }
668 //! <b>Effects</b>: Returns the number of the elements contained in the list.
670 //! <b>Throws</b>: Nothing.
672 //! <b>Complexity</b>: Linear to the number of elements contained in the list.
673 //! if constant_time_size is false. Constant time otherwise.
675 //! <b>Note</b>: Does not affect the validity of iterators and references.
676 size_type size() const
678 if(constant_time_size)
679 return this->priv_size_traits().get_size();
681 return node_algorithms::count(this->get_root_node()) - 1;
684 //! <b>Effects</b>: Returns true if the list contains no elements.
686 //! <b>Throws</b>: Nothing.
688 //! <b>Complexity</b>: Constant.
690 //! <b>Note</b>: Does not affect the validity of iterators and references.
692 { return node_algorithms::unique(this->get_root_node()); }
694 //! <b>Effects</b>: Swaps the elements of x and *this.
696 //! <b>Throws</b>: Nothing.
698 //! <b>Complexity</b>: Linear to the number of elements of both lists.
699 //! Constant-time if linear<> and/or cache_last<> options are used.
701 //! <b>Note</b>: Does not affect the validity of iterators and references.
702 void swap(slist_impl& other)
705 priv_swap_cache_last(this, &other);
708 this->priv_swap_lists(this->get_root_node(), other.get_root_node(), detail::bool_<linear>());
710 if(constant_time_size){
711 size_type backup = this->priv_size_traits().get_size();
712 this->priv_size_traits().set_size(other.priv_size_traits().get_size());
713 other.priv_size_traits().set_size(backup);
717 //! <b>Effects</b>: Moves backwards all the elements, so that the first
718 //! element becomes the second, the second becomes the third...
719 //! the last element becomes the first one.
721 //! <b>Throws</b>: Nothing.
723 //! <b>Complexity</b>: Linear to the number of elements plus the number shifts.
725 //! <b>Note</b>: Iterators Does not affect the validity of iterators and references.
726 void shift_backwards(size_type n = 1)
727 { this->priv_shift_backwards(n, detail::bool_<linear>()); }
729 //! <b>Effects</b>: Moves forward all the elements, so that the second
730 //! element becomes the first, the third becomes the second...
731 //! the first element becomes the last one.
733 //! <b>Throws</b>: Nothing.
735 //! <b>Complexity</b>: Linear to the number of elements plus the number shifts.
737 //! <b>Note</b>: Does not affect the validity of iterators and references.
738 void shift_forward(size_type n = 1)
739 { this->priv_shift_forward(n, detail::bool_<linear>()); }
741 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
742 //! Cloner should yield to nodes equivalent to the original nodes.
744 //! <b>Effects</b>: Erases all the elements from *this
745 //! calling Disposer::operator()(pointer), clones all the
746 //! elements from src calling Cloner::operator()(const_reference )
747 //! and inserts them on *this.
749 //! If cloner throws, all cloned elements are unlinked and disposed
750 //! calling Disposer::operator()(pointer).
752 //! <b>Complexity</b>: Linear to erased plus inserted elements.
754 //! <b>Throws</b>: If cloner throws.
755 template <class Cloner, class Disposer>
756 void clone_from(const slist_impl &src, Cloner cloner, Disposer disposer)
758 this->clear_and_dispose(disposer);
759 detail::exception_disposer<slist_impl, Disposer>
760 rollback(*this, disposer);
761 const_iterator prev(this->cbefore_begin());
762 const_iterator b(src.begin()), e(src.end());
764 prev = this->insert_after(prev, *cloner(*b));
769 //! <b>Requires</b>: value must be an lvalue and prev_p must point to an element
770 //! contained by the list or to end().
772 //! <b>Effects</b>: Inserts the value after the position pointed by prev_p.
773 //! No copy constructor is called.
775 //! <b>Returns</b>: An iterator to the inserted element.
777 //! <b>Throws</b>: Nothing.
779 //! <b>Complexity</b>: Constant.
781 //! <b>Note</b>: Does not affect the validity of iterators and references.
782 iterator insert_after(const_iterator prev_p, reference value)
784 node_ptr n = priv_value_traits().to_node_ptr(value);
785 if(safemode_or_autounlink)
786 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::inited(n));
787 node_ptr prev_n(prev_p.pointed_node());
788 node_algorithms::link_after(prev_n, n);
789 if(cache_last && (this->get_last_node() == prev_n)){
790 this->set_last_node(n);
792 this->priv_size_traits().increment();
793 return iterator (n, this->priv_value_traits_ptr());
796 //! <b>Requires</b>: Dereferencing iterator must yield
797 //! an lvalue of type value_type and prev_p must point to an element
798 //! contained by the list or to the end node.
800 //! <b>Effects</b>: Inserts the [f, l)
801 //! after the position prev_p.
803 //! <b>Throws</b>: Nothing.
805 //! <b>Complexity</b>: Linear to the number of elements inserted.
807 //! <b>Note</b>: Does not affect the validity of iterators and references.
808 template<class Iterator>
809 void insert_after(const_iterator prev_p, Iterator f, Iterator l)
811 //Insert first nodes avoiding cache and size checks
813 node_ptr prev_n(prev_p.pointed_node());
814 for (; f != l; ++f, ++count){
815 const node_ptr n = priv_value_traits().to_node_ptr(*f);
816 if(safemode_or_autounlink)
817 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::inited(n));
818 node_algorithms::link_after(prev_n, n);
821 //Now fix special cases if needed
822 if(cache_last && (this->get_last_node() == prev_p.pointed_node())){
823 this->set_last_node(prev_n);
825 if(constant_time_size){
826 this->priv_size_traits().increase(count);
830 //! <b>Requires</b>: value must be an lvalue and p must point to an element
831 //! contained by the list or to end().
833 //! <b>Effects</b>: Inserts the value before the position pointed by p.
834 //! No copy constructor is called.
836 //! <b>Throws</b>: Nothing.
838 //! <b>Complexity</b>: Linear to the number of elements before p.
839 //! Constant-time if cache_last<> is true and p == end().
841 //! <b>Note</b>: Does not affect the validity of iterators and references.
842 iterator insert(const_iterator p, reference value)
843 { return this->insert_after(this->previous(p), value); }
845 //! <b>Requires</b>: Dereferencing iterator must yield
846 //! an lvalue of type value_type and p must point to an element
847 //! contained by the list or to the end node.
849 //! <b>Effects</b>: Inserts the pointed by b and e
850 //! before the position p. No copy constructors are called.
852 //! <b>Throws</b>: Nothing.
854 //! <b>Complexity</b>: Linear to the number of elements inserted plus linear
855 //! to the elements before b.
856 //! Linear to the number of elements to insert if cache_last<> option is true and p == end().
858 //! <b>Note</b>: Does not affect the validity of iterators and references.
859 template<class Iterator>
860 void insert(const_iterator p, Iterator b, Iterator e)
861 { return this->insert_after(this->previous(p), b, e); }
863 //! <b>Effects</b>: Erases the element after the element pointed by prev of
864 //! the list. No destructors are called.
866 //! <b>Returns</b>: the first element remaining beyond the removed elements,
867 //! or end() if no such element exists.
869 //! <b>Throws</b>: Nothing.
871 //! <b>Complexity</b>: Constant.
873 //! <b>Note</b>: Invalidates the iterators (but not the references) to the
875 iterator erase_after(const_iterator prev)
876 { return this->erase_after_and_dispose(prev, detail::null_disposer()); }
878 //! <b>Effects</b>: Erases the range (before_f, l) from
879 //! the list. No destructors are called.
881 //! <b>Returns</b>: the first element remaining beyond the removed elements,
882 //! or end() if no such element exists.
884 //! <b>Throws</b>: Nothing.
886 //! <b>Complexity</b>: Linear to the number of erased elements if it's a safe-mode
887 //! , auto-unlink value or constant-time size is activated. Constant time otherwise.
889 //! <b>Note</b>: Invalidates the iterators (but not the references) to the
891 iterator erase_after(const_iterator before_f, const_iterator l)
893 if(safemode_or_autounlink || constant_time_size){
894 return this->erase_after_and_dispose(before_f, l, detail::null_disposer());
897 const node_ptr bfp = before_f.pointed_node();
898 const node_ptr lp = l.pointed_node();
900 if(lp == this->get_end_node()){
901 this->set_last_node(bfp);
904 node_algorithms::unlink_after(bfp, lp);
909 //! <b>Effects</b>: Erases the range (before_f, l) from
910 //! the list. n must be std::distance(before_f, l) - 1.
911 //! No destructors are called.
913 //! <b>Returns</b>: the first element remaining beyond the removed elements,
914 //! or end() if no such element exists.
916 //! <b>Throws</b>: Nothing.
918 //! <b>Complexity</b>: constant-time if link_mode is normal_link.
919 //! Linear to the elements (l - before_f) otherwise.
921 //! <b>Note</b>: Invalidates the iterators (but not the references) to the
923 iterator erase_after(const_iterator before_f, const_iterator l, size_type n)
925 BOOST_INTRUSIVE_INVARIANT_ASSERT(node_algorithms::distance((++const_iterator(before_f)).pointed_node(), l.pointed_node()) == n);
926 if(safemode_or_autounlink){
927 return this->erase_after(before_f, l);
930 const node_ptr bfp = before_f.pointed_node();
931 const node_ptr lp = l.pointed_node();
933 if((lp == this->get_end_node())){
934 this->set_last_node(bfp);
937 node_algorithms::unlink_after(bfp, lp);
938 if(constant_time_size){
939 this->priv_size_traits().decrease(n);
945 //! <b>Effects</b>: Erases the element pointed by i of the list.
946 //! No destructors are called.
948 //! <b>Returns</b>: the first element remaining beyond the removed element,
949 //! or end() if no such element exists.
951 //! <b>Throws</b>: Nothing.
953 //! <b>Complexity</b>: Linear to the elements before i.
955 //! <b>Note</b>: Invalidates the iterators (but not the references) to the
957 iterator erase(const_iterator i)
958 { return this->erase_after(this->previous(i)); }
960 //! <b>Requires</b>: f and l must be valid iterator to elements in *this.
962 //! <b>Effects</b>: Erases the range pointed by b and e.
963 //! No destructors are called.
965 //! <b>Returns</b>: the first element remaining beyond the removed elements,
966 //! or end() if no such element exists.
968 //! <b>Throws</b>: Nothing.
970 //! <b>Complexity</b>: Linear to the elements before l.
972 //! <b>Note</b>: Invalidates the iterators (but not the references) to the
974 iterator erase(const_iterator f, const_iterator l)
975 { return this->erase_after(this->previous(f), l); }
977 //! <b>Effects</b>: Erases the range [f, l) from
978 //! the list. n must be std::distance(f, l).
979 //! No destructors are called.
981 //! <b>Returns</b>: the first element remaining beyond the removed elements,
982 //! or end() if no such element exists.
984 //! <b>Throws</b>: Nothing.
986 //! <b>Complexity</b>: linear to the elements before f if link_mode is normal_link
987 //! and constant_time_size is activated. Linear to the elements before l otherwise.
989 //! <b>Note</b>: Invalidates the iterators (but not the references) to the
991 iterator erase(const_iterator f, const_iterator l, size_type n)
992 { return this->erase_after(this->previous(f), l, n); }
994 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
996 //! <b>Effects</b>: Erases the element after the element pointed by prev of
998 //! Disposer::operator()(pointer) is called for the removed element.
1000 //! <b>Returns</b>: the first element remaining beyond the removed elements,
1001 //! or end() if no such element exists.
1003 //! <b>Throws</b>: Nothing.
1005 //! <b>Complexity</b>: Constant.
1007 //! <b>Note</b>: Invalidates the iterators to the erased element.
1008 template<class Disposer>
1009 iterator erase_after_and_dispose(const_iterator prev, Disposer disposer)
1011 const_iterator it(prev);
1013 node_ptr to_erase(it.pointed_node());
1015 node_ptr prev_n(prev.pointed_node());
1016 node_algorithms::unlink_after(prev_n);
1017 if(cache_last && (to_erase == this->get_last_node())){
1018 this->set_last_node(prev_n);
1020 if(safemode_or_autounlink)
1021 node_algorithms::init(to_erase);
1022 disposer(priv_value_traits().to_value_ptr(to_erase));
1023 this->priv_size_traits().decrement();
1024 return it.unconst();
1029 template<class Disposer>
1030 static iterator s_erase_after_and_dispose(const_iterator prev, Disposer disposer)
1032 BOOST_STATIC_ASSERT(((!cache_last)&&(!constant_time_size)&&(!stateful_value_traits)));
1033 const_iterator it(prev);
1035 node_ptr to_erase(it.pointed_node());
1037 node_ptr prev_n(prev.pointed_node());
1038 node_algorithms::unlink_after(prev_n);
1039 if(safemode_or_autounlink)
1040 node_algorithms::init(to_erase);
1041 disposer(value_traits::to_value_ptr(to_erase));
1042 return it.unconst();
1045 static iterator s_erase_after(const_iterator prev)
1046 { return s_erase_after_and_dispose(prev, detail::null_disposer()); }
1050 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
1052 //! <b>Effects</b>: Erases the range (before_f, l) from
1054 //! Disposer::operator()(pointer) is called for the removed elements.
1056 //! <b>Returns</b>: the first element remaining beyond the removed elements,
1057 //! or end() if no such element exists.
1059 //! <b>Throws</b>: Nothing.
1061 //! <b>Complexity</b>: Lineal to the elements (l - before_f + 1).
1063 //! <b>Note</b>: Invalidates the iterators to the erased element.
1064 template<class Disposer>
1065 iterator erase_after_and_dispose(const_iterator before_f, const_iterator l, Disposer disposer)
1067 node_ptr bfp(before_f.pointed_node()), lp(l.pointed_node());
1068 node_ptr fp(node_traits::get_next(bfp));
1069 node_algorithms::unlink_after(bfp, lp);
1071 node_ptr to_erase(fp);
1072 fp = node_traits::get_next(fp);
1073 if(safemode_or_autounlink)
1074 node_algorithms::init(to_erase);
1075 disposer(priv_value_traits().to_value_ptr(to_erase));
1076 this->priv_size_traits().decrement();
1078 if(cache_last && (node_traits::get_next(bfp) == this->get_end_node())){
1079 this->set_last_node(bfp);
1084 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
1086 //! <b>Effects</b>: Erases the element pointed by i of the list.
1087 //! No destructors are called.
1088 //! Disposer::operator()(pointer) is called for the removed element.
1090 //! <b>Returns</b>: the first element remaining beyond the removed element,
1091 //! or end() if no such element exists.
1093 //! <b>Throws</b>: Nothing.
1095 //! <b>Complexity</b>: Linear to the elements before i.
1097 //! <b>Note</b>: Invalidates the iterators (but not the references) to the
1099 template<class Disposer>
1100 iterator erase_and_dispose(const_iterator i, Disposer disposer)
1101 { return this->erase_after_and_dispose(this->previous(i), disposer); }
1103 #if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1104 template<class Disposer>
1105 iterator erase_and_dispose(iterator i, Disposer disposer)
1106 { return this->erase_and_dispose(const_iterator(i), disposer); }
1109 //! <b>Requires</b>: f and l must be valid iterator to elements in *this.
1110 //! Disposer::operator()(pointer) shouldn't throw.
1112 //! <b>Effects</b>: Erases the range pointed by b and e.
1113 //! No destructors are called.
1114 //! Disposer::operator()(pointer) is called for the removed elements.
1116 //! <b>Returns</b>: the first element remaining beyond the removed elements,
1117 //! or end() if no such element exists.
1119 //! <b>Throws</b>: Nothing.
1121 //! <b>Complexity</b>: Linear to the number of erased elements plus linear
1122 //! to the elements before f.
1124 //! <b>Note</b>: Invalidates the iterators (but not the references) to the
1125 //! erased elements.
1126 template<class Disposer>
1127 iterator erase_and_dispose(const_iterator f, const_iterator l, Disposer disposer)
1128 { return this->erase_after_and_dispose(this->previous(f), l, disposer); }
1130 //! <b>Requires</b>: Dereferencing iterator must yield
1131 //! an lvalue of type value_type.
1133 //! <b>Effects</b>: Clears the list and inserts the range pointed by b and e.
1134 //! No destructors or copy constructors are called.
1136 //! <b>Throws</b>: Nothing.
1138 //! <b>Complexity</b>: Linear to the number of elements inserted plus
1139 //! linear to the elements contained in the list if it's a safe-mode
1140 //! or auto-unlink value.
1141 //! Linear to the number of elements inserted in the list otherwise.
1143 //! <b>Note</b>: Invalidates the iterators (but not the references)
1144 //! to the erased elements.
1145 template<class Iterator>
1146 void assign(Iterator b, Iterator e)
1149 this->insert_after(this->cbefore_begin(), b, e);
1152 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
1154 //! <b>Requires</b>: Dereferencing iterator must yield
1155 //! an lvalue of type value_type.
1157 //! <b>Effects</b>: Clears the list and inserts the range pointed by b and e.
1158 //! No destructors or copy constructors are called.
1159 //! Disposer::operator()(pointer) is called for the removed elements.
1161 //! <b>Throws</b>: Nothing.
1163 //! <b>Complexity</b>: Linear to the number of elements inserted plus
1164 //! linear to the elements contained in the list.
1166 //! <b>Note</b>: Invalidates the iterators (but not the references)
1167 //! to the erased elements.
1168 template<class Iterator, class Disposer>
1169 void dispose_and_assign(Disposer disposer, Iterator b, Iterator e)
1171 this->clear_and_dispose(disposer);
1172 this->insert_after(this->cbefore_begin(), b, e, disposer);
1175 //! <b>Requires</b>: prev must point to an element contained by this list or
1176 //! to the before_begin() element
1178 //! <b>Effects</b>: Transfers all the elements of list x to this list, after the
1179 //! the element pointed by prev. No destructors or copy constructors are called.
1181 //! <b>Returns</b>: Nothing.
1183 //! <b>Throws</b>: Nothing.
1185 //! <b>Complexity</b>: In general, linear to the elements contained in x.
1186 //! Constant-time if cache_last<> option is true and also constant-time if
1187 //! linear<> option is true "this" is empty and "l" is not used.
1189 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this
1190 //! list. Iterators of this list and all the references are not invalidated.
1192 //! <b>Additional note</b>: If the optional parameter "l" is provided, it will be
1193 //! assigned to the last spliced element or prev if x is empty.
1194 //! This iterator can be used as new "prev" iterator for a new splice_after call.
1195 //! that will splice new values after the previously spliced values.
1196 void splice_after(const_iterator prev, slist_impl &x, const_iterator *l = 0)
1201 else if(linear && this->empty()){
1203 if(l) *l = this->previous(this->cend());
1206 const_iterator last_x(x.previous(x.end())); //<- constant time if cache_last is active
1207 node_ptr prev_n(prev.pointed_node());
1208 node_ptr last_x_n(last_x.pointed_node());
1210 x.set_last_node(x.get_root_node());
1211 if(node_traits::get_next(prev_n) == this->get_end_node()){
1212 this->set_last_node(last_x_n);
1215 node_algorithms::transfer_after( prev_n, x.before_begin().pointed_node(), last_x_n);
1216 this->priv_size_traits().increase(x.priv_size_traits().get_size());
1217 x.priv_size_traits().set_size(size_type(0));
1222 //! <b>Requires</b>: prev must point to an element contained by this list or
1223 //! to the before_begin() element. prev_ele must point to an element contained in list
1224 //! x or must be x.before_begin().
1226 //! <b>Effects</b>: Transfers the element after prev_ele, from list x to this list,
1227 //! after the element pointed by prev. No destructors or copy constructors are called.
1229 //! <b>Throws</b>: Nothing.
1231 //! <b>Complexity</b>: Constant.
1233 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this
1234 //! list. Iterators of this list and all the references are not invalidated.
1235 void splice_after(const_iterator prev_pos, slist_impl &x, const_iterator prev_ele)
1237 const_iterator elem = prev_ele;
1238 this->splice_after(prev_pos, x, prev_ele, ++elem, 1);
1241 //! <b>Requires</b>: prev_pos must be a dereferenceable iterator in *this or be
1242 //! before_begin(), and before_f and before_l belong to x and
1243 //! ++before_f != x.end() && before_l != x.end().
1245 //! <b>Effects</b>: Transfers the range (before_f, before_l] from list x to this
1246 //! list, after the element pointed by prev_pos.
1247 //! No destructors or copy constructors are called.
1249 //! <b>Throws</b>: Nothing.
1251 //! <b>Complexity</b>: Linear to the number of elements transferred
1252 //! if constant_time_size is true. Constant-time otherwise.
1254 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this
1255 //! list. Iterators of this list and all the references are not invalidated.
1256 void splice_after(const_iterator prev_pos, slist_impl &x, const_iterator before_f, const_iterator before_l)
1258 if(constant_time_size)
1259 this->splice_after(prev_pos, x, before_f, before_l, node_algorithms::distance(before_f.pointed_node(), before_l.pointed_node()));
1261 this->priv_splice_after
1262 (prev_pos.pointed_node(), x, before_f.pointed_node(), before_l.pointed_node());
1265 //! <b>Requires</b>: prev_pos must be a dereferenceable iterator in *this or be
1266 //! before_begin(), and before_f and before_l belong to x and
1267 //! ++before_f != x.end() && before_l != x.end() and
1268 //! n == std::distance(before_f, before_l).
1270 //! <b>Effects</b>: Transfers the range (before_f, before_l] from list x to this
1271 //! list, after the element pointed by p. No destructors or copy constructors are called.
1273 //! <b>Throws</b>: Nothing.
1275 //! <b>Complexity</b>: Constant time.
1277 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this
1278 //! list. Iterators of this list and all the references are not invalidated.
1279 void splice_after(const_iterator prev_pos, slist_impl &x, const_iterator before_f, const_iterator before_l, size_type n)
1281 BOOST_INTRUSIVE_INVARIANT_ASSERT(node_algorithms::distance(before_f.pointed_node(), before_l.pointed_node()) == n);
1282 this->priv_splice_after
1283 (prev_pos.pointed_node(), x, before_f.pointed_node(), before_l.pointed_node());
1284 if(constant_time_size){
1285 this->priv_size_traits().increase(n);
1286 x.priv_size_traits().decrease(n);
1290 //! <b>Requires</b>: it is an iterator to an element in *this.
1292 //! <b>Effects</b>: Transfers all the elements of list x to this list, before the
1293 //! the element pointed by it. No destructors or copy constructors are called.
1295 //! <b>Returns</b>: Nothing.
1297 //! <b>Throws</b>: Nothing.
1299 //! <b>Complexity</b>: Linear to the elements contained in x plus linear to
1300 //! the elements before it.
1301 //! Linear to the elements before it if cache_last<> option is true.
1302 //! Constant-time if cache_last<> option is true and it == end().
1304 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this
1305 //! list. Iterators of this list and all the references are not invalidated.
1307 //! <b>Additional note</b>: If the optional parameter "l" is provided, it will be
1308 //! assigned to the last spliced element or prev if x is empty.
1309 //! This iterator can be used as new "prev" iterator for a new splice_after call.
1310 //! that will splice new values after the previously spliced values.
1311 void splice(const_iterator it, slist_impl &x, const_iterator *l = 0)
1312 { this->splice_after(this->previous(it), x, l); }
1314 //! <b>Requires</b>: it p must be a valid iterator of *this.
1315 //! elem must point to an element contained in list
1318 //! <b>Effects</b>: Transfers the element elem, from list x to this list,
1319 //! before the element pointed by pos. No destructors or copy constructors are called.
1321 //! <b>Throws</b>: Nothing.
1323 //! <b>Complexity</b>: Linear to the elements before pos and before elem.
1324 //! Linear to the elements before elem if cache_last<> option is true and pos == end().
1326 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this
1327 //! list. Iterators of this list and all the references are not invalidated.
1328 void splice(const_iterator pos, slist_impl &x, const_iterator elem)
1329 { return this->splice_after(this->previous(pos), x, x.previous(elem)); }
1331 //! <b>Requires</b>: pos must be a dereferenceable iterator in *this
1332 //! and f and f belong to x and f and f a valid range on x.
1334 //! <b>Effects</b>: Transfers the range [f, l) from list x to this
1335 //! list, before the element pointed by pos.
1336 //! No destructors or copy constructors are called.
1338 //! <b>Throws</b>: Nothing.
1340 //! <b>Complexity</b>: Linear to the sum of elements before pos, f, and l
1341 //! plus linear to the number of elements transferred if constant_time_size is true.
1342 //! Linear to the sum of elements before f, and l
1343 //! plus linear to the number of elements transferred if constant_time_size is true
1344 //! if cache_last<> is true and pos == end()
1346 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this
1347 //! list. Iterators of this list and all the references are not invalidated.
1348 void splice(const_iterator pos, slist_impl &x, const_iterator f, const_iterator l)
1349 { return this->splice_after(this->previous(pos), x, x.previous(f), x.previous(l)); }
1351 //! <b>Requires</b>: pos must be a dereferenceable iterator in *this
1352 //! and f and l belong to x and f and l a valid range on x.
1353 //! n == std::distance(f, l).
1355 //! <b>Effects</b>: Transfers the range [f, l) from list x to this
1356 //! list, before the element pointed by pos.
1357 //! No destructors or copy constructors are called.
1359 //! <b>Throws</b>: Nothing.
1361 //! <b>Complexity</b>: Linear to the sum of elements before pos, f, and l.
1362 //! Linear to the sum of elements before f and l
1363 //! if cache_last<> is true and pos == end().
1365 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this
1366 //! list. Iterators of this list and all the references are not invalidated.
1367 void splice(const_iterator pos, slist_impl &x, const_iterator f, const_iterator l, size_type n)
1368 { return this->splice_after(this->previous(pos), x, x.previous(f), x.previous(l), n); }
1370 //! <b>Effects</b>: This function sorts the list *this according to std::less<value_type>.
1371 //! The sort is stable, that is, the relative order of equivalent elements is preserved.
1373 //! <b>Throws</b>: If value_traits::node_traits::node
1374 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks)
1375 //! or the predicate throws. Basic guarantee.
1377 //! <b>Complexity</b>: The number of comparisons is approximately N log N, where N
1378 //! is the list's size.
1380 //! <b>Note</b>: Iterators and references are not invalidated
1381 template<class Predicate>
1382 void sort(Predicate p)
1384 if (node_traits::get_next(node_traits::get_next(this->get_root_node()))
1385 != this->get_root_node()) {
1387 slist_impl carry(this->priv_value_traits());
1388 detail::array_initializer<slist_impl, 64> counter(this->priv_value_traits());
1390 const_iterator last_inserted;
1391 while(!this->empty()){
1392 last_inserted = this->cbegin();
1393 carry.splice_after(carry.cbefore_begin(), *this, this->cbefore_begin());
1395 while(i < fill && !counter[i].empty()) {
1396 carry.swap(counter[i]);
1397 carry.merge(counter[i++], p, &last_inserted);
1399 BOOST_INTRUSIVE_INVARIANT_ASSERT(counter[i].empty());
1400 const_iterator last_element(carry.previous(last_inserted, carry.end()));
1402 if(constant_time_size){
1403 counter[i].splice_after( counter[i].cbefore_begin(), carry
1404 , carry.cbefore_begin(), last_element
1408 counter[i].splice_after( counter[i].cbefore_begin(), carry
1409 , carry.cbefore_begin(), last_element);
1415 for (int i = 1; i < fill; ++i)
1416 counter[i].merge(counter[i-1], p, &last_inserted);
1418 const_iterator last_element(counter[fill].previous(last_inserted, counter[fill].end()));
1419 if(constant_time_size){
1420 this->splice_after( cbefore_begin(), counter[fill], counter[fill].cbefore_begin()
1421 , last_element, counter[fill].size());
1424 this->splice_after( cbefore_begin(), counter[fill], counter[fill].cbefore_begin()
1430 //! <b>Requires</b>: p must be a comparison function that induces a strict weak
1431 //! ordering and both *this and x must be sorted according to that ordering
1432 //! The lists x and *this must be distinct.
1434 //! <b>Effects</b>: This function removes all of x's elements and inserts them
1435 //! in order into *this. The merge is stable; that is, if an element from *this is
1436 //! equivalent to one from x, then the element from *this will precede the one from x.
1438 //! <b>Throws</b>: If value_traits::node_traits::node
1439 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks)
1440 //! or std::less<value_type> throws. Basic guarantee.
1442 //! <b>Complexity</b>: This function is linear time: it performs at most
1443 //! size() + x.size() - 1 comparisons.
1445 //! <b>Note</b>: Iterators and references are not invalidated.
1447 { this->sort(std::less<value_type>()); }
1449 //! <b>Requires</b>: p must be a comparison function that induces a strict weak
1450 //! ordering and both *this and x must be sorted according to that ordering
1451 //! The lists x and *this must be distinct.
1453 //! <b>Effects</b>: This function removes all of x's elements and inserts them
1454 //! in order into *this. The merge is stable; that is, if an element from *this is
1455 //! equivalent to one from x, then the element from *this will precede the one from x.
1457 //! <b>Returns</b>: Nothing.
1459 //! <b>Throws</b>: If the predicate throws. Basic guarantee.
1461 //! <b>Complexity</b>: This function is linear time: it performs at most
1462 //! size() + x.size() - 1 comparisons.
1464 //! <b>Note</b>: Iterators and references are not invalidated.
1466 //! <b>Additional note</b>: If optional "l" argument is passed, it is assigned
1467 //! to an iterator to the last transferred value or end() is x is empty.
1468 template<class Predicate>
1469 void merge(slist_impl& x, Predicate p, const_iterator *l = 0)
1471 const_iterator e(this->cend()), ex(x.cend()), bb(this->cbefore_begin()),
1473 if(l) *l = e.unconst();
1475 const_iterator ibx_next(x.cbefore_begin()), ibx(ibx_next++);
1476 while (++(bb_next = bb) != e && !p(*ibx_next, *bb_next)){
1480 //Now transfer the rest to the end of the container
1481 this->splice_after(bb, x, l);
1487 ibx = ibx_next; ++n;
1488 } while(++(ibx_next = ibx) != ex && p(*ibx_next, *bb_next));
1489 this->splice_after(bb, x, x.before_begin(), ibx, n);
1495 //! <b>Effects</b>: This function removes all of x's elements and inserts them
1496 //! in order into *this according to std::less<value_type>. The merge is stable;
1497 //! that is, if an element from *this is equivalent to one from x, then the element
1498 //! from *this will precede the one from x.
1500 //! <b>Throws</b>: if std::less<value_type> throws. Basic guarantee.
1502 //! <b>Complexity</b>: This function is linear time: it performs at most
1503 //! size() + x.size() - 1 comparisons.
1505 //! <b>Note</b>: Iterators and references are not invalidated
1506 void merge(slist_impl& x)
1507 { this->merge(x, std::less<value_type>()); }
1509 //! <b>Effects</b>: Reverses the order of elements in the list.
1511 //! <b>Throws</b>: Nothing.
1513 //! <b>Complexity</b>: This function is linear to the contained elements.
1515 //! <b>Note</b>: Iterators and references are not invalidated
1518 if(cache_last && !this->empty()){
1519 this->set_last_node(node_traits::get_next(this->get_root_node()));
1521 this->priv_reverse(detail::bool_<linear>());
1524 //! <b>Effects</b>: Removes all the elements that compare equal to value.
1525 //! No destructors are called.
1527 //! <b>Throws</b>: If std::equal_to<value_type> throws. Basic guarantee.
1529 //! <b>Complexity</b>: Linear time. It performs exactly size() comparisons for equality.
1531 //! <b>Note</b>: The relative order of elements that are not removed is unchanged,
1532 //! and iterators to elements that are not removed remain valid. This function is
1533 //! linear time: it performs exactly size() comparisons for equality.
1534 void remove(const_reference value)
1535 { this->remove_if(detail::equal_to_value<const_reference>(value)); }
1537 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
1539 //! <b>Effects</b>: Removes all the elements that compare equal to value.
1540 //! Disposer::operator()(pointer) is called for every removed element.
1542 //! <b>Throws</b>: If std::equal_to<value_type> throws. Basic guarantee.
1544 //! <b>Complexity</b>: Linear time. It performs exactly size() comparisons for equality.
1546 //! <b>Note</b>: The relative order of elements that are not removed is unchanged,
1547 //! and iterators to elements that are not removed remain valid.
1548 template<class Disposer>
1549 void remove_and_dispose(const_reference value, Disposer disposer)
1550 { this->remove_and_dispose_if(detail::equal_to_value<const_reference>(value), disposer); }
1552 //! <b>Effects</b>: Removes all the elements for which a specified
1553 //! predicate is satisfied. No destructors are called.
1555 //! <b>Throws</b>: If pred throws. Basic guarantee.
1557 //! <b>Complexity</b>: Linear time. It performs exactly size() calls to the predicate.
1559 //! <b>Note</b>: The relative order of elements that are not removed is unchanged,
1560 //! and iterators to elements that are not removed remain valid.
1561 template<class Pred>
1562 void remove_if(Pred pred)
1564 const node_ptr bbeg = this->get_root_node();
1565 typename node_algorithms::stable_partition_info info;
1566 node_algorithms::stable_partition
1567 (bbeg, this->get_end_node(), detail::key_nodeptr_comp<Pred, value_traits>(pred, &this->priv_value_traits()), info);
1568 //After cache last is set, slist invariants are preserved...
1570 this->set_last_node(info.new_last_node);
1572 //...so erase can be safely called
1573 this->erase_after( const_iterator(bbeg, this->priv_value_traits_ptr())
1574 , const_iterator(info.beg_2st_partition, this->priv_value_traits_ptr())
1575 , info.num_1st_partition);
1578 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
1580 //! <b>Effects</b>: Removes all the elements for which a specified
1581 //! predicate is satisfied.
1582 //! Disposer::operator()(pointer) is called for every removed element.
1584 //! <b>Throws</b>: If pred 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.
1590 template<class Pred, class Disposer>
1591 void remove_and_dispose_if(Pred pred, Disposer disposer)
1593 const node_ptr bbeg = this->get_root_node();
1594 typename node_algorithms::stable_partition_info info;
1595 node_algorithms::stable_partition
1596 (bbeg, this->get_end_node(), detail::key_nodeptr_comp<Pred, value_traits>(pred, &this->priv_value_traits()), info);
1597 //After cache last is set, slist invariants are preserved...
1599 this->set_last_node(info.new_last_node);
1601 //...so erase can be safely called
1602 this->erase_after_and_dispose( const_iterator(bbeg, this->priv_value_traits_ptr())
1603 , const_iterator(info.beg_2st_partition, this->priv_value_traits_ptr())
1607 //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent
1608 //! elements that are equal from the list. No destructors are called.
1610 //! <b>Throws</b>: If std::equal_to<value_type> throws. Basic guarantee.
1612 //! <b>Complexity</b>: Linear time (size()-1) comparisons calls to pred()).
1614 //! <b>Note</b>: The relative order of elements that are not removed is unchanged,
1615 //! and iterators to elements that are not removed remain valid.
1617 { this->unique_and_dispose(std::equal_to<value_type>(), detail::null_disposer()); }
1619 //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent
1620 //! elements that satisfy some binary predicate from the list.
1621 //! No destructors are called.
1623 //! <b>Throws</b>: If the predicate throws. Basic guarantee.
1625 //! <b>Complexity</b>: Linear time (size()-1) comparisons equality comparisons.
1627 //! <b>Note</b>: The relative order of elements that are not removed is unchanged,
1628 //! and iterators to elements that are not removed remain valid.
1629 template<class BinaryPredicate>
1630 void unique(BinaryPredicate pred)
1631 { this->unique_and_dispose(pred, detail::null_disposer()); }
1633 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
1635 //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent
1636 //! elements that satisfy some binary predicate from the list.
1637 //! Disposer::operator()(pointer) is called for every removed element.
1639 //! <b>Throws</b>: If std::equal_to<value_type> throws. Basic guarantee.
1641 //! <b>Complexity</b>: Linear time (size()-1) comparisons equality comparisons.
1643 //! <b>Note</b>: The relative order of elements that are not removed is unchanged,
1644 //! and iterators to elements that are not removed remain valid.
1645 template<class Disposer>
1646 void unique_and_dispose(Disposer disposer)
1647 { this->unique(std::equal_to<value_type>(), disposer); }
1649 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
1651 //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent
1652 //! elements that satisfy some binary predicate from the list.
1653 //! Disposer::operator()(pointer) is called for every removed element.
1655 //! <b>Throws</b>: If the predicate throws. Basic guarantee.
1657 //! <b>Complexity</b>: Linear time (size()-1) comparisons equality comparisons.
1659 //! <b>Note</b>: The relative order of elements that are not removed is unchanged,
1660 //! and iterators to elements that are not removed remain valid.
1661 template<class BinaryPredicate, class Disposer>
1662 void unique_and_dispose(BinaryPredicate pred, Disposer disposer)
1664 const_iterator end_n(this->cend());
1665 const_iterator bcur(this->cbegin());
1667 const_iterator cur(bcur);
1669 while(cur != end_n) {
1670 if (pred(*bcur, *cur)){
1671 cur = this->erase_after_and_dispose(bcur, disposer);
1679 this->set_last_node(bcur.pointed_node());
1684 //! <b>Requires</b>: value must be a reference to a value inserted in a list.
1686 //! <b>Effects</b>: This function returns a const_iterator pointing to the element
1688 //! <b>Throws</b>: Nothing.
1690 //! <b>Complexity</b>: Constant time.
1692 //! <b>Note</b>: Iterators and references are not invalidated.
1693 //! This static function is available only if the <i>value traits</i>
1695 static iterator s_iterator_to(reference value)
1697 BOOST_STATIC_ASSERT((!stateful_value_traits));
1698 return iterator (value_traits::to_node_ptr(value), const_value_traits_ptr());
1701 //! <b>Requires</b>: value must be a const reference to a value inserted in a list.
1703 //! <b>Effects</b>: This function returns an iterator pointing to the element.
1705 //! <b>Throws</b>: Nothing.
1707 //! <b>Complexity</b>: Constant time.
1709 //! <b>Note</b>: Iterators and references are not invalidated.
1710 //! This static function is available only if the <i>value traits</i>
1712 static const_iterator s_iterator_to(const_reference value)
1714 BOOST_STATIC_ASSERT((!stateful_value_traits));
1715 reference r =*pointer_traits<pointer>::const_cast_from(pointer_traits<const_pointer>::pointer_to(value));
1716 return const_iterator(value_traits::to_node_ptr(r), const_value_traits_ptr());
1719 //! <b>Requires</b>: value must be a reference to a value inserted in a list.
1721 //! <b>Effects</b>: This function returns a const_iterator pointing to the element
1723 //! <b>Throws</b>: Nothing.
1725 //! <b>Complexity</b>: Constant time.
1727 //! <b>Note</b>: Iterators and references are not invalidated.
1728 iterator iterator_to(reference value)
1730 BOOST_INTRUSIVE_INVARIANT_ASSERT(linear || !node_algorithms::inited(this->priv_value_traits().to_node_ptr(value)));
1731 return iterator (this->priv_value_traits().to_node_ptr(value), this->priv_value_traits_ptr());
1734 //! <b>Requires</b>: value must be a const reference to a value inserted in a list.
1736 //! <b>Effects</b>: This function returns an iterator pointing to the element.
1738 //! <b>Throws</b>: Nothing.
1740 //! <b>Complexity</b>: Constant time.
1742 //! <b>Note</b>: Iterators and references are not invalidated.
1743 const_iterator iterator_to(const_reference value) const
1745 reference r =*pointer_traits<pointer>::const_cast_from(pointer_traits<const_pointer>::pointer_to(value));
1746 BOOST_INTRUSIVE_INVARIANT_ASSERT (linear || !node_algorithms::inited(this->priv_value_traits().to_node_ptr(r)));
1747 return const_iterator(this->priv_value_traits().to_node_ptr(r), this->priv_value_traits_ptr());
1750 //! <b>Returns</b>: The iterator to the element before i in the list.
1751 //! Returns the end-iterator, if either i is the begin-iterator or the
1754 //! <b>Throws</b>: Nothing.
1756 //! <b>Complexity</b>: Linear to the number of elements before i.
1757 //! Constant if cache_last<> is true and i == end().
1758 iterator previous(iterator i)
1759 { return this->previous(this->cbefore_begin(), i); }
1761 //! <b>Returns</b>: The const_iterator to the element before i in the list.
1762 //! Returns the end-const_iterator, if either i is the begin-const_iterator or
1763 //! the list is empty.
1765 //! <b>Throws</b>: Nothing.
1767 //! <b>Complexity</b>: Linear to the number of elements before i.
1768 //! Constant if cache_last<> is true and i == end().
1769 const_iterator previous(const_iterator i) const
1770 { return this->previous(this->cbefore_begin(), i); }
1772 //! <b>Returns</b>: The iterator to the element before i in the list,
1773 //! starting the search on element after prev_from.
1774 //! Returns the end-iterator, if either i is the begin-iterator or the
1777 //! <b>Throws</b>: Nothing.
1779 //! <b>Complexity</b>: Linear to the number of elements before i.
1780 //! Constant if cache_last<> is true and i == end().
1781 iterator previous(const_iterator prev_from, iterator i)
1782 { return this->previous(prev_from, const_iterator(i)).unconst(); }
1784 //! <b>Returns</b>: The const_iterator to the element before i in the list,
1785 //! starting the search on element after prev_from.
1786 //! Returns the end-const_iterator, if either i is the begin-const_iterator or
1787 //! the list is empty.
1789 //! <b>Throws</b>: Nothing.
1791 //! <b>Complexity</b>: Linear to the number of elements before i.
1792 //! Constant if cache_last<> is true and i == end().
1793 const_iterator previous(const_iterator prev_from, const_iterator i) const
1795 if(cache_last && (i.pointed_node() == this->get_end_node())){
1796 return const_iterator(detail::uncast(this->get_last_node()), this->priv_value_traits_ptr());
1798 return const_iterator
1799 (node_algorithms::get_previous_node
1800 (prev_from.pointed_node(), i.pointed_node()), this->priv_value_traits_ptr());
1805 //! <b>Requires</b>: prev_pos must be a dereferenceable iterator in *this or be
1806 //! before_begin(), and f and before_l belong to another slist.
1808 //! <b>Effects</b>: Transfers the range [f, before_l] to this
1809 //! list, after the element pointed by prev_pos.
1810 //! No destructors or copy constructors are called.
1812 //! <b>Throws</b>: Nothing.
1814 //! <b>Complexity</b>: Linear to the number of elements transferred
1815 //! if constant_time_size is true. Constant-time otherwise.
1817 //! <b>Note</b>: Iterators of values obtained from the list that owned f and before_l now
1818 //! point to elements of this list. Iterators of this list and all the references are not invalidated.
1820 //! <b>Warning</b>: Experimental function, don't use it!
1821 void incorporate_after(const_iterator prev_pos, const node_ptr & f, const node_ptr & before_l)
1823 if(constant_time_size)
1824 this->incorporate_after(prev_pos, f, before_l, node_algorithms::distance(f.pointed_node(), before_l.pointed_node())+1);
1826 this->priv_incorporate_after(prev_pos.pointed_node(), f, before_l);
1829 //! <b>Requires</b>: prev_pos must be a dereferenceable iterator in *this or be
1830 //! before_begin(), and f and before_l belong to another slist.
1831 //! n == std::distance(f, before_l) + 1.
1833 //! <b>Effects</b>: Transfers the range [f, before_l] to this
1834 //! list, after the element pointed by prev_pos.
1835 //! No destructors or copy constructors are called.
1837 //! <b>Throws</b>: Nothing.
1839 //! <b>Complexity</b>: Constant time.
1841 //! <b>Note</b>: Iterators of values obtained from the list that owned f and before_l now
1842 //! point to elements of this list. Iterators of this list and all the references are not invalidated.
1844 //! <b>Warning</b>: Experimental function, don't use it!
1845 void incorporate_after(const_iterator prev_pos, const node_ptr & f, const node_ptr & before_l, size_type n)
1848 BOOST_INTRUSIVE_INVARIANT_ASSERT(n > 0);
1849 BOOST_INTRUSIVE_INVARIANT_ASSERT
1850 (size_type(std::distance
1851 ( iterator(f, this->priv_value_traits_ptr())
1852 , iterator(before_l, this->priv_value_traits_ptr())))
1854 this->priv_incorporate_after(prev_pos.pointed_node(), f, before_l);
1855 if(constant_time_size){
1856 this->priv_size_traits().increase(n);
1863 //! <b>Effects</b>: Asserts the integrity of the container.
1865 //! <b>Complexity</b>: Linear time.
1867 //! <b>Note</b>: The method has no effect when asserts are turned off (e.g., with NDEBUG).
1868 //! Experimental function, interface might change in future versions.
1871 const_node_ptr header_ptr = get_root_node();
1872 // header's next is never null
1873 BOOST_INTRUSIVE_INVARIANT_ASSERT(node_traits::get_next(header_ptr));
1874 if (node_traits::get_next(header_ptr) == header_ptr)
1876 if (constant_time_size)
1877 BOOST_INTRUSIVE_INVARIANT_ASSERT(this->priv_size_traits().get_size() == 0);
1880 size_t node_count = 0;
1881 const_node_ptr p = header_ptr;
1884 const_node_ptr next_p = node_traits::get_next(p);
1887 BOOST_INTRUSIVE_INVARIANT_ASSERT(next_p);
1891 BOOST_INTRUSIVE_INVARIANT_ASSERT(next_p != header_ptr);
1893 if ((!linear && next_p == header_ptr) || (linear && !next_p))
1896 BOOST_INTRUSIVE_INVARIANT_ASSERT(get_last_node() == p);
1902 if (constant_time_size)
1903 BOOST_INTRUSIVE_INVARIANT_ASSERT(this->priv_size_traits().get_size() == node_count);
1907 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)
1909 if (cache_last && (before_f_n != before_l_n)){
1910 if(prev_pos_n == this->get_last_node()){
1911 this->set_last_node(before_l_n);
1913 if(&x != this && node_traits::get_next(before_l_n) == x.get_end_node()){
1914 x.set_last_node(before_f_n);
1917 node_algorithms::transfer_after(prev_pos_n, before_f_n, before_l_n);
1920 void priv_incorporate_after(const node_ptr & prev_pos_n, const node_ptr & first_n, const node_ptr & before_l_n)
1923 if(prev_pos_n == this->get_last_node()){
1924 this->set_last_node(before_l_n);
1927 node_algorithms::incorporate_after(prev_pos_n, first_n, before_l_n);
1930 void priv_reverse(detail::bool_<false>)
1931 { node_algorithms::reverse(this->get_root_node()); }
1933 void priv_reverse(detail::bool_<true>)
1935 node_ptr new_first = node_algorithms::reverse
1936 (node_traits::get_next(this->get_root_node()));
1937 node_traits::set_next(this->get_root_node(), new_first);
1940 void priv_shift_backwards(size_type n, detail::bool_<false>)
1942 node_ptr l = node_algorithms::move_forward(this->get_root_node(), (std::size_t)n);
1943 if(cache_last && l){
1944 this->set_last_node(l);
1948 void priv_shift_backwards(size_type n, detail::bool_<true>)
1950 std::pair<node_ptr, node_ptr> ret(
1951 node_algorithms::move_first_n_forward
1952 (node_traits::get_next(this->get_root_node()), (std::size_t)n));
1954 node_traits::set_next(this->get_root_node(), ret.first);
1956 this->set_last_node(ret.second);
1961 void priv_shift_forward(size_type n, detail::bool_<false>)
1963 node_ptr l = node_algorithms::move_backwards(this->get_root_node(), (std::size_t)n);
1964 if(cache_last && l){
1965 this->set_last_node(l);
1969 void priv_shift_forward(size_type n, detail::bool_<true>)
1971 std::pair<node_ptr, node_ptr> ret(
1972 node_algorithms::move_first_n_backwards
1973 (node_traits::get_next(this->get_root_node()), (std::size_t)n));
1975 node_traits::set_next(this->get_root_node(), ret.first);
1977 this->set_last_node(ret.second);
1982 static void priv_swap_cache_last(slist_impl *this_impl, slist_impl *other_impl)
1984 bool other_was_empty = false;
1985 if(this_impl->empty()){
1986 //Check if both are empty or
1987 if(other_impl->empty())
1989 //If this is empty swap pointers
1990 slist_impl *tmp = this_impl;
1991 this_impl = other_impl;
1993 other_was_empty = true;
1996 other_was_empty = other_impl->empty();
1999 //Precondition: this is not empty
2000 node_ptr other_old_last(other_impl->get_last_node());
2001 node_ptr other_bfirst(other_impl->get_root_node());
2002 node_ptr this_bfirst(this_impl->get_root_node());
2003 node_ptr this_old_last(this_impl->get_last_node());
2005 //Move all nodes from this to other's beginning
2006 node_algorithms::transfer_after(other_bfirst, this_bfirst, this_old_last);
2007 other_impl->set_last_node(this_old_last);
2009 if(other_was_empty){
2010 this_impl->set_last_node(this_bfirst);
2013 //Move trailing nodes from other to this
2014 node_algorithms::transfer_after(this_bfirst, this_old_last, other_old_last);
2015 this_impl->set_last_node(other_old_last);
2020 static void priv_swap_lists(const node_ptr & this_node, const node_ptr & other_node, detail::bool_<false>)
2021 { node_algorithms::swap_nodes(this_node, other_node); }
2024 static void priv_swap_lists(const node_ptr & this_node, const node_ptr & other_node, detail::bool_<true>)
2025 { node_algorithms::swap_trailing_nodes(this_node, other_node); }
2027 static slist_impl &priv_container_from_end_iterator(const const_iterator &end_iterator)
2029 //Obtaining the container from the end iterator is not possible with linear
2030 //singly linked lists (because "end" is represented by the null pointer)
2031 BOOST_STATIC_ASSERT(!linear);
2032 BOOST_STATIC_ASSERT((has_container_from_iterator));
2033 node_ptr p = end_iterator.pointed_node();
2034 header_holder_type* h = header_holder_type::get_holder(p);
2035 header_holder_plus_last_t* hpl = detail::parent_from_member< header_holder_plus_last_t, header_holder_type>
2036 (h, &header_holder_plus_last_t::header_holder_);
2037 root_plus_size* r = static_cast< root_plus_size* >(hpl);
2038 data_t *d = detail::parent_from_member<data_t, root_plus_size>
2039 ( r, &data_t::root_plus_size_);
2040 slist_impl *s = detail::parent_from_member<slist_impl, data_t>(d, &slist_impl::data_);
2045 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
2046 template<class T, class ...Options>
2048 template<class ValueTraits, class SizeType, std::size_t BoolFlags, typename HeaderHolder>
2050 inline bool operator<
2051 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
2052 (const slist_impl<T, Options...> &x, const slist_impl<T, Options...> &y)
2054 ( const slist_impl<ValueTraits, SizeType, BoolFlags, HeaderHolder> &x
2055 , const slist_impl<ValueTraits, SizeType, BoolFlags, HeaderHolder> &y)
2057 { return std::lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); }
2059 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
2060 template<class T, class ...Options>
2062 template<class ValueTraits, class SizeType, std::size_t BoolFlags, typename HeaderHolder>
2065 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
2066 (const slist_impl<T, Options...> &x, const slist_impl<T, Options...> &y)
2068 ( const slist_impl<ValueTraits, SizeType, BoolFlags, HeaderHolder> &x
2069 , const slist_impl<ValueTraits, SizeType, BoolFlags, HeaderHolder> &y)
2072 typedef slist_impl<ValueTraits, SizeType, BoolFlags, HeaderHolder> slist_type;
2073 typedef typename slist_type::const_iterator const_iterator;
2074 const bool C = slist_type::constant_time_size;
2075 if(C && x.size() != y.size()){
2078 const_iterator end1 = x.end();
2080 const_iterator i1 = x.begin();
2081 const_iterator i2 = y.begin();
2083 while (i1 != end1 && *i1 == *i2) {
2090 const_iterator end2 = y.end();
2091 while (i1 != end1 && i2 != end2 && *i1 == *i2) {
2095 return i1 == end1 && i2 == end2;
2099 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
2100 template<class T, class ...Options>
2102 template<class ValueTraits, class SizeType, std::size_t BoolFlags, typename HeaderHolder>
2104 inline bool operator!=
2105 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
2106 (const slist_impl<T, Options...> &x, const slist_impl<T, Options...> &y)
2108 ( const slist_impl<ValueTraits, SizeType, BoolFlags, HeaderHolder> &x
2109 , const slist_impl<ValueTraits, SizeType, BoolFlags, HeaderHolder> &y)
2111 { return !(x == y); }
2113 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
2114 template<class T, class ...Options>
2116 template<class ValueTraits, class SizeType, std::size_t BoolFlags, typename HeaderHolder>
2118 inline bool operator>
2119 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
2120 (const slist_impl<T, Options...> &x, const slist_impl<T, Options...> &y)
2122 ( const slist_impl<ValueTraits, SizeType, BoolFlags, HeaderHolder> &x
2123 , const slist_impl<ValueTraits, SizeType, BoolFlags, HeaderHolder> &y)
2127 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
2128 template<class T, class ...Options>
2130 template<class ValueTraits, class SizeType, std::size_t BoolFlags, typename HeaderHolder>
2132 inline bool operator<=
2133 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
2134 (const slist_impl<T, Options...> &x, const slist_impl<T, Options...> &y)
2136 ( const slist_impl<ValueTraits, SizeType, BoolFlags, HeaderHolder> &x
2137 , const slist_impl<ValueTraits, SizeType, BoolFlags, HeaderHolder> &y)
2139 { return !(y < x); }
2141 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
2142 template<class T, class ...Options>
2144 template<class ValueTraits, class SizeType, std::size_t BoolFlags, typename HeaderHolder>
2146 inline bool operator>=
2147 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
2148 (const slist_impl<T, Options...> &x, const slist_impl<T, Options...> &y)
2150 ( const slist_impl<ValueTraits, SizeType, BoolFlags, HeaderHolder> &x
2151 , const slist_impl<ValueTraits, SizeType, BoolFlags, HeaderHolder> &y)
2153 { return !(x < y); }
2155 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
2156 template<class T, class ...Options>
2158 template<class ValueTraits, class SizeType, std::size_t BoolFlags, typename HeaderHolder>
2161 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
2162 (slist_impl<T, Options...> &x, slist_impl<T, Options...> &y)
2164 ( slist_impl<ValueTraits, SizeType, BoolFlags, HeaderHolder> &x
2165 , slist_impl<ValueTraits, SizeType, BoolFlags, HeaderHolder> &y)
2169 //! Helper metafunction to define a \c slist that yields to the same type when the
2170 //! same options (either explicitly or implicitly) are used.
2171 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
2172 template<class T, class ...Options>
2174 template<class T, class O1 = void, class O2 = void, class O3 = void, class O4 = void, class O5 = void, class O6 = void>
2179 typedef typename pack_options
2181 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
2182 O1, O2, O3, O4, O5, O6
2186 >::type packed_options;
2187 typedef typename detail::get_value_traits
2188 <T, typename packed_options::proto_value_traits>::type value_traits;
2189 typedef typename detail::get_header_holder_type
2190 < value_traits, typename packed_options::header_holder_type >::type header_holder_type;
2193 , typename packed_options::size_type
2194 , (std::size_t(packed_options::linear)*slist_bool_flags::linear_pos)
2195 |(std::size_t(packed_options::constant_time_size)*slist_bool_flags::constant_time_size_pos)
2196 |(std::size_t(packed_options::cache_last)*slist_bool_flags::cache_last_pos)
2197 , header_holder_type
2198 > implementation_defined;
2200 typedef implementation_defined type;
2204 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
2206 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
2207 template<class T, class O1, class O2, class O3, class O4, class O5, class O6>
2209 template<class T, class ...Options>
2212 : public make_slist<T,
2213 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
2214 O1, O2, O3, O4, O5, O6
2220 typedef typename make_slist
2222 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
2223 O1, O2, O3, O4, O5, O6
2228 //Assert if passed value traits are compatible with the type
2229 BOOST_STATIC_ASSERT((detail::is_same<typename Base::value_traits::value_type, T>::value));
2230 BOOST_MOVABLE_BUT_NOT_COPYABLE(slist)
2233 typedef typename Base::value_traits value_traits;
2234 typedef typename Base::iterator iterator;
2235 typedef typename Base::const_iterator const_iterator;
2236 typedef typename Base::size_type size_type;
2237 typedef typename Base::node_ptr node_ptr;
2239 explicit slist(const value_traits &v_traits = value_traits())
2243 struct incorporate_t{};
2245 slist( const node_ptr & f, const node_ptr & before_l
2246 , size_type n, const value_traits &v_traits = value_traits())
2247 : Base(f, before_l, n, v_traits)
2250 template<class Iterator>
2251 slist(Iterator b, Iterator e, const value_traits &v_traits = value_traits())
2252 : Base(b, e, v_traits)
2255 slist(BOOST_RV_REF(slist) x)
2256 : Base(::boost::move(static_cast<Base&>(x)))
2259 slist& operator=(BOOST_RV_REF(slist) x)
2260 { return static_cast<slist &>(this->Base::operator=(::boost::move(static_cast<Base&>(x)))); }
2262 static slist &container_from_end_iterator(iterator end_iterator)
2263 { return static_cast<slist &>(Base::container_from_end_iterator(end_iterator)); }
2265 static const slist &container_from_end_iterator(const_iterator end_iterator)
2266 { return static_cast<const slist &>(Base::container_from_end_iterator(end_iterator)); }
2271 } //namespace intrusive
2274 #include <boost/intrusive/detail/config_end.hpp>
2276 #endif //BOOST_INTRUSIVE_SLIST_HPP