1 //////////////////////////////////////////////////////////////////////////////
3 // (C) Copyright Ion Gaztanaga 2004-2011. Distributed under the Boost
4 // Software License, Version 1.0. (See accompanying file
5 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
7 // See http://www.boost.org/libs/container for documentation.
9 //////////////////////////////////////////////////////////////////////////////
11 #ifndef BOOST_CONTAINERS_SLIST_HPP
12 #define BOOST_CONTAINERS_SLIST_HPP
14 #if (defined _MSC_VER) && (_MSC_VER >= 1200)
18 #include <boost/container/detail/config_begin.hpp>
19 #include <boost/container/detail/workaround.hpp>
21 #include <boost/container/container_fwd.hpp>
22 #include <boost/move/move.hpp>
23 #include <boost/pointer_to_other.hpp>
24 #include <boost/container/detail/utilities.hpp>
25 #include <boost/container/detail/mpl.hpp>
26 #include <boost/type_traits/has_trivial_destructor.hpp>
27 #include <boost/detail/no_exceptions_support.hpp>
28 #include <boost/container/detail/node_alloc_holder.hpp>
29 #include <boost/intrusive/slist.hpp>
32 #if defined(BOOST_CONTAINERS_PERFECT_FORWARDING) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
33 //Preprocessor library to emulate perfect forwarding
35 #include <boost/container/detail/preprocessor.hpp>
45 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
55 namespace containers_detail {
57 template<class VoidPointer>
60 typedef typename containers_detail::bi::make_slist_base_hook
61 <containers_detail::bi::void_pointer<VoidPointer>, containers_detail::bi::link_mode<containers_detail::bi::normal_link> >::type type;
64 template <class T, class VoidPointer>
66 : public slist_hook<VoidPointer>::type
68 #if defined(BOOST_CONTAINERS_PERFECT_FORWARDING) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
74 template<class ...Args>
75 slist_node(Args &&...args)
76 : m_data(boost::forward<Args>(args)...)
79 #else //#ifdef BOOST_CONTAINERS_PERFECT_FORWARDING
85 #define BOOST_PP_LOCAL_MACRO(n) \
86 template<BOOST_PP_ENUM_PARAMS(n, class P)> \
87 slist_node(BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_LIST, _)) \
88 : m_data(BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_FORWARD, _)) \
91 #define BOOST_PP_LOCAL_LIMITS (1, BOOST_CONTAINERS_MAX_CONSTRUCTOR_PARAMETERS)
92 #include BOOST_PP_LOCAL_ITERATE()
94 #endif//#ifdef BOOST_CONTAINERS_PERFECT_FORWARDING
100 struct intrusive_slist_type
102 typedef typename A::value_type value_type;
103 typedef typename boost::pointer_to_other
104 <typename A::pointer, void>::type void_pointer;
105 typedef typename containers_detail::slist_node
106 <value_type, void_pointer> node_type;
108 typedef typename containers_detail::bi::make_slist
110 ,containers_detail::bi::base_hook<typename slist_hook<void_pointer>::type>
111 ,containers_detail::bi::constant_time_size<true>
112 ,containers_detail::bi::size_type<typename A::size_type>
113 >::type container_type;
114 typedef container_type type ;
117 } //namespace containers_detail {
121 //! An slist is a singly linked list: a list where each element is linked to the next
122 //! element, but not to the previous element. That is, it is a Sequence that
123 //! supports forward but not backward traversal, and (amortized) constant time
124 //! insertion and removal of elements. Slists, like lists, have the important
125 //! property that insertion and splicing do not invalidate iterators to list elements,
126 //! and that even removal invalidates only the iterators that point to the elements
127 //! that are removed. The ordering of iterators may be changed (that is,
128 //! slist<T>::iterator might have a different predecessor or successor after a list
129 //! operation than it did before), but the iterators themselves will not be invalidated
130 //! or made to point to different elements unless that invalidation or mutation is explicit.
132 //! The main difference between slist and list is that list's iterators are bidirectional
133 //! iterators, while slist's iterators are forward iterators. This means that slist is
134 //! less versatile than list; frequently, however, bidirectional iterators are
135 //! unnecessary. You should usually use slist unless you actually need the extra
136 //! functionality of list, because singly linked lists are smaller and faster than double
139 //! Important performance note: like every other Sequence, slist defines the member
140 //! functions insert and erase. Using these member functions carelessly, however, can
141 //! result in disastrously slow programs. The problem is that insert's first argument is
142 //! an iterator p, and that it inserts the new element(s) before p. This means that
143 //! insert must find the iterator just before p; this is a constant-time operation
144 //! for list, since list has bidirectional iterators, but for slist it must find that
145 //! iterator by traversing the list from the beginning up to p. In other words:
146 //! insert and erase are slow operations anywhere but near the beginning of the slist.
148 //! Slist provides the member functions insert_after and erase_after, which are constant
149 //! time operations: you should always use insert_after and erase_after whenever
150 //! possible. If you find that insert_after and erase_after aren't adequate for your
151 //! needs, and that you often need to use insert and erase in the middle of the list,
152 //! then you should probably use list instead of slist.
153 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
154 template <class T, class A = std::allocator<T> >
156 template <class T, class A>
159 : protected containers_detail::node_alloc_holder
160 <A, typename containers_detail::intrusive_slist_type<A>::type>
163 typedef typename containers_detail::
164 move_const_ref_type<T>::type insert_const_ref_type;
166 containers_detail::intrusive_slist_type<A>::type Icont;
167 typedef containers_detail::node_alloc_holder<A, Icont> AllocHolder;
168 typedef typename AllocHolder::NodePtr NodePtr;
169 typedef slist <T, A> ThisType;
170 typedef typename AllocHolder::NodeAlloc NodeAlloc;
171 typedef typename AllocHolder::ValAlloc ValAlloc;
172 typedef typename AllocHolder::Node Node;
173 typedef containers_detail::allocator_destroyer<NodeAlloc> Destroyer;
174 typedef typename AllocHolder::allocator_v1 allocator_v1;
175 typedef typename AllocHolder::allocator_v2 allocator_v2;
176 typedef typename AllocHolder::alloc_version alloc_version;
180 typedef typename AllocHolder::value_type value_type;
181 const value_type &t_;
184 equal_to_value(const value_type &t)
188 bool operator()(const value_type &t)const
193 struct ValueCompareToNodeCompare
196 ValueCompareToNodeCompare(Pred pred)
200 bool operator()(const Node &a, const Node &b) const
201 { return static_cast<const Pred&>(*this)(a.m_data, b.m_data); }
203 bool operator()(const Node &a) const
204 { return static_cast<const Pred&>(*this)(a.m_data); }
208 //! The type of object, T, stored in the list
209 typedef T value_type;
211 typedef typename A::pointer pointer;
212 //! Const pointer to T
213 typedef typename A::const_pointer const_pointer;
215 typedef typename A::reference reference;
216 //! Const reference to T
217 typedef typename A::const_reference const_reference;
218 //! An unsigned integral type
219 typedef typename A::size_type size_type;
220 //! A signed integral type
221 typedef typename A::difference_type difference_type;
222 //! The allocator type
223 typedef A allocator_type;
224 //! The stored allocator type
225 typedef NodeAlloc stored_allocator_type;
229 BOOST_COPYABLE_AND_MOVABLE(slist)
230 typedef difference_type list_difference_type;
231 typedef pointer list_pointer;
232 typedef const_pointer list_const_pointer;
233 typedef reference list_reference;
234 typedef const_reference list_const_reference;
239 //! Const iterator used to iterate through a list.
242 : public std::iterator<std::forward_iterator_tag,
243 value_type, list_difference_type,
244 list_const_pointer, list_const_reference>
248 typename Icont::iterator m_it;
249 explicit const_iterator(typename Icont::iterator it) : m_it(it){}
250 void prot_incr(){ ++m_it; }
253 typename Icont::iterator get()
254 { return this->m_it; }
257 friend class slist<T, A>;
258 typedef list_difference_type difference_type;
265 //Pointer like operators
266 const_reference operator*() const
267 { return m_it->m_data; }
269 const_pointer operator->() const
270 { return const_pointer(&m_it->m_data); }
272 //Increment / Decrement
273 const_iterator& operator++()
274 { prot_incr(); return *this; }
276 const_iterator operator++(int)
277 { typename Icont::iterator tmp = m_it; ++*this; return const_iterator(tmp); }
279 //Comparison operators
280 bool operator== (const const_iterator& r) const
281 { return m_it == r.m_it; }
283 bool operator!= (const const_iterator& r) const
284 { return m_it != r.m_it; }
289 //! Iterator used to iterate through a list
292 : public const_iterator
296 explicit iterator(typename Icont::iterator it)
300 typename Icont::iterator get()
301 { return this->m_it; }
304 friend class slist<T, A>;
305 typedef list_pointer pointer;
306 typedef list_reference reference;
311 //Pointer like operators
312 reference operator*() const { return this->m_it->m_data; }
313 pointer operator->() const { return pointer(&this->m_it->m_data); }
315 //Increment / Decrement
316 iterator& operator++()
317 { this->prot_incr(); return *this; }
319 iterator operator++(int)
320 { typename Icont::iterator tmp = this->m_it; ++*this; return iterator(tmp); }
326 //! <b>Effects</b>: Constructs a list taking the allocator as parameter.
328 //! <b>Throws</b>: If allocator_type's copy constructor throws.
330 //! <b>Complexity</b>: Constant.
331 explicit slist(const allocator_type& a = allocator_type())
335 explicit slist(size_type n)
336 : AllocHolder(allocator_type())
339 //! <b>Effects</b>: Constructs a list that will use a copy of allocator a
340 //! and inserts n copies of value.
342 //! <b>Throws</b>: If allocator_type's default constructor or copy constructor
343 //! throws or T's default or copy constructor throws.
345 //! <b>Complexity</b>: Linear to n.
346 explicit slist(size_type n, const value_type& x, const allocator_type& a = allocator_type())
348 { this->priv_create_and_insert_nodes(this->before_begin(), n, x); }
350 //! <b>Effects</b>: Constructs a list that will use a copy of allocator a
351 //! and inserts a copy of the range [first, last) in the list.
353 //! <b>Throws</b>: If allocator_type's default constructor or copy constructor
354 //! throws or T's constructor taking an dereferenced InIt throws.
356 //! <b>Complexity</b>: Linear to the range [first, last).
357 template <class InpIt>
358 slist(InpIt first, InpIt last,
359 const allocator_type& a = allocator_type())
361 { this->insert_after(this->before_begin(), first, last); }
363 //! <b>Effects</b>: Copy constructs a list.
365 //! <b>Postcondition</b>: x == *this.
367 //! <b>Throws</b>: If allocator_type's default constructor or copy constructor throws.
369 //! <b>Complexity</b>: Linear to the elements x contains.
370 slist(const slist& x)
372 { this->insert_after(this->before_begin(), x.begin(), x.end()); }
374 //! <b>Effects</b>: Move constructor. Moves mx's resources to *this.
376 //! <b>Throws</b>: If allocator_type's copy constructor throws.
378 //! <b>Complexity</b>: Constant.
379 slist(BOOST_RV_REF(slist) x)
380 : AllocHolder(boost::move((AllocHolder&)x))
383 //! <b>Effects</b>: Makes *this contain the same elements as x.
385 //! <b>Postcondition</b>: this->size() == x.size(). *this contains a copy
386 //! of each of x's elements.
388 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws.
390 //! <b>Complexity</b>: Linear to the number of elements in x.
391 slist& operator= (BOOST_COPY_ASSIGN_REF(slist) x)
394 this->assign(x.begin(), x.end());
399 //! <b>Effects</b>: Makes *this contain the same elements as x.
401 //! <b>Postcondition</b>: this->size() == x.size(). *this contains a copy
402 //! of each of x's elements.
404 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws.
406 //! <b>Complexity</b>: Linear to the number of elements in x.
407 slist& operator= (BOOST_RV_REF(slist) mx)
416 //! <b>Effects</b>: Destroys the list. All stored values are destroyed
417 //! and used memory is deallocated.
419 //! <b>Throws</b>: Nothing.
421 //! <b>Complexity</b>: Linear to the number of elements.
423 {} //AllocHolder clears the slist
425 //! <b>Effects</b>: Returns a copy of the internal allocator.
427 //! <b>Throws</b>: If allocator's copy constructor throws.
429 //! <b>Complexity</b>: Constant.
430 allocator_type get_allocator() const
431 { return allocator_type(this->node_alloc()); }
433 const stored_allocator_type &get_stored_allocator() const
434 { return this->node_alloc(); }
436 stored_allocator_type &get_stored_allocator()
437 { return this->node_alloc(); }
441 //! <b>Effects</b>: Assigns the n copies of val to *this.
443 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws.
445 //! <b>Complexity</b>: Linear to n.
446 void assign(size_type n, const T& val)
447 { this->priv_fill_assign(n, val); }
449 //! <b>Effects</b>: Assigns the range [first, last) to *this.
451 //! <b>Throws</b>: If memory allocation throws or
452 //! T's constructor from dereferencing InpIt throws.
454 //! <b>Complexity</b>: Linear to n.
455 template <class InpIt>
456 void assign(InpIt first, InpIt last)
458 const bool aux_boolean = containers_detail::is_convertible<InpIt, size_type>::value;
459 typedef containers_detail::bool_<aux_boolean> Result;
460 this->priv_assign_dispatch(first, last, Result());
463 //! <b>Effects</b>: Returns an iterator to the first element contained in the list.
465 //! <b>Throws</b>: Nothing.
467 //! <b>Complexity</b>: Constant.
469 { return iterator(this->icont().begin()); }
471 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the list.
473 //! <b>Throws</b>: Nothing.
475 //! <b>Complexity</b>: Constant.
476 const_iterator begin() const
477 { return this->cbegin(); }
479 //! <b>Effects</b>: Returns an iterator to the end of the list.
481 //! <b>Throws</b>: Nothing.
483 //! <b>Complexity</b>: Constant.
485 { return iterator(this->icont().end()); }
487 //! <b>Effects</b>: Returns a const_iterator to the end of the list.
489 //! <b>Throws</b>: Nothing.
491 //! <b>Complexity</b>: Constant.
492 const_iterator end() const
493 { return this->cend(); }
495 //! <b>Effects</b>: Returns a non-dereferenceable iterator that,
496 //! when incremented, yields begin(). This iterator may be used
497 //! as the argument toinsert_after, erase_after, etc.
499 //! <b>Throws</b>: Nothing.
501 //! <b>Complexity</b>: Constant.
502 iterator before_begin()
503 { return iterator(end()); }
505 //! <b>Effects</b>: Returns a non-dereferenceable const_iterator
506 //! that, when incremented, yields begin(). This iterator may be used
507 //! as the argument toinsert_after, erase_after, etc.
509 //! <b>Throws</b>: Nothing.
511 //! <b>Complexity</b>: Constant.
512 const_iterator before_begin() const
513 { return this->cbefore_begin(); }
515 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the list.
517 //! <b>Throws</b>: Nothing.
519 //! <b>Complexity</b>: Constant.
520 const_iterator cbegin() const
521 { return const_iterator(this->non_const_icont().begin()); }
523 //! <b>Effects</b>: Returns a const_iterator to the end of the list.
525 //! <b>Throws</b>: Nothing.
527 //! <b>Complexity</b>: Constant.
528 const_iterator cend() const
529 { return const_iterator(this->non_const_icont().end()); }
531 //! <b>Effects</b>: Returns a non-dereferenceable const_iterator
532 //! that, when incremented, yields begin(). This iterator may be used
533 //! as the argument toinsert_after, erase_after, etc.
535 //! <b>Throws</b>: Nothing.
537 //! <b>Complexity</b>: Constant.
538 const_iterator cbefore_begin() const
539 { return const_iterator(end()); }
541 //! <b>Effects</b>: Returns the number of the elements contained in the list.
543 //! <b>Throws</b>: Nothing.
545 //! <b>Complexity</b>: Constant.
546 size_type size() const
547 { return this->icont().size(); }
549 //! <b>Effects</b>: Returns the largest possible size of the list.
551 //! <b>Throws</b>: Nothing.
553 //! <b>Complexity</b>: Constant.
554 size_type max_size() const
555 { return AllocHolder::max_size(); }
557 //! <b>Effects</b>: Returns true if the list contains no elements.
559 //! <b>Throws</b>: Nothing.
561 //! <b>Complexity</b>: Constant.
563 { return !this->size(); }
565 //! <b>Effects</b>: Swaps the contents of *this and x.
566 //! If this->allocator_type() != x.allocator_type()
567 //! allocators are also swapped.
569 //! <b>Throws</b>: Nothing.
571 //! <b>Complexity</b>: Linear to the number of elements on *this and x.
573 { AllocHolder::swap(x); }
575 //! <b>Requires</b>: !empty()
577 //! <b>Effects</b>: Returns a reference to the first element
578 //! from the beginning of the container.
580 //! <b>Throws</b>: Nothing.
582 //! <b>Complexity</b>: Constant.
584 { return *this->begin(); }
586 //! <b>Requires</b>: !empty()
588 //! <b>Effects</b>: Returns a const reference to the first element
589 //! from the beginning of the container.
591 //! <b>Throws</b>: Nothing.
593 //! <b>Complexity</b>: Constant.
594 const_reference front() const
595 { return *this->begin(); }
597 //! <b>Effects</b>: Inserts a copy of t in the beginning of the list.
599 //! <b>Throws</b>: If memory allocation throws or
600 //! T's copy constructor throws.
602 //! <b>Complexity</b>: Amortized constant time.
603 void push_front(insert_const_ref_type x)
604 { return priv_push_front(x); }
606 #if defined(BOOST_NO_RVALUE_REFERENCES) && !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
607 void push_front(T &x) { push_front(const_cast<const T &>(x)); }
610 void push_front(const U &u, typename containers_detail::enable_if_c<containers_detail::is_same<T, U>::value && !::boost::has_move_emulation_enabled<U>::value >::type* =0)
611 { return priv_push_front(u); }
614 //! <b>Effects</b>: Constructs a new element in the beginning of the list
615 //! and moves the resources of t to this new element.
617 //! <b>Throws</b>: If memory allocation throws.
619 //! <b>Complexity</b>: Amortized constant time.
620 void push_front(BOOST_RV_REF(T) x)
621 { this->icont().push_front(*this->create_node(boost::move(x))); }
623 //! <b>Effects</b>: Removes the first element from the list.
625 //! <b>Throws</b>: Nothing.
627 //! <b>Complexity</b>: Amortized constant time.
629 { this->icont().pop_front_and_dispose(Destroyer(this->node_alloc())); }
631 //! <b>Returns</b>: The iterator to the element before i in the sequence.
632 //! Returns the end-iterator, if either i is the begin-iterator or the
633 //! sequence is empty.
635 //! <b>Throws</b>: Nothing.
637 //! <b>Complexity</b>: Linear to the number of elements before i.
638 iterator previous(iterator p)
639 { return iterator(this->icont().previous(p.get())); }
641 //! <b>Returns</b>: The const_iterator to the element before i in the sequence.
642 //! Returns the end-const_iterator, if either i is the begin-const_iterator or
643 //! the sequence is empty.
645 //! <b>Throws</b>: Nothing.
647 //! <b>Complexity</b>: Linear to the number of elements before i.
648 const_iterator previous(const_iterator p)
649 { return const_iterator(this->icont().previous(p.get())); }
651 //! <b>Requires</b>: p must be a valid iterator of *this.
653 //! <b>Effects</b>: Inserts a copy of the value after the p pointed
656 //! <b>Returns</b>: An iterator to the inserted element.
658 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws.
660 //! <b>Complexity</b>: Amortized constant time.
662 //! <b>Note</b>: Does not affect the validity of iterators and references of
664 iterator insert_after(const_iterator prev_pos, insert_const_ref_type x)
665 { return this->priv_insert_after(prev_pos, x); }
667 #if defined(BOOST_NO_RVALUE_REFERENCES) && !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
668 iterator insert_after(const_iterator position, T &x)
669 { return this->insert_after(position, const_cast<const T &>(x)); }
672 iterator insert_after(const_iterator position, const U &u, typename containers_detail::enable_if_c<containers_detail::is_same<T, U>::value && !::boost::has_move_emulation_enabled<U>::value >::type* =0)
673 { return this->priv_insert_after(position, u); }
676 //! <b>Requires</b>: prev_pos must be a valid iterator of *this.
678 //! <b>Effects</b>: Inserts a move constructed copy object from the value after the
679 //! p pointed by prev_pos.
681 //! <b>Returns</b>: An iterator to the inserted element.
683 //! <b>Throws</b>: If memory allocation throws.
685 //! <b>Complexity</b>: Amortized constant time.
687 //! <b>Note</b>: Does not affect the validity of iterators and references of
689 iterator insert_after(const_iterator prev_pos, BOOST_RV_REF(value_type) x)
690 { return iterator(this->icont().insert_after(prev_pos.get(), *this->create_node(boost::move(x)))); }
692 //! <b>Requires</b>: prev_pos must be a valid iterator of *this.
694 //! <b>Effects</b>: Inserts n copies of x after prev_pos.
696 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws.
698 //! <b>Complexity</b>: Linear to n.
700 //! <b>Note</b>: Does not affect the validity of iterators and references of
702 void insert_after(const_iterator prev_pos, size_type n, const value_type& x)
703 { this->priv_create_and_insert_nodes(prev_pos, n, x); }
705 //! <b>Requires</b>: prev_pos must be a valid iterator of *this.
707 //! <b>Effects</b>: Inserts the range pointed by [first, last)
708 //! after the p prev_pos.
710 //! <b>Throws</b>: If memory allocation throws, T's constructor from a
711 //! dereferenced InpIt throws.
713 //! <b>Complexity</b>: Linear to the number of elements inserted.
715 //! <b>Note</b>: Does not affect the validity of iterators and references of
717 template <class InIter>
718 void insert_after(const_iterator prev_pos, InIter first, InIter last)
720 const bool aux_boolean = containers_detail::is_convertible<InIter, size_type>::value;
721 typedef containers_detail::bool_<aux_boolean> Result;
722 this->priv_insert_after_range_dispatch(prev_pos, first, last, Result());
725 //! <b>Requires</b>: p must be a valid iterator of *this.
727 //! <b>Effects</b>: Insert a copy of x before p.
729 //! <b>Throws</b>: If memory allocation throws or x's copy constructor throws.
731 //! <b>Complexity</b>: Linear to the elements before p.
732 iterator insert(const_iterator position, insert_const_ref_type x)
733 { return this->priv_insert(position, x); }
735 #if defined(BOOST_NO_RVALUE_REFERENCES) && !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
736 iterator insert(const_iterator position, T &x)
737 { return this->insert(position, const_cast<const T &>(x)); }
740 iterator insert(const_iterator position, const U &u, typename containers_detail::enable_if_c<containers_detail::is_same<T, U>::value && !::boost::has_move_emulation_enabled<U>::value >::type* =0)
741 { return this->priv_insert(position, u); }
744 //! <b>Requires</b>: p must be a valid iterator of *this.
746 //! <b>Effects</b>: Insert a new element before p with mx's resources.
748 //! <b>Throws</b>: If memory allocation throws.
750 //! <b>Complexity</b>: Linear to the elements before p.
751 iterator insert(const_iterator p, BOOST_RV_REF(value_type) x)
752 { return this->insert_after(previous(p), boost::move(x)); }
754 //! <b>Requires</b>: p must be a valid iterator of *this.
756 //! <b>Effects</b>: Inserts n copies of x before p.
758 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws.
760 //! <b>Complexity</b>: Linear to n plus linear to the elements before p.
761 void insert(const_iterator p, size_type n, const value_type& x)
762 { return this->insert_after(previous(p), n, x); }
764 //! <b>Requires</b>: p must be a valid iterator of *this.
766 //! <b>Effects</b>: Insert a copy of the [first, last) range before p.
768 //! <b>Throws</b>: If memory allocation throws, T's constructor from a
769 //! dereferenced InpIt throws.
771 //! <b>Complexity</b>: Linear to std::distance [first, last) plus
772 //! linear to the elements before p.
773 template <class InIter>
774 void insert(const_iterator p, InIter first, InIter last)
775 { return this->insert_after(previous(p), first, last); }
777 #if defined(BOOST_CONTAINERS_PERFECT_FORWARDING) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
779 //! <b>Effects</b>: Inserts an object of type T constructed with
780 //! std::forward<Args>(args)... in the front of the list
782 //! <b>Throws</b>: If memory allocation throws or
783 //! T's copy constructor throws.
785 //! <b>Complexity</b>: Amortized constant time.
786 template <class... Args>
787 void emplace_front(Args&&... args)
788 { this->emplace_after(this->cbefore_begin(), boost::forward<Args>(args)...); }
790 //! <b>Effects</b>: Inserts an object of type T constructed with
791 //! std::forward<Args>(args)... before p
793 //! <b>Throws</b>: If memory allocation throws or
794 //! T's in-place constructor throws.
796 //! <b>Complexity</b>: Linear to the elements before p
797 template <class... Args>
798 iterator emplace(const_iterator p, Args&&... args)
799 { return this->emplace_after(this->previous(p), boost::forward<Args>(args)...); }
801 //! <b>Effects</b>: Inserts an object of type T constructed with
802 //! std::forward<Args>(args)... after prev
804 //! <b>Throws</b>: If memory allocation throws or
805 //! T's in-place constructor throws.
807 //! <b>Complexity</b>: Constant
808 template <class... Args>
809 iterator emplace_after(const_iterator prev, Args&&... args)
811 typename AllocHolder::Deallocator d(AllocHolder::create_node_and_deallocator());
812 new ((void*)containers_detail::get_pointer(d.get())) Node(boost::forward<Args>(args)...);
813 NodePtr node = d.get();
815 return iterator(this->icont().insert_after(prev.get(), *node));
818 #else //#ifdef BOOST_CONTAINERS_PERFECT_FORWARDING
822 { this->emplace_after(this->cbefore_begin()); }
824 iterator emplace(const_iterator p)
825 { return this->emplace_after(this->previous(p)); }
827 iterator emplace_after(const_iterator prev)
829 typename AllocHolder::Deallocator d(AllocHolder::create_node_and_deallocator());
830 new ((void*)containers_detail::get_pointer(d.get())) Node();
831 NodePtr node = d.get();
833 return iterator(this->icont().insert_after(prev.get(), *node));
836 #define BOOST_PP_LOCAL_MACRO(n) \
837 template<BOOST_PP_ENUM_PARAMS(n, class P)> \
838 void emplace_front(BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_LIST, _)) \
841 (this->cbegin(), BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_FORWARD, _)); \
844 template<BOOST_PP_ENUM_PARAMS(n, class P)> \
846 (const_iterator p, BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_LIST, _)) \
848 return this->emplace_after \
849 (this->previous(p), BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_FORWARD, _)); \
852 template<BOOST_PP_ENUM_PARAMS(n, class P)> \
853 iterator emplace_after \
854 (const_iterator prev, BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_LIST, _)) \
856 typename AllocHolder::Deallocator d(AllocHolder::create_node_and_deallocator()); \
857 new ((void*)containers_detail::get_pointer(d.get())) \
858 Node(BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_FORWARD, _)); \
859 NodePtr node = d.get(); \
861 return iterator(this->icont().insert_after(prev.get(), *node)); \
864 #define BOOST_PP_LOCAL_LIMITS (1, BOOST_CONTAINERS_MAX_CONSTRUCTOR_PARAMETERS)
865 #include BOOST_PP_LOCAL_ITERATE()
867 #endif //#ifdef BOOST_CONTAINERS_PERFECT_FORWARDING
869 //! <b>Effects</b>: Erases the element after the element pointed by prev_pos
872 //! <b>Returns</b>: the first element remaining beyond the removed elements,
873 //! or end() if no such element exists.
875 //! <b>Throws</b>: Nothing.
877 //! <b>Complexity</b>: Constant.
879 //! <b>Note</b>: Does not invalidate iterators or references to non erased elements.
880 iterator erase_after(const_iterator prev_pos)
882 return iterator(this->icont().erase_after_and_dispose(prev_pos.get(), Destroyer(this->node_alloc())));
885 //! <b>Effects</b>: Erases the range (before_first, last) from
888 //! <b>Returns</b>: the first element remaining beyond the removed elements,
889 //! or end() if no such element exists.
891 //! <b>Throws</b>: Nothing.
893 //! <b>Complexity</b>: Linear to the number of erased elements.
895 //! <b>Note</b>: Does not invalidate iterators or references to non erased elements.
896 iterator erase_after(const_iterator before_first, const_iterator last)
898 return iterator(this->icont().erase_after_and_dispose(before_first.get(), last.get(), Destroyer(this->node_alloc())));
901 //! <b>Requires</b>: p must be a valid iterator of *this.
903 //! <b>Effects</b>: Erases the element at p p.
905 //! <b>Throws</b>: Nothing.
907 //! <b>Complexity</b>: Linear to the number of elements before p.
908 iterator erase(const_iterator p)
909 { return iterator(this->erase_after(previous(p))); }
911 //! <b>Requires</b>: first and last must be valid iterator to elements in *this.
913 //! <b>Effects</b>: Erases the elements pointed by [first, last).
915 //! <b>Throws</b>: Nothing.
917 //! <b>Complexity</b>: Linear to the distance between first and last plus
918 //! linear to the elements before first.
919 iterator erase(const_iterator first, const_iterator last)
920 { return iterator(this->erase_after(previous(first), last)); }
922 //! <b>Effects</b>: Inserts or erases elements at the end such that
923 //! the size becomes n. New elements are copy constructed from x.
925 //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws.
927 //! <b>Complexity</b>: Linear to the difference between size() and new_size.
928 void resize(size_type new_size, const T& x)
930 typename Icont::iterator end_n(this->icont().end()), cur(this->icont().before_begin()), cur_next;
931 while (++(cur_next = cur) != end_n && new_size > 0){
935 if (cur_next != end_n)
936 this->erase_after(const_iterator(cur), const_iterator(end_n));
938 this->insert_after(const_iterator(cur), new_size, x);
941 //! <b>Effects</b>: Inserts or erases elements at the end such that
942 //! the size becomes n. New elements are default constructed.
944 //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws.
946 //! <b>Complexity</b>: Linear to the difference between size() and new_size.
947 void resize(size_type new_size)
949 typename Icont::iterator end_n(this->icont().end()), cur(this->icont().before_begin()), cur_next;
950 size_type len = this->size();
951 size_type left = new_size;
953 while (++(cur_next = cur) != end_n && left > 0){
957 if (cur_next != end_n){
958 this->erase_after(const_iterator(cur), const_iterator(end_n));
961 this->priv_create_and_insert_nodes(const_iterator(cur), new_size - len);
965 //! <b>Effects</b>: Erases all the elements of the list.
967 //! <b>Throws</b>: Nothing.
969 //! <b>Complexity</b>: Linear to the number of elements in the list.
971 { this->icont().clear_and_dispose(Destroyer(this->node_alloc())); }
973 //! <b>Requires</b>: p must point to an element contained
974 //! by the list. x != *this
976 //! <b>Effects</b>: Transfers all the elements of list x to this list, after the
977 //! the element pointed by p. No destructors or copy constructors are called.
979 //! <b>Throws</b>: std::runtime_error if this' allocator and x's allocator
982 //! <b>Complexity</b>: Linear to the elements in x.
984 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of
985 //! this list. Iterators of this list and all the references are not invalidated.
986 void splice_after(const_iterator prev_pos, slist& x)
988 if((NodeAlloc&)*this == (NodeAlloc&)x){
989 this->icont().splice_after(prev_pos.get(), x.icont());
992 throw std::runtime_error("slist::splice called with unequal allocators");
996 //! <b>Requires</b>: prev_pos must be a valid iterator of this.
997 //! i must point to an element contained in list x.
999 //! <b>Effects</b>: Transfers the value pointed by i, from list x to this list,
1000 //! after the element pointed by prev_pos.
1001 //! If prev_pos == prev or prev_pos == ++prev, this function is a null operation.
1003 //! <b>Throws</b>: std::runtime_error if this' allocator and x's allocator
1006 //! <b>Complexity</b>: Constant.
1008 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this
1009 //! list. Iterators of this list and all the references are not invalidated.
1010 void splice_after(const_iterator prev_pos, slist& x, const_iterator prev)
1012 if((NodeAlloc&)*this == (NodeAlloc&)x){
1013 this->icont().splice_after(prev_pos.get(), x.icont(), prev.get());
1016 throw std::runtime_error("slist::splice called with unequal allocators");
1020 //! <b>Requires</b>: prev_pos must be a valid iterator of this.
1021 //! before_first and before_last must be valid iterators of x.
1022 //! prev_pos must not be contained in [before_first, before_last) range.
1024 //! <b>Effects</b>: Transfers the range [before_first + 1, before_last + 1)
1025 //! from list x to this list, after the element pointed by prev_pos.
1027 //! <b>Throws</b>: std::runtime_error if this' allocator and x's allocator
1030 //! <b>Complexity</b>: Linear to the number of transferred elements.
1032 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this
1033 //! list. Iterators of this list and all the references are not invalidated.
1034 void splice_after(const_iterator prev_pos, slist& x,
1035 const_iterator before_first, const_iterator before_last)
1037 if((NodeAlloc&)*this == (NodeAlloc&)x){
1038 this->icont().splice_after
1039 (prev_pos.get(), x.icont(), before_first.get(), before_last.get());
1042 throw std::runtime_error("slist::splice called with unequal allocators");
1046 //! <b>Requires</b>: prev_pos must be a valid iterator of this.
1047 //! before_first and before_last must be valid iterators of x.
1048 //! prev_pos must not be contained in [before_first, before_last) range.
1049 //! n == std::distance(before_first, before_last)
1051 //! <b>Effects</b>: Transfers the range [before_first + 1, before_last + 1)
1052 //! from list x to this list, after the element pointed by prev_pos.
1054 //! <b>Throws</b>: std::runtime_error if this' allocator and x's allocator
1057 //! <b>Complexity</b>: Constant.
1059 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this
1060 //! list. Iterators of this list and all the references are not invalidated.
1061 void splice_after(const_iterator prev_pos, slist& x,
1062 const_iterator before_first, const_iterator before_last,
1065 if((NodeAlloc&)*this == (NodeAlloc&)x){
1066 this->icont().splice_after
1067 (prev_pos.get(), x.icont(), before_first.get(), before_last.get(), n);
1070 throw std::runtime_error("slist::splice called with unequal allocators");
1074 //! <b>Requires</b>: p must point to an element contained
1075 //! by the list. x != *this
1077 //! <b>Effects</b>: Transfers all the elements of list x to this list, before the
1078 //! the element pointed by p. No destructors or copy constructors are called.
1080 //! <b>Throws</b>: std::runtime_error if this' allocator and x's allocator
1083 //! <b>Complexity</b>: Linear in distance(begin(), p), and linear in x.size().
1085 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of
1086 //! this list. Iterators of this list and all the references are not invalidated.
1087 void splice(const_iterator p, ThisType& x)
1088 { this->splice_after(this->previous(p), x); }
1090 //! <b>Requires</b>: p must point to an element contained
1091 //! by this list. i must point to an element contained in list x.
1093 //! <b>Effects</b>: Transfers the value pointed by i, from list x to this list,
1094 //! before the the element pointed by p. No destructors or copy constructors are called.
1095 //! If p == i or p == ++i, this function is a null operation.
1097 //! <b>Throws</b>: std::runtime_error if this' allocator and x's allocator
1100 //! <b>Complexity</b>: Linear in distance(begin(), p), and in distance(x.begin(), i).
1102 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this
1103 //! list. Iterators of this list and all the references are not invalidated.
1104 void splice(const_iterator p, slist& x, const_iterator i)
1105 { this->splice_after(previous(p), x, i); }
1107 //! <b>Requires</b>: p must point to an element contained
1108 //! by this list. first and last must point to elements contained in list x.
1110 //! <b>Effects</b>: Transfers the range pointed by first and last from list x to this list,
1111 //! before the the element pointed by p. No destructors or copy constructors are called.
1113 //! <b>Throws</b>: std::runtime_error if this' allocator and x's allocator
1116 //! <b>Complexity</b>: Linear in distance(begin(), p), in distance(x.begin(), first),
1117 //! and in distance(first, last).
1119 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this
1120 //! list. Iterators of this list and all the references are not invalidated.
1121 void splice(const_iterator p, slist& x, const_iterator first, const_iterator last)
1122 { this->splice_after(previous(p), x, previous(first), previous(last)); }
1124 //! <b>Effects</b>: Reverses the order of elements in the list.
1126 //! <b>Throws</b>: Nothing.
1128 //! <b>Complexity</b>: This function is linear time.
1130 //! <b>Note</b>: Iterators and references are not invalidated
1132 { this->icont().reverse(); }
1134 //! <b>Effects</b>: Removes all the elements that compare equal to value.
1136 //! <b>Throws</b>: Nothing.
1138 //! <b>Complexity</b>: Linear time. It performs exactly size() comparisons for equality.
1140 //! <b>Note</b>: The relative order of elements that are not removed is unchanged,
1141 //! and iterators to elements that are not removed remain valid.
1142 void remove(const T& value)
1143 { remove_if(equal_to_value(value)); }
1145 //! <b>Effects</b>: Removes all the elements for which a specified
1146 //! predicate is satisfied.
1148 //! <b>Throws</b>: If pred throws.
1150 //! <b>Complexity</b>: Linear time. It performs exactly size() calls to the predicate.
1152 //! <b>Note</b>: The relative order of elements that are not removed is unchanged,
1153 //! and iterators to elements that are not removed remain valid.
1154 template <class Pred>
1155 void remove_if(Pred pred)
1157 typedef ValueCompareToNodeCompare<Pred> Predicate;
1158 this->icont().remove_and_dispose_if(Predicate(pred), Destroyer(this->node_alloc()));
1161 //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent
1162 //! elements that are equal from the list.
1164 //! <b>Throws</b>: Nothing.
1166 //! <b>Complexity</b>: Linear time (size()-1 comparisons calls to pred()).
1168 //! <b>Note</b>: The relative order of elements that are not removed is unchanged,
1169 //! and iterators to elements that are not removed remain valid.
1171 { this->unique(value_equal()); }
1173 //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent
1174 //! elements that satisfy some binary predicate from the list.
1176 //! <b>Throws</b>: If pred throws.
1178 //! <b>Complexity</b>: Linear time (size()-1 comparisons equality comparisons).
1180 //! <b>Note</b>: The relative order of elements that are not removed is unchanged,
1181 //! and iterators to elements that are not removed remain valid.
1182 template <class Pred>
1183 void unique(Pred pred)
1185 typedef ValueCompareToNodeCompare<Pred> Predicate;
1186 this->icont().unique_and_dispose(Predicate(pred), Destroyer(this->node_alloc()));
1189 //! <b>Requires</b>: The lists x and *this must be distinct.
1191 //! <b>Effects</b>: This function removes all of x's elements and inserts them
1192 //! in order into *this according to std::less<value_type>. The merge is stable;
1193 //! that is, if an element from *this is equivalent to one from x, then the element
1194 //! from *this will precede the one from x.
1196 //! <b>Throws</b>: Nothing.
1198 //! <b>Complexity</b>: This function is linear time: it performs at most
1199 //! size() + x.size() - 1 comparisons.
1200 void merge(slist & x)
1201 { this->merge(x, value_less()); }
1203 //! <b>Requires</b>: p must be a comparison function that induces a strict weak
1204 //! ordering and both *this and x must be sorted according to that ordering
1205 //! The lists x and *this must be distinct.
1207 //! <b>Effects</b>: This function removes all of x's elements and inserts them
1208 //! in order into *this. The merge is stable; that is, if an element from *this is
1209 //! equivalent to one from x, then the element from *this will precede the one from x.
1211 //! <b>Throws</b>: Nothing.
1213 //! <b>Complexity</b>: This function is linear time: it performs at most
1214 //! size() + x.size() - 1 comparisons.
1216 //! <b>Note</b>: Iterators and references to *this are not invalidated.
1217 template <class StrictWeakOrdering>
1218 void merge(slist& x, StrictWeakOrdering comp)
1220 if((NodeAlloc&)*this == (NodeAlloc&)x){
1221 this->icont().merge(x.icont(),
1222 ValueCompareToNodeCompare<StrictWeakOrdering>(comp));
1225 throw std::runtime_error("list::merge called with unequal allocators");
1229 //! <b>Effects</b>: This function sorts the list *this according to std::less<value_type>.
1230 //! The sort is stable, that is, the relative order of equivalent elements is preserved.
1232 //! <b>Throws</b>: Nothing.
1234 //! <b>Notes</b>: Iterators and references are not invalidated.
1236 //! <b>Complexity</b>: The number of comparisons is approximately N log N, where N
1237 //! is the list's size.
1239 { this->sort(value_less()); }
1241 //! <b>Effects</b>: This function sorts the list *this according to std::less<value_type>.
1242 //! The sort is stable, that is, the relative order of equivalent elements is preserved.
1244 //! <b>Throws</b>: Nothing.
1246 //! <b>Notes</b>: Iterators and references are not invalidated.
1248 //! <b>Complexity</b>: The number of comparisons is approximately N log N, where N
1249 //! is the list's size.
1250 template <class StrictWeakOrdering>
1251 void sort(StrictWeakOrdering comp)
1253 // nothing if the slist has length 0 or 1.
1254 if (this->size() < 2)
1256 this->icont().sort(ValueCompareToNodeCompare<StrictWeakOrdering>(comp));
1261 iterator priv_insert(const_iterator p, const value_type& x)
1262 { return this->insert_after(previous(p), x); }
1264 iterator priv_insert_after(const_iterator prev_pos, const value_type& x)
1265 { return iterator(this->icont().insert_after(prev_pos.get(), *this->create_node(x))); }
1267 void priv_push_front(const value_type &x)
1268 { this->icont().push_front(*this->create_node(x)); }
1270 //Iterator range version
1271 template<class InpIterator>
1272 void priv_create_and_insert_nodes
1273 (const_iterator prev, InpIterator beg, InpIterator end)
1275 typedef typename std::iterator_traits<InpIterator>::iterator_category ItCat;
1276 priv_create_and_insert_nodes(prev, beg, end, alloc_version(), ItCat());
1279 template<class InpIterator>
1280 void priv_create_and_insert_nodes
1281 (const_iterator prev, InpIterator beg, InpIterator end, allocator_v1, std::input_iterator_tag)
1283 for (; beg != end; ++beg){
1284 this->icont().insert_after(prev.get(), *this->create_node_from_it(beg));
1289 template<class InpIterator>
1290 void priv_create_and_insert_nodes
1291 (const_iterator prev, InpIterator beg, InpIterator end, allocator_v2, std::input_iterator_tag)
1292 { //Just forward to the default one
1293 priv_create_and_insert_nodes(prev, beg, end, allocator_v1(), std::input_iterator_tag());
1296 class insertion_functor;
1297 friend class insertion_functor;
1299 class insertion_functor
1302 typename Icont::const_iterator prev_;
1305 insertion_functor(Icont &icont, typename Icont::const_iterator prev)
1306 : icont_(icont), prev_(prev)
1309 void operator()(Node &n)
1310 { prev_ = this->icont_.insert_after(prev_, n); }
1313 template<class FwdIterator>
1314 void priv_create_and_insert_nodes
1315 (const_iterator prev, FwdIterator beg, FwdIterator end, allocator_v2, std::forward_iterator_tag)
1317 //Optimized allocation and construction
1318 this->allocate_many_and_construct
1319 (beg, std::distance(beg, end), insertion_functor(this->icont(), prev.get()));
1322 //Default constructed version
1323 void priv_create_and_insert_nodes(const_iterator prev, size_type n)
1325 typedef default_construct_iterator<value_type, difference_type> default_iterator;
1326 this->priv_create_and_insert_nodes(prev, default_iterator(n), default_iterator());
1329 //Copy constructed version
1330 void priv_create_and_insert_nodes(const_iterator prev, size_type n, const T& x)
1332 typedef constant_iterator<value_type, difference_type> cvalue_iterator;
1333 this->priv_create_and_insert_nodes(prev, cvalue_iterator(x, n), cvalue_iterator());
1336 //Dispatch to detect iterator range or integer overloads
1337 template <class InputIter>
1338 void priv_insert_dispatch(const_iterator prev,
1339 InputIter first, InputIter last,
1340 containers_detail::false_)
1341 { this->priv_create_and_insert_nodes(prev, first, last); }
1343 template<class Integer>
1344 void priv_insert_dispatch(const_iterator prev, Integer n, Integer x, containers_detail::true_)
1345 { this->priv_create_and_insert_nodes(prev, (size_type)n, x); }
1347 void priv_fill_assign(size_type n, const T& val)
1349 iterator end_n(this->end());
1350 iterator prev(this->before_begin());
1351 iterator node(this->begin());
1352 for ( ; node != end_n && n > 0 ; --n){
1358 this->priv_create_and_insert_nodes(prev, n, val);
1360 this->erase_after(prev, end_n);
1363 template <class Int>
1364 void priv_assign_dispatch(Int n, Int val, containers_detail::true_)
1365 { this->priv_fill_assign((size_type) n, (T)val); }
1367 template <class InpIt>
1368 void priv_assign_dispatch(InpIt first, InpIt last, containers_detail::false_)
1370 iterator end_n(this->end());
1371 iterator prev(this->before_begin());
1372 iterator node(this->begin());
1373 while (node != end_n && first != last){
1380 this->priv_create_and_insert_nodes(prev, first, last);
1382 this->erase_after(prev, end_n);
1385 template <class Int>
1386 void priv_insert_after_range_dispatch(const_iterator prev_pos, Int n, Int x, containers_detail::true_)
1387 { this->priv_create_and_insert_nodes(prev_pos, (size_type)n, x); }
1389 template <class InIter>
1390 void priv_insert_after_range_dispatch(const_iterator prev_pos, InIter first, InIter last, containers_detail::false_)
1391 { this->priv_create_and_insert_nodes(prev_pos, first, last); }
1393 //Functors for member algorithm defaults
1396 bool operator()(const value_type &a, const value_type &b) const
1402 bool operator()(const value_type &a, const value_type &b) const
1406 struct value_equal_to_this
1408 explicit value_equal_to_this(const value_type &ref)
1411 bool operator()(const value_type &val) const
1412 { return m_ref == val; }
1414 const value_type &m_ref;
1419 template <class T, class A>
1421 operator==(const slist<T,A>& x, const slist<T,A>& y)
1423 if(x.size() != y.size()){
1426 typedef typename slist<T,A>::const_iterator const_iterator;
1427 const_iterator end1 = x.end();
1429 const_iterator i1 = x.begin();
1430 const_iterator i2 = y.begin();
1431 while (i1 != end1 && *i1 == *i2){
1438 template <class T, class A>
1440 operator<(const slist<T,A>& sL1, const slist<T,A>& sL2)
1442 return std::lexicographical_compare
1443 (sL1.begin(), sL1.end(), sL2.begin(), sL2.end());
1446 template <class T, class A>
1448 operator!=(const slist<T,A>& sL1, const slist<T,A>& sL2)
1449 { return !(sL1 == sL2); }
1451 template <class T, class A>
1453 operator>(const slist<T,A>& sL1, const slist<T,A>& sL2)
1454 { return sL2 < sL1; }
1456 template <class T, class A>
1458 operator<=(const slist<T,A>& sL1, const slist<T,A>& sL2)
1459 { return !(sL2 < sL1); }
1461 template <class T, class A>
1463 operator>=(const slist<T,A>& sL1, const slist<T,A>& sL2)
1464 { return !(sL1 < sL2); }
1466 template <class T, class A>
1467 inline void swap(slist<T,A>& x, slist<T,A>& y)
1476 //!has_trivial_destructor_after_move<> == true_type
1477 //!specialization for optimizations
1478 template <class T, class A>
1479 struct has_trivial_destructor_after_move<boost::container::slist<T, A> >
1481 static const bool value = has_trivial_destructor<A>::value;
1484 namespace container {
1488 }} //namespace boost{ namespace container {
1490 // Specialization of insert_iterator so that insertions will be constant
1491 // time rather than linear time.
1495 //Ummm, I don't like to define things in namespace std, but
1496 //there is no other way
1499 template <class T, class A>
1500 class insert_iterator<boost::container::slist<T, A> >
1503 typedef boost::container::slist<T, A> Container;
1504 Container* container;
1505 typename Container::iterator iter;
1507 typedef Container container_type;
1508 typedef output_iterator_tag iterator_category;
1509 typedef void value_type;
1510 typedef void difference_type;
1511 typedef void pointer;
1512 typedef void reference;
1514 insert_iterator(Container& x,
1515 typename Container::iterator i,
1516 bool is_previous = false)
1517 : container(&x), iter(is_previous ? i : x.previous(i)){ }
1519 insert_iterator<Container>&
1520 operator=(const typename Container::value_type& value)
1522 iter = container->insert_after(iter, value);
1525 insert_iterator<Container>& operator*(){ return *this; }
1526 insert_iterator<Container>& operator++(){ return *this; }
1527 insert_iterator<Container>& operator++(int){ return *this; }
1534 #include <boost/container/detail/config_end.hpp>
1536 #endif /* BOOST_CONTAINERS_SLIST_HPP */