1 // Implementation of the base circular buffer.
3 // Copyright (c) 2003-2008 Jan Gaspar
4 // Copyright (c) 2013 Paul A. Bristow // Doxygen comments changed.
5 // Copyright (c) 2013 Antony Polukhin // Move semantics implementation.
6 // Copyright (c) 2014 Glen Fernandes // C++11 allocator model support.
8 // Use, modification, and distribution is subject to the Boost Software
9 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
10 // http://www.boost.org/LICENSE_1_0.txt)
12 #if !defined(BOOST_CIRCULAR_BUFFER_BASE_HPP)
13 #define BOOST_CIRCULAR_BUFFER_BASE_HPP
19 #include <boost/config.hpp>
20 #include <boost/call_traits.hpp>
21 #include <boost/concept_check.hpp>
22 #include <boost/limits.hpp>
23 #include <boost/container/allocator_traits.hpp>
24 #include <boost/iterator/reverse_iterator.hpp>
25 #include <boost/iterator/iterator_traits.hpp>
26 #include <boost/type_traits/is_stateless.hpp>
27 #include <boost/type_traits/is_integral.hpp>
28 #include <boost/type_traits/is_scalar.hpp>
29 #include <boost/type_traits/is_nothrow_move_constructible.hpp>
30 #include <boost/type_traits/is_nothrow_move_assignable.hpp>
31 #include <boost/type_traits/is_copy_constructible.hpp>
32 #include <boost/type_traits/conditional.hpp>
33 #include <boost/move/adl_move_swap.hpp>
34 #include <boost/move/move.hpp>
35 #include <boost/utility/addressof.hpp>
41 #if BOOST_WORKAROUND(__MWERKS__, BOOST_TESTED_AT(0x3205))
48 \class circular_buffer
49 \brief Circular buffer - a STL compliant container.
50 \tparam T The type of the elements stored in the <code>circular_buffer</code>.
51 \par Type Requirements T
52 The <code>T</code> has to be <a href="http://www.sgi.com/tech/stl/Assignable.html">
53 SGIAssignable</a> (SGI STL defined combination of <a href="../../../utility/Assignable.html">
54 Assignable</a> and <a href="../../../utility/CopyConstructible.html">CopyConstructible</a>).
55 Moreover <code>T</code> has to be <a href="http://www.sgi.com/tech/stl/DefaultConstructible.html">
56 DefaultConstructible</a> if supplied as a default parameter when invoking some of the
57 <code>circular_buffer</code>'s methods e.g.
58 <code>insert(iterator pos, const value_type& item = %value_type())</code>. And
59 <a href="http://www.sgi.com/tech/stl/EqualityComparable.html">EqualityComparable</a> and/or
60 <a href="../../../utility/LessThanComparable.html">LessThanComparable</a> if the <code>circular_buffer</code>
61 will be compared with another container.
62 \tparam Alloc The allocator type used for all internal memory management.
63 \par Type Requirements Alloc
64 The <code>Alloc</code> has to meet the allocator requirements imposed by STL.
68 For detailed documentation of the circular_buffer visit:
69 http://www.boost.org/libs/circular_buffer/doc/circular_buffer.html
71 template <class T, class Alloc>
74 #if BOOST_CB_ENABLE_DEBUG
75 : public cb_details::debug_iterator_registry
81 //BOOST_CLASS_REQUIRE(T, boost, SGIAssignableConcept);
84 //BOOST_CONCEPT_ASSERT((Assignable<T>));
85 //BOOST_CONCEPT_ASSERT((CopyConstructible<T>));
86 //BOOST_CONCEPT_ASSERT((DefaultConstructible<T>));
88 // Required if the circular_buffer will be compared with anther container.
89 //BOOST_CONCEPT_ASSERT((EqualityComparable<T>));
90 //BOOST_CONCEPT_ASSERT((LessThanComparable<T>));
95 //! The type of this <code>circular_buffer</code>.
96 typedef circular_buffer<T, Alloc> this_type;
98 //! The type of elements stored in the <code>circular_buffer</code>.
99 typedef typename boost::container::allocator_traits<Alloc>::value_type value_type;
101 //! A pointer to an element.
102 typedef typename boost::container::allocator_traits<Alloc>::pointer pointer;
104 //! A const pointer to the element.
105 typedef typename boost::container::allocator_traits<Alloc>::const_pointer const_pointer;
107 //! A reference to an element.
108 typedef typename boost::container::allocator_traits<Alloc>::reference reference;
110 //! A const reference to an element.
111 typedef typename boost::container::allocator_traits<Alloc>::const_reference const_reference;
113 //! The distance type.
115 (A signed integral type used to represent the distance between two iterators.)
117 typedef typename boost::container::allocator_traits<Alloc>::difference_type difference_type;
121 (An unsigned integral type that can represent any non-negative value of the container's distance type.)
123 typedef typename boost::container::allocator_traits<Alloc>::size_type size_type;
125 //! The type of an allocator used in the <code>circular_buffer</code>.
126 typedef Alloc allocator_type;
130 //! A const (random access) iterator used to iterate through the <code>circular_buffer</code>.
131 typedef cb_details::iterator< circular_buffer<T, Alloc>, cb_details::const_traits<boost::container::allocator_traits<Alloc> > > const_iterator;
133 //! A (random access) iterator used to iterate through the <code>circular_buffer</code>.
134 typedef cb_details::iterator< circular_buffer<T, Alloc>, cb_details::nonconst_traits<boost::container::allocator_traits<Alloc> > > iterator;
136 //! A const iterator used to iterate backwards through a <code>circular_buffer</code>.
137 typedef boost::reverse_iterator<const_iterator> const_reverse_iterator;
139 //! An iterator used to iterate backwards through a <code>circular_buffer</code>.
140 typedef boost::reverse_iterator<iterator> reverse_iterator;
142 // Container specific types
146 (A typedef for the <a href="http://www.sgi.com/tech/stl/pair.html"><code>std::pair</code></a> where
147 its first element is a pointer to a beginning of an array and its second element represents
148 a size of the array.)
150 typedef std::pair<pointer, size_type> array_range;
152 //! A range of a const array.
154 (A typedef for the <a href="http://www.sgi.com/tech/stl/pair.html"><code>std::pair</code></a> where
155 its first element is a pointer to a beginning of a const array and its second element represents
156 a size of the const array.)
158 typedef std::pair<const_pointer, size_type> const_array_range;
160 //! The capacity type.
162 (Same as <code>size_type</code> - defined for consistency with the __cbso class.
165 // <a href="space_optimized.html"><code>circular_buffer_space_optimized</code></a>.)
167 typedef size_type capacity_type;
171 //! A type representing the "best" way to pass the value_type to a method.
172 typedef const value_type& param_value_type;
174 //! A type representing rvalue from param type.
175 //! On compilers without rvalue references support this type is the Boost.Moves type used for emulation.
176 typedef BOOST_RV_REF(value_type) rvalue_type;
181 //! The internal buffer used for storing elements in the circular buffer.
184 //! The internal buffer's end (end of the storage space).
187 //! The virtual beginning of the circular buffer.
190 //! The virtual end of the circular buffer (one behind the last element).
193 //! The number of items currently stored in the circular buffer.
197 allocator_type m_alloc;
200 #if defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
202 friend const_iterator;
204 template <class Buff, class Traits> friend struct cb_details::iterator;
210 //! Get the allocator.
212 \return The allocator.
214 \par Exception Safety
216 \par Iterator Invalidation
217 Does not invalidate any iterators.
219 Constant (in the size of the <code>circular_buffer</code>).
220 \sa <code>get_allocator()</code> for obtaining an allocator %reference.
222 allocator_type get_allocator() const BOOST_NOEXCEPT { return m_alloc; }
224 //! Get the allocator reference.
226 \return A reference to the allocator.
228 \par Exception Safety
230 \par Iterator Invalidation
231 Does not invalidate any iterators.
233 Constant (in the size of the <code>circular_buffer</code>).
234 \note This method was added in order to optimize obtaining of the allocator with a state,
235 although use of stateful allocators in STL is discouraged.
236 \sa <code>get_allocator() const</code>
238 allocator_type& get_allocator() BOOST_NOEXCEPT { return m_alloc; }
242 //! Get the iterator pointing to the beginning of the <code>circular_buffer</code>.
244 \return A random access iterator pointing to the first element of the <code>circular_buffer</code>. If the
245 <code>circular_buffer</code> is empty it returns an iterator equal to the one returned by
248 \par Exception Safety
250 \par Iterator Invalidation
251 Does not invalidate any iterators.
253 Constant (in the size of the <code>circular_buffer</code>).
254 \sa <code>end()</code>, <code>rbegin()</code>, <code>rend()</code>
256 iterator begin() BOOST_NOEXCEPT { return iterator(this, empty() ? 0 : m_first); }
258 //! Get the iterator pointing to the end of the <code>circular_buffer</code>.
260 \return A random access iterator pointing to the element "one behind" the last element of the <code>
261 circular_buffer</code>. If the <code>circular_buffer</code> is empty it returns an iterator equal to
262 the one returned by <code>begin()</code>.
264 \par Exception Safety
266 \par Iterator Invalidation
267 Does not invalidate any iterators.
269 Constant (in the size of the <code>circular_buffer</code>).
270 \sa <code>begin()</code>, <code>rbegin()</code>, <code>rend()</code>
272 iterator end() BOOST_NOEXCEPT { return iterator(this, 0); }
274 //! Get the const iterator pointing to the beginning of the <code>circular_buffer</code>.
276 \return A const random access iterator pointing to the first element of the <code>circular_buffer</code>. If
277 the <code>circular_buffer</code> is empty it returns an iterator equal to the one returned by
278 <code>end() const</code>.
280 \par Exception Safety
282 \par Iterator Invalidation
283 Does not invalidate any iterators.
285 Constant (in the size of the <code>circular_buffer</code>).
286 \sa <code>end() const</code>, <code>rbegin() const</code>, <code>rend() const</code>
288 const_iterator begin() const BOOST_NOEXCEPT { return const_iterator(this, empty() ? 0 : m_first); }
290 //! Get the const iterator pointing to the end of the <code>circular_buffer</code>.
292 \return A const random access iterator pointing to the element "one behind" the last element of the <code>
293 circular_buffer</code>. If the <code>circular_buffer</code> is empty it returns an iterator equal to
294 the one returned by <code>begin() const</code> const.
296 \par Exception Safety
298 \par Iterator Invalidation
299 Does not invalidate any iterators.
301 Constant (in the size of the <code>circular_buffer</code>).
302 \sa <code>begin() const</code>, <code>rbegin() const</code>, <code>rend() const</code>
304 const_iterator end() const BOOST_NOEXCEPT { return const_iterator(this, 0); }
306 //! Get the iterator pointing to the beginning of the "reversed" <code>circular_buffer</code>.
308 \return A reverse random access iterator pointing to the last element of the <code>circular_buffer</code>.
309 If the <code>circular_buffer</code> is empty it returns an iterator equal to the one returned by
312 \par Exception Safety
314 \par Iterator Invalidation
315 Does not invalidate any iterators.
317 Constant (in the size of the <code>circular_buffer</code>).
318 \sa <code>rend()</code>, <code>begin()</code>, <code>end()</code>
320 reverse_iterator rbegin() BOOST_NOEXCEPT { return reverse_iterator(end()); }
322 //! Get the iterator pointing to the end of the "reversed" <code>circular_buffer</code>.
324 \return A reverse random access iterator pointing to the element "one before" the first element of the <code>
325 circular_buffer</code>. If the <code>circular_buffer</code> is empty it returns an iterator equal to
326 the one returned by <code>rbegin()</code>.
328 \par Exception Safety
330 \par Iterator Invalidation
331 Does not invalidate any iterators.
333 Constant (in the size of the <code>circular_buffer</code>).
334 \sa <code>rbegin()</code>, <code>begin()</code>, <code>end()</code>
336 reverse_iterator rend() BOOST_NOEXCEPT { return reverse_iterator(begin()); }
338 //! Get the const iterator pointing to the beginning of the "reversed" <code>circular_buffer</code>.
340 \return A const reverse random access iterator pointing to the last element of the
341 <code>circular_buffer</code>. If the <code>circular_buffer</code> is empty it returns an iterator equal
342 to the one returned by <code>rend() const</code>.
344 \par Exception Safety
346 \par Iterator Invalidation
347 Does not invalidate any iterators.
349 Constant (in the size of the <code>circular_buffer</code>).
350 \sa <code>rend() const</code>, <code>begin() const</code>, <code>end() const</code>
352 const_reverse_iterator rbegin() const BOOST_NOEXCEPT { return const_reverse_iterator(end()); }
354 //! Get the const iterator pointing to the end of the "reversed" <code>circular_buffer</code>.
356 \return A const reverse random access iterator pointing to the element "one before" the first element of the
357 <code>circular_buffer</code>. If the <code>circular_buffer</code> is empty it returns an iterator equal
358 to the one returned by <code>rbegin() const</code>.
360 \par Exception Safety
362 \par Iterator Invalidation
363 Does not invalidate any iterators.
365 Constant (in the size of the <code>circular_buffer</code>).
366 \sa <code>rbegin() const</code>, <code>begin() const</code>, <code>end() const</code>
368 const_reverse_iterator rend() const BOOST_NOEXCEPT { return const_reverse_iterator(begin()); }
370 //! Get the element at the <code>index</code> position.
372 \pre <code>0 \<= index \&\& index \< size()</code>
373 \param index The position of the element.
374 \return A reference to the element at the <code>index</code> position.
376 \par Exception Safety
378 \par Iterator Invalidation
379 Does not invalidate any iterators.
381 Constant (in the size of the <code>circular_buffer</code>).
382 \sa <code>at()</code>
384 reference operator [] (size_type index) {
385 BOOST_CB_ASSERT(index < size()); // check for invalid index
386 return *add(m_first, index);
389 //! Get the element at the <code>index</code> position.
391 \pre <code>0 \<= index \&\& index \< size()</code>
392 \param index The position of the element.
393 \return A const reference to the element at the <code>index</code> position.
395 \par Exception Safety
397 \par Iterator Invalidation
398 Does not invalidate any iterators.
400 Constant (in the size of the <code>circular_buffer</code>).
401 \sa <code>\link at(size_type)const at() const \endlink</code>
403 const_reference operator [] (size_type index) const {
404 BOOST_CB_ASSERT(index < size()); // check for invalid index
405 return *add(m_first, index);
408 //! Get the element at the <code>index</code> position.
410 \param index The position of the element.
411 \return A reference to the element at the <code>index</code> position.
412 \throws <code>std::out_of_range</code> when the <code>index</code> is invalid (when
413 <code>index >= size()</code>).
414 \par Exception Safety
416 \par Iterator Invalidation
417 Does not invalidate any iterators.
419 Constant (in the size of the <code>circular_buffer</code>).
420 \sa <code>\link operator[](size_type) operator[] \endlink</code>
422 reference at(size_type index) {
423 check_position(index);
424 return (*this)[index];
427 //! Get the element at the <code>index</code> position.
429 \param index The position of the element.
430 \return A const reference to the element at the <code>index</code> position.
431 \throws <code>std::out_of_range</code> when the <code>index</code> is invalid (when
432 <code>index >= size()</code>).
433 \par Exception Safety
435 \par Iterator Invalidation
436 Does not invalidate any iterators.
438 Constant (in the size of the <code>circular_buffer</code>).
439 \sa <code>\link operator[](size_type)const operator[] const \endlink</code>
441 const_reference at(size_type index) const {
442 check_position(index);
443 return (*this)[index];
446 //! Get the first element.
448 \pre <code>!empty()</code>
449 \return A reference to the first element of the <code>circular_buffer</code>.
451 \par Exception Safety
453 \par Iterator Invalidation
454 Does not invalidate any iterators.
456 Constant (in the size of the <code>circular_buffer</code>).
457 \sa <code>back()</code>
460 BOOST_CB_ASSERT(!empty()); // check for empty buffer (front element not available)
464 //! Get the last element.
466 \pre <code>!empty()</code>
467 \return A reference to the last element of the <code>circular_buffer</code>.
469 \par Exception Safety
471 \par Iterator Invalidation
472 Does not invalidate any iterators.
474 Constant (in the size of the <code>circular_buffer</code>).
475 \sa <code>front()</code>
478 BOOST_CB_ASSERT(!empty()); // check for empty buffer (back element not available)
479 return *((m_last == m_buff ? m_end : m_last) - 1);
482 //! Get the first element.
484 \pre <code>!empty()</code>
485 \return A const reference to the first element of the <code>circular_buffer</code>.
487 \par Exception Safety
489 \par Iterator Invalidation
490 Does not invalidate any iterators.
492 Constant (in the size of the <code>circular_buffer</code>).
493 \sa <code>back() const</code>
495 const_reference front() const {
496 BOOST_CB_ASSERT(!empty()); // check for empty buffer (front element not available)
500 //! Get the last element.
502 \pre <code>!empty()</code>
503 \return A const reference to the last element of the <code>circular_buffer</code>.
505 \par Exception Safety
507 \par Iterator Invalidation
508 Does not invalidate any iterators.
510 Constant (in the size of the <code>circular_buffer</code>).
511 \sa <code>front() const</code>
513 const_reference back() const {
514 BOOST_CB_ASSERT(!empty()); // check for empty buffer (back element not available)
515 return *((m_last == m_buff ? m_end : m_last) - 1);
518 //! Get the first continuous array of the internal buffer.
520 This method in combination with <code>array_two()</code> can be useful when passing the stored data into
521 a legacy C API as an array. Suppose there is a <code>circular_buffer</code> of capacity 10, containing 7
522 characters <code>'a', 'b', ..., 'g'</code> where <code>buff[0] == 'a'</code>, <code>buff[1] == 'b'</code>,
523 ... and <code>buff[6] == 'g'</code>:<br><br>
524 <code>circular_buffer<char> buff(10);</code><br><br>
525 The internal representation is often not linear and the state of the internal buffer may look like this:<br>
527 |e|f|g| | | |a|b|c|d|<br>
529 begin _______^</code><br><br>
531 where <code>|a|b|c|d|</code> represents the "array one", <code>|e|f|g|</code> represents the "array two" and
532 <code>| | | |</code> is a free space.<br>
533 Now consider a typical C style function for writing data into a file:<br><br>
534 <code>int write(int file_desc, char* buff, int num_bytes);</code><br><br>
535 There are two ways how to write the content of the <code>circular_buffer</code> into a file. Either relying
536 on <code>array_one()</code> and <code>array_two()</code> methods and calling the write function twice:<br><br>
537 <code>array_range ar = buff.array_one();<br>
538 write(file_desc, ar.first, ar.second);<br>
539 ar = buff.array_two();<br>
540 write(file_desc, ar.first, ar.second);</code><br><br>
541 Or relying on the <code>linearize()</code> method:<br><br><code>
542 write(file_desc, buff.linearize(), buff.size());</code><br><br>
543 Since the complexity of <code>array_one()</code> and <code>array_two()</code> methods is constant the first
544 option is suitable when calling the write method is "cheap". On the other hand the second option is more
545 suitable when calling the write method is more "expensive" than calling the <code>linearize()</code> method
546 whose complexity is linear.
547 \return The array range of the first continuous array of the internal buffer. In the case the
548 <code>circular_buffer</code> is empty the size of the returned array is <code>0</code>.
550 \par Exception Safety
552 \par Iterator Invalidation
553 Does not invalidate any iterators.
555 Constant (in the size of the <code>circular_buffer</code>).
556 \warning In general invoking any method which modifies the internal state of the circular_buffer may
557 delinearize the internal buffer and invalidate the array ranges returned by <code>array_one()</code>
558 and <code>array_two()</code> (and their const versions).
559 \note In the case the internal buffer is linear e.g. <code>|a|b|c|d|e|f|g| | | |</code> the "array one" is
560 represented by <code>|a|b|c|d|e|f|g|</code> and the "array two" does not exist (the
561 <code>array_two()</code> method returns an array with the size <code>0</code>).
562 \sa <code>array_two()</code>, <code>linearize()</code>
564 array_range array_one() {
565 return array_range(m_first, (m_last <= m_first && !empty() ? m_end : m_last) - m_first);
568 //! Get the second continuous array of the internal buffer.
570 This method in combination with <code>array_one()</code> can be useful when passing the stored data into
571 a legacy C API as an array.
572 \return The array range of the second continuous array of the internal buffer. In the case the internal buffer
573 is linear or the <code>circular_buffer</code> is empty the size of the returned array is
576 \par Exception Safety
578 \par Iterator Invalidation
579 Does not invalidate any iterators.
581 Constant (in the size of the <code>circular_buffer</code>).
582 \sa <code>array_one()</code>
584 array_range array_two() {
585 return array_range(m_buff, m_last <= m_first && !empty() ? m_last - m_buff : 0);
588 //! Get the first continuous array of the internal buffer.
590 This method in combination with <code>array_two() const</code> can be useful when passing the stored data into
591 a legacy C API as an array.
592 \return The array range of the first continuous array of the internal buffer. In the case the
593 <code>circular_buffer</code> is empty the size of the returned array is <code>0</code>.
595 \par Exception Safety
597 \par Iterator Invalidation
598 Does not invalidate any iterators.
600 Constant (in the size of the <code>circular_buffer</code>).
601 \sa <code>array_two() const</code>; <code>array_one()</code> for more details how to pass data into a legacy C
604 const_array_range array_one() const {
605 return const_array_range(m_first, (m_last <= m_first && !empty() ? m_end : m_last) - m_first);
608 //! Get the second continuous array of the internal buffer.
610 This method in combination with <code>array_one() const</code> can be useful when passing the stored data into
611 a legacy C API as an array.
612 \return The array range of the second continuous array of the internal buffer. In the case the internal buffer
613 is linear or the <code>circular_buffer</code> is empty the size of the returned array is
616 \par Exception Safety
618 \par Iterator Invalidation
619 Does not invalidate any iterators.
621 Constant (in the size of the <code>circular_buffer</code>).
622 \sa <code>array_one() const</code>
624 const_array_range array_two() const {
625 return const_array_range(m_buff, m_last <= m_first && !empty() ? m_last - m_buff : 0);
628 //! Linearize the internal buffer into a continuous array.
630 This method can be useful when passing the stored data into a legacy C API as an array.
631 \post <code>\&(*this)[0] \< \&(*this)[1] \< ... \< \&(*this)[size() - 1]</code>
632 \return A pointer to the beginning of the array or <code>0</code> if empty.
633 \throws <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>.
634 \par Exception Safety
635 Basic; no-throw if the operations in the <i>Throws</i> section do not throw anything.
636 \par Iterator Invalidation
637 Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to
638 <code>end()</code>); does not invalidate any iterators if the postcondition (the <i>Effect</i>) is already
639 met prior calling this method.
641 Linear (in the size of the <code>circular_buffer</code>); constant if the postcondition (the
642 <i>Effect</i>) is already met.
643 \warning In general invoking any method which modifies the internal state of the <code>circular_buffer</code>
644 may delinearize the internal buffer and invalidate the returned pointer.
645 \sa <code>array_one()</code> and <code>array_two()</code> for the other option how to pass data into a legacy
646 C API; <code>is_linearized()</code>, <code>rotate(const_iterator)</code>
648 pointer linearize() {
651 if (m_first < m_last || m_last == m_buff)
653 pointer src = m_first;
654 pointer dest = m_buff;
656 size_type constructed = 0;
658 for (pointer first = m_first; dest < src; src = first) {
659 for (size_type ii = 0; src < m_end; ++src, ++dest, ++moved, ++ii) {
660 if (moved == size()) {
668 if (is_uninitialized(dest)) {
669 boost::container::allocator_traits<Alloc>::construct(m_alloc, boost::addressof(*dest), boost::move_if_noexcept(*src));
672 value_type tmp = boost::move_if_noexcept(*src);
673 replace(src, boost::move_if_noexcept(*dest));
674 replace(dest, boost::move(tmp));
679 m_last += constructed;
680 m_size += constructed;
684 for (src = m_end - constructed; src < m_end; ++src)
687 m_last = add(m_buff, size());
688 #if BOOST_CB_ENABLE_DEBUG
689 invalidate_iterators_except(end());
694 //! Is the <code>circular_buffer</code> linearized?
696 \return <code>true</code> if the internal buffer is linearized into a continuous array (i.e. the
697 <code>circular_buffer</code> meets a condition
698 <code>\&(*this)[0] \< \&(*this)[1] \< ... \< \&(*this)[size() - 1]</code>);
699 <code>false</code> otherwise.
701 \par Exception Safety
703 \par Iterator Invalidation
704 Does not invalidate any iterators.
706 Constant (in the size of the <code>circular_buffer</code>).
707 \sa <code>linearize()</code>, <code>array_one()</code>, <code>array_two()</code>
709 bool is_linearized() const BOOST_NOEXCEPT { return m_first < m_last || m_last == m_buff; }
711 //! Rotate elements in the <code>circular_buffer</code>.
713 A more effective implementation of
714 <code><a href="http://www.sgi.com/tech/stl/rotate.html">std::rotate</a></code>.
715 \pre <code>new_begin</code> is a valid iterator pointing to the <code>circular_buffer</code> <b>except</b> its
717 \post Before calling the method suppose:<br><br>
718 <code>m == std::distance(new_begin, end())</code><br><code>n == std::distance(begin(), new_begin)</code>
719 <br><code>val_0 == *new_begin, val_1 == *(new_begin + 1), ... val_m == *(new_begin + m)</code><br>
720 <code>val_r1 == *(new_begin - 1), val_r2 == *(new_begin - 2), ... val_rn == *(new_begin - n)</code><br>
721 <br>then after call to the method:<br><br>
722 <code>val_0 == (*this)[0] \&\& val_1 == (*this)[1] \&\& ... \&\& val_m == (*this)[m - 1] \&\& val_r1 ==
723 (*this)[m + n - 1] \&\& val_r2 == (*this)[m + n - 2] \&\& ... \&\& val_rn == (*this)[m]</code>
724 \param new_begin The new beginning.
725 \throws See <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>.
726 \par Exception Safety
727 Basic; no-throw if the <code>circular_buffer</code> is full or <code>new_begin</code> points to
728 <code>begin()</code> or if the operations in the <i>Throws</i> section do not throw anything.
729 \par Iterator Invalidation
730 If <code>m \< n</code> invalidates iterators pointing to the last <code>m</code> elements
731 (<b>including</b> <code>new_begin</code>, but not iterators equal to <code>end()</code>) else invalidates
732 iterators pointing to the first <code>n</code> elements; does not invalidate any iterators if the
733 <code>circular_buffer</code> is full.
735 Linear (in <code>(std::min)(m, n)</code>); constant if the <code>circular_buffer</code> is full.
736 \sa <code><a href="http://www.sgi.com/tech/stl/rotate.html">std::rotate</a></code>
738 void rotate(const_iterator new_begin) {
739 BOOST_CB_ASSERT(new_begin.is_valid(this)); // check for uninitialized or invalidated iterator
740 BOOST_CB_ASSERT(new_begin.m_it != 0); // check for iterator pointing to end()
742 m_first = m_last = const_cast<pointer>(new_begin.m_it);
744 difference_type m = end() - new_begin;
745 difference_type n = new_begin - begin();
748 push_front(boost::move_if_noexcept(back()));
753 push_back(boost::move_if_noexcept(front()));
762 //! Get the number of elements currently stored in the <code>circular_buffer</code>.
764 \return The number of elements stored in the <code>circular_buffer</code>.
766 \par Exception Safety
768 \par Iterator Invalidation
769 Does not invalidate any iterators.
771 Constant (in the size of the <code>circular_buffer</code>).
772 \sa <code>capacity()</code>, <code>max_size()</code>, <code>reserve()</code>,
773 <code>\link resize() resize(size_type, const_reference)\endlink</code>
775 size_type size() const BOOST_NOEXCEPT { return m_size; }
777 /*! \brief Get the largest possible size or capacity of the <code>circular_buffer</code>. (It depends on
778 allocator's %max_size()).
779 \return The maximum size/capacity the <code>circular_buffer</code> can be set to.
781 \par Exception Safety
783 \par Iterator Invalidation
784 Does not invalidate any iterators.
786 Constant (in the size of the <code>circular_buffer</code>).
787 \sa <code>size()</code>, <code>capacity()</code>, <code>reserve()</code>
789 size_type max_size() const BOOST_NOEXCEPT {
790 return (std::min<size_type>)(boost::container::allocator_traits<Alloc>::max_size(m_alloc), (std::numeric_limits<difference_type>::max)());
793 //! Is the <code>circular_buffer</code> empty?
795 \return <code>true</code> if there are no elements stored in the <code>circular_buffer</code>;
796 <code>false</code> otherwise.
798 \par Exception Safety
800 \par Iterator Invalidation
801 Does not invalidate any iterators.
803 Constant (in the size of the <code>circular_buffer</code>).
804 \sa <code>full()</code>
806 bool empty() const BOOST_NOEXCEPT { return size() == 0; }
808 //! Is the <code>circular_buffer</code> full?
810 \return <code>true</code> if the number of elements stored in the <code>circular_buffer</code>
811 equals the capacity of the <code>circular_buffer</code>; <code>false</code> otherwise.
813 \par Exception Safety
815 \par Iterator Invalidation
816 Does not invalidate any iterators.
818 Constant (in the size of the <code>circular_buffer</code>).
819 \sa <code>empty()</code>
821 bool full() const BOOST_NOEXCEPT { return capacity() == size(); }
823 /*! \brief Get the maximum number of elements which can be inserted into the <code>circular_buffer</code> without
824 overwriting any of already stored elements.
825 \return <code>capacity() - size()</code>
827 \par Exception Safety
829 \par Iterator Invalidation
830 Does not invalidate any iterators.
832 Constant (in the size of the <code>circular_buffer</code>).
833 \sa <code>capacity()</code>, <code>size()</code>, <code>max_size()</code>
835 size_type reserve() const BOOST_NOEXCEPT { return capacity() - size(); }
837 //! Get the capacity of the <code>circular_buffer</code>.
839 \return The maximum number of elements which can be stored in the <code>circular_buffer</code>.
841 \par Exception Safety
843 \par Iterator Invalidation
844 Does not invalidate any iterators.
846 Constant (in the size of the <code>circular_buffer</code>).
847 \sa <code>reserve()</code>, <code>size()</code>, <code>max_size()</code>,
848 <code>set_capacity(capacity_type)</code>
850 capacity_type capacity() const BOOST_NOEXCEPT { return m_end - m_buff; }
852 //! Change the capacity of the <code>circular_buffer</code>.
854 \pre If <code>T</code> is a move only type, then compiler shall support <code>noexcept</code> modifiers
855 and move constructor of <code>T</code> must be marked with it (must not throw exceptions).
856 \post <code>capacity() == new_capacity \&\& size() \<= new_capacity</code><br><br>
857 If the current number of elements stored in the <code>circular_buffer</code> is greater than the desired
858 new capacity then number of <code>[size() - new_capacity]</code> <b>last</b> elements will be removed and
859 the new size will be equal to <code>new_capacity</code>.
860 \param new_capacity The new capacity.
861 \throws "An allocation error" if memory is exhausted, (<code>std::bad_alloc</code> if the standard allocator is
863 Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept.
864 \par Exception Safety
866 \par Iterator Invalidation
867 Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to
868 <code>end()</code>) if the new capacity is different from the original.
870 Linear (in <code>min[size(), new_capacity]</code>).
871 \sa <code>rset_capacity(capacity_type)</code>,
872 <code>\link resize() resize(size_type, const_reference)\endlink</code>
874 void set_capacity(capacity_type new_capacity) {
875 if (new_capacity == capacity())
877 pointer buff = allocate(new_capacity);
878 iterator b = begin();
881 cb_details::uninitialized_move_if_noexcept(b, b + (std::min)(new_capacity, size()), buff, m_alloc),
884 deallocate(buff, new_capacity);
890 //! Change the size of the <code>circular_buffer</code>.
892 \post <code>size() == new_size \&\& capacity() >= new_size</code><br><br>
893 If the new size is greater than the current size, copies of <code>item</code> will be inserted at the
894 <b>back</b> of the of the <code>circular_buffer</code> in order to achieve the desired size. In the case
895 the resulting size exceeds the current capacity the capacity will be set to <code>new_size</code>.<br>
896 If the current number of elements stored in the <code>circular_buffer</code> is greater than the desired
897 new size then number of <code>[size() - new_size]</code> <b>last</b> elements will be removed. (The
898 capacity will remain unchanged.)
899 \param new_size The new size.
900 \param item The element the <code>circular_buffer</code> will be filled with in order to gain the requested
901 size. (See the <i>Effect</i>.)
902 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
904 Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept.
905 \par Exception Safety
907 \par Iterator Invalidation
908 Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to
909 <code>end()</code>) if the new size is greater than the current capacity. Invalidates iterators pointing
910 to the removed elements if the new size is lower that the original size. Otherwise it does not invalidate
913 Linear (in the new size of the <code>circular_buffer</code>).
914 \sa <code>\link rresize() rresize(size_type, const_reference)\endlink</code>,
915 <code>set_capacity(capacity_type)</code>
917 void resize(size_type new_size, param_value_type item = value_type()) {
918 if (new_size > size()) {
919 if (new_size > capacity())
920 set_capacity(new_size);
921 insert(end(), new_size - size(), item);
924 erase(e - (size() - new_size), e);
928 //! Change the capacity of the <code>circular_buffer</code>.
930 \pre If <code>T</code> is a move only type, then compiler shall support <code>noexcept</code> modifiers
931 and move constructor of <code>T</code> must be marked with it (must not throw exceptions).
932 \post <code>capacity() == new_capacity \&\& size() \<= new_capacity</code><br><br>
933 If the current number of elements stored in the <code>circular_buffer</code> is greater than the desired
934 new capacity then number of <code>[size() - new_capacity]</code> <b>first</b> elements will be removed
935 and the new size will be equal to <code>new_capacity</code>.
936 \param new_capacity The new capacity.
937 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
939 Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept.
940 \par Exception Safety
942 \par Iterator Invalidation
943 Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to
944 <code>end()</code>) if the new capacity is different from the original.
946 Linear (in <code>min[size(), new_capacity]</code>).
947 \sa <code>set_capacity(capacity_type)</code>,
948 <code>\link rresize() rresize(size_type, const_reference)\endlink</code>
950 void rset_capacity(capacity_type new_capacity) {
951 if (new_capacity == capacity())
953 pointer buff = allocate(new_capacity);
956 reset(buff, cb_details::uninitialized_move_if_noexcept(e - (std::min)(new_capacity, size()),
957 e, buff, m_alloc), new_capacity);
959 deallocate(buff, new_capacity);
965 //! Change the size of the <code>circular_buffer</code>.
967 \post <code>size() == new_size \&\& capacity() >= new_size</code><br><br>
968 If the new size is greater than the current size, copies of <code>item</code> will be inserted at the
969 <b>front</b> of the of the <code>circular_buffer</code> in order to achieve the desired size. In the case
970 the resulting size exceeds the current capacity the capacity will be set to <code>new_size</code>.<br>
971 If the current number of elements stored in the <code>circular_buffer</code> is greater than the desired
972 new size then number of <code>[size() - new_size]</code> <b>first</b> elements will be removed. (The
973 capacity will remain unchanged.)
974 \param new_size The new size.
975 \param item The element the <code>circular_buffer</code> will be filled with in order to gain the requested
976 size. (See the <i>Effect</i>.)
977 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
979 Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept.
980 \par Exception Safety
982 \par Iterator Invalidation
983 Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to
984 <code>end()</code>) if the new size is greater than the current capacity. Invalidates iterators pointing
985 to the removed elements if the new size is lower that the original size. Otherwise it does not invalidate
988 Linear (in the new size of the <code>circular_buffer</code>).
989 \sa <code>\link resize() resize(size_type, const_reference)\endlink</code>,
990 <code>rset_capacity(capacity_type)</code>
992 void rresize(size_type new_size, param_value_type item = value_type()) {
993 if (new_size > size()) {
994 if (new_size > capacity())
995 set_capacity(new_size);
996 rinsert(begin(), new_size - size(), item);
998 rerase(begin(), end() - new_size);
1002 // Construction/Destruction
1004 //! Create an empty <code>circular_buffer</code> with zero capacity.
1006 \post <code>capacity() == 0 \&\& size() == 0</code>
1007 \param alloc The allocator.
1011 \warning Since Boost version 1.36 the behaviour of this constructor has changed. Now the constructor does not
1012 allocate any memory and both capacity and size are set to zero. Also note when inserting an element
1013 into a <code>circular_buffer</code> with zero capacity (e.g. by
1014 <code>\link push_back() push_back(const_reference)\endlink</code> or
1015 <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>) nothing
1016 will be inserted and the size (as well as capacity) remains zero.
1017 \note You can explicitly set the capacity by calling the <code>set_capacity(capacity_type)</code> method or you
1018 can use the other constructor with the capacity specified.
1019 \sa <code>circular_buffer(capacity_type, const allocator_type& alloc)</code>,
1020 <code>set_capacity(capacity_type)</code>
1022 explicit circular_buffer(const allocator_type& alloc = allocator_type()) BOOST_NOEXCEPT
1023 : m_buff(0), m_end(0), m_first(0), m_last(0), m_size(0), m_alloc(alloc) {}
1025 //! Create an empty <code>circular_buffer</code> with the specified capacity.
1027 \post <code>capacity() == buffer_capacity \&\& size() == 0</code>
1028 \param buffer_capacity The maximum number of elements which can be stored in the <code>circular_buffer</code>.
1029 \param alloc The allocator.
1030 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
1035 explicit circular_buffer(capacity_type buffer_capacity, const allocator_type& alloc = allocator_type())
1036 : m_size(0), m_alloc(alloc) {
1037 initialize_buffer(buffer_capacity);
1038 m_first = m_last = m_buff;
1041 /*! \brief Create a full <code>circular_buffer</code> with the specified capacity and filled with <code>n</code>
1042 copies of <code>item</code>.
1043 \post <code>capacity() == n \&\& full() \&\& (*this)[0] == item \&\& (*this)[1] == item \&\& ... \&\&
1044 (*this)[n - 1] == item </code>
1045 \param n The number of elements the created <code>circular_buffer</code> will be filled with.
1046 \param item The element the created <code>circular_buffer</code> will be filled with.
1047 \param alloc The allocator.
1048 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
1050 Whatever <code>T::T(const T&)</code> throws.
1052 Linear (in the <code>n</code>).
1054 circular_buffer(size_type n, param_value_type item, const allocator_type& alloc = allocator_type())
1055 : m_size(n), m_alloc(alloc) {
1056 initialize_buffer(n, item);
1057 m_first = m_last = m_buff;
1060 /*! \brief Create a <code>circular_buffer</code> with the specified capacity and filled with <code>n</code>
1061 copies of <code>item</code>.
1062 \pre <code>buffer_capacity >= n</code>
1063 \post <code>capacity() == buffer_capacity \&\& size() == n \&\& (*this)[0] == item \&\& (*this)[1] == item
1064 \&\& ... \&\& (*this)[n - 1] == item</code>
1065 \param buffer_capacity The capacity of the created <code>circular_buffer</code>.
1066 \param n The number of elements the created <code>circular_buffer</code> will be filled with.
1067 \param item The element the created <code>circular_buffer</code> will be filled with.
1068 \param alloc The allocator.
1069 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
1071 Whatever <code>T::T(const T&)</code> throws.
1073 Linear (in the <code>n</code>).
1075 circular_buffer(capacity_type buffer_capacity, size_type n, param_value_type item,
1076 const allocator_type& alloc = allocator_type())
1077 : m_size(n), m_alloc(alloc) {
1078 BOOST_CB_ASSERT(buffer_capacity >= size()); // check for capacity lower than size
1079 initialize_buffer(buffer_capacity, item);
1081 m_last = buffer_capacity == n ? m_buff : m_buff + n;
1084 //! The copy constructor.
1086 Creates a copy of the specified <code>circular_buffer</code>.
1087 \post <code>*this == cb</code>
1088 \param cb The <code>circular_buffer</code> to be copied.
1089 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
1091 Whatever <code>T::T(const T&)</code> throws.
1093 Linear (in the size of <code>cb</code>).
1095 circular_buffer(const circular_buffer<T, Alloc>& cb)
1097 #if BOOST_CB_ENABLE_DEBUG
1098 debug_iterator_registry(),
1100 m_size(cb.size()), m_alloc(cb.get_allocator()) {
1101 initialize_buffer(cb.capacity());
1104 m_last = cb_details::uninitialized_copy(cb.begin(), cb.end(), m_buff, m_alloc);
1105 } BOOST_CATCH(...) {
1106 deallocate(m_buff, cb.capacity());
1110 if (m_last == m_end)
1114 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
1115 //! The move constructor.
1116 /*! \brief Move constructs a <code>circular_buffer</code> from <code>cb</code>, leaving <code>cb</code> empty.
1117 \pre C++ compiler with rvalue references support.
1118 \post <code>cb.empty()</code>
1119 \param cb <code>circular_buffer</code> to 'steal' value from.
1123 circular_buffer(circular_buffer<T, Alloc>&& cb) BOOST_NOEXCEPT
1124 : m_buff(0), m_end(0), m_first(0), m_last(0), m_size(0), m_alloc(cb.get_allocator()) {
1127 #endif // BOOST_NO_CXX11_RVALUE_REFERENCES
1129 //! Create a full <code>circular_buffer</code> filled with a copy of the range.
1131 \pre Valid range <code>[first, last)</code>.<br>
1132 <code>first</code> and <code>last</code> have to meet the requirements of
1133 <a href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>.
1134 \post <code>capacity() == std::distance(first, last) \&\& full() \&\& (*this)[0]== *first \&\&
1135 (*this)[1] == *(first + 1) \&\& ... \&\& (*this)[std::distance(first, last) - 1] == *(last - 1)</code>
1136 \param first The beginning of the range to be copied.
1137 \param last The end of the range to be copied.
1138 \param alloc The allocator.
1139 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
1141 Whatever <code>T::T(const T&)</code> throws.
1143 Linear (in the <code>std::distance(first, last)</code>).
1145 template <class InputIterator>
1146 circular_buffer(InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type())
1148 initialize(first, last, is_integral<InputIterator>());
1151 //! Create a <code>circular_buffer</code> with the specified capacity and filled with a copy of the range.
1153 \pre Valid range <code>[first, last)</code>.<br>
1154 <code>first</code> and <code>last</code> have to meet the requirements of
1155 <a href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>.
1156 \post <code>capacity() == buffer_capacity \&\& size() \<= std::distance(first, last) \&\&
1157 (*this)[0]== *(last - buffer_capacity) \&\& (*this)[1] == *(last - buffer_capacity + 1) \&\& ... \&\&
1158 (*this)[buffer_capacity - 1] == *(last - 1)</code><br><br>
1159 If the number of items to be copied from the range <code>[first, last)</code> is greater than the
1160 specified <code>buffer_capacity</code> then only elements from the range
1161 <code>[last - buffer_capacity, last)</code> will be copied.
1162 \param buffer_capacity The capacity of the created <code>circular_buffer</code>.
1163 \param first The beginning of the range to be copied.
1164 \param last The end of the range to be copied.
1165 \param alloc The allocator.
1166 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
1168 Whatever <code>T::T(const T&)</code> throws.
1170 Linear (in <code>std::distance(first, last)</code>; in
1171 <code>min[capacity, std::distance(first, last)]</code> if the <code>InputIterator</code> is a
1172 <a href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">RandomAccessIterator</a>).
1174 template <class InputIterator>
1175 circular_buffer(capacity_type buffer_capacity, InputIterator first, InputIterator last,
1176 const allocator_type& alloc = allocator_type())
1178 initialize(buffer_capacity, first, last, is_integral<InputIterator>());
1183 Destroys the <code>circular_buffer</code>.
1185 \par Iterator Invalidation
1186 Invalidates all iterators pointing to the <code>circular_buffer</code> (including iterators equal to
1187 <code>end()</code>).
1189 Constant (in the size of the <code>circular_buffer</code>) for scalar types; linear for other types.
1190 \sa <code>clear()</code>
1192 ~circular_buffer() BOOST_NOEXCEPT {
1194 #if BOOST_CB_ENABLE_DEBUG
1195 invalidate_all_iterators();
1202 //! The assign operator.
1204 Makes this <code>circular_buffer</code> to become a copy of the specified <code>circular_buffer</code>.
1205 \post <code>*this == cb</code>
1206 \param cb The <code>circular_buffer</code> to be copied.
1207 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
1209 Whatever <code>T::T(const T&)</code> throws.
1210 \par Exception Safety
1212 \par Iterator Invalidation
1213 Invalidates all iterators pointing to this <code>circular_buffer</code> (except iterators equal to
1214 <code>end()</code>).
1216 Linear (in the size of <code>cb</code>).
1217 \sa <code>\link assign(size_type, param_value_type) assign(size_type, const_reference)\endlink</code>,
1218 <code>\link assign(capacity_type, size_type, param_value_type)
1219 assign(capacity_type, size_type, const_reference)\endlink</code>,
1220 <code>assign(InputIterator, InputIterator)</code>,
1221 <code>assign(capacity_type, InputIterator, InputIterator)</code>
1223 circular_buffer<T, Alloc>& operator = (const circular_buffer<T, Alloc>& cb) {
1226 pointer buff = allocate(cb.capacity());
1228 reset(buff, cb_details::uninitialized_copy(cb.begin(), cb.end(), buff, m_alloc), cb.capacity());
1229 } BOOST_CATCH(...) {
1230 deallocate(buff, cb.capacity());
1237 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
1238 /*! \brief Move assigns content of <code>cb</code> to <code>*this</code>, leaving <code>cb</code> empty.
1239 \pre C++ compiler with rvalue references support.
1240 \post <code>cb.empty()</code>
1241 \param cb <code>circular_buffer</code> to 'steal' value from.
1246 circular_buffer<T, Alloc>& operator = (circular_buffer<T, Alloc>&& cb) BOOST_NOEXCEPT {
1247 cb.swap(*this); // now `this` holds `cb`
1248 circular_buffer<T, Alloc>(get_allocator()) // temprary that holds initial `cb` allocator
1249 .swap(cb); // makes `cb` empty
1252 #endif // BOOST_NO_CXX11_RVALUE_REFERENCES
1254 //! Assign <code>n</code> items into the <code>circular_buffer</code>.
1256 The content of the <code>circular_buffer</code> will be removed and replaced with <code>n</code> copies of the
1258 \post <code>capacity() == n \&\& size() == n \&\& (*this)[0] == item \&\& (*this)[1] == item \&\& ... \&\&
1259 (*this) [n - 1] == item</code>
1260 \param n The number of elements the <code>circular_buffer</code> will be filled with.
1261 \param item The element the <code>circular_buffer</code> will be filled with.
1262 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
1264 Whatever <code>T::T(const T&)</code> throws.
1265 \par Exception Safety
1267 \par Iterator Invalidation
1268 Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to
1269 <code>end()</code>).
1271 Linear (in the <code>n</code>).
1272 \sa <code>\link operator=(const circular_buffer&) operator=\endlink</code>,
1273 <code>\link assign(capacity_type, size_type, param_value_type)
1274 assign(capacity_type, size_type, const_reference)\endlink</code>,
1275 <code>assign(InputIterator, InputIterator)</code>,
1276 <code>assign(capacity_type, InputIterator, InputIterator)</code>
1278 void assign(size_type n, param_value_type item) {
1279 assign_n(n, n, cb_details::assign_n<param_value_type, allocator_type>(n, item, m_alloc));
1282 //! Assign <code>n</code> items into the <code>circular_buffer</code> specifying the capacity.
1284 The capacity of the <code>circular_buffer</code> will be set to the specified value and the content of the
1285 <code>circular_buffer</code> will be removed and replaced with <code>n</code> copies of the <code>item</code>.
1286 \pre <code>capacity >= n</code>
1287 \post <code>capacity() == buffer_capacity \&\& size() == n \&\& (*this)[0] == item \&\& (*this)[1] == item
1288 \&\& ... \&\& (*this) [n - 1] == item </code>
1289 \param buffer_capacity The new capacity.
1290 \param n The number of elements the <code>circular_buffer</code> will be filled with.
1291 \param item The element the <code>circular_buffer</code> will be filled with.
1292 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
1294 Whatever <code>T::T(const T&)</code> throws.
1295 \par Exception Safety
1297 \par Iterator Invalidation
1298 Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to
1299 <code>end()</code>).
1301 Linear (in the <code>n</code>).
1302 \sa <code>\link operator=(const circular_buffer&) operator=\endlink</code>,
1303 <code>\link assign(size_type, param_value_type) assign(size_type, const_reference)\endlink</code>,
1304 <code>assign(InputIterator, InputIterator)</code>,
1305 <code>assign(capacity_type, InputIterator, InputIterator)</code>
1307 void assign(capacity_type buffer_capacity, size_type n, param_value_type item) {
1308 BOOST_CB_ASSERT(buffer_capacity >= n); // check for new capacity lower than n
1309 assign_n(buffer_capacity, n, cb_details::assign_n<param_value_type, allocator_type>(n, item, m_alloc));
1312 //! Assign a copy of the range into the <code>circular_buffer</code>.
1314 The content of the <code>circular_buffer</code> will be removed and replaced with copies of elements from the
1316 \pre Valid range <code>[first, last)</code>.<br>
1317 <code>first</code> and <code>last</code> have to meet the requirements of
1318 <a href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>.
1319 \post <code>capacity() == std::distance(first, last) \&\& size() == std::distance(first, last) \&\&
1320 (*this)[0]== *first \&\& (*this)[1] == *(first + 1) \&\& ... \&\& (*this)[std::distance(first, last) - 1]
1321 == *(last - 1)</code>
1322 \param first The beginning of the range to be copied.
1323 \param last The end of the range to be copied.
1324 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
1326 Whatever <code>T::T(const T&)</code> throws.
1327 \par Exception Safety
1329 \par Iterator Invalidation
1330 Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to
1331 <code>end()</code>).
1333 Linear (in the <code>std::distance(first, last)</code>).
1334 \sa <code>\link operator=(const circular_buffer&) operator=\endlink</code>,
1335 <code>\link assign(size_type, param_value_type) assign(size_type, const_reference)\endlink</code>,
1336 <code>\link assign(capacity_type, size_type, param_value_type)
1337 assign(capacity_type, size_type, const_reference)\endlink</code>,
1338 <code>assign(capacity_type, InputIterator, InputIterator)</code>
1340 template <class InputIterator>
1341 void assign(InputIterator first, InputIterator last) {
1342 assign(first, last, is_integral<InputIterator>());
1345 //! Assign a copy of the range into the <code>circular_buffer</code> specifying the capacity.
1347 The capacity of the <code>circular_buffer</code> will be set to the specified value and the content of the
1348 <code>circular_buffer</code> will be removed and replaced with copies of elements from the specified range.
1349 \pre Valid range <code>[first, last)</code>.<br>
1350 <code>first</code> and <code>last</code> have to meet the requirements of
1351 <a href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>.
1352 \post <code>capacity() == buffer_capacity \&\& size() \<= std::distance(first, last) \&\&
1353 (*this)[0]== *(last - buffer_capacity) \&\& (*this)[1] == *(last - buffer_capacity + 1) \&\& ... \&\&
1354 (*this)[buffer_capacity - 1] == *(last - 1)</code><br><br>
1355 If the number of items to be copied from the range <code>[first, last)</code> is greater than the
1356 specified <code>buffer_capacity</code> then only elements from the range
1357 <code>[last - buffer_capacity, last)</code> will be copied.
1358 \param buffer_capacity The new capacity.
1359 \param first The beginning of the range to be copied.
1360 \param last The end of the range to be copied.
1361 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
1363 Whatever <code>T::T(const T&)</code> throws.
1364 \par Exception Safety
1366 \par Iterator Invalidation
1367 Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to
1368 <code>end()</code>).
1370 Linear (in <code>std::distance(first, last)</code>; in
1371 <code>min[capacity, std::distance(first, last)]</code> if the <code>InputIterator</code> is a
1372 <a href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">RandomAccessIterator</a>).
1373 \sa <code>\link operator=(const circular_buffer&) operator=\endlink</code>,
1374 <code>\link assign(size_type, param_value_type) assign(size_type, const_reference)\endlink</code>,
1375 <code>\link assign(capacity_type, size_type, param_value_type)
1376 assign(capacity_type, size_type, const_reference)\endlink</code>,
1377 <code>assign(InputIterator, InputIterator)</code>
1379 template <class InputIterator>
1380 void assign(capacity_type buffer_capacity, InputIterator first, InputIterator last) {
1381 assign(buffer_capacity, first, last, is_integral<InputIterator>());
1384 //! Swap the contents of two <code>circular_buffer</code>s.
1386 \post <code>this</code> contains elements of <code>cb</code> and vice versa; the capacity of <code>this</code>
1387 equals to the capacity of <code>cb</code> and vice versa.
1388 \param cb The <code>circular_buffer</code> whose content will be swapped.
1390 \par Exception Safety
1392 \par Iterator Invalidation
1393 Invalidates all iterators of both <code>circular_buffer</code>s. (On the other hand the iterators still
1394 point to the same elements but within another container. If you want to rely on this feature you have to
1395 turn the <a href="#debug">Debug Support</a> off otherwise an assertion will report an error if such
1396 invalidated iterator is used.)
1398 Constant (in the size of the <code>circular_buffer</code>).
1399 \sa <code>swap(circular_buffer<T, Alloc>&, circular_buffer<T, Alloc>&)</code>
1401 void swap(circular_buffer<T, Alloc>& cb) BOOST_NOEXCEPT {
1402 swap_allocator(cb, is_stateless<allocator_type>());
1403 adl_move_swap(m_buff, cb.m_buff);
1404 adl_move_swap(m_end, cb.m_end);
1405 adl_move_swap(m_first, cb.m_first);
1406 adl_move_swap(m_last, cb.m_last);
1407 adl_move_swap(m_size, cb.m_size);
1408 #if BOOST_CB_ENABLE_DEBUG
1409 invalidate_all_iterators();
1410 cb.invalidate_all_iterators();
1416 template <class ValT>
1417 void push_back_impl(ValT item) {
1421 replace(m_last, static_cast<ValT>(item));
1425 boost::container::allocator_traits<Alloc>::construct(m_alloc, boost::addressof(*m_last), static_cast<ValT>(item));
1431 template <class ValT>
1432 void push_front_impl(ValT item) {
1438 replace(m_first, static_cast<ValT>(item));
1442 boost::container::allocator_traits<Alloc>::construct(m_alloc, boost::addressof(*m_first), static_cast<ValT>(item));
1445 } BOOST_CATCH(...) {
1453 //! Insert a new element at the end of the <code>circular_buffer</code>.
1455 \post if <code>capacity() > 0</code> then <code>back() == item</code><br>
1456 If the <code>circular_buffer</code> is full, the first element will be removed. If the capacity is
1457 <code>0</code>, nothing will be inserted.
1458 \param item The element to be inserted.
1459 \throws Whatever <code>T::T(const T&)</code> throws.
1460 Whatever <code>T::operator = (const T&)</code> throws.
1461 \par Exception Safety
1462 Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything.
1463 \par Iterator Invalidation
1464 Does not invalidate any iterators with the exception of iterators pointing to the overwritten element.
1466 Constant (in the size of the <code>circular_buffer</code>).
1467 \sa <code>\link push_front() push_front(const_reference)\endlink</code>,
1468 <code>pop_back()</code>, <code>pop_front()</code>
1470 void push_back(param_value_type item) {
1471 push_back_impl<param_value_type>(item);
1474 //! Insert a new element at the end of the <code>circular_buffer</code> using rvalue references or rvalues references emulation.
1476 \post if <code>capacity() > 0</code> then <code>back() == item</code><br>
1477 If the <code>circular_buffer</code> is full, the first element will be removed. If the capacity is
1478 <code>0</code>, nothing will be inserted.
1479 \param item The element to be inserted.
1480 \throws Whatever <code>T::T(T&&)</code> throws.
1481 Whatever <code>T::operator = (T&&)</code> throws.
1482 \par Exception Safety
1483 Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything.
1484 \par Iterator Invalidation
1485 Does not invalidate any iterators with the exception of iterators pointing to the overwritten element.
1487 Constant (in the size of the <code>circular_buffer</code>).
1488 \sa <code>\link push_front() push_front(const_reference)\endlink</code>,
1489 <code>pop_back()</code>, <code>pop_front()</code>
1491 void push_back(rvalue_type item) {
1492 push_back_impl<rvalue_type>(boost::move(item));
1495 //! Insert a new default-constructed element at the end of the <code>circular_buffer</code>.
1497 \post if <code>capacity() > 0</code> then <code>back() == item</code><br>
1498 If the <code>circular_buffer</code> is full, the first element will be removed. If the capacity is
1499 <code>0</code>, nothing will be inserted.
1500 \throws Whatever <code>T::T()</code> throws.
1501 Whatever <code>T::T(T&&)</code> throws.
1502 Whatever <code>T::operator = (T&&)</code> throws.
1503 \par Exception Safety
1504 Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything.
1505 \par Iterator Invalidation
1506 Does not invalidate any iterators with the exception of iterators pointing to the overwritten element.
1508 Constant (in the size of the <code>circular_buffer</code>).
1509 \sa <code>\link push_front() push_front(const_reference)\endlink</code>,
1510 <code>pop_back()</code>, <code>pop_front()</code>
1514 push_back(boost::move(temp));
1517 //! Insert a new element at the beginning of the <code>circular_buffer</code>.
1519 \post if <code>capacity() > 0</code> then <code>front() == item</code><br>
1520 If the <code>circular_buffer</code> is full, the last element will be removed. If the capacity is
1521 <code>0</code>, nothing will be inserted.
1522 \param item The element to be inserted.
1523 \throws Whatever <code>T::T(const T&)</code> throws.
1524 Whatever <code>T::operator = (const T&)</code> throws.
1525 \par Exception Safety
1526 Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything.
1527 \par Iterator Invalidation
1528 Does not invalidate any iterators with the exception of iterators pointing to the overwritten element.
1530 Constant (in the size of the <code>circular_buffer</code>).
1531 \sa <code>\link push_back() push_back(const_reference)\endlink</code>,
1532 <code>pop_back()</code>, <code>pop_front()</code>
1534 void push_front(param_value_type item) {
1535 push_front_impl<param_value_type>(item);
1538 //! Insert a new element at the beginning of the <code>circular_buffer</code> using rvalue references or rvalues references emulation.
1540 \post if <code>capacity() > 0</code> then <code>front() == item</code><br>
1541 If the <code>circular_buffer</code> is full, the last element will be removed. If the capacity is
1542 <code>0</code>, nothing will be inserted.
1543 \param item The element to be inserted.
1544 \throws Whatever <code>T::T(T&&)</code> throws.
1545 Whatever <code>T::operator = (T&&)</code> throws.
1546 \par Exception Safety
1547 Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything.
1548 \par Iterator Invalidation
1549 Does not invalidate any iterators with the exception of iterators pointing to the overwritten element.
1551 Constant (in the size of the <code>circular_buffer</code>).
1552 \sa <code>\link push_back() push_back(const_reference)\endlink</code>,
1553 <code>pop_back()</code>, <code>pop_front()</code>
1555 void push_front(rvalue_type item) {
1556 push_front_impl<rvalue_type>(boost::move(item));
1559 //! Insert a new default-constructed element at the beginning of the <code>circular_buffer</code>.
1561 \post if <code>capacity() > 0</code> then <code>front() == item</code><br>
1562 If the <code>circular_buffer</code> is full, the last element will be removed. If the capacity is
1563 <code>0</code>, nothing will be inserted.
1564 \throws Whatever <code>T::T()</code> throws.
1565 Whatever <code>T::T(T&&)</code> throws.
1566 Whatever <code>T::operator = (T&&)</code> throws.
1567 \par Exception Safety
1568 Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything.
1569 \par Iterator Invalidation
1570 Does not invalidate any iterators with the exception of iterators pointing to the overwritten element.
1572 Constant (in the size of the <code>circular_buffer</code>).
1573 \sa <code>\link push_back() push_back(const_reference)\endlink</code>,
1574 <code>pop_back()</code>, <code>pop_front()</code>
1578 push_front(boost::move(temp));
1581 //! Remove the last element from the <code>circular_buffer</code>.
1583 \pre <code>!empty()</code>
1584 \post The last element is removed from the <code>circular_buffer</code>.
1586 \par Exception Safety
1588 \par Iterator Invalidation
1589 Invalidates only iterators pointing to the removed element.
1591 Constant (in the size of the <code>circular_buffer</code>).
1592 \sa <code>pop_front()</code>, <code>\link push_back() push_back(const_reference)\endlink</code>,
1593 <code>\link push_front() push_front(const_reference)\endlink</code>
1596 BOOST_CB_ASSERT(!empty()); // check for empty buffer (back element not available)
1598 destroy_item(m_last);
1602 //! Remove the first element from the <code>circular_buffer</code>.
1604 \pre <code>!empty()</code>
1605 \post The first element is removed from the <code>circular_buffer</code>.
1607 \par Exception Safety
1609 \par Iterator Invalidation
1610 Invalidates only iterators pointing to the removed element.
1612 Constant (in the size of the <code>circular_buffer</code>).
1613 \sa <code>pop_back()</code>, <code>\link push_back() push_back(const_reference)\endlink</code>,
1614 <code>\link push_front() push_front(const_reference)\endlink</code>
1617 BOOST_CB_ASSERT(!empty()); // check for empty buffer (front element not available)
1618 destroy_item(m_first);
1623 template <class ValT>
1624 iterator insert_impl(iterator pos, ValT item) {
1625 BOOST_CB_ASSERT(pos.is_valid(this)); // check for uninitialized or invalidated iterator
1626 iterator b = begin();
1627 if (full() && pos == b)
1629 return insert_item<ValT>(pos, static_cast<ValT>(item));
1635 //! Insert an element at the specified position.
1637 \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> or its end.
1638 \post The <code>item</code> will be inserted at the position <code>pos</code>.<br>
1639 If the <code>circular_buffer</code> is full, the first element will be overwritten. If the
1640 <code>circular_buffer</code> is full and the <code>pos</code> points to <code>begin()</code>, then the
1641 <code>item</code> will not be inserted. If the capacity is <code>0</code>, nothing will be inserted.
1642 \param pos An iterator specifying the position where the <code>item</code> will be inserted.
1643 \param item The element to be inserted.
1644 \return Iterator to the inserted element or <code>begin()</code> if the <code>item</code> is not inserted. (See
1646 \throws Whatever <code>T::T(const T&)</code> throws.
1647 Whatever <code>T::operator = (const T&)</code> throws.
1648 <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>.
1650 \par Exception Safety
1651 Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything.
1652 \par Iterator Invalidation
1653 Invalidates iterators pointing to the elements at the insertion point (including <code>pos</code>) and
1654 iterators behind the insertion point (towards the end; except iterators equal to <code>end()</code>). It
1655 also invalidates iterators pointing to the overwritten element.
1657 Linear (in <code>std::distance(pos, end())</code>).
1658 \sa <code>\link insert(iterator, size_type, param_value_type)
1659 insert(iterator, size_type, value_type)\endlink</code>,
1660 <code>insert(iterator, InputIterator, InputIterator)</code>,
1661 <code>\link rinsert(iterator, param_value_type) rinsert(iterator, value_type)\endlink</code>,
1662 <code>\link rinsert(iterator, size_type, param_value_type)
1663 rinsert(iterator, size_type, value_type)\endlink</code>,
1664 <code>rinsert(iterator, InputIterator, InputIterator)</code>
1666 iterator insert(iterator pos, param_value_type item) {
1667 return insert_impl<param_value_type>(pos, item);
1670 //! Insert an element at the specified position.
1672 \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> or its end.
1673 \post The <code>item</code> will be inserted at the position <code>pos</code>.<br>
1674 If the <code>circular_buffer</code> is full, the first element will be overwritten. If the
1675 <code>circular_buffer</code> is full and the <code>pos</code> points to <code>begin()</code>, then the
1676 <code>item</code> will not be inserted. If the capacity is <code>0</code>, nothing will be inserted.
1677 \param pos An iterator specifying the position where the <code>item</code> will be inserted.
1678 \param item The element to be inserted.
1679 \return Iterator to the inserted element or <code>begin()</code> if the <code>item</code> is not inserted. (See
1681 \throws Whatever <code>T::T(T&&)</code> throws.
1682 Whatever <code>T::operator = (T&&)</code> throws.
1683 <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>.
1684 \par Exception Safety
1685 Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything.
1686 \par Iterator Invalidation
1687 Invalidates iterators pointing to the elements at the insertion point (including <code>pos</code>) and
1688 iterators behind the insertion point (towards the end; except iterators equal to <code>end()</code>). It
1689 also invalidates iterators pointing to the overwritten element.
1691 Linear (in <code>std::distance(pos, end())</code>).
1692 \sa <code>\link insert(iterator, size_type, param_value_type)
1693 insert(iterator, size_type, value_type)\endlink</code>,
1694 <code>insert(iterator, InputIterator, InputIterator)</code>,
1695 <code>\link rinsert(iterator, param_value_type) rinsert(iterator, value_type)\endlink</code>,
1696 <code>\link rinsert(iterator, size_type, param_value_type)
1697 rinsert(iterator, size_type, value_type)\endlink</code>,
1698 <code>rinsert(iterator, InputIterator, InputIterator)</code>
1700 iterator insert(iterator pos, rvalue_type item) {
1701 return insert_impl<rvalue_type>(pos, boost::move(item));
1704 //! Insert a default-constructed element at the specified position.
1706 \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> or its end.
1707 \post The <code>item</code> will be inserted at the position <code>pos</code>.<br>
1708 If the <code>circular_buffer</code> is full, the first element will be overwritten. If the
1709 <code>circular_buffer</code> is full and the <code>pos</code> points to <code>begin()</code>, then the
1710 <code>item</code> will not be inserted. If the capacity is <code>0</code>, nothing will be inserted.
1711 \param pos An iterator specifying the position where the <code>item</code> will be inserted.
1712 \return Iterator to the inserted element or <code>begin()</code> if the <code>item</code> is not inserted. (See
1714 \throws Whatever <code>T::T()</code> throws.
1715 Whatever <code>T::T(T&&)</code> throws.
1716 Whatever <code>T::operator = (T&&)</code> throws.
1717 <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>.
1718 \par Exception Safety
1719 Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything.
1720 \par Iterator Invalidation
1721 Invalidates iterators pointing to the elements at the insertion point (including <code>pos</code>) and
1722 iterators behind the insertion point (towards the end; except iterators equal to <code>end()</code>). It
1723 also invalidates iterators pointing to the overwritten element.
1725 Linear (in <code>std::distance(pos, end())</code>).
1726 \sa <code>\link insert(iterator, size_type, param_value_type)
1727 insert(iterator, size_type, value_type)\endlink</code>,
1728 <code>insert(iterator, InputIterator, InputIterator)</code>,
1729 <code>\link rinsert(iterator, param_value_type) rinsert(iterator, value_type)\endlink</code>,
1730 <code>\link rinsert(iterator, size_type, param_value_type)
1731 rinsert(iterator, size_type, value_type)\endlink</code>,
1732 <code>rinsert(iterator, InputIterator, InputIterator)</code>
1734 iterator insert(iterator pos) {
1736 return insert(pos, boost::move(temp));
1739 //! Insert <code>n</code> copies of the <code>item</code> at the specified position.
1741 \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> or its end.
1742 \post The number of <code>min[n, (pos - begin()) + reserve()]</code> elements will be inserted at the position
1743 <code>pos</code>.<br>The number of <code>min[pos - begin(), max[0, n - reserve()]]</code> elements will
1744 be overwritten at the beginning of the <code>circular_buffer</code>.<br>(See <i>Example</i> for the
1746 \param pos An iterator specifying the position where the <code>item</code>s will be inserted.
1747 \param n The number of <code>item</code>s the to be inserted.
1748 \param item The element whose copies will be inserted.
1749 \throws Whatever <code>T::T(const T&)</code> throws.
1750 Whatever <code>T::operator = (const T&)</code> throws.
1751 <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>.
1752 \par Exception Safety
1753 Basic; no-throw if the operations in the <i>Throws</i> section do not throw anything.
1754 \par Iterator Invalidation
1755 Invalidates iterators pointing to the elements at the insertion point (including <code>pos</code>) and
1756 iterators behind the insertion point (towards the end; except iterators equal to <code>end()</code>). It
1757 also invalidates iterators pointing to the overwritten elements.
1759 Linear (in <code>min[capacity(), std::distance(pos, end()) + n]</code>).
1761 Consider a <code>circular_buffer</code> with the capacity of 6 and the size of 4. Its internal buffer may
1762 look like the one below.<br><br>
1763 <code>|1|2|3|4| | |</code><br>
1764 <code>p ___^</code><br><br>After inserting 5 elements at the position <code>p</code>:<br><br>
1765 <code>insert(p, (size_t)5, 0);</code><br><br>actually only 4 elements get inserted and elements
1766 <code>1</code> and <code>2</code> are overwritten. This is due to the fact the insert operation preserves
1767 the capacity. After insertion the internal buffer looks like this:<br><br><code>|0|0|0|0|3|4|</code><br>
1768 <br>For comparison if the capacity would not be preserved the internal buffer would then result in
1769 <code>|1|2|0|0|0|0|0|3|4|</code>.
1770 \sa <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>,
1771 <code>insert(iterator, InputIterator, InputIterator)</code>,
1772 <code>\link rinsert(iterator, param_value_type) rinsert(iterator, value_type)\endlink</code>,
1773 <code>\link rinsert(iterator, size_type, param_value_type)
1774 rinsert(iterator, size_type, value_type)\endlink</code>,
1775 <code>rinsert(iterator, InputIterator, InputIterator)</code>
1777 void insert(iterator pos, size_type n, param_value_type item) {
1778 BOOST_CB_ASSERT(pos.is_valid(this)); // check for uninitialized or invalidated iterator
1781 size_type copy = capacity() - (end() - pos);
1786 insert_n(pos, n, cb_details::item_wrapper<const_pointer, param_value_type>(item));
1789 //! Insert the range <code>[first, last)</code> at the specified position.
1791 \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> or its end.<br>
1792 Valid range <code>[first, last)</code> where <code>first</code> and <code>last</code> meet the
1793 requirements of an <a href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>.
1794 \post Elements from the range
1795 <code>[first + max[0, distance(first, last) - (pos - begin()) - reserve()], last)</code> will be
1796 inserted at the position <code>pos</code>.<br>The number of <code>min[pos - begin(), max[0,
1797 distance(first, last) - reserve()]]</code> elements will be overwritten at the beginning of the
1798 <code>circular_buffer</code>.<br>(See <i>Example</i> for the explanation.)
1799 \param pos An iterator specifying the position where the range will be inserted.
1800 \param first The beginning of the range to be inserted.
1801 \param last The end of the range to be inserted.
1802 \throws Whatever <code>T::T(const T&)</code> throws if the <code>InputIterator</code> is not a move iterator.
1803 Whatever <code>T::operator = (const T&)</code> throws if the <code>InputIterator</code> is not a move iterator.
1804 Whatever <code>T::T(T&&)</code> throws if the <code>InputIterator</code> is a move iterator.
1805 Whatever <code>T::operator = (T&&)</code> throws if the <code>InputIterator</code> is a move iterator.
1806 \par Exception Safety
1807 Basic; no-throw if the operations in the <i>Throws</i> section do not throw anything.
1808 \par Iterator Invalidation
1809 Invalidates iterators pointing to the elements at the insertion point (including <code>pos</code>) and
1810 iterators behind the insertion point (towards the end; except iterators equal to <code>end()</code>). It
1811 also invalidates iterators pointing to the overwritten elements.
1813 Linear (in <code>[std::distance(pos, end()) + std::distance(first, last)]</code>; in
1814 <code>min[capacity(), std::distance(pos, end()) + std::distance(first, last)]</code> if the
1815 <code>InputIterator</code> is a
1816 <a href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">RandomAccessIterator</a>).
1818 Consider a <code>circular_buffer</code> with the capacity of 6 and the size of 4. Its internal buffer may
1819 look like the one below.<br><br>
1820 <code>|1|2|3|4| | |</code><br>
1821 <code>p ___^</code><br><br>After inserting a range of elements at the position <code>p</code>:<br><br>
1822 <code>int array[] = { 5, 6, 7, 8, 9 };</code><br><code>insert(p, array, array + 5);</code><br><br>
1823 actually only elements <code>6</code>, <code>7</code>, <code>8</code> and <code>9</code> from the
1824 specified range get inserted and elements <code>1</code> and <code>2</code> are overwritten. This is due
1825 to the fact the insert operation preserves the capacity. After insertion the internal buffer looks like
1826 this:<br><br><code>|6|7|8|9|3|4|</code><br><br>For comparison if the capacity would not be preserved the
1827 internal buffer would then result in <code>|1|2|5|6|7|8|9|3|4|</code>.
1828 \sa <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>,
1829 <code>\link insert(iterator, size_type, param_value_type)
1830 insert(iterator, size_type, value_type)\endlink</code>, <code>\link rinsert(iterator, param_value_type)
1831 rinsert(iterator, value_type)\endlink</code>, <code>\link rinsert(iterator, size_type, param_value_type)
1832 rinsert(iterator, size_type, value_type)\endlink</code>,
1833 <code>rinsert(iterator, InputIterator, InputIterator)</code>
1835 template <class InputIterator>
1836 void insert(iterator pos, InputIterator first, InputIterator last) {
1837 BOOST_CB_ASSERT(pos.is_valid(this)); // check for uninitialized or invalidated iterator
1838 insert(pos, first, last, is_integral<InputIterator>());
1842 template <class ValT>
1843 iterator rinsert_impl(iterator pos, ValT item) {
1844 BOOST_CB_ASSERT(pos.is_valid(this)); // check for uninitialized or invalidated iterator
1845 if (full() && pos.m_it == 0)
1847 if (pos == begin()) {
1850 construct_or_replace(!full(), m_first, static_cast<ValT>(item));
1851 } BOOST_CATCH(...) {
1858 pointer src = m_first;
1859 pointer dest = m_first;
1861 pos.m_it = map_pointer(pos.m_it);
1862 bool construct = !full();
1864 while (src != pos.m_it) {
1865 construct_or_replace(construct, dest, boost::move_if_noexcept(*src));
1870 decrement(pos.m_it);
1871 replace(pos.m_it, static_cast<ValT>(item));
1872 } BOOST_CATCH(...) {
1873 if (!construct && !full()) {
1886 return iterator(this, pos.m_it);
1891 //! Insert an element before the specified position.
1893 \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> or its end.
1894 \post The <code>item</code> will be inserted before the position <code>pos</code>.<br>
1895 If the <code>circular_buffer</code> is full, the last element will be overwritten. If the
1896 <code>circular_buffer</code> is full and the <code>pos</code> points to <code>end()</code>, then the
1897 <code>item</code> will not be inserted. If the capacity is <code>0</code>, nothing will be inserted.
1898 \param pos An iterator specifying the position before which the <code>item</code> will be inserted.
1899 \param item The element to be inserted.
1900 \return Iterator to the inserted element or <code>end()</code> if the <code>item</code> is not inserted. (See
1902 \throws Whatever <code>T::T(const T&)</code> throws.
1903 Whatever <code>T::operator = (const T&)</code> throws.
1904 <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>.
1905 \par Exception Safety
1906 Basic; no-throw if the operations in the <i>Throws</i> section do not throw anything.
1907 \par Iterator Invalidation
1908 Invalidates iterators pointing to the elements before the insertion point (towards the beginning and
1909 excluding <code>pos</code>). It also invalidates iterators pointing to the overwritten element.
1911 Linear (in <code>std::distance(begin(), pos)</code>).
1912 \sa <code>\link rinsert(iterator, size_type, param_value_type)
1913 rinsert(iterator, size_type, value_type)\endlink</code>,
1914 <code>rinsert(iterator, InputIterator, InputIterator)</code>,
1915 <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>,
1916 <code>\link insert(iterator, size_type, param_value_type)
1917 insert(iterator, size_type, value_type)\endlink</code>,
1918 <code>insert(iterator, InputIterator, InputIterator)</code>
1920 iterator rinsert(iterator pos, param_value_type item) {
1921 return rinsert_impl<param_value_type>(pos, item);
1924 //! Insert an element before the specified position.
1926 \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> or its end.
1927 \post The <code>item</code> will be inserted before the position <code>pos</code>.<br>
1928 If the <code>circular_buffer</code> is full, the last element will be overwritten. If the
1929 <code>circular_buffer</code> is full and the <code>pos</code> points to <code>end()</code>, then the
1930 <code>item</code> will not be inserted. If the capacity is <code>0</code>, nothing will be inserted.
1931 \param pos An iterator specifying the position before which the <code>item</code> will be inserted.
1932 \param item The element to be inserted.
1933 \return Iterator to the inserted element or <code>end()</code> if the <code>item</code> is not inserted. (See
1935 \throws Whatever <code>T::T(T&&)</code> throws.
1936 Whatever <code>T::operator = (T&&)</code> throws.
1937 <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>.
1938 \par Exception Safety
1939 Basic; no-throw if the operations in the <i>Throws</i> section do not throw anything.
1940 \par Iterator Invalidation
1941 Invalidates iterators pointing to the elements before the insertion point (towards the beginning and
1942 excluding <code>pos</code>). It also invalidates iterators pointing to the overwritten element.
1944 Linear (in <code>std::distance(begin(), pos)</code>).
1945 \sa <code>\link rinsert(iterator, size_type, param_value_type)
1946 rinsert(iterator, size_type, value_type)\endlink</code>,
1947 <code>rinsert(iterator, InputIterator, InputIterator)</code>,
1948 <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>,
1949 <code>\link insert(iterator, size_type, param_value_type)
1950 insert(iterator, size_type, value_type)\endlink</code>,
1951 <code>insert(iterator, InputIterator, InputIterator)</code>
1953 iterator rinsert(iterator pos, rvalue_type item) {
1954 return rinsert_impl<rvalue_type>(pos, boost::move(item));
1957 //! Insert an element before the specified position.
1959 \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> or its end.
1960 \post The <code>item</code> will be inserted before the position <code>pos</code>.<br>
1961 If the <code>circular_buffer</code> is full, the last element will be overwritten. If the
1962 <code>circular_buffer</code> is full and the <code>pos</code> points to <code>end()</code>, then the
1963 <code>item</code> will not be inserted. If the capacity is <code>0</code>, nothing will be inserted.
1964 \param pos An iterator specifying the position before which the <code>item</code> will be inserted.
1965 \return Iterator to the inserted element or <code>end()</code> if the <code>item</code> is not inserted. (See
1967 \throws Whatever <code>T::T()</code> throws.
1968 Whatever <code>T::T(T&&)</code> throws.
1969 Whatever <code>T::operator = (T&&)</code> throws.
1970 <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>.
1971 \par Exception Safety
1972 Basic; no-throw if the operations in the <i>Throws</i> section do not throw anything.
1973 \par Iterator Invalidation
1974 Invalidates iterators pointing to the elements before the insertion point (towards the beginning and
1975 excluding <code>pos</code>). It also invalidates iterators pointing to the overwritten element.
1977 Linear (in <code>std::distance(begin(), pos)</code>).
1978 \sa <code>\link rinsert(iterator, size_type, param_value_type)
1979 rinsert(iterator, size_type, value_type)\endlink</code>,
1980 <code>rinsert(iterator, InputIterator, InputIterator)</code>,
1981 <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>,
1982 <code>\link insert(iterator, size_type, param_value_type)
1983 insert(iterator, size_type, value_type)\endlink</code>,
1984 <code>insert(iterator, InputIterator, InputIterator)</code>
1986 iterator rinsert(iterator pos) {
1988 return rinsert(pos, boost::move(temp));
1991 //! Insert <code>n</code> copies of the <code>item</code> before the specified position.
1993 \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> or its end.
1994 \post The number of <code>min[n, (end() - pos) + reserve()]</code> elements will be inserted before the
1995 position <code>pos</code>.<br>The number of <code>min[end() - pos, max[0, n - reserve()]]</code> elements
1996 will be overwritten at the end of the <code>circular_buffer</code>.<br>(See <i>Example</i> for the
1998 \param pos An iterator specifying the position where the <code>item</code>s will be inserted.
1999 \param n The number of <code>item</code>s the to be inserted.
2000 \param item The element whose copies will be inserted.
2001 \throws Whatever <code>T::T(const T&)</code> throws.
2002 Whatever <code>T::operator = (const T&)</code> throws.
2003 <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>.
2004 \par Exception Safety
2005 Basic; no-throw if the operations in the <i>Throws</i> section do not throw anything.
2006 \par Iterator Invalidation
2007 Invalidates iterators pointing to the elements before the insertion point (towards the beginning and
2008 excluding <code>pos</code>). It also invalidates iterators pointing to the overwritten elements.
2010 Linear (in <code>min[capacity(), std::distance(begin(), pos) + n]</code>).
2012 Consider a <code>circular_buffer</code> with the capacity of 6 and the size of 4. Its internal buffer may
2013 look like the one below.<br><br>
2014 <code>|1|2|3|4| | |</code><br>
2015 <code>p ___^</code><br><br>After inserting 5 elements before the position <code>p</code>:<br><br>
2016 <code>rinsert(p, (size_t)5, 0);</code><br><br>actually only 4 elements get inserted and elements
2017 <code>3</code> and <code>4</code> are overwritten. This is due to the fact the rinsert operation preserves
2018 the capacity. After insertion the internal buffer looks like this:<br><br><code>|1|2|0|0|0|0|</code><br>
2019 <br>For comparison if the capacity would not be preserved the internal buffer would then result in
2020 <code>|1|2|0|0|0|0|0|3|4|</code>.
2021 \sa <code>\link rinsert(iterator, param_value_type) rinsert(iterator, value_type)\endlink</code>,
2022 <code>rinsert(iterator, InputIterator, InputIterator)</code>,
2023 <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>,
2024 <code>\link insert(iterator, size_type, param_value_type)
2025 insert(iterator, size_type, value_type)\endlink</code>,
2026 <code>insert(iterator, InputIterator, InputIterator)</code>
2028 void rinsert(iterator pos, size_type n, param_value_type item) {
2029 BOOST_CB_ASSERT(pos.is_valid(this)); // check for uninitialized or invalidated iterator
2030 rinsert_n(pos, n, cb_details::item_wrapper<const_pointer, param_value_type>(item));
2033 //! Insert the range <code>[first, last)</code> before the specified position.
2035 \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> or its end.<br>
2036 Valid range <code>[first, last)</code> where <code>first</code> and <code>last</code> meet the
2037 requirements of an <a href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>.
2038 \post Elements from the range
2039 <code>[first, last - max[0, distance(first, last) - (end() - pos) - reserve()])</code> will be inserted
2040 before the position <code>pos</code>.<br>The number of <code>min[end() - pos, max[0,
2041 distance(first, last) - reserve()]]</code> elements will be overwritten at the end of the
2042 <code>circular_buffer</code>.<br>(See <i>Example</i> for the explanation.)
2043 \param pos An iterator specifying the position where the range will be inserted.
2044 \param first The beginning of the range to be inserted.
2045 \param last The end of the range to be inserted.
2046 \throws Whatever <code>T::T(const T&)</code> throws if the <code>InputIterator</code> is not a move iterator.
2047 Whatever <code>T::operator = (const T&)</code> throws if the <code>InputIterator</code> is not a move iterator.
2048 Whatever <code>T::T(T&&)</code> throws if the <code>InputIterator</code> is a move iterator.
2049 Whatever <code>T::operator = (T&&)</code> throws if the <code>InputIterator</code> is a move iterator.
2050 \par Exception Safety
2051 Basic; no-throw if the operations in the <i>Throws</i> section do not throw anything.
2052 \par Iterator Invalidation
2053 Invalidates iterators pointing to the elements before the insertion point (towards the beginning and
2054 excluding <code>pos</code>). It also invalidates iterators pointing to the overwritten elements.
2056 Linear (in <code>[std::distance(begin(), pos) + std::distance(first, last)]</code>; in
2057 <code>min[capacity(), std::distance(begin(), pos) + std::distance(first, last)]</code> if the
2058 <code>InputIterator</code> is a
2059 <a href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">RandomAccessIterator</a>).
2061 Consider a <code>circular_buffer</code> with the capacity of 6 and the size of 4. Its internal buffer may
2062 look like the one below.<br><br>
2063 <code>|1|2|3|4| | |</code><br>
2064 <code>p ___^</code><br><br>After inserting a range of elements before the position <code>p</code>:<br><br>
2065 <code>int array[] = { 5, 6, 7, 8, 9 };</code><br><code>insert(p, array, array + 5);</code><br><br>
2066 actually only elements <code>5</code>, <code>6</code>, <code>7</code> and <code>8</code> from the
2067 specified range get inserted and elements <code>3</code> and <code>4</code> are overwritten. This is due
2068 to the fact the rinsert operation preserves the capacity. After insertion the internal buffer looks like
2069 this:<br><br><code>|1|2|5|6|7|8|</code><br><br>For comparison if the capacity would not be preserved the
2070 internal buffer would then result in <code>|1|2|5|6|7|8|9|3|4|</code>.
2071 \sa <code>\link rinsert(iterator, param_value_type) rinsert(iterator, value_type)\endlink</code>,
2072 <code>\link rinsert(iterator, size_type, param_value_type)
2073 rinsert(iterator, size_type, value_type)\endlink</code>, <code>\link insert(iterator, param_value_type)
2074 insert(iterator, value_type)\endlink</code>, <code>\link insert(iterator, size_type, param_value_type)
2075 insert(iterator, size_type, value_type)\endlink</code>,
2076 <code>insert(iterator, InputIterator, InputIterator)</code>
2078 template <class InputIterator>
2079 void rinsert(iterator pos, InputIterator first, InputIterator last) {
2080 BOOST_CB_ASSERT(pos.is_valid(this)); // check for uninitialized or invalidated iterator
2081 rinsert(pos, first, last, is_integral<InputIterator>());
2086 //! Remove an element at the specified position.
2088 \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> (but not an
2089 <code>end()</code>).
2090 \post The element at the position <code>pos</code> is removed.
2091 \param pos An iterator pointing at the element to be removed.
2092 \return Iterator to the first element remaining beyond the removed element or <code>end()</code> if no such
2094 \throws <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>.
2095 \par Exception Safety
2096 Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything.
2097 \par Iterator Invalidation
2098 Invalidates iterators pointing to the erased element and iterators pointing to the elements behind
2099 the erased element (towards the end; except iterators equal to <code>end()</code>).
2101 Linear (in <code>std::distance(pos, end())</code>).
2102 \sa <code>erase(iterator, iterator)</code>, <code>rerase(iterator)</code>,
2103 <code>rerase(iterator, iterator)</code>, <code>erase_begin(size_type)</code>,
2104 <code>erase_end(size_type)</code>, <code>clear()</code>
2106 iterator erase(iterator pos) {
2107 BOOST_CB_ASSERT(pos.is_valid(this)); // check for uninitialized or invalidated iterator
2108 BOOST_CB_ASSERT(pos.m_it != 0); // check for iterator pointing to end()
2109 pointer next = pos.m_it;
2111 for (pointer p = pos.m_it; next != m_last; p = next, increment(next))
2112 replace(p, boost::move_if_noexcept(*next));
2114 destroy_item(m_last);
2116 #if BOOST_CB_ENABLE_DEBUG
2117 return m_last == pos.m_it ? end() : iterator(this, pos.m_it);
2119 return m_last == pos.m_it ? end() : pos;
2123 //! Erase the range <code>[first, last)</code>.
2125 \pre Valid range <code>[first, last)</code>.
2126 \post The elements from the range <code>[first, last)</code> are removed. (If <code>first == last</code>
2127 nothing is removed.)
2128 \param first The beginning of the range to be removed.
2129 \param last The end of the range to be removed.
2130 \return Iterator to the first element remaining beyond the removed elements or <code>end()</code> if no such
2132 \throws <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>.
2133 \par Exception Safety
2134 Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything.
2135 \par Iterator Invalidation
2136 Invalidates iterators pointing to the erased elements and iterators pointing to the elements behind
2137 the erased range (towards the end; except iterators equal to <code>end()</code>).
2139 Linear (in <code>std::distance(first, end())</code>).
2140 \sa <code>erase(iterator)</code>, <code>rerase(iterator)</code>, <code>rerase(iterator, iterator)</code>,
2141 <code>erase_begin(size_type)</code>, <code>erase_end(size_type)</code>, <code>clear()</code>
2143 iterator erase(iterator first, iterator last) {
2144 BOOST_CB_ASSERT(first.is_valid(this)); // check for uninitialized or invalidated iterator
2145 BOOST_CB_ASSERT(last.is_valid(this)); // check for uninitialized or invalidated iterator
2146 BOOST_CB_ASSERT(first <= last); // check for wrong range
2149 pointer p = first.m_it;
2150 while (last.m_it != 0)
2151 replace((first++).m_it, boost::move_if_noexcept(*last++));
2154 destroy_item(m_last);
2156 } while(m_last != first.m_it);
2157 return m_last == p ? end() : iterator(this, p);
2160 //! Remove an element at the specified position.
2162 \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> (but not an
2163 <code>end()</code>).
2164 \post The element at the position <code>pos</code> is removed.
2165 \param pos An iterator pointing at the element to be removed.
2166 \return Iterator to the first element remaining in front of the removed element or <code>begin()</code> if no
2167 such element exists.
2168 \throws <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>.
2169 \par Exception Safety
2170 Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything.
2171 \par Iterator Invalidation
2172 Invalidates iterators pointing to the erased element and iterators pointing to the elements in front of
2173 the erased element (towards the beginning).
2175 Linear (in <code>std::distance(begin(), pos)</code>).
2176 \note This method is symetric to the <code>erase(iterator)</code> method and is more effective than
2177 <code>erase(iterator)</code> if the iterator <code>pos</code> is close to the beginning of the
2178 <code>circular_buffer</code>. (See the <i>Complexity</i>.)
2179 \sa <code>erase(iterator)</code>, <code>erase(iterator, iterator)</code>,
2180 <code>rerase(iterator, iterator)</code>, <code>erase_begin(size_type)</code>,
2181 <code>erase_end(size_type)</code>, <code>clear()</code>
2183 iterator rerase(iterator pos) {
2184 BOOST_CB_ASSERT(pos.is_valid(this)); // check for uninitialized or invalidated iterator
2185 BOOST_CB_ASSERT(pos.m_it != 0); // check for iterator pointing to end()
2186 pointer prev = pos.m_it;
2188 for (decrement(prev); p != m_first; p = prev, decrement(prev))
2189 replace(p, boost::move_if_noexcept(*prev));
2190 destroy_item(m_first);
2193 #if BOOST_CB_ENABLE_DEBUG
2194 return p == pos.m_it ? begin() : iterator(this, pos.m_it);
2196 return p == pos.m_it ? begin() : pos;
2200 //! Erase the range <code>[first, last)</code>.
2202 \pre Valid range <code>[first, last)</code>.
2203 \post The elements from the range <code>[first, last)</code> are removed. (If <code>first == last</code>
2204 nothing is removed.)
2205 \param first The beginning of the range to be removed.
2206 \param last The end of the range to be removed.
2207 \return Iterator to the first element remaining in front of the removed elements or <code>begin()</code> if no
2208 such element exists.
2209 \throws <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>.
2210 \par Exception Safety
2211 Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything.
2212 \par Iterator Invalidation
2213 Invalidates iterators pointing to the erased elements and iterators pointing to the elements in front of
2214 the erased range (towards the beginning).
2216 Linear (in <code>std::distance(begin(), last)</code>).
2217 \note This method is symetric to the <code>erase(iterator, iterator)</code> method and is more effective than
2218 <code>erase(iterator, iterator)</code> if <code>std::distance(begin(), first)</code> is lower that
2219 <code>std::distance(last, end())</code>.
2220 \sa <code>erase(iterator)</code>, <code>erase(iterator, iterator)</code>, <code>rerase(iterator)</code>,
2221 <code>erase_begin(size_type)</code>, <code>erase_end(size_type)</code>, <code>clear()</code>
2223 iterator rerase(iterator first, iterator last) {
2224 BOOST_CB_ASSERT(first.is_valid(this)); // check for uninitialized or invalidated iterator
2225 BOOST_CB_ASSERT(last.is_valid(this)); // check for uninitialized or invalidated iterator
2226 BOOST_CB_ASSERT(first <= last); // check for wrong range
2229 pointer p = map_pointer(last.m_it);
2231 while (first.m_it != m_first) {
2232 decrement(first.m_it);
2234 replace(p, boost::move_if_noexcept(*first.m_it));
2237 destroy_item(m_first);
2240 } while(m_first != p);
2241 if (m_first == last.m_it)
2243 decrement(last.m_it);
2244 return iterator(this, last.m_it);
2247 //! Remove first <code>n</code> elements (with constant complexity for scalar types).
2249 \pre <code>n \<= size()</code>
2250 \post The <code>n</code> elements at the beginning of the <code>circular_buffer</code> will be removed.
2251 \param n The number of elements to be removed.
2252 \throws <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>.
2253 \par Exception Safety
2254 Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything. (I.e. no throw in
2256 \par Iterator Invalidation
2257 Invalidates iterators pointing to the first <code>n</code> erased elements.
2259 Constant (in <code>n</code>) for scalar types; linear for other types.
2260 \note This method has been specially designed for types which do not require an explicit destructruction (e.g.
2261 integer, float or a pointer). For these scalar types a call to a destructor is not required which makes
2262 it possible to implement the "erase from beginning" operation with a constant complexity. For non-sacalar
2263 types the complexity is linear (hence the explicit destruction is needed) and the implementation is
2264 actually equivalent to
2265 <code>\link circular_buffer::rerase(iterator, iterator) rerase(begin(), begin() + n)\endlink</code>.
2266 \sa <code>erase(iterator)</code>, <code>erase(iterator, iterator)</code>,
2267 <code>rerase(iterator)</code>, <code>rerase(iterator, iterator)</code>,
2268 <code>erase_end(size_type)</code>, <code>clear()</code>
2270 void erase_begin(size_type n) {
2271 BOOST_CB_ASSERT(n <= size()); // check for n greater than size
2272 #if BOOST_CB_ENABLE_DEBUG
2273 erase_begin(n, false_type());
2275 erase_begin(n, is_scalar<value_type>());
2279 //! Remove last <code>n</code> elements (with constant complexity for scalar types).
2281 \pre <code>n \<= size()</code>
2282 \post The <code>n</code> elements at the end of the <code>circular_buffer</code> will be removed.
2283 \param n The number of elements to be removed.
2284 \throws <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>.
2285 \par Exception Safety
2286 Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything. (I.e. no throw in
2288 \par Iterator Invalidation
2289 Invalidates iterators pointing to the last <code>n</code> erased elements.
2291 Constant (in <code>n</code>) for scalar types; linear for other types.
2292 \note This method has been specially designed for types which do not require an explicit destructruction (e.g.
2293 integer, float or a pointer). For these scalar types a call to a destructor is not required which makes
2294 it possible to implement the "erase from end" operation with a constant complexity. For non-sacalar
2295 types the complexity is linear (hence the explicit destruction is needed) and the implementation is
2296 actually equivalent to
2297 <code>\link circular_buffer::erase(iterator, iterator) erase(end() - n, end())\endlink</code>.
2298 \sa <code>erase(iterator)</code>, <code>erase(iterator, iterator)</code>,
2299 <code>rerase(iterator)</code>, <code>rerase(iterator, iterator)</code>,
2300 <code>erase_begin(size_type)</code>, <code>clear()</code>
2302 void erase_end(size_type n) {
2303 BOOST_CB_ASSERT(n <= size()); // check for n greater than size
2304 #if BOOST_CB_ENABLE_DEBUG
2305 erase_end(n, false_type());
2307 erase_end(n, is_scalar<value_type>());
2311 //! Remove all stored elements from the <code>circular_buffer</code>.
2313 \post <code>size() == 0</code>
2315 \par Exception Safety
2317 \par Iterator Invalidation
2318 Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to
2319 <code>end()</code>).
2321 Constant (in the size of the <code>circular_buffer</code>) for scalar types; linear for other types.
2322 \sa <code>~circular_buffer()</code>, <code>erase(iterator)</code>, <code>erase(iterator, iterator)</code>,
2323 <code>rerase(iterator)</code>, <code>rerase(iterator, iterator)</code>,
2324 <code>erase_begin(size_type)</code>, <code>erase_end(size_type)</code>
2326 void clear() BOOST_NOEXCEPT {
2334 //! Check if the <code>index</code> is valid.
2335 void check_position(size_type index) const {
2336 if (index >= size())
2337 throw_exception(std::out_of_range("circular_buffer"));
2340 //! Increment the pointer.
2341 template <class Pointer>
2342 void increment(Pointer& p) const {
2347 //! Decrement the pointer.
2348 template <class Pointer>
2349 void decrement(Pointer& p) const {
2355 //! Add <code>n</code> to the pointer.
2356 template <class Pointer>
2357 Pointer add(Pointer p, difference_type n) const {
2358 return p + (n < (m_end - p) ? n : n - capacity());
2361 //! Subtract <code>n</code> from the pointer.
2362 template <class Pointer>
2363 Pointer sub(Pointer p, difference_type n) const {
2364 return p - (n > (p - m_buff) ? n - capacity() : n);
2367 //! Map the null pointer to virtual end of circular buffer.
2368 pointer map_pointer(pointer p) const { return p == 0 ? m_last : p; }
2370 //! Allocate memory.
2371 pointer allocate(size_type n) {
2373 throw_exception(std::length_error("circular_buffer"));
2374 #if BOOST_CB_ENABLE_DEBUG
2375 pointer p = (n == 0) ? 0 : m_alloc.allocate(n);
2376 cb_details::do_fill_uninitialized_memory(p, sizeof(value_type) * n);
2379 return (n == 0) ? 0 : m_alloc.allocate(n);
2383 //! Deallocate memory.
2384 void deallocate(pointer p, size_type n) {
2386 m_alloc.deallocate(p, n);
2389 //! Does the pointer point to the uninitialized memory?
2390 bool is_uninitialized(const_pointer p) const BOOST_NOEXCEPT {
2391 return p >= m_last && (m_first < m_last || p < m_first);
2394 //! Replace an element.
2395 void replace(pointer pos, param_value_type item) {
2397 #if BOOST_CB_ENABLE_DEBUG
2398 invalidate_iterators(iterator(this, pos));
2402 //! Replace an element.
2403 void replace(pointer pos, rvalue_type item) {
2404 *pos = boost::move(item);
2405 #if BOOST_CB_ENABLE_DEBUG
2406 invalidate_iterators(iterator(this, pos));
2410 //! Construct or replace an element.
2412 <code>construct</code> has to be set to <code>true</code> if and only if
2413 <code>pos</code> points to an uninitialized memory.
2415 void construct_or_replace(bool construct, pointer pos, param_value_type item) {
2417 boost::container::allocator_traits<Alloc>::construct(m_alloc, boost::addressof(*pos), item);
2422 //! Construct or replace an element.
2424 <code>construct</code> has to be set to <code>true</code> if and only if
2425 <code>pos</code> points to an uninitialized memory.
2427 void construct_or_replace(bool construct, pointer pos, rvalue_type item) {
2429 boost::container::allocator_traits<Alloc>::construct(m_alloc, boost::addressof(*pos), boost::move(item));
2431 replace(pos, boost::move(item));
2434 //! Destroy an item.
2435 void destroy_item(pointer p) {
2436 boost::container::allocator_traits<Alloc>::destroy(m_alloc, boost::addressof(*p));
2437 #if BOOST_CB_ENABLE_DEBUG
2438 invalidate_iterators(iterator(this, p));
2439 cb_details::do_fill_uninitialized_memory(p, sizeof(value_type));
2443 //! Destroy an item only if it has been constructed.
2444 void destroy_if_constructed(pointer pos) {
2445 if (is_uninitialized(pos))
2449 //! Destroy the whole content of the circular buffer.
2450 void destroy_content() {
2451 #if BOOST_CB_ENABLE_DEBUG
2452 destroy_content(false_type());
2454 destroy_content(is_scalar<value_type>());
2458 //! Specialized destroy_content method.
2459 void destroy_content(const true_type&) {
2460 m_first = add(m_first, size());
2463 //! Specialized destroy_content method.
2464 void destroy_content(const false_type&) {
2465 for (size_type ii = 0; ii < size(); ++ii, increment(m_first))
2466 destroy_item(m_first);
2469 //! Destroy content and free allocated memory.
2470 void destroy() BOOST_NOEXCEPT {
2472 deallocate(m_buff, capacity());
2473 #if BOOST_CB_ENABLE_DEBUG
2481 //! Initialize the internal buffer.
2482 void initialize_buffer(capacity_type buffer_capacity) {
2483 m_buff = allocate(buffer_capacity);
2484 m_end = m_buff + buffer_capacity;
2487 //! Initialize the internal buffer.
2488 void initialize_buffer(capacity_type buffer_capacity, param_value_type item) {
2489 initialize_buffer(buffer_capacity);
2491 cb_details::uninitialized_fill_n_with_alloc(m_buff, size(), item, m_alloc);
2492 } BOOST_CATCH(...) {
2493 deallocate(m_buff, size());
2499 //! Specialized initialize method.
2500 template <class IntegralType>
2501 void initialize(IntegralType n, IntegralType item, const true_type&) {
2502 m_size = static_cast<size_type>(n);
2503 initialize_buffer(size(), item);
2504 m_first = m_last = m_buff;
2507 //! Specialized initialize method.
2508 template <class Iterator>
2509 void initialize(Iterator first, Iterator last, const false_type&) {
2510 BOOST_CB_IS_CONVERTIBLE(Iterator, value_type); // check for invalid iterator type
2511 #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x581))
2512 initialize(first, last, iterator_category<Iterator>::type());
2514 initialize(first, last, BOOST_DEDUCED_TYPENAME iterator_category<Iterator>::type());
2518 //! Specialized initialize method.
2519 template <class InputIterator>
2520 void initialize(InputIterator first, InputIterator last, const std::input_iterator_tag&) {
2521 BOOST_CB_ASSERT_TEMPLATED_ITERATOR_CONSTRUCTORS // check if the STL provides templated iterator constructors
2523 std::deque<value_type, allocator_type> tmp(first, last, m_alloc);
2524 size_type distance = tmp.size();
2525 initialize(distance, boost::make_move_iterator(tmp.begin()), boost::make_move_iterator(tmp.end()), distance);
2528 //! Specialized initialize method.
2529 template <class ForwardIterator>
2530 void initialize(ForwardIterator first, ForwardIterator last, const std::forward_iterator_tag&) {
2531 BOOST_CB_ASSERT(std::distance(first, last) >= 0); // check for wrong range
2532 size_type distance = std::distance(first, last);
2533 initialize(distance, first, last, distance);
2536 //! Specialized initialize method.
2537 template <class IntegralType>
2538 void initialize(capacity_type buffer_capacity, IntegralType n, IntegralType item, const true_type&) {
2539 BOOST_CB_ASSERT(buffer_capacity >= static_cast<size_type>(n)); // check for capacity lower than n
2540 m_size = static_cast<size_type>(n);
2541 initialize_buffer(buffer_capacity, item);
2543 m_last = buffer_capacity == size() ? m_buff : m_buff + size();
2546 //! Specialized initialize method.
2547 template <class Iterator>
2548 void initialize(capacity_type buffer_capacity, Iterator first, Iterator last, const false_type&) {
2549 BOOST_CB_IS_CONVERTIBLE(Iterator, value_type); // check for invalid iterator type
2550 #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x581))
2551 initialize(buffer_capacity, first, last, iterator_category<Iterator>::type());
2553 initialize(buffer_capacity, first, last, BOOST_DEDUCED_TYPENAME iterator_category<Iterator>::type());
2557 //! Specialized initialize method.
2558 template <class InputIterator>
2559 void initialize(capacity_type buffer_capacity,
2560 InputIterator first,
2562 const std::input_iterator_tag&) {
2563 initialize_buffer(buffer_capacity);
2564 m_first = m_last = m_buff;
2566 if (buffer_capacity == 0)
2568 while (first != last && !full()) {
2569 boost::container::allocator_traits<Alloc>::construct(m_alloc, boost::addressof(*m_last), *first++);
2573 while (first != last) {
2574 replace(m_last, *first++);
2580 //! Specialized initialize method.
2581 template <class ForwardIterator>
2582 void initialize(capacity_type buffer_capacity,
2583 ForwardIterator first,
2584 ForwardIterator last,
2585 const std::forward_iterator_tag&) {
2586 BOOST_CB_ASSERT(std::distance(first, last) >= 0); // check for wrong range
2587 initialize(buffer_capacity, first, last, std::distance(first, last));
2590 //! Initialize the circular buffer.
2591 template <class ForwardIterator>
2592 void initialize(capacity_type buffer_capacity,
2593 ForwardIterator first,
2594 ForwardIterator last,
2595 size_type distance) {
2596 initialize_buffer(buffer_capacity);
2598 if (distance > buffer_capacity) {
2599 std::advance(first, distance - buffer_capacity);
2600 m_size = buffer_capacity;
2605 m_last = cb_details::uninitialized_copy(first, last, m_buff, m_alloc);
2606 } BOOST_CATCH(...) {
2607 deallocate(m_buff, buffer_capacity);
2611 if (m_last == m_end)
2615 //! Reset the circular buffer.
2616 void reset(pointer buff, pointer last, capacity_type new_capacity) {
2618 m_size = last - buff;
2619 m_first = m_buff = buff;
2620 m_end = m_buff + new_capacity;
2621 m_last = last == m_end ? m_buff : last;
2624 //! Specialized method for swapping the allocator.
2625 void swap_allocator(circular_buffer<T, Alloc>&, const true_type&) {
2626 // Swap is not needed because allocators have no state.
2629 //! Specialized method for swapping the allocator.
2630 void swap_allocator(circular_buffer<T, Alloc>& cb, const false_type&) {
2631 adl_move_swap(m_alloc, cb.m_alloc);
2634 //! Specialized assign method.
2635 template <class IntegralType>
2636 void assign(IntegralType n, IntegralType item, const true_type&) {
2637 assign(static_cast<size_type>(n), static_cast<value_type>(item));
2640 //! Specialized assign method.
2641 template <class Iterator>
2642 void assign(Iterator first, Iterator last, const false_type&) {
2643 BOOST_CB_IS_CONVERTIBLE(Iterator, value_type); // check for invalid iterator type
2644 #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x581))
2645 assign(first, last, iterator_category<Iterator>::type());
2647 assign(first, last, BOOST_DEDUCED_TYPENAME iterator_category<Iterator>::type());
2651 //! Specialized assign method.
2652 template <class InputIterator>
2653 void assign(InputIterator first, InputIterator last, const std::input_iterator_tag&) {
2654 BOOST_CB_ASSERT_TEMPLATED_ITERATOR_CONSTRUCTORS // check if the STL provides templated iterator constructors
2656 std::deque<value_type, allocator_type> tmp(first, last, m_alloc);
2657 size_type distance = tmp.size();
2658 assign_n(distance, distance,
2659 cb_details::make_assign_range
2660 (boost::make_move_iterator(tmp.begin()), boost::make_move_iterator(tmp.end()), m_alloc));
2663 //! Specialized assign method.
2664 template <class ForwardIterator>
2665 void assign(ForwardIterator first, ForwardIterator last, const std::forward_iterator_tag&) {
2666 BOOST_CB_ASSERT(std::distance(first, last) >= 0); // check for wrong range
2667 size_type distance = std::distance(first, last);
2668 assign_n(distance, distance, cb_details::make_assign_range(first, last, m_alloc));
2671 //! Specialized assign method.
2672 template <class IntegralType>
2673 void assign(capacity_type new_capacity, IntegralType n, IntegralType item, const true_type&) {
2674 assign(new_capacity, static_cast<size_type>(n), static_cast<value_type>(item));
2677 //! Specialized assign method.
2678 template <class Iterator>
2679 void assign(capacity_type new_capacity, Iterator first, Iterator last, const false_type&) {
2680 BOOST_CB_IS_CONVERTIBLE(Iterator, value_type); // check for invalid iterator type
2681 #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x581))
2682 assign(new_capacity, first, last, iterator_category<Iterator>::type());
2684 assign(new_capacity, first, last, BOOST_DEDUCED_TYPENAME iterator_category<Iterator>::type());
2688 //! Specialized assign method.
2689 template <class InputIterator>
2690 void assign(capacity_type new_capacity, InputIterator first, InputIterator last, const std::input_iterator_tag&) {
2691 if (new_capacity == capacity()) {
2693 insert(begin(), first, last);
2695 circular_buffer<value_type, allocator_type> tmp(new_capacity, first, last, m_alloc);
2700 //! Specialized assign method.
2701 template <class ForwardIterator>
2702 void assign(capacity_type new_capacity, ForwardIterator first, ForwardIterator last,
2703 const std::forward_iterator_tag&) {
2704 BOOST_CB_ASSERT(std::distance(first, last) >= 0); // check for wrong range
2705 size_type distance = std::distance(first, last);
2706 if (distance > new_capacity) {
2707 std::advance(first, distance - new_capacity);
2708 distance = new_capacity;
2710 assign_n(new_capacity, distance,
2711 cb_details::make_assign_range(first, last, m_alloc));
2714 //! Helper assign method.
2715 template <class Functor>
2716 void assign_n(capacity_type new_capacity, size_type n, const Functor& fnc) {
2717 if (new_capacity == capacity()) {
2721 } BOOST_CATCH(...) {
2727 pointer buff = allocate(new_capacity);
2730 } BOOST_CATCH(...) {
2731 deallocate(buff, new_capacity);
2737 m_end = m_buff + new_capacity;
2741 m_last = add(m_buff, size());
2744 //! Helper insert method.
2745 template <class ValT>
2746 iterator insert_item(const iterator& pos, ValT item) {
2747 pointer p = pos.m_it;
2749 construct_or_replace(!full(), m_last, static_cast<ValT>(item));
2752 pointer src = m_last;
2753 pointer dest = m_last;
2754 bool construct = !full();
2758 construct_or_replace(construct, dest, boost::move_if_noexcept(*src));
2762 replace(p, static_cast<ValT>(item));
2763 } BOOST_CATCH(...) {
2764 if (!construct && !full()) {
2777 return iterator(this, p);
2780 //! Specialized insert method.
2781 template <class IntegralType>
2782 void insert(const iterator& pos, IntegralType n, IntegralType item, const true_type&) {
2783 insert(pos, static_cast<size_type>(n), static_cast<value_type>(item));
2786 //! Specialized insert method.
2787 template <class Iterator>
2788 void insert(const iterator& pos, Iterator first, Iterator last, const false_type&) {
2789 BOOST_CB_IS_CONVERTIBLE(Iterator, value_type); // check for invalid iterator type
2790 #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x581))
2791 insert(pos, first, last, iterator_category<Iterator>::type());
2793 insert(pos, first, last, BOOST_DEDUCED_TYPENAME iterator_category<Iterator>::type());
2797 //! Specialized insert method.
2798 template <class InputIterator>
2799 void insert(iterator pos, InputIterator first, InputIterator last, const std::input_iterator_tag&) {
2800 if (!full() || pos != begin()) {
2801 for (;first != last; ++pos)
2802 pos = insert(pos, *first++);
2806 //! Specialized insert method.
2807 template <class ForwardIterator>
2808 void insert(const iterator& pos, ForwardIterator first, ForwardIterator last, const std::forward_iterator_tag&) {
2809 BOOST_CB_ASSERT(std::distance(first, last) >= 0); // check for wrong range
2810 size_type n = std::distance(first, last);
2813 size_type copy = capacity() - (end() - pos);
2817 std::advance(first, n - copy);
2820 insert_n(pos, n, cb_details::iterator_wrapper<ForwardIterator>(first));
2823 //! Helper insert method.
2824 template <class Wrapper>
2825 void insert_n(const iterator& pos, size_type n, const Wrapper& wrapper) {
2826 size_type construct = reserve();
2829 if (pos.m_it == 0) {
2833 for (; ii < construct; ++ii, increment(p))
2834 boost::container::allocator_traits<Alloc>::construct(m_alloc, boost::addressof(*p), *wrapper());
2835 for (;ii < n; ++ii, increment(p))
2836 replace(p, *wrapper());
2837 } BOOST_CATCH(...) {
2838 size_type constructed = (std::min)(ii, construct);
2839 m_last = add(m_last, constructed);
2840 m_size += constructed;
2845 pointer src = m_last;
2846 pointer dest = add(m_last, n - 1);
2847 pointer p = pos.m_it;
2850 while (src != pos.m_it) {
2852 construct_or_replace(is_uninitialized(dest), dest, *src);
2855 for (; ii < n; ++ii, increment(p))
2856 construct_or_replace(is_uninitialized(p), p, *wrapper());
2857 } BOOST_CATCH(...) {
2858 for (p = add(m_last, n - 1); p != dest; decrement(p))
2859 destroy_if_constructed(p);
2860 for (n = 0, p = pos.m_it; n < ii; ++n, increment(p))
2861 destroy_if_constructed(p);
2866 m_last = add(m_last, n);
2867 m_first = add(m_first, n - construct);
2868 m_size += construct;
2871 //! Specialized rinsert method.
2872 template <class IntegralType>
2873 void rinsert(const iterator& pos, IntegralType n, IntegralType item, const true_type&) {
2874 rinsert(pos, static_cast<size_type>(n), static_cast<value_type>(item));
2877 //! Specialized rinsert method.
2878 template <class Iterator>
2879 void rinsert(const iterator& pos, Iterator first, Iterator last, const false_type&) {
2880 BOOST_CB_IS_CONVERTIBLE(Iterator, value_type); // check for invalid iterator type
2881 #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x581))
2882 rinsert(pos, first, last, iterator_category<Iterator>::type());
2884 rinsert(pos, first, last, BOOST_DEDUCED_TYPENAME iterator_category<Iterator>::type());
2888 //! Specialized insert method.
2889 template <class InputIterator>
2890 void rinsert(iterator pos, InputIterator first, InputIterator last, const std::input_iterator_tag&) {
2891 if (!full() || pos.m_it != 0) {
2892 for (;first != last; ++pos) {
2893 pos = rinsert(pos, *first++);
2900 //! Specialized rinsert method.
2901 template <class ForwardIterator>
2902 void rinsert(const iterator& pos, ForwardIterator first, ForwardIterator last, const std::forward_iterator_tag&) {
2903 BOOST_CB_ASSERT(std::distance(first, last) >= 0); // check for wrong range
2904 rinsert_n(pos, std::distance(first, last), cb_details::iterator_wrapper<ForwardIterator>(first));
2907 //! Helper rinsert method.
2908 template <class Wrapper>
2909 void rinsert_n(const iterator& pos, size_type n, const Wrapper& wrapper) {
2912 iterator b = begin();
2913 size_type copy = capacity() - (pos - b);
2918 size_type construct = reserve();
2922 pointer p = sub(m_first, n);
2925 for (;ii > construct; --ii, increment(p))
2926 replace(p, *wrapper());
2927 for (; ii > 0; --ii, increment(p))
2928 boost::container::allocator_traits<Alloc>::construct(m_alloc, boost::addressof(*p), *wrapper());
2929 } BOOST_CATCH(...) {
2930 size_type constructed = ii < construct ? construct - ii : 0;
2931 m_last = add(m_last, constructed);
2932 m_size += constructed;
2937 pointer src = m_first;
2938 pointer dest = sub(m_first, n);
2939 pointer p = map_pointer(pos.m_it);
2942 construct_or_replace(is_uninitialized(dest), dest, *src);
2946 for (size_type ii = 0; ii < n; ++ii, increment(dest))
2947 construct_or_replace(is_uninitialized(dest), dest, *wrapper());
2948 } BOOST_CATCH(...) {
2949 for (src = sub(m_first, n); src != dest; increment(src))
2950 destroy_if_constructed(src);
2955 m_first = sub(m_first, n);
2956 m_last = sub(m_last, n - construct);
2957 m_size += construct;
2960 //! Specialized erase_begin method.
2961 void erase_begin(size_type n, const true_type&) {
2962 m_first = add(m_first, n);
2966 //! Specialized erase_begin method.
2967 void erase_begin(size_type n, const false_type&) {
2968 iterator b = begin();
2972 //! Specialized erase_end method.
2973 void erase_end(size_type n, const true_type&) {
2974 m_last = sub(m_last, n);
2978 //! Specialized erase_end method.
2979 void erase_end(size_type n, const false_type&) {
2985 // Non-member functions
2987 //! Compare two <code>circular_buffer</code>s element-by-element to determine if they are equal.
2989 \param lhs The <code>circular_buffer</code> to compare.
2990 \param rhs The <code>circular_buffer</code> to compare.
2991 \return <code>lhs.\link circular_buffer::size() size()\endlink == rhs.\link circular_buffer::size() size()\endlink
2992 && <a href="http://www.sgi.com/tech/stl/equal.html">std::equal</a>(lhs.\link circular_buffer::begin()
2993 begin()\endlink, lhs.\link circular_buffer::end() end()\endlink,
2994 rhs.\link circular_buffer::begin() begin()\endlink)</code>
2997 Linear (in the size of the <code>circular_buffer</code>s).
2998 \par Iterator Invalidation
2999 Does not invalidate any iterators.
3001 template <class T, class Alloc>
3002 inline bool operator == (const circular_buffer<T, Alloc>& lhs, const circular_buffer<T, Alloc>& rhs) {
3003 return lhs.size() == rhs.size() && std::equal(lhs.begin(), lhs.end(), rhs.begin());
3007 \brief Compare two <code>circular_buffer</code>s element-by-element to determine if the left one is lesser than the
3009 \param lhs The <code>circular_buffer</code> to compare.
3010 \param rhs The <code>circular_buffer</code> to compare.
3011 \return <code><a href="http://www.sgi.com/tech/stl/lexicographical_compare.html">
3012 std::lexicographical_compare</a>(lhs.\link circular_buffer::begin() begin()\endlink,
3013 lhs.\link circular_buffer::end() end()\endlink, rhs.\link circular_buffer::begin() begin()\endlink,
3014 rhs.\link circular_buffer::end() end()\endlink)</code>
3017 Linear (in the size of the <code>circular_buffer</code>s).
3018 \par Iterator Invalidation
3019 Does not invalidate any iterators.
3021 template <class T, class Alloc>
3022 inline bool operator < (const circular_buffer<T, Alloc>& lhs, const circular_buffer<T, Alloc>& rhs) {
3023 return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
3026 #if !defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING) || defined(BOOST_MSVC)
3028 //! Compare two <code>circular_buffer</code>s element-by-element to determine if they are non-equal.
3030 \param lhs The <code>circular_buffer</code> to compare.
3031 \param rhs The <code>circular_buffer</code> to compare.
3032 \return <code>!(lhs == rhs)</code>
3035 Linear (in the size of the <code>circular_buffer</code>s).
3036 \par Iterator Invalidation
3037 Does not invalidate any iterators.
3038 \sa <code>operator==(const circular_buffer<T,Alloc>&, const circular_buffer<T,Alloc>&)</code>
3040 template <class T, class Alloc>
3041 inline bool operator != (const circular_buffer<T, Alloc>& lhs, const circular_buffer<T, Alloc>& rhs) {
3042 return !(lhs == rhs);
3046 \brief Compare two <code>circular_buffer</code>s element-by-element to determine if the left one is greater than
3048 \param lhs The <code>circular_buffer</code> to compare.
3049 \param rhs The <code>circular_buffer</code> to compare.
3050 \return <code>rhs \< lhs</code>
3053 Linear (in the size of the <code>circular_buffer</code>s).
3054 \par Iterator Invalidation
3055 Does not invalidate any iterators.
3056 \sa <code>operator<(const circular_buffer<T,Alloc>&, const circular_buffer<T,Alloc>&)</code>
3058 template <class T, class Alloc>
3059 inline bool operator > (const circular_buffer<T, Alloc>& lhs, const circular_buffer<T, Alloc>& rhs) {
3064 \brief Compare two <code>circular_buffer</code>s element-by-element to determine if the left one is lesser or equal
3066 \param lhs The <code>circular_buffer</code> to compare.
3067 \param rhs The <code>circular_buffer</code> to compare.
3068 \return <code>!(rhs \< lhs)</code>
3071 Linear (in the size of the <code>circular_buffer</code>s).
3072 \par Iterator Invalidation
3073 Does not invalidate any iterators.
3074 \sa <code>operator<(const circular_buffer<T,Alloc>&, const circular_buffer<T,Alloc>&)</code>
3076 template <class T, class Alloc>
3077 inline bool operator <= (const circular_buffer<T, Alloc>& lhs, const circular_buffer<T, Alloc>& rhs) {
3078 return !(rhs < lhs);
3082 \brief Compare two <code>circular_buffer</code>s element-by-element to determine if the left one is greater or
3083 equal to the right one.
3084 \param lhs The <code>circular_buffer</code> to compare.
3085 \param rhs The <code>circular_buffer</code> to compare.
3086 \return <code>!(lhs < rhs)</code>
3089 Linear (in the size of the <code>circular_buffer</code>s).
3090 \par Iterator Invalidation
3091 Does not invalidate any iterators.
3092 \sa <code>operator<(const circular_buffer<T,Alloc>&, const circular_buffer<T,Alloc>&)</code>
3094 template <class T, class Alloc>
3095 inline bool operator >= (const circular_buffer<T, Alloc>& lhs, const circular_buffer<T, Alloc>& rhs) {
3096 return !(lhs < rhs);
3099 //! Swap the contents of two <code>circular_buffer</code>s.
3101 \post <code>lhs</code> contains elements of <code>rhs</code> and vice versa.
3102 \param lhs The <code>circular_buffer</code> whose content will be swapped with <code>rhs</code>.
3103 \param rhs The <code>circular_buffer</code> whose content will be swapped with <code>lhs</code>.
3106 Constant (in the size of the <code>circular_buffer</code>s).
3107 \par Iterator Invalidation
3108 Invalidates all iterators of both <code>circular_buffer</code>s. (On the other hand the iterators still
3109 point to the same elements but within another container. If you want to rely on this feature you have to
3110 turn the <a href="#debug">Debug Support</a> off otherwise an assertion will report an error if such
3111 invalidated iterator is used.)
3112 \sa <code>\link circular_buffer::swap(circular_buffer<T, Alloc>&) swap(circular_buffer<T, Alloc>&)\endlink</code>
3114 template <class T, class Alloc>
3115 inline void swap(circular_buffer<T, Alloc>& lhs, circular_buffer<T, Alloc>& rhs) BOOST_NOEXCEPT {
3119 #endif // #if !defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING) || defined(BOOST_MSVC)
3121 } // namespace boost
3123 #endif // #if !defined(BOOST_CIRCULAR_BUFFER_BASE_HPP)