| ////////////////////////////////////////////////////////////////////////////// |
| // |
| // (C) Copyright Ion Gaztanaga 2004-2009. Distributed under the Boost |
| // Software License, Version 1.0. (See accompanying file |
| // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) |
| // |
| // See http://www.boost.org/libs/container for documentation. |
| // |
| ////////////////////////////////////////////////////////////////////////////// |
| |
| #ifndef BOOST_CONTAINERS_SLIST_HPP |
| #define BOOST_CONTAINERS_SLIST_HPP |
| |
| #if (defined _MSC_VER) && (_MSC_VER >= 1200) |
| # pragma once |
| #endif |
| |
| #include "detail/config_begin.hpp" |
| #include INCLUDE_BOOST_CONTAINER_DETAIL_WORKAROUND_HPP |
| |
| #include INCLUDE_BOOST_CONTAINER_CONTAINER_FWD_HPP |
| #include INCLUDE_BOOST_CONTAINER_MOVE_HPP |
| #include <boost/pointer_to_other.hpp> |
| #include INCLUDE_BOOST_CONTAINER_DETAIL_UTILITIES_HPP |
| #include INCLUDE_BOOST_CONTAINER_DETAIL_MPL_HPP |
| #include <boost/type_traits/has_trivial_destructor.hpp> |
| #include <boost/detail/no_exceptions_support.hpp> |
| #include INCLUDE_BOOST_CONTAINER_DETAIL_NODE_ALLOC_HOLDER_HPP |
| #include <boost/intrusive/slist.hpp> |
| |
| |
| #if defined(BOOST_CONTAINERS_PERFECT_FORWARDING) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) |
| //Preprocessor library to emulate perfect forwarding |
| #else |
| #include INCLUDE_BOOST_CONTAINER_DETAIL_PREPROCESSOR_HPP |
| #endif |
| |
| #include <stdexcept> |
| #include <iterator> |
| #include <utility> |
| #include <memory> |
| #include <functional> |
| #include <algorithm> |
| |
| #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED |
| namespace boost { |
| namespace container { |
| #else |
| namespace boost { |
| namespace container { |
| #endif |
| |
| /// @cond |
| |
| namespace containers_detail { |
| |
| template<class VoidPointer> |
| struct slist_hook |
| { |
| typedef typename containers_detail::bi::make_slist_base_hook |
| <containers_detail::bi::void_pointer<VoidPointer>, containers_detail::bi::link_mode<containers_detail::bi::normal_link> >::type type; |
| }; |
| |
| template <class T, class VoidPointer> |
| struct slist_node |
| : public slist_hook<VoidPointer>::type |
| { |
| #if defined(BOOST_CONTAINERS_PERFECT_FORWARDING) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) |
| |
| slist_node() |
| : m_data() |
| {} |
| |
| template<class ...Args> |
| slist_node(Args &&...args) |
| : m_data(BOOST_CONTAINER_MOVE_NAMESPACE::forward<Args>(args)...) |
| {} |
| |
| #else //#ifdef BOOST_CONTAINERS_PERFECT_FORWARDING |
| |
| slist_node() |
| : m_data() |
| {} |
| |
| #define BOOST_PP_LOCAL_MACRO(n) \ |
| template<BOOST_PP_ENUM_PARAMS(n, class P)> \ |
| slist_node(BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_LIST, _)) \ |
| : m_data(BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_FORWARD, _)) \ |
| {} \ |
| //! |
| #define BOOST_PP_LOCAL_LIMITS (1, BOOST_CONTAINERS_MAX_CONSTRUCTOR_PARAMETERS) |
| #include BOOST_PP_LOCAL_ITERATE() |
| |
| #endif//#ifdef BOOST_CONTAINERS_PERFECT_FORWARDING |
| |
| T m_data; |
| }; |
| |
| template<class A> |
| struct intrusive_slist_type |
| { |
| typedef typename A::value_type value_type; |
| typedef typename boost::pointer_to_other |
| <typename A::pointer, void>::type void_pointer; |
| typedef typename containers_detail::slist_node |
| <value_type, void_pointer> node_type; |
| |
| typedef typename containers_detail::bi::make_slist |
| <node_type |
| ,containers_detail::bi::base_hook<typename slist_hook<void_pointer>::type> |
| ,containers_detail::bi::constant_time_size<true> |
| ,containers_detail::bi::size_type<typename A::size_type> |
| >::type container_type; |
| typedef container_type type ; |
| }; |
| |
| } //namespace containers_detail { |
| |
| /// @endcond |
| |
| //! An slist is a singly linked list: a list where each element is linked to the next |
| //! element, but not to the previous element. That is, it is a Sequence that |
| //! supports forward but not backward traversal, and (amortized) constant time |
| //! insertion and removal of elements. Slists, like lists, have the important |
| //! property that insertion and splicing do not invalidate iterators to list elements, |
| //! and that even removal invalidates only the iterators that point to the elements |
| //! that are removed. The ordering of iterators may be changed (that is, |
| //! slist<T>::iterator might have a different predecessor or successor after a list |
| //! operation than it did before), but the iterators themselves will not be invalidated |
| //! or made to point to different elements unless that invalidation or mutation is explicit. |
| //! |
| //! The main difference between slist and list is that list's iterators are bidirectional |
| //! iterators, while slist's iterators are forward iterators. This means that slist is |
| //! less versatile than list; frequently, however, bidirectional iterators are |
| //! unnecessary. You should usually use slist unless you actually need the extra |
| //! functionality of list, because singly linked lists are smaller and faster than double |
| //! linked lists. |
| //! |
| //! Important performance note: like every other Sequence, slist defines the member |
| //! functions insert and erase. Using these member functions carelessly, however, can |
| //! result in disastrously slow programs. The problem is that insert's first argument is |
| //! an iterator p, and that it inserts the new element(s) before p. This means that |
| //! insert must find the iterator just before p; this is a constant-time operation |
| //! for list, since list has bidirectional iterators, but for slist it must find that |
| //! iterator by traversing the list from the beginning up to p. In other words: |
| //! insert and erase are slow operations anywhere but near the beginning of the slist. |
| //! |
| //! Slist provides the member functions insert_after and erase_after, which are constant |
| //! time operations: you should always use insert_after and erase_after whenever |
| //! possible. If you find that insert_after and erase_after aren't adequate for your |
| //! needs, and that you often need to use insert and erase in the middle of the list, |
| //! then you should probably use list instead of slist. |
| template <class T, class A> |
| class slist |
| : protected containers_detail::node_alloc_holder |
| <A, typename containers_detail::intrusive_slist_type<A>::type> |
| { |
| /// @cond |
| typedef typename containers_detail:: |
| move_const_ref_type<T>::type insert_const_ref_type; |
| typedef typename |
| containers_detail::intrusive_slist_type<A>::type Icont; |
| typedef containers_detail::node_alloc_holder<A, Icont> AllocHolder; |
| typedef typename AllocHolder::NodePtr NodePtr; |
| typedef slist <T, A> ThisType; |
| typedef typename AllocHolder::NodeAlloc NodeAlloc; |
| typedef typename AllocHolder::ValAlloc ValAlloc; |
| typedef typename AllocHolder::Node Node; |
| typedef containers_detail::allocator_destroyer<NodeAlloc> Destroyer; |
| typedef typename AllocHolder::allocator_v1 allocator_v1; |
| typedef typename AllocHolder::allocator_v2 allocator_v2; |
| typedef typename AllocHolder::alloc_version alloc_version; |
| |
| class equal_to_value |
| { |
| typedef typename AllocHolder::value_type value_type; |
| const value_type &t_; |
| |
| public: |
| equal_to_value(const value_type &t) |
| : t_(t) |
| {} |
| |
| bool operator()(const value_type &t)const |
| { return t_ == t; } |
| }; |
| |
| template<class Pred> |
| struct ValueCompareToNodeCompare |
| : Pred |
| { |
| ValueCompareToNodeCompare(Pred pred) |
| : Pred(pred) |
| {} |
| |
| bool operator()(const Node &a, const Node &b) const |
| { return static_cast<const Pred&>(*this)(a.m_data, b.m_data); } |
| |
| bool operator()(const Node &a) const |
| { return static_cast<const Pred&>(*this)(a.m_data); } |
| }; |
| /// @endcond |
| public: |
| //! The type of object, T, stored in the list |
| typedef T value_type; |
| //! Pointer to T |
| typedef typename A::pointer pointer; |
| //! Const pointer to T |
| typedef typename A::const_pointer const_pointer; |
| //! Reference to T |
| typedef typename A::reference reference; |
| //! Const reference to T |
| typedef typename A::const_reference const_reference; |
| //! An unsigned integral type |
| typedef typename A::size_type size_type; |
| //! A signed integral type |
| typedef typename A::difference_type difference_type; |
| //! The allocator type |
| typedef A allocator_type; |
| //! The stored allocator type |
| typedef NodeAlloc stored_allocator_type; |
| |
| /// @cond |
| private: |
| BOOST_MOVE_MACRO_COPYABLE_AND_MOVABLE(slist) |
| typedef difference_type list_difference_type; |
| typedef pointer list_pointer; |
| typedef const_pointer list_const_pointer; |
| typedef reference list_reference; |
| typedef const_reference list_const_reference; |
| /// @endcond |
| |
| public: |
| |
| //! Const iterator used to iterate through a list. |
| class const_iterator |
| /// @cond |
| : public std::iterator<std::forward_iterator_tag, |
| value_type, list_difference_type, |
| list_const_pointer, list_const_reference> |
| { |
| |
| protected: |
| typename Icont::iterator m_it; |
| explicit const_iterator(typename Icont::iterator it) : m_it(it){} |
| void prot_incr(){ ++m_it; } |
| |
| private: |
| typename Icont::iterator get() |
| { return this->m_it; } |
| |
| public: |
| friend class slist<T, A>; |
| typedef list_difference_type difference_type; |
| |
| //Constructors |
| const_iterator() |
| : m_it() |
| {} |
| |
| //Pointer like operators |
| const_reference operator*() const |
| { return m_it->m_data; } |
| |
| const_pointer operator->() const |
| { return const_pointer(&m_it->m_data); } |
| |
| //Increment / Decrement |
| const_iterator& operator++() |
| { prot_incr(); return *this; } |
| |
| const_iterator operator++(int) |
| { typename Icont::iterator tmp = m_it; ++*this; return const_iterator(tmp); } |
| |
| //Comparison operators |
| bool operator== (const const_iterator& r) const |
| { return m_it == r.m_it; } |
| |
| bool operator!= (const const_iterator& r) const |
| { return m_it != r.m_it; } |
| } |
| /// @endcond |
| ; |
| |
| //! Iterator used to iterate through a list |
| class iterator |
| /// @cond |
| : public const_iterator |
| { |
| |
| private: |
| explicit iterator(typename Icont::iterator it) |
| : const_iterator(it) |
| {} |
| |
| typename Icont::iterator get() |
| { return this->m_it; } |
| |
| public: |
| friend class slist<T, A>; |
| typedef list_pointer pointer; |
| typedef list_reference reference; |
| |
| //Constructors |
| iterator(){} |
| |
| //Pointer like operators |
| reference operator*() const { return this->m_it->m_data; } |
| pointer operator->() const { return pointer(&this->m_it->m_data); } |
| |
| //Increment / Decrement |
| iterator& operator++() |
| { this->prot_incr(); return *this; } |
| |
| iterator operator++(int) |
| { typename Icont::iterator tmp = this->m_it; ++*this; return iterator(tmp); } |
| } |
| /// @endcond |
| ; |
| |
| public: |
| //! <b>Effects</b>: Constructs a list taking the allocator as parameter. |
| //! |
| //! <b>Throws</b>: If allocator_type's copy constructor throws. |
| //! |
| //! <b>Complexity</b>: Constant. |
| explicit slist(const allocator_type& a = allocator_type()) |
| : AllocHolder(a) |
| {} |
| |
| explicit slist(size_type n) |
| : AllocHolder(allocator_type()) |
| { this->resize(n); } |
| |
| //! <b>Effects</b>: Constructs a list that will use a copy of allocator a |
| //! and inserts n copies of value. |
| //! |
| //! <b>Throws</b>: If allocator_type's default constructor or copy constructor |
| //! throws or T's default or copy constructor throws. |
| //! |
| //! <b>Complexity</b>: Linear to n. |
| explicit slist(size_type n, const value_type& x, const allocator_type& a = allocator_type()) |
| : AllocHolder(a) |
| { this->priv_create_and_insert_nodes(this->before_begin(), n, x); } |
| |
| //! <b>Effects</b>: Constructs a list that will use a copy of allocator a |
| //! and inserts a copy of the range [first, last) in the list. |
| //! |
| //! <b>Throws</b>: If allocator_type's default constructor or copy constructor |
| //! throws or T's constructor taking an dereferenced InIt throws. |
| //! |
| //! <b>Complexity</b>: Linear to the range [first, last). |
| template <class InpIt> |
| slist(InpIt first, InpIt last, |
| const allocator_type& a = allocator_type()) |
| : AllocHolder(a) |
| { this->insert_after(this->before_begin(), first, last); } |
| |
| //! <b>Effects</b>: Copy constructs a list. |
| //! |
| //! <b>Postcondition</b>: x == *this. |
| //! |
| //! <b>Throws</b>: If allocator_type's default constructor or copy constructor throws. |
| //! |
| //! <b>Complexity</b>: Linear to the elements x contains. |
| slist(const slist& x) |
| : AllocHolder(x) |
| { this->insert_after(this->before_begin(), x.begin(), x.end()); } |
| |
| //! <b>Effects</b>: Move constructor. Moves mx's resources to *this. |
| //! |
| //! <b>Throws</b>: If allocator_type's copy constructor throws. |
| //! |
| //! <b>Complexity</b>: Constant. |
| slist(BOOST_MOVE_MACRO_RV_REF(slist) x) |
| : AllocHolder(BOOST_CONTAINER_MOVE_NAMESPACE::move((AllocHolder&)x)) |
| {} |
| |
| //! <b>Effects</b>: Makes *this contain the same elements as x. |
| //! |
| //! <b>Postcondition</b>: this->size() == x.size(). *this contains a copy |
| //! of each of x's elements. |
| //! |
| //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws. |
| //! |
| //! <b>Complexity</b>: Linear to the number of elements in x. |
| slist& operator= (BOOST_MOVE_MACRO_COPY_ASSIGN_REF(slist) x) |
| { |
| if (&x != this){ |
| this->assign(x.begin(), x.end()); |
| } |
| return *this; |
| } |
| |
| //! <b>Effects</b>: Makes *this contain the same elements as x. |
| //! |
| //! <b>Postcondition</b>: this->size() == x.size(). *this contains a copy |
| //! of each of x's elements. |
| //! |
| //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws. |
| //! |
| //! <b>Complexity</b>: Linear to the number of elements in x. |
| slist& operator= (BOOST_MOVE_MACRO_RV_REF(slist) mx) |
| { |
| if (&mx != this){ |
| this->clear(); |
| this->swap(mx); |
| } |
| return *this; |
| } |
| |
| //! <b>Effects</b>: Destroys the list. All stored values are destroyed |
| //! and used memory is deallocated. |
| //! |
| //! <b>Throws</b>: Nothing. |
| //! |
| //! <b>Complexity</b>: Linear to the number of elements. |
| ~slist() |
| {} //AllocHolder clears the slist |
| |
| //! <b>Effects</b>: Returns a copy of the internal allocator. |
| //! |
| //! <b>Throws</b>: If allocator's copy constructor throws. |
| //! |
| //! <b>Complexity</b>: Constant. |
| allocator_type get_allocator() const |
| { return allocator_type(this->node_alloc()); } |
| |
| const stored_allocator_type &get_stored_allocator() const |
| { return this->node_alloc(); } |
| |
| stored_allocator_type &get_stored_allocator() |
| { return this->node_alloc(); } |
| |
| public: |
| |
| //! <b>Effects</b>: Assigns the n copies of val to *this. |
| //! |
| //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws. |
| //! |
| //! <b>Complexity</b>: Linear to n. |
| void assign(size_type n, const T& val) |
| { this->priv_fill_assign(n, val); } |
| |
| //! <b>Effects</b>: Assigns the range [first, last) to *this. |
| //! |
| //! <b>Throws</b>: If memory allocation throws or |
| //! T's constructor from dereferencing InpIt throws. |
| //! |
| //! <b>Complexity</b>: Linear to n. |
| template <class InpIt> |
| void assign(InpIt first, InpIt last) |
| { |
| const bool aux_boolean = containers_detail::is_convertible<InpIt, std::size_t>::value; |
| typedef containers_detail::bool_<aux_boolean> Result; |
| this->priv_assign_dispatch(first, last, Result()); |
| } |
| |
| //! <b>Effects</b>: Returns an iterator to the first element contained in the list. |
| //! |
| //! <b>Throws</b>: Nothing. |
| //! |
| //! <b>Complexity</b>: Constant. |
| iterator begin() |
| { return iterator(this->icont().begin()); } |
| |
| //! <b>Effects</b>: Returns a const_iterator to the first element contained in the list. |
| //! |
| //! <b>Throws</b>: Nothing. |
| //! |
| //! <b>Complexity</b>: Constant. |
| const_iterator begin() const |
| { return this->cbegin(); } |
| |
| //! <b>Effects</b>: Returns an iterator to the end of the list. |
| //! |
| //! <b>Throws</b>: Nothing. |
| //! |
| //! <b>Complexity</b>: Constant. |
| iterator end() |
| { return iterator(this->icont().end()); } |
| |
| //! <b>Effects</b>: Returns a const_iterator to the end of the list. |
| //! |
| //! <b>Throws</b>: Nothing. |
| //! |
| //! <b>Complexity</b>: Constant. |
| const_iterator end() const |
| { return this->cend(); } |
| |
| //! <b>Effects</b>: Returns a non-dereferenceable iterator that, |
| //! when incremented, yields begin(). This iterator may be used |
| //! as the argument toinsert_after, erase_after, etc. |
| //! |
| //! <b>Throws</b>: Nothing. |
| //! |
| //! <b>Complexity</b>: Constant. |
| iterator before_begin() |
| { return iterator(end()); } |
| |
| //! <b>Effects</b>: Returns a non-dereferenceable const_iterator |
| //! that, when incremented, yields begin(). This iterator may be used |
| //! as the argument toinsert_after, erase_after, etc. |
| //! |
| //! <b>Throws</b>: Nothing. |
| //! |
| //! <b>Complexity</b>: Constant. |
| const_iterator before_begin() const |
| { return this->cbefore_begin(); } |
| |
| //! <b>Effects</b>: Returns a const_iterator to the first element contained in the list. |
| //! |
| //! <b>Throws</b>: Nothing. |
| //! |
| //! <b>Complexity</b>: Constant. |
| const_iterator cbegin() const |
| { return const_iterator(this->non_const_icont().begin()); } |
| |
| //! <b>Effects</b>: Returns a const_iterator to the end of the list. |
| //! |
| //! <b>Throws</b>: Nothing. |
| //! |
| //! <b>Complexity</b>: Constant. |
| const_iterator cend() const |
| { return const_iterator(this->non_const_icont().end()); } |
| |
| //! <b>Effects</b>: Returns a non-dereferenceable const_iterator |
| //! that, when incremented, yields begin(). This iterator may be used |
| //! as the argument toinsert_after, erase_after, etc. |
| //! |
| //! <b>Throws</b>: Nothing. |
| //! |
| //! <b>Complexity</b>: Constant. |
| const_iterator cbefore_begin() const |
| { return const_iterator(end()); } |
| |
| //! <b>Effects</b>: Returns the number of the elements contained in the list. |
| //! |
| //! <b>Throws</b>: Nothing. |
| //! |
| //! <b>Complexity</b>: Constant. |
| size_type size() const |
| { return this->icont().size(); } |
| |
| //! <b>Effects</b>: Returns the largest possible size of the list. |
| //! |
| //! <b>Throws</b>: Nothing. |
| //! |
| //! <b>Complexity</b>: Constant. |
| size_type max_size() const |
| { return AllocHolder::max_size(); } |
| |
| //! <b>Effects</b>: Returns true if the list contains no elements. |
| //! |
| //! <b>Throws</b>: Nothing. |
| //! |
| //! <b>Complexity</b>: Constant. |
| bool empty() const |
| { return !this->size(); } |
| |
| //! <b>Effects</b>: Swaps the contents of *this and x. |
| //! If this->allocator_type() != x.allocator_type() |
| //! allocators are also swapped. |
| //! |
| //! <b>Throws</b>: Nothing. |
| //! |
| //! <b>Complexity</b>: Linear to the number of elements on *this and x. |
| void swap(slist& x) |
| { AllocHolder::swap(x); } |
| |
| //! <b>Requires</b>: !empty() |
| //! |
| //! <b>Effects</b>: Returns a reference to the first element |
| //! from the beginning of the container. |
| //! |
| //! <b>Throws</b>: Nothing. |
| //! |
| //! <b>Complexity</b>: Constant. |
| reference front() |
| { return *this->begin(); } |
| |
| //! <b>Requires</b>: !empty() |
| //! |
| //! <b>Effects</b>: Returns a const reference to the first element |
| //! from the beginning of the container. |
| //! |
| //! <b>Throws</b>: Nothing. |
| //! |
| //! <b>Complexity</b>: Constant. |
| const_reference front() const |
| { return *this->begin(); } |
| |
| //! <b>Effects</b>: Inserts a copy of t in the beginning of the list. |
| //! |
| //! <b>Throws</b>: If memory allocation throws or |
| //! T's copy constructor throws. |
| //! |
| //! <b>Complexity</b>: Amortized constant time. |
| void push_front(insert_const_ref_type x) |
| { return priv_push_front(x); } |
| |
| #if defined(BOOST_NO_RVALUE_REFERENCES) && !defined(BOOST_MOVE_DOXYGEN_INVOKED) |
| void push_front(T &x) { push_front(const_cast<const T &>(x)); } |
| |
| template<class U> |
| void push_front(const U &u, typename containers_detail::enable_if_c<containers_detail::is_same<T, U>::value && !::BOOST_CONTAINER_MOVE_NAMESPACE::is_movable<U>::value >::type* =0) |
| { return priv_push_front(u); } |
| #endif |
| |
| //! <b>Effects</b>: Constructs a new element in the beginning of the list |
| //! and moves the resources of t to this new element. |
| //! |
| //! <b>Throws</b>: If memory allocation throws. |
| //! |
| //! <b>Complexity</b>: Amortized constant time. |
| void push_front(BOOST_MOVE_MACRO_RV_REF(T) x) |
| { this->icont().push_front(*this->create_node(BOOST_CONTAINER_MOVE_NAMESPACE::move(x))); } |
| |
| //! <b>Effects</b>: Removes the first element from the list. |
| //! |
| //! <b>Throws</b>: Nothing. |
| //! |
| //! <b>Complexity</b>: Amortized constant time. |
| void pop_front() |
| { this->icont().pop_front_and_dispose(Destroyer(this->node_alloc())); } |
| |
| //! <b>Returns</b>: The iterator to the element before i in the sequence. |
| //! Returns the end-iterator, if either i is the begin-iterator or the |
| //! sequence is empty. |
| //! |
| //! <b>Throws</b>: Nothing. |
| //! |
| //! <b>Complexity</b>: Linear to the number of elements before i. |
| iterator previous(iterator p) |
| { return iterator(this->icont().previous(p.get())); } |
| |
| //! <b>Returns</b>: The const_iterator to the element before i in the sequence. |
| //! Returns the end-const_iterator, if either i is the begin-const_iterator or |
| //! the sequence is empty. |
| //! |
| //! <b>Throws</b>: Nothing. |
| //! |
| //! <b>Complexity</b>: Linear to the number of elements before i. |
| const_iterator previous(const_iterator p) |
| { return const_iterator(this->icont().previous(p.get())); } |
| |
| //! <b>Requires</b>: p must be a valid iterator of *this. |
| //! |
| //! <b>Effects</b>: Inserts a copy of the value after the p pointed |
| //! by prev_p. |
| //! |
| //! <b>Returns</b>: An iterator to the inserted element. |
| //! |
| //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws. |
| //! |
| //! <b>Complexity</b>: Amortized constant time. |
| //! |
| //! <b>Note</b>: Does not affect the validity of iterators and references of |
| //! previous values. |
| iterator insert_after(const_iterator prev_pos, insert_const_ref_type x) |
| { return this->priv_insert_after(prev_pos, x); } |
| |
| #if defined(BOOST_NO_RVALUE_REFERENCES) && !defined(BOOST_MOVE_DOXYGEN_INVOKED) |
| iterator insert_after(const_iterator position, T &x) |
| { return this->insert_after(position, const_cast<const T &>(x)); } |
| |
| template<class U> |
| iterator insert_after(const_iterator position, const U &u, typename containers_detail::enable_if_c<containers_detail::is_same<T, U>::value && !::BOOST_CONTAINER_MOVE_NAMESPACE::is_movable<U>::value >::type* =0) |
| { return this->priv_insert_after(position, u); } |
| #endif |
| |
| //! <b>Requires</b>: prev_pos must be a valid iterator of *this. |
| //! |
| //! <b>Effects</b>: Inserts a move constructed copy object from the value after the |
| //! p pointed by prev_pos. |
| //! |
| //! <b>Returns</b>: An iterator to the inserted element. |
| //! |
| //! <b>Throws</b>: If memory allocation throws. |
| //! |
| //! <b>Complexity</b>: Amortized constant time. |
| //! |
| //! <b>Note</b>: Does not affect the validity of iterators and references of |
| //! previous values. |
| iterator insert_after(const_iterator prev_pos, BOOST_MOVE_MACRO_RV_REF(value_type) x) |
| { return iterator(this->icont().insert_after(prev_pos.get(), *this->create_node(BOOST_CONTAINER_MOVE_NAMESPACE::move(x)))); } |
| |
| //! <b>Requires</b>: prev_pos must be a valid iterator of *this. |
| //! |
| //! <b>Effects</b>: Inserts n copies of x after prev_pos. |
| //! |
| //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws. |
| //! |
| //! <b>Complexity</b>: Linear to n. |
| //! |
| //! <b>Note</b>: Does not affect the validity of iterators and references of |
| //! previous values. |
| void insert_after(const_iterator prev_pos, size_type n, const value_type& x) |
| { this->priv_create_and_insert_nodes(prev_pos, n, x); } |
| |
| //! <b>Requires</b>: prev_pos must be a valid iterator of *this. |
| //! |
| //! <b>Effects</b>: Inserts the range pointed by [first, last) |
| //! after the p prev_pos. |
| //! |
| //! <b>Throws</b>: If memory allocation throws, T's constructor from a |
| //! dereferenced InpIt throws. |
| //! |
| //! <b>Complexity</b>: Linear to the number of elements inserted. |
| //! |
| //! <b>Note</b>: Does not affect the validity of iterators and references of |
| //! previous values. |
| template <class InIter> |
| void insert_after(const_iterator prev_pos, InIter first, InIter last) |
| { |
| const bool aux_boolean = containers_detail::is_convertible<InIter, std::size_t>::value; |
| typedef containers_detail::bool_<aux_boolean> Result; |
| this->priv_insert_after_range_dispatch(prev_pos, first, last, Result()); |
| } |
| |
| //! <b>Requires</b>: p must be a valid iterator of *this. |
| //! |
| //! <b>Effects</b>: Insert a copy of x before p. |
| //! |
| //! <b>Throws</b>: If memory allocation throws or x's copy constructor throws. |
| //! |
| //! <b>Complexity</b>: Linear to the elements before p. |
| iterator insert(const_iterator position, insert_const_ref_type x) |
| { return this->priv_insert(position, x); } |
| |
| #if defined(BOOST_NO_RVALUE_REFERENCES) && !defined(BOOST_MOVE_DOXYGEN_INVOKED) |
| iterator insert(const_iterator position, T &x) |
| { return this->insert(position, const_cast<const T &>(x)); } |
| |
| template<class U> |
| iterator insert(const_iterator position, const U &u, typename containers_detail::enable_if_c<containers_detail::is_same<T, U>::value && !::BOOST_CONTAINER_MOVE_NAMESPACE::is_movable<U>::value >::type* =0) |
| { return this->priv_insert(position, u); } |
| #endif |
| |
| //! <b>Requires</b>: p must be a valid iterator of *this. |
| //! |
| //! <b>Effects</b>: Insert a new element before p with mx's resources. |
| //! |
| //! <b>Throws</b>: If memory allocation throws. |
| //! |
| //! <b>Complexity</b>: Linear to the elements before p. |
| iterator insert(const_iterator p, BOOST_MOVE_MACRO_RV_REF(value_type) x) |
| { return this->insert_after(previous(p), BOOST_CONTAINER_MOVE_NAMESPACE::move(x)); } |
| |
| //! <b>Requires</b>: p must be a valid iterator of *this. |
| //! |
| //! <b>Effects</b>: Inserts n copies of x before p. |
| //! |
| //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws. |
| //! |
| //! <b>Complexity</b>: Linear to n plus linear to the elements before p. |
| void insert(const_iterator p, size_type n, const value_type& x) |
| { return this->insert_after(previous(p), n, x); } |
| |
| //! <b>Requires</b>: p must be a valid iterator of *this. |
| //! |
| //! <b>Effects</b>: Insert a copy of the [first, last) range before p. |
| //! |
| //! <b>Throws</b>: If memory allocation throws, T's constructor from a |
| //! dereferenced InpIt throws. |
| //! |
| //! <b>Complexity</b>: Linear to std::distance [first, last) plus |
| //! linear to the elements before p. |
| template <class InIter> |
| void insert(const_iterator p, InIter first, InIter last) |
| { return this->insert_after(previous(p), first, last); } |
| |
| #if defined(BOOST_CONTAINERS_PERFECT_FORWARDING) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) |
| |
| //! <b>Effects</b>: Inserts an object of type T constructed with |
| //! std::forward<Args>(args)... in the front of the list |
| //! |
| //! <b>Throws</b>: If memory allocation throws or |
| //! T's copy constructor throws. |
| //! |
| //! <b>Complexity</b>: Amortized constant time. |
| template <class... Args> |
| void emplace_front(Args&&... args) |
| { this->emplace_after(this->cbefore_begin(), BOOST_CONTAINER_MOVE_NAMESPACE::forward<Args>(args)...); } |
| |
| //! <b>Effects</b>: Inserts an object of type T constructed with |
| //! std::forward<Args>(args)... before p |
| //! |
| //! <b>Throws</b>: If memory allocation throws or |
| //! T's in-place constructor throws. |
| //! |
| //! <b>Complexity</b>: Linear to the elements before p |
| template <class... Args> |
| iterator emplace(const_iterator p, Args&&... args) |
| { return this->emplace_after(this->previous(p), BOOST_CONTAINER_MOVE_NAMESPACE::forward<Args>(args)...); } |
| |
| //! <b>Effects</b>: Inserts an object of type T constructed with |
| //! std::forward<Args>(args)... after prev |
| //! |
| //! <b>Throws</b>: If memory allocation throws or |
| //! T's in-place constructor throws. |
| //! |
| //! <b>Complexity</b>: Constant |
| template <class... Args> |
| iterator emplace_after(const_iterator prev, Args&&... args) |
| { |
| typename AllocHolder::Deallocator d(AllocHolder::create_node_and_deallocator()); |
| new ((void*)containers_detail::get_pointer(d.get())) Node(BOOST_CONTAINER_MOVE_NAMESPACE::forward<Args>(args)...); |
| NodePtr node = d.get(); |
| d.release(); |
| return iterator(this->icont().insert_after(prev.get(), *node)); |
| } |
| |
| #else //#ifdef BOOST_CONTAINERS_PERFECT_FORWARDING |
| |
| //0 args |
| void emplace_front() |
| { this->emplace_after(this->cbefore_begin()); } |
| |
| iterator emplace(const_iterator p) |
| { return this->emplace_after(this->previous(p)); } |
| |
| iterator emplace_after(const_iterator prev) |
| { |
| typename AllocHolder::Deallocator d(AllocHolder::create_node_and_deallocator()); |
| new ((void*)containers_detail::get_pointer(d.get())) Node(); |
| NodePtr node = d.get(); |
| d.release(); |
| return iterator(this->icont().insert_after(prev.get(), *node)); |
| } |
| |
| #define BOOST_PP_LOCAL_MACRO(n) \ |
| template<BOOST_PP_ENUM_PARAMS(n, class P)> \ |
| void emplace_front(BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_LIST, _)) \ |
| { \ |
| this->emplace \ |
| (this->cbegin(), BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_FORWARD, _)); \ |
| } \ |
| \ |
| template<BOOST_PP_ENUM_PARAMS(n, class P)> \ |
| iterator emplace \ |
| (const_iterator p, BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_LIST, _)) \ |
| { \ |
| return this->emplace_after \ |
| (this->previous(p), BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_FORWARD, _)); \ |
| } \ |
| \ |
| template<BOOST_PP_ENUM_PARAMS(n, class P)> \ |
| iterator emplace_after \ |
| (const_iterator prev, BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_LIST, _)) \ |
| { \ |
| typename AllocHolder::Deallocator d(AllocHolder::create_node_and_deallocator()); \ |
| new ((void*)containers_detail::get_pointer(d.get())) \ |
| Node(BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_FORWARD, _)); \ |
| NodePtr node = d.get(); \ |
| d.release(); \ |
| return iterator(this->icont().insert_after(prev.get(), *node)); \ |
| } \ |
| //! |
| #define BOOST_PP_LOCAL_LIMITS (1, BOOST_CONTAINERS_MAX_CONSTRUCTOR_PARAMETERS) |
| #include BOOST_PP_LOCAL_ITERATE() |
| |
| #endif //#ifdef BOOST_CONTAINERS_PERFECT_FORWARDING |
| |
| //! <b>Effects</b>: Erases the element after the element pointed by prev_pos |
| //! of the list. |
| //! |
| //! <b>Returns</b>: the first element remaining beyond the removed elements, |
| //! or end() if no such element exists. |
| //! |
| //! <b>Throws</b>: Nothing. |
| //! |
| //! <b>Complexity</b>: Constant. |
| //! |
| //! <b>Note</b>: Does not invalidate iterators or references to non erased elements. |
| iterator erase_after(const_iterator prev_pos) |
| { |
| return iterator(this->icont().erase_after_and_dispose(prev_pos.get(), Destroyer(this->node_alloc()))); |
| } |
| |
| //! <b>Effects</b>: Erases the range (before_first, last) from |
| //! the list. |
| //! |
| //! <b>Returns</b>: the first element remaining beyond the removed elements, |
| //! or end() if no such element exists. |
| //! |
| //! <b>Throws</b>: Nothing. |
| //! |
| //! <b>Complexity</b>: Linear to the number of erased elements. |
| //! |
| //! <b>Note</b>: Does not invalidate iterators or references to non erased elements. |
| iterator erase_after(const_iterator before_first, const_iterator last) |
| { |
| return iterator(this->icont().erase_after_and_dispose(before_first.get(), last.get(), Destroyer(this->node_alloc()))); |
| } |
| |
| //! <b>Requires</b>: p must be a valid iterator of *this. |
| //! |
| //! <b>Effects</b>: Erases the element at p p. |
| //! |
| //! <b>Throws</b>: Nothing. |
| //! |
| //! <b>Complexity</b>: Linear to the number of elements before p. |
| iterator erase(const_iterator p) |
| { return iterator(this->erase_after(previous(p))); } |
| |
| //! <b>Requires</b>: first and last must be valid iterator to elements in *this. |
| //! |
| //! <b>Effects</b>: Erases the elements pointed by [first, last). |
| //! |
| //! <b>Throws</b>: Nothing. |
| //! |
| //! <b>Complexity</b>: Linear to the distance between first and last plus |
| //! linear to the elements before first. |
| iterator erase(const_iterator first, const_iterator last) |
| { return iterator(this->erase_after(previous(first), last)); } |
| |
| //! <b>Effects</b>: Inserts or erases elements at the end such that |
| //! the size becomes n. New elements are copy constructed from x. |
| //! |
| //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws. |
| //! |
| //! <b>Complexity</b>: Linear to the difference between size() and new_size. |
| void resize(size_type new_size, const T& x) |
| { |
| typename Icont::iterator end_n(this->icont().end()), cur(this->icont().before_begin()), cur_next; |
| while (++(cur_next = cur) != end_n && new_size > 0){ |
| --new_size; |
| cur = cur_next; |
| } |
| if (cur_next != end_n) |
| this->erase_after(const_iterator(cur), const_iterator(end_n)); |
| else |
| this->insert_after(const_iterator(cur), new_size, x); |
| } |
| |
| //! <b>Effects</b>: Inserts or erases elements at the end such that |
| //! the size becomes n. New elements are default constructed. |
| //! |
| //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws. |
| //! |
| //! <b>Complexity</b>: Linear to the difference between size() and new_size. |
| void resize(size_type new_size) |
| { |
| typename Icont::iterator end_n(this->icont().end()), cur(this->icont().before_begin()), cur_next; |
| size_type len = this->size(); |
| size_type left = new_size; |
| |
| while (++(cur_next = cur) != end_n && left > 0){ |
| --left; |
| cur = cur_next; |
| } |
| if (cur_next != end_n){ |
| this->erase_after(const_iterator(cur), const_iterator(end_n)); |
| } |
| else{ |
| this->priv_create_and_insert_nodes(const_iterator(cur), new_size - len); |
| } |
| } |
| |
| //! <b>Effects</b>: Erases all the elements of the list. |
| //! |
| //! <b>Throws</b>: Nothing. |
| //! |
| //! <b>Complexity</b>: Linear to the number of elements in the list. |
| void clear() |
| { this->icont().clear_and_dispose(Destroyer(this->node_alloc())); } |
| |
| //! <b>Requires</b>: p must point to an element contained |
| //! by the list. x != *this |
| //! |
| //! <b>Effects</b>: Transfers all the elements of list x to this list, after the |
| //! the element pointed by p. No destructors or copy constructors are called. |
| //! |
| //! <b>Throws</b>: std::runtime_error if this' allocator and x's allocator |
| //! are not equal. |
| //! |
| //! <b>Complexity</b>: Linear to the elements in x. |
| //! |
| //! <b>Note</b>: Iterators of values obtained from list x now point to elements of |
| //! this list. Iterators of this list and all the references are not invalidated. |
| void splice_after(const_iterator prev_pos, slist& x) |
| { |
| if((NodeAlloc&)*this == (NodeAlloc&)x){ |
| this->icont().splice_after(prev_pos.get(), x.icont()); |
| } |
| else{ |
| throw std::runtime_error("slist::splice called with unequal allocators"); |
| } |
| } |
| |
| //! <b>Requires</b>: prev_pos must be a valid iterator of this. |
| //! i must point to an element contained in list x. |
| //! |
| //! <b>Effects</b>: Transfers the value pointed by i, from list x to this list, |
| //! after the element pointed by prev_pos. |
| //! If prev_pos == prev or prev_pos == ++prev, this function is a null operation. |
| //! |
| //! <b>Throws</b>: std::runtime_error if this' allocator and x's allocator |
| //! are not equal. |
| //! |
| //! <b>Complexity</b>: Constant. |
| //! |
| //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this |
| //! list. Iterators of this list and all the references are not invalidated. |
| void splice_after(const_iterator prev_pos, slist& x, const_iterator prev) |
| { |
| if((NodeAlloc&)*this == (NodeAlloc&)x){ |
| this->icont().splice_after(prev_pos.get(), x.icont(), prev.get()); |
| } |
| else{ |
| throw std::runtime_error("slist::splice called with unequal allocators"); |
| } |
| } |
| |
| //! <b>Requires</b>: prev_pos must be a valid iterator of this. |
| //! before_first and before_last must be valid iterators of x. |
| //! prev_pos must not be contained in [before_first, before_last) range. |
| //! |
| //! <b>Effects</b>: Transfers the range [before_first + 1, before_last + 1) |
| //! from list x to this list, after the element pointed by prev_pos. |
| //! |
| //! <b>Throws</b>: std::runtime_error if this' allocator and x's allocator |
| //! are not equal. |
| //! |
| //! <b>Complexity</b>: Linear to the number of transferred elements. |
| //! |
| //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this |
| //! list. Iterators of this list and all the references are not invalidated. |
| void splice_after(const_iterator prev_pos, slist& x, |
| const_iterator before_first, const_iterator before_last) |
| { |
| if((NodeAlloc&)*this == (NodeAlloc&)x){ |
| this->icont().splice_after |
| (prev_pos.get(), x.icont(), before_first.get(), before_last.get()); |
| } |
| else{ |
| throw std::runtime_error("slist::splice called with unequal allocators"); |
| } |
| } |
| |
| //! <b>Requires</b>: prev_pos must be a valid iterator of this. |
| //! before_first and before_last must be valid iterators of x. |
| //! prev_pos must not be contained in [before_first, before_last) range. |
| //! n == std::distance(before_first, before_last) |
| //! |
| //! <b>Effects</b>: Transfers the range [before_first + 1, before_last + 1) |
| //! from list x to this list, after the element pointed by prev_pos. |
| //! |
| //! <b>Throws</b>: std::runtime_error if this' allocator and x's allocator |
| //! are not equal. |
| //! |
| //! <b>Complexity</b>: Constant. |
| //! |
| //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this |
| //! list. Iterators of this list and all the references are not invalidated. |
| void splice_after(const_iterator prev_pos, slist& x, |
| const_iterator before_first, const_iterator before_last, |
| size_type n) |
| { |
| if((NodeAlloc&)*this == (NodeAlloc&)x){ |
| this->icont().splice_after |
| (prev_pos.get(), x.icont(), before_first.get(), before_last.get(), n); |
| } |
| else{ |
| throw std::runtime_error("slist::splice called with unequal allocators"); |
| } |
| } |
| |
| //! <b>Requires</b>: p must point to an element contained |
| //! by the list. x != *this |
| //! |
| //! <b>Effects</b>: Transfers all the elements of list x to this list, before the |
| //! the element pointed by p. No destructors or copy constructors are called. |
| //! |
| //! <b>Throws</b>: std::runtime_error if this' allocator and x's allocator |
| //! are not equal. |
| //! |
| //! <b>Complexity</b>: Linear in distance(begin(), p), and linear in x.size(). |
| //! |
| //! <b>Note</b>: Iterators of values obtained from list x now point to elements of |
| //! this list. Iterators of this list and all the references are not invalidated. |
| void splice(const_iterator p, ThisType& x) |
| { this->splice_after(this->previous(p), x); } |
| |
| //! <b>Requires</b>: p must point to an element contained |
| //! by this list. i must point to an element contained in list x. |
| //! |
| //! <b>Effects</b>: Transfers the value pointed by i, from list x to this list, |
| //! before the the element pointed by p. No destructors or copy constructors are called. |
| //! If p == i or p == ++i, this function is a null operation. |
| //! |
| //! <b>Throws</b>: std::runtime_error if this' allocator and x's allocator |
| //! are not equal. |
| //! |
| //! <b>Complexity</b>: Linear in distance(begin(), p), and in distance(x.begin(), i). |
| //! |
| //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this |
| //! list. Iterators of this list and all the references are not invalidated. |
| void splice(const_iterator p, slist& x, const_iterator i) |
| { this->splice_after(previous(p), x, i); } |
| |
| //! <b>Requires</b>: p must point to an element contained |
| //! by this list. first and last must point to elements contained in list x. |
| //! |
| //! <b>Effects</b>: Transfers the range pointed by first and last from list x to this list, |
| //! before the the element pointed by p. No destructors or copy constructors are called. |
| //! |
| //! <b>Throws</b>: std::runtime_error if this' allocator and x's allocator |
| //! are not equal. |
| //! |
| //! <b>Complexity</b>: Linear in distance(begin(), p), in distance(x.begin(), first), |
| //! and in distance(first, last). |
| //! |
| //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this |
| //! list. Iterators of this list and all the references are not invalidated. |
| void splice(const_iterator p, slist& x, const_iterator first, const_iterator last) |
| { this->splice_after(previous(p), x, previous(first), previous(last)); } |
| |
| //! <b>Effects</b>: Reverses the order of elements in the list. |
| //! |
| //! <b>Throws</b>: Nothing. |
| //! |
| //! <b>Complexity</b>: This function is linear time. |
| //! |
| //! <b>Note</b>: Iterators and references are not invalidated |
| void reverse() |
| { this->icont().reverse(); } |
| |
| //! <b>Effects</b>: Removes all the elements that compare equal to value. |
| //! |
| //! <b>Throws</b>: Nothing. |
| //! |
| //! <b>Complexity</b>: Linear time. It performs exactly size() comparisons for equality. |
| //! |
| //! <b>Note</b>: The relative order of elements that are not removed is unchanged, |
| //! and iterators to elements that are not removed remain valid. |
| void remove(const T& value) |
| { remove_if(equal_to_value(value)); } |
| |
| //! <b>Effects</b>: Removes all the elements for which a specified |
| //! predicate is satisfied. |
| //! |
| //! <b>Throws</b>: If pred throws. |
| //! |
| //! <b>Complexity</b>: Linear time. It performs exactly size() calls to the predicate. |
| //! |
| //! <b>Note</b>: The relative order of elements that are not removed is unchanged, |
| //! and iterators to elements that are not removed remain valid. |
| template <class Pred> |
| void remove_if(Pred pred) |
| { |
| typedef ValueCompareToNodeCompare<Pred> Predicate; |
| this->icont().remove_and_dispose_if(Predicate(pred), Destroyer(this->node_alloc())); |
| } |
| |
| //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent |
| //! elements that are equal from the list. |
| //! |
| //! <b>Throws</b>: Nothing. |
| //! |
| //! <b>Complexity</b>: Linear time (size()-1 comparisons calls to pred()). |
| //! |
| //! <b>Note</b>: The relative order of elements that are not removed is unchanged, |
| //! and iterators to elements that are not removed remain valid. |
| void unique() |
| { this->unique(value_equal()); } |
| |
| //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent |
| //! elements that satisfy some binary predicate from the list. |
| //! |
| //! <b>Throws</b>: If pred throws. |
| //! |
| //! <b>Complexity</b>: Linear time (size()-1 comparisons equality comparisons). |
| //! |
| //! <b>Note</b>: The relative order of elements that are not removed is unchanged, |
| //! and iterators to elements that are not removed remain valid. |
| template <class Pred> |
| void unique(Pred pred) |
| { |
| typedef ValueCompareToNodeCompare<Pred> Predicate; |
| this->icont().unique_and_dispose(Predicate(pred), Destroyer(this->node_alloc())); |
| } |
| |
| //! <b>Requires</b>: The lists x and *this must be distinct. |
| //! |
| //! <b>Effects</b>: This function removes all of x's elements and inserts them |
| //! in order into *this according to std::less<value_type>. The merge is stable; |
| //! that is, if an element from *this is equivalent to one from x, then the element |
| //! from *this will precede the one from x. |
| //! |
| //! <b>Throws</b>: Nothing. |
| //! |
| //! <b>Complexity</b>: This function is linear time: it performs at most |
| //! size() + x.size() - 1 comparisons. |
| void merge(slist & x) |
| { this->merge(x, value_less()); } |
| |
| //! <b>Requires</b>: p must be a comparison function that induces a strict weak |
| //! ordering and both *this and x must be sorted according to that ordering |
| //! The lists x and *this must be distinct. |
| //! |
| //! <b>Effects</b>: This function removes all of x's elements and inserts them |
| //! in order into *this. The merge is stable; that is, if an element from *this is |
| //! equivalent to one from x, then the element from *this will precede the one from x. |
| //! |
| //! <b>Throws</b>: Nothing. |
| //! |
| //! <b>Complexity</b>: This function is linear time: it performs at most |
| //! size() + x.size() - 1 comparisons. |
| //! |
| //! <b>Note</b>: Iterators and references to *this are not invalidated. |
| template <class StrictWeakOrdering> |
| void merge(slist& x, StrictWeakOrdering comp) |
| { |
| if((NodeAlloc&)*this == (NodeAlloc&)x){ |
| this->icont().merge(x.icont(), |
| ValueCompareToNodeCompare<StrictWeakOrdering>(comp)); |
| } |
| else{ |
| throw std::runtime_error("list::merge called with unequal allocators"); |
| } |
| } |
| |
| //! <b>Effects</b>: This function sorts the list *this according to std::less<value_type>. |
| //! The sort is stable, that is, the relative order of equivalent elements is preserved. |
| //! |
| //! <b>Throws</b>: Nothing. |
| //! |
| //! <b>Notes</b>: Iterators and references are not invalidated. |
| //! |
| //! <b>Complexity</b>: The number of comparisons is approximately N log N, where N |
| //! is the list's size. |
| void sort() |
| { this->sort(value_less()); } |
| |
| //! <b>Effects</b>: This function sorts the list *this according to std::less<value_type>. |
| //! The sort is stable, that is, the relative order of equivalent elements is preserved. |
| //! |
| //! <b>Throws</b>: Nothing. |
| //! |
| //! <b>Notes</b>: Iterators and references are not invalidated. |
| //! |
| //! <b>Complexity</b>: The number of comparisons is approximately N log N, where N |
| //! is the list's size. |
| template <class StrictWeakOrdering> |
| void sort(StrictWeakOrdering comp) |
| { |
| // nothing if the slist has length 0 or 1. |
| if (this->size() < 2) |
| return; |
| this->icont().sort(ValueCompareToNodeCompare<StrictWeakOrdering>(comp)); |
| } |
| |
| /// @cond |
| private: |
| iterator priv_insert(const_iterator p, const value_type& x) |
| { return this->insert_after(previous(p), x); } |
| |
| iterator priv_insert_after(const_iterator prev_pos, const value_type& x) |
| { return iterator(this->icont().insert_after(prev_pos.get(), *this->create_node(x))); } |
| |
| void priv_push_front(const value_type &x) |
| { this->icont().push_front(*this->create_node(x)); } |
| |
| //Iterator range version |
| template<class InpIterator> |
| void priv_create_and_insert_nodes |
| (const_iterator prev, InpIterator beg, InpIterator end) |
| { |
| typedef typename std::iterator_traits<InpIterator>::iterator_category ItCat; |
| priv_create_and_insert_nodes(prev, beg, end, alloc_version(), ItCat()); |
| } |
| |
| template<class InpIterator> |
| void priv_create_and_insert_nodes |
| (const_iterator prev, InpIterator beg, InpIterator end, allocator_v1, std::input_iterator_tag) |
| { |
| for (; beg != end; ++beg){ |
| this->icont().insert_after(prev.get(), *this->create_node_from_it(beg)); |
| ++prev; |
| } |
| } |
| |
| template<class InpIterator> |
| void priv_create_and_insert_nodes |
| (const_iterator prev, InpIterator beg, InpIterator end, allocator_v2, std::input_iterator_tag) |
| { //Just forward to the default one |
| priv_create_and_insert_nodes(prev, beg, end, allocator_v1(), std::input_iterator_tag()); |
| } |
| |
| class insertion_functor; |
| friend class insertion_functor; |
| |
| class insertion_functor |
| { |
| Icont &icont_; |
| typename Icont::const_iterator prev_; |
| |
| public: |
| insertion_functor(Icont &icont, typename Icont::const_iterator prev) |
| : icont_(icont), prev_(prev) |
| {} |
| |
| void operator()(Node &n) |
| { prev_ = this->icont_.insert_after(prev_, n); } |
| }; |
| |
| template<class FwdIterator> |
| void priv_create_and_insert_nodes |
| (const_iterator prev, FwdIterator beg, FwdIterator end, allocator_v2, std::forward_iterator_tag) |
| { |
| //Optimized allocation and construction |
| this->allocate_many_and_construct |
| (beg, std::distance(beg, end), insertion_functor(this->icont(), prev.get())); |
| } |
| |
| //Default constructed version |
| void priv_create_and_insert_nodes(const_iterator prev, size_type n) |
| { |
| typedef default_construct_iterator<value_type, difference_type> default_iterator; |
| this->priv_create_and_insert_nodes(prev, default_iterator(n), default_iterator()); |
| } |
| |
| //Copy constructed version |
| void priv_create_and_insert_nodes(const_iterator prev, size_type n, const T& x) |
| { |
| typedef constant_iterator<value_type, difference_type> cvalue_iterator; |
| this->priv_create_and_insert_nodes(prev, cvalue_iterator(x, n), cvalue_iterator()); |
| } |
| |
| //Dispatch to detect iterator range or integer overloads |
| template <class InputIter> |
| void priv_insert_dispatch(const_iterator prev, |
| InputIter first, InputIter last, |
| containers_detail::false_) |
| { this->priv_create_and_insert_nodes(prev, first, last); } |
| |
| template<class Integer> |
| void priv_insert_dispatch(const_iterator prev, Integer n, Integer x, containers_detail::true_) |
| { this->priv_create_and_insert_nodes(prev, (std::size_t)n, x); } |
| |
| void priv_fill_assign(size_type n, const T& val) |
| { |
| iterator end_n(this->end()); |
| iterator prev(this->before_begin()); |
| iterator node(this->begin()); |
| for ( ; node != end_n && n > 0 ; --n){ |
| *node = val; |
| prev = node; |
| ++node; |
| } |
| if (n > 0) |
| this->priv_create_and_insert_nodes(prev, n, val); |
| else |
| this->erase_after(prev, end_n); |
| } |
| |
| template <class Int> |
| void priv_assign_dispatch(Int n, Int val, containers_detail::true_) |
| { this->priv_fill_assign((size_type) n, (T)val); } |
| |
| template <class InpIt> |
| void priv_assign_dispatch(InpIt first, InpIt last, containers_detail::false_) |
| { |
| iterator end_n(this->end()); |
| iterator prev(this->before_begin()); |
| iterator node(this->begin()); |
| while (node != end_n && first != last){ |
| *node = *first; |
| prev = node; |
| ++node; |
| ++first; |
| } |
| if (first != last) |
| this->priv_create_and_insert_nodes(prev, first, last); |
| else |
| this->erase_after(prev, end_n); |
| } |
| |
| template <class Int> |
| void priv_insert_after_range_dispatch(const_iterator prev_pos, Int n, Int x, containers_detail::true_) |
| { this->priv_create_and_insert_nodes(prev_pos, (std::size_t)n, x); } |
| |
| template <class InIter> |
| void priv_insert_after_range_dispatch(const_iterator prev_pos, InIter first, InIter last, containers_detail::false_) |
| { this->priv_create_and_insert_nodes(prev_pos, first, last); } |
| |
| //Functors for member algorithm defaults |
| struct value_less |
| { |
| bool operator()(const value_type &a, const value_type &b) const |
| { return a < b; } |
| }; |
| |
| struct value_equal |
| { |
| bool operator()(const value_type &a, const value_type &b) const |
| { return a == b; } |
| }; |
| |
| struct value_equal_to_this |
| { |
| explicit value_equal_to_this(const value_type &ref) |
| : m_ref(ref){} |
| |
| bool operator()(const value_type &val) const |
| { return m_ref == val; } |
| |
| const value_type &m_ref; |
| }; |
| /// @endcond |
| }; |
| |
| template <class T, class A> |
| inline bool |
| operator==(const slist<T,A>& x, const slist<T,A>& y) |
| { |
| if(x.size() != y.size()){ |
| return false; |
| } |
| typedef typename slist<T,A>::const_iterator const_iterator; |
| const_iterator end1 = x.end(); |
| |
| const_iterator i1 = x.begin(); |
| const_iterator i2 = y.begin(); |
| while (i1 != end1 && *i1 == *i2){ |
| ++i1; |
| ++i2; |
| } |
| return i1 == end1; |
| } |
| |
| template <class T, class A> |
| inline bool |
| operator<(const slist<T,A>& sL1, const slist<T,A>& sL2) |
| { |
| return std::lexicographical_compare |
| (sL1.begin(), sL1.end(), sL2.begin(), sL2.end()); |
| } |
| |
| template <class T, class A> |
| inline bool |
| operator!=(const slist<T,A>& sL1, const slist<T,A>& sL2) |
| { return !(sL1 == sL2); } |
| |
| template <class T, class A> |
| inline bool |
| operator>(const slist<T,A>& sL1, const slist<T,A>& sL2) |
| { return sL2 < sL1; } |
| |
| template <class T, class A> |
| inline bool |
| operator<=(const slist<T,A>& sL1, const slist<T,A>& sL2) |
| { return !(sL2 < sL1); } |
| |
| template <class T, class A> |
| inline bool |
| operator>=(const slist<T,A>& sL1, const slist<T,A>& sL2) |
| { return !(sL1 < sL2); } |
| |
| template <class T, class A> |
| inline void swap(slist<T,A>& x, slist<T,A>& y) |
| { x.swap(y); } |
| |
| }} |
| |
| /// @cond |
| |
| namespace boost { |
| /* |
| //!has_trivial_destructor_after_move<> == true_type |
| //!specialization for optimizations |
| template <class T, class A> |
| struct has_trivial_destructor_after_move<boost::container::slist<T, A> > |
| { |
| static const bool value = has_trivial_destructor<A>::value; |
| }; |
| */ |
| namespace container { |
| |
| /// @endcond |
| |
| }} //namespace boost{ namespace container { |
| |
| // Specialization of insert_iterator so that insertions will be constant |
| // time rather than linear time. |
| |
| ///@cond |
| |
| //Ummm, I don't like to define things in namespace std, but |
| //there is no other way |
| namespace std { |
| |
| template <class T, class A> |
| class insert_iterator<boost::container::slist<T, A> > |
| { |
| protected: |
| typedef boost::container::slist<T, A> Container; |
| Container* container; |
| typename Container::iterator iter; |
| public: |
| typedef Container container_type; |
| typedef output_iterator_tag iterator_category; |
| typedef void value_type; |
| typedef void difference_type; |
| typedef void pointer; |
| typedef void reference; |
| |
| insert_iterator(Container& x, |
| typename Container::iterator i, |
| bool is_previous = false) |
| : container(&x), iter(is_previous ? i : x.previous(i)){ } |
| |
| insert_iterator<Container>& |
| operator=(const typename Container::value_type& value) |
| { |
| iter = container->insert_after(iter, value); |
| return *this; |
| } |
| insert_iterator<Container>& operator*(){ return *this; } |
| insert_iterator<Container>& operator++(){ return *this; } |
| insert_iterator<Container>& operator++(int){ return *this; } |
| }; |
| |
| } //namespace std; |
| |
| ///@endcond |
| |
| #include INCLUDE_BOOST_CONTAINER_DETAIL_CONFIG_END_HPP |
| |
| #endif /* BOOST_CONTAINERS_SLIST_HPP */ |