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

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