diff options
Diffstat (limited to 'boost/container/slist.hpp')
| -rw-r--r-- | boost/container/slist.hpp | 1685 |
1 files changed, 929 insertions, 756 deletions
diff --git a/boost/container/slist.hpp b/boost/container/slist.hpp index 57719357fc..b6b4c388a2 100644 --- a/boost/container/slist.hpp +++ b/boost/container/slist.hpp @@ -1,6 +1,6 @@ ////////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2004-2012. Distributed under the Boost +// (C) Copyright Ion Gaztanaga 2004-2013. 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) // @@ -11,7 +11,7 @@ #ifndef BOOST_CONTAINER_SLIST_HPP #define BOOST_CONTAINER_SLIST_HPP -#if (defined _MSC_VER) && (_MSC_VER >= 1200) +#if defined(_MSC_VER) # pragma once #endif @@ -19,14 +19,19 @@ #include <boost/container/detail/workaround.hpp> #include <boost/container/container_fwd.hpp> -#include <boost/move/move.hpp> +#include <boost/container/throw_exception.hpp> +#include <boost/move/utility_core.hpp> +#include <boost/move/detail/move_helpers.hpp> +#include <boost/move/traits.hpp> #include <boost/intrusive/pointer_traits.hpp> #include <boost/container/detail/utilities.hpp> +#include <boost/container/detail/iterators.hpp> #include <boost/container/detail/mpl.hpp> -#include <boost/type_traits/has_trivial_destructor.hpp> -#include <boost/detail/no_exceptions_support.hpp> +#include <boost/container/detail/type_traits.hpp> +#include <boost/core/no_exceptions_support.hpp> #include <boost/container/detail/node_alloc_holder.hpp> #include <boost/intrusive/slist.hpp> +#include <iterator> #if defined(BOOST_CONTAINER_PERFECT_FORWARDING) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) @@ -35,22 +40,24 @@ #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 +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) +#include <initializer_list> +#endif + + namespace boost { namespace container { -#endif -/// @cond +#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED + +template <class T, class Allocator> +class slist; namespace container_detail { @@ -69,14 +76,27 @@ struct slist_node slist_node(); public: + typedef T value_type; typedef typename slist_hook<VoidPointer>::type hook_type; + T m_data; + + T &get_data() + { return this->m_data; } + + const T &get_data() const + { return this->m_data; } }; -template<class A> +template <class T, class VoidPointer> +struct iiterator_node_value_type< slist_node<T,VoidPointer> > { + typedef T type; +}; + +template<class Allocator> struct intrusive_slist_type { - typedef boost::container::allocator_traits<A> allocator_traits_type; + typedef boost::container::allocator_traits<Allocator> allocator_traits_type; typedef typename allocator_traits_type::value_type value_type; typedef typename boost::intrusive::pointer_traits <typename allocator_traits_type::pointer>::template @@ -97,7 +117,7 @@ struct intrusive_slist_type } //namespace container_detail { -/// @endcond +#endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED //! 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 @@ -131,23 +151,23 @@ struct intrusive_slist_type //! 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. +//! +//! \tparam T The type of object that is stored in the list +//! \tparam Allocator The allocator used for all internal memory management #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED -template <class T, class A = std::allocator<T> > +template <class T, class Allocator = std::allocator<T> > #else -template <class T, class A> +template <class T, class Allocator> #endif class slist : protected container_detail::node_alloc_holder - <A, typename container_detail::intrusive_slist_type<A>::type> + <Allocator, typename container_detail::intrusive_slist_type<Allocator>::type> { - /// @cond - typedef typename container_detail:: - move_const_ref_type<T>::type insert_const_ref_type; + #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED typedef typename - container_detail::intrusive_slist_type<A>::type Icont; - typedef container_detail::node_alloc_holder<A, Icont> AllocHolder; + container_detail::intrusive_slist_type<Allocator>::type Icont; + typedef container_detail::node_alloc_holder<Allocator, 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; @@ -155,7 +175,7 @@ class slist typedef typename AllocHolder::allocator_v1 allocator_v1; typedef typename AllocHolder::allocator_v2 allocator_v2; typedef typename AllocHolder::alloc_version alloc_version; - typedef boost::container::allocator_traits<A> allocator_traits_type; + typedef boost::container::allocator_traits<Allocator> allocator_traits_type; class equal_to_value { @@ -185,126 +205,39 @@ class slist 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 allocator_traits_type::pointer pointer; - //! Const pointer to T - typedef typename allocator_traits_type::const_pointer const_pointer; - //! Reference to T - typedef typename allocator_traits_type::reference reference; - //! Const reference to T - typedef typename allocator_traits_type::const_reference const_reference; - //! An unsigned integral type - typedef typename allocator_traits_type::size_type size_type; - //! A signed integral type - typedef typename allocator_traits_type::difference_type difference_type; - //! The allocator type - typedef A allocator_type; - //! Non-standard extension: the stored allocator type - typedef NodeAlloc stored_allocator_type; - - /// @cond - private: + BOOST_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 + typedef container_detail::iterator<typename Icont::iterator, false> iterator_impl; + typedef container_detail::iterator<typename Icont::iterator, true > const_iterator_impl; + #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED public: + ////////////////////////////////////////////// + // + // types + // + ////////////////////////////////////////////// + + typedef T value_type; + typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer; + typedef typename ::boost::container::allocator_traits<Allocator>::const_pointer const_pointer; + typedef typename ::boost::container::allocator_traits<Allocator>::reference reference; + typedef typename ::boost::container::allocator_traits<Allocator>::const_reference const_reference; + typedef typename ::boost::container::allocator_traits<Allocator>::size_type size_type; + typedef typename ::boost::container::allocator_traits<Allocator>::difference_type difference_type; + typedef Allocator allocator_type; + typedef BOOST_CONTAINER_IMPDEF(NodeAlloc) stored_allocator_type; + typedef BOOST_CONTAINER_IMPDEF(iterator_impl) iterator; + typedef BOOST_CONTAINER_IMPDEF(const_iterator_impl) const_iterator; - //! 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; } + public: - iterator operator++(int) - { typename Icont::iterator tmp = this->m_it; ++*this; return iterator(tmp); } - } - /// @endcond - ; + ////////////////////////////////////////////// + // + // construct/copy/destroy + // + ////////////////////////////////////////////// - public: //! <b>Effects</b>: Constructs a list taking the allocator as parameter. //! //! <b>Throws</b>: If allocator_type's copy constructor throws. @@ -316,10 +249,10 @@ class slist //! <b>Effects</b>: Constructs a list taking the allocator as parameter. //! - //! <b>Throws</b>: If allocator_type's copy constructor throws. + //! <b>Throws</b>: Nothing //! //! <b>Complexity</b>: Constant. - explicit slist(const allocator_type& a) + explicit slist(const allocator_type& a) BOOST_CONTAINER_NOEXCEPT : AllocHolder(a) {} @@ -330,37 +263,49 @@ class slist //! <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 + //! <b>Throws</b>: If allocator_type's default 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); } + { this->insert_after(this->cbefore_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>Throws</b>: If allocator_type's default constructor + //! throws or T's constructor taking a 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()) + slist(InpIt first, InpIt last, const allocator_type& a = allocator_type()) : AllocHolder(a) - { this->insert_after(this->before_begin(), first, last); } + { this->insert_after(this->cbefore_begin(), first, last); } - //! <b>Effects</b>: Copy constructs a list. +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) + //! <b>Effects</b>: Constructs a list that will use a copy of allocator a + //! and inserts a copy of the range [il.begin(), il.end()) in the list. + //! + //! <b>Throws</b>: If allocator_type's default constructor + //! throws or T's constructor taking a dereferenced std::initializer_list iterator throws. + //! + //! <b>Complexity</b>: Linear to the range [il.begin(), il.end()). + slist(std::initializer_list<value_type> il, const allocator_type& a = allocator_type()) + : AllocHolder(a) + { this->insert_after(this->cbefore_begin(), il.begin(), il.end()); } +#endif + + //! <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>Throws</b>: If allocator_type's default constructor //! //! <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()); } + { this->insert_after(this->cbefore_begin(), x.begin(), x.end()); } //! <b>Effects</b>: Move constructor. Moves mx's resources to *this. //! @@ -375,12 +320,12 @@ class slist //! //! <b>Postcondition</b>: x == *this. //! - //! <b>Throws</b>: If allocator_type's default constructor or copy constructor throws. + //! <b>Throws</b>: If allocator_type's default constructor //! //! <b>Complexity</b>: Linear to the elements x contains. slist(const slist& x, const allocator_type &a) : AllocHolder(a) - { this->insert_after(this->before_begin(), x.begin(), x.end()); } + { this->insert_after(this->cbefore_begin(), x.begin(), x.end()); } //! <b>Effects</b>: Move constructor using the specified allocator. //! Moves x's resources to *this. @@ -395,10 +340,19 @@ class slist this->icont().swap(x.icont()); } else{ - this->insert(this->cbegin(), x.begin(), x.end()); + this->insert_after(this->cbefore_begin(), x.begin(), x.end()); } } + //! <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() BOOST_CONTAINER_NOEXCEPT + {} //AllocHolder clears the slist + //! <b>Effects</b>: Makes *this contain the same elements as x. //! //! <b>Postcondition</b>: this->size() == x.size(). *this contains a copy @@ -428,85 +382,168 @@ class slist //! <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>Throws</b>: If allocator_traits_type::propagate_on_container_move_assignment + //! is false and (allocation throws or value_type's move constructor throws) //! - //! <b>Complexity</b>: Linear to the number of elements in x. + //! <b>Complexity</b>: Constant if allocator_traits_type:: + //! propagate_on_container_move_assignment is true or + //! this->get>allocator() == x.get_allocator(). Linear otherwise. slist& operator= (BOOST_RV_REF(slist) x) + BOOST_CONTAINER_NOEXCEPT_IF(allocator_traits_type::propagate_on_container_move_assignment::value) { - if (&x != this){ - NodeAlloc &this_alloc = this->node_alloc(); - NodeAlloc &x_alloc = x.node_alloc(); - //If allocators a re equal we can just swap pointers - if(this_alloc == x_alloc){ - //Destroy and swap pointers - this->clear(); - this->icont() = boost::move(x.icont()); - //Move allocator if needed - this->AllocHolder::move_assign_alloc(x); - } - //If unequal allocators, then do a one by one move - else{ - typedef typename std::iterator_traits<iterator>::iterator_category ItCat; - this->assign( boost::make_move_iterator(x.begin()) - , boost::make_move_iterator(x.end())); - } + BOOST_ASSERT(this != &x); + NodeAlloc &this_alloc = this->node_alloc(); + NodeAlloc &x_alloc = x.node_alloc(); + const bool propagate_alloc = allocator_traits_type:: + propagate_on_container_move_assignment::value; + const bool allocators_equal = this_alloc == x_alloc; (void)allocators_equal; + //Resources can be transferred if both allocators are + //going to be equal after this function (either propagated or already equal) + if(propagate_alloc || allocators_equal){ + //Destroy + this->clear(); + //Move allocator if needed + this->AllocHolder::move_assign_alloc(x); + //Obtain resources + this->icont() = boost::move(x.icont()); + } + //Else do a one by one move + else{ + this->assign( boost::make_move_iterator(x.begin()) + , boost::make_move_iterator(x.end())); } return *this; } - //! <b>Effects</b>: Destroys the list. All stored values are destroyed - //! and used memory is deallocated. +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) + //! <b>Effects</b>: Makes *this contain the same elements as in il. //! - //! <b>Throws</b>: Nothing. + //! <b>Postcondition</b>: this->size() == il.size(). *this contains a copy + //! of each of il's elements. //! - //! <b>Complexity</b>: Linear to the number of elements. - ~slist() - {} //AllocHolder clears the slist + //! <b>Throws</b>: If allocator_traits_type::propagate_on_container_move_assignment + //! is false and (allocation throws or value_type's move constructor throws) + slist& operator=(std::initializer_list<value_type> il) + { + assign(il.begin(), il.end()); + return *this; + } +#endif + + //! <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) + { + typedef constant_iterator<value_type, difference_type> cvalue_iterator; + return this->assign(cvalue_iterator(val, n), cvalue_iterator()); + } + + //! <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 + #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) + , typename container_detail::enable_if_c + < !container_detail::is_convertible<InpIt, size_type>::value + >::type * = 0 + #endif + ) + { + 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->insert_after(prev, first, last); + else + this->erase_after(prev, end_n); + } +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) + //! <b>Effects</b>: Assigns the range [il.begin(), il.end()) to *this. + //! + //! <b>Throws</b>: If memory allocation throws or + //! T's constructor from dereferencing std::initializer_list iterator throws. + //! + //! <b>Complexity</b>: Linear to range [il.begin(), il.end()). + + void assign(std::initializer_list<value_type> il) + { + assign(il.begin(), il.end()); + } +#endif //! <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 + allocator_type get_allocator() const BOOST_CONTAINER_NOEXCEPT { return allocator_type(this->node_alloc()); } - const stored_allocator_type &get_stored_allocator() const + //! <b>Effects</b>: Returns a reference to the internal allocator. + //! + //! <b>Throws</b>: Nothing + //! + //! <b>Complexity</b>: Constant. + //! + //! <b>Note</b>: Non-standard extension. + stored_allocator_type &get_stored_allocator() BOOST_CONTAINER_NOEXCEPT { return this->node_alloc(); } - stored_allocator_type &get_stored_allocator() + //! <b>Effects</b>: Returns a reference to the internal allocator. + //! + //! <b>Throws</b>: Nothing + //! + //! <b>Complexity</b>: Constant. + //! + //! <b>Note</b>: Non-standard extension. + const stored_allocator_type &get_stored_allocator() const BOOST_CONTAINER_NOEXCEPT { return this->node_alloc(); } - public: + ////////////////////////////////////////////// + // + // iterators + // + ////////////////////////////////////////////// - //! <b>Effects</b>: Assigns the n copies of val to *this. + //! <b>Effects</b>: Returns a non-dereferenceable iterator that, + //! when incremented, yields begin(). This iterator may be used + //! as the argument to insert_after, erase_after, etc. //! - //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws. + //! <b>Throws</b>: Nothing. //! - //! <b>Complexity</b>: Linear to n. - void assign(size_type n, const T& val) - { this->priv_fill_assign(n, val); } + //! <b>Complexity</b>: Constant. + iterator before_begin() BOOST_CONTAINER_NOEXCEPT + { return iterator(end()); } - //! <b>Effects</b>: Assigns the range [first, last) to *this. + //! <b>Effects</b>: Returns a non-dereferenceable const_iterator + //! that, when incremented, yields begin(). This iterator may be used + //! as the argument to insert_after, erase_after, etc. //! - //! <b>Throws</b>: If memory allocation throws or - //! T's constructor from dereferencing InpIt throws. + //! <b>Throws</b>: Nothing. //! - //! <b>Complexity</b>: Linear to n. - template <class InpIt> - void assign(InpIt first, InpIt last) - { - const bool aux_boolean = container_detail::is_convertible<InpIt, size_type>::value; - typedef container_detail::bool_<aux_boolean> Result; - this->priv_assign_dispatch(first, last, Result()); - } + //! <b>Complexity</b>: Constant. + const_iterator before_begin() const BOOST_CONTAINER_NOEXCEPT + { return this->cbefore_begin(); } //! <b>Effects</b>: Returns an iterator to the first element contained in the list. //! //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Constant. - iterator begin() + iterator begin() BOOST_CONTAINER_NOEXCEPT { return iterator(this->icont().begin()); } //! <b>Effects</b>: Returns a const_iterator to the first element contained in the list. @@ -514,7 +551,7 @@ class slist //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Constant. - const_iterator begin() const + const_iterator begin() const BOOST_CONTAINER_NOEXCEPT { return this->cbegin(); } //! <b>Effects</b>: Returns an iterator to the end of the list. @@ -522,7 +559,7 @@ class slist //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Constant. - iterator end() + iterator end() BOOST_CONTAINER_NOEXCEPT { return iterator(this->icont().end()); } //! <b>Effects</b>: Returns a const_iterator to the end of the list. @@ -530,35 +567,25 @@ class slist //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Constant. - const_iterator end() const + const_iterator end() const BOOST_CONTAINER_NOEXCEPT { 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. + //! as the argument to insert_after, erase_after, etc. //! //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Constant. - const_iterator before_begin() const - { return this->cbefore_begin(); } + const_iterator cbefore_begin() const BOOST_CONTAINER_NOEXCEPT + { return const_iterator(end()); } //! <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 + const_iterator cbegin() const BOOST_CONTAINER_NOEXCEPT { return const_iterator(this->non_const_icont().begin()); } //! <b>Effects</b>: Returns a const_iterator to the end of the list. @@ -566,18 +593,46 @@ class slist //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Constant. - const_iterator cend() const + const_iterator cend() const BOOST_CONTAINER_NOEXCEPT { 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>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. + //! + //! <b>Note</b>: Non-standard extension. + iterator previous(iterator p) BOOST_CONTAINER_NOEXCEPT + { 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. + //! + //! <b>Note</b>: Non-standard extension. + const_iterator previous(const_iterator p) + { return const_iterator(this->icont().previous(p.get())); } + + ////////////////////////////////////////////// + // + // capacity + // + ////////////////////////////////////////////// + + //! <b>Effects</b>: Returns true if the list contains no elements. //! //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Constant. - const_iterator cbefore_begin() const - { return const_iterator(end()); } + bool empty() const + { return !this->size(); } //! <b>Effects</b>: Returns the number of the elements contained in the list. //! @@ -595,21 +650,40 @@ class slist size_type max_size() const { return AllocHolder::max_size(); } - //! <b>Effects</b>: Returns true if the list contains no elements. + //! <b>Effects</b>: Inserts or erases elements at the end such that + //! the size becomes n. New elements are value initialized. //! - //! <b>Throws</b>: Nothing. + //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws. //! - //! <b>Complexity</b>: Constant. - bool empty() const - { return !this->size(); } + //! <b>Complexity</b>: Linear to the difference between size() and new_size. + void resize(size_type new_size) + { + const_iterator last_pos; + if(!priv_try_shrink(new_size, last_pos)){ + typedef value_init_construct_iterator<value_type, difference_type> value_init_iterator; + this->insert_after(last_pos, value_init_iterator(new_size - this->size()), value_init_iterator()); + } + } - //! <b>Effects</b>: Swaps the contents of *this and x. + //! <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>: Nothing. + //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws. //! - //! <b>Complexity</b>: Linear to the number of elements on *this and x. - void swap(slist& x) - { AllocHolder::swap(x); } + //! <b>Complexity</b>: Linear to the difference between size() and new_size. + void resize(size_type new_size, const T& x) + { + const_iterator last_pos; + if(!priv_try_shrink(new_size, last_pos)){ + this->insert_after(last_pos, new_size, x); + } + } + + ////////////////////////////////////////////// + // + // element access + // + ////////////////////////////////////////////// //! <b>Requires</b>: !empty() //! @@ -633,65 +707,88 @@ class slist const_reference front() const { return *this->begin(); } - //! <b>Effects</b>: Inserts a copy of t in the beginning of the list. + ////////////////////////////////////////////// + // + // modifiers + // + ////////////////////////////////////////////// + + #if defined(BOOST_CONTAINER_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. - void push_front(insert_const_ref_type x) - { return priv_push_front(x); } + template <class... Args> + void emplace_front(Args&&... args) + { this->emplace_after(this->cbefore_begin(), boost::forward<Args>(args)...); } - #if defined(BOOST_NO_RVALUE_REFERENCES) && !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) - void push_front(T &x) { push_front(const_cast<const T &>(x)); } + //! <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) + { + NodePtr pnode(AllocHolder::create_node(boost::forward<Args>(args)...)); + return iterator(this->icont().insert_after(prev.get(), *pnode)); + } - template<class U> - void push_front(const U &u - , typename container_detail::enable_if_c<container_detail::is_same<T, U>::value && !::boost::has_move_emulation_enabled<U>::value >::type* =0) - { return priv_push_front(u); } - #endif + #else //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING - //! <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. + #define BOOST_PP_LOCAL_MACRO(n) \ + BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \ + void emplace_front(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \ + { \ + this->emplace(this->cbegin() \ + BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _)); \ + } \ + \ + BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \ + iterator emplace_after(const_iterator prev \ + BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \ + { \ + NodePtr pnode (AllocHolder::create_node \ + (BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _))); \ + return iterator(this->icont().insert_after(prev.get(), *pnode)); \ + } \ //! - //! <b>Complexity</b>: Amortized constant time. - void push_front(BOOST_RV_REF(T) x) - { this->icont().push_front(*this->create_node(boost::move(x))); } + #define BOOST_PP_LOCAL_LIMITS (0, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS) + #include BOOST_PP_LOCAL_ITERATE() - //! <b>Effects</b>: Removes the first element from the list. + #endif //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING + + #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) + //! <b>Effects</b>: Inserts a copy of x at the beginning of the list. //! - //! <b>Throws</b>: Nothing. + //! <b>Throws</b>: If memory allocation throws or + //! T's copy constructor throws. //! //! <b>Complexity</b>: Amortized constant time. - void pop_front() - { this->icont().pop_front_and_dispose(Destroyer(this->node_alloc())); } + void push_front(const T &x); - //! <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>Effects</b>: Constructs a new element in the beginning of the list + //! and moves the resources of mx to this new element. //! - //! <b>Throws</b>: Nothing. + //! <b>Throws</b>: If memory allocation throws. //! - //! <b>Complexity</b>: Linear to the number of elements before i. - iterator previous(iterator p) - { return iterator(this->icont().previous(p.get())); } + //! <b>Complexity</b>: Amortized constant time. + void push_front(T &&x); + #else + BOOST_MOVE_CONVERSION_AWARE_CATCH(push_front, T, void, priv_push_front) + #endif - //! <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())); } + #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) //! <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>Effects</b>: Inserts a copy of the value after prev_p. //! //! <b>Returns</b>: An iterator to the inserted element. //! @@ -701,23 +798,12 @@ class slist //! //! <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_CONTAINER_DOXYGEN_INVOKED) - iterator insert_after(const_iterator position, T &x) - { return this->insert_after(position, const_cast<const T &>(x)); } + iterator insert_after(const_iterator prev_p, const T &x); - template<class U> - iterator insert_after( const_iterator position, const U &u - , typename container_detail::enable_if_c<container_detail::is_same<T, U>::value && !::boost::has_move_emulation_enabled<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>Requires</b>: prev_p 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. + //! p pointed by prev_p. //! //! <b>Returns</b>: An iterator to the inserted element. //! @@ -727,26 +813,35 @@ class slist //! //! <b>Note</b>: Does not affect the validity of iterators and references of //! previous values. - iterator insert_after(const_iterator prev_pos, BOOST_RV_REF(value_type) x) - { return iterator(this->icont().insert_after(prev_pos.get(), *this->create_node(boost::move(x)))); } + iterator insert_after(const_iterator prev_p, T &&x); + #else + BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert_after, T, iterator, priv_insert_after, const_iterator, const_iterator) + #endif - //! <b>Requires</b>: prev_pos must be a valid iterator of *this. + //! <b>Requires</b>: prev_p must be a valid iterator of *this. + //! + //! <b>Effects</b>: Inserts n copies of x after prev_p. //! - //! <b>Effects</b>: Inserts n copies of x after prev_pos. + //! <b>Returns</b>: an iterator to the last inserted element or prev_p if n is 0. //! //! <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); } + iterator insert_after(const_iterator prev_p, size_type n, const value_type& x) + { + typedef constant_iterator<value_type, difference_type> cvalue_iterator; + return this->insert_after(prev_p, cvalue_iterator(x, n), cvalue_iterator()); + } - //! <b>Requires</b>: prev_pos must be a valid iterator of *this. + //! <b>Requires</b>: prev_p must be a valid iterator of *this. + //! + //! <b>Effects</b>: Inserts the range pointed by [first, last) after prev_p. //! - //! <b>Effects</b>: Inserts the range pointed by [first, last) - //! after the p prev_pos. + //! <b>Returns</b>: an iterator to the last inserted element or prev_p if first == last. //! //! <b>Throws</b>: If memory allocation throws, T's constructor from a //! dereferenced InpIt throws. @@ -755,139 +850,71 @@ class slist //! //! <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) + template <class InpIt> + iterator insert_after(const_iterator prev_p, InpIt first, InpIt last + #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) + , typename container_detail::enable_if_c + < !container_detail::is_convertible<InpIt, size_type>::value + && (container_detail::is_input_iterator<InpIt>::value + || container_detail::is_same<alloc_version, allocator_v1>::value + ) + >::type * = 0 + #endif + ) { - const bool aux_boolean = container_detail::is_convertible<InIter, size_type>::value; - typedef container_detail::bool_<aux_boolean> Result; - this->priv_insert_after_range_dispatch(prev_pos, first, last, Result()); + iterator ret_it(prev_p.get()); + for (; first != last; ++first){ + ret_it = iterator(this->icont().insert_after(ret_it.get(), *this->create_node_from_it(first))); + } + return ret_it; } - //! <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_CONTAINER_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 container_detail::enable_if_c<container_detail::is_same<T, U>::value && !::boost::has_move_emulation_enabled<U>::value >::type* =0) - { return this->priv_insert(position, u); } - #endif - - //! <b>Requires</b>: p must be a valid iterator of *this. +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) + //! <b>Requires</b>: prev_p must be a valid iterator of *this. //! - //! <b>Effects</b>: Insert a new element before p with mx's resources. + //! <b>Effects</b>: Inserts the range pointed by [il.begin(), il.end()) after prev_p. //! - //! <b>Throws</b>: If memory allocation throws. - //! - //! <b>Complexity</b>: Linear to the elements before p. - iterator insert(const_iterator p, BOOST_RV_REF(value_type) x) - { return this->insert_after(previous(p), boost::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>Returns</b>: an iterator to the last inserted element or prev_p if il.begin() == il.end(). //! //! <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_CONTAINER_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 + //! dereferenced std::initializer_list iterator throws. //! - //! <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::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::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>: Linear to the number of elements inserted. //! - //! <b>Complexity</b>: Constant - template <class... Args> - iterator emplace_after(const_iterator prev, Args&&... args) + //! <b>Note</b>: Does not affect the validity of iterators and references of + //! previous values. + iterator insert_after(const_iterator prev_p, std::initializer_list<value_type> il) { - NodePtr pnode(AllocHolder::create_node(boost::forward<Args>(args)...)); - return iterator(this->icont().insert_after(prev.get(), *pnode)); + return insert_after(prev_p, il.begin(), il.end()); } +#endif + #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) + template <class FwdIt> + iterator insert_after(const_iterator prev, FwdIt first, FwdIt last + , typename container_detail::enable_if_c + < !container_detail::is_convertible<FwdIt, size_type>::value + && !(container_detail::is_input_iterator<FwdIt>::value + || container_detail::is_same<alloc_version, allocator_v1>::value + ) + >::type * = 0 + ) + { + //Optimized allocation and construction + insertion_functor func(this->icont(), prev.get()); + this->allocate_many_and_construct(first, std::distance(first, last), func); + return iterator(func.inserted_first()); + } + #endif - #else //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING - - #define BOOST_PP_LOCAL_MACRO(n) \ - BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \ - void emplace_front(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \ - { \ - this->emplace(this->cbegin() \ - BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _)); \ - } \ - \ - BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \ - iterator emplace (const_iterator p \ - BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \ - { \ - return this->emplace_after \ - (this->previous(p) \ - BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _)); \ - } \ - \ - BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \ - iterator emplace_after(const_iterator prev \ - BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \ - { \ - NodePtr pnode (AllocHolder::create_node \ - (BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _))); \ - return iterator(this->icont().insert_after(prev.get(), *pnode)); \ - } \ + //! <b>Effects</b>: Removes the first element from the list. //! - #define BOOST_PP_LOCAL_LIMITS (0, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS) - #include BOOST_PP_LOCAL_ITERATE() - - #endif //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Amortized constant time. + void pop_front() + { this->icont().pop_front_and_dispose(Destroyer(this->node_alloc())); } - //! <b>Effects</b>: Erases the element after the element pointed by prev_pos + //! <b>Effects</b>: Erases the element after the element pointed by prev_p //! of the list. //! //! <b>Returns</b>: the first element remaining beyond the removed elements, @@ -898,9 +925,9 @@ class slist //! <b>Complexity</b>: Constant. //! //! <b>Note</b>: Does not invalidate iterators or references to non erased elements. - iterator erase_after(const_iterator prev_pos) + iterator erase_after(const_iterator prev_p) { - return iterator(this->icont().erase_after_and_dispose(prev_pos.get(), Destroyer(this->node_alloc()))); + return iterator(this->icont().erase_after_and_dispose(prev_p.get(), Destroyer(this->node_alloc()))); } //! <b>Effects</b>: Erases the range (before_first, last) from @@ -919,78 +946,48 @@ class slist 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>Effects</b>: Swaps the contents of *this and x. //! //! <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>Complexity</b>: Linear to the number of elements on *this and x. + void swap(slist& x) + { AllocHolder::swap(x); } - //! <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>Effects</b>: Erases all the elements of the list. //! //! <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>Complexity</b>: Linear to the number of elements in the list. + void clear() + { this->icont().clear_and_dispose(Destroyer(this->node_alloc())); } - //! <b>Effects</b>: Inserts or erases elements at the end such that - //! the size becomes n. New elements are copy constructed from x. + ////////////////////////////////////////////// + // + // slist operations + // + ////////////////////////////////////////////// + + //! <b>Requires</b>: p must point to an element contained + //! by the list. x != *this //! - //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws. + //! <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>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>: std::runtime_error if this' allocator and x's allocator + //! are not equal. //! - //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws. + //! <b>Complexity</b>: Linear to the elements in x. //! - //! <b>Complexity</b>: Linear to the difference between size() and new_size. - void resize(size_type new_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_after(const_iterator prev_p, slist& x) BOOST_CONTAINER_NOEXCEPT { - 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); - } + BOOST_ASSERT(this != &x); + BOOST_ASSERT(this->node_alloc() == x.node_alloc()); + this->icont().splice_after(prev_p.get(), x.icont()); } - //! <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 //! @@ -1004,153 +1001,129 @@ class slist //! //! <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"); - } - } + void splice_after(const_iterator prev_p, BOOST_RV_REF(slist) x) BOOST_CONTAINER_NOEXCEPT + { this->splice_after(prev_p, static_cast<slist&>(x)); } - //! <b>Requires</b>: prev_pos must be a valid iterator of this. + //! <b>Requires</b>: prev_p must be a valid iterator of this. //! i must point to an element contained in list x. + //! this' allocator and x's allocator shall compare equal. //! //! <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. + //! after the element pointed by prev_p. + //! If prev_p == prev or prev_p == ++prev, this function is a null operation. //! - //! <b>Throws</b>: std::runtime_error if this' allocator and x's allocator - //! are not equal. + //! <b>Throws</b>: Nothing //! //! <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) + void splice_after(const_iterator prev_p, slist& x, const_iterator prev) BOOST_CONTAINER_NOEXCEPT { - 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"); - } + BOOST_ASSERT(this->node_alloc() == x.node_alloc()); + this->icont().splice_after(prev_p.get(), x.icont(), prev.get()); } - //! <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>Requires</b>: prev_p must be a valid iterator of this. + //! i must point to an element contained in list x. + //! this' allocator and x's allocator shall compare equal. //! - //! <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>Effects</b>: Transfers the value pointed by i, from list x to this list, + //! after the element pointed by prev_p. + //! If prev_p == prev or prev_p == ++prev, this function is a null operation. //! - //! <b>Throws</b>: std::runtime_error if this' allocator and x's allocator - //! are not equal. + //! <b>Throws</b>: Nothing //! - //! <b>Complexity</b>: Linear to the number of transferred elements. + //! <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) - { - 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"); - } - } + void splice_after(const_iterator prev_p, BOOST_RV_REF(slist) x, const_iterator prev) BOOST_CONTAINER_NOEXCEPT + { this->splice_after(prev_p, static_cast<slist&>(x), prev); } - //! <b>Requires</b>: prev_pos must be a valid iterator of this. + //! <b>Requires</b>: prev_p 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) + //! prev_p must not be contained in [before_first, before_last) range. + //! this' allocator and x's allocator shall compare equal. //! //! <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. + //! from list x to this list, after the element pointed by prev_p. //! - //! <b>Throws</b>: std::runtime_error if this' allocator and x's allocator - //! are not equal. + //! <b>Throws</b>: Nothing //! - //! <b>Complexity</b>: Constant. + //! <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, - size_type n) + void splice_after(const_iterator prev_p, slist& x, + const_iterator before_first, const_iterator before_last) BOOST_CONTAINER_NOEXCEPT { - 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"); - } + BOOST_ASSERT(this->node_alloc() == x.node_alloc()); + this->icont().splice_after + (prev_p.get(), x.icont(), before_first.get(), before_last.get()); } - //! <b>Requires</b>: p must point to an element contained - //! by the list. x != *this + //! <b>Requires</b>: prev_p must be a valid iterator of this. + //! before_first and before_last must be valid iterators of x. + //! prev_p must not be contained in [before_first, before_last) range. + //! this' allocator and x's allocator shall compare equal. //! - //! <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>Effects</b>: Transfers the range [before_first + 1, before_last + 1) + //! from list x to this list, after the element pointed by prev_p. //! - //! <b>Throws</b>: std::runtime_error if this' allocator and x's allocator - //! are not equal. + //! <b>Throws</b>: Nothing //! - //! <b>Complexity</b>: Linear in distance(begin(), p), and linear in x.size(). + //! <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(const_iterator p, ThisType& x) - { this->splice_after(this->previous(p), 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_p, BOOST_RV_REF(slist) x, + const_iterator before_first, const_iterator before_last) BOOST_CONTAINER_NOEXCEPT + { this->splice_after(prev_p, static_cast<slist&>(x), before_first, before_last); } - //! <b>Requires</b>: p must point to an element contained - //! by this list. i must point to an element contained in list x. + //! <b>Requires</b>: prev_p must be a valid iterator of this. + //! before_first and before_last must be valid iterators of x. + //! prev_p must not be contained in [before_first, before_last) range. + //! n == std::distance(before_first, before_last). + //! this' allocator and x's allocator shall compare equal. //! - //! <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>Effects</b>: Transfers the range [before_first + 1, before_last + 1) + //! from list x to this list, after the element pointed by prev_p. //! - //! <b>Throws</b>: std::runtime_error if this' allocator and x's allocator - //! are not equal. + //! <b>Throws</b>: Nothing //! - //! <b>Complexity</b>: Linear in distance(begin(), p), and in distance(x.begin(), i). + //! <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(const_iterator p, slist& x, const_iterator i) - { this->splice_after(previous(p), x, i); } + void splice_after(const_iterator prev_p, slist& x, + const_iterator before_first, const_iterator before_last, + size_type n) BOOST_CONTAINER_NOEXCEPT + { + BOOST_ASSERT(this->node_alloc() == x.node_alloc()); + this->icont().splice_after + (prev_p.get(), x.icont(), before_first.get(), before_last.get(), n); + } - //! <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>Requires</b>: prev_p must be a valid iterator of this. + //! before_first and before_last must be valid iterators of x. + //! prev_p must not be contained in [before_first, before_last) range. + //! n == std::distance(before_first, before_last). + //! this' allocator and x's allocator shall compare equal. //! - //! <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>Effects</b>: Transfers the range [before_first + 1, before_last + 1) + //! from list x to this list, after the element pointed by prev_p. //! - //! <b>Throws</b>: std::runtime_error if this' allocator and x's allocator - //! are not equal. + //! <b>Throws</b>: Nothing //! - //! <b>Complexity</b>: Linear in distance(begin(), p), in distance(x.begin(), first), - //! and in distance(first, last). + //! <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(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(); } + void splice_after(const_iterator prev_p, BOOST_RV_REF(slist) x, + const_iterator before_first, const_iterator before_last, + size_type n) BOOST_CONTAINER_NOEXCEPT + { this->splice_after(prev_p, static_cast<slist&>(x), before_first, before_last, n); } //! <b>Effects</b>: Removes all the elements that compare equal to value. //! @@ -1161,7 +1134,7 @@ class slist //! <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)); } + { this->remove_if(equal_to_value(value)); } //! <b>Effects</b>: Removes all the elements for which a specified //! predicate is satisfied. @@ -1182,9 +1155,9 @@ class slist //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent //! elements that are equal from the list. //! - //! <b>Throws</b>: Nothing. + //! <b>Throws</b>: If comparison throws. //! - //! <b>Complexity</b>: Linear time (size()-1 comparisons calls to pred()). + //! <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. @@ -1196,7 +1169,7 @@ class slist //! //! <b>Throws</b>: If pred throws. //! - //! <b>Complexity</b>: Linear time (size()-1 comparisons equality comparisons). + //! <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. @@ -1214,13 +1187,27 @@ class slist //! 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>Throws</b>: If comparison throws. //! //! <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>: 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>: If comparison throws. + //! + //! <b>Complexity</b>: This function is linear time: it performs at most + //! size() + x.size() - 1 comparisons. + void merge(BOOST_RV_REF(slist) x) + { this->merge(static_cast<slist&>(x)); } + //! <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. @@ -1229,7 +1216,7 @@ class slist //! 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>Throws</b>: If comp throws. //! //! <b>Complexity</b>: This function is linear time: it performs at most //! size() + x.size() - 1 comparisons. @@ -1238,19 +1225,33 @@ class slist 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"); - } + BOOST_ASSERT(this->node_alloc() == x.node_alloc()); + this->icont().merge(x.icont(), + ValueCompareToNodeCompare<StrictWeakOrdering>(comp)); } + //! <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>: If comp throws. + //! + //! <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(BOOST_RV_REF(slist) x, StrictWeakOrdering comp) + { this->merge(static_cast<slist&>(x), comp); } + //! <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>Throws</b>: If comparison throws. //! //! <b>Notes</b>: Iterators and references are not invalidated. //! @@ -1262,7 +1263,7 @@ class slist //! <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>Throws</b>: If comp throws. //! //! <b>Notes</b>: Iterators and references are not invalidated. //! @@ -1277,139 +1278,363 @@ class slist 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); } + //! <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() BOOST_CONTAINER_NOEXCEPT + { this->icont().reverse(); } - 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))); } + ////////////////////////////////////////////// + // + // list compatibility interface + // + ////////////////////////////////////////////// - void priv_push_front(const value_type &x) - { this->icont().push_front(*this->create_node(x)); } + #if defined(BOOST_CONTAINER_PERFECT_FORWARDING) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) - //Iterator range version - template<class InpIterator> - void priv_create_and_insert_nodes - (const_iterator prev, InpIterator beg, InpIterator end) + //! <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::forward<Args>(args)...); } + + #else //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING + + #define BOOST_PP_LOCAL_MACRO(n) \ + BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \ + iterator emplace (const_iterator p \ + BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \ + { \ + return this->emplace_after \ + (this->previous(p) \ + BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _)); \ + } \ + //! + #define BOOST_PP_LOCAL_LIMITS (0, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS) + #include BOOST_PP_LOCAL_ITERATE() + #endif //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING + + #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) + //! <b>Requires</b>: p must be a valid iterator of *this. + //! + //! <b>Effects</b>: Insert a copy of x before p. + //! + //! <b>Returns</b>: an iterator to the inserted element. + //! + //! <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 p, const T &x); + + //! <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>Returns</b>: an iterator to the inserted element. + //! + //! <b>Throws</b>: If memory allocation throws. + //! + //! <b>Complexity</b>: Linear to the elements before p. + iterator insert(const_iterator prev_p, T &&x); + #else + BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, T, iterator, priv_insert, const_iterator, const_iterator) + #endif + + //! <b>Requires</b>: p must be a valid iterator of *this. + //! + //! <b>Effects</b>: Inserts n copies of x before p. + //! + //! <b>Returns</b>: an iterator to the first inserted element or p if n == 0. + //! + //! <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. + iterator insert(const_iterator p, size_type n, const value_type& x) { - typedef typename std::iterator_traits<InpIterator>::iterator_category ItCat; - priv_create_and_insert_nodes(prev, beg, end, alloc_version(), ItCat()); + const_iterator prev(this->previous(p)); + this->insert_after(prev, n, x); + return ++iterator(prev.get()); } - template<class InpIterator> - void priv_create_and_insert_nodes - (const_iterator prev, InpIterator beg, InpIterator end, allocator_v1, std::input_iterator_tag) + //! <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>Returns</b>: an iterator to the first inserted element or p if first == last. + //! + //! <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> + iterator insert(const_iterator p, InIter first, InIter last) { - for (; beg != end; ++beg){ - this->icont().insert_after(prev.get(), *this->create_node_from_it(beg)); - ++prev; - } + const_iterator prev(this->previous(p)); + this->insert_after(prev, first, last); + return ++iterator(prev.get()); } - 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()); +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) + //! <b>Requires</b>: p must be a valid iterator of *this. + //! + //! <b>Effects</b>: Insert a copy of the [il.begin(), il.end()) range before p. + //! + //! <b>Returns</b>: an iterator to the first inserted element or p if il.begin() == il.end(). + //! + //! <b>Throws</b>: If memory allocation throws, T's constructor from a + //! dereferenced std::initializer_list iterator throws. + //! + //! <b>Complexity</b>: Linear to the range [il.begin(), il.end()) plus + //! linear to the elements before p. + iterator insert(const_iterator p, std::initializer_list<value_type> il) + { + return insert(p, il.begin(), il.end()); } +#endif - class insertion_functor; - friend class insertion_functor; + //! <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) BOOST_CONTAINER_NOEXCEPT + { return iterator(this->erase_after(previous(p))); } - class insertion_functor - { - Icont &icont_; - typename Icont::const_iterator prev_; + //! <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) BOOST_CONTAINER_NOEXCEPT + { return iterator(this->erase_after(previous(first), last)); } - public: - insertion_functor(Icont &icont, typename Icont::const_iterator prev) - : icont_(icont), prev_(prev) - {} + //! <b>Requires</b>: p must point to an element contained + //! by the list. x != *this. this' allocator and x's allocator shall compare equal + //! + //! <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>: Nothing + //! + //! <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, slist& x) BOOST_CONTAINER_NOEXCEPT + { this->splice_after(this->previous(p), x); } - void operator()(Node &n) - { prev_ = this->icont_.insert_after(prev_, n); } - }; + //! <b>Requires</b>: p must point to an element contained + //! by the list. x != *this. this' allocator and x's allocator shall compare equal + //! + //! <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>: Nothing + //! + //! <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, BOOST_RV_REF(slist) x) BOOST_CONTAINER_NOEXCEPT + { this->splice(p, static_cast<slist&>(x)); } - 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())); - } + //! <b>Requires</b>: p must point to an element contained + //! by this list. i must point to an element contained in list x. + //! this' allocator and x's allocator shall compare equal + //! + //! <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>: Nothing + //! + //! <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) BOOST_CONTAINER_NOEXCEPT + { this->splice_after(this->previous(p), x, this->previous(i)); } - //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()); - } + //! <b>Requires</b>: p must point to an element contained + //! by this list. i must point to an element contained in list x. + //! this' allocator and x's allocator shall compare equal. + //! + //! <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>: Nothing + //! + //! <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, BOOST_RV_REF(slist) x, const_iterator i) BOOST_CONTAINER_NOEXCEPT + { this->splice(p, static_cast<slist&>(x), i); } - //Copy constructed version - void priv_create_and_insert_nodes(const_iterator prev, size_type n, const T& x) + //! <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. + //! this' allocator and x's allocator shall compare equal. + //! + //! <b>Throws</b>: Nothing + //! + //! <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) BOOST_CONTAINER_NOEXCEPT + { this->splice_after(this->previous(p), x, this->previous(first), this->previous(last)); } + + //! <b>Requires</b>: p must point to an element contained + //! by this list. first and last must point to elements contained in list x. + //! this' allocator and x's allocator shall compare equal + //! + //! <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>: Nothing + //! + //! <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, BOOST_RV_REF(slist) x, const_iterator first, const_iterator last) BOOST_CONTAINER_NOEXCEPT + { this->splice(p, static_cast<slist&>(x), first, last); } + + //! <b>Effects</b>: Returns true if x and y are equal + //! + //! <b>Complexity</b>: Linear to the number of elements in the container. + friend bool operator==(const slist& x, const slist& y) { - typedef constant_iterator<value_type, difference_type> cvalue_iterator; - this->priv_create_and_insert_nodes(prev, cvalue_iterator(x, n), cvalue_iterator()); + if(x.size() != y.size()){ + return false; + } + typedef typename slist<T,Allocator>::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; } - //Dispatch to detect iterator range or integer overloads - template <class InputIter> - void priv_insert_dispatch(const_iterator prev, - InputIter first, InputIter last, - container_detail::false_) - { this->priv_create_and_insert_nodes(prev, first, last); } + //! <b>Effects</b>: Returns true if x and y are unequal + //! + //! <b>Complexity</b>: Linear to the number of elements in the container. + friend bool operator!=(const slist& x, const slist& y) + { return !(x == y); } + + //! <b>Effects</b>: Returns true if x is less than y + //! + //! <b>Complexity</b>: Linear to the number of elements in the container. + friend bool operator<(const slist& x, const slist& y) + { return std::lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); } + + //! <b>Effects</b>: Returns true if x is greater than y + //! + //! <b>Complexity</b>: Linear to the number of elements in the container. + friend bool operator>(const slist& x, const slist& y) + { return y < x; } + + //! <b>Effects</b>: Returns true if x is equal or less than y + //! + //! <b>Complexity</b>: Linear to the number of elements in the container. + friend bool operator<=(const slist& x, const slist& y) + { return !(y < x); } - template<class Integer> - void priv_insert_dispatch(const_iterator prev, Integer n, Integer x, container_detail::true_) - { this->priv_create_and_insert_nodes(prev, (size_type)n, x); } + //! <b>Effects</b>: Returns true if x is equal or greater than y + //! + //! <b>Complexity</b>: Linear to the number of elements in the container. + friend bool operator>=(const slist& x, const slist& y) + { return !(x < y); } - void priv_fill_assign(size_type n, const T& val) + //! <b>Effects</b>: x.swap(y) + //! + //! <b>Complexity</b>: Constant. + friend void swap(slist& x, slist& y) + { x.swap(y); } + + #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED + private: + + void priv_push_front (const T &x) + { this->insert_after(this->cbefore_begin(), x); } + + void priv_push_front (BOOST_RV_REF(T) x) + { this->insert_after(this->cbefore_begin(), ::boost::move(x)); } + + bool priv_try_shrink(size_type new_size, const_iterator &last_pos) { - 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; + 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; + } + last_pos = const_iterator(cur); + if (cur_next != end_n){ + this->erase_after(last_pos, const_iterator(end_n)); + return true; + } + else{ + return false; } - 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, container_detail::true_) - { this->priv_fill_assign((size_type) n, (T)val); } + template<class U> + iterator priv_insert(const_iterator p, BOOST_FWD_REF(U) x) + { return this->insert_after(previous(p), ::boost::forward<U>(x)); } - template <class InpIt> - void priv_assign_dispatch(InpIt first, InpIt last, container_detail::false_) + template<class U> + iterator priv_insert_after(const_iterator prev_p, BOOST_FWD_REF(U) x) + { return iterator(this->icont().insert_after(prev_p.get(), *this->create_node(::boost::forward<U>(x)))); } + + class insertion_functor; + friend class insertion_functor; + + class insertion_functor { - 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); - } + Icont &icont_; + typedef typename Icont::iterator iiterator; + typedef typename Icont::const_iterator iconst_iterator; + const iconst_iterator prev_; + iiterator ret_; - template <class Int> - void priv_insert_after_range_dispatch(const_iterator prev_pos, Int n, Int x, container_detail::true_) - { this->priv_create_and_insert_nodes(prev_pos, (size_type)n, x); } + public: + insertion_functor(Icont &icont, typename Icont::const_iterator prev) + : icont_(icont), prev_(prev), ret_(prev.unconst()) + {} - template <class InIter> - void priv_insert_after_range_dispatch(const_iterator prev_pos, InIter first, InIter last, container_detail::false_) - { this->priv_create_and_insert_nodes(prev_pos, first, last); } + void operator()(Node &n) + { + ret_ = this->icont_.insert_after(prev_, n); + } + + iiterator inserted_first() const + { return ret_; } + }; //Functors for member algorithm defaults struct value_less @@ -1434,94 +1659,42 @@ class slist const value_type &m_ref; }; - /// @endcond + #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED }; -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 +#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 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; -}; -*/ +template <class T, class Allocator> +struct has_trivial_destructor_after_move<boost::container::slist<T, Allocator> > + : public ::boost::has_trivial_destructor_after_move<Allocator> +{}; + namespace container { -/// @endcond +#endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED }} //namespace boost{ namespace container { // Specialization of insert_iterator so that insertions will be constant // time rather than linear time. -///@cond +#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED //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> > +template <class T, class Allocator> +class insert_iterator<boost::container::slist<T, Allocator> > { protected: - typedef boost::container::slist<T, A> Container; + typedef boost::container::slist<T, Allocator> Container; Container* container; typename Container::iterator iter; public: @@ -1550,8 +1723,8 @@ class insert_iterator<boost::container::slist<T, A> > } //namespace std; -///@endcond +#endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED #include <boost/container/detail/config_end.hpp> -#endif /* BOOST_CONTAINER_SLIST_HPP */ +#endif // BOOST_CONTAINER_SLIST_HPP |