boost/circular_buffer/base.hpp
// Implementation of the base circular buffer. // Copyright (c) 2003-2008 Jan Gaspar // Use, modification, and distribution is subject to the Boost Software // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) #if !defined(BOOST_CIRCULAR_BUFFER_BASE_HPP) #define BOOST_CIRCULAR_BUFFER_BASE_HPP #if defined(_MSC_VER) && _MSC_VER >= 1200 #pragma once #endif #include <boost/call_traits.hpp> #include <boost/concept_check.hpp> #include <boost/limits.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 <algorithm> #include <utility> #include <deque> #if !defined(BOOST_NO_EXCEPTIONS) #include <stdexcept> #endif #if BOOST_CB_ENABLE_DEBUG #include <cstring> #endif #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>. \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>). 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> will be compared with another container. \param 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 std::allocator<T> For detailed documentation of the circular_buffer visit: http://www.boost.org/libs/circular_buffer/doc/circular_buffer.html */ template <class T, class Alloc> class circular_buffer /*! \cond */ #if BOOST_CB_ENABLE_DEBUG : public cb_details::debug_iterator_registry #endif /*! \endcond */ { // Requirements BOOST_CLASS_REQUIRE(T, boost, SGIAssignableConcept); public: // Basic types //! The type of elements stored in the <code>circular_buffer</code>. typedef typename Alloc::value_type value_type; //! A pointer to an element. typedef typename Alloc::pointer pointer; //! A const pointer to the element. typedef typename Alloc::const_pointer const_pointer; //! A reference to an element. typedef typename Alloc::reference reference; //! A const reference to an element. typedef typename 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; //! 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; //! The type of an allocator used in the <code>circular_buffer</code>. typedef Alloc allocator_type; // 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; //! 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; //! A const iterator used to iterate backwards through a <code>circular_buffer</code>. typedef boost::reverse_iterator<const_iterator> const_reverse_iterator; //! An iterator used to iterate backwards through a <code>circular_buffer</code>. typedef boost::reverse_iterator<iterator> reverse_iterator; // Container specific types //! An array range. /*! (A typedef for the <a href="http://www.sgi.com/tech/stl/pair.html"><code>std::pair</code></a> where its first element is a pointer to a beginning of an array and its second element represents a size of the array.) */ typedef std::pair<pointer, size_type> array_range; //! A range of a const array. /*! (A typedef for the <a href="http://www.sgi.com/tech/stl/pair.html"><code>std::pair</code></a> where its first element is a pointer to a beginning of a const array and its second element represents a size of the const array.) */ typedef std::pair<const_pointer, size_type> const_array_range; //! 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>.) */ 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 return the value_type from a const method. typedef typename call_traits<value_type>::param_type return_value_type; private: // Member variables //! The internal buffer used for storing elements in the circular buffer. pointer m_buff; //! The internal buffer's end (end of the storage space). pointer m_end; //! The virtual beginning of the circular buffer. pointer m_first; //! The virtual end of the circular buffer (one behind the last element). pointer m_last; //! The number of items currently stored in the circular buffer. size_type m_size; //! The allocator. allocator_type m_alloc; // Friends #if defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) friend iterator; friend const_iterator; #else template <class Buff, class Traits> friend struct cb_details::iterator; #endif public: // Allocator //! Get the allocator. /*! \return The allocator. \throws Nothing. \par Exception Safety No-throw. \par Iterator Invalidation Does not invalidate any iterators. \par Complexity 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; } //! Get the allocator reference. /*! \return A reference to the allocator. \throws Nothing. \par Exception Safety No-throw. \par Iterator Invalidation Does not invalidate any iterators. \par Complexity Constant (in the size of the <code>circular_buffer</code>). \note This method was added in order to optimize obtaining of the allocator with a state, although use of stateful allocators in STL is discouraged. \sa <code>get_allocator() const</code> */ allocator_type& get_allocator() { return m_alloc; } // Element access //! Get the iterator pointing to the beginning of the <code>circular_buffer</code>. /*! \return A random access iterator pointing to the first element of the <code>circular_buffer</code>. If the <code>circular_buffer</code> is empty it returns an iterator equal to the one returned by <code>end()</code>. \throws Nothing. \par Exception Safety No-throw. \par Iterator Invalidation Does not invalidate any iterators. \par Complexity 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); } //! Get the iterator pointing to the end of the <code>circular_buffer</code>. /*! \return A random access iterator pointing to the element "one behind" the last element of the <code> circular_buffer</code>. If the <code>circular_buffer</code> is empty it returns an iterator equal to the one returned by <code>begin()</code>. \throws Nothing. \par Exception Safety No-throw. \par Iterator Invalidation Does not invalidate any iterators. \par Complexity 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); } //! Get the const iterator pointing to the beginning of the <code>circular_buffer</code>. /*! \return A const random access iterator pointing to the first element of the <code>circular_buffer</code>. If the <code>circular_buffer</code> is empty it returns an iterator equal to the one returned by <code>end() const</code>. \throws Nothing. \par Exception Safety No-throw. \par Iterator Invalidation Does not invalidate any iterators. \par Complexity 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); } //! Get the const iterator pointing to the end of the <code>circular_buffer</code>. /*! \return A const random access iterator pointing to the element "one behind" the last element of the <code> circular_buffer</code>. If the <code>circular_buffer</code> is empty it returns an iterator equal to the one returned by <code>begin() const</code> const. \throws Nothing. \par Exception Safety No-throw. \par Iterator Invalidation Does not invalidate any iterators. \par Complexity 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); } //! Get the iterator pointing to the beginning of the "reversed" <code>circular_buffer</code>. /*! \return A reverse random access iterator pointing to the last element of the <code>circular_buffer</code>. If the <code>circular_buffer</code> is empty it returns an iterator equal to the one returned by <code>rend()</code>. \throws Nothing. \par Exception Safety No-throw. \par Iterator Invalidation Does not invalidate any iterators. \par Complexity 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()); } //! Get the iterator pointing to the end of the "reversed" <code>circular_buffer</code>. /*! \return A reverse random access iterator pointing to the element "one before" the first element of the <code> circular_buffer</code>. If the <code>circular_buffer</code> is empty it returns an iterator equal to the one returned by <code>rbegin()</code>. \throws Nothing. \par Exception Safety No-throw. \par Iterator Invalidation Does not invalidate any iterators. \par Complexity 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()); } //! Get the const iterator pointing to the beginning of the "reversed" <code>circular_buffer</code>. /*! \return A const reverse random access iterator pointing to the last element of the <code>circular_buffer</code>. If the <code>circular_buffer</code> is empty it returns an iterator equal to the one returned by <code>rend() const</code>. \throws Nothing. \par Exception Safety No-throw. \par Iterator Invalidation Does not invalidate any iterators. \par Complexity 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()); } //! Get the const iterator pointing to the end of the "reversed" <code>circular_buffer</code>. /*! \return A const reverse random access iterator pointing to the element "one before" the first element of the <code>circular_buffer</code>. If the <code>circular_buffer</code> is empty it returns an iterator equal to the one returned by <code>rbegin() const</code>. \throws Nothing. \par Exception Safety No-throw. \par Iterator Invalidation Does not invalidate any iterators. \par Complexity 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()); } //! Get the element at the <code>index</code> position. /*! \pre <code>0 \<= index \&\& index \< size()</code> \param index The position of the element. \return A reference to the element at the <code>index</code> position. \throws Nothing. \par Exception Safety No-throw. \par Iterator Invalidation Does not invalidate any iterators. \par Complexity Constant (in the size of the <code>circular_buffer</code>). \sa <code>at()</code> */ reference operator [] (size_type index) { BOOST_CB_ASSERT(index < size()); // check for invalid index return *add(m_first, index); } //! Get the element at the <code>index</code> position. /*! \pre <code>0 \<= index \&\& index \< size()</code> \param index The position of the element. \return A const reference to the element at the <code>index</code> position. \throws Nothing. \par Exception Safety No-throw. \par Iterator Invalidation Does not invalidate any iterators. \par Complexity 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 { BOOST_CB_ASSERT(index < size()); // check for invalid index return *add(m_first, index); } //! Get the element at the <code>index</code> position. /*! \param index The position of the element. \return A reference to the element at the <code>index</code> position. \throws <code>std::out_of_range</code> when the <code>index</code> is invalid (when <code>index >= size()</code>). \par Exception Safety Strong. \par Iterator Invalidation Does not invalidate any iterators. \par Complexity Constant (in the size of the <code>circular_buffer</code>). \sa <code>\link operator[](size_type) operator[] \endlink</code> */ reference at(size_type index) { check_position(index); return (*this)[index]; } //! Get the element at the <code>index</code> position. /*! \param index The position of the element. \return A const reference to the element at the <code>index</code> position. \throws <code>std::out_of_range</code> when the <code>index</code> is invalid (when <code>index >= size()</code>). \par Exception Safety Strong. \par Iterator Invalidation Does not invalidate any iterators. \par Complexity 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 { check_position(index); return (*this)[index]; } //! Get the first element. /*! \pre <code>!empty()</code> \return A reference to the first element of the <code>circular_buffer</code>. \throws Nothing. \par Exception Safety No-throw. \par Iterator Invalidation Does not invalidate any iterators. \par Complexity Constant (in the size of the <code>circular_buffer</code>). \sa <code>back()</code> */ reference front() { BOOST_CB_ASSERT(!empty()); // check for empty buffer (front element not available) return *m_first; } //! Get the last element. /*! \pre <code>!empty()</code> \return A reference to the last element of the <code>circular_buffer</code>. \throws Nothing. \par Exception Safety No-throw. \par Iterator Invalidation Does not invalidate any iterators. \par Complexity Constant (in the size of the <code>circular_buffer</code>). \sa <code>front()</code> */ reference back() { BOOST_CB_ASSERT(!empty()); // check for empty buffer (back element not available) return *((m_last == m_buff ? m_end : m_last) - 1); } //! Get the first element. /*! \pre <code>!empty()</code> \return A const reference to the first element of the <code>circular_buffer</code>. \throws Nothing. \par Exception Safety No-throw. \par Iterator Invalidation Does not invalidate any iterators. \par Complexity Constant (in the size of the <code>circular_buffer</code>). \sa <code>back() const</code> */ return_value_type front() const { BOOST_CB_ASSERT(!empty()); // check for empty buffer (front element not available) return *m_first; } //! Get the last element. /*! \pre <code>!empty()</code> \return A const reference to the last element of the <code>circular_buffer</code>. \throws Nothing. \par Exception Safety No-throw. \par Iterator Invalidation Does not invalidate any iterators. \par Complexity Constant (in the size of the <code>circular_buffer</code>). \sa <code>front() const</code> */ return_value_type back() const { BOOST_CB_ASSERT(!empty()); // check for empty buffer (back element not available) return *((m_last == m_buff ? m_end : m_last) - 1); } //! Get the first continuous array of the internal buffer. /*! This method in combination with <code>array_two()</code> can be useful when passing the stored data into a legacy C API as an array. Suppose there is a <code>circular_buffer</code> of capacity 10, containing 7 characters <code>'a', 'b', ..., 'g'</code> where <code>buff[0] == 'a'</code>, <code>buff[1] == 'b'</code>, ... and <code>buff[6] == 'g'</code>:<br><br> <code>circular_buffer<char> buff(10);</code><br><br> 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> 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> <code>int write(int file_desc, char* buff, int num_bytes);</code><br><br> There are two ways how to write the content of the <code>circular_buffer</code> into a file. Either relying on <code>array_one()</code> and <code>array_two()</code> methods and calling the write function twice:<br><br> <code>array_range ar = buff.array_one();<br> write(file_desc, ar.first, ar.second);<br> ar = buff.array_two();<br> write(file_desc, ar.first, ar.second);</code><br><br> Or relying on the <code>linearize()</code> method:<br><br><code> write(file_desc, buff.linearize(), buff.size());</code><br><br> Since the complexity of <code>array_one()</code> and <code>array_two()</code> methods is constant the first option is suitable when calling the write method is "cheap". On the other hand the second option is more suitable when calling the write method is more "expensive" than calling the <code>linearize()</code> method whose complexity is linear. \return The array range of the first continuous array of the internal buffer. In the case the <code>circular_buffer</code> is empty the size of the returned array is <code>0</code>. \throws Nothing. \par Exception Safety No-throw. \par Iterator Invalidation Does not invalidate any iterators. \par Complexity Constant (in the size of the <code>circular_buffer</code>). \warning In general invoking any method which modifies the internal state of the circular_buffer may delinearize the internal buffer and invalidate the array ranges returned by <code>array_one()</code> and <code>array_two()</code> (and their const versions). \note In the case the internal buffer is linear e.g. <code>|a|b|c|d|e|f|g| | | |</code> the "array one" is represented by <code>|a|b|c|d|e|f|g|</code> and the "array two" does not exist (the <code>array_two()</code> method returns an array with the size <code>0</code>). \sa <code>array_two()</code>, <code>linearize()</code> */ array_range array_one() { return array_range(m_first, (m_last <= m_first && !empty() ? m_end : m_last) - m_first); } //! Get the second continuous array of the internal buffer. /*! This method in combination with <code>array_one()</code> can be useful when passing the stored data into a legacy C API as an array. \return The array range of the second continuous array of the internal buffer. In the case the internal buffer is linear or the <code>circular_buffer</code> is empty the size of the returned array is <code>0</code>. \throws Nothing. \par Exception Safety No-throw. \par Iterator Invalidation Does not invalidate any iterators. \par Complexity Constant (in the size of the <code>circular_buffer</code>). \sa <code>array_one()</code> */ array_range array_two() { return array_range(m_buff, m_last <= m_first && !empty() ? m_last - m_buff : 0); } //! Get the first continuous array of the internal buffer. /*! This method in combination with <code>array_two() const</code> can be useful when passing the stored data into a legacy C API as an array. \return The array range of the first continuous array of the internal buffer. In the case the <code>circular_buffer</code> is empty the size of the returned array is <code>0</code>. \throws Nothing. \par Exception Safety No-throw. \par Iterator Invalidation Does not invalidate any iterators. \par Complexity Constant (in the size of the <code>circular_buffer</code>). \sa <code>array_two() const</code>; <code>array_one()</code> for more details how to pass data into a legacy C API. */ const_array_range array_one() const { return const_array_range(m_first, (m_last <= m_first && !empty() ? m_end : m_last) - m_first); } //! Get the second continuous array of the internal buffer. /*! This method in combination with <code>array_one() const</code> can be useful when passing the stored data into a legacy C API as an array. \return The array range of the second continuous array of the internal buffer. In the case the internal buffer is linear or the <code>circular_buffer</code> is empty the size of the returned array is <code>0</code>. \throws Nothing. \par Exception Safety No-throw. \par Iterator Invalidation Does not invalidate any iterators. \par Complexity Constant (in the size of the <code>circular_buffer</code>). \sa <code>array_one() const</code> */ const_array_range array_two() const { return const_array_range(m_buff, m_last <= m_first && !empty() ? m_last - m_buff : 0); } //! Linearize the internal buffer into a continuous array. /*! 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. \par Exception Safety Basic; no-throw if the operations in the <i>Throws</i> section do not throw anything. \par Iterator Invalidation Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to <code>end()</code>); does not invalidate any iterators if the postcondition (the <i>Effect</i>) is already met prior calling this method. \par Complexity Linear (in the size of the <code>circular_buffer</code>); constant if the postcondition (the <i>Effect</i>) is already met. \warning In general invoking any method which modifies the internal state of the <code>circular_buffer</code> may delinearize the internal buffer and invalidate the returned pointer. \sa <code>array_one()</code> and <code>array_two()</code> for the other option how to pass data into a legacy C API; <code>is_linearized()</code>, <code>rotate(const_iterator)</code> */ pointer linearize() { if (empty()) return 0; if (m_first < m_last || m_last == m_buff) return m_first; pointer src = m_first; pointer dest = m_buff; size_type moved = 0; size_type constructed = 0; BOOST_TRY { for (pointer first = m_first; dest < src; src = first) { for (size_type ii = 0; src < m_end; ++src, ++dest, ++moved, ++ii) { if (moved == size()) { first = dest; break; } if (dest == first) { first += ii; break; } if (is_uninitialized(dest)) { m_alloc.construct(dest, *src); ++constructed; } else { value_type tmp = *src; replace(src, *dest); replace(dest, tmp); } } } } BOOST_CATCH(...) { m_last += constructed; m_size += constructed; BOOST_RETHROW } BOOST_CATCH_END for (src = m_end - constructed; src < m_end; ++src) destroy_item(src); m_first = m_buff; m_last = add(m_buff, size()); #if BOOST_CB_ENABLE_DEBUG invalidate_iterators_except(end()); #endif return m_buff; } //! Is the <code>circular_buffer</code> linearized? /*! \return <code>true</code> if the internal buffer is linearized into a continuous array (i.e. the <code>circular_buffer</code> meets a condition <code>\&(*this)[0] \< \&(*this)[1] \< ... \< \&(*this)[size() - 1]</code>); <code>false</code> otherwise. \throws Nothing. \par Exception Safety No-throw. \par Iterator Invalidation Does not invalidate any iterators. \par Complexity 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; } //! Rotate elements in the <code>circular_buffer</code>. /*! A more effective implementation of <code><a href="http://www.sgi.com/tech/stl/rotate.html">std::rotate</a></code>. \pre <code>new_begin</code> is a valid iterator pointing to the <code>circular_buffer</code> <b>except</b> its end. \post Before calling the method suppose:<br><br> <code>m == std::distance(new_begin, end())</code><br><code>n == std::distance(begin(), new_begin)</code> <br><code>val_0 == *new_begin, val_1 == *(new_begin + 1), ... val_m == *(new_begin + m)</code><br> <code>val_r1 == *(new_begin - 1), val_r2 == *(new_begin - 2), ... val_rn == *(new_begin - n)</code><br> <br>then after call to the method:<br><br> <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. \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. \par Iterator Invalidation If <code>m \< n</code> invalidates iterators pointing to the last <code>m</code> elements (<b>including</b> <code>new_begin</code>, but not iterators equal to <code>end()</code>) else invalidates iterators pointing to the first <code>n</code> elements; does not invalidate any iterators if the <code>circular_buffer</code> is full. \par Complexity Linear (in <code>(std::min)(m, n)</code>); constant if the <code>circular_buffer</code> is full. \sa <code><a href="http://www.sgi.com/tech/stl/rotate.html">std::rotate</a></code> */ void rotate(const_iterator new_begin) { BOOST_CB_ASSERT(new_begin.is_valid(this)); // check for uninitialized or invalidated iterator BOOST_CB_ASSERT(new_begin.m_it != 0); // check for iterator pointing to end() if (full()) { m_first = m_last = const_cast<pointer>(new_begin.m_it); } else { difference_type m = end() - new_begin; difference_type n = new_begin - begin(); if (m < n) { for (; m > 0; --m) { push_front(back()); pop_back(); } } else { for (; n > 0; --n) { push_back(front()); pop_front(); } } } } // Size and capacity //! Get the number of elements currently stored in the <code>circular_buffer</code>. /*! \return The number of elements stored in the <code>circular_buffer</code>. \throws Nothing. \par Exception Safety No-throw. \par Iterator Invalidation Does not invalidate any iterators. \par Complexity Constant (in the size of the <code>circular_buffer</code>). \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; } /*! \brief Get the largest possible size or capacity of the <code>circular_buffer</code>. (It depends on allocator's %max_size()). \return The maximum size/capacity the <code>circular_buffer</code> can be set to. \throws Nothing. \par Exception Safety No-throw. \par Iterator Invalidation Does not invalidate any iterators. \par Complexity 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)()); } //! Is the <code>circular_buffer</code> empty? /*! \return <code>true</code> if there are no elements stored in the <code>circular_buffer</code>; <code>false</code> otherwise. \throws Nothing. \par Exception Safety No-throw. \par Iterator Invalidation Does not invalidate any iterators. \par Complexity Constant (in the size of the <code>circular_buffer</code>). \sa <code>full()</code> */ bool empty() const { return size() == 0; } //! Is the <code>circular_buffer</code> full? /*! \return <code>true</code> if the number of elements stored in the <code>circular_buffer</code> equals the capacity of the <code>circular_buffer</code>; <code>false</code> otherwise. \throws Nothing. \par Exception Safety No-throw. \par Iterator Invalidation Does not invalidate any iterators. \par Complexity Constant (in the size of the <code>circular_buffer</code>). \sa <code>empty()</code> */ bool full() const { 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. \return <code>capacity() - size()</code> \throws Nothing. \par Exception Safety No-throw. \par Iterator Invalidation Does not invalidate any iterators. \par Complexity 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(); } //! Get the capacity of the <code>circular_buffer</code>. /*! \return The maximum number of elements which can be stored in the <code>circular_buffer</code>. \throws Nothing. \par Exception Safety No-throw. \par Iterator Invalidation Does not invalidate any iterators. \par Complexity Constant (in the size of the <code>circular_buffer</code>). \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; } //! Change the capacity of the <code>circular_buffer</code>. /*! \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 used). \throws Whatever <code>T::T(const T&)</code> throws. \par Exception Safety Strong. \par Iterator Invalidation Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to <code>end()</code>) if the new capacity is different from the original. \par Complexity Linear (in <code>min[size(), new_capacity]</code>). \sa <code>rset_capacity(capacity_type)</code>, <code>\link resize() resize(size_type, const_reference)\endlink</code> */ void set_capacity(capacity_type new_capacity) { if (new_capacity == capacity()) return; pointer buff = allocate(new_capacity); iterator b = begin(); BOOST_TRY { reset(buff, cb_details::uninitialized_copy_with_alloc(b, b + (std::min)(new_capacity, size()), buff, m_alloc), new_capacity); } BOOST_CATCH(...) { deallocate(buff, new_capacity); BOOST_RETHROW } BOOST_CATCH_END } //! Change the size of the <code>circular_buffer</code>. /*! \post <code>size() == new_size \&\& capacity() >= new_size</code><br><br> If the new size is greater than the current size, copies of <code>item</code> will be inserted at the <b>back</b> of the of the <code>circular_buffer</code> in order to achieve the desired size. In the case the resulting size exceeds the current capacity the capacity will be set to <code>new_size</code>.<br> If the current number of elements stored in the <code>circular_buffer</code> is greater than the desired new size then number of <code>[size() - new_size]</code> <b>last</b> elements will be removed. (The capacity will remain unchanged.) \param new_size The new size. \param item The element the <code>circular_buffer</code> will be filled with in order to gain 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. \par Exception Safety Basic. \par Iterator Invalidation Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to <code>end()</code>) if the new size is greater than the current capacity. Invalidates iterators pointing to the removed elements if the new size is lower that the original size. Otherwise it does not invalidate any iterator. \par Complexity Linear (in the new size of the <code>circular_buffer</code>). \sa <code>\link rresize() rresize(size_type, const_reference)\endlink</code>, <code>set_capacity(capacity_type)</code> */ void resize(size_type new_size, param_value_type item = value_type()) { if (new_size > size()) { if (new_size > capacity()) set_capacity(new_size); insert(end(), new_size - size(), item); } else { iterator e = end(); erase(e - (size() - new_size), e); } } //! Change the capacity of the <code>circular_buffer</code>. /*! \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 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 used). \throws Whatever <code>T::T(const T&)</code> throws. \par Exception Safety Strong. \par Iterator Invalidation Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to <code>end()</code>) if the new capacity is different from the original. \par Complexity Linear (in <code>min[size(), new_capacity]</code>). \sa <code>set_capacity(capacity_type)</code>, <code>\link rresize() rresize(size_type, const_reference)\endlink</code> */ void rset_capacity(capacity_type new_capacity) { if (new_capacity == capacity()) return; pointer buff = allocate(new_capacity); iterator e = end(); BOOST_TRY { reset(buff, cb_details::uninitialized_copy_with_alloc(e - (std::min)(new_capacity, size()), e, buff, m_alloc), new_capacity); } BOOST_CATCH(...) { deallocate(buff, new_capacity); BOOST_RETHROW } BOOST_CATCH_END } //! Change the size of the <code>circular_buffer</code>. /*! \post <code>size() == new_size \&\& capacity() >= new_size</code><br><br> If the new size is greater than the current size, copies of <code>item</code> will be inserted at the <b>front</b> of the of the <code>circular_buffer</code> in order to achieve the desired size. In the case the resulting size exceeds the current capacity the capacity will be set to <code>new_size</code>.<br> If the current number of elements stored in the <code>circular_buffer</code> is greater than the desired new size then number of <code>[size() - new_size]</code> <b>first</b> elements will be removed. (The capacity will remain unchanged.) \param new_size The new size. \param item The element the <code>circular_buffer</code> will be filled with in order to gain 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. \par Exception Safety Basic. \par Iterator Invalidation Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to <code>end()</code>) if the new size is greater than the current capacity. Invalidates iterators pointing to the removed elements if the new size is lower that the original size. Otherwise it does not invalidate any iterator. \par Complexity Linear (in the new size of the <code>circular_buffer</code>). \sa <code>\link resize() resize(size_type, const_reference)\endlink</code>, <code>rset_capacity(capacity_type)</code> */ void rresize(size_type new_size, param_value_type item = value_type()) { if (new_size > size()) { if (new_size > capacity()) set_capacity(new_size); rinsert(begin(), new_size - size(), item); } else { rerase(begin(), end() - new_size); } } // Construction/Destruction //! Create an empty <code>circular_buffer</code> with zero capacity. /*! \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). \par Complexity Constant. \warning Since Boost version 1.36 the behaviour of this constructor has changed. Now the constructor does not allocate any memory and both capacity and size are set to zero. Also note when inserting an element into a <code>circular_buffer</code> with zero capacity (e.g. by <code>\link push_back() push_back(const_reference)\endlink</code> or <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>) nothing will be inserted and the size (as well as capacity) remains zero. \note You can explicitly set the capacity by calling the <code>set_capacity(capacity_type)</code> method or you can use the other constructor with the capacity specified. \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()) : 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. /*! \post <code>capacity() == buffer_capacity \&\& size() == 0</code> \param buffer_capacity The maximum number of elements which can be stored in the <code>circular_buffer</code>. \param alloc The allocator. \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is used). \par Complexity Constant. */ explicit circular_buffer(capacity_type buffer_capacity, const allocator_type& alloc = allocator_type()) : m_size(0), m_alloc(alloc) { initialize_buffer(buffer_capacity); m_first = m_last = m_buff; } /*! \brief Create a full <code>circular_buffer</code> with the specified capacity and filled with <code>n</code> copies of <code>item</code>. \post <code>capacity() == n \&\& full() \&\& (*this)[0] == item \&\& (*this)[1] == item \&\& ... \&\& (*this)[n - 1] == item </code> \param n The number of elements the created <code>circular_buffer</code> will be filled with. \param item The element the created <code>circular_buffer</code> will be filled with. \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. \par Complexity Linear (in the <code>n</code>). */ circular_buffer(size_type n, param_value_type item, const allocator_type& alloc = allocator_type()) : m_size(n), m_alloc(alloc) { initialize_buffer(n, item); m_first = m_last = m_buff; } /*! \brief Create a <code>circular_buffer</code> with the specified capacity and filled with <code>n</code> copies of <code>item</code>. \pre <code>buffer_capacity >= n</code> \post <code>capacity() == buffer_capacity \&\& size() == n \&\& (*this)[0] == item \&\& (*this)[1] == item \&\& ... \&\& (*this)[n - 1] == item</code> \param buffer_capacity The capacity of the created <code>circular_buffer</code>. \param n The number of elements the created <code>circular_buffer</code> will be filled with. \param item The element the created <code>circular_buffer</code> will be filled with. \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. \par Complexity Linear (in the <code>n</code>). */ circular_buffer(capacity_type buffer_capacity, size_type n, param_value_type item, const allocator_type& alloc = allocator_type()) : m_size(n), m_alloc(alloc) { BOOST_CB_ASSERT(buffer_capacity >= size()); // check for capacity lower than size initialize_buffer(buffer_capacity, item); m_first = m_buff; m_last = buffer_capacity == n ? m_buff : m_buff + n; } //! The copy constructor. /*! Creates a copy of the specified <code>circular_buffer</code>. \post <code>*this == cb</code> \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. \par Complexity Linear (in the size of <code>cb</code>). */ circular_buffer(const circular_buffer<T, Alloc>& cb) : #if BOOST_CB_ENABLE_DEBUG debug_iterator_registry(), #endif m_size(cb.size()), m_alloc(cb.get_allocator()) { 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); } BOOST_CATCH(...) { deallocate(m_buff, cb.capacity()); BOOST_RETHROW } BOOST_CATCH_END 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>()); } /*! \endcond */ #else //! Create a full <code>circular_buffer</code> filled with a copy of the range. /*! \pre Valid range <code>[first, last)</code>.<br> <code>first</code> and <code>last</code> have to meet the requirements of <a href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>. \post <code>capacity() == std::distance(first, last) \&\& full() \&\& (*this)[0]== *first \&\& (*this)[1] == *(first + 1) \&\& ... \&\& (*this)[std::distance(first, last) - 1] == *(last - 1)</code> \param first The beginning of the range to be copied. \param last The end of the range to be copied. \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. \par Complexity Linear (in the <code>std::distance(first, last)</code>). */ template <class InputIterator> circular_buffer(InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type()) : m_alloc(alloc) { initialize(first, last, is_integral<InputIterator>()); } //! Create a <code>circular_buffer</code> with the specified capacity and filled with a copy of the range. /*! \pre Valid range <code>[first, last)</code>.<br> <code>first</code> and <code>last</code> have to meet the requirements of <a href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>. \post <code>capacity() == buffer_capacity \&\& size() \<= std::distance(first, last) \&\& (*this)[0]== *(last - buffer_capacity) \&\& (*this)[1] == *(last - buffer_capacity + 1) \&\& ... \&\& (*this)[buffer_capacity - 1] == *(last - 1)</code><br><br> If the number of items to be copied from the range <code>[first, last)</code> is greater than the specified <code>buffer_capacity</code> then only elements from the range <code>[last - buffer_capacity, last)</code> will be copied. \param buffer_capacity The capacity of the created <code>circular_buffer</code>. \param first The beginning of the range to be copied. \param last The end of the range to be copied. \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. \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 <a href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">RandomAccessIterator</a>). */ template <class InputIterator> circular_buffer(capacity_type buffer_capacity, InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type()) : m_alloc(alloc) { initialize(buffer_capacity, first, last, is_integral<InputIterator>()); } #endif // #if BOOST_WORKAROUND(BOOST_MSVC, < 1300) //! The destructor. /*! Destroys the <code>circular_buffer</code>. \throws Nothing. \par Iterator Invalidation Invalidates all iterators pointing to the <code>circular_buffer</code> (including iterators equal to <code>end()</code>). \par Complexity Constant (in the size of the <code>circular_buffer</code>) for scalar types; linear for other types. \sa <code>clear()</code> */ ~circular_buffer() { destroy(); #if BOOST_CB_ENABLE_DEBUG invalidate_all_iterators(); #endif } public: // Assign methods //! The assign operator. /*! Makes this <code>circular_buffer</code> to become a copy of the specified <code>circular_buffer</code>. \post <code>*this == cb</code> \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. \par Exception Safety Strong. \par Iterator Invalidation Invalidates all iterators pointing to this <code>circular_buffer</code> (except iterators equal to <code>end()</code>). \par Complexity Linear (in the size of <code>cb</code>). \sa <code>\link assign(size_type, param_value_type) assign(size_type, const_reference)\endlink</code>, <code>\link assign(capacity_type, size_type, param_value_type) assign(capacity_type, size_type, const_reference)\endlink</code>, <code>assign(InputIterator, InputIterator)</code>, <code>assign(capacity_type, InputIterator, InputIterator)</code> */ circular_buffer<T, Alloc>& operator = (const circular_buffer<T, Alloc>& cb) { if (this == &cb) 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()); } BOOST_CATCH(...) { deallocate(buff, cb.capacity()); BOOST_RETHROW } BOOST_CATCH_END return *this; } //! 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 <code>item</code>. \post <code>capacity() == n \&\& size() == n \&\& (*this)[0] == item \&\& (*this)[1] == item \&\& ... \&\& (*this) [n - 1] == item</code> \param n The number of elements the <code>circular_buffer</code> will be filled with. \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. \par Exception Safety Basic. \par Iterator Invalidation Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to <code>end()</code>). \par Complexity Linear (in the <code>n</code>). \sa <code>\link operator=(const circular_buffer&) operator=\endlink</code>, <code>\link assign(capacity_type, size_type, param_value_type) assign(capacity_type, size_type, const_reference)\endlink</code>, <code>assign(InputIterator, InputIterator)</code>, <code>assign(capacity_type, InputIterator, InputIterator)</code> */ void assign(size_type n, param_value_type item) { assign_n(n, n, cb_details::assign_n<param_value_type, allocator_type>(n, item, m_alloc)); } //! Assign <code>n</code> items into the <code>circular_buffer</code> specifying the capacity. /*! The capacity of the <code>circular_buffer</code> will be set to the specified value and the content of the <code>circular_buffer</code> will be removed and replaced with <code>n</code> copies of the <code>item</code>. \pre <code>capacity >= n</code> \post <code>capacity() == buffer_capacity \&\& size() == n \&\& (*this)[0] == item \&\& (*this)[1] == item \&\& ... \&\& (*this) [n - 1] == item </code> \param buffer_capacity The new capacity. \param n The number of elements the <code>circular_buffer</code> will be filled with. \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. \par Exception Safety Basic. \par Iterator Invalidation Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to <code>end()</code>). \par Complexity Linear (in the <code>n</code>). \sa <code>\link operator=(const circular_buffer&) operator=\endlink</code>, <code>\link assign(size_type, param_value_type) assign(size_type, const_reference)\endlink</code>, <code>assign(InputIterator, InputIterator)</code>, <code>assign(capacity_type, InputIterator, InputIterator)</code> */ void assign(capacity_type buffer_capacity, size_type n, param_value_type item) { BOOST_CB_ASSERT(buffer_capacity >= n); // check for new capacity lower than n assign_n(buffer_capacity, n, cb_details::assign_n<param_value_type, allocator_type>(n, item, m_alloc)); } //! Assign a copy of the range into the <code>circular_buffer</code>. /*! The content of the <code>circular_buffer</code> will be removed and replaced with copies of elements from the specified range. \pre Valid range <code>[first, last)</code>.<br> <code>first</code> and <code>last</code> have to meet the requirements of <a href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>. \post <code>capacity() == std::distance(first, last) \&\& size() == std::distance(first, last) \&\& (*this)[0]== *first \&\& (*this)[1] == *(first + 1) \&\& ... \&\& (*this)[std::distance(first, last) - 1] == *(last - 1)</code> \param first The beginning of the range to be copied. \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. \par Exception Safety Basic. \par Iterator Invalidation Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to <code>end()</code>). \par Complexity Linear (in the <code>std::distance(first, last)</code>). \sa <code>\link operator=(const circular_buffer&) operator=\endlink</code>, <code>\link assign(size_type, param_value_type) assign(size_type, const_reference)\endlink</code>, <code>\link assign(capacity_type, size_type, param_value_type) assign(capacity_type, size_type, const_reference)\endlink</code>, <code>assign(capacity_type, InputIterator, InputIterator)</code> */ template <class InputIterator> void assign(InputIterator first, InputIterator last) { assign(first, last, is_integral<InputIterator>()); } //! Assign a copy of the range into the <code>circular_buffer</code> specifying the capacity. /*! The capacity of the <code>circular_buffer</code> will be set to the specified value and the content of the <code>circular_buffer</code> will be removed and replaced with copies of elements from the specified range. \pre Valid range <code>[first, last)</code>.<br> <code>first</code> and <code>last</code> have to meet the requirements of <a href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>. \post <code>capacity() == buffer_capacity \&\& size() \<= std::distance(first, last) \&\& (*this)[0]== *(last - buffer_capacity) \&\& (*this)[1] == *(last - buffer_capacity + 1) \&\& ... \&\& (*this)[buffer_capacity - 1] == *(last - 1)</code><br><br> If the number of items to be copied from the range <code>[first, last)</code> is greater than the specified <code>buffer_capacity</code> then only elements from the range <code>[last - buffer_capacity, last)</code> will be copied. \param buffer_capacity The new capacity. \param first The beginning of the range to be copied. \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. \par Exception Safety Basic. \par Iterator Invalidation Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to <code>end()</code>). \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 <a href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">RandomAccessIterator</a>). \sa <code>\link operator=(const circular_buffer&) operator=\endlink</code>, <code>\link assign(size_type, param_value_type) assign(size_type, const_reference)\endlink</code>, <code>\link assign(capacity_type, size_type, param_value_type) assign(capacity_type, size_type, const_reference)\endlink</code>, <code>assign(InputIterator, InputIterator)</code> */ template <class InputIterator> void assign(capacity_type buffer_capacity, InputIterator first, InputIterator last) { assign(buffer_capacity, first, last, is_integral<InputIterator>()); } //! Swap the contents of two <code>circular_buffer</code>s. /*! \post <code>this</code> contains elements of <code>cb</code> and vice versa; the capacity of <code>this</code> equals to the capacity of <code>cb</code> and vice versa. \param cb The <code>circular_buffer</code> whose content will be swapped. \throws Nothing. \par Exception Safety No-throw. \par Iterator Invalidation Invalidates all iterators of both <code>circular_buffer</code>s. (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="#debug">Debug Support</a> off otherwise an assertion will report an error if such invalidated iterator is used.) \par Complexity 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) { swap_allocator(cb, is_stateless<allocator_type>()); std::swap(m_buff, cb.m_buff); std::swap(m_end, cb.m_end); std::swap(m_first, cb.m_first); std::swap(m_last, cb.m_last); std::swap(m_size, cb.m_size); #if BOOST_CB_ENABLE_DEBUG invalidate_all_iterators(); cb.invalidate_all_iterators(); #endif } // push and pop //! 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> 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(const T&)</code> throws. \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 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(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; } } //! Insert a new 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. \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. \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(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 } //! Remove the last element from the <code>circular_buffer</code>. /*! \pre <code>!empty()</code> \post The last element is removed from the <code>circular_buffer</code>. \throws Nothing. \par Exception Safety No-throw. \par Iterator Invalidation Invalidates only iterators pointing to the removed element. \par Complexity Constant (in the size of the <code>circular_buffer</code>). \sa <code>pop_front()</code>, <code>\link push_back() push_back(const_reference)\endlink</code>, <code>\link push_front() push_front(const_reference)\endlink</code> */ void pop_back() { BOOST_CB_ASSERT(!empty()); // check for empty buffer (back element not available) decrement(m_last); destroy_item(m_last); --m_size; } //! Remove the first element from the <code>circular_buffer</code>. /*! \pre <code>!empty()</code> \post The first element is removed from the <code>circular_buffer</code>. \throws Nothing. \par Exception Safety No-throw. \par Iterator Invalidation Invalidates only iterators pointing to the removed element. \par Complexity Constant (in the size of the <code>circular_buffer</code>). \sa <code>pop_back()</code>, <code>\link push_back() push_back(const_reference)\endlink</code>, <code>\link push_front() push_front(const_reference)\endlink</code> */ void pop_front() { BOOST_CB_ASSERT(!empty()); // check for empty buffer (front element not available) destroy_item(m_first); increment(m_first); --m_size; } public: // Insert //! 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(const T&)</code> throws. \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 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, 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); } //! 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</code> or its end. \post The number of <code>min[n, (pos - begin()) + reserve()]</code> elements will be inserted at the position <code>pos</code>.<br>The number of <code>min[pos - begin(), max[0, n - reserve()]]</code> elements will be overwritten at the beginning of the <code>circular_buffer</code>.<br>(See <i>Example</i> for the explanation.) \param pos An iterator specifying the position where the <code>item</code>s will be inserted. \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. \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 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 elements. \par Complexity Linear (in <code>min[capacity(), std::distance(pos, end()) + n]</code>). \par Example 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>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> <br>For comparison if the capacity would not be preserved the internal buffer would then result in <code>|1|2|0|0|0|0|0|3|4|</code>. \sa <code>\link insert(iterator, param_value_type) insert(iterator, 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> */ void insert(iterator pos, size_type n, param_value_type item) { BOOST_CB_ASSERT(pos.is_valid(this)); // check for uninitialized or invalidated iterator if (n == 0) return; size_type copy = capacity() - (end() - pos); if (copy == 0) return; if (n > copy) n = copy; insert_n(pos, n, cb_details::item_wrapper<const_pointer, param_value_type>(item)); } //! Insert the range <code>[first, last)</code> at the specified position. /*! \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> or its end.<br> Valid range <code>[first, last)</code> where <code>first</code> and <code>last</code> meet the requirements of an <a href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>. \post Elements from the range <code>[first + max[0, distance(first, last) - (pos - begin()) - reserve()], last)</code> will be inserted at the position <code>pos</code>.<br>The number of <code>min[pos - begin(), max[0, distance(first, last) - reserve()]]</code> elements will be overwritten at the beginning of the <code>circular_buffer</code>.<br>(See <i>Example</i> for the explanation.) \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. \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 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 elements. \par Complexity Linear (in <code>[std::distance(pos, end()) + std::distance(first, last)]</code>; in <code>min[capacity(), std::distance(pos, end()) + std::distance(first, last)]</code> if the <code>InputIterator</code> is a <a href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">RandomAccessIterator</a>). \par Example 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>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 to the fact the insert operation preserves the capacity. After insertion the internal buffer looks like this:<br><br><code>|6|7|8|9|3|4|</code><br><br>For comparison if the capacity would not be preserved the internal buffer would then result in <code>|1|2|5|6|7|8|9|3|4|</code>. \sa <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>\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> */ template <class InputIterator> void insert(iterator pos, InputIterator first, InputIterator last) { BOOST_CB_ASSERT(pos.is_valid(this)); // check for uninitialized or invalidated iterator 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()) { 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); } BOOST_CATCH(...) { increment(m_first); BOOST_RETHROW } BOOST_CATCH_END pos.m_it = m_first; } else { pointer src = m_first; pointer dest = m_first; decrement(dest); pos.m_it = map_pointer(pos.m_it); bool construct = !full(); BOOST_TRY { while (src != pos.m_it) { construct_or_replace(construct, dest, *src); increment(src); increment(dest); construct = false; } decrement(pos.m_it); replace(pos.m_it, item); } BOOST_CATCH(...) { if (!construct && !full()) { decrement(m_first); ++m_size; } BOOST_RETHROW } BOOST_CATCH_END decrement(m_first); } if (full()) m_last = m_first; else ++m_size; return iterator(this, pos.m_it); } //! 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. \post The number of <code>min[n, (end() - pos) + reserve()]</code> elements will be inserted before the position <code>pos</code>.<br>The number of <code>min[end() - pos, max[0, n - reserve()]]</code> elements will be overwritten at the end of the <code>circular_buffer</code>.<br>(See <i>Example</i> for the explanation.) \param pos An iterator specifying the position where the <code>item</code>s will be inserted. \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. \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 elements. \par Complexity Linear (in <code>min[capacity(), std::distance(begin(), pos) + n]</code>). \par Example 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>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> <br>For comparison if the capacity would not be preserved the internal buffer would then result in <code>|1|2|0|0|0|0|0|3|4|</code>. \sa <code>\link rinsert(iterator, param_value_type) rinsert(iterator, 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> */ void rinsert(iterator pos, size_type n, param_value_type item) { BOOST_CB_ASSERT(pos.is_valid(this)); // check for uninitialized or invalidated iterator rinsert_n(pos, n, cb_details::item_wrapper<const_pointer, param_value_type>(item)); } //! Insert the range <code>[first, last)</code> before the specified position. /*! \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> or its end.<br> Valid range <code>[first, last)</code> where <code>first</code> and <code>last</code> meet the requirements of an <a href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>. \post Elements from the range <code>[first, last - max[0, distance(first, last) - (end() - pos) - reserve()])</code> will be inserted before the position <code>pos</code>.<br>The number of <code>min[end() - pos, max[0, distance(first, last) - reserve()]]</code> elements will be overwritten at the end of the <code>circular_buffer</code>.<br>(See <i>Example</i> for the explanation.) \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. \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 elements. \par Complexity Linear (in <code>[std::distance(begin(), pos) + std::distance(first, last)]</code>; in <code>min[capacity(), std::distance(begin(), pos) + std::distance(first, last)]</code> if the <code>InputIterator</code> is a <a href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">RandomAccessIterator</a>). \par Example 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>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 to the fact the rinsert operation preserves the capacity. After insertion the internal buffer looks like this:<br><br><code>|1|2|5|6|7|8|</code><br><br>For comparison if the capacity would not be preserved the internal buffer would then result in <code>|1|2|5|6|7|8|9|3|4|</code>. \sa <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>\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> */ template <class InputIterator> void rinsert(iterator pos, InputIterator first, InputIterator last) { BOOST_CB_ASSERT(pos.is_valid(this)); // check for uninitialized or invalidated iterator rinsert(pos, first, last, is_integral<InputIterator>()); } // Erase //! Remove an element at the specified position. /*! \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> (but not an <code>end()</code>). \post The element at the position <code>pos</code> is removed. \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. \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 erased element and iterators pointing to the elements behind the erased element (towards the end; except iterators equal to <code>end()</code>). \par Complexity Linear (in <code>std::distance(pos, end())</code>). \sa <code>erase(iterator, iterator)</code>, <code>rerase(iterator)</code>, <code>rerase(iterator, iterator)</code>, <code>erase_begin(size_type)</code>, <code>erase_end(size_type)</code>, <code>clear()</code> */ iterator erase(iterator pos) { BOOST_CB_ASSERT(pos.is_valid(this)); // check for uninitialized or invalidated iterator BOOST_CB_ASSERT(pos.m_it != 0); // check for iterator pointing to end() pointer next = pos.m_it; increment(next); for (pointer p = pos.m_it; next != m_last; p = next, increment(next)) replace(p, *next); decrement(m_last); destroy_item(m_last); --m_size; #if BOOST_CB_ENABLE_DEBUG return m_last == pos.m_it ? end() : iterator(this, pos.m_it); #else return m_last == pos.m_it ? end() : pos; #endif } //! Erase the range <code>[first, last)</code>. /*! \pre Valid range <code>[first, last)</code>. \post The elements from the range <code>[first, last)</code> are removed. (If <code>first == last</code> nothing is removed.) \param first The beginning of the range to be removed. \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. \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 erased elements and iterators pointing to the elements behind the erased range (towards the end; except iterators equal to <code>end()</code>). \par Complexity Linear (in <code>std::distance(first, end())</code>). \sa <code>erase(iterator)</code>, <code>rerase(iterator)</code>, <code>rerase(iterator, iterator)</code>, <code>erase_begin(size_type)</code>, <code>erase_end(size_type)</code>, <code>clear()</code> */ iterator erase(iterator first, iterator last) { BOOST_CB_ASSERT(first.is_valid(this)); // check for uninitialized or invalidated iterator BOOST_CB_ASSERT(last.is_valid(this)); // check for uninitialized or invalidated iterator BOOST_CB_ASSERT(first <= last); // check for wrong range if (first == last) return first; pointer p = first.m_it; while (last.m_it != 0) replace((first++).m_it, *last++); do { decrement(m_last); destroy_item(m_last); --m_size; } while(m_last != first.m_it); return m_last == p ? end() : iterator(this, p); } //! Remove an element at the specified position. /*! \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> (but not an <code>end()</code>). \post The element at the position <code>pos</code> is removed. \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. \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 erased element and iterators pointing to the elements in front of the erased element (towards the beginning). \par Complexity Linear (in <code>std::distance(begin(), pos)</code>). \note This method is symetric to the <code>erase(iterator)</code> method and is more effective than <code>erase(iterator)</code> if the iterator <code>pos</code> is close to the beginning of the <code>circular_buffer</code>. (See the <i>Complexity</i>.) \sa <code>erase(iterator)</code>, <code>erase(iterator, iterator)</code>, <code>rerase(iterator, iterator)</code>, <code>erase_begin(size_type)</code>, <code>erase_end(size_type)</code>, <code>clear()</code> */ iterator rerase(iterator pos) { BOOST_CB_ASSERT(pos.is_valid(this)); // check for uninitialized or invalidated iterator BOOST_CB_ASSERT(pos.m_it != 0); // check for iterator pointing to end() pointer prev = pos.m_it; pointer p = prev; for (decrement(prev); p != m_first; p = prev, decrement(prev)) replace(p, *prev); destroy_item(m_first); increment(m_first); --m_size; #if BOOST_CB_ENABLE_DEBUG return p == pos.m_it ? begin() : iterator(this, pos.m_it); #else return p == pos.m_it ? begin() : pos; #endif } //! Erase the range <code>[first, last)</code>. /*! \pre Valid range <code>[first, last)</code>. \post The elements from the range <code>[first, last)</code> are removed. (If <code>first == last</code> nothing is removed.) \param first The beginning of the range to be removed. \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. \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 erased elements and iterators pointing to the elements in front of the erased range (towards the beginning). \par Complexity Linear (in <code>std::distance(begin(), last)</code>). \note This method is symetric to the <code>erase(iterator, iterator)</code> method and is more effective than <code>erase(iterator, iterator)</code> if <code>std::distance(begin(), first)</code> is lower that <code>std::distance(last, end())</code>. \sa <code>erase(iterator)</code>, <code>erase(iterator, iterator)</code>, <code>rerase(iterator)</code>, <code>erase_begin(size_type)</code>, <code>erase_end(size_type)</code>, <code>clear()</code> */ iterator rerase(iterator first, iterator last) { BOOST_CB_ASSERT(first.is_valid(this)); // check for uninitialized or invalidated iterator BOOST_CB_ASSERT(last.is_valid(this)); // check for uninitialized or invalidated iterator BOOST_CB_ASSERT(first <= last); // check for wrong range if (first == last) return first; pointer p = map_pointer(last.m_it); last.m_it = p; while (first.m_it != m_first) { decrement(first.m_it); decrement(p); replace(p, *first.m_it); } do { destroy_item(m_first); increment(m_first); --m_size; } while(m_first != p); if (m_first == last.m_it) return begin(); decrement(last.m_it); return iterator(this, last.m_it); } //! Remove first <code>n</code> elements (with constant complexity for scalar types). /*! \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.) \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.) \par Iterator Invalidation Invalidates iterators pointing to the first <code>n</code> erased elements. \par Complexity Constant (in <code>n</code>) for scalar types; linear for other types. \note This method has been specially designed for types which do not require an explicit destructruction (e.g. integer, float or a pointer). For these scalar types a call to a destructor is not required which makes it possible to implement the "erase from beginning" operation with a constant complexity. For non-sacalar types the complexity is linear (hence the explicit destruction is needed) and the implementation is actually equivalent to <code>\link circular_buffer::rerase(iterator, iterator) rerase(begin(), begin() + n)\endlink</code>. \sa <code>erase(iterator)</code>, <code>erase(iterator, iterator)</code>, <code>rerase(iterator)</code>, <code>rerase(iterator, iterator)</code>, <code>erase_end(size_type)</code>, <code>clear()</code> */ void erase_begin(size_type n) { BOOST_CB_ASSERT(n <= size()); // check for n greater than size #if BOOST_CB_ENABLE_DEBUG erase_begin(n, false_type()); #else erase_begin(n, is_scalar<value_type>()); #endif } //! Remove last <code>n</code> elements (with constant complexity for scalar types). /*! \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.) \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.) \par Iterator Invalidation Invalidates iterators pointing to the last <code>n</code> erased elements. \par Complexity Constant (in <code>n</code>) for scalar types; linear for other types. \note This method has been specially designed for types which do not require an explicit destructruction (e.g. integer, float or a pointer). For these scalar types a call to a destructor is not required which makes it possible to implement the "erase from end" operation with a constant complexity. For non-sacalar types the complexity is linear (hence the explicit destruction is needed) and the implementation is actually equivalent to <code>\link circular_buffer::erase(iterator, iterator) erase(end() - n, end())\endlink</code>. \sa <code>erase(iterator)</code>, <code>erase(iterator, iterator)</code>, <code>rerase(iterator)</code>, <code>rerase(iterator, iterator)</code>, <code>erase_begin(size_type)</code>, <code>clear()</code> */ void erase_end(size_type n) { BOOST_CB_ASSERT(n <= size()); // check for n greater than size #if BOOST_CB_ENABLE_DEBUG erase_end(n, false_type()); #else erase_end(n, is_scalar<value_type>()); #endif } //! Remove all stored elements from the <code>circular_buffer</code>. /*! \post <code>size() == 0</code> \throws Nothing. \par Exception Safety No-throw. \par Iterator Invalidation Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to <code>end()</code>). \par Complexity Constant (in the size of the <code>circular_buffer</code>) for scalar types; linear for other types. \sa <code>~circular_buffer()</code>, <code>erase(iterator)</code>, <code>erase(iterator, iterator)</code>, <code>rerase(iterator)</code>, <code>rerase(iterator, iterator)</code>, <code>erase_begin(size_type)</code>, <code>erase_end(size_type)</code> */ void clear() { destroy_content(); m_size = 0; } private: // Helper methods //! Check if the <code>index</code> is valid. void check_position(size_type index) const { if (index >= size()) throw_exception(std::out_of_range("circular_buffer")); } //! Increment the pointer. template <class Pointer> void increment(Pointer& p) const { if (++p == m_end) p = m_buff; } //! Decrement the pointer. template <class Pointer> void decrement(Pointer& p) const { if (p == m_buff) p = m_end; --p; } //! Add <code>n</code> to the pointer. template <class Pointer> Pointer add(Pointer p, difference_type n) const { return p + (n < (m_end - p) ? n : n - capacity()); } //! Subtract <code>n</code> from the pointer. template <class Pointer> Pointer sub(Pointer p, difference_type n) const { return p - (n > (p - m_buff) ? n - capacity() : n); } //! Map the null pointer to virtual end of circular buffer. pointer map_pointer(pointer p) const { return p == 0 ? m_last : p; } //! Allocate memory. pointer allocate(size_type n) { 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); return p; #else return (n == 0) ? 0 : m_alloc.allocate(n, 0); #endif } //! Deallocate memory. void deallocate(pointer p, size_type n) { if (p != 0) m_alloc.deallocate(p, n); } //! Does the pointer point to the uninitialized memory? bool is_uninitialized(const_pointer p) const { return p >= m_last && (m_first < m_last || p < m_first); } //! Replace an element. void replace(pointer pos, param_value_type item) { *pos = 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 <code>pos</code> points to an uninitialized memory. */ void construct_or_replace(bool construct, pointer pos, param_value_type item) { if (construct) m_alloc.construct(pos, item); else replace(pos, item); } //! Destroy an item. void destroy_item(pointer p) { m_alloc.destroy(p); #if BOOST_CB_ENABLE_DEBUG invalidate_iterators(iterator(this, p)); std::memset(p, cb_details::UNINITIALIZED, sizeof(value_type)); #endif } //! Destroy an item only if it has been constructed. void destroy_if_constructed(pointer pos) { if (is_uninitialized(pos)) destroy_item(pos); } //! Destroy the whole content of the circular buffer. void destroy_content() { #if BOOST_CB_ENABLE_DEBUG destroy_content(false_type()); #else destroy_content(is_scalar<value_type>()); #endif } //! Specialized destroy_content method. void destroy_content(const true_type&) { m_first = add(m_first, size()); } //! Specialized destroy_content method. void destroy_content(const false_type&) { for (size_type ii = 0; ii < size(); ++ii, increment(m_first)) destroy_item(m_first); } //! Destroy content and free allocated memory. void destroy() { destroy_content(); deallocate(m_buff, capacity()); #if BOOST_CB_ENABLE_DEBUG m_buff = 0; m_first = 0; m_last = 0; m_end = 0; #endif } //! Initialize the internal buffer. void initialize_buffer(capacity_type buffer_capacity) { m_buff = allocate(buffer_capacity); m_end = m_buff + buffer_capacity; } //! Initialize the internal buffer. void initialize_buffer(capacity_type buffer_capacity, param_value_type item) { initialize_buffer(buffer_capacity); BOOST_TRY { cb_details::uninitialized_fill_n_with_alloc(m_buff, size(), item, m_alloc); } BOOST_CATCH(...) { deallocate(m_buff, size()); BOOST_RETHROW } BOOST_CATCH_END } //! Specialized initialize method. template <class IntegralType> void initialize(IntegralType n, IntegralType item, const true_type&) { m_size = static_cast<size_type>(n); initialize_buffer(size(), item); m_first = m_last = m_buff; } //! Specialized initialize method. template <class Iterator> 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()); #else initialize(first, last, BOOST_DEDUCED_TYPENAME BOOST_ITERATOR_CATEGORY<Iterator>::type()); #endif } //! Specialized initialize method. template <class InputIterator> void initialize(InputIterator first, InputIterator last, const std::input_iterator_tag&) { BOOST_CB_ASSERT_TEMPLATED_ITERATOR_CONSTRUCTORS // check if the STL provides templated iterator constructors // 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); } //! Specialized initialize method. template <class ForwardIterator> void initialize(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); initialize(distance, first, last, distance); } //! Specialized initialize method. template <class IntegralType> void initialize(capacity_type buffer_capacity, IntegralType n, IntegralType item, const true_type&) { BOOST_CB_ASSERT(buffer_capacity >= static_cast<size_type>(n)); // check for capacity lower than n m_size = static_cast<size_type>(n); initialize_buffer(buffer_capacity, item); m_first = m_buff; m_last = buffer_capacity == size() ? m_buff : m_buff + size(); } //! Specialized initialize method. template <class Iterator> 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()); #else initialize(buffer_capacity, first, last, BOOST_DEDUCED_TYPENAME BOOST_ITERATOR_CATEGORY<Iterator>::type()); #endif } //! Specialized initialize method. template <class InputIterator> void initialize(capacity_type buffer_capacity, InputIterator first, InputIterator last, const std::input_iterator_tag&) { initialize_buffer(buffer_capacity); m_first = m_last = m_buff; m_size = 0; if (buffer_capacity == 0) return; while (first != last && !full()) { m_alloc.construct(m_last, *first++); increment(m_last); ++m_size; } while (first != last) { replace(m_last, *first++); increment(m_last); m_first = m_last; } } //! Specialized initialize method. template <class ForwardIterator> void initialize(capacity_type buffer_capacity, ForwardIterator first, ForwardIterator last, const std::forward_iterator_tag&) { BOOST_CB_ASSERT(std::distance(first, last) >= 0); // check for wrong range initialize(buffer_capacity, first, last, std::distance(first, last)); } //! Initialize the circular buffer. template <class ForwardIterator> void initialize(capacity_type buffer_capacity, ForwardIterator first, ForwardIterator last, size_type distance) { initialize_buffer(buffer_capacity); m_first = m_buff; if (distance > buffer_capacity) { std::advance(first, distance - buffer_capacity); m_size = buffer_capacity; } else { m_size = distance; } BOOST_TRY { m_last = cb_details::uninitialized_copy_with_alloc(first, last, m_buff, m_alloc); } BOOST_CATCH(...) { deallocate(m_buff, buffer_capacity); BOOST_RETHROW } BOOST_CATCH_END if (m_last == m_end) m_last = m_buff; } //! Reset the circular buffer. void reset(pointer buff, pointer last, capacity_type new_capacity) { destroy(); m_size = last - buff; m_first = m_buff = buff; m_end = m_buff + new_capacity; m_last = last == m_end ? m_buff : last; } //! Specialized method for swapping the allocator. void swap_allocator(circular_buffer<T, Alloc>& cb, const true_type&) { // Swap is not needed because allocators have no state. } //! Specialized method for swapping the allocator. void swap_allocator(circular_buffer<T, Alloc>& cb, const false_type&) { std::swap(m_alloc, cb.m_alloc); } //! Specialized assign method. template <class IntegralType> void assign(IntegralType n, IntegralType item, const true_type&) { assign(static_cast<size_type>(n), static_cast<value_type>(item)); } //! Specialized assign method. template <class Iterator> 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()); #else assign(first, last, BOOST_DEDUCED_TYPENAME BOOST_ITERATOR_CATEGORY<Iterator>::type()); #endif } //! Specialized assign method. template <class InputIterator> void assign(InputIterator first, InputIterator last, const std::input_iterator_tag&) { BOOST_CB_ASSERT_TEMPLATED_ITERATOR_CONSTRUCTORS // check if the STL provides templated iterator constructors // for containers 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)); } //! Specialized assign method. template <class ForwardIterator> 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)); } //! Specialized assign method. template <class IntegralType> void assign(capacity_type new_capacity, IntegralType n, IntegralType item, const true_type&) { assign(new_capacity, static_cast<size_type>(n), static_cast<value_type>(item)); } //! Specialized assign method. template <class Iterator> 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()); #else assign(new_capacity, first, last, BOOST_DEDUCED_TYPENAME BOOST_ITERATOR_CATEGORY<Iterator>::type()); #endif } //! Specialized assign method. template <class InputIterator> void assign(capacity_type new_capacity, InputIterator first, InputIterator last, const std::input_iterator_tag&) { if (new_capacity == capacity()) { 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); } } //! Specialized assign method. template <class ForwardIterator> void assign(capacity_type new_capacity, 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); if (distance > new_capacity) { std::advance(first, distance - new_capacity); distance = new_capacity; } assign_n(new_capacity, distance, cb_details::assign_range<ForwardIterator, allocator_type>(first, last, m_alloc)); } //! Helper assign method. template <class Functor> void assign_n(capacity_type new_capacity, size_type n, const Functor& fnc) { if (new_capacity == capacity()) { destroy_content(); BOOST_TRY { fnc(m_buff); } BOOST_CATCH(...) { m_size = 0; BOOST_RETHROW } BOOST_CATCH_END } else { pointer buff = allocate(new_capacity); BOOST_TRY { fnc(buff); } BOOST_CATCH(...) { deallocate(buff, new_capacity); BOOST_RETHROW } BOOST_CATCH_END destroy(); m_buff = buff; m_end = m_buff + new_capacity; } m_size = n; m_first = m_buff; m_last = add(m_buff, size()); } //! Helper insert method. iterator insert_item(const iterator& pos, param_value_type item) { pointer p = pos.m_it; if (p == 0) { construct_or_replace(!full(), m_last, item); p = m_last; } else { pointer src = m_last; pointer dest = m_last; bool construct = !full(); BOOST_TRY { while (src != p) { decrement(src); construct_or_replace(construct, dest, *src); decrement(dest); construct = false; } replace(p, item); } BOOST_CATCH(...) { if (!construct && !full()) { increment(m_last); ++m_size; } BOOST_RETHROW } BOOST_CATCH_END } increment(m_last); if (full()) m_first = m_last; else ++m_size; return iterator(this, p); } //! Specialized insert method. template <class IntegralType> void insert(const iterator& pos, IntegralType n, IntegralType item, const true_type&) { insert(pos, static_cast<size_type>(n), static_cast<value_type>(item)); } //! Specialized insert method. template <class Iterator> 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()); #else insert(pos, first, last, BOOST_DEDUCED_TYPENAME BOOST_ITERATOR_CATEGORY<Iterator>::type()); #endif } //! Specialized insert method. template <class InputIterator> 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++); } } //! Specialized insert method. template <class ForwardIterator> void insert(const iterator& pos, ForwardIterator first, ForwardIterator last, const std::forward_iterator_tag&) { BOOST_CB_ASSERT(std::distance(first, last) >= 0); // check for wrong range size_type n = std::distance(first, last); if (n == 0) return; size_type copy = capacity() - (end() - pos); if (copy == 0) return; if (n > copy) { std::advance(first, n - copy); n = copy; } insert_n(pos, n, cb_details::iterator_wrapper<ForwardIterator>(first)); } //! Helper insert method. template <class Wrapper> void insert_n(const iterator& pos, size_type n, const Wrapper& wrapper) { size_type construct = reserve(); if (construct > n) construct = n; if (pos.m_it == 0) { size_type ii = 0; pointer p = m_last; BOOST_TRY { for (; ii < construct; ++ii, increment(p)) m_alloc.construct(p, *wrapper()); for (;ii < n; ++ii, increment(p)) replace(p, *wrapper()); } BOOST_CATCH(...) { size_type constructed = (std::min)(ii, construct); m_last = add(m_last, constructed); m_size += constructed; BOOST_RETHROW } BOOST_CATCH_END } else { pointer src = m_last; pointer dest = add(m_last, n - 1); pointer p = pos.m_it; size_type ii = 0; BOOST_TRY { while (src != pos.m_it) { decrement(src); construct_or_replace(is_uninitialized(dest), dest, *src); decrement(dest); } for (; ii < n; ++ii, increment(p)) construct_or_replace(is_uninitialized(p), p, *wrapper()); } BOOST_CATCH(...) { for (p = add(m_last, n - 1); p != dest; decrement(p)) destroy_if_constructed(p); for (n = 0, p = pos.m_it; n < ii; ++n, increment(p)) destroy_if_constructed(p); BOOST_RETHROW } BOOST_CATCH_END } m_last = add(m_last, n); m_first = add(m_first, n - construct); m_size += construct; } //! Specialized rinsert method. template <class IntegralType> void rinsert(const iterator& pos, IntegralType n, IntegralType item, const true_type&) { rinsert(pos, static_cast<size_type>(n), static_cast<value_type>(item)); } //! Specialized rinsert method. template <class Iterator> 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()); #else rinsert(pos, first, last, BOOST_DEDUCED_TYPENAME BOOST_ITERATOR_CATEGORY<Iterator>::type()); #endif } //! Specialized insert method. template <class InputIterator> void rinsert(iterator pos, InputIterator first, InputIterator last, const std::input_iterator_tag&) { if (!full() || pos.m_it != 0) { for (;first != last; ++pos) { pos = rinsert(pos, *first++); if (pos.m_it == 0) break; } } } //! Specialized rinsert method. template <class ForwardIterator> void rinsert(const iterator& pos, ForwardIterator first, ForwardIterator last, const std::forward_iterator_tag&) { BOOST_CB_ASSERT(std::distance(first, last) >= 0); // check for wrong range rinsert_n(pos, std::distance(first, last), cb_details::iterator_wrapper<ForwardIterator>(first)); } //! Helper rinsert method. template <class Wrapper> void rinsert_n(const iterator& pos, size_type n, const Wrapper& wrapper) { if (n == 0) return; iterator b = begin(); size_type copy = capacity() - (pos - b); if (copy == 0) return; if (n > copy) n = copy; size_type construct = reserve(); if (construct > n) construct = n; if (pos == b) { pointer p = sub(m_first, n); size_type ii = n; BOOST_TRY { for (;ii > construct; --ii, increment(p)) replace(p, *wrapper()); for (; ii > 0; --ii, increment(p)) m_alloc.construct(p, *wrapper()); } BOOST_CATCH(...) { size_type constructed = ii < construct ? construct - ii : 0; m_last = add(m_last, constructed); m_size += constructed; BOOST_RETHROW } BOOST_CATCH_END } else { pointer src = m_first; pointer dest = sub(m_first, n); pointer p = map_pointer(pos.m_it); BOOST_TRY { while (src != p) { construct_or_replace(is_uninitialized(dest), dest, *src); increment(src); increment(dest); } for (size_type ii = 0; ii < n; ++ii, increment(dest)) construct_or_replace(is_uninitialized(dest), dest, *wrapper()); } BOOST_CATCH(...) { for (src = sub(m_first, n); src != dest; increment(src)) destroy_if_constructed(src); BOOST_RETHROW } BOOST_CATCH_END } m_first = sub(m_first, n); m_last = sub(m_last, n - construct); m_size += construct; } //! Specialized erase_begin method. void erase_begin(size_type n, const true_type&) { m_first = add(m_first, n); m_size -= n; } //! Specialized erase_begin method. void erase_begin(size_type n, const false_type&) { iterator b = begin(); rerase(b, b + n); } //! Specialized erase_end method. void erase_end(size_type n, const true_type&) { m_last = sub(m_last, n); m_size -= n; } //! Specialized erase_end method. void erase_end(size_type n, const false_type&) { iterator e = end(); erase(e - n, e); } }; // Non-member functions //! Compare two <code>circular_buffer</code>s element-by-element to determine if they are equal. /*! \param lhs The <code>circular_buffer</code> to compare. \param rhs The <code>circular_buffer</code> to compare. \return <code>lhs.\link circular_buffer::size() size()\endlink == rhs.\link circular_buffer::size() size()\endlink && <a href="http://www.sgi.com/tech/stl/equal.html">std::equal</a>(lhs.\link circular_buffer::begin() begin()\endlink, lhs.\link circular_buffer::end() end()\endlink, rhs.\link circular_buffer::begin() begin()\endlink)</code> \throws Nothing. \par Complexity Linear (in the size of the <code>circular_buffer</code>s). \par Iterator Invalidation Does not invalidate any iterators. */ template <class T, class Alloc> inline bool operator == (const circular_buffer<T, Alloc>& lhs, const circular_buffer<T, Alloc>& rhs) { return lhs.size() == rhs.size() && std::equal(lhs.begin(), lhs.end(), rhs.begin()); } /*! \brief Compare two <code>circular_buffer</code>s element-by-element to determine if the left one is lesser than the right one. \param lhs The <code>circular_buffer</code> to compare. \param rhs The <code>circular_buffer</code> to compare. \return <code><a href="http://www.sgi.com/tech/stl/lexicographical_compare.html"> std::lexicographical_compare</a>(lhs.\link circular_buffer::begin() begin()\endlink, lhs.\link circular_buffer::end() end()\endlink, rhs.\link circular_buffer::begin() begin()\endlink, rhs.\link circular_buffer::end() end()\endlink)</code> \throws Nothing. \par Complexity Linear (in the size of the <code>circular_buffer</code>s). \par Iterator Invalidation Does not invalidate any iterators. */ template <class T, class Alloc> inline bool operator < (const circular_buffer<T, Alloc>& lhs, const circular_buffer<T, Alloc>& rhs) { return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end()); } #if !defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING) || defined(BOOST_MSVC) //! Compare two <code>circular_buffer</code>s element-by-element to determine if they are non-equal. /*! \param lhs The <code>circular_buffer</code> to compare. \param rhs The <code>circular_buffer</code> to compare. \return <code>!(lhs == rhs)</code> \throws Nothing. \par Complexity Linear (in the size of the <code>circular_buffer</code>s). \par Iterator Invalidation Does not invalidate any iterators. \sa <code>operator==(const circular_buffer<T,Alloc>&, const circular_buffer<T,Alloc>&)</code> */ template <class T, class Alloc> inline bool operator != (const circular_buffer<T, Alloc>& lhs, const circular_buffer<T, Alloc>& rhs) { return !(lhs == rhs); } /*! \brief Compare two <code>circular_buffer</code>s element-by-element to determine if the left one is greater than the right one. \param lhs The <code>circular_buffer</code> to compare. \param rhs The <code>circular_buffer</code> to compare. \return <code>rhs \< lhs</code> \throws Nothing. \par Complexity Linear (in the size of the <code>circular_buffer</code>s). \par Iterator Invalidation Does not invalidate any iterators. \sa <code>operator<(const circular_buffer<T,Alloc>&, const circular_buffer<T,Alloc>&)</code> */ template <class T, class Alloc> inline bool operator > (const circular_buffer<T, Alloc>& lhs, const circular_buffer<T, Alloc>& rhs) { return rhs < lhs; } /*! \brief Compare two <code>circular_buffer</code>s element-by-element to determine if the left one is lesser or equal to the right one. \param lhs The <code>circular_buffer</code> to compare. \param rhs The <code>circular_buffer</code> to compare. \return <code>!(rhs \< lhs)</code> \throws Nothing. \par Complexity Linear (in the size of the <code>circular_buffer</code>s). \par Iterator Invalidation Does not invalidate any iterators. \sa <code>operator<(const circular_buffer<T,Alloc>&, const circular_buffer<T,Alloc>&)</code> */ template <class T, class Alloc> inline bool operator <= (const circular_buffer<T, Alloc>& lhs, const circular_buffer<T, Alloc>& rhs) { return !(rhs < lhs); } /*! \brief Compare two <code>circular_buffer</code>s element-by-element to determine if the left one is greater or equal to the right one. \param lhs The <code>circular_buffer</code> to compare. \param rhs The <code>circular_buffer</code> to compare. \return <code>!(lhs < rhs)</code> \throws Nothing. \par Complexity Linear (in the size of the <code>circular_buffer</code>s). \par Iterator Invalidation Does not invalidate any iterators. \sa <code>operator<(const circular_buffer<T,Alloc>&, const circular_buffer<T,Alloc>&)</code> */ template <class T, class Alloc> inline bool operator >= (const circular_buffer<T, Alloc>& lhs, const circular_buffer<T, Alloc>& rhs) { return !(lhs < rhs); } //! Swap the contents of two <code>circular_buffer</code>s. /*! \post <code>lhs</code> contains elements of <code>rhs</code> and vice versa. \param lhs The <code>circular_buffer</code> whose content will be swapped with <code>rhs</code>. \param rhs The <code>circular_buffer</code> whose content will be swapped with <code>lhs</code>. \throws Nothing. \par Complexity Constant (in the size of the <code>circular_buffer</code>s). \par Iterator Invalidation Invalidates all iterators of both <code>circular_buffer</code>s. (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="#debug">Debug Support</a> off otherwise an assertion will report an error if such invalidated iterator is used.) \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) { lhs.swap(rhs); } #endif // #if !defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING) || defined(BOOST_MSVC) } // namespace boost #endif // #if !defined(BOOST_CIRCULAR_BUFFER_BASE_HPP)