diff options
Diffstat (limited to 'boost/circular_buffer')
| -rw-r--r-- | boost/circular_buffer/base.hpp | 795 | ||||
| -rw-r--r-- | boost/circular_buffer/debug.hpp | 23 | ||||
| -rw-r--r-- | boost/circular_buffer/details.hpp | 113 | ||||
| -rw-r--r-- | boost/circular_buffer/space_optimized.hpp | 520 |
4 files changed, 1048 insertions, 403 deletions
diff --git a/boost/circular_buffer/base.hpp b/boost/circular_buffer/base.hpp index 3b9886a3d3..3efa8de145 100644 --- a/boost/circular_buffer/base.hpp +++ b/boost/circular_buffer/base.hpp @@ -1,6 +1,9 @@ // Implementation of the base circular buffer. // Copyright (c) 2003-2008 Jan Gaspar +// Copyright (c) 2013 Paul A. Bristow // Doxygen comments changed. +// Copyright (c) 2013 Antony Polukhin // Move semantics implementation. +// Copyright (c) 2014 Glen Fernandes // C++11 allocator model support. // Use, modification, and distribution is subject to the Boost Software // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at @@ -9,55 +12,53 @@ #if !defined(BOOST_CIRCULAR_BUFFER_BASE_HPP) #define BOOST_CIRCULAR_BUFFER_BASE_HPP -#if defined(_MSC_VER) && _MSC_VER >= 1200 +#if defined(_MSC_VER) #pragma once #endif +#include <boost/config.hpp> #include <boost/call_traits.hpp> #include <boost/concept_check.hpp> #include <boost/limits.hpp> +#include <boost/container/allocator_traits.hpp> #include <boost/iterator/reverse_iterator.hpp> #include <boost/iterator/iterator_traits.hpp> #include <boost/type_traits/is_stateless.hpp> #include <boost/type_traits/is_integral.hpp> #include <boost/type_traits/is_scalar.hpp> +#include <boost/type_traits/is_nothrow_move_constructible.hpp> +#include <boost/type_traits/is_nothrow_move_assignable.hpp> +#include <boost/type_traits/is_copy_constructible.hpp> +#include <boost/type_traits/conditional.hpp> +#include <boost/move/move.hpp> +#include <boost/utility/addressof.hpp> #include <algorithm> #include <utility> #include <deque> -#if !defined(BOOST_NO_EXCEPTIONS) - #include <stdexcept> -#endif -#if BOOST_CB_ENABLE_DEBUG - #include <cstring> -#endif +#include <stdexcept> + #if BOOST_WORKAROUND(__MWERKS__, BOOST_TESTED_AT(0x3205)) #include <stddef.h> #endif -#if defined(BOOST_NO_STDC_NAMESPACE) -namespace std { - using ::memset; -} -#endif - namespace boost { /*! \class circular_buffer \brief Circular buffer - a STL compliant container. - \param T The type of the elements stored in the <code>circular_buffer</code>. + \tparam T The type of the elements stored in the <code>circular_buffer</code>. \par Type Requirements T The <code>T</code> has to be <a href="http://www.sgi.com/tech/stl/Assignable.html"> - SGIAssignable</a> (SGI STL defined combination of <a href="../../utility/Assignable.html"> - Assignable</a> and <a href="../../utility/CopyConstructible.html">CopyConstructible</a>). + SGIAssignable</a> (SGI STL defined combination of <a href="../../../utility/Assignable.html"> + Assignable</a> and <a href="../../../utility/CopyConstructible.html">CopyConstructible</a>). Moreover <code>T</code> has to be <a href="http://www.sgi.com/tech/stl/DefaultConstructible.html"> DefaultConstructible</a> if supplied as a default parameter when invoking some of the <code>circular_buffer</code>'s methods e.g. <code>insert(iterator pos, const value_type& item = %value_type())</code>. And <a href="http://www.sgi.com/tech/stl/EqualityComparable.html">EqualityComparable</a> and/or - <a href="../../utility/LessThanComparable.html">LessThanComparable</a> if the <code>circular_buffer</code> + <a href="../../../utility/LessThanComparable.html">LessThanComparable</a> if the <code>circular_buffer</code> will be compared with another container. - \param Alloc The allocator type used for all internal memory management. + \tparam Alloc The allocator type used for all internal memory management. \par Type Requirements Alloc The <code>Alloc</code> has to meet the allocator requirements imposed by STL. \par Default Alloc @@ -75,38 +76,50 @@ class circular_buffer /*! \endcond */ { -// Requirements - BOOST_CLASS_REQUIRE(T, boost, SGIAssignableConcept); + // Requirements + //BOOST_CLASS_REQUIRE(T, boost, SGIAssignableConcept); + + + //BOOST_CONCEPT_ASSERT((Assignable<T>)); + //BOOST_CONCEPT_ASSERT((CopyConstructible<T>)); + //BOOST_CONCEPT_ASSERT((DefaultConstructible<T>)); + + // Required if the circular_buffer will be compared with anther container. + //BOOST_CONCEPT_ASSERT((EqualityComparable<T>)); + //BOOST_CONCEPT_ASSERT((LessThanComparable<T>)); public: // Basic types + + //! The type of this <code>circular_buffer</code>. + typedef circular_buffer<T, Alloc> this_type; //! The type of elements stored in the <code>circular_buffer</code>. - typedef typename Alloc::value_type value_type; + typedef typename boost::container::allocator_traits<Alloc>::value_type value_type; //! A pointer to an element. - typedef typename Alloc::pointer pointer; + typedef typename boost::container::allocator_traits<Alloc>::pointer pointer; //! A const pointer to the element. - typedef typename Alloc::const_pointer const_pointer; + typedef typename boost::container::allocator_traits<Alloc>::const_pointer const_pointer; //! A reference to an element. - typedef typename Alloc::reference reference; + typedef typename boost::container::allocator_traits<Alloc>::reference reference; //! A const reference to an element. - typedef typename Alloc::const_reference const_reference; + typedef typename boost::container::allocator_traits<Alloc>::const_reference const_reference; //! The distance type. /*! (A signed integral type used to represent the distance between two iterators.) */ - typedef typename Alloc::difference_type difference_type; + typedef typename boost::container::allocator_traits<Alloc>::difference_type difference_type; //! The size type. /*! (An unsigned integral type that can represent any non-negative value of the container's distance type.) */ - typedef typename Alloc::size_type size_type; + typedef typename boost::container::allocator_traits<Alloc>::size_type size_type; //! The type of an allocator used in the <code>circular_buffer</code>. typedef Alloc allocator_type; @@ -114,10 +127,10 @@ public: // Iterators //! A const (random access) iterator used to iterate through the <code>circular_buffer</code>. - typedef cb_details::iterator< circular_buffer<T, Alloc>, cb_details::const_traits<Alloc> > const_iterator; + typedef cb_details::iterator< circular_buffer<T, Alloc>, cb_details::const_traits<boost::container::allocator_traits<Alloc> > > const_iterator; //! A (random access) iterator used to iterate through the <code>circular_buffer</code>. - typedef cb_details::iterator< circular_buffer<T, Alloc>, cb_details::nonconst_traits<Alloc> > iterator; + typedef cb_details::iterator< circular_buffer<T, Alloc>, cb_details::nonconst_traits<boost::container::allocator_traits<Alloc> > > iterator; //! A const iterator used to iterate backwards through a <code>circular_buffer</code>. typedef boost::reverse_iterator<const_iterator> const_reverse_iterator; @@ -145,18 +158,21 @@ public: //! The capacity type. /*! - (Same as <code>size_type</code> - defined for consistency with the - <a href="space_optimized.html"><code>circular_buffer_space_optimized</code></a>.) + (Same as <code>size_type</code> - defined for consistency with the __cbso class. + */ + // <a href="space_optimized.html"><code>circular_buffer_space_optimized</code></a>.) + typedef size_type capacity_type; // Helper types - // A type representing the "best" way to pass the value_type to a method. - typedef typename call_traits<value_type>::param_type param_value_type; + //! A type representing the "best" way to pass the value_type to a method. + typedef const value_type& param_value_type; - // A type representing the "best" way to return the value_type from a const method. - typedef typename call_traits<value_type>::param_type return_value_type; + //! A type representing rvalue from param type. + //! On compilers without rvalue references support this type is the Boost.Moves type used for emulation. + typedef BOOST_RV_REF(value_type) rvalue_type; private: // Member variables @@ -202,7 +218,7 @@ public: Constant (in the size of the <code>circular_buffer</code>). \sa <code>get_allocator()</code> for obtaining an allocator %reference. */ - allocator_type get_allocator() const { return m_alloc; } + allocator_type get_allocator() const BOOST_NOEXCEPT { return m_alloc; } //! Get the allocator reference. /*! @@ -218,7 +234,7 @@ public: although use of stateful allocators in STL is discouraged. \sa <code>get_allocator() const</code> */ - allocator_type& get_allocator() { return m_alloc; } + allocator_type& get_allocator() BOOST_NOEXCEPT { return m_alloc; } // Element access @@ -236,7 +252,7 @@ public: Constant (in the size of the <code>circular_buffer</code>). \sa <code>end()</code>, <code>rbegin()</code>, <code>rend()</code> */ - iterator begin() { return iterator(this, empty() ? 0 : m_first); } + iterator begin() BOOST_NOEXCEPT { return iterator(this, empty() ? 0 : m_first); } //! Get the iterator pointing to the end of the <code>circular_buffer</code>. /*! @@ -252,7 +268,7 @@ public: Constant (in the size of the <code>circular_buffer</code>). \sa <code>begin()</code>, <code>rbegin()</code>, <code>rend()</code> */ - iterator end() { return iterator(this, 0); } + iterator end() BOOST_NOEXCEPT { return iterator(this, 0); } //! Get the const iterator pointing to the beginning of the <code>circular_buffer</code>. /*! @@ -268,7 +284,7 @@ public: Constant (in the size of the <code>circular_buffer</code>). \sa <code>end() const</code>, <code>rbegin() const</code>, <code>rend() const</code> */ - const_iterator begin() const { return const_iterator(this, empty() ? 0 : m_first); } + const_iterator begin() const BOOST_NOEXCEPT { return const_iterator(this, empty() ? 0 : m_first); } //! Get the const iterator pointing to the end of the <code>circular_buffer</code>. /*! @@ -284,7 +300,7 @@ public: Constant (in the size of the <code>circular_buffer</code>). \sa <code>begin() const</code>, <code>rbegin() const</code>, <code>rend() const</code> */ - const_iterator end() const { return const_iterator(this, 0); } + const_iterator end() const BOOST_NOEXCEPT { return const_iterator(this, 0); } //! Get the iterator pointing to the beginning of the "reversed" <code>circular_buffer</code>. /*! @@ -300,7 +316,7 @@ public: Constant (in the size of the <code>circular_buffer</code>). \sa <code>rend()</code>, <code>begin()</code>, <code>end()</code> */ - reverse_iterator rbegin() { return reverse_iterator(end()); } + reverse_iterator rbegin() BOOST_NOEXCEPT { return reverse_iterator(end()); } //! Get the iterator pointing to the end of the "reversed" <code>circular_buffer</code>. /*! @@ -316,7 +332,7 @@ public: Constant (in the size of the <code>circular_buffer</code>). \sa <code>rbegin()</code>, <code>begin()</code>, <code>end()</code> */ - reverse_iterator rend() { return reverse_iterator(begin()); } + reverse_iterator rend() BOOST_NOEXCEPT { return reverse_iterator(begin()); } //! Get the const iterator pointing to the beginning of the "reversed" <code>circular_buffer</code>. /*! @@ -332,7 +348,7 @@ public: Constant (in the size of the <code>circular_buffer</code>). \sa <code>rend() const</code>, <code>begin() const</code>, <code>end() const</code> */ - const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); } + const_reverse_iterator rbegin() const BOOST_NOEXCEPT { return const_reverse_iterator(end()); } //! Get the const iterator pointing to the end of the "reversed" <code>circular_buffer</code>. /*! @@ -348,7 +364,7 @@ public: Constant (in the size of the <code>circular_buffer</code>). \sa <code>rbegin() const</code>, <code>begin() const</code>, <code>end() const</code> */ - const_reverse_iterator rend() const { return const_reverse_iterator(begin()); } + const_reverse_iterator rend() const BOOST_NOEXCEPT { return const_reverse_iterator(begin()); } //! Get the element at the <code>index</code> position. /*! @@ -383,7 +399,7 @@ public: Constant (in the size of the <code>circular_buffer</code>). \sa <code>\link at(size_type)const at() const \endlink</code> */ - return_value_type operator [] (size_type index) const { + const_reference operator [] (size_type index) const { BOOST_CB_ASSERT(index < size()); // check for invalid index return *add(m_first, index); } @@ -421,7 +437,7 @@ public: Constant (in the size of the <code>circular_buffer</code>). \sa <code>\link operator[](size_type)const operator[] const \endlink</code> */ - return_value_type at(size_type index) const { + const_reference at(size_type index) const { check_position(index); return (*this)[index]; } @@ -475,7 +491,7 @@ public: Constant (in the size of the <code>circular_buffer</code>). \sa <code>back() const</code> */ - return_value_type front() const { + const_reference front() const { BOOST_CB_ASSERT(!empty()); // check for empty buffer (front element not available) return *m_first; } @@ -493,7 +509,7 @@ public: Constant (in the size of the <code>circular_buffer</code>). \sa <code>front() const</code> */ - return_value_type back() const { + const_reference back() const { BOOST_CB_ASSERT(!empty()); // check for empty buffer (back element not available) return *((m_last == m_buff ? m_end : m_last) - 1); } @@ -508,8 +524,9 @@ public: The internal representation is often not linear and the state of the internal buffer may look like this:<br> <br><code> |e|f|g| | | |a|b|c|d|<br> - end ---^<br> - begin -------^</code><br><br> + end ___^<br> + begin _______^</code><br><br> + where <code>|a|b|c|d|</code> represents the "array one", <code>|e|f|g|</code> represents the "array two" and <code>| | | |</code> is a free space.<br> Now consider a typical C style function for writing data into a file:<br><br> @@ -612,8 +629,7 @@ public: This method can be useful when passing the stored data into a legacy C API as an array. \post <code>\&(*this)[0] \< \&(*this)[1] \< ... \< \&(*this)[size() - 1]</code> \return A pointer to the beginning of the array or <code>0</code> if empty. - \throws Whatever <code>T::T(const T&)</code> throws. - \throws Whatever <code>T::operator = (const T&)</code> throws. + \throws <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>. \par Exception Safety Basic; no-throw if the operations in the <i>Throws</i> section do not throw anything. \par Iterator Invalidation @@ -649,12 +665,12 @@ public: break; } if (is_uninitialized(dest)) { - m_alloc.construct(dest, *src); + boost::container::allocator_traits<Alloc>::construct(m_alloc, boost::addressof(*dest), boost::move_if_noexcept(*src)); ++constructed; } else { - value_type tmp = *src; - replace(src, *dest); - replace(dest, tmp); + value_type tmp = boost::move_if_noexcept(*src); + replace(src, boost::move_if_noexcept(*dest)); + replace(dest, boost::move(tmp)); } } } @@ -689,7 +705,7 @@ public: Constant (in the size of the <code>circular_buffer</code>). \sa <code>linearize()</code>, <code>array_one()</code>, <code>array_two()</code> */ - bool is_linearized() const { return m_first < m_last || m_last == m_buff; } + bool is_linearized() const BOOST_NOEXCEPT { return m_first < m_last || m_last == m_buff; } //! Rotate elements in the <code>circular_buffer</code>. /*! @@ -705,8 +721,7 @@ public: <code>val_0 == (*this)[0] \&\& val_1 == (*this)[1] \&\& ... \&\& val_m == (*this)[m - 1] \&\& val_r1 == (*this)[m + n - 1] \&\& val_r2 == (*this)[m + n - 2] \&\& ... \&\& val_rn == (*this)[m]</code> \param new_begin The new beginning. - \throws Whatever <code>T::T(const T&)</code> throws. - \throws Whatever <code>T::operator = (const T&)</code> throws. + \throws See <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>. \par Exception Safety Basic; no-throw if the <code>circular_buffer</code> is full or <code>new_begin</code> points to <code>begin()</code> or if the operations in the <i>Throws</i> section do not throw anything. @@ -729,12 +744,12 @@ public: difference_type n = new_begin - begin(); if (m < n) { for (; m > 0; --m) { - push_front(back()); + push_front(boost::move_if_noexcept(back())); pop_back(); } } else { for (; n > 0; --n) { - push_back(front()); + push_back(boost::move_if_noexcept(front())); pop_front(); } } @@ -756,7 +771,7 @@ public: \sa <code>capacity()</code>, <code>max_size()</code>, <code>reserve()</code>, <code>\link resize() resize(size_type, const_reference)\endlink</code> */ - size_type size() const { return m_size; } + size_type size() const BOOST_NOEXCEPT { return m_size; } /*! \brief Get the largest possible size or capacity of the <code>circular_buffer</code>. (It depends on allocator's %max_size()). @@ -770,8 +785,8 @@ public: Constant (in the size of the <code>circular_buffer</code>). \sa <code>size()</code>, <code>capacity()</code>, <code>reserve()</code> */ - size_type max_size() const { - return (std::min<size_type>)(m_alloc.max_size(), (std::numeric_limits<difference_type>::max)()); + size_type max_size() const BOOST_NOEXCEPT { + return (std::min<size_type>)(boost::container::allocator_traits<Alloc>::max_size(m_alloc), (std::numeric_limits<difference_type>::max)()); } //! Is the <code>circular_buffer</code> empty? @@ -787,7 +802,7 @@ public: Constant (in the size of the <code>circular_buffer</code>). \sa <code>full()</code> */ - bool empty() const { return size() == 0; } + bool empty() const BOOST_NOEXCEPT { return size() == 0; } //! Is the <code>circular_buffer</code> full? /*! @@ -802,7 +817,7 @@ public: Constant (in the size of the <code>circular_buffer</code>). \sa <code>empty()</code> */ - bool full() const { return capacity() == size(); } + bool full() const BOOST_NOEXCEPT { return capacity() == size(); } /*! \brief Get the maximum number of elements which can be inserted into the <code>circular_buffer</code> without overwriting any of already stored elements. @@ -816,7 +831,7 @@ public: Constant (in the size of the <code>circular_buffer</code>). \sa <code>capacity()</code>, <code>size()</code>, <code>max_size()</code> */ - size_type reserve() const { return capacity() - size(); } + size_type reserve() const BOOST_NOEXCEPT { return capacity() - size(); } //! Get the capacity of the <code>circular_buffer</code>. /*! @@ -831,18 +846,20 @@ public: \sa <code>reserve()</code>, <code>size()</code>, <code>max_size()</code>, <code>set_capacity(capacity_type)</code> */ - capacity_type capacity() const { return m_end - m_buff; } + capacity_type capacity() const BOOST_NOEXCEPT { return m_end - m_buff; } //! Change the capacity of the <code>circular_buffer</code>. - /*! + /*! + \pre If <code>T</code> is a move only type, then compiler shall support <code>noexcept</code> modifiers + and move constructor of <code>T</code> must be marked with it (must not throw exceptions). \post <code>capacity() == new_capacity \&\& size() \<= new_capacity</code><br><br> If the current number of elements stored in the <code>circular_buffer</code> is greater than the desired new capacity then number of <code>[size() - new_capacity]</code> <b>last</b> elements will be removed and the new size will be equal to <code>new_capacity</code>. \param new_capacity The new capacity. - \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is + \throws "An allocation error" if memory is exhausted, (<code>std::bad_alloc</code> if the standard allocator is used). - \throws Whatever <code>T::T(const T&)</code> throws. + Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept. \par Exception Safety Strong. \par Iterator Invalidation @@ -860,7 +877,7 @@ public: iterator b = begin(); BOOST_TRY { reset(buff, - cb_details::uninitialized_copy_with_alloc(b, b + (std::min)(new_capacity, size()), buff, m_alloc), + cb_details::uninitialized_move_if_noexcept(b, b + (std::min)(new_capacity, size()), buff, m_alloc), new_capacity); } BOOST_CATCH(...) { deallocate(buff, new_capacity); @@ -883,7 +900,7 @@ public: size. (See the <i>Effect</i>.) \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is used). - \throws Whatever <code>T::T(const T&)</code> throws. + Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept. \par Exception Safety Basic. \par Iterator Invalidation @@ -908,7 +925,9 @@ public: } //! Change the capacity of the <code>circular_buffer</code>. - /*! + /*! + \pre If <code>T</code> is a move only type, then compiler shall support <code>noexcept</code> modifiers + and move constructor of <code>T</code> must be marked with it (must not throw exceptions). \post <code>capacity() == new_capacity \&\& size() \<= new_capacity</code><br><br> If the current number of elements stored in the <code>circular_buffer</code> is greater than the desired new capacity then number of <code>[size() - new_capacity]</code> <b>first</b> elements will be removed @@ -916,7 +935,7 @@ public: \param new_capacity The new capacity. \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is used). - \throws Whatever <code>T::T(const T&)</code> throws. + Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept. \par Exception Safety Strong. \par Iterator Invalidation @@ -933,7 +952,7 @@ public: pointer buff = allocate(new_capacity); iterator e = end(); BOOST_TRY { - reset(buff, cb_details::uninitialized_copy_with_alloc(e - (std::min)(new_capacity, size()), + reset(buff, cb_details::uninitialized_move_if_noexcept(e - (std::min)(new_capacity, size()), e, buff, m_alloc), new_capacity); } BOOST_CATCH(...) { deallocate(buff, new_capacity); @@ -956,7 +975,7 @@ public: size. (See the <i>Effect</i>.) \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is used). - \throws Whatever <code>T::T(const T&)</code> throws. + Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept. \par Exception Safety Basic. \par Iterator Invalidation @@ -985,8 +1004,7 @@ public: /*! \post <code>capacity() == 0 \&\& size() == 0</code> \param alloc The allocator. - \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is - used). + \throws Nothing. \par Complexity Constant. \warning Since Boost version 1.36 the behaviour of this constructor has changed. Now the constructor does not @@ -1000,7 +1018,7 @@ public: \sa <code>circular_buffer(capacity_type, const allocator_type& alloc)</code>, <code>set_capacity(capacity_type)</code> */ - explicit circular_buffer(const allocator_type& alloc = allocator_type()) + explicit circular_buffer(const allocator_type& alloc = allocator_type()) BOOST_NOEXCEPT : m_buff(0), m_end(0), m_first(0), m_last(0), m_size(0), m_alloc(alloc) {} //! Create an empty <code>circular_buffer</code> with the specified capacity. @@ -1028,7 +1046,7 @@ public: \param alloc The allocator. \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is used). - \throws Whatever <code>T::T(const T&)</code> throws. + Whatever <code>T::T(const T&)</code> throws. \par Complexity Linear (in the <code>n</code>). */ @@ -1049,7 +1067,7 @@ public: \param alloc The allocator. \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is used). - \throws Whatever <code>T::T(const T&)</code> throws. + Whatever <code>T::T(const T&)</code> throws. \par Complexity Linear (in the <code>n</code>). */ @@ -1069,7 +1087,7 @@ public: \param cb The <code>circular_buffer</code> to be copied. \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is used). - \throws Whatever <code>T::T(const T&)</code> throws. + Whatever <code>T::T(const T&)</code> throws. \par Complexity Linear (in the size of <code>cb</code>). */ @@ -1082,7 +1100,7 @@ public: initialize_buffer(cb.capacity()); m_first = m_buff; BOOST_TRY { - m_last = cb_details::uninitialized_copy_with_alloc(cb.begin(), cb.end(), m_buff, m_alloc); + m_last = cb_details::uninitialized_copy(cb.begin(), cb.end(), m_buff, m_alloc); } BOOST_CATCH(...) { deallocate(m_buff, cb.capacity()); BOOST_RETHROW @@ -1091,24 +1109,21 @@ public: if (m_last == m_end) m_last = m_buff; } - -#if BOOST_WORKAROUND(BOOST_MSVC, < 1300) - - /*! \cond */ - template <class InputIterator> - circular_buffer(InputIterator first, InputIterator last) - : m_alloc(allocator_type()) { - initialize(first, last, is_integral<InputIterator>()); - } - - template <class InputIterator> - circular_buffer(capacity_type capacity, InputIterator first, InputIterator last) - : m_alloc(allocator_type()) { - initialize(capacity, first, last, is_integral<InputIterator>()); + +#ifndef BOOST_NO_CXX11_RVALUE_REFERENCES + //! The move constructor. + /*! \brief Move constructs a <code>circular_buffer</code> from <code>cb</code>, leaving <code>cb</code> empty. + \pre C++ compiler with rvalue references support. + \post <code>cb.empty()</code> + \param cb <code>circular_buffer</code> to 'steal' value from. + \throws Nothing. + \par Constant. + */ + circular_buffer(circular_buffer<T, Alloc>&& cb) BOOST_NOEXCEPT + : m_buff(0), m_end(0), m_first(0), m_last(0), m_size(0), m_alloc(cb.get_allocator()) { + cb.swap(*this); } - /*! \endcond */ - -#else +#endif // BOOST_NO_CXX11_RVALUE_REFERENCES //! Create a full <code>circular_buffer</code> filled with a copy of the range. /*! @@ -1122,7 +1137,7 @@ public: \param alloc The allocator. \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is used). - \throws Whatever <code>T::T(const T&)</code> throws. + Whatever <code>T::T(const T&)</code> throws. \par Complexity Linear (in the <code>std::distance(first, last)</code>). */ @@ -1149,7 +1164,7 @@ public: \param alloc The allocator. \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is used). - \throws Whatever <code>T::T(const T&)</code> throws. + Whatever <code>T::T(const T&)</code> throws. \par Complexity Linear (in <code>std::distance(first, last)</code>; in <code>min[capacity, std::distance(first, last)]</code> if the <code>InputIterator</code> is a @@ -1162,8 +1177,6 @@ public: initialize(buffer_capacity, first, last, is_integral<InputIterator>()); } -#endif // #if BOOST_WORKAROUND(BOOST_MSVC, < 1300) - //! The destructor. /*! Destroys the <code>circular_buffer</code>. @@ -1175,7 +1188,7 @@ public: Constant (in the size of the <code>circular_buffer</code>) for scalar types; linear for other types. \sa <code>clear()</code> */ - ~circular_buffer() { + ~circular_buffer() BOOST_NOEXCEPT { destroy(); #if BOOST_CB_ENABLE_DEBUG invalidate_all_iterators(); @@ -1192,7 +1205,7 @@ public: \param cb The <code>circular_buffer</code> to be copied. \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is used). - \throws Whatever <code>T::T(const T&)</code> throws. + Whatever <code>T::T(const T&)</code> throws. \par Exception Safety Strong. \par Iterator Invalidation @@ -1211,7 +1224,7 @@ public: return *this; pointer buff = allocate(cb.capacity()); BOOST_TRY { - reset(buff, cb_details::uninitialized_copy_with_alloc(cb.begin(), cb.end(), buff, m_alloc), cb.capacity()); + reset(buff, cb_details::uninitialized_copy(cb.begin(), cb.end(), buff, m_alloc), cb.capacity()); } BOOST_CATCH(...) { deallocate(buff, cb.capacity()); BOOST_RETHROW @@ -1220,6 +1233,23 @@ public: return *this; } +#ifndef BOOST_NO_CXX11_RVALUE_REFERENCES + /*! \brief Move assigns content of <code>cb</code> to <code>*this</code>, leaving <code>cb</code> empty. + \pre C++ compiler with rvalue references support. + \post <code>cb.empty()</code> + \param cb <code>circular_buffer</code> to 'steal' value from. + \throws Nothing. + \par Complexity + Constant. + */ + circular_buffer<T, Alloc>& operator = (circular_buffer<T, Alloc>&& cb) BOOST_NOEXCEPT { + cb.swap(*this); // now `this` holds `cb` + circular_buffer<T, Alloc>(get_allocator()) // temprary that holds initial `cb` allocator + .swap(cb); // makes `cb` empty + return *this; + } +#endif // BOOST_NO_CXX11_RVALUE_REFERENCES + //! Assign <code>n</code> items into the <code>circular_buffer</code>. /*! The content of the <code>circular_buffer</code> will be removed and replaced with <code>n</code> copies of the @@ -1230,7 +1260,7 @@ public: \param item The element the <code>circular_buffer</code> will be filled with. \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is used). - \throws Whatever <code>T::T(const T&)</code> throws. + Whatever <code>T::T(const T&)</code> throws. \par Exception Safety Basic. \par Iterator Invalidation @@ -1260,7 +1290,7 @@ public: \param item The element the <code>circular_buffer</code> will be filled with. \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is used). - \throws Whatever <code>T::T(const T&)</code> throws. + Whatever <code>T::T(const T&)</code> throws. \par Exception Safety Basic. \par Iterator Invalidation @@ -1292,7 +1322,7 @@ public: \param last The end of the range to be copied. \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is used). - \throws Whatever <code>T::T(const T&)</code> throws. + Whatever <code>T::T(const T&)</code> throws. \par Exception Safety Basic. \par Iterator Invalidation @@ -1329,7 +1359,7 @@ public: \param last The end of the range to be copied. \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is used). - \throws Whatever <code>T::T(const T&)</code> throws. + Whatever <code>T::T(const T&)</code> throws. \par Exception Safety Basic. \par Iterator Invalidation @@ -1367,7 +1397,7 @@ public: Constant (in the size of the <code>circular_buffer</code>). \sa <code>swap(circular_buffer<T, Alloc>&, circular_buffer<T, Alloc>&)</code> */ - void swap(circular_buffer<T, Alloc>& cb) { + void swap(circular_buffer<T, Alloc>& cb) BOOST_NOEXCEPT { swap_allocator(cb, is_stateless<allocator_type>()); std::swap(m_buff, cb.m_buff); std::swap(m_end, cb.m_end); @@ -1381,7 +1411,44 @@ public: } // push and pop +private: + template <class ValT> + void push_back_impl(ValT item) { + if (full()) { + if (empty()) + return; + replace(m_last, static_cast<ValT>(item)); + increment(m_last); + m_first = m_last; + } else { + boost::container::allocator_traits<Alloc>::construct(m_alloc, boost::addressof(*m_last), static_cast<ValT>(item)); + increment(m_last); + ++m_size; + } + } + + template <class ValT> + void push_front_impl(ValT item) { + BOOST_TRY { + if (full()) { + if (empty()) + return; + decrement(m_first); + replace(m_first, static_cast<ValT>(item)); + m_last = m_first; + } else { + decrement(m_first); + boost::container::allocator_traits<Alloc>::construct(m_alloc, boost::addressof(*m_first), static_cast<ValT>(item)); + ++m_size; + } + } BOOST_CATCH(...) { + increment(m_first); + BOOST_RETHROW + } + BOOST_CATCH_END + } +public: //! Insert a new element at the end of the <code>circular_buffer</code>. /*! \post if <code>capacity() > 0</code> then <code>back() == item</code><br> @@ -1389,7 +1456,7 @@ public: <code>0</code>, nothing will be inserted. \param item The element to be inserted. \throws Whatever <code>T::T(const T&)</code> throws. - \throws Whatever <code>T::operator = (const T&)</code> throws. + Whatever <code>T::operator = (const T&)</code> throws. \par Exception Safety Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything. \par Iterator Invalidation @@ -1399,18 +1466,51 @@ public: \sa <code>\link push_front() push_front(const_reference)\endlink</code>, <code>pop_back()</code>, <code>pop_front()</code> */ - void push_back(param_value_type item = value_type()) { - if (full()) { - if (empty()) - return; - replace(m_last, item); - increment(m_last); - m_first = m_last; - } else { - m_alloc.construct(m_last, item); - increment(m_last); - ++m_size; - } + void push_back(param_value_type item) { + push_back_impl<param_value_type>(item); + } + + //! Insert a new element at the end of the <code>circular_buffer</code> using rvalue references or rvalues references emulation. + /*! + \post if <code>capacity() > 0</code> then <code>back() == item</code><br> + If the <code>circular_buffer</code> is full, the first element will be removed. If the capacity is + <code>0</code>, nothing will be inserted. + \param item The element to be inserted. + \throws Whatever <code>T::T(T&&)</code> throws. + Whatever <code>T::operator = (T&&)</code> throws. + \par Exception Safety + Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything. + \par Iterator Invalidation + Does not invalidate any iterators with the exception of iterators pointing to the overwritten element. + \par Complexity + Constant (in the size of the <code>circular_buffer</code>). + \sa <code>\link push_front() push_front(const_reference)\endlink</code>, + <code>pop_back()</code>, <code>pop_front()</code> + */ + void push_back(rvalue_type item) { + push_back_impl<rvalue_type>(boost::move(item)); + } + + //! Insert a new default-constructed element at the end of the <code>circular_buffer</code>. + /*! + \post if <code>capacity() > 0</code> then <code>back() == item</code><br> + If the <code>circular_buffer</code> is full, the first element will be removed. If the capacity is + <code>0</code>, nothing will be inserted. + \throws Whatever <code>T::T()</code> throws. + Whatever <code>T::T(T&&)</code> throws. + Whatever <code>T::operator = (T&&)</code> throws. + \par Exception Safety + Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything. + \par Iterator Invalidation + Does not invalidate any iterators with the exception of iterators pointing to the overwritten element. + \par Complexity + Constant (in the size of the <code>circular_buffer</code>). + \sa <code>\link push_front() push_front(const_reference)\endlink</code>, + <code>pop_back()</code>, <code>pop_front()</code> + */ + void push_back() { + value_type temp; + push_back(boost::move(temp)); } //! Insert a new element at the beginning of the <code>circular_buffer</code>. @@ -1420,7 +1520,7 @@ public: <code>0</code>, nothing will be inserted. \param item The element to be inserted. \throws Whatever <code>T::T(const T&)</code> throws. - \throws Whatever <code>T::operator = (const T&)</code> throws. + Whatever <code>T::operator = (const T&)</code> throws. \par Exception Safety Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything. \par Iterator Invalidation @@ -1430,24 +1530,51 @@ public: \sa <code>\link push_back() push_back(const_reference)\endlink</code>, <code>pop_back()</code>, <code>pop_front()</code> */ - void push_front(param_value_type item = value_type()) { - BOOST_TRY { - if (full()) { - if (empty()) - return; - decrement(m_first); - replace(m_first, item); - m_last = m_first; - } else { - decrement(m_first); - m_alloc.construct(m_first, item); - ++m_size; - } - } BOOST_CATCH(...) { - increment(m_first); - BOOST_RETHROW - } - BOOST_CATCH_END + void push_front(param_value_type item) { + push_front_impl<param_value_type>(item); + } + + //! Insert a new element at the beginning of the <code>circular_buffer</code> using rvalue references or rvalues references emulation. + /*! + \post if <code>capacity() > 0</code> then <code>front() == item</code><br> + If the <code>circular_buffer</code> is full, the last element will be removed. If the capacity is + <code>0</code>, nothing will be inserted. + \param item The element to be inserted. + \throws Whatever <code>T::T(T&&)</code> throws. + Whatever <code>T::operator = (T&&)</code> throws. + \par Exception Safety + Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything. + \par Iterator Invalidation + Does not invalidate any iterators with the exception of iterators pointing to the overwritten element. + \par Complexity + Constant (in the size of the <code>circular_buffer</code>). + \sa <code>\link push_back() push_back(const_reference)\endlink</code>, + <code>pop_back()</code>, <code>pop_front()</code> + */ + void push_front(rvalue_type item) { + push_front_impl<rvalue_type>(boost::move(item)); + } + + //! Insert a new default-constructed element at the beginning of the <code>circular_buffer</code>. + /*! + \post if <code>capacity() > 0</code> then <code>front() == item</code><br> + If the <code>circular_buffer</code> is full, the last element will be removed. If the capacity is + <code>0</code>, nothing will be inserted. + \throws Whatever <code>T::T()</code> throws. + Whatever <code>T::T(T&&)</code> throws. + Whatever <code>T::operator = (T&&)</code> throws. + \par Exception Safety + Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything. + \par Iterator Invalidation + Does not invalidate any iterators with the exception of iterators pointing to the overwritten element. + \par Complexity + Constant (in the size of the <code>circular_buffer</code>). + \sa <code>\link push_back() push_back(const_reference)\endlink</code>, + <code>pop_back()</code>, <code>pop_front()</code> + */ + void push_front() { + value_type temp; + push_front(boost::move(temp)); } //! Remove the last element from the <code>circular_buffer</code>. @@ -1491,6 +1618,15 @@ public: increment(m_first); --m_size; } +private: + template <class ValT> + iterator insert_impl(iterator pos, ValT item) { + BOOST_CB_ASSERT(pos.is_valid(this)); // check for uninitialized or invalidated iterator + iterator b = begin(); + if (full() && pos == b) + return b; + return insert_item<ValT>(pos, static_cast<ValT>(item)); + } public: // Insert @@ -1507,7 +1643,9 @@ public: \return Iterator to the inserted element or <code>begin()</code> if the <code>item</code> is not inserted. (See the <i>Effect</i>.) \throws Whatever <code>T::T(const T&)</code> throws. - \throws Whatever <code>T::operator = (const T&)</code> throws. + Whatever <code>T::operator = (const T&)</code> throws. + <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>. + \par Exception Safety Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything. \par Iterator Invalidation @@ -1524,12 +1662,77 @@ public: rinsert(iterator, size_type, value_type)\endlink</code>, <code>rinsert(iterator, InputIterator, InputIterator)</code> */ - iterator insert(iterator pos, param_value_type item = value_type()) { - BOOST_CB_ASSERT(pos.is_valid(this)); // check for uninitialized or invalidated iterator - iterator b = begin(); - if (full() && pos == b) - return b; - return insert_item(pos, item); + iterator insert(iterator pos, param_value_type item) { + return insert_impl<param_value_type>(pos, item); + } + + //! Insert an element at the specified position. + /*! + \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> or its end. + \post The <code>item</code> will be inserted at the position <code>pos</code>.<br> + If the <code>circular_buffer</code> is full, the first element will be overwritten. If the + <code>circular_buffer</code> is full and the <code>pos</code> points to <code>begin()</code>, then the + <code>item</code> will not be inserted. If the capacity is <code>0</code>, nothing will be inserted. + \param pos An iterator specifying the position where the <code>item</code> will be inserted. + \param item The element to be inserted. + \return Iterator to the inserted element or <code>begin()</code> if the <code>item</code> is not inserted. (See + the <i>Effect</i>.) + \throws Whatever <code>T::T(T&&)</code> throws. + Whatever <code>T::operator = (T&&)</code> throws. + <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>. + \par Exception Safety + Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything. + \par Iterator Invalidation + Invalidates iterators pointing to the elements at the insertion point (including <code>pos</code>) and + iterators behind the insertion point (towards the end; except iterators equal to <code>end()</code>). It + also invalidates iterators pointing to the overwritten element. + \par Complexity + Linear (in <code>std::distance(pos, end())</code>). + \sa <code>\link insert(iterator, size_type, param_value_type) + insert(iterator, size_type, value_type)\endlink</code>, + <code>insert(iterator, InputIterator, InputIterator)</code>, + <code>\link rinsert(iterator, param_value_type) rinsert(iterator, value_type)\endlink</code>, + <code>\link rinsert(iterator, size_type, param_value_type) + rinsert(iterator, size_type, value_type)\endlink</code>, + <code>rinsert(iterator, InputIterator, InputIterator)</code> + */ + iterator insert(iterator pos, rvalue_type item) { + return insert_impl<rvalue_type>(pos, boost::move(item)); + } + + //! Insert a default-constructed element at the specified position. + /*! + \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> or its end. + \post The <code>item</code> will be inserted at the position <code>pos</code>.<br> + If the <code>circular_buffer</code> is full, the first element will be overwritten. If the + <code>circular_buffer</code> is full and the <code>pos</code> points to <code>begin()</code>, then the + <code>item</code> will not be inserted. If the capacity is <code>0</code>, nothing will be inserted. + \param pos An iterator specifying the position where the <code>item</code> will be inserted. + \return Iterator to the inserted element or <code>begin()</code> if the <code>item</code> is not inserted. (See + the <i>Effect</i>.) + \throws Whatever <code>T::T()</code> throws. + Whatever <code>T::T(T&&)</code> throws. + Whatever <code>T::operator = (T&&)</code> throws. + <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>. + \par Exception Safety + Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything. + \par Iterator Invalidation + Invalidates iterators pointing to the elements at the insertion point (including <code>pos</code>) and + iterators behind the insertion point (towards the end; except iterators equal to <code>end()</code>). It + also invalidates iterators pointing to the overwritten element. + \par Complexity + Linear (in <code>std::distance(pos, end())</code>). + \sa <code>\link insert(iterator, size_type, param_value_type) + insert(iterator, size_type, value_type)\endlink</code>, + <code>insert(iterator, InputIterator, InputIterator)</code>, + <code>\link rinsert(iterator, param_value_type) rinsert(iterator, value_type)\endlink</code>, + <code>\link rinsert(iterator, size_type, param_value_type) + rinsert(iterator, size_type, value_type)\endlink</code>, + <code>rinsert(iterator, InputIterator, InputIterator)</code> + */ + iterator insert(iterator pos) { + value_type temp; + return insert(pos, boost::move(temp)); } //! Insert <code>n</code> copies of the <code>item</code> at the specified position. @@ -1543,7 +1746,8 @@ public: \param n The number of <code>item</code>s the to be inserted. \param item The element whose copies will be inserted. \throws Whatever <code>T::T(const T&)</code> throws. - \throws Whatever <code>T::operator = (const T&)</code> throws. + Whatever <code>T::operator = (const T&)</code> throws. + <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>. \par Exception Safety Basic; no-throw if the operations in the <i>Throws</i> section do not throw anything. \par Iterator Invalidation @@ -1556,7 +1760,7 @@ public: Consider a <code>circular_buffer</code> with the capacity of 6 and the size of 4. Its internal buffer may look like the one below.<br><br> <code>|1|2|3|4| | |</code><br> - <code>p ---^</code><br><br>After inserting 5 elements at the position <code>p</code>:<br><br> + <code>p ___^</code><br><br>After inserting 5 elements at the position <code>p</code>:<br><br> <code>insert(p, (size_t)5, 0);</code><br><br>actually only 4 elements get inserted and elements <code>1</code> and <code>2</code> are overwritten. This is due to the fact the insert operation preserves the capacity. After insertion the internal buffer looks like this:<br><br><code>|0|0|0|0|3|4|</code><br> @@ -1594,8 +1798,10 @@ public: \param pos An iterator specifying the position where the range will be inserted. \param first The beginning of the range to be inserted. \param last The end of the range to be inserted. - \throws Whatever <code>T::T(const T&)</code> throws. - \throws Whatever <code>T::operator = (const T&)</code> throws. + \throws Whatever <code>T::T(const T&)</code> throws if the <code>InputIterator</code> is not a move iterator. + Whatever <code>T::operator = (const T&)</code> throws if the <code>InputIterator</code> is not a move iterator. + Whatever <code>T::T(T&&)</code> throws if the <code>InputIterator</code> is a move iterator. + Whatever <code>T::operator = (T&&)</code> throws if the <code>InputIterator</code> is a move iterator. \par Exception Safety Basic; no-throw if the operations in the <i>Throws</i> section do not throw anything. \par Iterator Invalidation @@ -1611,7 +1817,7 @@ public: Consider a <code>circular_buffer</code> with the capacity of 6 and the size of 4. Its internal buffer may look like the one below.<br><br> <code>|1|2|3|4| | |</code><br> - <code>p ---^</code><br><br>After inserting a range of elements at the position <code>p</code>:<br><br> + <code>p ___^</code><br><br>After inserting a range of elements at the position <code>p</code>:<br><br> <code>int array[] = { 5, 6, 7, 8, 9 };</code><br><code>insert(p, array, array + 5);</code><br><br> actually only elements <code>6</code>, <code>7</code>, <code>8</code> and <code>9</code> from the specified range get inserted and elements <code>1</code> and <code>2</code> are overwritten. This is due @@ -1631,42 +1837,16 @@ public: insert(pos, first, last, is_integral<InputIterator>()); } - //! Insert an element before the specified position. - /*! - \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> or its end. - \post The <code>item</code> will be inserted before the position <code>pos</code>.<br> - If the <code>circular_buffer</code> is full, the last element will be overwritten. If the - <code>circular_buffer</code> is full and the <code>pos</code> points to <code>end()</code>, then the - <code>item</code> will not be inserted. If the capacity is <code>0</code>, nothing will be inserted. - \param pos An iterator specifying the position before which the <code>item</code> will be inserted. - \param item The element to be inserted. - \return Iterator to the inserted element or <code>end()</code> if the <code>item</code> is not inserted. (See - the <i>Effect</i>.) - \throws Whatever <code>T::T(const T&)</code> throws. - \throws Whatever <code>T::operator = (const T&)</code> throws. - \par Exception Safety - Basic; no-throw if the operations in the <i>Throws</i> section do not throw anything. - \par Iterator Invalidation - Invalidates iterators pointing to the elements before the insertion point (towards the beginning and - excluding <code>pos</code>). It also invalidates iterators pointing to the overwritten element. - \par Complexity - Linear (in <code>std::distance(begin(), pos)</code>). - \sa <code>\link rinsert(iterator, size_type, param_value_type) - rinsert(iterator, size_type, value_type)\endlink</code>, - <code>rinsert(iterator, InputIterator, InputIterator)</code>, - <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>, - <code>\link insert(iterator, size_type, param_value_type) - insert(iterator, size_type, value_type)\endlink</code>, - <code>insert(iterator, InputIterator, InputIterator)</code> - */ - iterator rinsert(iterator pos, param_value_type item = value_type()) { +private: + template <class ValT> + iterator rinsert_impl(iterator pos, ValT item) { BOOST_CB_ASSERT(pos.is_valid(this)); // check for uninitialized or invalidated iterator if (full() && pos.m_it == 0) return end(); if (pos == begin()) { BOOST_TRY { decrement(m_first); - construct_or_replace(!full(), m_first, item); + construct_or_replace(!full(), m_first, static_cast<ValT>(item)); } BOOST_CATCH(...) { increment(m_first); BOOST_RETHROW @@ -1681,13 +1861,13 @@ public: bool construct = !full(); BOOST_TRY { while (src != pos.m_it) { - construct_or_replace(construct, dest, *src); + construct_or_replace(construct, dest, boost::move_if_noexcept(*src)); increment(src); increment(dest); construct = false; } decrement(pos.m_it); - replace(pos.m_it, item); + replace(pos.m_it, static_cast<ValT>(item)); } BOOST_CATCH(...) { if (!construct && !full()) { decrement(m_first); @@ -1705,6 +1885,108 @@ public: return iterator(this, pos.m_it); } +public: + + //! Insert an element before the specified position. + /*! + \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> or its end. + \post The <code>item</code> will be inserted before the position <code>pos</code>.<br> + If the <code>circular_buffer</code> is full, the last element will be overwritten. If the + <code>circular_buffer</code> is full and the <code>pos</code> points to <code>end()</code>, then the + <code>item</code> will not be inserted. If the capacity is <code>0</code>, nothing will be inserted. + \param pos An iterator specifying the position before which the <code>item</code> will be inserted. + \param item The element to be inserted. + \return Iterator to the inserted element or <code>end()</code> if the <code>item</code> is not inserted. (See + the <i>Effect</i>.) + \throws Whatever <code>T::T(const T&)</code> throws. + Whatever <code>T::operator = (const T&)</code> throws. + <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>. + \par Exception Safety + Basic; no-throw if the operations in the <i>Throws</i> section do not throw anything. + \par Iterator Invalidation + Invalidates iterators pointing to the elements before the insertion point (towards the beginning and + excluding <code>pos</code>). It also invalidates iterators pointing to the overwritten element. + \par Complexity + Linear (in <code>std::distance(begin(), pos)</code>). + \sa <code>\link rinsert(iterator, size_type, param_value_type) + rinsert(iterator, size_type, value_type)\endlink</code>, + <code>rinsert(iterator, InputIterator, InputIterator)</code>, + <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>, + <code>\link insert(iterator, size_type, param_value_type) + insert(iterator, size_type, value_type)\endlink</code>, + <code>insert(iterator, InputIterator, InputIterator)</code> + */ + iterator rinsert(iterator pos, param_value_type item) { + return rinsert_impl<param_value_type>(pos, item); + } + + //! Insert an element before the specified position. + /*! + \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> or its end. + \post The <code>item</code> will be inserted before the position <code>pos</code>.<br> + If the <code>circular_buffer</code> is full, the last element will be overwritten. If the + <code>circular_buffer</code> is full and the <code>pos</code> points to <code>end()</code>, then the + <code>item</code> will not be inserted. If the capacity is <code>0</code>, nothing will be inserted. + \param pos An iterator specifying the position before which the <code>item</code> will be inserted. + \param item The element to be inserted. + \return Iterator to the inserted element or <code>end()</code> if the <code>item</code> is not inserted. (See + the <i>Effect</i>.) + \throws Whatever <code>T::T(T&&)</code> throws. + Whatever <code>T::operator = (T&&)</code> throws. + <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>. + \par Exception Safety + Basic; no-throw if the operations in the <i>Throws</i> section do not throw anything. + \par Iterator Invalidation + Invalidates iterators pointing to the elements before the insertion point (towards the beginning and + excluding <code>pos</code>). It also invalidates iterators pointing to the overwritten element. + \par Complexity + Linear (in <code>std::distance(begin(), pos)</code>). + \sa <code>\link rinsert(iterator, size_type, param_value_type) + rinsert(iterator, size_type, value_type)\endlink</code>, + <code>rinsert(iterator, InputIterator, InputIterator)</code>, + <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>, + <code>\link insert(iterator, size_type, param_value_type) + insert(iterator, size_type, value_type)\endlink</code>, + <code>insert(iterator, InputIterator, InputIterator)</code> + */ + iterator rinsert(iterator pos, rvalue_type item) { + return rinsert_impl<rvalue_type>(pos, boost::move(item)); + } + + //! Insert an element before the specified position. + /*! + \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> or its end. + \post The <code>item</code> will be inserted before the position <code>pos</code>.<br> + If the <code>circular_buffer</code> is full, the last element will be overwritten. If the + <code>circular_buffer</code> is full and the <code>pos</code> points to <code>end()</code>, then the + <code>item</code> will not be inserted. If the capacity is <code>0</code>, nothing will be inserted. + \param pos An iterator specifying the position before which the <code>item</code> will be inserted. + \return Iterator to the inserted element or <code>end()</code> if the <code>item</code> is not inserted. (See + the <i>Effect</i>.) + \throws Whatever <code>T::T()</code> throws. + Whatever <code>T::T(T&&)</code> throws. + Whatever <code>T::operator = (T&&)</code> throws. + <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>. + \par Exception Safety + Basic; no-throw if the operations in the <i>Throws</i> section do not throw anything. + \par Iterator Invalidation + Invalidates iterators pointing to the elements before the insertion point (towards the beginning and + excluding <code>pos</code>). It also invalidates iterators pointing to the overwritten element. + \par Complexity + Linear (in <code>std::distance(begin(), pos)</code>). + \sa <code>\link rinsert(iterator, size_type, param_value_type) + rinsert(iterator, size_type, value_type)\endlink</code>, + <code>rinsert(iterator, InputIterator, InputIterator)</code>, + <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>, + <code>\link insert(iterator, size_type, param_value_type) + insert(iterator, size_type, value_type)\endlink</code>, + <code>insert(iterator, InputIterator, InputIterator)</code> + */ + iterator rinsert(iterator pos) { + value_type temp; + return rinsert(pos, boost::move(temp)); + } + //! Insert <code>n</code> copies of the <code>item</code> before the specified position. /*! \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> or its end. @@ -1716,7 +1998,8 @@ public: \param n The number of <code>item</code>s the to be inserted. \param item The element whose copies will be inserted. \throws Whatever <code>T::T(const T&)</code> throws. - \throws Whatever <code>T::operator = (const T&)</code> throws. + Whatever <code>T::operator = (const T&)</code> throws. + <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>. \par Exception Safety Basic; no-throw if the operations in the <i>Throws</i> section do not throw anything. \par Iterator Invalidation @@ -1728,7 +2011,7 @@ public: Consider a <code>circular_buffer</code> with the capacity of 6 and the size of 4. Its internal buffer may look like the one below.<br><br> <code>|1|2|3|4| | |</code><br> - <code>p ---^</code><br><br>After inserting 5 elements before the position <code>p</code>:<br><br> + <code>p ___^</code><br><br>After inserting 5 elements before the position <code>p</code>:<br><br> <code>rinsert(p, (size_t)5, 0);</code><br><br>actually only 4 elements get inserted and elements <code>3</code> and <code>4</code> are overwritten. This is due to the fact the rinsert operation preserves the capacity. After insertion the internal buffer looks like this:<br><br><code>|1|2|0|0|0|0|</code><br> @@ -1759,8 +2042,10 @@ public: \param pos An iterator specifying the position where the range will be inserted. \param first The beginning of the range to be inserted. \param last The end of the range to be inserted. - \throws Whatever <code>T::T(const T&)</code> throws. - \throws Whatever <code>T::operator = (const T&)</code> throws. + \throws Whatever <code>T::T(const T&)</code> throws if the <code>InputIterator</code> is not a move iterator. + Whatever <code>T::operator = (const T&)</code> throws if the <code>InputIterator</code> is not a move iterator. + Whatever <code>T::T(T&&)</code> throws if the <code>InputIterator</code> is a move iterator. + Whatever <code>T::operator = (T&&)</code> throws if the <code>InputIterator</code> is a move iterator. \par Exception Safety Basic; no-throw if the operations in the <i>Throws</i> section do not throw anything. \par Iterator Invalidation @@ -1775,7 +2060,7 @@ public: Consider a <code>circular_buffer</code> with the capacity of 6 and the size of 4. Its internal buffer may look like the one below.<br><br> <code>|1|2|3|4| | |</code><br> - <code>p ---^</code><br><br>After inserting a range of elements before the position <code>p</code>:<br><br> + <code>p ___^</code><br><br>After inserting a range of elements before the position <code>p</code>:<br><br> <code>int array[] = { 5, 6, 7, 8, 9 };</code><br><code>insert(p, array, array + 5);</code><br><br> actually only elements <code>5</code>, <code>6</code>, <code>7</code> and <code>8</code> from the specified range get inserted and elements <code>3</code> and <code>4</code> are overwritten. This is due @@ -1805,7 +2090,7 @@ public: \param pos An iterator pointing at the element to be removed. \return Iterator to the first element remaining beyond the removed element or <code>end()</code> if no such element exists. - \throws Whatever <code>T::operator = (const T&)</code> throws. + \throws <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>. \par Exception Safety Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything. \par Iterator Invalidation @@ -1823,7 +2108,7 @@ public: pointer next = pos.m_it; increment(next); for (pointer p = pos.m_it; next != m_last; p = next, increment(next)) - replace(p, *next); + replace(p, boost::move_if_noexcept(*next)); decrement(m_last); destroy_item(m_last); --m_size; @@ -1843,7 +2128,7 @@ public: \param last The end of the range to be removed. \return Iterator to the first element remaining beyond the removed elements or <code>end()</code> if no such element exists. - \throws Whatever <code>T::operator = (const T&)</code> throws. + \throws <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>. \par Exception Safety Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything. \par Iterator Invalidation @@ -1862,7 +2147,7 @@ public: return first; pointer p = first.m_it; while (last.m_it != 0) - replace((first++).m_it, *last++); + replace((first++).m_it, boost::move_if_noexcept(*last++)); do { decrement(m_last); destroy_item(m_last); @@ -1879,7 +2164,7 @@ public: \param pos An iterator pointing at the element to be removed. \return Iterator to the first element remaining in front of the removed element or <code>begin()</code> if no such element exists. - \throws Whatever <code>T::operator = (const T&)</code> throws. + \throws <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>. \par Exception Safety Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything. \par Iterator Invalidation @@ -1900,7 +2185,7 @@ public: pointer prev = pos.m_it; pointer p = prev; for (decrement(prev); p != m_first; p = prev, decrement(prev)) - replace(p, *prev); + replace(p, boost::move_if_noexcept(*prev)); destroy_item(m_first); increment(m_first); --m_size; @@ -1920,7 +2205,7 @@ public: \param last The end of the range to be removed. \return Iterator to the first element remaining in front of the removed elements or <code>begin()</code> if no such element exists. - \throws Whatever <code>T::operator = (const T&)</code> throws. + \throws <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>. \par Exception Safety Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything. \par Iterator Invalidation @@ -1945,7 +2230,7 @@ public: while (first.m_it != m_first) { decrement(first.m_it); decrement(p); - replace(p, *first.m_it); + replace(p, boost::move_if_noexcept(*first.m_it)); } do { destroy_item(m_first); @@ -1963,7 +2248,7 @@ public: \pre <code>n \<= size()</code> \post The <code>n</code> elements at the beginning of the <code>circular_buffer</code> will be removed. \param n The number of elements to be removed. - \throws Whatever <code>T::operator = (const T&)</code> throws. (Does not throw anything in case of scalars.) + \throws <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>. \par Exception Safety Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything. (I.e. no throw in case of scalars.) @@ -1995,7 +2280,7 @@ public: \pre <code>n \<= size()</code> \post The <code>n</code> elements at the end of the <code>circular_buffer</code> will be removed. \param n The number of elements to be removed. - \throws Whatever <code>T::operator = (const T&)</code> throws. (Does not throw anything in case of scalars.) + \throws <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>. \par Exception Safety Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything. (I.e. no throw in case of scalars.) @@ -2037,7 +2322,7 @@ public: <code>rerase(iterator)</code>, <code>rerase(iterator, iterator)</code>, <code>erase_begin(size_type)</code>, <code>erase_end(size_type)</code> */ - void clear() { + void clear() BOOST_NOEXCEPT { destroy_content(); m_size = 0; } @@ -2086,11 +2371,11 @@ private: if (n > max_size()) throw_exception(std::length_error("circular_buffer")); #if BOOST_CB_ENABLE_DEBUG - pointer p = (n == 0) ? 0 : m_alloc.allocate(n, 0); - std::memset(p, cb_details::UNINITIALIZED, sizeof(value_type) * n); + pointer p = (n == 0) ? 0 : m_alloc.allocate(n); + cb_details::do_fill_uninitialized_memory(p, sizeof(value_type) * n); return p; #else - return (n == 0) ? 0 : m_alloc.allocate(n, 0); + return (n == 0) ? 0 : m_alloc.allocate(n); #endif } @@ -2101,7 +2386,7 @@ private: } //! Does the pointer point to the uninitialized memory? - bool is_uninitialized(const_pointer p) const { + bool is_uninitialized(const_pointer p) const BOOST_NOEXCEPT { return p >= m_last && (m_first < m_last || p < m_first); } @@ -2113,6 +2398,14 @@ private: #endif } + //! Replace an element. + void replace(pointer pos, rvalue_type item) { + *pos = boost::move(item); +#if BOOST_CB_ENABLE_DEBUG + invalidate_iterators(iterator(this, pos)); +#endif + } + //! Construct or replace an element. /*! <code>construct</code> has to be set to <code>true</code> if and only if @@ -2120,17 +2413,29 @@ private: */ void construct_or_replace(bool construct, pointer pos, param_value_type item) { if (construct) - m_alloc.construct(pos, item); + boost::container::allocator_traits<Alloc>::construct(m_alloc, boost::addressof(*pos), item); else replace(pos, item); } + //! Construct or replace an element. + /*! + <code>construct</code> has to be set to <code>true</code> if and only if + <code>pos</code> points to an uninitialized memory. + */ + void construct_or_replace(bool construct, pointer pos, rvalue_type item) { + if (construct) + boost::container::allocator_traits<Alloc>::construct(m_alloc, boost::addressof(*pos), boost::move(item)); + else + replace(pos, boost::move(item)); + } + //! Destroy an item. void destroy_item(pointer p) { - m_alloc.destroy(p); + boost::container::allocator_traits<Alloc>::destroy(m_alloc, boost::addressof(*p)); #if BOOST_CB_ENABLE_DEBUG invalidate_iterators(iterator(this, p)); - std::memset(p, cb_details::UNINITIALIZED, sizeof(value_type)); + cb_details::do_fill_uninitialized_memory(p, sizeof(value_type)); #endif } @@ -2161,7 +2466,7 @@ private: } //! Destroy content and free allocated memory. - void destroy() { + void destroy() BOOST_NOEXCEPT { destroy_content(); deallocate(m_buff, capacity()); #if BOOST_CB_ENABLE_DEBUG @@ -2203,9 +2508,9 @@ private: void initialize(Iterator first, Iterator last, const false_type&) { BOOST_CB_IS_CONVERTIBLE(Iterator, value_type); // check for invalid iterator type #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x581)) - initialize(first, last, BOOST_ITERATOR_CATEGORY<Iterator>::type()); + initialize(first, last, iterator_category<Iterator>::type()); #else - initialize(first, last, BOOST_DEDUCED_TYPENAME BOOST_ITERATOR_CATEGORY<Iterator>::type()); + initialize(first, last, BOOST_DEDUCED_TYPENAME iterator_category<Iterator>::type()); #endif } @@ -2216,7 +2521,7 @@ private: // for containers std::deque<value_type, allocator_type> tmp(first, last, m_alloc); size_type distance = tmp.size(); - initialize(distance, tmp.begin(), tmp.end(), distance); + initialize(distance, boost::make_move_iterator(tmp.begin()), boost::make_move_iterator(tmp.end()), distance); } //! Specialized initialize method. @@ -2242,9 +2547,9 @@ private: void initialize(capacity_type buffer_capacity, Iterator first, Iterator last, const false_type&) { BOOST_CB_IS_CONVERTIBLE(Iterator, value_type); // check for invalid iterator type #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x581)) - initialize(buffer_capacity, first, last, BOOST_ITERATOR_CATEGORY<Iterator>::type()); + initialize(buffer_capacity, first, last, iterator_category<Iterator>::type()); #else - initialize(buffer_capacity, first, last, BOOST_DEDUCED_TYPENAME BOOST_ITERATOR_CATEGORY<Iterator>::type()); + initialize(buffer_capacity, first, last, BOOST_DEDUCED_TYPENAME iterator_category<Iterator>::type()); #endif } @@ -2260,7 +2565,7 @@ private: if (buffer_capacity == 0) return; while (first != last && !full()) { - m_alloc.construct(m_last, *first++); + boost::container::allocator_traits<Alloc>::construct(m_alloc, boost::addressof(*m_last), *first++); increment(m_last); ++m_size; } @@ -2296,7 +2601,7 @@ private: m_size = distance; } BOOST_TRY { - m_last = cb_details::uninitialized_copy_with_alloc(first, last, m_buff, m_alloc); + m_last = cb_details::uninitialized_copy(first, last, m_buff, m_alloc); } BOOST_CATCH(...) { deallocate(m_buff, buffer_capacity); BOOST_RETHROW @@ -2316,7 +2621,7 @@ private: } //! Specialized method for swapping the allocator. - void swap_allocator(circular_buffer<T, Alloc>& cb, const true_type&) { + void swap_allocator(circular_buffer<T, Alloc>&, const true_type&) { // Swap is not needed because allocators have no state. } @@ -2336,9 +2641,9 @@ private: void assign(Iterator first, Iterator last, const false_type&) { BOOST_CB_IS_CONVERTIBLE(Iterator, value_type); // check for invalid iterator type #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x581)) - assign(first, last, BOOST_ITERATOR_CATEGORY<Iterator>::type()); + assign(first, last, iterator_category<Iterator>::type()); #else - assign(first, last, BOOST_DEDUCED_TYPENAME BOOST_ITERATOR_CATEGORY<Iterator>::type()); + assign(first, last, BOOST_DEDUCED_TYPENAME iterator_category<Iterator>::type()); #endif } @@ -2350,8 +2655,8 @@ private: std::deque<value_type, allocator_type> tmp(first, last, m_alloc); size_type distance = tmp.size(); assign_n(distance, distance, - cb_details::assign_range<BOOST_DEDUCED_TYPENAME std::deque<value_type, allocator_type>::iterator, - allocator_type>(tmp.begin(), tmp.end(), m_alloc)); + cb_details::make_assign_range + (boost::make_move_iterator(tmp.begin()), boost::make_move_iterator(tmp.end()), m_alloc)); } //! Specialized assign method. @@ -2359,7 +2664,7 @@ private: void assign(ForwardIterator first, ForwardIterator last, const std::forward_iterator_tag&) { BOOST_CB_ASSERT(std::distance(first, last) >= 0); // check for wrong range size_type distance = std::distance(first, last); - assign_n(distance, distance, cb_details::assign_range<ForwardIterator, allocator_type>(first, last, m_alloc)); + assign_n(distance, distance, cb_details::make_assign_range(first, last, m_alloc)); } //! Specialized assign method. @@ -2373,9 +2678,9 @@ private: void assign(capacity_type new_capacity, Iterator first, Iterator last, const false_type&) { BOOST_CB_IS_CONVERTIBLE(Iterator, value_type); // check for invalid iterator type #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x581)) - assign(new_capacity, first, last, BOOST_ITERATOR_CATEGORY<Iterator>::type()); + assign(new_capacity, first, last, iterator_category<Iterator>::type()); #else - assign(new_capacity, first, last, BOOST_DEDUCED_TYPENAME BOOST_ITERATOR_CATEGORY<Iterator>::type()); + assign(new_capacity, first, last, BOOST_DEDUCED_TYPENAME iterator_category<Iterator>::type()); #endif } @@ -2386,12 +2691,7 @@ private: clear(); insert(begin(), first, last); } else { -#if BOOST_WORKAROUND(BOOST_MSVC, < 1300) - circular_buffer<value_type, allocator_type> tmp(new_capacity, m_alloc); - tmp.insert(begin(), first, last); -#else circular_buffer<value_type, allocator_type> tmp(new_capacity, first, last, m_alloc); -#endif tmp.swap(*this); } } @@ -2407,7 +2707,7 @@ private: distance = new_capacity; } assign_n(new_capacity, distance, - cb_details::assign_range<ForwardIterator, allocator_type>(first, last, m_alloc)); + cb_details::make_assign_range(first, last, m_alloc)); } //! Helper assign method. @@ -2441,10 +2741,11 @@ private: } //! Helper insert method. - iterator insert_item(const iterator& pos, param_value_type item) { + template <class ValT> + iterator insert_item(const iterator& pos, ValT item) { pointer p = pos.m_it; if (p == 0) { - construct_or_replace(!full(), m_last, item); + construct_or_replace(!full(), m_last, static_cast<ValT>(item)); p = m_last; } else { pointer src = m_last; @@ -2453,11 +2754,11 @@ private: BOOST_TRY { while (src != p) { decrement(src); - construct_or_replace(construct, dest, *src); + construct_or_replace(construct, dest, boost::move_if_noexcept(*src)); decrement(dest); construct = false; } - replace(p, item); + replace(p, static_cast<ValT>(item)); } BOOST_CATCH(...) { if (!construct && !full()) { increment(m_last); @@ -2486,9 +2787,9 @@ private: void insert(const iterator& pos, Iterator first, Iterator last, const false_type&) { BOOST_CB_IS_CONVERTIBLE(Iterator, value_type); // check for invalid iterator type #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x581)) - insert(pos, first, last, BOOST_ITERATOR_CATEGORY<Iterator>::type()); + insert(pos, first, last, iterator_category<Iterator>::type()); #else - insert(pos, first, last, BOOST_DEDUCED_TYPENAME BOOST_ITERATOR_CATEGORY<Iterator>::type()); + insert(pos, first, last, BOOST_DEDUCED_TYPENAME iterator_category<Iterator>::type()); #endif } @@ -2497,7 +2798,7 @@ private: void insert(iterator pos, InputIterator first, InputIterator last, const std::input_iterator_tag&) { if (!full() || pos != begin()) { for (;first != last; ++pos) - pos = insert_item(pos, *first++); + pos = insert(pos, *first++); } } @@ -2529,7 +2830,7 @@ private: pointer p = m_last; BOOST_TRY { for (; ii < construct; ++ii, increment(p)) - m_alloc.construct(p, *wrapper()); + boost::container::allocator_traits<Alloc>::construct(m_alloc, boost::addressof(*p), *wrapper()); for (;ii < n; ++ii, increment(p)) replace(p, *wrapper()); } BOOST_CATCH(...) { @@ -2577,9 +2878,9 @@ private: void rinsert(const iterator& pos, Iterator first, Iterator last, const false_type&) { BOOST_CB_IS_CONVERTIBLE(Iterator, value_type); // check for invalid iterator type #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x581)) - rinsert(pos, first, last, BOOST_ITERATOR_CATEGORY<Iterator>::type()); + rinsert(pos, first, last, iterator_category<Iterator>::type()); #else - rinsert(pos, first, last, BOOST_DEDUCED_TYPENAME BOOST_ITERATOR_CATEGORY<Iterator>::type()); + rinsert(pos, first, last, BOOST_DEDUCED_TYPENAME iterator_category<Iterator>::type()); #endif } @@ -2623,7 +2924,7 @@ private: for (;ii > construct; --ii, increment(p)) replace(p, *wrapper()); for (; ii > 0; --ii, increment(p)) - m_alloc.construct(p, *wrapper()); + boost::container::allocator_traits<Alloc>::construct(m_alloc, boost::addressof(*p), *wrapper()); } BOOST_CATCH(...) { size_type constructed = ii < construct ? construct - ii : 0; m_last = add(m_last, constructed); @@ -2810,7 +3111,7 @@ inline bool operator >= (const circular_buffer<T, Alloc>& lhs, const circular_bu \sa <code>\link circular_buffer::swap(circular_buffer<T, Alloc>&) swap(circular_buffer<T, Alloc>&)\endlink</code> */ template <class T, class Alloc> -inline void swap(circular_buffer<T, Alloc>& lhs, circular_buffer<T, Alloc>& rhs) { +inline void swap(circular_buffer<T, Alloc>& lhs, circular_buffer<T, Alloc>& rhs) BOOST_NOEXCEPT { lhs.swap(rhs); } diff --git a/boost/circular_buffer/debug.hpp b/boost/circular_buffer/debug.hpp index 6eb4515856..b6ab0fefbe 100644 --- a/boost/circular_buffer/debug.hpp +++ b/boost/circular_buffer/debug.hpp @@ -9,10 +9,20 @@ #if !defined(BOOST_CIRCULAR_BUFFER_DEBUG_HPP) #define BOOST_CIRCULAR_BUFFER_DEBUG_HPP -#if defined(_MSC_VER) && _MSC_VER >= 1200 +#if defined(_MSC_VER) #pragma once #endif +#if BOOST_CB_ENABLE_DEBUG +#include <cstring> + +#if defined(BOOST_NO_STDC_NAMESPACE) +namespace std { + using ::memset; +} +#endif + +#endif // BOOST_CB_ENABLE_DEBUG namespace boost { namespace cb_details { @@ -22,6 +32,17 @@ namespace cb_details { // The value the uninitialized memory is filled with. const int UNINITIALIZED = 0xcc; +template <class T> +inline void do_fill_uninitialized_memory(T* data, std::size_t size_in_bytes) BOOST_NOEXCEPT { + std::memset(static_cast<void*>(data), UNINITIALIZED, size_in_bytes); +} + +template <class T> +inline void do_fill_uninitialized_memory(T& /*data*/, std::size_t /*size_in_bytes*/) BOOST_NOEXCEPT { + // Do nothing +} + + class debug_iterator_registry; /*! diff --git a/boost/circular_buffer/details.hpp b/boost/circular_buffer/details.hpp index da25ff07ed..44ca9c9689 100644 --- a/boost/circular_buffer/details.hpp +++ b/boost/circular_buffer/details.hpp @@ -1,6 +1,7 @@ // Helper classes and functions for the circular buffer. // Copyright (c) 2003-2008 Jan Gaspar +// Copyright (c) 2014 Glen Fernandes // C++11 allocator model support. // Use, modification, and distribution is subject to the Boost Software // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at @@ -9,15 +10,27 @@ #if !defined(BOOST_CIRCULAR_BUFFER_DETAILS_HPP) #define BOOST_CIRCULAR_BUFFER_DETAILS_HPP -#if defined(_MSC_VER) && _MSC_VER >= 1200 +#if defined(_MSC_VER) #pragma once #endif #include <boost/iterator.hpp> #include <boost/throw_exception.hpp> +#include <boost/container/allocator_traits.hpp> +#include <boost/move/move.hpp> +#include <boost/type_traits/is_nothrow_move_constructible.hpp> +#include <boost/utility/addressof.hpp> #include <boost/detail/no_exceptions_support.hpp> #include <iterator> +// Silence MS /W4 warnings like C4913: +// "user defined binary operator ',' exists but no overload could convert all operands, default built-in binary operator ',' used" +// This might happen when previously including some boost headers that overload the coma operator. +#if defined(_MSC_VER) +# pragma warning(push) +# pragma warning(disable:4913) +#endif + namespace boost { namespace cb_details { @@ -29,8 +42,10 @@ void uninitialized_fill_n_with_alloc( ForwardIterator first, Diff n, const T& item, Alloc& alloc); template<class InputIterator, class ForwardIterator, class Alloc> -ForwardIterator uninitialized_copy_with_alloc( - InputIterator first, InputIterator last, ForwardIterator dest, Alloc& alloc); +ForwardIterator uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator dest, Alloc& a); + +template<class InputIterator, class ForwardIterator, class Alloc> +ForwardIterator uninitialized_move_if_noexcept(InputIterator first, InputIterator last, ForwardIterator dest, Alloc& a); /*! \struct const_traits @@ -98,7 +113,7 @@ private: */ template <class Value, class Alloc> struct assign_n { - typedef typename Alloc::size_type size_type; + typedef typename boost::container::allocator_traits<Alloc>::size_type size_type; size_type m_n; Value m_item; Alloc& m_alloc; @@ -117,19 +132,24 @@ private: */ template <class Iterator, class Alloc> struct assign_range { - const Iterator& m_first; - const Iterator& m_last; - Alloc& m_alloc; + Iterator m_first; + Iterator m_last; + Alloc& m_alloc; + assign_range(const Iterator& first, const Iterator& last, Alloc& alloc) - : m_first(first), m_last(last), m_alloc(alloc) {} + : m_first(first), m_last(last), m_alloc(alloc) {} + template <class Pointer> void operator () (Pointer p) const { - uninitialized_copy_with_alloc(m_first, m_last, p, m_alloc); + boost::cb_details::uninitialized_copy(m_first, m_last, p, m_alloc); } -private: - assign_range<Iterator, Alloc>& operator = (const assign_range<Iterator, Alloc>&); // do not generate }; +template <class Iterator, class Alloc> +inline assign_range<Iterator, Alloc> make_assign_range(const Iterator& first, const Iterator& last, Alloc& a) { + return assign_range<Iterator, Alloc>(first, last, a); +} + /*! \class capacity_control \brief Capacity controller of the space optimized circular buffer. @@ -137,18 +157,19 @@ private: template <class Size> class capacity_control { - //! The capacity of the space optimized circular buffer. + //! The capacity of the space-optimized circular buffer. Size m_capacity; - //! The lowest guaranteed capacity of the adapted circular buffer. + //! The lowest guaranteed or minimum capacity of the adapted space-optimized circular buffer. Size m_min_capacity; public: //! Constructor. capacity_control(Size buffer_capacity, Size min_buffer_capacity = 0) - : m_capacity(buffer_capacity), m_min_capacity(min_buffer_capacity) { - BOOST_CB_ASSERT(buffer_capacity >= min_buffer_capacity); // check for capacity lower than min_capacity + : m_capacity(buffer_capacity), m_min_capacity(min_buffer_capacity) + { // Check for capacity lower than min_capacity. + BOOST_CB_ASSERT(buffer_capacity >= min_buffer_capacity); } // Default copy constructor. @@ -406,45 +427,49 @@ operator + (typename Traits::difference_type n, const iterator<Buff, Traits>& it return it + n; } -#if defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION) && !defined(BOOST_MSVC_STD_ITERATOR) - -//! Iterator category. -template <class Buff, class Traits> -inline std::random_access_iterator_tag iterator_category(const iterator<Buff, Traits>&) { - return std::random_access_iterator_tag(); -} - -//! The type of the elements stored in the circular buffer. -template <class Buff, class Traits> -inline typename Traits::value_type* value_type(const iterator<Buff, Traits>&) { return 0; } - -//! Distance type. -template <class Buff, class Traits> -inline typename Traits::difference_type* distance_type(const iterator<Buff, Traits>&) { return 0; } - -#endif // #if defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION) && !defined(BOOST_MSVC_STD_ITERATOR) - /*! - \fn ForwardIterator uninitialized_copy_with_alloc(InputIterator first, InputIterator last, ForwardIterator dest, - Alloc& alloc) - \brief Equivalent of <code>std::uninitialized_copy</code> with allocator. + \fn ForwardIterator uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator dest) + \brief Equivalent of <code>std::uninitialized_copy</code> but with explicit specification of value type. */ template<class InputIterator, class ForwardIterator, class Alloc> -inline ForwardIterator uninitialized_copy_with_alloc(InputIterator first, InputIterator last, ForwardIterator dest, - Alloc& alloc) { +inline ForwardIterator uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator dest, Alloc& a) { ForwardIterator next = dest; BOOST_TRY { for (; first != last; ++first, ++dest) - alloc.construct(dest, *first); + boost::container::allocator_traits<Alloc>::construct(a, boost::addressof(*dest), *first); } BOOST_CATCH(...) { for (; next != dest; ++next) - alloc.destroy(next); + boost::container::allocator_traits<Alloc>::destroy(a, boost::addressof(*next)); BOOST_RETHROW } BOOST_CATCH_END return dest; } +template<class InputIterator, class ForwardIterator, class Alloc> +ForwardIterator uninitialized_move_if_noexcept_impl(InputIterator first, InputIterator last, ForwardIterator dest, Alloc& a, + true_type) { + for (; first != last; ++first, ++dest) + boost::container::allocator_traits<Alloc>::construct(a, boost::addressof(*dest), boost::move(*first)); + return dest; +} + +template<class InputIterator, class ForwardIterator, class Alloc> +ForwardIterator uninitialized_move_if_noexcept_impl(InputIterator first, InputIterator last, ForwardIterator dest, Alloc& a, + false_type) { + return uninitialized_copy(first, last, dest, a); +} + +/*! + \fn ForwardIterator uninitialized_move_if_noexcept(InputIterator first, InputIterator last, ForwardIterator dest) + \brief Equivalent of <code>std::uninitialized_copy</code> but with explicit specification of value type and moves elements if they have noexcept move constructors. +*/ +template<class InputIterator, class ForwardIterator, class Alloc> +ForwardIterator uninitialized_move_if_noexcept(InputIterator first, InputIterator last, ForwardIterator dest, Alloc& a) { + typedef typename boost::is_nothrow_move_constructible<typename boost::container::allocator_traits<Alloc>::value_type>::type tag_t; + return uninitialized_move_if_noexcept_impl(first, last, dest, a, tag_t()); +} + /*! \fn void uninitialized_fill_n_with_alloc(ForwardIterator first, Diff n, const T& item, Alloc& alloc) \brief Equivalent of <code>std::uninitialized_fill_n</code> with allocator. @@ -454,10 +479,10 @@ inline void uninitialized_fill_n_with_alloc(ForwardIterator first, Diff n, const ForwardIterator next = first; BOOST_TRY { for (; n > 0; ++first, --n) - alloc.construct(first, item); + boost::container::allocator_traits<Alloc>::construct(alloc, boost::addressof(*first), item); } BOOST_CATCH(...) { for (; next != first; ++next) - alloc.destroy(next); + boost::container::allocator_traits<Alloc>::destroy(alloc, boost::addressof(*next)); BOOST_RETHROW } BOOST_CATCH_END @@ -467,4 +492,8 @@ inline void uninitialized_fill_n_with_alloc(ForwardIterator first, Diff n, const } // namespace boost +#if defined(_MSC_VER) +# pragma warning(pop) +#endif + #endif // #if !defined(BOOST_CIRCULAR_BUFFER_DETAILS_HPP) diff --git a/boost/circular_buffer/space_optimized.hpp b/boost/circular_buffer/space_optimized.hpp index 9c76afe7a5..688ab95796 100644 --- a/boost/circular_buffer/space_optimized.hpp +++ b/boost/circular_buffer/space_optimized.hpp @@ -1,6 +1,8 @@ // Implementation of the circular buffer adaptor. // Copyright (c) 2003-2008 Jan Gaspar +// Copyright (c) 2013 Paul A. Bristow // Doxygen comments changed for new version of documentation. +// Copyright (c) 2013 Antony Polukhin // Move semantics implementation. // Use, modification, and distribution is subject to the Boost Software // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at @@ -9,7 +11,7 @@ #if !defined(BOOST_CIRCULAR_BUFFER_SPACE_OPTIMIZED_HPP) #define BOOST_CIRCULAR_BUFFER_SPACE_OPTIMIZED_HPP -#if defined(_MSC_VER) && _MSC_VER >= 1200 +#if defined(_MSC_VER) #pragma once #endif @@ -20,10 +22,9 @@ namespace boost { /*! \class circular_buffer_space_optimized - \brief Space optimized circular buffer container adaptor. - - For detailed documentation of the space_optimized_circular_buffer visit: - http://www.boost.org/libs/circular_buffer/doc/space_optimized.html + \brief Space optimized circular buffer container adaptor. + <code>T</code> must be a copyable class or must have an noexcept move constructor + and move assignment operator. */ template <class T, class Alloc> class circular_buffer_space_optimized : @@ -51,29 +52,53 @@ public: typedef typename circular_buffer<T, Alloc>::array_range array_range; typedef typename circular_buffer<T, Alloc>::const_array_range const_array_range; typedef typename circular_buffer<T, Alloc>::param_value_type param_value_type; - typedef typename circular_buffer<T, Alloc>::return_value_type return_value_type; + typedef typename circular_buffer<T, Alloc>::rvalue_type rvalue_type; + //typedef typename circular_buffer<T, Alloc>::return_value_type return_value_type; - //! Capacity controller of the space optimized circular buffer. - /*! - <p><pre> -class capacity_control { - size_type m_capacity; - size_type m_min_capacity; -public: - capacity_control(size_type capacity, size_type min_capacity = 0) : m_capacity(capacity), m_min_capacity(min_capacity) {}; - size_type %capacity() const { return m_capacity; } - size_type min_capacity() const { return m_min_capacity; } - operator size_type() const { return m_capacity; } -};</pre></p> - \pre <code>capacity >= min_capacity</code> - <p>The <code>capacity()</code> represents the capacity of the <code>circular_buffer_space_optimized</code> and - the <code>min_capacity()</code> determines the minimal allocated size of its internal buffer.</p> - <p>The converting constructor of the <code>capacity_control</code> allows implicit conversion from - <code>size_type</code>-like types which ensures compatibility of creating an instance of the - <code>circular_buffer_space_optimized</code> with other STL containers. On the other hand the operator - <code>%size_type()</code> provides implicit conversion to the <code>size_type</code> which allows to treat the - capacity of the <code>circular_buffer_space_optimized</code> the same way as in the - <code><a href="circular_buffer.html">circular_buffer</a></code>.</p> +/* <pre> is not passed through to html or pdf. So <br> is used in code section below. Ugly :-( +Ideally want a link to capacity_control, but this would require include details +and this would expose all the functions in details. +There must be a better way of doing this. +*/ + + /*! Capacity controller of the space optimized circular buffer. + + \see capacity_control in details.hpp. +<p> +<code> +class capacity_control<br> +{<br> + size_type m_capacity; // Available capacity.<br> + size_type m_min_capacity; // Minimum capacity.<br> +public:<br> + capacity_control(size_type capacity, size_type min_capacity = 0)<br> + : m_capacity(capacity), m_min_capacity(min_capacity)<br> + {};<br> + size_type %capacity() const { return m_capacity; }<br> + size_type min_capacity() const { return m_min_capacity; }<br> + operator size_type() const { return m_capacity; }<br> +};<br> +</code> +</p> + + + <p>Always + <code>capacity >= min_capacity</code>. + </p> + <p> + The <code>capacity()</code> represents the capacity + of the <code>circular_buffer_space_optimized</code> and + the <code>min_capacity()</code> determines the minimal allocated size of its internal buffer. + </p> + <p>The converting constructor of the <code>capacity_control</code> allows implicit conversion from + <code>size_type</code>-like types which ensures compatibility of creating an instance of the + <code>circular_buffer_space_optimized</code> with other STL containers. + + On the other hand the operator <code>%size_type()</code> + provides implicit conversion to the <code>size_type</code> which allows to treat the + capacity of the <code>circular_buffer_space_optimized</code> the same way as in the + <code>circular_buffer</a></code>. +</p> */ typedef cb_details::capacity_control<size_type> capacity_type; @@ -98,7 +123,7 @@ public: #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564)) reference operator [] (size_type n) { return circular_buffer<T, Alloc>::operator[](n); } - return_value_type operator [] (size_type n) const { return circular_buffer<T, Alloc>::operator[](n); } + const_reference operator [] (size_type n) const { return circular_buffer<T, Alloc>::operator[](n); } #else using circular_buffer<T, Alloc>::operator[]; #endif @@ -125,7 +150,7 @@ public: Constant (in the size of the <code>circular_buffer_space_optimized</code>). \sa <code>empty()</code> */ - bool full() const { return m_capacity_ctrl == size(); } + bool full() const BOOST_NOEXCEPT { return m_capacity_ctrl == size(); } /*! \brief Get the maximum number of elements which can be inserted into the <code>circular_buffer_space_optimized</code> without overwriting any of already stored elements. @@ -139,7 +164,7 @@ public: Constant (in the size of the <code>circular_buffer_space_optimized</code>). \sa <code>capacity()</code>, <code>size()</code>, <code>max_size()</code> */ - size_type reserve() const { return m_capacity_ctrl - size(); } + size_type reserve() const BOOST_NOEXCEPT { return m_capacity_ctrl - size(); } //! Get the capacity of the <code>circular_buffer_space_optimized</code>. /*! @@ -155,7 +180,7 @@ public: \sa <code>reserve()</code>, <code>size()</code>, <code>max_size()</code>, <code>set_capacity(const capacity_type&)</code> */ - const capacity_type& capacity() const { return m_capacity_ctrl; } + const capacity_type& capacity() const BOOST_NOEXCEPT { return m_capacity_ctrl; } #if defined(BOOST_CB_TEST) @@ -164,7 +189,7 @@ public: \note This method is not intended to be used directly by the user. It is defined only for testing purposes. */ - size_type internal_capacity() const { return circular_buffer<T, Alloc>::capacity(); } + size_type internal_capacity() const BOOST_NOEXCEPT { return circular_buffer<T, Alloc>::capacity(); } #endif // #if defined(BOOST_CB_TEST) @@ -178,9 +203,9 @@ public: than the new capacity then the amount of allocated memory in the internal buffer may be accommodated as necessary but it will never drop below <code>capacity_ctrl.min_capacity()</code>. \param capacity_ctrl The new capacity controller. - \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is + \throws "An allocation error" if memory is exhausted, (<code>std::bad_alloc</code> if the standard allocator is used). - \throws Whatever <code>T::T(const T&)</code> throws. + Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept. \par Exception Safety Strong. \par Iterator Invalidation @@ -222,7 +247,7 @@ public: the requested size. (See the <i>Effect</i>.) \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is used). - \throws Whatever <code>T::T(const T&)</code> throws. + Whatever <code>T::T(const T&)</code> throws. \par Exception Safety Basic. \par Iterator Invalidation @@ -257,7 +282,7 @@ public: \param capacity_ctrl The new capacity controller. \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is used). - \throws Whatever <code>T::T(const T&)</code> throws. + Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept. \par Exception Safety Strong. \par Iterator Invalidation @@ -293,7 +318,7 @@ public: the requested size. (See the <i>Effect</i>.) \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is used). - \throws Whatever <code>T::T(const T&)</code> throws. + Whatever <code>T::T(const T&)</code> throws. \par Exception Safety Basic. \par Iterator Invalidation @@ -324,7 +349,7 @@ public: \warning Since Boost version 1.36 the behaviour of this constructor has changed. Now it creates a space optimized circular buffer with zero capacity. */ - explicit circular_buffer_space_optimized(const allocator_type& alloc = allocator_type()) + explicit circular_buffer_space_optimized(const allocator_type& alloc = allocator_type()) BOOST_NOEXCEPT : circular_buffer<T, Alloc>(0, alloc) , m_capacity_ctrl(0) {} @@ -382,7 +407,7 @@ public: \param alloc The allocator. \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is used). - \throws Whatever <code>T::T(const T&)</code> throws. + Whatever <code>T::T(const T&)</code> throws. \par Complexity Linear (in the <code>n</code>). */ @@ -391,31 +416,6 @@ public: : circular_buffer<T, Alloc>(init_capacity(capacity_ctrl, n), n, item, alloc) , m_capacity_ctrl(capacity_ctrl) {} -#if BOOST_WORKAROUND(BOOST_MSVC, < 1300) - - /*! \cond */ - circular_buffer_space_optimized(const circular_buffer_space_optimized<T, Alloc>& cb) - : circular_buffer<T, Alloc>(cb.begin(), cb.end()) - , m_capacity_ctrl(cb.m_capacity_ctrl) {} - - template <class InputIterator> - circular_buffer_space_optimized(InputIterator first, InputIterator last) - : circular_buffer<T, Alloc>(first, last) - , m_capacity_ctrl(circular_buffer<T, Alloc>::capacity()) {} - - template <class InputIterator> - circular_buffer_space_optimized(capacity_type capacity_ctrl, InputIterator first, InputIterator last) - : circular_buffer<T, Alloc>( - init_capacity(capacity_ctrl, first, last, is_integral<InputIterator>()), - first, last) - , m_capacity_ctrl(capacity_ctrl) { - reduce_capacity( - is_same< BOOST_DEDUCED_TYPENAME BOOST_ITERATOR_CATEGORY<InputIterator>::type, std::input_iterator_tag >()); - } - /*! \endcond */ - -#else - //! The copy constructor. /*! Creates a copy of the specified <code>circular_buffer_space_optimized</code>. @@ -424,7 +424,7 @@ public: \param cb The <code>circular_buffer_space_optimized</code> to be copied. \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is used). - \throws Whatever <code>T::T(const T&)</code> throws. + Whatever <code>T::T(const T&)</code> throws. \par Complexity Linear (in the size of <code>cb</code>). */ @@ -432,6 +432,23 @@ public: : circular_buffer<T, Alloc>(cb.begin(), cb.end(), cb.get_allocator()) , m_capacity_ctrl(cb.m_capacity_ctrl) {} +#ifndef BOOST_NO_CXX11_RVALUE_REFERENCES + //! The move constructor. + /*! \brief Move constructs a <code>circular_buffer_space_optimized</code> from <code>cb</code>, + leaving <code>cb</code> empty. + \pre C++ compiler with rvalue references support. + \post <code>cb.empty()</code> + \param cb <code>circular_buffer</code> to 'steal' value from. + \throws Nothing. + \par Constant. + */ + circular_buffer_space_optimized(circular_buffer_space_optimized<T, Alloc>&& cb) BOOST_NOEXCEPT + : circular_buffer<T, Alloc>() + , m_capacity_ctrl(0) { + cb.swap(*this); + } +#endif // BOOST_NO_CXX11_RVALUE_REFERENCES + //! Create a full space optimized circular buffer filled with a copy of the range. /*! \pre Valid range <code>[first, last)</code>.<br> @@ -446,7 +463,8 @@ public: \param alloc The allocator. \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is used). - \throws Whatever <code>T::T(const T&)</code> throws. + Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept + and <code>InputIterator</code> is a move iterator. \par Complexity Linear (in the <code>std::distance(first, last)</code>). */ @@ -477,7 +495,7 @@ public: \param alloc The allocator. \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is used). - \throws Whatever <code>T::T(const T&)</code> throws. + Whatever <code>T::T(const T&)</code> throws. \par Complexity Linear (in <code>std::distance(first, last)</code>; in <code>min[capacity_ctrl.%capacity(), std::distance(first, last)]</code> if the <code>InputIterator</code> @@ -491,11 +509,9 @@ public: first, last, alloc) , m_capacity_ctrl(capacity_ctrl) { reduce_capacity( - is_same< BOOST_DEDUCED_TYPENAME BOOST_ITERATOR_CATEGORY<InputIterator>::type, std::input_iterator_tag >()); + is_same< BOOST_DEDUCED_TYPENAME iterator_category<InputIterator>::type, std::input_iterator_tag >()); } -#endif // #if BOOST_WORKAROUND(BOOST_MSVC, < 1300) - #if defined(BOOST_CB_NEVER_DEFINED) // This section will never be compiled - the default destructor will be generated instead. // Declared only for documentation purpose. @@ -552,6 +568,24 @@ public: return *this; } +#ifndef BOOST_NO_CXX11_RVALUE_REFERENCES + /*! \brief Move assigns content of <code>cb</code> to <code>*this</code>, leaving <code>cb</code> empty. + \pre C++ compiler with rvalue references support. + \post <code>cb.empty()</code> + \param cb <code>circular_buffer</code> to 'steal' value from. + \throws Nothing. + \par Complexity + Constant. + */ + circular_buffer_space_optimized<T, Alloc>& operator = (circular_buffer_space_optimized<T, Alloc>&& cb) BOOST_NOEXCEPT { + cb.swap(*this); // now `this` holds `cb` + circular_buffer<T, Alloc>(get_allocator()) // temprary that holds initial `cb` allocator + .swap(cb); // makes `cb` empty + return *this; + } +#endif // BOOST_NO_CXX11_RVALUE_REFERENCES + + //! Assign <code>n</code> items into the space optimized circular buffer. /*! The content of the <code>circular_buffer_space_optimized</code> will be removed and replaced with @@ -563,7 +597,7 @@ public: \param item The element the <code>circular_buffer_space_optimized</code> will be filled with. \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is used). - \throws Whatever <code>T::T(const T&)</code> throws. + Whatever <code>T::T(const T&)</code> throws. \par Exception Safety Basic. \par Iterator Invalidation @@ -596,7 +630,7 @@ public: \param item The element the <code>circular_buffer_space_optimized</code> will be filled with. \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is used). - \throws Whatever <code>T::T(const T&)</code> throws. + Whatever <code>T::T(const T&)</code> throws. \par Exception Safety Basic. \par Iterator Invalidation @@ -630,7 +664,8 @@ public: \param last The end of the range to be copied. \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is used). - \throws Whatever <code>T::T(const T&)</code> throws. + Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept and + <code>InputIterator</code> is a move iterator. \par Exception Safety Basic. \par Iterator Invalidation @@ -670,7 +705,8 @@ public: \param last The end of the range to be copied. \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is used). - \throws Whatever <code>T::T(const T&)</code> throws. + Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept and + <code>InputIterator</code> is a move iterator. \par Exception Safety Basic. \par Iterator Invalidation @@ -692,7 +728,7 @@ public: circular_buffer<T, Alloc>::assign(capacity_ctrl, first, last); } - //! Swap the contents of two space optimized circular buffers. + //! Swap the contents of two space-optimized circular-buffers. /*! \post <code>this</code> contains elements of <code>cb</code> and vice versa; the capacity and the amount of allocated memory in the internal buffer of <code>this</code> equal to the capacity and the amount of @@ -704,14 +740,18 @@ public: \par Iterator Invalidation Invalidates all iterators of both <code>circular_buffer_space_optimized</code> containers. (On the other hand the iterators still point to the same elements but within another container. If you want to rely on - this feature you have to turn the <a href="circular_buffer.html#debug">Debug Support</a> off otherwise an - assertion will report an error if such invalidated iterator is used.) + this feature you have to turn the __debug_support off by defining macro BOOST_CB_DISABLE_DEBUG, + otherwise an assertion will report an error if such invalidated iterator is used.) \par Complexity Constant (in the size of the <code>circular_buffer_space_optimized</code>). - \sa <code>\link swap(circular_buffer<T, Alloc>&, circular_buffer<T, Alloc>&) - swap(circular_buffer_space_optimized<T, Alloc>&, circular_buffer_space_optimized<T, Alloc>&)\endlink</code> + \sa <code>swap(circular_buffer<T, Alloc>&, circular_buffer<T, Alloc>&)</code>, + <code>swap(circular_buffer_space_optimized<T, Alloc>&, circular_buffer_space_optimized<T, Alloc>&)</code> + + */ - void swap(circular_buffer_space_optimized<T, Alloc>& cb) { + // Note link does not work right. Asked on Doxygen forum for advice 23 May 2103. + + void swap(circular_buffer_space_optimized<T, Alloc>& cb) BOOST_NOEXCEPT { std::swap(m_capacity_ctrl, cb.m_capacity_ctrl); circular_buffer<T, Alloc>::swap(cb); } @@ -725,7 +765,7 @@ public: \param item The element to be inserted. \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is used). - \throws Whatever <code>T::T(const T&)</code> throws. + Whatever <code>T::T(const T&)</code> throws. \par Exception Safety Basic. \par Iterator Invalidation @@ -736,11 +776,60 @@ public: \sa <code>\link push_front() push_front(const_reference)\endlink</code>, <code>pop_back()</code>, <code>pop_front()</code> */ - void push_back(param_value_type item = value_type()) { + void push_back(param_value_type item) { check_low_capacity(); circular_buffer<T, Alloc>::push_back(item); } + //! Insert a new element at the end of the space optimized circular buffer. + /*! + \post if <code>capacity().%capacity() > 0</code> then <code>back() == item</code><br> + If the <code>circular_buffer_space_optimized</code> is full, the first element will be removed. If the + capacity is <code>0</code>, nothing will be inserted.<br><br> + The amount of allocated memory in the internal buffer may be predictively increased. + \param item The element to be inserted. + \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is + used). + \par Exception Safety + Basic. + \par Iterator Invalidation + Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators + equal to <code>end()</code>). + \par Complexity + Linear (in the size of the <code>circular_buffer_space_optimized</code>). + \sa <code>\link push_front() push_front(const_reference)\endlink</code>, <code>pop_back()</code>, + <code>pop_front()</code> + */ + void push_back(rvalue_type item) { + check_low_capacity(); + circular_buffer<T, Alloc>::push_back(boost::move(item)); + } + + //! Insert a new element at the end of the space optimized circular buffer. + /*! + \post if <code>capacity().%capacity() > 0</code> then <code>back() == item</code><br> + If the <code>circular_buffer_space_optimized</code> is full, the first element will be removed. If the + capacity is <code>0</code>, nothing will be inserted.<br><br> + The amount of allocated memory in the internal buffer may be predictively increased. + \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is + used). + Whatever <code>T::T()</code> throws. + Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept. + \par Exception Safety + Basic. + \par Iterator Invalidation + Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators + equal to <code>end()</code>). + \par Complexity + Linear (in the size of the <code>circular_buffer_space_optimized</code>). + \sa <code>\link push_front() push_front(const_reference)\endlink</code>, <code>pop_back()</code>, + <code>pop_front()</code> + */ + void push_back() { + check_low_capacity(); + circular_buffer<T, Alloc>::push_back(); + } + //! Insert a new element at the beginning of the space optimized circular buffer. /*! \post if <code>capacity().%capacity() > 0</code> then <code>front() == item</code><br> @@ -750,7 +839,7 @@ public: \param item The element to be inserted. \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is used). - \throws Whatever <code>T::T(const T&)</code> throws. + Whatever <code>T::T(const T&)</code> throws. \par Exception Safety Basic. \par Iterator Invalidation @@ -761,11 +850,61 @@ public: \sa <code>\link push_back() push_back(const_reference)\endlink</code>, <code>pop_back()</code>, <code>pop_front()</code> */ - void push_front(param_value_type item = value_type()) { + void push_front(param_value_type item) { check_low_capacity(); circular_buffer<T, Alloc>::push_front(item); } + //! Insert a new element at the beginning of the space optimized circular buffer. + /*! + \post if <code>capacity().%capacity() > 0</code> then <code>front() == item</code><br> + If the <code>circular_buffer_space_optimized</code> is full, the last element will be removed. If the + capacity is <code>0</code>, nothing will be inserted.<br><br> + The amount of allocated memory in the internal buffer may be predictively increased. + \param item The element to be inserted. + \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is + used). + Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept. + \par Exception Safety + Basic. + \par Iterator Invalidation + Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators + equal to <code>end()</code>). + \par Complexity + Linear (in the size of the <code>circular_buffer_space_optimized</code>). + \sa <code>\link push_back() push_back(const_reference)\endlink</code>, <code>pop_back()</code>, + <code>pop_front()</code> + */ + void push_front(rvalue_type item) { + check_low_capacity(); + circular_buffer<T, Alloc>::push_front(boost::move(item)); + } + + //! Insert a new element at the beginning of the space optimized circular buffer. + /*! + \post if <code>capacity().%capacity() > 0</code> then <code>front() == item</code><br> + If the <code>circular_buffer_space_optimized</code> is full, the last element will be removed. If the + capacity is <code>0</code>, nothing will be inserted.<br><br> + The amount of allocated memory in the internal buffer may be predictively increased. + \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is + used). + Whatever <code>T::T()</code> throws. + Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept. + \par Exception Safety + Basic. + \par Iterator Invalidation + Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators + equal to <code>end()</code>). + \par Complexity + Linear (in the size of the <code>circular_buffer_space_optimized</code>). + \sa <code>\link push_back() push_back(const_reference)\endlink</code>, <code>pop_back()</code>, + <code>pop_front()</code> + */ + void push_front() { + check_low_capacity(); + circular_buffer<T, Alloc>::push_front(); + } + //! Remove the last element from the space optimized circular buffer. /*! \pre <code>!empty()</code> @@ -826,8 +965,8 @@ public: the <i>Effect</i>.) \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is used). - \throws Whatever <code>T::T(const T&)</code> throws. - \throws Whatever <code>T::operator = (const T&)</code> throws. + Whatever <code>T::T(const T&)</code> throws. + Whatever <code>T::operator = (const T&)</code> throws. \par Exception Safety Basic. \par Iterator Invalidation @@ -843,12 +982,88 @@ public: rinsert(iterator, size_type, value_type)\endlink</code>, <code>rinsert(iterator, InputIterator, InputIterator)</code> */ - iterator insert(iterator pos, param_value_type item = value_type()) { + iterator insert(iterator pos, param_value_type item) { size_type index = pos - begin(); check_low_capacity(); return circular_buffer<T, Alloc>::insert(begin() + index, item); } + //! Insert an element at the specified position. + /*! + \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer_space_optimized</code> or its + end. + \post The <code>item</code> will be inserted at the position <code>pos</code>.<br> + If the <code>circular_buffer_space_optimized</code> is full, the first element will be overwritten. If + the <code>circular_buffer_space_optimized</code> is full and the <code>pos</code> points to + <code>begin()</code>, then the <code>item</code> will not be inserted. If the capacity is <code>0</code>, + nothing will be inserted.<br><br> + The amount of allocated memory in the internal buffer may be predictively increased. + \param pos An iterator specifying the position where the <code>item</code> will be inserted. + \param item The element to be inserted. + \return Iterator to the inserted element or <code>begin()</code> if the <code>item</code> is not inserted. (See + the <i>Effect</i>.) + \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is + used). + Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept. + \par Exception Safety + Basic. + \par Iterator Invalidation + Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators + equal to <code>end()</code>). + \par Complexity + Linear (in the size of the <code>circular_buffer_space_optimized</code>). + \sa <code>\link insert(iterator, size_type, param_value_type) + insert(iterator, size_type, value_type)\endlink</code>, + <code>insert(iterator, InputIterator, InputIterator)</code>, + <code>\link rinsert(iterator, param_value_type) rinsert(iterator, value_type)\endlink</code>, + <code>\link rinsert(iterator, size_type, param_value_type) + rinsert(iterator, size_type, value_type)\endlink</code>, + <code>rinsert(iterator, InputIterator, InputIterator)</code> + */ + iterator insert(iterator pos, rvalue_type item) { + size_type index = pos - begin(); + check_low_capacity(); + return circular_buffer<T, Alloc>::insert(begin() + index, boost::move(item)); + } + + //! Insert an element at the specified position. + /*! + \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer_space_optimized</code> or its + end. + \post The <code>item</code> will be inserted at the position <code>pos</code>.<br> + If the <code>circular_buffer_space_optimized</code> is full, the first element will be overwritten. If + the <code>circular_buffer_space_optimized</code> is full and the <code>pos</code> points to + <code>begin()</code>, then the <code>item</code> will not be inserted. If the capacity is <code>0</code>, + nothing will be inserted.<br><br> + The amount of allocated memory in the internal buffer may be predictively increased. + \param pos An iterator specifying the position where the <code>item</code> will be inserted. + \return Iterator to the inserted element or <code>begin()</code> if the <code>item</code> is not inserted. (See + the <i>Effect</i>.) + \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is + used). + Whatever <code>T::T()</code> throws. + Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept. + \par Exception Safety + Basic. + \par Iterator Invalidation + Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators + equal to <code>end()</code>). + \par Complexity + Linear (in the size of the <code>circular_buffer_space_optimized</code>). + \sa <code>\link insert(iterator, size_type, param_value_type) + insert(iterator, size_type, value_type)\endlink</code>, + <code>insert(iterator, InputIterator, InputIterator)</code>, + <code>\link rinsert(iterator, param_value_type) rinsert(iterator, value_type)\endlink</code>, + <code>\link rinsert(iterator, size_type, param_value_type) + rinsert(iterator, size_type, value_type)\endlink</code>, + <code>rinsert(iterator, InputIterator, InputIterator)</code> + */ + iterator insert(iterator pos) { + size_type index = pos - begin(); + check_low_capacity(); + return circular_buffer<T, Alloc>::insert(begin() + index); + } + //! Insert <code>n</code> copies of the <code>item</code> at the specified position. /*! \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer_space_optimized</code> or its @@ -863,8 +1078,8 @@ public: \param item The element whose copies will be inserted. \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is used). - \throws Whatever <code>T::T(const T&)</code> throws. - \throws Whatever <code>T::operator = (const T&)</code> throws. + Whatever <code>T::T(const T&)</code> throws. + Whatever <code>T::operator = (const T&)</code> throws. \par Exception Safety Basic. \par Iterator Invalidation @@ -876,7 +1091,7 @@ public: Consider a <code>circular_buffer_space_optimized</code> with the capacity of 6 and the size of 4. Its internal buffer may look like the one below.<br><br> <code>|1|2|3|4| | |</code><br> - <code>p ---^</code><br><br>After inserting 5 elements at the position <code>p</code>:<br><br> + <code>p ___^</code><br><br>After inserting 5 elements at the position <code>p</code>:<br><br> <code>insert(p, (size_t)5, 0);</code><br><br>actually only 4 elements get inserted and elements <code>1</code> and <code>2</code> are overwritten. This is due to the fact the insert operation preserves the capacity. After insertion the internal buffer looks like this:<br><br><code>|0|0|0|0|3|4|</code><br> @@ -911,8 +1126,7 @@ public: \param last The end of the range to be inserted. \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is used). - \throws Whatever <code>T::T(const T&)</code> throws. - \throws Whatever <code>T::operator = (const T&)</code> throws. + Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept. \par Exception Safety Basic. \par Iterator Invalidation @@ -927,7 +1141,7 @@ public: Consider a <code>circular_buffer_space_optimized</code> with the capacity of 6 and the size of 4. Its internal buffer may look like the one below.<br><br> <code>|1|2|3|4| | |</code><br> - <code>p ---^</code><br><br>After inserting a range of elements at the position <code>p</code>:<br><br> + <code>p ___^</code><br><br>After inserting a range of elements at the position <code>p</code>:<br><br> <code>int array[] = { 5, 6, 7, 8, 9 };</code><br><code>insert(p, array, array + 5);</code><br><br> actually only elements <code>6</code>, <code>7</code>, <code>8</code> and <code>9</code> from the specified range get inserted and elements <code>1</code> and <code>2</code> are overwritten. This is due @@ -962,8 +1176,8 @@ public: the <i>Effect</i>.) \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is used). - \throws Whatever <code>T::T(const T&)</code> throws. - \throws Whatever <code>T::operator = (const T&)</code> throws. + Whatever <code>T::T(const T&)</code> throws. + Whatever <code>T::operator = (const T&)</code> throws. \par Exception Safety Basic. \par Iterator Invalidation @@ -979,12 +1193,88 @@ public: insert(iterator, size_type, value_type)\endlink</code>, <code>insert(iterator, InputIterator, InputIterator)</code> */ - iterator rinsert(iterator pos, param_value_type item = value_type()) { + iterator rinsert(iterator pos, param_value_type item) { size_type index = pos - begin(); check_low_capacity(); return circular_buffer<T, Alloc>::rinsert(begin() + index, item); } + //! Insert an element before the specified position. + /*! + \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer_space_optimized</code> or its + end. + \post The <code>item</code> will be inserted before the position <code>pos</code>.<br> + If the <code>circular_buffer_space_optimized</code> is full, the last element will be overwritten. If the + <code>circular_buffer_space_optimized</code> is full and the <code>pos</code> points to + <code>end()</code>, then the <code>item</code> will not be inserted. If the capacity is <code>0</code>, + nothing will be inserted.<br><br> + The amount of allocated memory in the internal buffer may be predictively increased. + \param pos An iterator specifying the position before which the <code>item</code> will be inserted. + \param item The element to be inserted. + \return Iterator to the inserted element or <code>end()</code> if the <code>item</code> is not inserted. (See + the <i>Effect</i>.) + \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is + used). + Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept. + \par Exception Safety + Basic. + \par Iterator Invalidation + Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators + equal to <code>end()</code>). + \par Complexity + Linear (in the size of the <code>circular_buffer_space_optimized</code>). + \sa <code>\link rinsert(iterator, size_type, param_value_type) + rinsert(iterator, size_type, value_type)\endlink</code>, + <code>rinsert(iterator, InputIterator, InputIterator)</code>, + <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>, + <code>\link insert(iterator, size_type, param_value_type) + insert(iterator, size_type, value_type)\endlink</code>, + <code>insert(iterator, InputIterator, InputIterator)</code> + */ + iterator rinsert(iterator pos, rvalue_type item) { + size_type index = pos - begin(); + check_low_capacity(); + return circular_buffer<T, Alloc>::rinsert(begin() + index, boost::move(item)); + } + + //! Insert an element before the specified position. + /*! + \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer_space_optimized</code> or its + end. + \post The <code>item</code> will be inserted before the position <code>pos</code>.<br> + If the <code>circular_buffer_space_optimized</code> is full, the last element will be overwritten. If the + <code>circular_buffer_space_optimized</code> is full and the <code>pos</code> points to + <code>end()</code>, then the <code>item</code> will not be inserted. If the capacity is <code>0</code>, + nothing will be inserted.<br><br> + The amount of allocated memory in the internal buffer may be predictively increased. + \param pos An iterator specifying the position before which the <code>item</code> will be inserted. + \return Iterator to the inserted element or <code>end()</code> if the <code>item</code> is not inserted. (See + the <i>Effect</i>.) + \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is + used). + Whatever <code>T::T()</code> throws. + Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept. + \par Exception Safety + Basic. + \par Iterator Invalidation + Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators + equal to <code>end()</code>). + \par Complexity + Linear (in the size of the <code>circular_buffer_space_optimized</code>). + \sa <code>\link rinsert(iterator, size_type, param_value_type) + rinsert(iterator, size_type, value_type)\endlink</code>, + <code>rinsert(iterator, InputIterator, InputIterator)</code>, + <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>, + <code>\link insert(iterator, size_type, param_value_type) + insert(iterator, size_type, value_type)\endlink</code>, + <code>insert(iterator, InputIterator, InputIterator)</code> + */ + iterator rinsert(iterator pos) { + size_type index = pos - begin(); + check_low_capacity(); + return circular_buffer<T, Alloc>::rinsert(begin() + index); + } + //! Insert <code>n</code> copies of the <code>item</code> before the specified position. /*! \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer_space_optimized</code> or its @@ -999,8 +1289,8 @@ public: \param item The element whose copies will be inserted. \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is used). - \throws Whatever <code>T::T(const T&)</code> throws. - \throws Whatever <code>T::operator = (const T&)</code> throws. + Whatever <code>T::T(const T&)</code> throws. + Whatever <code>T::operator = (const T&)</code> throws. \par Exception Safety Basic. \par Iterator Invalidation @@ -1012,7 +1302,7 @@ public: Consider a <code>circular_buffer_space_optimized</code> with the capacity of 6 and the size of 4. Its internal buffer may look like the one below.<br><br> <code>|1|2|3|4| | |</code><br> - <code>p ---^</code><br><br>After inserting 5 elements before the position <code>p</code>:<br><br> + <code>p ___^</code><br><br>After inserting 5 elements before the position <code>p</code>:<br><br> <code>rinsert(p, (size_t)5, 0);</code><br><br>actually only 4 elements get inserted and elements <code>3</code> and <code>4</code> are overwritten. This is due to the fact the rinsert operation preserves the capacity. After insertion the internal buffer looks like this:<br><br><code>|1|2|0|0|0|0|</code><br> @@ -1048,8 +1338,8 @@ public: \param last The end of the range to be inserted. \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is used). - \throws Whatever <code>T::T(const T&)</code> throws. - \throws Whatever <code>T::operator = (const T&)</code> throws. + Whatever <code>T::T(const T&)</code> throws. + Whatever <code>T::operator = (const T&)</code> throws. \par Exception Safety Basic. \par Iterator Invalidation @@ -1064,7 +1354,7 @@ public: Consider a <code>circular_buffer_space_optimized</code> with the capacity of 6 and the size of 4. Its internal buffer may look like the one below.<br><br> <code>|1|2|3|4| | |</code><br> - <code>p ---^</code><br><br>After inserting a range of elements before the position <code>p</code>:<br><br> + <code>p ___^</code><br><br>After inserting a range of elements before the position <code>p</code>:<br><br> <code>int array[] = { 5, 6, 7, 8, 9 };</code><br><code>insert(p, array, array + 5);</code><br><br> actually only elements <code>5</code>, <code>6</code>, <code>7</code> and <code>8</code> from the specified range get inserted and elements <code>3</code> and <code>4</code> are overwritten. This is due @@ -1094,7 +1384,8 @@ public: element exists. \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is used). - \throws Whatever <code>T::operator = (const T&)</code> throws. + Whatever <code>T::operator = (const T&)</code> throws or + nothing if <code>T::operator = (T&&)</code> is noexcept. \par Exception Safety Basic. \par Iterator Invalidation @@ -1124,7 +1415,8 @@ public: element exists. \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is used). - \throws Whatever <code>T::operator = (const T&)</code> throws. + Whatever <code>T::operator = (const T&)</code> throws or + nothing if <code>T::operator = (T&&)</code> is noexcept. \par Exception Safety Basic. \par Iterator Invalidation @@ -1153,7 +1445,8 @@ public: such element exists. \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is used). - \throws Whatever <code>T::operator = (const T&)</code> throws. + Whatever <code>T::operator = (const T&)</code> throws or + nothing if <code>T::operator = (T&&)</code> is noexcept. \par Exception Safety Basic. \par Iterator Invalidation @@ -1162,7 +1455,7 @@ public: \par Complexity Linear (in the size of the <code>circular_buffer_space_optimized</code>). \note Basically there is no difference between <code>erase(iterator)</code> and this method. It is implemented - only for consistency with the base <code><a href="circular_buffer.html">circular_buffer</a></code>. + only for consistency with the base <code>circular_buffer</code>. \sa <code>erase(iterator)</code>, <code>erase(iterator, iterator)</code>, <code>rerase(iterator, iterator)</code>, <code>clear()</code> */ @@ -1185,7 +1478,8 @@ public: such element exists. \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is used). - \throws Whatever <code>T::operator = (const T&)</code> throws. + Whatever <code>T::operator = (const T&)</code> throws or + nothing if <code>T::operator = (T&&)</code> is noexcept. \par Exception Safety Basic. \par Iterator Invalidation @@ -1195,7 +1489,7 @@ public: Linear (in the size of the <code>circular_buffer_space_optimized</code>). \note Basically there is no difference between <code>erase(iterator, iterator)</code> and this method. It is implemented only for consistency with the base - <code><a href="circular_buffer.html">circular_buffer</a></code>. + <code><circular_buffer</code>. \sa <code>erase(iterator)</code>, <code>erase(iterator, iterator)</code>, <code>rerase(iterator)</code>, <code>clear()</code> */ @@ -1300,7 +1594,7 @@ private: //! Specialized method for determining the initial capacity. template <class IntegralType> - static size_type init_capacity(const capacity_type& capacity_ctrl, IntegralType n, IntegralType item, + static size_type init_capacity(const capacity_type& capacity_ctrl, IntegralType n, IntegralType, const true_type&) { return init_capacity(capacity_ctrl, static_cast<size_type>(n)); } @@ -1311,16 +1605,16 @@ private: const false_type&) { BOOST_CB_IS_CONVERTIBLE(Iterator, value_type); // check for invalid iterator type #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x581)) - return init_capacity(capacity_ctrl, first, last, BOOST_ITERATOR_CATEGORY<Iterator>::type()); + return init_capacity(capacity_ctrl, first, last, iterator_category<Iterator>::type()); #else return init_capacity( - capacity_ctrl, first, last, BOOST_DEDUCED_TYPENAME BOOST_ITERATOR_CATEGORY<Iterator>::type()); + capacity_ctrl, first, last, BOOST_DEDUCED_TYPENAME iterator_category<Iterator>::type()); #endif } //! Specialized method for determining the initial capacity. template <class InputIterator> - static size_type init_capacity(const capacity_type& capacity_ctrl, InputIterator first, InputIterator last, + static size_type init_capacity(const capacity_type& capacity_ctrl, InputIterator, InputIterator, const std::input_iterator_tag&) { return capacity_ctrl.capacity(); } @@ -1414,7 +1708,7 @@ inline bool operator >= (const circular_buffer_space_optimized<T, Alloc>& lhs, //! Swap the contents of two space optimized circular buffers. template <class T, class Alloc> inline void swap(circular_buffer_space_optimized<T, Alloc>& lhs, - circular_buffer_space_optimized<T, Alloc>& rhs) { + circular_buffer_space_optimized<T, Alloc>& rhs) BOOST_NOEXCEPT { lhs.swap(rhs); } |