1// Implementation of the base circular buffer.
2
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.
7
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)
11
12#if !defined(BOOST_CIRCULAR_BUFFER_BASE_HPP)
13#define BOOST_CIRCULAR_BUFFER_BASE_HPP
14
15#if defined(_MSC_VER)
16 #pragma once
17#endif
18
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/move.hpp>
34#include <boost/utility/addressof.hpp>
35#include <algorithm>
36#include <utility>
37#include <deque>
38#include <stdexcept>
39
40#if BOOST_WORKAROUND(__MWERKS__, BOOST_TESTED_AT(0x3205))
41 #include <stddef.h>
42#endif
43
44namespace boost {
45
46/*!
47 \class circular_buffer
48 \brief Circular buffer - a STL compliant container.
49 \tparam T The type of the elements stored in the <code>circular_buffer</code>.
50 \par Type Requirements T
51 The <code>T</code> has to be <a href="http://www.sgi.com/tech/stl/Assignable.html">
52 SGIAssignable</a> (SGI STL defined combination of <a href="../../../utility/Assignable.html">
53 Assignable</a> and <a href="../../../utility/CopyConstructible.html">CopyConstructible</a>).
54 Moreover <code>T</code> has to be <a href="http://www.sgi.com/tech/stl/DefaultConstructible.html">
55 DefaultConstructible</a> if supplied as a default parameter when invoking some of the
56 <code>circular_buffer</code>'s methods e.g.
57 <code>insert(iterator pos, const value_type& item = %value_type())</code>. And
58 <a href="http://www.sgi.com/tech/stl/EqualityComparable.html">EqualityComparable</a> and/or
59 <a href="../../../utility/LessThanComparable.html">LessThanComparable</a> if the <code>circular_buffer</code>
60 will be compared with another container.
61 \tparam Alloc The allocator type used for all internal memory management.
62 \par Type Requirements Alloc
63 The <code>Alloc</code> has to meet the allocator requirements imposed by STL.
64 \par Default Alloc
65 std::allocator<T>
66
67 For detailed documentation of the circular_buffer visit:
68 http://www.boost.org/libs/circular_buffer/doc/circular_buffer.html
69*/
70template <class T, class Alloc>
71class circular_buffer
72/*! \cond */
73#if BOOST_CB_ENABLE_DEBUG
74: public cb_details::debug_iterator_registry
75#endif
76/*! \endcond */
77{
78
79 // Requirements
80 //BOOST_CLASS_REQUIRE(T, boost, SGIAssignableConcept);
81
82
83 //BOOST_CONCEPT_ASSERT((Assignable<T>));
84 //BOOST_CONCEPT_ASSERT((CopyConstructible<T>));
85 //BOOST_CONCEPT_ASSERT((DefaultConstructible<T>));
86
87 // Required if the circular_buffer will be compared with anther container.
88 //BOOST_CONCEPT_ASSERT((EqualityComparable<T>));
89 //BOOST_CONCEPT_ASSERT((LessThanComparable<T>));
90
91public:
92// Basic types
93
94 //! The type of this <code>circular_buffer</code>.
95 typedef circular_buffer<T, Alloc> this_type;
96
97 //! The type of elements stored in the <code>circular_buffer</code>.
98 typedef typename boost::container::allocator_traits<Alloc>::value_type value_type;
99
100 //! A pointer to an element.
101 typedef typename boost::container::allocator_traits<Alloc>::pointer pointer;
102
103 //! A const pointer to the element.
104 typedef typename boost::container::allocator_traits<Alloc>::const_pointer const_pointer;
105
106 //! A reference to an element.
107 typedef typename boost::container::allocator_traits<Alloc>::reference reference;
108
109 //! A const reference to an element.
110 typedef typename boost::container::allocator_traits<Alloc>::const_reference const_reference;
111
112 //! The distance type.
113 /*!
114 (A signed integral type used to represent the distance between two iterators.)
115 */
116 typedef typename boost::container::allocator_traits<Alloc>::difference_type difference_type;
117
118 //! The size type.
119 /*!
120 (An unsigned integral type that can represent any non-negative value of the container's distance type.)
121 */
122 typedef typename boost::container::allocator_traits<Alloc>::size_type size_type;
123
124 //! The type of an allocator used in the <code>circular_buffer</code>.
125 typedef Alloc allocator_type;
126
127// Iterators
128
129 //! A const (random access) iterator used to iterate through the <code>circular_buffer</code>.
130 typedef cb_details::iterator< circular_buffer<T, Alloc>, cb_details::const_traits<boost::container::allocator_traits<Alloc> > > const_iterator;
131
132 //! A (random access) iterator used to iterate through the <code>circular_buffer</code>.
133 typedef cb_details::iterator< circular_buffer<T, Alloc>, cb_details::nonconst_traits<boost::container::allocator_traits<Alloc> > > iterator;
134
135 //! A const iterator used to iterate backwards through a <code>circular_buffer</code>.
136 typedef boost::reverse_iterator<const_iterator> const_reverse_iterator;
137
138 //! An iterator used to iterate backwards through a <code>circular_buffer</code>.
139 typedef boost::reverse_iterator<iterator> reverse_iterator;
140
141// Container specific types
142
143 //! An array range.
144 /*!
145 (A typedef for the <a href="http://www.sgi.com/tech/stl/pair.html"><code>std::pair</code></a> where
146 its first element is a pointer to a beginning of an array and its second element represents
147 a size of the array.)
148 */
149 typedef std::pair<pointer, size_type> array_range;
150
151 //! A range of a const array.
152 /*!
153 (A typedef for the <a href="http://www.sgi.com/tech/stl/pair.html"><code>std::pair</code></a> where
154 its first element is a pointer to a beginning of a const array and its second element represents
155 a size of the const array.)
156 */
157 typedef std::pair<const_pointer, size_type> const_array_range;
158
159 //! The capacity type.
160 /*!
161 (Same as <code>size_type</code> - defined for consistency with the __cbso class.
162
163 */
164 // <a href="space_optimized.html"><code>circular_buffer_space_optimized</code></a>.)
165
166 typedef size_type capacity_type;
167
168// Helper types
169
170 //! A type representing the "best" way to pass the value_type to a method.
171 typedef const value_type& param_value_type;
172
173 //! A type representing rvalue from param type.
174 //! On compilers without rvalue references support this type is the Boost.Moves type used for emulation.
175 typedef BOOST_RV_REF(value_type) rvalue_type;
176
177private:
178// Member variables
179
180 //! The internal buffer used for storing elements in the circular buffer.
181 pointer m_buff;
182
183 //! The internal buffer's end (end of the storage space).
184 pointer m_end;
185
186 //! The virtual beginning of the circular buffer.
187 pointer m_first;
188
189 //! The virtual end of the circular buffer (one behind the last element).
190 pointer m_last;
191
192 //! The number of items currently stored in the circular buffer.
193 size_type m_size;
194
195 //! The allocator.
196 allocator_type m_alloc;
197
198// Friends
199#if defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
200 friend iterator;
201 friend const_iterator;
202#else
203 template <class Buff, class Traits> friend struct cb_details::iterator;
204#endif
205
206public:
207// Allocator
208
209 //! Get the allocator.
210 /*!
211 \return The allocator.
212 \throws Nothing.
213 \par Exception Safety
214 No-throw.
215 \par Iterator Invalidation
216 Does not invalidate any iterators.
217 \par Complexity
218 Constant (in the size of the <code>circular_buffer</code>).
219 \sa <code>get_allocator()</code> for obtaining an allocator %reference.
220 */
221 allocator_type get_allocator() const BOOST_NOEXCEPT { return m_alloc; }
222
223 //! Get the allocator reference.
224 /*!
225 \return A reference to the allocator.
226 \throws Nothing.
227 \par Exception Safety
228 No-throw.
229 \par Iterator Invalidation
230 Does not invalidate any iterators.
231 \par Complexity
232 Constant (in the size of the <code>circular_buffer</code>).
233 \note This method was added in order to optimize obtaining of the allocator with a state,
234 although use of stateful allocators in STL is discouraged.
235 \sa <code>get_allocator() const</code>
236 */
237 allocator_type& get_allocator() BOOST_NOEXCEPT { return m_alloc; }
238
239// Element access
240
241 //! Get the iterator pointing to the beginning of the <code>circular_buffer</code>.
242 /*!
243 \return A random access iterator pointing to the first element of the <code>circular_buffer</code>. If the
244 <code>circular_buffer</code> is empty it returns an iterator equal to the one returned by
245 <code>end()</code>.
246 \throws Nothing.
247 \par Exception Safety
248 No-throw.
249 \par Iterator Invalidation
250 Does not invalidate any iterators.
251 \par Complexity
252 Constant (in the size of the <code>circular_buffer</code>).
253 \sa <code>end()</code>, <code>rbegin()</code>, <code>rend()</code>
254 */
255 iterator begin() BOOST_NOEXCEPT { return iterator(this, empty() ? 0 : m_first); }
256
257 //! Get the iterator pointing to the end of the <code>circular_buffer</code>.
258 /*!
259 \return A random access iterator pointing to the element "one behind" the last element of the <code>
260 circular_buffer</code>. If the <code>circular_buffer</code> is empty it returns an iterator equal to
261 the one returned by <code>begin()</code>.
262 \throws Nothing.
263 \par Exception Safety
264 No-throw.
265 \par Iterator Invalidation
266 Does not invalidate any iterators.
267 \par Complexity
268 Constant (in the size of the <code>circular_buffer</code>).
269 \sa <code>begin()</code>, <code>rbegin()</code>, <code>rend()</code>
270 */
271 iterator end() BOOST_NOEXCEPT { return iterator(this, 0); }
272
273 //! Get the const iterator pointing to the beginning of the <code>circular_buffer</code>.
274 /*!
275 \return A const random access iterator pointing to the first element of the <code>circular_buffer</code>. If
276 the <code>circular_buffer</code> is empty it returns an iterator equal to the one returned by
277 <code>end() const</code>.
278 \throws Nothing.
279 \par Exception Safety
280 No-throw.
281 \par Iterator Invalidation
282 Does not invalidate any iterators.
283 \par Complexity
284 Constant (in the size of the <code>circular_buffer</code>).
285 \sa <code>end() const</code>, <code>rbegin() const</code>, <code>rend() const</code>
286 */
287 const_iterator begin() const BOOST_NOEXCEPT { return const_iterator(this, empty() ? 0 : m_first); }
288
289 //! Get the const iterator pointing to the end of the <code>circular_buffer</code>.
290 /*!
291 \return A const random access iterator pointing to the element "one behind" the last element of the <code>
292 circular_buffer</code>. If the <code>circular_buffer</code> is empty it returns an iterator equal to
293 the one returned by <code>begin() const</code> const.
294 \throws Nothing.
295 \par Exception Safety
296 No-throw.
297 \par Iterator Invalidation
298 Does not invalidate any iterators.
299 \par Complexity
300 Constant (in the size of the <code>circular_buffer</code>).
301 \sa <code>begin() const</code>, <code>rbegin() const</code>, <code>rend() const</code>
302 */
303 const_iterator end() const BOOST_NOEXCEPT { return const_iterator(this, 0); }
304
305 //! Get the iterator pointing to the beginning of the "reversed" <code>circular_buffer</code>.
306 /*!
307 \return A reverse random access iterator pointing to the last element of the <code>circular_buffer</code>.
308 If the <code>circular_buffer</code> is empty it returns an iterator equal to the one returned by
309 <code>rend()</code>.
310 \throws Nothing.
311 \par Exception Safety
312 No-throw.
313 \par Iterator Invalidation
314 Does not invalidate any iterators.
315 \par Complexity
316 Constant (in the size of the <code>circular_buffer</code>).
317 \sa <code>rend()</code>, <code>begin()</code>, <code>end()</code>
318 */
319 reverse_iterator rbegin() BOOST_NOEXCEPT { return reverse_iterator(end()); }
320
321 //! Get the iterator pointing to the end of the "reversed" <code>circular_buffer</code>.
322 /*!
323 \return A reverse random access iterator pointing to the element "one before" the first element of the <code>
324 circular_buffer</code>. If the <code>circular_buffer</code> is empty it returns an iterator equal to
325 the one returned by <code>rbegin()</code>.
326 \throws Nothing.
327 \par Exception Safety
328 No-throw.
329 \par Iterator Invalidation
330 Does not invalidate any iterators.
331 \par Complexity
332 Constant (in the size of the <code>circular_buffer</code>).
333 \sa <code>rbegin()</code>, <code>begin()</code>, <code>end()</code>
334 */
335 reverse_iterator rend() BOOST_NOEXCEPT { return reverse_iterator(begin()); }
336
337 //! Get the const iterator pointing to the beginning of the "reversed" <code>circular_buffer</code>.
338 /*!
339 \return A const reverse random access iterator pointing to the last element of the
340 <code>circular_buffer</code>. If the <code>circular_buffer</code> is empty it returns an iterator equal
341 to the one returned by <code>rend() const</code>.
342 \throws Nothing.
343 \par Exception Safety
344 No-throw.
345 \par Iterator Invalidation
346 Does not invalidate any iterators.
347 \par Complexity
348 Constant (in the size of the <code>circular_buffer</code>).
349 \sa <code>rend() const</code>, <code>begin() const</code>, <code>end() const</code>
350 */
351 const_reverse_iterator rbegin() const BOOST_NOEXCEPT { return const_reverse_iterator(end()); }
352
353 //! Get the const iterator pointing to the end of the "reversed" <code>circular_buffer</code>.
354 /*!
355 \return A const reverse random access iterator pointing to the element "one before" the first element of the
356 <code>circular_buffer</code>. If the <code>circular_buffer</code> is empty it returns an iterator equal
357 to the one returned by <code>rbegin() const</code>.
358 \throws Nothing.
359 \par Exception Safety
360 No-throw.
361 \par Iterator Invalidation
362 Does not invalidate any iterators.
363 \par Complexity
364 Constant (in the size of the <code>circular_buffer</code>).
365 \sa <code>rbegin() const</code>, <code>begin() const</code>, <code>end() const</code>
366 */
367 const_reverse_iterator rend() const BOOST_NOEXCEPT { return const_reverse_iterator(begin()); }
368
369 //! Get the element at the <code>index</code> position.
370 /*!
371 \pre <code>0 \<= index \&\& index \< size()</code>
372 \param index The position of the element.
373 \return A reference to the element at the <code>index</code> position.
374 \throws Nothing.
375 \par Exception Safety
376 No-throw.
377 \par Iterator Invalidation
378 Does not invalidate any iterators.
379 \par Complexity
380 Constant (in the size of the <code>circular_buffer</code>).
381 \sa <code>at()</code>
382 */
383 reference operator [] (size_type index) {
384 BOOST_CB_ASSERT(index < size()); // check for invalid index
385 return *add(m_first, index);
386 }
387
388 //! Get the element at the <code>index</code> position.
389 /*!
390 \pre <code>0 \<= index \&\& index \< size()</code>
391 \param index The position of the element.
392 \return A const reference to the element at the <code>index</code> position.
393 \throws Nothing.
394 \par Exception Safety
395 No-throw.
396 \par Iterator Invalidation
397 Does not invalidate any iterators.
398 \par Complexity
399 Constant (in the size of the <code>circular_buffer</code>).
400 \sa <code>\link at(size_type)const at() const \endlink</code>
401 */
402 const_reference operator [] (size_type index) const {
403 BOOST_CB_ASSERT(index < size()); // check for invalid index
404 return *add(m_first, index);
405 }
406
407 //! Get the element at the <code>index</code> position.
408 /*!
409 \param index The position of the element.
410 \return A reference to the element at the <code>index</code> position.
411 \throws <code>std::out_of_range</code> when the <code>index</code> is invalid (when
412 <code>index >= size()</code>).
413 \par Exception Safety
414 Strong.
415 \par Iterator Invalidation
416 Does not invalidate any iterators.
417 \par Complexity
418 Constant (in the size of the <code>circular_buffer</code>).
419 \sa <code>\link operator[](size_type) operator[] \endlink</code>
420 */
421 reference at(size_type index) {
422 check_position(index);
423 return (*this)[index];
424 }
425
426 //! Get the element at the <code>index</code> position.
427 /*!
428 \param index The position of the element.
429 \return A const reference to the element at the <code>index</code> position.
430 \throws <code>std::out_of_range</code> when the <code>index</code> is invalid (when
431 <code>index >= size()</code>).
432 \par Exception Safety
433 Strong.
434 \par Iterator Invalidation
435 Does not invalidate any iterators.
436 \par Complexity
437 Constant (in the size of the <code>circular_buffer</code>).
438 \sa <code>\link operator[](size_type)const operator[] const \endlink</code>
439 */
440 const_reference at(size_type index) const {
441 check_position(index);
442 return (*this)[index];
443 }
444
445 //! Get the first element.
446 /*!
447 \pre <code>!empty()</code>
448 \return A reference to the first element of the <code>circular_buffer</code>.
449 \throws Nothing.
450 \par Exception Safety
451 No-throw.
452 \par Iterator Invalidation
453 Does not invalidate any iterators.
454 \par Complexity
455 Constant (in the size of the <code>circular_buffer</code>).
456 \sa <code>back()</code>
457 */
458 reference front() {
459 BOOST_CB_ASSERT(!empty()); // check for empty buffer (front element not available)
460 return *m_first;
461 }
462
463 //! Get the last element.
464 /*!
465 \pre <code>!empty()</code>
466 \return A reference to the last element of the <code>circular_buffer</code>.
467 \throws Nothing.
468 \par Exception Safety
469 No-throw.
470 \par Iterator Invalidation
471 Does not invalidate any iterators.
472 \par Complexity
473 Constant (in the size of the <code>circular_buffer</code>).
474 \sa <code>front()</code>
475 */
476 reference back() {
477 BOOST_CB_ASSERT(!empty()); // check for empty buffer (back element not available)
478 return *((m_last == m_buff ? m_end : m_last) - 1);
479 }
480
481 //! Get the first element.
482 /*!
483 \pre <code>!empty()</code>
484 \return A const reference to the first element of the <code>circular_buffer</code>.
485 \throws Nothing.
486 \par Exception Safety
487 No-throw.
488 \par Iterator Invalidation
489 Does not invalidate any iterators.
490 \par Complexity
491 Constant (in the size of the <code>circular_buffer</code>).
492 \sa <code>back() const</code>
493 */
494 const_reference front() const {
495 BOOST_CB_ASSERT(!empty()); // check for empty buffer (front element not available)
496 return *m_first;
497 }
498
499 //! Get the last element.
500 /*!
501 \pre <code>!empty()</code>
502 \return A const reference to the last element of the <code>circular_buffer</code>.
503 \throws Nothing.
504 \par Exception Safety
505 No-throw.
506 \par Iterator Invalidation
507 Does not invalidate any iterators.
508 \par Complexity
509 Constant (in the size of the <code>circular_buffer</code>).
510 \sa <code>front() const</code>
511 */
512 const_reference back() const {
513 BOOST_CB_ASSERT(!empty()); // check for empty buffer (back element not available)
514 return *((m_last == m_buff ? m_end : m_last) - 1);
515 }
516
517 //! Get the first continuous array of the internal buffer.
518 /*!
519 This method in combination with <code>array_two()</code> can be useful when passing the stored data into
520 a legacy C API as an array. Suppose there is a <code>circular_buffer</code> of capacity 10, containing 7
521 characters <code>'a', 'b', ..., 'g'</code> where <code>buff[0] == 'a'</code>, <code>buff[1] == 'b'</code>,
522 ... and <code>buff[6] == 'g'</code>:<br><br>
523 <code>circular_buffer<char> buff(10);</code><br><br>
524 The internal representation is often not linear and the state of the internal buffer may look like this:<br>
525 <br><code>
526 |e|f|g| | | |a|b|c|d|<br>
527 end ___^<br>
528 begin _______^</code><br><br>
529
530 where <code>|a|b|c|d|</code> represents the "array one", <code>|e|f|g|</code> represents the "array two" and
531 <code>| | | |</code> is a free space.<br>
532 Now consider a typical C style function for writing data into a file:<br><br>
533 <code>int write(int file_desc, char* buff, int num_bytes);</code><br><br>
534 There are two ways how to write the content of the <code>circular_buffer</code> into a file. Either relying
535 on <code>array_one()</code> and <code>array_two()</code> methods and calling the write function twice:<br><br>
536 <code>array_range ar = buff.array_one();<br>
537 write(file_desc, ar.first, ar.second);<br>
538 ar = buff.array_two();<br>
539 write(file_desc, ar.first, ar.second);</code><br><br>
540 Or relying on the <code>linearize()</code> method:<br><br><code>
541 write(file_desc, buff.linearize(), buff.size());</code><br><br>
542 Since the complexity of <code>array_one()</code> and <code>array_two()</code> methods is constant the first
543 option is suitable when calling the write method is "cheap". On the other hand the second option is more
544 suitable when calling the write method is more "expensive" than calling the <code>linearize()</code> method
545 whose complexity is linear.
546 \return The array range of the first continuous array of the internal buffer. In the case the
547 <code>circular_buffer</code> is empty the size of the returned array is <code>0</code>.
548 \throws Nothing.
549 \par Exception Safety
550 No-throw.
551 \par Iterator Invalidation
552 Does not invalidate any iterators.
553 \par Complexity
554 Constant (in the size of the <code>circular_buffer</code>).
555 \warning In general invoking any method which modifies the internal state of the circular_buffer may
556 delinearize the internal buffer and invalidate the array ranges returned by <code>array_one()</code>
557 and <code>array_two()</code> (and their const versions).
558 \note In the case the internal buffer is linear e.g. <code>|a|b|c|d|e|f|g| | | |</code> the "array one" is
559 represented by <code>|a|b|c|d|e|f|g|</code> and the "array two" does not exist (the
560 <code>array_two()</code> method returns an array with the size <code>0</code>).
561 \sa <code>array_two()</code>, <code>linearize()</code>
562 */
563 array_range array_one() {
564 return array_range(m_first, (m_last <= m_first && !empty() ? m_end : m_last) - m_first);
565 }
566
567 //! Get the second continuous array of the internal buffer.
568 /*!
569 This method in combination with <code>array_one()</code> can be useful when passing the stored data into
570 a legacy C API as an array.
571 \return The array range of the second continuous array of the internal buffer. In the case the internal buffer
572 is linear or the <code>circular_buffer</code> is empty the size of the returned array is
573 <code>0</code>.
574 \throws Nothing.
575 \par Exception Safety
576 No-throw.
577 \par Iterator Invalidation
578 Does not invalidate any iterators.
579 \par Complexity
580 Constant (in the size of the <code>circular_buffer</code>).
581 \sa <code>array_one()</code>
582 */
583 array_range array_two() {
584 return array_range(m_buff, m_last <= m_first && !empty() ? m_last - m_buff : 0);
585 }
586
587 //! Get the first continuous array of the internal buffer.
588 /*!
589 This method in combination with <code>array_two() const</code> can be useful when passing the stored data into
590 a legacy C API as an array.
591 \return The array range of the first continuous array of the internal buffer. In the case the
592 <code>circular_buffer</code> is empty the size of the returned array is <code>0</code>.
593 \throws Nothing.
594 \par Exception Safety
595 No-throw.
596 \par Iterator Invalidation
597 Does not invalidate any iterators.
598 \par Complexity
599 Constant (in the size of the <code>circular_buffer</code>).
600 \sa <code>array_two() const</code>; <code>array_one()</code> for more details how to pass data into a legacy C
601 API.
602 */
603 const_array_range array_one() const {
604 return const_array_range(m_first, (m_last <= m_first && !empty() ? m_end : m_last) - m_first);
605 }
606
607 //! Get the second continuous array of the internal buffer.
608 /*!
609 This method in combination with <code>array_one() const</code> can be useful when passing the stored data into
610 a legacy C API as an array.
611 \return The array range of the second continuous array of the internal buffer. In the case the internal buffer
612 is linear or the <code>circular_buffer</code> is empty the size of the returned array is
613 <code>0</code>.
614 \throws Nothing.
615 \par Exception Safety
616 No-throw.
617 \par Iterator Invalidation
618 Does not invalidate any iterators.
619 \par Complexity
620 Constant (in the size of the <code>circular_buffer</code>).
621 \sa <code>array_one() const</code>
622 */
623 const_array_range array_two() const {
624 return const_array_range(m_buff, m_last <= m_first && !empty() ? m_last - m_buff : 0);
625 }
626
627 //! Linearize the internal buffer into a continuous array.
628 /*!
629 This method can be useful when passing the stored data into a legacy C API as an array.
630 \post <code>\&(*this)[0] \< \&(*this)[1] \< ... \< \&(*this)[size() - 1]</code>
631 \return A pointer to the beginning of the array or <code>0</code> if empty.
632 \throws <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>.
633 \par Exception Safety
634 Basic; no-throw if the operations in the <i>Throws</i> section do not throw anything.
635 \par Iterator Invalidation
636 Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to
637 <code>end()</code>); does not invalidate any iterators if the postcondition (the <i>Effect</i>) is already
638 met prior calling this method.
639 \par Complexity
640 Linear (in the size of the <code>circular_buffer</code>); constant if the postcondition (the
641 <i>Effect</i>) is already met.
642 \warning In general invoking any method which modifies the internal state of the <code>circular_buffer</code>
643 may delinearize the internal buffer and invalidate the returned pointer.
644 \sa <code>array_one()</code> and <code>array_two()</code> for the other option how to pass data into a legacy
645 C API; <code>is_linearized()</code>, <code>rotate(const_iterator)</code>
646 */
647 pointer linearize() {
648 if (empty())
649 return 0;
650 if (m_first < m_last || m_last == m_buff)
651 return m_first;
652 pointer src = m_first;
653 pointer dest = m_buff;
654 size_type moved = 0;
655 size_type constructed = 0;
656 BOOST_TRY {
657 for (pointer first = m_first; dest < src; src = first) {
658 for (size_type ii = 0; src < m_end; ++src, ++dest, ++moved, ++ii) {
659 if (moved == size()) {
660 first = dest;
661 break;
662 }
663 if (dest == first) {
664 first += ii;
665 break;
666 }
667 if (is_uninitialized(p: dest)) {
668 boost::container::allocator_traits<Alloc>::construct(m_alloc, boost::addressof(*dest), boost::move_if_noexcept(*src));
669 ++constructed;
670 } else {
671 value_type tmp = boost::move_if_noexcept(*src);
672 replace(src, boost::move_if_noexcept(*dest));
673 replace(dest, boost::move(tmp));
674 }
675 }
676 }
677 } BOOST_CATCH(...) {
678 m_last += constructed;
679 m_size += constructed;
680 BOOST_RETHROW
681 }
682 BOOST_CATCH_END
683 for (src = m_end - constructed; src < m_end; ++src)
684 destroy_item(p: src);
685 m_first = m_buff;
686 m_last = add(m_buff, size());
687#if BOOST_CB_ENABLE_DEBUG
688 invalidate_iterators_except(end());
689#endif
690 return m_buff;
691 }
692
693 //! Is the <code>circular_buffer</code> linearized?
694 /*!
695 \return <code>true</code> if the internal buffer is linearized into a continuous array (i.e. the
696 <code>circular_buffer</code> meets a condition
697 <code>\&(*this)[0] \< \&(*this)[1] \< ... \< \&(*this)[size() - 1]</code>);
698 <code>false</code> otherwise.
699 \throws Nothing.
700 \par Exception Safety
701 No-throw.
702 \par Iterator Invalidation
703 Does not invalidate any iterators.
704 \par Complexity
705 Constant (in the size of the <code>circular_buffer</code>).
706 \sa <code>linearize()</code>, <code>array_one()</code>, <code>array_two()</code>
707 */
708 bool is_linearized() const BOOST_NOEXCEPT { return m_first < m_last || m_last == m_buff; }
709
710 //! Rotate elements in the <code>circular_buffer</code>.
711 /*!
712 A more effective implementation of
713 <code><a href="http://www.sgi.com/tech/stl/rotate.html">std::rotate</a></code>.
714 \pre <code>new_begin</code> is a valid iterator pointing to the <code>circular_buffer</code> <b>except</b> its
715 end.
716 \post Before calling the method suppose:<br><br>
717 <code>m == std::distance(new_begin, end())</code><br><code>n == std::distance(begin(), new_begin)</code>
718 <br><code>val_0 == *new_begin, val_1 == *(new_begin + 1), ... val_m == *(new_begin + m)</code><br>
719 <code>val_r1 == *(new_begin - 1), val_r2 == *(new_begin - 2), ... val_rn == *(new_begin - n)</code><br>
720 <br>then after call to the method:<br><br>
721 <code>val_0 == (*this)[0] \&\& val_1 == (*this)[1] \&\& ... \&\& val_m == (*this)[m - 1] \&\& val_r1 ==
722 (*this)[m + n - 1] \&\& val_r2 == (*this)[m + n - 2] \&\& ... \&\& val_rn == (*this)[m]</code>
723 \param new_begin The new beginning.
724 \throws See <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>.
725 \par Exception Safety
726 Basic; no-throw if the <code>circular_buffer</code> is full or <code>new_begin</code> points to
727 <code>begin()</code> or if the operations in the <i>Throws</i> section do not throw anything.
728 \par Iterator Invalidation
729 If <code>m \< n</code> invalidates iterators pointing to the last <code>m</code> elements
730 (<b>including</b> <code>new_begin</code>, but not iterators equal to <code>end()</code>) else invalidates
731 iterators pointing to the first <code>n</code> elements; does not invalidate any iterators if the
732 <code>circular_buffer</code> is full.
733 \par Complexity
734 Linear (in <code>(std::min)(m, n)</code>); constant if the <code>circular_buffer</code> is full.
735 \sa <code><a href="http://www.sgi.com/tech/stl/rotate.html">std::rotate</a></code>
736 */
737 void rotate(const_iterator new_begin) {
738 BOOST_CB_ASSERT(new_begin.is_valid(this)); // check for uninitialized or invalidated iterator
739 BOOST_CB_ASSERT(new_begin.m_it != 0); // check for iterator pointing to end()
740 if (full()) {
741 m_first = m_last = const_cast<pointer>(new_begin.m_it);
742 } else {
743 difference_type m = end() - new_begin;
744 difference_type n = new_begin - begin();
745 if (m < n) {
746 for (; m > 0; --m) {
747 push_front(boost::move_if_noexcept(back()));
748 pop_back();
749 }
750 } else {
751 for (; n > 0; --n) {
752 push_back(boost::move_if_noexcept(front()));
753 pop_front();
754 }
755 }
756 }
757 }
758
759// Size and capacity
760
761 //! Get the number of elements currently stored in the <code>circular_buffer</code>.
762 /*!
763 \return The number of elements stored in the <code>circular_buffer</code>.
764 \throws Nothing.
765 \par Exception Safety
766 No-throw.
767 \par Iterator Invalidation
768 Does not invalidate any iterators.
769 \par Complexity
770 Constant (in the size of the <code>circular_buffer</code>).
771 \sa <code>capacity()</code>, <code>max_size()</code>, <code>reserve()</code>,
772 <code>\link resize() resize(size_type, const_reference)\endlink</code>
773 */
774 size_type size() const BOOST_NOEXCEPT { return m_size; }
775
776 /*! \brief Get the largest possible size or capacity of the <code>circular_buffer</code>. (It depends on
777 allocator's %max_size()).
778 \return The maximum size/capacity the <code>circular_buffer</code> can be set to.
779 \throws Nothing.
780 \par Exception Safety
781 No-throw.
782 \par Iterator Invalidation
783 Does not invalidate any iterators.
784 \par Complexity
785 Constant (in the size of the <code>circular_buffer</code>).
786 \sa <code>size()</code>, <code>capacity()</code>, <code>reserve()</code>
787 */
788 size_type max_size() const BOOST_NOEXCEPT {
789 return (std::min<size_type>)(boost::container::allocator_traits<Alloc>::max_size(m_alloc), (std::numeric_limits<difference_type>::max)());
790 }
791
792 //! Is the <code>circular_buffer</code> empty?
793 /*!
794 \return <code>true</code> if there are no elements stored in the <code>circular_buffer</code>;
795 <code>false</code> otherwise.
796 \throws Nothing.
797 \par Exception Safety
798 No-throw.
799 \par Iterator Invalidation
800 Does not invalidate any iterators.
801 \par Complexity
802 Constant (in the size of the <code>circular_buffer</code>).
803 \sa <code>full()</code>
804 */
805 bool empty() const BOOST_NOEXCEPT { return size() == 0; }
806
807 //! Is the <code>circular_buffer</code> full?
808 /*!
809 \return <code>true</code> if the number of elements stored in the <code>circular_buffer</code>
810 equals the capacity of the <code>circular_buffer</code>; <code>false</code> otherwise.
811 \throws Nothing.
812 \par Exception Safety
813 No-throw.
814 \par Iterator Invalidation
815 Does not invalidate any iterators.
816 \par Complexity
817 Constant (in the size of the <code>circular_buffer</code>).
818 \sa <code>empty()</code>
819 */
820 bool full() const BOOST_NOEXCEPT { return capacity() == size(); }
821
822 /*! \brief Get the maximum number of elements which can be inserted into the <code>circular_buffer</code> without
823 overwriting any of already stored elements.
824 \return <code>capacity() - size()</code>
825 \throws Nothing.
826 \par Exception Safety
827 No-throw.
828 \par Iterator Invalidation
829 Does not invalidate any iterators.
830 \par Complexity
831 Constant (in the size of the <code>circular_buffer</code>).
832 \sa <code>capacity()</code>, <code>size()</code>, <code>max_size()</code>
833 */
834 size_type reserve() const BOOST_NOEXCEPT { return capacity() - size(); }
835
836 //! Get the capacity of the <code>circular_buffer</code>.
837 /*!
838 \return The maximum number of elements which can be stored in the <code>circular_buffer</code>.
839 \throws Nothing.
840 \par Exception Safety
841 No-throw.
842 \par Iterator Invalidation
843 Does not invalidate any iterators.
844 \par Complexity
845 Constant (in the size of the <code>circular_buffer</code>).
846 \sa <code>reserve()</code>, <code>size()</code>, <code>max_size()</code>,
847 <code>set_capacity(capacity_type)</code>
848 */
849 capacity_type capacity() const BOOST_NOEXCEPT { return m_end - m_buff; }
850
851 //! Change the capacity of the <code>circular_buffer</code>.
852 /*!
853 \pre If <code>T</code> is a move only type, then compiler shall support <code>noexcept</code> modifiers
854 and move constructor of <code>T</code> must be marked with it (must not throw exceptions).
855 \post <code>capacity() == new_capacity \&\& size() \<= new_capacity</code><br><br>
856 If the current number of elements stored in the <code>circular_buffer</code> is greater than the desired
857 new capacity then number of <code>[size() - new_capacity]</code> <b>last</b> elements will be removed and
858 the new size will be equal to <code>new_capacity</code>.
859 \param new_capacity The new capacity.
860 \throws "An allocation error" if memory is exhausted, (<code>std::bad_alloc</code> if the standard allocator is
861 used).
862 Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept.
863 \par Exception Safety
864 Strong.
865 \par Iterator Invalidation
866 Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to
867 <code>end()</code>) if the new capacity is different from the original.
868 \par Complexity
869 Linear (in <code>min[size(), new_capacity]</code>).
870 \sa <code>rset_capacity(capacity_type)</code>,
871 <code>\link resize() resize(size_type, const_reference)\endlink</code>
872 */
873 void set_capacity(capacity_type new_capacity) {
874 if (new_capacity == capacity())
875 return;
876 pointer buff = allocate(n: new_capacity);
877 iterator b = begin();
878 BOOST_TRY {
879 reset(buff,
880 last: cb_details::uninitialized_move_if_noexcept(b, b + (std::min)(new_capacity, size()), buff, m_alloc),
881 new_capacity);
882 } BOOST_CATCH(...) {
883 deallocate(p: buff, n: new_capacity);
884 BOOST_RETHROW
885 }
886 BOOST_CATCH_END
887 }
888
889 //! Change the size of the <code>circular_buffer</code>.
890 /*!
891 \post <code>size() == new_size \&\& capacity() >= new_size</code><br><br>
892 If the new size is greater than the current size, copies of <code>item</code> will be inserted at the
893 <b>back</b> of the of the <code>circular_buffer</code> in order to achieve the desired size. In the case
894 the resulting size exceeds the current capacity the capacity will be set to <code>new_size</code>.<br>
895 If the current number of elements stored in the <code>circular_buffer</code> is greater than the desired
896 new size then number of <code>[size() - new_size]</code> <b>last</b> elements will be removed. (The
897 capacity will remain unchanged.)
898 \param new_size The new size.
899 \param item The element the <code>circular_buffer</code> will be filled with in order to gain the requested
900 size. (See the <i>Effect</i>.)
901 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
902 used).
903 Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept.
904 \par Exception Safety
905 Basic.
906 \par Iterator Invalidation
907 Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to
908 <code>end()</code>) if the new size is greater than the current capacity. Invalidates iterators pointing
909 to the removed elements if the new size is lower that the original size. Otherwise it does not invalidate
910 any iterator.
911 \par Complexity
912 Linear (in the new size of the <code>circular_buffer</code>).
913 \sa <code>\link rresize() rresize(size_type, const_reference)\endlink</code>,
914 <code>set_capacity(capacity_type)</code>
915 */
916 void resize(size_type new_size, param_value_type item = value_type()) {
917 if (new_size > size()) {
918 if (new_size > capacity())
919 set_capacity(new_size);
920 insert(end(), new_size - size(), item);
921 } else {
922 iterator e = end();
923 erase(e - (size() - new_size), e);
924 }
925 }
926
927 //! Change the capacity of the <code>circular_buffer</code>.
928 /*!
929 \pre If <code>T</code> is a move only type, then compiler shall support <code>noexcept</code> modifiers
930 and move constructor of <code>T</code> must be marked with it (must not throw exceptions).
931 \post <code>capacity() == new_capacity \&\& size() \<= new_capacity</code><br><br>
932 If the current number of elements stored in the <code>circular_buffer</code> is greater than the desired
933 new capacity then number of <code>[size() - new_capacity]</code> <b>first</b> elements will be removed
934 and the new size will be equal to <code>new_capacity</code>.
935 \param new_capacity The new capacity.
936 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
937 used).
938 Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept.
939 \par Exception Safety
940 Strong.
941 \par Iterator Invalidation
942 Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to
943 <code>end()</code>) if the new capacity is different from the original.
944 \par Complexity
945 Linear (in <code>min[size(), new_capacity]</code>).
946 \sa <code>set_capacity(capacity_type)</code>,
947 <code>\link rresize() rresize(size_type, const_reference)\endlink</code>
948 */
949 void rset_capacity(capacity_type new_capacity) {
950 if (new_capacity == capacity())
951 return;
952 pointer buff = allocate(n: new_capacity);
953 iterator e = end();
954 BOOST_TRY {
955 reset(buff, last: cb_details::uninitialized_move_if_noexcept(e - (std::min)(new_capacity, size()),
956 e, buff, m_alloc), new_capacity);
957 } BOOST_CATCH(...) {
958 deallocate(p: buff, n: new_capacity);
959 BOOST_RETHROW
960 }
961 BOOST_CATCH_END
962 }
963
964 //! Change the size of the <code>circular_buffer</code>.
965 /*!
966 \post <code>size() == new_size \&\& capacity() >= new_size</code><br><br>
967 If the new size is greater than the current size, copies of <code>item</code> will be inserted at the
968 <b>front</b> of the of the <code>circular_buffer</code> in order to achieve the desired size. In the case
969 the resulting size exceeds the current capacity the capacity will be set to <code>new_size</code>.<br>
970 If the current number of elements stored in the <code>circular_buffer</code> is greater than the desired
971 new size then number of <code>[size() - new_size]</code> <b>first</b> elements will be removed. (The
972 capacity will remain unchanged.)
973 \param new_size The new size.
974 \param item The element the <code>circular_buffer</code> will be filled with in order to gain the requested
975 size. (See the <i>Effect</i>.)
976 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
977 used).
978 Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept.
979 \par Exception Safety
980 Basic.
981 \par Iterator Invalidation
982 Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to
983 <code>end()</code>) if the new size is greater than the current capacity. Invalidates iterators pointing
984 to the removed elements if the new size is lower that the original size. Otherwise it does not invalidate
985 any iterator.
986 \par Complexity
987 Linear (in the new size of the <code>circular_buffer</code>).
988 \sa <code>\link resize() resize(size_type, const_reference)\endlink</code>,
989 <code>rset_capacity(capacity_type)</code>
990 */
991 void rresize(size_type new_size, param_value_type item = value_type()) {
992 if (new_size > size()) {
993 if (new_size > capacity())
994 set_capacity(new_size);
995 rinsert(begin(), new_size - size(), item);
996 } else {
997 rerase(begin(), end() - new_size);
998 }
999 }
1000
1001// Construction/Destruction
1002
1003 //! Create an empty <code>circular_buffer</code> with zero capacity.
1004 /*!
1005 \post <code>capacity() == 0 \&\& size() == 0</code>
1006 \param alloc The allocator.
1007 \throws Nothing.
1008 \par Complexity
1009 Constant.
1010 \warning Since Boost version 1.36 the behaviour of this constructor has changed. Now the constructor does not
1011 allocate any memory and both capacity and size are set to zero. Also note when inserting an element
1012 into a <code>circular_buffer</code> with zero capacity (e.g. by
1013 <code>\link push_back() push_back(const_reference)\endlink</code> or
1014 <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>) nothing
1015 will be inserted and the size (as well as capacity) remains zero.
1016 \note You can explicitly set the capacity by calling the <code>set_capacity(capacity_type)</code> method or you
1017 can use the other constructor with the capacity specified.
1018 \sa <code>circular_buffer(capacity_type, const allocator_type& alloc)</code>,
1019 <code>set_capacity(capacity_type)</code>
1020 */
1021 explicit circular_buffer(const allocator_type& alloc = allocator_type()) BOOST_NOEXCEPT
1022 : m_buff(0), m_end(0), m_first(0), m_last(0), m_size(0), m_alloc(alloc) {}
1023
1024 //! Create an empty <code>circular_buffer</code> with the specified capacity.
1025 /*!
1026 \post <code>capacity() == buffer_capacity \&\& size() == 0</code>
1027 \param buffer_capacity The maximum number of elements which can be stored in the <code>circular_buffer</code>.
1028 \param alloc The allocator.
1029 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
1030 used).
1031 \par Complexity
1032 Constant.
1033 */
1034 explicit circular_buffer(capacity_type buffer_capacity, const allocator_type& alloc = allocator_type())
1035 : m_size(0), m_alloc(alloc) {
1036 initialize_buffer(buffer_capacity);
1037 m_first = m_last = m_buff;
1038 }
1039
1040 /*! \brief Create a full <code>circular_buffer</code> with the specified capacity and filled with <code>n</code>
1041 copies of <code>item</code>.
1042 \post <code>capacity() == n \&\& full() \&\& (*this)[0] == item \&\& (*this)[1] == item \&\& ... \&\&
1043 (*this)[n - 1] == item </code>
1044 \param n The number of elements the created <code>circular_buffer</code> will be filled with.
1045 \param item The element the created <code>circular_buffer</code> will be filled with.
1046 \param alloc The allocator.
1047 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
1048 used).
1049 Whatever <code>T::T(const T&)</code> throws.
1050 \par Complexity
1051 Linear (in the <code>n</code>).
1052 */
1053 circular_buffer(size_type n, param_value_type item, const allocator_type& alloc = allocator_type())
1054 : m_size(n), m_alloc(alloc) {
1055 initialize_buffer(n, item);
1056 m_first = m_last = m_buff;
1057 }
1058
1059 /*! \brief Create a <code>circular_buffer</code> with the specified capacity and filled with <code>n</code>
1060 copies of <code>item</code>.
1061 \pre <code>buffer_capacity >= n</code>
1062 \post <code>capacity() == buffer_capacity \&\& size() == n \&\& (*this)[0] == item \&\& (*this)[1] == item
1063 \&\& ... \&\& (*this)[n - 1] == item</code>
1064 \param buffer_capacity The capacity of the created <code>circular_buffer</code>.
1065 \param n The number of elements the created <code>circular_buffer</code> will be filled with.
1066 \param item The element the created <code>circular_buffer</code> will be filled with.
1067 \param alloc The allocator.
1068 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
1069 used).
1070 Whatever <code>T::T(const T&)</code> throws.
1071 \par Complexity
1072 Linear (in the <code>n</code>).
1073 */
1074 circular_buffer(capacity_type buffer_capacity, size_type n, param_value_type item,
1075 const allocator_type& alloc = allocator_type())
1076 : m_size(n), m_alloc(alloc) {
1077 BOOST_CB_ASSERT(buffer_capacity >= size()); // check for capacity lower than size
1078 initialize_buffer(buffer_capacity, item);
1079 m_first = m_buff;
1080 m_last = buffer_capacity == n ? m_buff : m_buff + n;
1081 }
1082
1083 //! The copy constructor.
1084 /*!
1085 Creates a copy of the specified <code>circular_buffer</code>.
1086 \post <code>*this == cb</code>
1087 \param cb The <code>circular_buffer</code> to be copied.
1088 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
1089 used).
1090 Whatever <code>T::T(const T&)</code> throws.
1091 \par Complexity
1092 Linear (in the size of <code>cb</code>).
1093 */
1094 circular_buffer(const circular_buffer<T, Alloc>& cb)
1095 :
1096#if BOOST_CB_ENABLE_DEBUG
1097 debug_iterator_registry(),
1098#endif
1099 m_size(cb.size()), m_alloc(cb.get_allocator()) {
1100 initialize_buffer(cb.capacity());
1101 m_first = m_buff;
1102 BOOST_TRY {
1103 m_last = cb_details::uninitialized_copy(cb.begin(), cb.end(), m_buff, m_alloc);
1104 } BOOST_CATCH(...) {
1105 deallocate(p: m_buff, n: cb.capacity());
1106 BOOST_RETHROW
1107 }
1108 BOOST_CATCH_END
1109 if (m_last == m_end)
1110 m_last = m_buff;
1111 }
1112
1113#ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
1114 //! The move constructor.
1115 /*! \brief Move constructs a <code>circular_buffer</code> from <code>cb</code>, leaving <code>cb</code> empty.
1116 \pre C++ compiler with rvalue references support.
1117 \post <code>cb.empty()</code>
1118 \param cb <code>circular_buffer</code> to 'steal' value from.
1119 \throws Nothing.
1120 \par Constant.
1121 */
1122 circular_buffer(circular_buffer<T, Alloc>&& cb) BOOST_NOEXCEPT
1123 : m_buff(0), m_end(0), m_first(0), m_last(0), m_size(0), m_alloc(cb.get_allocator()) {
1124 cb.swap(*this);
1125 }
1126#endif // BOOST_NO_CXX11_RVALUE_REFERENCES
1127
1128 //! Create a full <code>circular_buffer</code> filled with a copy of the range.
1129 /*!
1130 \pre Valid range <code>[first, last)</code>.<br>
1131 <code>first</code> and <code>last</code> have to meet the requirements of
1132 <a href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>.
1133 \post <code>capacity() == std::distance(first, last) \&\& full() \&\& (*this)[0]== *first \&\&
1134 (*this)[1] == *(first + 1) \&\& ... \&\& (*this)[std::distance(first, last) - 1] == *(last - 1)</code>
1135 \param first The beginning of the range to be copied.
1136 \param last The end of the range to be copied.
1137 \param alloc The allocator.
1138 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
1139 used).
1140 Whatever <code>T::T(const T&)</code> throws.
1141 \par Complexity
1142 Linear (in the <code>std::distance(first, last)</code>).
1143 */
1144 template <class InputIterator>
1145 circular_buffer(InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type())
1146 : m_alloc(alloc) {
1147 initialize(first, last, is_integral<InputIterator>());
1148 }
1149
1150 //! Create a <code>circular_buffer</code> with the specified capacity and filled with a copy of the range.
1151 /*!
1152 \pre Valid range <code>[first, last)</code>.<br>
1153 <code>first</code> and <code>last</code> have to meet the requirements of
1154 <a href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>.
1155 \post <code>capacity() == buffer_capacity \&\& size() \<= std::distance(first, last) \&\&
1156 (*this)[0]== *(last - buffer_capacity) \&\& (*this)[1] == *(last - buffer_capacity + 1) \&\& ... \&\&
1157 (*this)[buffer_capacity - 1] == *(last - 1)</code><br><br>
1158 If the number of items to be copied from the range <code>[first, last)</code> is greater than the
1159 specified <code>buffer_capacity</code> then only elements from the range
1160 <code>[last - buffer_capacity, last)</code> will be copied.
1161 \param buffer_capacity The capacity of the created <code>circular_buffer</code>.
1162 \param first The beginning of the range to be copied.
1163 \param last The end of the range to be copied.
1164 \param alloc The allocator.
1165 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
1166 used).
1167 Whatever <code>T::T(const T&)</code> throws.
1168 \par Complexity
1169 Linear (in <code>std::distance(first, last)</code>; in
1170 <code>min[capacity, std::distance(first, last)]</code> if the <code>InputIterator</code> is a
1171 <a href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">RandomAccessIterator</a>).
1172 */
1173 template <class InputIterator>
1174 circular_buffer(capacity_type buffer_capacity, InputIterator first, InputIterator last,
1175 const allocator_type& alloc = allocator_type())
1176 : m_alloc(alloc) {
1177 initialize(buffer_capacity, first, last, is_integral<InputIterator>());
1178 }
1179
1180 //! The destructor.
1181 /*!
1182 Destroys the <code>circular_buffer</code>.
1183 \throws Nothing.
1184 \par Iterator Invalidation
1185 Invalidates all iterators pointing to the <code>circular_buffer</code> (including iterators equal to
1186 <code>end()</code>).
1187 \par Complexity
1188 Constant (in the size of the <code>circular_buffer</code>) for scalar types; linear for other types.
1189 \sa <code>clear()</code>
1190 */
1191 ~circular_buffer() BOOST_NOEXCEPT {
1192 destroy();
1193#if BOOST_CB_ENABLE_DEBUG
1194 invalidate_all_iterators();
1195#endif
1196 }
1197
1198public:
1199// Assign methods
1200
1201 //! The assign operator.
1202 /*!
1203 Makes this <code>circular_buffer</code> to become a copy of the specified <code>circular_buffer</code>.
1204 \post <code>*this == cb</code>
1205 \param cb The <code>circular_buffer</code> to be copied.
1206 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
1207 used).
1208 Whatever <code>T::T(const T&)</code> throws.
1209 \par Exception Safety
1210 Strong.
1211 \par Iterator Invalidation
1212 Invalidates all iterators pointing to this <code>circular_buffer</code> (except iterators equal to
1213 <code>end()</code>).
1214 \par Complexity
1215 Linear (in the size of <code>cb</code>).
1216 \sa <code>\link assign(size_type, param_value_type) assign(size_type, const_reference)\endlink</code>,
1217 <code>\link assign(capacity_type, size_type, param_value_type)
1218 assign(capacity_type, size_type, const_reference)\endlink</code>,
1219 <code>assign(InputIterator, InputIterator)</code>,
1220 <code>assign(capacity_type, InputIterator, InputIterator)</code>
1221 */
1222 circular_buffer<T, Alloc>& operator = (const circular_buffer<T, Alloc>& cb) {
1223 if (this == &cb)
1224 return *this;
1225 pointer buff = allocate(n: cb.capacity());
1226 BOOST_TRY {
1227 reset(buff, last: cb_details::uninitialized_copy(cb.begin(), cb.end(), buff, m_alloc), new_capacity: cb.capacity());
1228 } BOOST_CATCH(...) {
1229 deallocate(p: buff, n: cb.capacity());
1230 BOOST_RETHROW
1231 }
1232 BOOST_CATCH_END
1233 return *this;
1234 }
1235
1236#ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
1237 /*! \brief Move assigns content of <code>cb</code> to <code>*this</code>, leaving <code>cb</code> empty.
1238 \pre C++ compiler with rvalue references support.
1239 \post <code>cb.empty()</code>
1240 \param cb <code>circular_buffer</code> to 'steal' value from.
1241 \throws Nothing.
1242 \par Complexity
1243 Constant.
1244 */
1245 circular_buffer<T, Alloc>& operator = (circular_buffer<T, Alloc>&& cb) BOOST_NOEXCEPT {
1246 cb.swap(*this); // now `this` holds `cb`
1247 circular_buffer<T, Alloc>(get_allocator()) // temprary that holds initial `cb` allocator
1248 .swap(cb); // makes `cb` empty
1249 return *this;
1250 }
1251#endif // BOOST_NO_CXX11_RVALUE_REFERENCES
1252
1253 //! Assign <code>n</code> items into the <code>circular_buffer</code>.
1254 /*!
1255 The content of the <code>circular_buffer</code> will be removed and replaced with <code>n</code> copies of the
1256 <code>item</code>.
1257 \post <code>capacity() == n \&\& size() == n \&\& (*this)[0] == item \&\& (*this)[1] == item \&\& ... \&\&
1258 (*this) [n - 1] == item</code>
1259 \param n The number of elements the <code>circular_buffer</code> will be filled with.
1260 \param item The element the <code>circular_buffer</code> will be filled with.
1261 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
1262 used).
1263 Whatever <code>T::T(const T&)</code> throws.
1264 \par Exception Safety
1265 Basic.
1266 \par Iterator Invalidation
1267 Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to
1268 <code>end()</code>).
1269 \par Complexity
1270 Linear (in the <code>n</code>).
1271 \sa <code>\link operator=(const circular_buffer&) operator=\endlink</code>,
1272 <code>\link assign(capacity_type, size_type, param_value_type)
1273 assign(capacity_type, size_type, const_reference)\endlink</code>,
1274 <code>assign(InputIterator, InputIterator)</code>,
1275 <code>assign(capacity_type, InputIterator, InputIterator)</code>
1276 */
1277 void assign(size_type n, param_value_type item) {
1278 assign_n(n, n, cb_details::assign_n<param_value_type, allocator_type>(n, item, m_alloc));
1279 }
1280
1281 //! Assign <code>n</code> items into the <code>circular_buffer</code> specifying the capacity.
1282 /*!
1283 The capacity of the <code>circular_buffer</code> will be set to the specified value and the content of the
1284 <code>circular_buffer</code> will be removed and replaced with <code>n</code> copies of the <code>item</code>.
1285 \pre <code>capacity >= n</code>
1286 \post <code>capacity() == buffer_capacity \&\& size() == n \&\& (*this)[0] == item \&\& (*this)[1] == item
1287 \&\& ... \&\& (*this) [n - 1] == item </code>
1288 \param buffer_capacity The new capacity.
1289 \param n The number of elements the <code>circular_buffer</code> will be filled with.
1290 \param item The element the <code>circular_buffer</code> will be filled with.
1291 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
1292 used).
1293 Whatever <code>T::T(const T&)</code> throws.
1294 \par Exception Safety
1295 Basic.
1296 \par Iterator Invalidation
1297 Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to
1298 <code>end()</code>).
1299 \par Complexity
1300 Linear (in the <code>n</code>).
1301 \sa <code>\link operator=(const circular_buffer&) operator=\endlink</code>,
1302 <code>\link assign(size_type, param_value_type) assign(size_type, const_reference)\endlink</code>,
1303 <code>assign(InputIterator, InputIterator)</code>,
1304 <code>assign(capacity_type, InputIterator, InputIterator)</code>
1305 */
1306 void assign(capacity_type buffer_capacity, size_type n, param_value_type item) {
1307 BOOST_CB_ASSERT(buffer_capacity >= n); // check for new capacity lower than n
1308 assign_n(buffer_capacity, n, cb_details::assign_n<param_value_type, allocator_type>(n, item, m_alloc));
1309 }
1310
1311 //! Assign a copy of the range into the <code>circular_buffer</code>.
1312 /*!
1313 The content of the <code>circular_buffer</code> will be removed and replaced with copies of elements from the
1314 specified range.
1315 \pre Valid range <code>[first, last)</code>.<br>
1316 <code>first</code> and <code>last</code> have to meet the requirements of
1317 <a href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>.
1318 \post <code>capacity() == std::distance(first, last) \&\& size() == std::distance(first, last) \&\&
1319 (*this)[0]== *first \&\& (*this)[1] == *(first + 1) \&\& ... \&\& (*this)[std::distance(first, last) - 1]
1320 == *(last - 1)</code>
1321 \param first The beginning of the range to be copied.
1322 \param last The end of the range to be copied.
1323 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
1324 used).
1325 Whatever <code>T::T(const T&)</code> throws.
1326 \par Exception Safety
1327 Basic.
1328 \par Iterator Invalidation
1329 Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to
1330 <code>end()</code>).
1331 \par Complexity
1332 Linear (in the <code>std::distance(first, last)</code>).
1333 \sa <code>\link operator=(const circular_buffer&) operator=\endlink</code>,
1334 <code>\link assign(size_type, param_value_type) assign(size_type, const_reference)\endlink</code>,
1335 <code>\link assign(capacity_type, size_type, param_value_type)
1336 assign(capacity_type, size_type, const_reference)\endlink</code>,
1337 <code>assign(capacity_type, InputIterator, InputIterator)</code>
1338 */
1339 template <class InputIterator>
1340 void assign(InputIterator first, InputIterator last) {
1341 assign(first, last, is_integral<InputIterator>());
1342 }
1343
1344 //! Assign a copy of the range into the <code>circular_buffer</code> specifying the capacity.
1345 /*!
1346 The capacity of the <code>circular_buffer</code> will be set to the specified value and the content of the
1347 <code>circular_buffer</code> will be removed and replaced with copies of elements from the specified range.
1348 \pre Valid range <code>[first, last)</code>.<br>
1349 <code>first</code> and <code>last</code> have to meet the requirements of
1350 <a href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>.
1351 \post <code>capacity() == buffer_capacity \&\& size() \<= std::distance(first, last) \&\&
1352 (*this)[0]== *(last - buffer_capacity) \&\& (*this)[1] == *(last - buffer_capacity + 1) \&\& ... \&\&
1353 (*this)[buffer_capacity - 1] == *(last - 1)</code><br><br>
1354 If the number of items to be copied from the range <code>[first, last)</code> is greater than the
1355 specified <code>buffer_capacity</code> then only elements from the range
1356 <code>[last - buffer_capacity, last)</code> will be copied.
1357 \param buffer_capacity The new capacity.
1358 \param first The beginning of the range to be copied.
1359 \param last The end of the range to be copied.
1360 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
1361 used).
1362 Whatever <code>T::T(const T&)</code> throws.
1363 \par Exception Safety
1364 Basic.
1365 \par Iterator Invalidation
1366 Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to
1367 <code>end()</code>).
1368 \par Complexity
1369 Linear (in <code>std::distance(first, last)</code>; in
1370 <code>min[capacity, std::distance(first, last)]</code> if the <code>InputIterator</code> is a
1371 <a href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">RandomAccessIterator</a>).
1372 \sa <code>\link operator=(const circular_buffer&) operator=\endlink</code>,
1373 <code>\link assign(size_type, param_value_type) assign(size_type, const_reference)\endlink</code>,
1374 <code>\link assign(capacity_type, size_type, param_value_type)
1375 assign(capacity_type, size_type, const_reference)\endlink</code>,
1376 <code>assign(InputIterator, InputIterator)</code>
1377 */
1378 template <class InputIterator>
1379 void assign(capacity_type buffer_capacity, InputIterator first, InputIterator last) {
1380 assign(buffer_capacity, first, last, is_integral<InputIterator>());
1381 }
1382
1383 //! Swap the contents of two <code>circular_buffer</code>s.
1384 /*!
1385 \post <code>this</code> contains elements of <code>cb</code> and vice versa; the capacity of <code>this</code>
1386 equals to the capacity of <code>cb</code> and vice versa.
1387 \param cb The <code>circular_buffer</code> whose content will be swapped.
1388 \throws Nothing.
1389 \par Exception Safety
1390 No-throw.
1391 \par Iterator Invalidation
1392 Invalidates all iterators of both <code>circular_buffer</code>s. (On the other hand the iterators still
1393 point to the same elements but within another container. If you want to rely on this feature you have to
1394 turn the <a href="#debug">Debug Support</a> off otherwise an assertion will report an error if such
1395 invalidated iterator is used.)
1396 \par Complexity
1397 Constant (in the size of the <code>circular_buffer</code>).
1398 \sa <code>swap(circular_buffer<T, Alloc>&, circular_buffer<T, Alloc>&)</code>
1399 */
1400 void swap(circular_buffer<T, Alloc>& cb) BOOST_NOEXCEPT {
1401 swap_allocator(cb, is_stateless<allocator_type>());
1402 std::swap(m_buff, cb.m_buff);
1403 std::swap(m_end, cb.m_end);
1404 std::swap(m_first, cb.m_first);
1405 std::swap(m_last, cb.m_last);
1406 std::swap(m_size, cb.m_size);
1407#if BOOST_CB_ENABLE_DEBUG
1408 invalidate_all_iterators();
1409 cb.invalidate_all_iterators();
1410#endif
1411 }
1412
1413// push and pop
1414private:
1415 template <class ValT>
1416 void push_back_impl(ValT item) {
1417 if (full()) {
1418 if (empty())
1419 return;
1420 replace(m_last, static_cast<ValT>(item));
1421 increment(m_last);
1422 m_first = m_last;
1423 } else {
1424 boost::container::allocator_traits<Alloc>::construct(m_alloc, boost::addressof(*m_last), static_cast<ValT>(item));
1425 increment(m_last);
1426 ++m_size;
1427 }
1428 }
1429
1430 template <class ValT>
1431 void push_front_impl(ValT item) {
1432 BOOST_TRY {
1433 if (full()) {
1434 if (empty())
1435 return;
1436 decrement(m_first);
1437 replace(m_first, static_cast<ValT>(item));
1438 m_last = m_first;
1439 } else {
1440 decrement(m_first);
1441 boost::container::allocator_traits<Alloc>::construct(m_alloc, boost::addressof(*m_first), static_cast<ValT>(item));
1442 ++m_size;
1443 }
1444 } BOOST_CATCH(...) {
1445 increment(m_first);
1446 BOOST_RETHROW
1447 }
1448 BOOST_CATCH_END
1449 }
1450
1451public:
1452 //! Insert a new element at the end of the <code>circular_buffer</code>.
1453 /*!
1454 \post if <code>capacity() > 0</code> then <code>back() == item</code><br>
1455 If the <code>circular_buffer</code> is full, the first element will be removed. If the capacity is
1456 <code>0</code>, nothing will be inserted.
1457 \param item The element to be inserted.
1458 \throws Whatever <code>T::T(const T&)</code> throws.
1459 Whatever <code>T::operator = (const T&)</code> throws.
1460 \par Exception Safety
1461 Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything.
1462 \par Iterator Invalidation
1463 Does not invalidate any iterators with the exception of iterators pointing to the overwritten element.
1464 \par Complexity
1465 Constant (in the size of the <code>circular_buffer</code>).
1466 \sa <code>\link push_front() push_front(const_reference)\endlink</code>,
1467 <code>pop_back()</code>, <code>pop_front()</code>
1468 */
1469 void push_back(param_value_type item) {
1470 push_back_impl<param_value_type>(item);
1471 }
1472
1473 //! Insert a new element at the end of the <code>circular_buffer</code> using rvalue references or rvalues references emulation.
1474 /*!
1475 \post if <code>capacity() > 0</code> then <code>back() == item</code><br>
1476 If the <code>circular_buffer</code> is full, the first element will be removed. If the capacity is
1477 <code>0</code>, nothing will be inserted.
1478 \param item The element to be inserted.
1479 \throws Whatever <code>T::T(T&&)</code> throws.
1480 Whatever <code>T::operator = (T&&)</code> throws.
1481 \par Exception Safety
1482 Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything.
1483 \par Iterator Invalidation
1484 Does not invalidate any iterators with the exception of iterators pointing to the overwritten element.
1485 \par Complexity
1486 Constant (in the size of the <code>circular_buffer</code>).
1487 \sa <code>\link push_front() push_front(const_reference)\endlink</code>,
1488 <code>pop_back()</code>, <code>pop_front()</code>
1489 */
1490 void push_back(rvalue_type item) {
1491 push_back_impl<rvalue_type>(boost::move(item));
1492 }
1493
1494 //! Insert a new default-constructed element at the end of the <code>circular_buffer</code>.
1495 /*!
1496 \post if <code>capacity() > 0</code> then <code>back() == item</code><br>
1497 If the <code>circular_buffer</code> is full, the first element will be removed. If the capacity is
1498 <code>0</code>, nothing will be inserted.
1499 \throws Whatever <code>T::T()</code> throws.
1500 Whatever <code>T::T(T&&)</code> throws.
1501 Whatever <code>T::operator = (T&&)</code> throws.
1502 \par Exception Safety
1503 Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything.
1504 \par Iterator Invalidation
1505 Does not invalidate any iterators with the exception of iterators pointing to the overwritten element.
1506 \par Complexity
1507 Constant (in the size of the <code>circular_buffer</code>).
1508 \sa <code>\link push_front() push_front(const_reference)\endlink</code>,
1509 <code>pop_back()</code>, <code>pop_front()</code>
1510 */
1511 void push_back() {
1512 value_type temp;
1513 push_back(boost::move(temp));
1514 }
1515
1516 //! Insert a new element at the beginning of the <code>circular_buffer</code>.
1517 /*!
1518 \post if <code>capacity() > 0</code> then <code>front() == item</code><br>
1519 If the <code>circular_buffer</code> is full, the last element will be removed. If the capacity is
1520 <code>0</code>, nothing will be inserted.
1521 \param item The element to be inserted.
1522 \throws Whatever <code>T::T(const T&)</code> throws.
1523 Whatever <code>T::operator = (const T&)</code> throws.
1524 \par Exception Safety
1525 Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything.
1526 \par Iterator Invalidation
1527 Does not invalidate any iterators with the exception of iterators pointing to the overwritten element.
1528 \par Complexity
1529 Constant (in the size of the <code>circular_buffer</code>).
1530 \sa <code>\link push_back() push_back(const_reference)\endlink</code>,
1531 <code>pop_back()</code>, <code>pop_front()</code>
1532 */
1533 void push_front(param_value_type item) {
1534 push_front_impl<param_value_type>(item);
1535 }
1536
1537 //! Insert a new element at the beginning of the <code>circular_buffer</code> using rvalue references or rvalues references emulation.
1538 /*!
1539 \post if <code>capacity() > 0</code> then <code>front() == item</code><br>
1540 If the <code>circular_buffer</code> is full, the last element will be removed. If the capacity is
1541 <code>0</code>, nothing will be inserted.
1542 \param item The element to be inserted.
1543 \throws Whatever <code>T::T(T&&)</code> throws.
1544 Whatever <code>T::operator = (T&&)</code> throws.
1545 \par Exception Safety
1546 Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything.
1547 \par Iterator Invalidation
1548 Does not invalidate any iterators with the exception of iterators pointing to the overwritten element.
1549 \par Complexity
1550 Constant (in the size of the <code>circular_buffer</code>).
1551 \sa <code>\link push_back() push_back(const_reference)\endlink</code>,
1552 <code>pop_back()</code>, <code>pop_front()</code>
1553 */
1554 void push_front(rvalue_type item) {
1555 push_front_impl<rvalue_type>(boost::move(item));
1556 }
1557
1558 //! Insert a new default-constructed element at the beginning of the <code>circular_buffer</code>.
1559 /*!
1560 \post if <code>capacity() > 0</code> then <code>front() == item</code><br>
1561 If the <code>circular_buffer</code> is full, the last element will be removed. If the capacity is
1562 <code>0</code>, nothing will be inserted.
1563 \throws Whatever <code>T::T()</code> throws.
1564 Whatever <code>T::T(T&&)</code> throws.
1565 Whatever <code>T::operator = (T&&)</code> throws.
1566 \par Exception Safety
1567 Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything.
1568 \par Iterator Invalidation
1569 Does not invalidate any iterators with the exception of iterators pointing to the overwritten element.
1570 \par Complexity
1571 Constant (in the size of the <code>circular_buffer</code>).
1572 \sa <code>\link push_back() push_back(const_reference)\endlink</code>,
1573 <code>pop_back()</code>, <code>pop_front()</code>
1574 */
1575 void push_front() {
1576 value_type temp;
1577 push_front(boost::move(temp));
1578 }
1579
1580 //! Remove the last element from the <code>circular_buffer</code>.
1581 /*!
1582 \pre <code>!empty()</code>
1583 \post The last element is removed from the <code>circular_buffer</code>.
1584 \throws Nothing.
1585 \par Exception Safety
1586 No-throw.
1587 \par Iterator Invalidation
1588 Invalidates only iterators pointing to the removed element.
1589 \par Complexity
1590 Constant (in the size of the <code>circular_buffer</code>).
1591 \sa <code>pop_front()</code>, <code>\link push_back() push_back(const_reference)\endlink</code>,
1592 <code>\link push_front() push_front(const_reference)\endlink</code>
1593 */
1594 void pop_back() {
1595 BOOST_CB_ASSERT(!empty()); // check for empty buffer (back element not available)
1596 decrement(m_last);
1597 destroy_item(p: m_last);
1598 --m_size;
1599 }
1600
1601 //! Remove the first element from the <code>circular_buffer</code>.
1602 /*!
1603 \pre <code>!empty()</code>
1604 \post The first element is removed from the <code>circular_buffer</code>.
1605 \throws Nothing.
1606 \par Exception Safety
1607 No-throw.
1608 \par Iterator Invalidation
1609 Invalidates only iterators pointing to the removed element.
1610 \par Complexity
1611 Constant (in the size of the <code>circular_buffer</code>).
1612 \sa <code>pop_back()</code>, <code>\link push_back() push_back(const_reference)\endlink</code>,
1613 <code>\link push_front() push_front(const_reference)\endlink</code>
1614 */
1615 void pop_front() {
1616 BOOST_CB_ASSERT(!empty()); // check for empty buffer (front element not available)
1617 destroy_item(p: m_first);
1618 increment(m_first);
1619 --m_size;
1620 }
1621private:
1622 template <class ValT>
1623 iterator insert_impl(iterator pos, ValT item) {
1624 BOOST_CB_ASSERT(pos.is_valid(this)); // check for uninitialized or invalidated iterator
1625 iterator b = begin();
1626 if (full() && pos == b)
1627 return b;
1628 return insert_item<ValT>(pos, static_cast<ValT>(item));
1629 }
1630
1631public:
1632// Insert
1633
1634 //! Insert an element at the specified position.
1635 /*!
1636 \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> or its end.
1637 \post The <code>item</code> will be inserted at the position <code>pos</code>.<br>
1638 If the <code>circular_buffer</code> is full, the first element will be overwritten. If the
1639 <code>circular_buffer</code> is full and the <code>pos</code> points to <code>begin()</code>, then the
1640 <code>item</code> will not be inserted. If the capacity is <code>0</code>, nothing will be inserted.
1641 \param pos An iterator specifying the position where the <code>item</code> will be inserted.
1642 \param item The element to be inserted.
1643 \return Iterator to the inserted element or <code>begin()</code> if the <code>item</code> is not inserted. (See
1644 the <i>Effect</i>.)
1645 \throws Whatever <code>T::T(const T&)</code> throws.
1646 Whatever <code>T::operator = (const T&)</code> throws.
1647 <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>.
1648
1649 \par Exception Safety
1650 Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything.
1651 \par Iterator Invalidation
1652 Invalidates iterators pointing to the elements at the insertion point (including <code>pos</code>) and
1653 iterators behind the insertion point (towards the end; except iterators equal to <code>end()</code>). It
1654 also invalidates iterators pointing to the overwritten element.
1655 \par Complexity
1656 Linear (in <code>std::distance(pos, end())</code>).
1657 \sa <code>\link insert(iterator, size_type, param_value_type)
1658 insert(iterator, size_type, value_type)\endlink</code>,
1659 <code>insert(iterator, InputIterator, InputIterator)</code>,
1660 <code>\link rinsert(iterator, param_value_type) rinsert(iterator, value_type)\endlink</code>,
1661 <code>\link rinsert(iterator, size_type, param_value_type)
1662 rinsert(iterator, size_type, value_type)\endlink</code>,
1663 <code>rinsert(iterator, InputIterator, InputIterator)</code>
1664 */
1665 iterator insert(iterator pos, param_value_type item) {
1666 return insert_impl<param_value_type>(pos, item);
1667 }
1668
1669 //! Insert an element at the specified position.
1670 /*!
1671 \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> or its end.
1672 \post The <code>item</code> will be inserted at the position <code>pos</code>.<br>
1673 If the <code>circular_buffer</code> is full, the first element will be overwritten. If the
1674 <code>circular_buffer</code> is full and the <code>pos</code> points to <code>begin()</code>, then the
1675 <code>item</code> will not be inserted. If the capacity is <code>0</code>, nothing will be inserted.
1676 \param pos An iterator specifying the position where the <code>item</code> will be inserted.
1677 \param item The element to be inserted.
1678 \return Iterator to the inserted element or <code>begin()</code> if the <code>item</code> is not inserted. (See
1679 the <i>Effect</i>.)
1680 \throws Whatever <code>T::T(T&&)</code> throws.
1681 Whatever <code>T::operator = (T&&)</code> throws.
1682 <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>.
1683 \par Exception Safety
1684 Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything.
1685 \par Iterator Invalidation
1686 Invalidates iterators pointing to the elements at the insertion point (including <code>pos</code>) and
1687 iterators behind the insertion point (towards the end; except iterators equal to <code>end()</code>). It
1688 also invalidates iterators pointing to the overwritten element.
1689 \par Complexity
1690 Linear (in <code>std::distance(pos, end())</code>).
1691 \sa <code>\link insert(iterator, size_type, param_value_type)
1692 insert(iterator, size_type, value_type)\endlink</code>,
1693 <code>insert(iterator, InputIterator, InputIterator)</code>,
1694 <code>\link rinsert(iterator, param_value_type) rinsert(iterator, value_type)\endlink</code>,
1695 <code>\link rinsert(iterator, size_type, param_value_type)
1696 rinsert(iterator, size_type, value_type)\endlink</code>,
1697 <code>rinsert(iterator, InputIterator, InputIterator)</code>
1698 */
1699 iterator insert(iterator pos, rvalue_type item) {
1700 return insert_impl<rvalue_type>(pos, boost::move(item));
1701 }
1702
1703 //! Insert a default-constructed element at the specified position.
1704 /*!
1705 \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> or its end.
1706 \post The <code>item</code> will be inserted at the position <code>pos</code>.<br>
1707 If the <code>circular_buffer</code> is full, the first element will be overwritten. If the
1708 <code>circular_buffer</code> is full and the <code>pos</code> points to <code>begin()</code>, then the
1709 <code>item</code> will not be inserted. If the capacity is <code>0</code>, nothing will be inserted.
1710 \param pos An iterator specifying the position where the <code>item</code> will be inserted.
1711 \return Iterator to the inserted element or <code>begin()</code> if the <code>item</code> is not inserted. (See
1712 the <i>Effect</i>.)
1713 \throws Whatever <code>T::T()</code> throws.
1714 Whatever <code>T::T(T&&)</code> throws.
1715 Whatever <code>T::operator = (T&&)</code> throws.
1716 <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>.
1717 \par Exception Safety
1718 Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything.
1719 \par Iterator Invalidation
1720 Invalidates iterators pointing to the elements at the insertion point (including <code>pos</code>) and
1721 iterators behind the insertion point (towards the end; except iterators equal to <code>end()</code>). It
1722 also invalidates iterators pointing to the overwritten element.
1723 \par Complexity
1724 Linear (in <code>std::distance(pos, end())</code>).
1725 \sa <code>\link insert(iterator, size_type, param_value_type)
1726 insert(iterator, size_type, value_type)\endlink</code>,
1727 <code>insert(iterator, InputIterator, InputIterator)</code>,
1728 <code>\link rinsert(iterator, param_value_type) rinsert(iterator, value_type)\endlink</code>,
1729 <code>\link rinsert(iterator, size_type, param_value_type)
1730 rinsert(iterator, size_type, value_type)\endlink</code>,
1731 <code>rinsert(iterator, InputIterator, InputIterator)</code>
1732 */
1733 iterator insert(iterator pos) {
1734 value_type temp;
1735 return insert(pos, boost::move(temp));
1736 }
1737
1738 //! Insert <code>n</code> copies of the <code>item</code> at the specified position.
1739 /*!
1740 \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> or its end.
1741 \post The number of <code>min[n, (pos - begin()) + reserve()]</code> elements will be inserted at the position
1742 <code>pos</code>.<br>The number of <code>min[pos - begin(), max[0, n - reserve()]]</code> elements will
1743 be overwritten at the beginning of the <code>circular_buffer</code>.<br>(See <i>Example</i> for the
1744 explanation.)
1745 \param pos An iterator specifying the position where the <code>item</code>s will be inserted.
1746 \param n The number of <code>item</code>s the to be inserted.
1747 \param item The element whose copies will be inserted.
1748 \throws Whatever <code>T::T(const T&)</code> throws.
1749 Whatever <code>T::operator = (const T&)</code> throws.
1750 <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>.
1751 \par Exception Safety
1752 Basic; no-throw if the operations in the <i>Throws</i> section do not throw anything.
1753 \par Iterator Invalidation
1754 Invalidates iterators pointing to the elements at the insertion point (including <code>pos</code>) and
1755 iterators behind the insertion point (towards the end; except iterators equal to <code>end()</code>). It
1756 also invalidates iterators pointing to the overwritten elements.
1757 \par Complexity
1758 Linear (in <code>min[capacity(), std::distance(pos, end()) + n]</code>).
1759 \par Example
1760 Consider a <code>circular_buffer</code> with the capacity of 6 and the size of 4. Its internal buffer may
1761 look like the one below.<br><br>
1762 <code>|1|2|3|4| | |</code><br>
1763 <code>p ___^</code><br><br>After inserting 5 elements at the position <code>p</code>:<br><br>
1764 <code>insert(p, (size_t)5, 0);</code><br><br>actually only 4 elements get inserted and elements
1765 <code>1</code> and <code>2</code> are overwritten. This is due to the fact the insert operation preserves
1766 the capacity. After insertion the internal buffer looks like this:<br><br><code>|0|0|0|0|3|4|</code><br>
1767 <br>For comparison if the capacity would not be preserved the internal buffer would then result in
1768 <code>|1|2|0|0|0|0|0|3|4|</code>.
1769 \sa <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>,
1770 <code>insert(iterator, InputIterator, InputIterator)</code>,
1771 <code>\link rinsert(iterator, param_value_type) rinsert(iterator, value_type)\endlink</code>,
1772 <code>\link rinsert(iterator, size_type, param_value_type)
1773 rinsert(iterator, size_type, value_type)\endlink</code>,
1774 <code>rinsert(iterator, InputIterator, InputIterator)</code>
1775 */
1776 void insert(iterator pos, size_type n, param_value_type item) {
1777 BOOST_CB_ASSERT(pos.is_valid(this)); // check for uninitialized or invalidated iterator
1778 if (n == 0)
1779 return;
1780 size_type copy = capacity() - (end() - pos);
1781 if (copy == 0)
1782 return;
1783 if (n > copy)
1784 n = copy;
1785 insert_n(pos, n, cb_details::item_wrapper<const_pointer, param_value_type>(item));
1786 }
1787
1788 //! Insert the range <code>[first, last)</code> at the specified position.
1789 /*!
1790 \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> or its end.<br>
1791 Valid range <code>[first, last)</code> where <code>first</code> and <code>last</code> meet the
1792 requirements of an <a href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>.
1793 \post Elements from the range
1794 <code>[first + max[0, distance(first, last) - (pos - begin()) - reserve()], last)</code> will be
1795 inserted at the position <code>pos</code>.<br>The number of <code>min[pos - begin(), max[0,
1796 distance(first, last) - reserve()]]</code> elements will be overwritten at the beginning of the
1797 <code>circular_buffer</code>.<br>(See <i>Example</i> for the explanation.)
1798 \param pos An iterator specifying the position where the range will be inserted.
1799 \param first The beginning of the range to be inserted.
1800 \param last The end of the range to be inserted.
1801 \throws Whatever <code>T::T(const T&)</code> throws if the <code>InputIterator</code> is not a move iterator.
1802 Whatever <code>T::operator = (const T&)</code> throws if the <code>InputIterator</code> is not a move iterator.
1803 Whatever <code>T::T(T&&)</code> throws if the <code>InputIterator</code> is a move iterator.
1804 Whatever <code>T::operator = (T&&)</code> throws if the <code>InputIterator</code> is a move iterator.
1805 \par Exception Safety
1806 Basic; no-throw if the operations in the <i>Throws</i> section do not throw anything.
1807 \par Iterator Invalidation
1808 Invalidates iterators pointing to the elements at the insertion point (including <code>pos</code>) and
1809 iterators behind the insertion point (towards the end; except iterators equal to <code>end()</code>). It
1810 also invalidates iterators pointing to the overwritten elements.
1811 \par Complexity
1812 Linear (in <code>[std::distance(pos, end()) + std::distance(first, last)]</code>; in
1813 <code>min[capacity(), std::distance(pos, end()) + std::distance(first, last)]</code> if the
1814 <code>InputIterator</code> is a
1815 <a href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">RandomAccessIterator</a>).
1816 \par Example
1817 Consider a <code>circular_buffer</code> with the capacity of 6 and the size of 4. Its internal buffer may
1818 look like the one below.<br><br>
1819 <code>|1|2|3|4| | |</code><br>
1820 <code>p ___^</code><br><br>After inserting a range of elements at the position <code>p</code>:<br><br>
1821 <code>int array[] = { 5, 6, 7, 8, 9 };</code><br><code>insert(p, array, array + 5);</code><br><br>
1822 actually only elements <code>6</code>, <code>7</code>, <code>8</code> and <code>9</code> from the
1823 specified range get inserted and elements <code>1</code> and <code>2</code> are overwritten. This is due
1824 to the fact the insert operation preserves the capacity. After insertion the internal buffer looks like
1825 this:<br><br><code>|6|7|8|9|3|4|</code><br><br>For comparison if the capacity would not be preserved the
1826 internal buffer would then result in <code>|1|2|5|6|7|8|9|3|4|</code>.
1827 \sa <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>,
1828 <code>\link insert(iterator, size_type, param_value_type)
1829 insert(iterator, size_type, value_type)\endlink</code>, <code>\link rinsert(iterator, param_value_type)
1830 rinsert(iterator, value_type)\endlink</code>, <code>\link rinsert(iterator, size_type, param_value_type)
1831 rinsert(iterator, size_type, value_type)\endlink</code>,
1832 <code>rinsert(iterator, InputIterator, InputIterator)</code>
1833 */
1834 template <class InputIterator>
1835 void insert(iterator pos, InputIterator first, InputIterator last) {
1836 BOOST_CB_ASSERT(pos.is_valid(this)); // check for uninitialized or invalidated iterator
1837 insert(pos, first, last, is_integral<InputIterator>());
1838 }
1839
1840private:
1841 template <class ValT>
1842 iterator rinsert_impl(iterator pos, ValT item) {
1843 BOOST_CB_ASSERT(pos.is_valid(this)); // check for uninitialized or invalidated iterator
1844 if (full() && pos.m_it == 0)
1845 return end();
1846 if (pos == begin()) {
1847 BOOST_TRY {
1848 decrement(m_first);
1849 construct_or_replace(!full(), m_first, static_cast<ValT>(item));
1850 } BOOST_CATCH(...) {
1851 increment(m_first);
1852 BOOST_RETHROW
1853 }
1854 BOOST_CATCH_END
1855 pos.m_it = m_first;
1856 } else {
1857 pointer src = m_first;
1858 pointer dest = m_first;
1859 decrement(dest);
1860 pos.m_it = map_pointer(p: pos.m_it);
1861 bool construct = !full();
1862 BOOST_TRY {
1863 while (src != pos.m_it) {
1864 construct_or_replace(construct, dest, boost::move_if_noexcept(*src));
1865 increment(src);
1866 increment(dest);
1867 construct = false;
1868 }
1869 decrement(pos.m_it);
1870 replace(pos.m_it, static_cast<ValT>(item));
1871 } BOOST_CATCH(...) {
1872 if (!construct && !full()) {
1873 decrement(m_first);
1874 ++m_size;
1875 }
1876 BOOST_RETHROW
1877 }
1878 BOOST_CATCH_END
1879 decrement(m_first);
1880 }
1881 if (full())
1882 m_last = m_first;
1883 else
1884 ++m_size;
1885 return iterator(this, pos.m_it);
1886 }
1887
1888public:
1889
1890 //! Insert an element before the specified position.
1891 /*!
1892 \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> or its end.
1893 \post The <code>item</code> will be inserted before the position <code>pos</code>.<br>
1894 If the <code>circular_buffer</code> is full, the last element will be overwritten. If the
1895 <code>circular_buffer</code> is full and the <code>pos</code> points to <code>end()</code>, then the
1896 <code>item</code> will not be inserted. If the capacity is <code>0</code>, nothing will be inserted.
1897 \param pos An iterator specifying the position before which the <code>item</code> will be inserted.
1898 \param item The element to be inserted.
1899 \return Iterator to the inserted element or <code>end()</code> if the <code>item</code> is not inserted. (See
1900 the <i>Effect</i>.)
1901 \throws Whatever <code>T::T(const T&)</code> throws.
1902 Whatever <code>T::operator = (const T&)</code> throws.
1903 <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>.
1904 \par Exception Safety
1905 Basic; no-throw if the operations in the <i>Throws</i> section do not throw anything.
1906 \par Iterator Invalidation
1907 Invalidates iterators pointing to the elements before the insertion point (towards the beginning and
1908 excluding <code>pos</code>). It also invalidates iterators pointing to the overwritten element.
1909 \par Complexity
1910 Linear (in <code>std::distance(begin(), pos)</code>).
1911 \sa <code>\link rinsert(iterator, size_type, param_value_type)
1912 rinsert(iterator, size_type, value_type)\endlink</code>,
1913 <code>rinsert(iterator, InputIterator, InputIterator)</code>,
1914 <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>,
1915 <code>\link insert(iterator, size_type, param_value_type)
1916 insert(iterator, size_type, value_type)\endlink</code>,
1917 <code>insert(iterator, InputIterator, InputIterator)</code>
1918 */
1919 iterator rinsert(iterator pos, param_value_type item) {
1920 return rinsert_impl<param_value_type>(pos, item);
1921 }
1922
1923 //! Insert an element before the specified position.
1924 /*!
1925 \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> or its end.
1926 \post The <code>item</code> will be inserted before the position <code>pos</code>.<br>
1927 If the <code>circular_buffer</code> is full, the last element will be overwritten. If the
1928 <code>circular_buffer</code> is full and the <code>pos</code> points to <code>end()</code>, then the
1929 <code>item</code> will not be inserted. If the capacity is <code>0</code>, nothing will be inserted.
1930 \param pos An iterator specifying the position before which the <code>item</code> will be inserted.
1931 \param item The element to be inserted.
1932 \return Iterator to the inserted element or <code>end()</code> if the <code>item</code> is not inserted. (See
1933 the <i>Effect</i>.)
1934 \throws Whatever <code>T::T(T&&)</code> throws.
1935 Whatever <code>T::operator = (T&&)</code> throws.
1936 <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>.
1937 \par Exception Safety
1938 Basic; no-throw if the operations in the <i>Throws</i> section do not throw anything.
1939 \par Iterator Invalidation
1940 Invalidates iterators pointing to the elements before the insertion point (towards the beginning and
1941 excluding <code>pos</code>). It also invalidates iterators pointing to the overwritten element.
1942 \par Complexity
1943 Linear (in <code>std::distance(begin(), pos)</code>).
1944 \sa <code>\link rinsert(iterator, size_type, param_value_type)
1945 rinsert(iterator, size_type, value_type)\endlink</code>,
1946 <code>rinsert(iterator, InputIterator, InputIterator)</code>,
1947 <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>,
1948 <code>\link insert(iterator, size_type, param_value_type)
1949 insert(iterator, size_type, value_type)\endlink</code>,
1950 <code>insert(iterator, InputIterator, InputIterator)</code>
1951 */
1952 iterator rinsert(iterator pos, rvalue_type item) {
1953 return rinsert_impl<rvalue_type>(pos, boost::move(item));
1954 }
1955
1956 //! Insert an element before the specified position.
1957 /*!
1958 \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> or its end.
1959 \post The <code>item</code> will be inserted before the position <code>pos</code>.<br>
1960 If the <code>circular_buffer</code> is full, the last element will be overwritten. If the
1961 <code>circular_buffer</code> is full and the <code>pos</code> points to <code>end()</code>, then the
1962 <code>item</code> will not be inserted. If the capacity is <code>0</code>, nothing will be inserted.
1963 \param pos An iterator specifying the position before which the <code>item</code> will be inserted.
1964 \return Iterator to the inserted element or <code>end()</code> if the <code>item</code> is not inserted. (See
1965 the <i>Effect</i>.)
1966 \throws Whatever <code>T::T()</code> throws.
1967 Whatever <code>T::T(T&&)</code> throws.
1968 Whatever <code>T::operator = (T&&)</code> throws.
1969 <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>.
1970 \par Exception Safety
1971 Basic; no-throw if the operations in the <i>Throws</i> section do not throw anything.
1972 \par Iterator Invalidation
1973 Invalidates iterators pointing to the elements before the insertion point (towards the beginning and
1974 excluding <code>pos</code>). It also invalidates iterators pointing to the overwritten element.
1975 \par Complexity
1976 Linear (in <code>std::distance(begin(), pos)</code>).
1977 \sa <code>\link rinsert(iterator, size_type, param_value_type)
1978 rinsert(iterator, size_type, value_type)\endlink</code>,
1979 <code>rinsert(iterator, InputIterator, InputIterator)</code>,
1980 <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>,
1981 <code>\link insert(iterator, size_type, param_value_type)
1982 insert(iterator, size_type, value_type)\endlink</code>,
1983 <code>insert(iterator, InputIterator, InputIterator)</code>
1984 */
1985 iterator rinsert(iterator pos) {
1986 value_type temp;
1987 return rinsert(pos, boost::move(temp));
1988 }
1989
1990 //! Insert <code>n</code> copies of the <code>item</code> before the specified position.
1991 /*!
1992 \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> or its end.
1993 \post The number of <code>min[n, (end() - pos) + reserve()]</code> elements will be inserted before the
1994 position <code>pos</code>.<br>The number of <code>min[end() - pos, max[0, n - reserve()]]</code> elements
1995 will be overwritten at the end of the <code>circular_buffer</code>.<br>(See <i>Example</i> for the
1996 explanation.)
1997 \param pos An iterator specifying the position where the <code>item</code>s will be inserted.
1998 \param n The number of <code>item</code>s the to be inserted.
1999 \param item The element whose copies will be inserted.
2000 \throws Whatever <code>T::T(const T&)</code> throws.
2001 Whatever <code>T::operator = (const T&)</code> throws.
2002 <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>.
2003 \par Exception Safety
2004 Basic; no-throw if the operations in the <i>Throws</i> section do not throw anything.
2005 \par Iterator Invalidation
2006 Invalidates iterators pointing to the elements before the insertion point (towards the beginning and
2007 excluding <code>pos</code>). It also invalidates iterators pointing to the overwritten elements.
2008 \par Complexity
2009 Linear (in <code>min[capacity(), std::distance(begin(), pos) + n]</code>).
2010 \par Example
2011 Consider a <code>circular_buffer</code> with the capacity of 6 and the size of 4. Its internal buffer may
2012 look like the one below.<br><br>
2013 <code>|1|2|3|4| | |</code><br>
2014 <code>p ___^</code><br><br>After inserting 5 elements before the position <code>p</code>:<br><br>
2015 <code>rinsert(p, (size_t)5, 0);</code><br><br>actually only 4 elements get inserted and elements
2016 <code>3</code> and <code>4</code> are overwritten. This is due to the fact the rinsert operation preserves
2017 the capacity. After insertion the internal buffer looks like this:<br><br><code>|1|2|0|0|0|0|</code><br>
2018 <br>For comparison if the capacity would not be preserved the internal buffer would then result in
2019 <code>|1|2|0|0|0|0|0|3|4|</code>.
2020 \sa <code>\link rinsert(iterator, param_value_type) rinsert(iterator, value_type)\endlink</code>,
2021 <code>rinsert(iterator, InputIterator, InputIterator)</code>,
2022 <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>,
2023 <code>\link insert(iterator, size_type, param_value_type)
2024 insert(iterator, size_type, value_type)\endlink</code>,
2025 <code>insert(iterator, InputIterator, InputIterator)</code>
2026 */
2027 void rinsert(iterator pos, size_type n, param_value_type item) {
2028 BOOST_CB_ASSERT(pos.is_valid(this)); // check for uninitialized or invalidated iterator
2029 rinsert_n(pos, n, cb_details::item_wrapper<const_pointer, param_value_type>(item));
2030 }
2031
2032 //! Insert the range <code>[first, last)</code> before the specified position.
2033 /*!
2034 \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> or its end.<br>
2035 Valid range <code>[first, last)</code> where <code>first</code> and <code>last</code> meet the
2036 requirements of an <a href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>.
2037 \post Elements from the range
2038 <code>[first, last - max[0, distance(first, last) - (end() - pos) - reserve()])</code> will be inserted
2039 before the position <code>pos</code>.<br>The number of <code>min[end() - pos, max[0,
2040 distance(first, last) - reserve()]]</code> elements will be overwritten at the end of the
2041 <code>circular_buffer</code>.<br>(See <i>Example</i> for the explanation.)
2042 \param pos An iterator specifying the position where the range will be inserted.
2043 \param first The beginning of the range to be inserted.
2044 \param last The end of the range to be inserted.
2045 \throws Whatever <code>T::T(const T&)</code> throws if the <code>InputIterator</code> is not a move iterator.
2046 Whatever <code>T::operator = (const T&)</code> throws if the <code>InputIterator</code> is not a move iterator.
2047 Whatever <code>T::T(T&&)</code> throws if the <code>InputIterator</code> is a move iterator.
2048 Whatever <code>T::operator = (T&&)</code> throws if the <code>InputIterator</code> is a move iterator.
2049 \par Exception Safety
2050 Basic; no-throw if the operations in the <i>Throws</i> section do not throw anything.
2051 \par Iterator Invalidation
2052 Invalidates iterators pointing to the elements before the insertion point (towards the beginning and
2053 excluding <code>pos</code>). It also invalidates iterators pointing to the overwritten elements.
2054 \par Complexity
2055 Linear (in <code>[std::distance(begin(), pos) + std::distance(first, last)]</code>; in
2056 <code>min[capacity(), std::distance(begin(), pos) + std::distance(first, last)]</code> if the
2057 <code>InputIterator</code> is a
2058 <a href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">RandomAccessIterator</a>).
2059 \par Example
2060 Consider a <code>circular_buffer</code> with the capacity of 6 and the size of 4. Its internal buffer may
2061 look like the one below.<br><br>
2062 <code>|1|2|3|4| | |</code><br>
2063 <code>p ___^</code><br><br>After inserting a range of elements before the position <code>p</code>:<br><br>
2064 <code>int array[] = { 5, 6, 7, 8, 9 };</code><br><code>insert(p, array, array + 5);</code><br><br>
2065 actually only elements <code>5</code>, <code>6</code>, <code>7</code> and <code>8</code> from the
2066 specified range get inserted and elements <code>3</code> and <code>4</code> are overwritten. This is due
2067 to the fact the rinsert operation preserves the capacity. After insertion the internal buffer looks like
2068 this:<br><br><code>|1|2|5|6|7|8|</code><br><br>For comparison if the capacity would not be preserved the
2069 internal buffer would then result in <code>|1|2|5|6|7|8|9|3|4|</code>.
2070 \sa <code>\link rinsert(iterator, param_value_type) rinsert(iterator, value_type)\endlink</code>,
2071 <code>\link rinsert(iterator, size_type, param_value_type)
2072 rinsert(iterator, size_type, value_type)\endlink</code>, <code>\link insert(iterator, param_value_type)
2073 insert(iterator, value_type)\endlink</code>, <code>\link insert(iterator, size_type, param_value_type)
2074 insert(iterator, size_type, value_type)\endlink</code>,
2075 <code>insert(iterator, InputIterator, InputIterator)</code>
2076 */
2077 template <class InputIterator>
2078 void rinsert(iterator pos, InputIterator first, InputIterator last) {
2079 BOOST_CB_ASSERT(pos.is_valid(this)); // check for uninitialized or invalidated iterator
2080 rinsert(pos, first, last, is_integral<InputIterator>());
2081 }
2082
2083// Erase
2084
2085 //! Remove an element at the specified position.
2086 /*!
2087 \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> (but not an
2088 <code>end()</code>).
2089 \post The element at the position <code>pos</code> is removed.
2090 \param pos An iterator pointing at the element to be removed.
2091 \return Iterator to the first element remaining beyond the removed element or <code>end()</code> if no such
2092 element exists.
2093 \throws <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>.
2094 \par Exception Safety
2095 Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything.
2096 \par Iterator Invalidation
2097 Invalidates iterators pointing to the erased element and iterators pointing to the elements behind
2098 the erased element (towards the end; except iterators equal to <code>end()</code>).
2099 \par Complexity
2100 Linear (in <code>std::distance(pos, end())</code>).
2101 \sa <code>erase(iterator, iterator)</code>, <code>rerase(iterator)</code>,
2102 <code>rerase(iterator, iterator)</code>, <code>erase_begin(size_type)</code>,
2103 <code>erase_end(size_type)</code>, <code>clear()</code>
2104 */
2105 iterator erase(iterator pos) {
2106 BOOST_CB_ASSERT(pos.is_valid(this)); // check for uninitialized or invalidated iterator
2107 BOOST_CB_ASSERT(pos.m_it != 0); // check for iterator pointing to end()
2108 pointer next = pos.m_it;
2109 increment(next);
2110 for (pointer p = pos.m_it; next != m_last; p = next, increment(next))
2111 replace(p, boost::move_if_noexcept(*next));
2112 decrement(m_last);
2113 destroy_item(p: m_last);
2114 --m_size;
2115#if BOOST_CB_ENABLE_DEBUG
2116 return m_last == pos.m_it ? end() : iterator(this, pos.m_it);
2117#else
2118 return m_last == pos.m_it ? end() : pos;
2119#endif
2120 }
2121
2122 //! Erase the range <code>[first, last)</code>.
2123 /*!
2124 \pre Valid range <code>[first, last)</code>.
2125 \post The elements from the range <code>[first, last)</code> are removed. (If <code>first == last</code>
2126 nothing is removed.)
2127 \param first The beginning of the range to be removed.
2128 \param last The end of the range to be removed.
2129 \return Iterator to the first element remaining beyond the removed elements or <code>end()</code> if no such
2130 element exists.
2131 \throws <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>.
2132 \par Exception Safety
2133 Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything.
2134 \par Iterator Invalidation
2135 Invalidates iterators pointing to the erased elements and iterators pointing to the elements behind
2136 the erased range (towards the end; except iterators equal to <code>end()</code>).
2137 \par Complexity
2138 Linear (in <code>std::distance(first, end())</code>).
2139 \sa <code>erase(iterator)</code>, <code>rerase(iterator)</code>, <code>rerase(iterator, iterator)</code>,
2140 <code>erase_begin(size_type)</code>, <code>erase_end(size_type)</code>, <code>clear()</code>
2141 */
2142 iterator erase(iterator first, iterator last) {
2143 BOOST_CB_ASSERT(first.is_valid(this)); // check for uninitialized or invalidated iterator
2144 BOOST_CB_ASSERT(last.is_valid(this)); // check for uninitialized or invalidated iterator
2145 BOOST_CB_ASSERT(first <= last); // check for wrong range
2146 if (first == last)
2147 return first;
2148 pointer p = first.m_it;
2149 while (last.m_it != 0)
2150 replace((first++).m_it, boost::move_if_noexcept(*last++));
2151 do {
2152 decrement(m_last);
2153 destroy_item(p: m_last);
2154 --m_size;
2155 } while(m_last != first.m_it);
2156 return m_last == p ? end() : iterator(this, p);
2157 }
2158
2159 //! Remove an element at the specified position.
2160 /*!
2161 \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer</code> (but not an
2162 <code>end()</code>).
2163 \post The element at the position <code>pos</code> is removed.
2164 \param pos An iterator pointing at the element to be removed.
2165 \return Iterator to the first element remaining in front of the removed element or <code>begin()</code> if no
2166 such element exists.
2167 \throws <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>.
2168 \par Exception Safety
2169 Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything.
2170 \par Iterator Invalidation
2171 Invalidates iterators pointing to the erased element and iterators pointing to the elements in front of
2172 the erased element (towards the beginning).
2173 \par Complexity
2174 Linear (in <code>std::distance(begin(), pos)</code>).
2175 \note This method is symetric to the <code>erase(iterator)</code> method and is more effective than
2176 <code>erase(iterator)</code> if the iterator <code>pos</code> is close to the beginning of the
2177 <code>circular_buffer</code>. (See the <i>Complexity</i>.)
2178 \sa <code>erase(iterator)</code>, <code>erase(iterator, iterator)</code>,
2179 <code>rerase(iterator, iterator)</code>, <code>erase_begin(size_type)</code>,
2180 <code>erase_end(size_type)</code>, <code>clear()</code>
2181 */
2182 iterator rerase(iterator pos) {
2183 BOOST_CB_ASSERT(pos.is_valid(this)); // check for uninitialized or invalidated iterator
2184 BOOST_CB_ASSERT(pos.m_it != 0); // check for iterator pointing to end()
2185 pointer prev = pos.m_it;
2186 pointer p = prev;
2187 for (decrement(prev); p != m_first; p = prev, decrement(prev))
2188 replace(p, boost::move_if_noexcept(*prev));
2189 destroy_item(p: m_first);
2190 increment(m_first);
2191 --m_size;
2192#if BOOST_CB_ENABLE_DEBUG
2193 return p == pos.m_it ? begin() : iterator(this, pos.m_it);
2194#else
2195 return p == pos.m_it ? begin() : pos;
2196#endif
2197 }
2198
2199 //! Erase the range <code>[first, last)</code>.
2200 /*!
2201 \pre Valid range <code>[first, last)</code>.
2202 \post The elements from the range <code>[first, last)</code> are removed. (If <code>first == last</code>
2203 nothing is removed.)
2204 \param first The beginning of the range to be removed.
2205 \param last The end of the range to be removed.
2206 \return Iterator to the first element remaining in front of the removed elements or <code>begin()</code> if no
2207 such element exists.
2208 \throws <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>.
2209 \par Exception Safety
2210 Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything.
2211 \par Iterator Invalidation
2212 Invalidates iterators pointing to the erased elements and iterators pointing to the elements in front of
2213 the erased range (towards the beginning).
2214 \par Complexity
2215 Linear (in <code>std::distance(begin(), last)</code>).
2216 \note This method is symetric to the <code>erase(iterator, iterator)</code> method and is more effective than
2217 <code>erase(iterator, iterator)</code> if <code>std::distance(begin(), first)</code> is lower that
2218 <code>std::distance(last, end())</code>.
2219 \sa <code>erase(iterator)</code>, <code>erase(iterator, iterator)</code>, <code>rerase(iterator)</code>,
2220 <code>erase_begin(size_type)</code>, <code>erase_end(size_type)</code>, <code>clear()</code>
2221 */
2222 iterator rerase(iterator first, iterator last) {
2223 BOOST_CB_ASSERT(first.is_valid(this)); // check for uninitialized or invalidated iterator
2224 BOOST_CB_ASSERT(last.is_valid(this)); // check for uninitialized or invalidated iterator
2225 BOOST_CB_ASSERT(first <= last); // check for wrong range
2226 if (first == last)
2227 return first;
2228 pointer p = map_pointer(p: last.m_it);
2229 last.m_it = p;
2230 while (first.m_it != m_first) {
2231 decrement(first.m_it);
2232 decrement(p);
2233 replace(p, boost::move_if_noexcept(*first.m_it));
2234 }
2235 do {
2236 destroy_item(p: m_first);
2237 increment(m_first);
2238 --m_size;
2239 } while(m_first != p);
2240 if (m_first == last.m_it)
2241 return begin();
2242 decrement(last.m_it);
2243 return iterator(this, last.m_it);
2244 }
2245
2246 //! Remove first <code>n</code> elements (with constant complexity for scalar types).
2247 /*!
2248 \pre <code>n \<= size()</code>
2249 \post The <code>n</code> elements at the beginning of the <code>circular_buffer</code> will be removed.
2250 \param n The number of elements to be removed.
2251 \throws <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>.
2252 \par Exception Safety
2253 Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything. (I.e. no throw in
2254 case of scalars.)
2255 \par Iterator Invalidation
2256 Invalidates iterators pointing to the first <code>n</code> erased elements.
2257 \par Complexity
2258 Constant (in <code>n</code>) for scalar types; linear for other types.
2259 \note This method has been specially designed for types which do not require an explicit destructruction (e.g.
2260 integer, float or a pointer). For these scalar types a call to a destructor is not required which makes
2261 it possible to implement the "erase from beginning" operation with a constant complexity. For non-sacalar
2262 types the complexity is linear (hence the explicit destruction is needed) and the implementation is
2263 actually equivalent to
2264 <code>\link circular_buffer::rerase(iterator, iterator) rerase(begin(), begin() + n)\endlink</code>.
2265 \sa <code>erase(iterator)</code>, <code>erase(iterator, iterator)</code>,
2266 <code>rerase(iterator)</code>, <code>rerase(iterator, iterator)</code>,
2267 <code>erase_end(size_type)</code>, <code>clear()</code>
2268 */
2269 void erase_begin(size_type n) {
2270 BOOST_CB_ASSERT(n <= size()); // check for n greater than size
2271#if BOOST_CB_ENABLE_DEBUG
2272 erase_begin(n, false_type());
2273#else
2274 erase_begin(n, is_scalar<value_type>());
2275#endif
2276 }
2277
2278 //! Remove last <code>n</code> elements (with constant complexity for scalar types).
2279 /*!
2280 \pre <code>n \<= size()</code>
2281 \post The <code>n</code> elements at the end of the <code>circular_buffer</code> will be removed.
2282 \param n The number of elements to be removed.
2283 \throws <a href="circular_buffer/implementation.html#circular_buffer.implementation.exceptions_of_move_if_noexcept_t">Exceptions of move_if_noexcept(T&)</a>.
2284 \par Exception Safety
2285 Basic; no-throw if the operation in the <i>Throws</i> section does not throw anything. (I.e. no throw in
2286 case of scalars.)
2287 \par Iterator Invalidation
2288 Invalidates iterators pointing to the last <code>n</code> erased elements.
2289 \par Complexity
2290 Constant (in <code>n</code>) for scalar types; linear for other types.
2291 \note This method has been specially designed for types which do not require an explicit destructruction (e.g.
2292 integer, float or a pointer). For these scalar types a call to a destructor is not required which makes
2293 it possible to implement the "erase from end" operation with a constant complexity. For non-sacalar
2294 types the complexity is linear (hence the explicit destruction is needed) and the implementation is
2295 actually equivalent to
2296 <code>\link circular_buffer::erase(iterator, iterator) erase(end() - n, end())\endlink</code>.
2297 \sa <code>erase(iterator)</code>, <code>erase(iterator, iterator)</code>,
2298 <code>rerase(iterator)</code>, <code>rerase(iterator, iterator)</code>,
2299 <code>erase_begin(size_type)</code>, <code>clear()</code>
2300 */
2301 void erase_end(size_type n) {
2302 BOOST_CB_ASSERT(n <= size()); // check for n greater than size
2303#if BOOST_CB_ENABLE_DEBUG
2304 erase_end(n, false_type());
2305#else
2306 erase_end(n, is_scalar<value_type>());
2307#endif
2308 }
2309
2310 //! Remove all stored elements from the <code>circular_buffer</code>.
2311 /*!
2312 \post <code>size() == 0</code>
2313 \throws Nothing.
2314 \par Exception Safety
2315 No-throw.
2316 \par Iterator Invalidation
2317 Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to
2318 <code>end()</code>).
2319 \par Complexity
2320 Constant (in the size of the <code>circular_buffer</code>) for scalar types; linear for other types.
2321 \sa <code>~circular_buffer()</code>, <code>erase(iterator)</code>, <code>erase(iterator, iterator)</code>,
2322 <code>rerase(iterator)</code>, <code>rerase(iterator, iterator)</code>,
2323 <code>erase_begin(size_type)</code>, <code>erase_end(size_type)</code>
2324 */
2325 void clear() BOOST_NOEXCEPT {
2326 destroy_content();
2327 m_size = 0;
2328 }
2329
2330private:
2331// Helper methods
2332
2333 //! Check if the <code>index</code> is valid.
2334 void check_position(size_type index) const {
2335 if (index >= size())
2336 throw_exception(e: std::out_of_range("circular_buffer"));
2337 }
2338
2339 //! Increment the pointer.
2340 template <class Pointer>
2341 void increment(Pointer& p) const {
2342 if (++p == m_end)
2343 p = m_buff;
2344 }
2345
2346 //! Decrement the pointer.
2347 template <class Pointer>
2348 void decrement(Pointer& p) const {
2349 if (p == m_buff)
2350 p = m_end;
2351 --p;
2352 }
2353
2354 //! Add <code>n</code> to the pointer.
2355 template <class Pointer>
2356 Pointer add(Pointer p, difference_type n) const {
2357 return p + (n < (m_end - p) ? n : n - capacity());
2358 }
2359
2360 //! Subtract <code>n</code> from the pointer.
2361 template <class Pointer>
2362 Pointer sub(Pointer p, difference_type n) const {
2363 return p - (n > (p - m_buff) ? n - capacity() : n);
2364 }
2365
2366 //! Map the null pointer to virtual end of circular buffer.
2367 pointer map_pointer(pointer p) const { return p == 0 ? m_last : p; }
2368
2369 //! Allocate memory.
2370 pointer allocate(size_type n) {
2371 if (n > max_size())
2372 throw_exception(e: std::length_error("circular_buffer"));
2373#if BOOST_CB_ENABLE_DEBUG
2374 pointer p = (n == 0) ? 0 : m_alloc.allocate(n);
2375 cb_details::do_fill_uninitialized_memory(p, sizeof(value_type) * n);
2376 return p;
2377#else
2378 return (n == 0) ? 0 : m_alloc.allocate(n);
2379#endif
2380 }
2381
2382 //! Deallocate memory.
2383 void deallocate(pointer p, size_type n) {
2384 if (p != 0)
2385 m_alloc.deallocate(p, n);
2386 }
2387
2388 //! Does the pointer point to the uninitialized memory?
2389 bool is_uninitialized(const_pointer p) const BOOST_NOEXCEPT {
2390 return p >= m_last && (m_first < m_last || p < m_first);
2391 }
2392
2393 //! Replace an element.
2394 void replace(pointer pos, param_value_type item) {
2395 *pos = item;
2396#if BOOST_CB_ENABLE_DEBUG
2397 invalidate_iterators(iterator(this, pos));
2398#endif
2399 }
2400
2401 //! Replace an element.
2402 void replace(pointer pos, rvalue_type item) {
2403 *pos = boost::move(item);
2404#if BOOST_CB_ENABLE_DEBUG
2405 invalidate_iterators(iterator(this, pos));
2406#endif
2407 }
2408
2409 //! Construct or replace an element.
2410 /*!
2411 <code>construct</code> has to be set to <code>true</code> if and only if
2412 <code>pos</code> points to an uninitialized memory.
2413 */
2414 void construct_or_replace(bool construct, pointer pos, param_value_type item) {
2415 if (construct)
2416 boost::container::allocator_traits<Alloc>::construct(m_alloc, boost::addressof(*pos), item);
2417 else
2418 replace(pos, item);
2419 }
2420
2421 //! Construct or replace an element.
2422 /*!
2423 <code>construct</code> has to be set to <code>true</code> if and only if
2424 <code>pos</code> points to an uninitialized memory.
2425 */
2426 void construct_or_replace(bool construct, pointer pos, rvalue_type item) {
2427 if (construct)
2428 boost::container::allocator_traits<Alloc>::construct(m_alloc, boost::addressof(*pos), boost::move(item));
2429 else
2430 replace(pos, boost::move(item));
2431 }
2432
2433 //! Destroy an item.
2434 void destroy_item(pointer p) {
2435 boost::container::allocator_traits<Alloc>::destroy(m_alloc, boost::addressof(*p));
2436#if BOOST_CB_ENABLE_DEBUG
2437 invalidate_iterators(iterator(this, p));
2438 cb_details::do_fill_uninitialized_memory(p, sizeof(value_type));
2439#endif
2440 }
2441
2442 //! Destroy an item only if it has been constructed.
2443 void destroy_if_constructed(pointer pos) {
2444 if (is_uninitialized(p: pos))
2445 destroy_item(p: pos);
2446 }
2447
2448 //! Destroy the whole content of the circular buffer.
2449 void destroy_content() {
2450#if BOOST_CB_ENABLE_DEBUG
2451 destroy_content(false_type());
2452#else
2453 destroy_content(is_scalar<value_type>());
2454#endif
2455 }
2456
2457 //! Specialized destroy_content method.
2458 void destroy_content(const true_type&) {
2459 m_first = add(m_first, size());
2460 }
2461
2462 //! Specialized destroy_content method.
2463 void destroy_content(const false_type&) {
2464 for (size_type ii = 0; ii < size(); ++ii, increment(m_first))
2465 destroy_item(p: m_first);
2466 }
2467
2468 //! Destroy content and free allocated memory.
2469 void destroy() BOOST_NOEXCEPT {
2470 destroy_content();
2471 deallocate(p: m_buff, n: capacity());
2472#if BOOST_CB_ENABLE_DEBUG
2473 m_buff = 0;
2474 m_first = 0;
2475 m_last = 0;
2476 m_end = 0;
2477#endif
2478 }
2479
2480 //! Initialize the internal buffer.
2481 void initialize_buffer(capacity_type buffer_capacity) {
2482 m_buff = allocate(n: buffer_capacity);
2483 m_end = m_buff + buffer_capacity;
2484 }
2485
2486 //! Initialize the internal buffer.
2487 void initialize_buffer(capacity_type buffer_capacity, param_value_type item) {
2488 initialize_buffer(buffer_capacity);
2489 BOOST_TRY {
2490 cb_details::uninitialized_fill_n_with_alloc(m_buff, size(), item, m_alloc);
2491 } BOOST_CATCH(...) {
2492 deallocate(p: m_buff, n: size());
2493 BOOST_RETHROW
2494 }
2495 BOOST_CATCH_END
2496 }
2497
2498 //! Specialized initialize method.
2499 template <class IntegralType>
2500 void initialize(IntegralType n, IntegralType item, const true_type&) {
2501 m_size = static_cast<size_type>(n);
2502 initialize_buffer(size(), item);
2503 m_first = m_last = m_buff;
2504 }
2505
2506 //! Specialized initialize method.
2507 template <class Iterator>
2508 void initialize(Iterator first, Iterator last, const false_type&) {
2509 BOOST_CB_IS_CONVERTIBLE(Iterator, value_type); // check for invalid iterator type
2510#if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x581))
2511 initialize(first, last, iterator_category<Iterator>::type());
2512#else
2513 initialize(first, last, BOOST_DEDUCED_TYPENAME iterator_category<Iterator>::type());
2514#endif
2515 }
2516
2517 //! Specialized initialize method.
2518 template <class InputIterator>
2519 void initialize(InputIterator first, InputIterator last, const std::input_iterator_tag&) {
2520 BOOST_CB_ASSERT_TEMPLATED_ITERATOR_CONSTRUCTORS // check if the STL provides templated iterator constructors
2521 // for containers
2522 std::deque<value_type, allocator_type> tmp(first, last, m_alloc);
2523 size_type distance = tmp.size();
2524 initialize(distance, boost::make_move_iterator(tmp.begin()), boost::make_move_iterator(tmp.end()), distance);
2525 }
2526
2527 //! Specialized initialize method.
2528 template <class ForwardIterator>
2529 void initialize(ForwardIterator first, ForwardIterator last, const std::forward_iterator_tag&) {
2530 BOOST_CB_ASSERT(std::distance(first, last) >= 0); // check for wrong range
2531 size_type distance = std::distance(first, last);
2532 initialize(distance, first, last, distance);
2533 }
2534
2535 //! Specialized initialize method.
2536 template <class IntegralType>
2537 void initialize(capacity_type buffer_capacity, IntegralType n, IntegralType item, const true_type&) {
2538 BOOST_CB_ASSERT(buffer_capacity >= static_cast<size_type>(n)); // check for capacity lower than n
2539 m_size = static_cast<size_type>(n);
2540 initialize_buffer(buffer_capacity, item);
2541 m_first = m_buff;
2542 m_last = buffer_capacity == size() ? m_buff : m_buff + size();
2543 }
2544
2545 //! Specialized initialize method.
2546 template <class Iterator>
2547 void initialize(capacity_type buffer_capacity, Iterator first, Iterator last, const false_type&) {
2548 BOOST_CB_IS_CONVERTIBLE(Iterator, value_type); // check for invalid iterator type
2549#if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x581))
2550 initialize(buffer_capacity, first, last, iterator_category<Iterator>::type());
2551#else
2552 initialize(buffer_capacity, first, last, BOOST_DEDUCED_TYPENAME iterator_category<Iterator>::type());
2553#endif
2554 }
2555
2556 //! Specialized initialize method.
2557 template <class InputIterator>
2558 void initialize(capacity_type buffer_capacity,
2559 InputIterator first,
2560 InputIterator last,
2561 const std::input_iterator_tag&) {
2562 initialize_buffer(buffer_capacity);
2563 m_first = m_last = m_buff;
2564 m_size = 0;
2565 if (buffer_capacity == 0)
2566 return;
2567 while (first != last && !full()) {
2568 boost::container::allocator_traits<Alloc>::construct(m_alloc, boost::addressof(*m_last), *first++);
2569 increment(m_last);
2570 ++m_size;
2571 }
2572 while (first != last) {
2573 replace(m_last, *first++);
2574 increment(m_last);
2575 m_first = m_last;
2576 }
2577 }
2578
2579 //! Specialized initialize method.
2580 template <class ForwardIterator>
2581 void initialize(capacity_type buffer_capacity,
2582 ForwardIterator first,
2583 ForwardIterator last,
2584 const std::forward_iterator_tag&) {
2585 BOOST_CB_ASSERT(std::distance(first, last) >= 0); // check for wrong range
2586 initialize(buffer_capacity, first, last, std::distance(first, last));
2587 }
2588
2589 //! Initialize the circular buffer.
2590 template <class ForwardIterator>
2591 void initialize(capacity_type buffer_capacity,
2592 ForwardIterator first,
2593 ForwardIterator last,
2594 size_type distance) {
2595 initialize_buffer(buffer_capacity);
2596 m_first = m_buff;
2597 if (distance > buffer_capacity) {
2598 std::advance(first, distance - buffer_capacity);
2599 m_size = buffer_capacity;
2600 } else {
2601 m_size = distance;
2602 }
2603 BOOST_TRY {
2604 m_last = cb_details::uninitialized_copy(first, last, m_buff, m_alloc);
2605 } BOOST_CATCH(...) {
2606 deallocate(p: m_buff, n: buffer_capacity);
2607 BOOST_RETHROW
2608 }
2609 BOOST_CATCH_END
2610 if (m_last == m_end)
2611 m_last = m_buff;
2612 }
2613
2614 //! Reset the circular buffer.
2615 void reset(pointer buff, pointer last, capacity_type new_capacity) {
2616 destroy();
2617 m_size = last - buff;
2618 m_first = m_buff = buff;
2619 m_end = m_buff + new_capacity;
2620 m_last = last == m_end ? m_buff : last;
2621 }
2622
2623 //! Specialized method for swapping the allocator.
2624 void swap_allocator(circular_buffer<T, Alloc>&, const true_type&) {
2625 // Swap is not needed because allocators have no state.
2626 }
2627
2628 //! Specialized method for swapping the allocator.
2629 void swap_allocator(circular_buffer<T, Alloc>& cb, const false_type&) {
2630 std::swap(m_alloc, cb.m_alloc);
2631 }
2632
2633 //! Specialized assign method.
2634 template <class IntegralType>
2635 void assign(IntegralType n, IntegralType item, const true_type&) {
2636 assign(static_cast<size_type>(n), static_cast<value_type>(item));
2637 }
2638
2639 //! Specialized assign method.
2640 template <class Iterator>
2641 void assign(Iterator first, Iterator last, const false_type&) {
2642 BOOST_CB_IS_CONVERTIBLE(Iterator, value_type); // check for invalid iterator type
2643#if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x581))
2644 assign(first, last, iterator_category<Iterator>::type());
2645#else
2646 assign(first, last, BOOST_DEDUCED_TYPENAME iterator_category<Iterator>::type());
2647#endif
2648 }
2649
2650 //! Specialized assign method.
2651 template <class InputIterator>
2652 void assign(InputIterator first, InputIterator last, const std::input_iterator_tag&) {
2653 BOOST_CB_ASSERT_TEMPLATED_ITERATOR_CONSTRUCTORS // check if the STL provides templated iterator constructors
2654 // for containers
2655 std::deque<value_type, allocator_type> tmp(first, last, m_alloc);
2656 size_type distance = tmp.size();
2657 assign_n(distance, distance,
2658 cb_details::make_assign_range
2659 (boost::make_move_iterator(tmp.begin()), boost::make_move_iterator(tmp.end()), m_alloc));
2660 }
2661
2662 //! Specialized assign method.
2663 template <class ForwardIterator>
2664 void assign(ForwardIterator first, ForwardIterator last, const std::forward_iterator_tag&) {
2665 BOOST_CB_ASSERT(std::distance(first, last) >= 0); // check for wrong range
2666 size_type distance = std::distance(first, last);
2667 assign_n(distance, distance, cb_details::make_assign_range(first, last, m_alloc));
2668 }
2669
2670 //! Specialized assign method.
2671 template <class IntegralType>
2672 void assign(capacity_type new_capacity, IntegralType n, IntegralType item, const true_type&) {
2673 assign(new_capacity, static_cast<size_type>(n), static_cast<value_type>(item));
2674 }
2675
2676 //! Specialized assign method.
2677 template <class Iterator>
2678 void assign(capacity_type new_capacity, Iterator first, Iterator last, const false_type&) {
2679 BOOST_CB_IS_CONVERTIBLE(Iterator, value_type); // check for invalid iterator type
2680#if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x581))
2681 assign(new_capacity, first, last, iterator_category<Iterator>::type());
2682#else
2683 assign(new_capacity, first, last, BOOST_DEDUCED_TYPENAME iterator_category<Iterator>::type());
2684#endif
2685 }
2686
2687 //! Specialized assign method.
2688 template <class InputIterator>
2689 void assign(capacity_type new_capacity, InputIterator first, InputIterator last, const std::input_iterator_tag&) {
2690 if (new_capacity == capacity()) {
2691 clear();
2692 insert(begin(), first, last);
2693 } else {
2694 circular_buffer<value_type, allocator_type> tmp(new_capacity, first, last, m_alloc);
2695 tmp.swap(*this);
2696 }
2697 }
2698
2699 //! Specialized assign method.
2700 template <class ForwardIterator>
2701 void assign(capacity_type new_capacity, ForwardIterator first, ForwardIterator last,
2702 const std::forward_iterator_tag&) {
2703 BOOST_CB_ASSERT(std::distance(first, last) >= 0); // check for wrong range
2704 size_type distance = std::distance(first, last);
2705 if (distance > new_capacity) {
2706 std::advance(first, distance - new_capacity);
2707 distance = new_capacity;
2708 }
2709 assign_n(new_capacity, distance,
2710 cb_details::make_assign_range(first, last, m_alloc));
2711 }
2712
2713 //! Helper assign method.
2714 template <class Functor>
2715 void assign_n(capacity_type new_capacity, size_type n, const Functor& fnc) {
2716 if (new_capacity == capacity()) {
2717 destroy_content();
2718 BOOST_TRY {
2719 fnc(m_buff);
2720 } BOOST_CATCH(...) {
2721 m_size = 0;
2722 BOOST_RETHROW
2723 }
2724 BOOST_CATCH_END
2725 } else {
2726 pointer buff = allocate(n: new_capacity);
2727 BOOST_TRY {
2728 fnc(buff);
2729 } BOOST_CATCH(...) {
2730 deallocate(p: buff, n: new_capacity);
2731 BOOST_RETHROW
2732 }
2733 BOOST_CATCH_END
2734 destroy();
2735 m_buff = buff;
2736 m_end = m_buff + new_capacity;
2737 }
2738 m_size = n;
2739 m_first = m_buff;
2740 m_last = add(m_buff, size());
2741 }
2742
2743 //! Helper insert method.
2744 template <class ValT>
2745 iterator insert_item(const iterator& pos, ValT item) {
2746 pointer p = pos.m_it;
2747 if (p == 0) {
2748 construct_or_replace(!full(), m_last, static_cast<ValT>(item));
2749 p = m_last;
2750 } else {
2751 pointer src = m_last;
2752 pointer dest = m_last;
2753 bool construct = !full();
2754 BOOST_TRY {
2755 while (src != p) {
2756 decrement(src);
2757 construct_or_replace(construct, dest, boost::move_if_noexcept(*src));
2758 decrement(dest);
2759 construct = false;
2760 }
2761 replace(p, static_cast<ValT>(item));
2762 } BOOST_CATCH(...) {
2763 if (!construct && !full()) {
2764 increment(m_last);
2765 ++m_size;
2766 }
2767 BOOST_RETHROW
2768 }
2769 BOOST_CATCH_END
2770 }
2771 increment(m_last);
2772 if (full())
2773 m_first = m_last;
2774 else
2775 ++m_size;
2776 return iterator(this, p);
2777 }
2778
2779 //! Specialized insert method.
2780 template <class IntegralType>
2781 void insert(const iterator& pos, IntegralType n, IntegralType item, const true_type&) {
2782 insert(pos, static_cast<size_type>(n), static_cast<value_type>(item));
2783 }
2784
2785 //! Specialized insert method.
2786 template <class Iterator>
2787 void insert(const iterator& pos, Iterator first, Iterator last, const false_type&) {
2788 BOOST_CB_IS_CONVERTIBLE(Iterator, value_type); // check for invalid iterator type
2789#if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x581))
2790 insert(pos, first, last, iterator_category<Iterator>::type());
2791#else
2792 insert(pos, first, last, BOOST_DEDUCED_TYPENAME iterator_category<Iterator>::type());
2793#endif
2794 }
2795
2796 //! Specialized insert method.
2797 template <class InputIterator>
2798 void insert(iterator pos, InputIterator first, InputIterator last, const std::input_iterator_tag&) {
2799 if (!full() || pos != begin()) {
2800 for (;first != last; ++pos)
2801 pos = insert(pos, *first++);
2802 }
2803 }
2804
2805 //! Specialized insert method.
2806 template <class ForwardIterator>
2807 void insert(const iterator& pos, ForwardIterator first, ForwardIterator last, const std::forward_iterator_tag&) {
2808 BOOST_CB_ASSERT(std::distance(first, last) >= 0); // check for wrong range
2809 size_type n = std::distance(first, last);
2810 if (n == 0)
2811 return;
2812 size_type copy = capacity() - (end() - pos);
2813 if (copy == 0)
2814 return;
2815 if (n > copy) {
2816 std::advance(first, n - copy);
2817 n = copy;
2818 }
2819 insert_n(pos, n, cb_details::iterator_wrapper<ForwardIterator>(first));
2820 }
2821
2822 //! Helper insert method.
2823 template <class Wrapper>
2824 void insert_n(const iterator& pos, size_type n, const Wrapper& wrapper) {
2825 size_type construct = reserve();
2826 if (construct > n)
2827 construct = n;
2828 if (pos.m_it == 0) {
2829 size_type ii = 0;
2830 pointer p = m_last;
2831 BOOST_TRY {
2832 for (; ii < construct; ++ii, increment(p))
2833 boost::container::allocator_traits<Alloc>::construct(m_alloc, boost::addressof(*p), *wrapper());
2834 for (;ii < n; ++ii, increment(p))
2835 replace(p, *wrapper());
2836 } BOOST_CATCH(...) {
2837 size_type constructed = (std::min)(ii, construct);
2838 m_last = add(m_last, constructed);
2839 m_size += constructed;
2840 BOOST_RETHROW
2841 }
2842 BOOST_CATCH_END
2843 } else {
2844 pointer src = m_last;
2845 pointer dest = add(m_last, n - 1);
2846 pointer p = pos.m_it;
2847 size_type ii = 0;
2848 BOOST_TRY {
2849 while (src != pos.m_it) {
2850 decrement(src);
2851 construct_or_replace(is_uninitialized(p: dest), dest, *src);
2852 decrement(dest);
2853 }
2854 for (; ii < n; ++ii, increment(p))
2855 construct_or_replace(is_uninitialized(p), p, *wrapper());
2856 } BOOST_CATCH(...) {
2857 for (p = add(m_last, n - 1); p != dest; decrement(p))
2858 destroy_if_constructed(pos: p);
2859 for (n = 0, p = pos.m_it; n < ii; ++n, increment(p))
2860 destroy_if_constructed(pos: p);
2861 BOOST_RETHROW
2862 }
2863 BOOST_CATCH_END
2864 }
2865 m_last = add(m_last, n);
2866 m_first = add(m_first, n - construct);
2867 m_size += construct;
2868 }
2869
2870 //! Specialized rinsert method.
2871 template <class IntegralType>
2872 void rinsert(const iterator& pos, IntegralType n, IntegralType item, const true_type&) {
2873 rinsert(pos, static_cast<size_type>(n), static_cast<value_type>(item));
2874 }
2875
2876 //! Specialized rinsert method.
2877 template <class Iterator>
2878 void rinsert(const iterator& pos, Iterator first, Iterator last, const false_type&) {
2879 BOOST_CB_IS_CONVERTIBLE(Iterator, value_type); // check for invalid iterator type
2880#if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x581))
2881 rinsert(pos, first, last, iterator_category<Iterator>::type());
2882#else
2883 rinsert(pos, first, last, BOOST_DEDUCED_TYPENAME iterator_category<Iterator>::type());
2884#endif
2885 }
2886
2887 //! Specialized insert method.
2888 template <class InputIterator>
2889 void rinsert(iterator pos, InputIterator first, InputIterator last, const std::input_iterator_tag&) {
2890 if (!full() || pos.m_it != 0) {
2891 for (;first != last; ++pos) {
2892 pos = rinsert(pos, *first++);
2893 if (pos.m_it == 0)
2894 break;
2895 }
2896 }
2897 }
2898
2899 //! Specialized rinsert method.
2900 template <class ForwardIterator>
2901 void rinsert(const iterator& pos, ForwardIterator first, ForwardIterator last, const std::forward_iterator_tag&) {
2902 BOOST_CB_ASSERT(std::distance(first, last) >= 0); // check for wrong range
2903 rinsert_n(pos, std::distance(first, last), cb_details::iterator_wrapper<ForwardIterator>(first));
2904 }
2905
2906 //! Helper rinsert method.
2907 template <class Wrapper>
2908 void rinsert_n(const iterator& pos, size_type n, const Wrapper& wrapper) {
2909 if (n == 0)
2910 return;
2911 iterator b = begin();
2912 size_type copy = capacity() - (pos - b);
2913 if (copy == 0)
2914 return;
2915 if (n > copy)
2916 n = copy;
2917 size_type construct = reserve();
2918 if (construct > n)
2919 construct = n;
2920 if (pos == b) {
2921 pointer p = sub(m_first, n);
2922 size_type ii = n;
2923 BOOST_TRY {
2924 for (;ii > construct; --ii, increment(p))
2925 replace(p, *wrapper());
2926 for (; ii > 0; --ii, increment(p))
2927 boost::container::allocator_traits<Alloc>::construct(m_alloc, boost::addressof(*p), *wrapper());
2928 } BOOST_CATCH(...) {
2929 size_type constructed = ii < construct ? construct - ii : 0;
2930 m_last = add(m_last, constructed);
2931 m_size += constructed;
2932 BOOST_RETHROW
2933 }
2934 BOOST_CATCH_END
2935 } else {
2936 pointer src = m_first;
2937 pointer dest = sub(m_first, n);
2938 pointer p = map_pointer(p: pos.m_it);
2939 BOOST_TRY {
2940 while (src != p) {
2941 construct_or_replace(is_uninitialized(p: dest), dest, *src);
2942 increment(src);
2943 increment(dest);
2944 }
2945 for (size_type ii = 0; ii < n; ++ii, increment(dest))
2946 construct_or_replace(is_uninitialized(p: dest), dest, *wrapper());
2947 } BOOST_CATCH(...) {
2948 for (src = sub(m_first, n); src != dest; increment(src))
2949 destroy_if_constructed(pos: src);
2950 BOOST_RETHROW
2951 }
2952 BOOST_CATCH_END
2953 }
2954 m_first = sub(m_first, n);
2955 m_last = sub(m_last, n - construct);
2956 m_size += construct;
2957 }
2958
2959 //! Specialized erase_begin method.
2960 void erase_begin(size_type n, const true_type&) {
2961 m_first = add(m_first, n);
2962 m_size -= n;
2963 }
2964
2965 //! Specialized erase_begin method.
2966 void erase_begin(size_type n, const false_type&) {
2967 iterator b = begin();
2968 rerase(b, b + n);
2969 }
2970
2971 //! Specialized erase_end method.
2972 void erase_end(size_type n, const true_type&) {
2973 m_last = sub(m_last, n);
2974 m_size -= n;
2975 }
2976
2977 //! Specialized erase_end method.
2978 void erase_end(size_type n, const false_type&) {
2979 iterator e = end();
2980 erase(e - n, e);
2981 }
2982};
2983
2984// Non-member functions
2985
2986//! Compare two <code>circular_buffer</code>s element-by-element to determine if they are equal.
2987/*!
2988 \param lhs The <code>circular_buffer</code> to compare.
2989 \param rhs The <code>circular_buffer</code> to compare.
2990 \return <code>lhs.\link circular_buffer::size() size()\endlink == rhs.\link circular_buffer::size() size()\endlink
2991 && <a href="http://www.sgi.com/tech/stl/equal.html">std::equal</a>(lhs.\link circular_buffer::begin()
2992 begin()\endlink, lhs.\link circular_buffer::end() end()\endlink,
2993 rhs.\link circular_buffer::begin() begin()\endlink)</code>
2994 \throws Nothing.
2995 \par Complexity
2996 Linear (in the size of the <code>circular_buffer</code>s).
2997 \par Iterator Invalidation
2998 Does not invalidate any iterators.
2999*/
3000template <class T, class Alloc>
3001inline bool operator == (const circular_buffer<T, Alloc>& lhs, const circular_buffer<T, Alloc>& rhs) {
3002 return lhs.size() == rhs.size() && std::equal(lhs.begin(), lhs.end(), rhs.begin());
3003}
3004
3005/*!
3006 \brief Compare two <code>circular_buffer</code>s element-by-element to determine if the left one is lesser than the
3007 right one.
3008 \param lhs The <code>circular_buffer</code> to compare.
3009 \param rhs The <code>circular_buffer</code> to compare.
3010 \return <code><a href="http://www.sgi.com/tech/stl/lexicographical_compare.html">
3011 std::lexicographical_compare</a>(lhs.\link circular_buffer::begin() begin()\endlink,
3012 lhs.\link circular_buffer::end() end()\endlink, rhs.\link circular_buffer::begin() begin()\endlink,
3013 rhs.\link circular_buffer::end() end()\endlink)</code>
3014 \throws Nothing.
3015 \par Complexity
3016 Linear (in the size of the <code>circular_buffer</code>s).
3017 \par Iterator Invalidation
3018 Does not invalidate any iterators.
3019*/
3020template <class T, class Alloc>
3021inline bool operator < (const circular_buffer<T, Alloc>& lhs, const circular_buffer<T, Alloc>& rhs) {
3022 return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
3023}
3024
3025#if !defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING) || defined(BOOST_MSVC)
3026
3027//! Compare two <code>circular_buffer</code>s element-by-element to determine if they are non-equal.
3028/*!
3029 \param lhs The <code>circular_buffer</code> to compare.
3030 \param rhs The <code>circular_buffer</code> to compare.
3031 \return <code>!(lhs == rhs)</code>
3032 \throws Nothing.
3033 \par Complexity
3034 Linear (in the size of the <code>circular_buffer</code>s).
3035 \par Iterator Invalidation
3036 Does not invalidate any iterators.
3037 \sa <code>operator==(const circular_buffer<T,Alloc>&, const circular_buffer<T,Alloc>&)</code>
3038*/
3039template <class T, class Alloc>
3040inline bool operator != (const circular_buffer<T, Alloc>& lhs, const circular_buffer<T, Alloc>& rhs) {
3041 return !(lhs == rhs);
3042}
3043
3044/*!
3045 \brief Compare two <code>circular_buffer</code>s element-by-element to determine if the left one is greater than
3046 the right one.
3047 \param lhs The <code>circular_buffer</code> to compare.
3048 \param rhs The <code>circular_buffer</code> to compare.
3049 \return <code>rhs \< lhs</code>
3050 \throws Nothing.
3051 \par Complexity
3052 Linear (in the size of the <code>circular_buffer</code>s).
3053 \par Iterator Invalidation
3054 Does not invalidate any iterators.
3055 \sa <code>operator<(const circular_buffer<T,Alloc>&, const circular_buffer<T,Alloc>&)</code>
3056*/
3057template <class T, class Alloc>
3058inline bool operator > (const circular_buffer<T, Alloc>& lhs, const circular_buffer<T, Alloc>& rhs) {
3059 return rhs < lhs;
3060}
3061
3062/*!
3063 \brief Compare two <code>circular_buffer</code>s element-by-element to determine if the left one is lesser or equal
3064 to the right one.
3065 \param lhs The <code>circular_buffer</code> to compare.
3066 \param rhs The <code>circular_buffer</code> to compare.
3067 \return <code>!(rhs \< lhs)</code>
3068 \throws Nothing.
3069 \par Complexity
3070 Linear (in the size of the <code>circular_buffer</code>s).
3071 \par Iterator Invalidation
3072 Does not invalidate any iterators.
3073 \sa <code>operator<(const circular_buffer<T,Alloc>&, const circular_buffer<T,Alloc>&)</code>
3074*/
3075template <class T, class Alloc>
3076inline bool operator <= (const circular_buffer<T, Alloc>& lhs, const circular_buffer<T, Alloc>& rhs) {
3077 return !(rhs < lhs);
3078}
3079
3080/*!
3081 \brief Compare two <code>circular_buffer</code>s element-by-element to determine if the left one is greater or
3082 equal to the right one.
3083 \param lhs The <code>circular_buffer</code> to compare.
3084 \param rhs The <code>circular_buffer</code> to compare.
3085 \return <code>!(lhs < rhs)</code>
3086 \throws Nothing.
3087 \par Complexity
3088 Linear (in the size of the <code>circular_buffer</code>s).
3089 \par Iterator Invalidation
3090 Does not invalidate any iterators.
3091 \sa <code>operator<(const circular_buffer<T,Alloc>&, const circular_buffer<T,Alloc>&)</code>
3092*/
3093template <class T, class Alloc>
3094inline bool operator >= (const circular_buffer<T, Alloc>& lhs, const circular_buffer<T, Alloc>& rhs) {
3095 return !(lhs < rhs);
3096}
3097
3098//! Swap the contents of two <code>circular_buffer</code>s.
3099/*!
3100 \post <code>lhs</code> contains elements of <code>rhs</code> and vice versa.
3101 \param lhs The <code>circular_buffer</code> whose content will be swapped with <code>rhs</code>.
3102 \param rhs The <code>circular_buffer</code> whose content will be swapped with <code>lhs</code>.
3103 \throws Nothing.
3104 \par Complexity
3105 Constant (in the size of the <code>circular_buffer</code>s).
3106 \par Iterator Invalidation
3107 Invalidates all iterators of both <code>circular_buffer</code>s. (On the other hand the iterators still
3108 point to the same elements but within another container. If you want to rely on this feature you have to
3109 turn the <a href="#debug">Debug Support</a> off otherwise an assertion will report an error if such
3110 invalidated iterator is used.)
3111 \sa <code>\link circular_buffer::swap(circular_buffer<T, Alloc>&) swap(circular_buffer<T, Alloc>&)\endlink</code>
3112*/
3113template <class T, class Alloc>
3114inline void swap(circular_buffer<T, Alloc>& lhs, circular_buffer<T, Alloc>& rhs) BOOST_NOEXCEPT {
3115 lhs.swap(rhs);
3116}
3117
3118#endif // #if !defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING) || defined(BOOST_MSVC)
3119
3120} // namespace boost
3121
3122#endif // #if !defined(BOOST_CIRCULAR_BUFFER_BASE_HPP)
3123

source code of boost/boost/circular_buffer/base.hpp