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