1 // Implementation of the circular buffer adaptor.
3 // Copyright (c) 2003-2008 Jan Gaspar
4 // Copyright (c) 2013 Paul A. Bristow // Doxygen comments changed for new version of documentation.
5 // Copyright (c) 2013 Antony Polukhin // Move semantics implementation.
7 // Use, modification, and distribution is subject to the Boost Software
8 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
9 // http://www.boost.org/LICENSE_1_0.txt)
11 #if !defined(BOOST_CIRCULAR_BUFFER_SPACE_OPTIMIZED_HPP)
12 #define BOOST_CIRCULAR_BUFFER_SPACE_OPTIMIZED_HPP
18 #include <boost/type_traits/is_same.hpp>
19 #include <boost/detail/workaround.hpp>
24 \class circular_buffer_space_optimized
25 \brief Space optimized circular buffer container adaptor.
26 <code>T</code> must be a copyable class or must have an noexcept move constructor
27 and move assignment operator.
29 template <class T, class Alloc>
30 class circular_buffer_space_optimized :
32 #if BOOST_CB_ENABLE_DEBUG
36 circular_buffer<T, Alloc> {
40 typedef typename circular_buffer<T, Alloc>::value_type value_type;
41 typedef typename circular_buffer<T, Alloc>::pointer pointer;
42 typedef typename circular_buffer<T, Alloc>::const_pointer const_pointer;
43 typedef typename circular_buffer<T, Alloc>::reference reference;
44 typedef typename circular_buffer<T, Alloc>::const_reference const_reference;
45 typedef typename circular_buffer<T, Alloc>::size_type size_type;
46 typedef typename circular_buffer<T, Alloc>::difference_type difference_type;
47 typedef typename circular_buffer<T, Alloc>::allocator_type allocator_type;
48 typedef typename circular_buffer<T, Alloc>::const_iterator const_iterator;
49 typedef typename circular_buffer<T, Alloc>::iterator iterator;
50 typedef typename circular_buffer<T, Alloc>::const_reverse_iterator const_reverse_iterator;
51 typedef typename circular_buffer<T, Alloc>::reverse_iterator reverse_iterator;
52 typedef typename circular_buffer<T, Alloc>::array_range array_range;
53 typedef typename circular_buffer<T, Alloc>::const_array_range const_array_range;
54 typedef typename circular_buffer<T, Alloc>::param_value_type param_value_type;
55 typedef typename circular_buffer<T, Alloc>::rvalue_type rvalue_type;
56 //typedef typename circular_buffer<T, Alloc>::return_value_type return_value_type;
58 /* <pre> is not passed through to html or pdf. So <br> is used in code section below. Ugly :-(
59 Ideally want a link to capacity_control, but this would require include details
60 and this would expose all the functions in details.
61 There must be a better way of doing this.
64 /*! Capacity controller of the space optimized circular buffer.
66 \see capacity_control in details.hpp.
69 class capacity_control<br>
71 size_type m_capacity; // Available capacity.<br>
72 size_type m_min_capacity; // Minimum capacity.<br>
74 capacity_control(size_type capacity, size_type min_capacity = 0)<br>
75 : m_capacity(capacity), m_min_capacity(min_capacity)<br>
77 size_type %capacity() const { return m_capacity; }<br>
78 size_type min_capacity() const { return m_min_capacity; }<br>
79 operator size_type() const { return m_capacity; }<br>
86 <code>capacity >= min_capacity</code>.
89 The <code>capacity()</code> represents the capacity
90 of the <code>circular_buffer_space_optimized</code> and
91 the <code>min_capacity()</code> determines the minimal allocated size of its internal buffer.
93 <p>The converting constructor of the <code>capacity_control</code> allows implicit conversion from
94 <code>size_type</code>-like types which ensures compatibility of creating an instance of the
95 <code>circular_buffer_space_optimized</code> with other STL containers.
97 On the other hand the operator <code>%size_type()</code>
98 provides implicit conversion to the <code>size_type</code> which allows to treat the
99 capacity of the <code>circular_buffer_space_optimized</code> the same way as in the
100 <code>circular_buffer</a></code>.
103 typedef cb_details::capacity_control<size_type> capacity_type;
107 using circular_buffer<T, Alloc>::get_allocator;
108 using circular_buffer<T, Alloc>::begin;
109 using circular_buffer<T, Alloc>::end;
110 using circular_buffer<T, Alloc>::rbegin;
111 using circular_buffer<T, Alloc>::rend;
112 using circular_buffer<T, Alloc>::at;
113 using circular_buffer<T, Alloc>::front;
114 using circular_buffer<T, Alloc>::back;
115 using circular_buffer<T, Alloc>::array_one;
116 using circular_buffer<T, Alloc>::array_two;
117 using circular_buffer<T, Alloc>::linearize;
118 using circular_buffer<T, Alloc>::is_linearized;
119 using circular_buffer<T, Alloc>::rotate;
120 using circular_buffer<T, Alloc>::size;
121 using circular_buffer<T, Alloc>::max_size;
122 using circular_buffer<T, Alloc>::empty;
124 #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564))
125 reference operator [] (size_type n) { return circular_buffer<T, Alloc>::operator[](n); }
126 const_reference operator [] (size_type n) const { return circular_buffer<T, Alloc>::operator[](n); }
128 using circular_buffer<T, Alloc>::operator[];
134 //! The capacity controller of the space optimized circular buffer.
135 capacity_type m_capacity_ctrl;
140 //! Is the <code>circular_buffer_space_optimized</code> full?
142 \return <code>true</code> if the number of elements stored in the <code>circular_buffer_space_optimized</code>
143 equals the capacity of the <code>circular_buffer_space_optimized</code>; <code>false</code> otherwise.
145 \par Exception Safety
147 \par Iterator Invalidation
148 Does not invalidate any iterators.
150 Constant (in the size of the <code>circular_buffer_space_optimized</code>).
151 \sa <code>empty()</code>
153 bool full() const BOOST_NOEXCEPT { return m_capacity_ctrl == size(); }
155 /*! \brief Get the maximum number of elements which can be inserted into the
156 <code>circular_buffer_space_optimized</code> without overwriting any of already stored elements.
157 \return <code>capacity().%capacity() - size()</code>
159 \par Exception Safety
161 \par Iterator Invalidation
162 Does not invalidate any iterators.
164 Constant (in the size of the <code>circular_buffer_space_optimized</code>).
165 \sa <code>capacity()</code>, <code>size()</code>, <code>max_size()</code>
167 size_type reserve() const BOOST_NOEXCEPT { return m_capacity_ctrl - size(); }
169 //! Get the capacity of the <code>circular_buffer_space_optimized</code>.
171 \return The capacity controller representing the maximum number of elements which can be stored in the
172 <code>circular_buffer_space_optimized</code> and the minimal allocated size of the internal buffer.
174 \par Exception Safety
176 \par Iterator Invalidation
177 Does not invalidate any iterators.
179 Constant (in the size of the <code>circular_buffer_space_optimized</code>).
180 \sa <code>reserve()</code>, <code>size()</code>, <code>max_size()</code>,
181 <code>set_capacity(const capacity_type&)</code>
183 const capacity_type& capacity() const BOOST_NOEXCEPT { return m_capacity_ctrl; }
185 #if defined(BOOST_CB_TEST)
187 // Return the current capacity of the adapted circular buffer.
189 \note This method is not intended to be used directly by the user.
190 It is defined only for testing purposes.
192 size_type internal_capacity() const BOOST_NOEXCEPT { return circular_buffer<T, Alloc>::capacity(); }
194 #endif // #if defined(BOOST_CB_TEST)
196 /*! \brief Change the capacity (and the minimal guaranteed amount of allocated memory) of the
197 <code>circular_buffer_space_optimized</code>.
198 \post <code>capacity() == capacity_ctrl \&\& size() \<= capacity_ctrl.capacity()</code><br><br>
199 If the current number of elements stored in the <code>circular_buffer_space_optimized</code> is greater
200 than the desired new capacity then number of <code>[size() - capacity_ctrl.capacity()]</code> <b>last</b>
201 elements will be removed and the new size will be equal to <code>capacity_ctrl.capacity()</code>.<br><br>
202 If the current number of elements stored in the <code>circular_buffer_space_optimized</code> is lower
203 than the new capacity then the amount of allocated memory in the internal buffer may be accommodated as
204 necessary but it will never drop below <code>capacity_ctrl.min_capacity()</code>.
205 \param capacity_ctrl The new capacity controller.
206 \throws "An allocation error" if memory is exhausted, (<code>std::bad_alloc</code> if the standard allocator is
208 Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept.
209 \par Exception Safety
211 \par Iterator Invalidation
212 Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
213 equal to <code>end()</code>).
215 Linear (in <code>min[size(), capacity_ctrl.%capacity()]</code>).
216 \note To explicitly clear the extra allocated memory use the <b>shrink-to-fit</b> technique:<br><br>
217 <code>%boost::%circular_buffer_space_optimized\<int\> cb(1000);<br>
219 %boost::%circular_buffer_space_optimized\<int\>(cb).swap(cb);</code><br><br>
220 For more information about the shrink-to-fit technique in STL see
221 <a href="http://www.gotw.ca/gotw/054.htm">http://www.gotw.ca/gotw/054.htm</a>.
222 \sa <code>rset_capacity(const capacity_type&)</code>,
223 <code>\link resize() resize(size_type, const_reference)\endlink</code>
225 void set_capacity(const capacity_type& capacity_ctrl) {
226 m_capacity_ctrl = capacity_ctrl;
227 if (capacity_ctrl < size()) {
229 circular_buffer<T, Alloc>::erase(e - (size() - capacity_ctrl), e);
231 adjust_min_capacity();
234 //! Change the size of the <code>circular_buffer_space_optimized</code>.
236 \post <code>size() == new_size \&\& capacity().%capacity() >= new_size</code><br><br>
237 If the new size is greater than the current size, copies of <code>item</code> will be inserted at the
238 <b>back</b> of the of the <code>circular_buffer_space_optimized</code> in order to achieve the desired
239 size. In the case the resulting size exceeds the current capacity the capacity will be set to
240 <code>new_size</code>.<br><br>
241 If the current number of elements stored in the <code>circular_buffer_space_optimized</code> is greater
242 than the desired new size then number of <code>[size() - new_size]</code> <b>last</b> elements will be
243 removed. (The capacity will remain unchanged.)<br><br>
244 The amount of allocated memory in the internal buffer may be accommodated as necessary.
245 \param new_size The new size.
246 \param item The element the <code>circular_buffer_space_optimized</code> will be filled with in order to gain
247 the requested size. (See the <i>Effect</i>.)
248 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
250 Whatever <code>T::T(const T&)</code> throws.
251 \par Exception Safety
253 \par Iterator Invalidation
254 Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
255 equal to <code>end()</code>).
257 Linear (in the new size of the <code>circular_buffer_space_optimized</code>).
258 \sa <code>\link rresize() rresize(size_type, const_reference)\endlink</code>,
259 <code>set_capacity(const capacity_type&)</code>
261 void resize(size_type new_size, param_value_type item = value_type()) {
262 if (new_size > size()) {
263 if (new_size > m_capacity_ctrl)
264 m_capacity_ctrl = capacity_type(new_size, m_capacity_ctrl.min_capacity());
265 insert(end(), new_size - size(), item);
268 erase(e - (size() - new_size), e);
272 /*! \brief Change the capacity (and the minimal guaranteed amount of allocated memory) of the
273 <code>circular_buffer_space_optimized</code>.
274 \post <code>capacity() == capacity_ctrl \&\& size() \<= capacity_ctrl</code><br><br>
275 If the current number of elements stored in the <code>circular_buffer_space_optimized</code> is greater
276 than the desired new capacity then number of <code>[size() - capacity_ctrl.capacity()]</code>
277 <b>first</b> elements will be removed and the new size will be equal to
278 <code>capacity_ctrl.capacity()</code>.<br><br>
279 If the current number of elements stored in the <code>circular_buffer_space_optimized</code> is lower
280 than the new capacity then the amount of allocated memory in the internal buffer may be accommodated as
281 necessary but it will never drop below <code>capacity_ctrl.min_capacity()</code>.
282 \param capacity_ctrl The new capacity controller.
283 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
285 Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept.
286 \par Exception Safety
288 \par Iterator Invalidation
289 Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
290 equal to <code>end()</code>).
292 Linear (in <code>min[size(), capacity_ctrl.%capacity()]</code>).
293 \sa <code>set_capacity(const capacity_type&)</code>,
294 <code>\link rresize() rresize(size_type, const_reference)\endlink</code>
296 void rset_capacity(const capacity_type& capacity_ctrl) {
297 m_capacity_ctrl = capacity_ctrl;
298 if (capacity_ctrl < size()) {
299 iterator b = begin();
300 circular_buffer<T, Alloc>::rerase(b, b + (size() - capacity_ctrl));
302 adjust_min_capacity();
305 //! Change the size of the <code>circular_buffer_space_optimized</code>.
307 \post <code>size() == new_size \&\& capacity().%capacity() >= new_size</code><br><br>
308 If the new size is greater than the current size, copies of <code>item</code> will be inserted at the
309 <b>front</b> of the of the <code>circular_buffer_space_optimized</code> in order to achieve the desired
310 size. In the case the resulting size exceeds the current capacity the capacity will be set to
311 <code>new_size</code>.<br><br>
312 If the current number of elements stored in the <code>circular_buffer_space_optimized</code> is greater
313 than the desired new size then number of <code>[size() - new_size]</code> <b>first</b> elements will be
314 removed. (The capacity will remain unchanged.)<br><br>
315 The amount of allocated memory in the internal buffer may be accommodated as necessary.
316 \param new_size The new size.
317 \param item The element the <code>circular_buffer_space_optimized</code> will be filled with in order to gain
318 the requested size. (See the <i>Effect</i>.)
319 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
321 Whatever <code>T::T(const T&)</code> throws.
322 \par Exception Safety
324 \par Iterator Invalidation
325 Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
326 equal to <code>end()</code>).
328 Linear (in the new size of the <code>circular_buffer_space_optimized</code>).
329 \sa <code>\link resize() resize(size_type, const_reference)\endlink</code>,
330 <code>rset_capacity(const capacity_type&)</code>
332 void rresize(size_type new_size, param_value_type item = value_type()) {
333 if (new_size > size()) {
334 if (new_size > m_capacity_ctrl)
335 m_capacity_ctrl = capacity_type(new_size, m_capacity_ctrl.min_capacity());
336 rinsert(begin(), new_size - size(), item);
338 rerase(begin(), end() - new_size);
342 //! Create an empty space optimized circular buffer with zero capacity.
344 \post <code>capacity().%capacity() == 0 \&\& capacity().min_capacity() == 0 \&\& size() == 0</code>
345 \param alloc The allocator.
349 \warning Since Boost version 1.36 the behaviour of this constructor has changed. Now it creates a space
350 optimized circular buffer with zero capacity.
352 explicit circular_buffer_space_optimized(const allocator_type& alloc = allocator_type()) BOOST_NOEXCEPT
353 : circular_buffer<T, Alloc>(0, alloc)
354 , m_capacity_ctrl(0) {}
356 //! Create an empty space optimized circular buffer with the specified capacity.
358 \post <code>capacity() == capacity_ctrl \&\& size() == 0</code><br><br>
359 The amount of allocated memory in the internal buffer is <code>capacity_ctrl.min_capacity()</code>.
360 \param capacity_ctrl The capacity controller representing the maximum number of elements which can be stored in
361 the <code>circular_buffer_space_optimized</code> and the minimal allocated size of the
363 \param alloc The allocator.
364 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
369 explicit circular_buffer_space_optimized(capacity_type capacity_ctrl,
370 const allocator_type& alloc = allocator_type())
371 : circular_buffer<T, Alloc>(capacity_ctrl.min_capacity(), alloc)
372 , m_capacity_ctrl(capacity_ctrl) {}
374 /*! \brief Create a full space optimized circular buffer with the specified capacity filled with
375 <code>capacity_ctrl.%capacity()</code> copies of <code>item</code>.
376 \post <code>capacity() == capacity_ctrl \&\& full() \&\& (*this)[0] == item \&\& (*this)[1] == item \&\& ...
377 \&\& (*this) [capacity_ctrl.%capacity() - 1] == item </code><br><br>
378 The amount of allocated memory in the internal buffer is <code>capacity_ctrl.capacity()</code>.
379 \param capacity_ctrl The capacity controller representing the maximum number of elements which can be stored in
380 the <code>circular_buffer_space_optimized</code> and the minimal allocated size of the
382 \param item The element the created <code>circular_buffer_space_optimized</code> will be filled with.
383 \param alloc The allocator.
384 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
386 \throws Whatever <code>T::T(const T&)</code> throws.
388 Linear (in the <code>capacity_ctrl.%capacity()</code>).
390 circular_buffer_space_optimized(capacity_type capacity_ctrl, param_value_type item,
391 const allocator_type& alloc = allocator_type())
392 : circular_buffer<T, Alloc>(capacity_ctrl.capacity(), item, alloc)
393 , m_capacity_ctrl(capacity_ctrl) {}
395 /*! \brief Create a space optimized circular buffer with the specified capacity filled with <code>n</code> copies
396 of <code>item</code>.
397 \pre <code>capacity_ctrl.%capacity() >= n</code>
398 \post <code>capacity() == capacity_ctrl \&\& size() == n \&\& (*this)[0] == item \&\& (*this)[1] == item
399 \&\& ... \&\& (*this)[n - 1] == item</code><br><br>
400 The amount of allocated memory in the internal buffer is
401 <code>max[n, capacity_ctrl.min_capacity()]</code>.
402 \param capacity_ctrl The capacity controller representing the maximum number of elements which can be stored in
403 the <code>circular_buffer_space_optimized</code> and the minimal allocated size of the
405 \param n The number of elements the created <code>circular_buffer_space_optimized</code> will be filled with.
406 \param item The element the created <code>circular_buffer_space_optimized</code> will be filled with.
407 \param alloc The allocator.
408 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
410 Whatever <code>T::T(const T&)</code> throws.
412 Linear (in the <code>n</code>).
414 circular_buffer_space_optimized(capacity_type capacity_ctrl, size_type n, param_value_type item,
415 const allocator_type& alloc = allocator_type())
416 : circular_buffer<T, Alloc>(init_capacity(capacity_ctrl, n), n, item, alloc)
417 , m_capacity_ctrl(capacity_ctrl) {}
419 //! The copy constructor.
421 Creates a copy of the specified <code>circular_buffer_space_optimized</code>.
422 \post <code>*this == cb</code><br><br>
423 The amount of allocated memory in the internal buffer is <code>cb.size()</code>.
424 \param cb The <code>circular_buffer_space_optimized</code> to be copied.
425 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
427 Whatever <code>T::T(const T&)</code> throws.
429 Linear (in the size of <code>cb</code>).
431 circular_buffer_space_optimized(const circular_buffer_space_optimized<T, Alloc>& cb)
432 : circular_buffer<T, Alloc>(cb.begin(), cb.end(), cb.get_allocator())
433 , m_capacity_ctrl(cb.m_capacity_ctrl) {}
435 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
436 //! The move constructor.
437 /*! \brief Move constructs a <code>circular_buffer_space_optimized</code> from <code>cb</code>,
438 leaving <code>cb</code> empty.
439 \pre C++ compiler with rvalue references support.
440 \post <code>cb.empty()</code>
441 \param cb <code>circular_buffer</code> to 'steal' value from.
445 circular_buffer_space_optimized(circular_buffer_space_optimized<T, Alloc>&& cb) BOOST_NOEXCEPT
446 : circular_buffer<T, Alloc>()
447 , m_capacity_ctrl(0) {
450 #endif // BOOST_NO_CXX11_RVALUE_REFERENCES
452 //! Create a full space optimized circular buffer filled with a copy of the range.
454 \pre Valid range <code>[first, last)</code>.<br>
455 <code>first</code> and <code>last</code> have to meet the requirements of
456 <a href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>.
457 \post <code>capacity().%capacity() == std::distance(first, last) \&\& capacity().min_capacity() == 0 \&\&
458 full() \&\& (*this)[0]== *first \&\& (*this)[1] == *(first + 1) \&\& ... \&\&
459 (*this)[std::distance(first, last) - 1] == *(last - 1)</code><br><br>
460 The amount of allocated memory in the internal buffer is <code>std::distance(first, last)</code>.
461 \param first The beginning of the range to be copied.
462 \param last The end of the range to be copied.
463 \param alloc The allocator.
464 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
466 Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept
467 and <code>InputIterator</code> is a move iterator.
469 Linear (in the <code>std::distance(first, last)</code>).
471 template <class InputIterator>
472 circular_buffer_space_optimized(InputIterator first, InputIterator last,
473 const allocator_type& alloc = allocator_type())
474 : circular_buffer<T, Alloc>(first, last, alloc)
475 , m_capacity_ctrl(circular_buffer<T, Alloc>::capacity()) {}
477 /*! \brief Create a space optimized circular buffer with the specified capacity (and the minimal guaranteed amount
478 of allocated memory) filled with a copy of the range.
479 \pre Valid range <code>[first, last)</code>.<br>
480 <code>first</code> and <code>last</code> have to meet the requirements of
481 <a href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>.
482 \post <code>capacity() == capacity_ctrl \&\& size() \<= std::distance(first, last) \&\& (*this)[0]==
483 *(last - capacity_ctrl.%capacity()) \&\& (*this)[1] == *(last - capacity_ctrl.%capacity() + 1) \&\& ...
484 \&\& (*this)[capacity_ctrl.%capacity() - 1] == *(last - 1)</code><br><br>
485 If the number of items to be copied from the range <code>[first, last)</code> is greater than the
486 specified <code>capacity_ctrl.%capacity()</code> then only elements from the range
487 <code>[last - capacity_ctrl.%capacity(), last)</code> will be copied.<br><br>
488 The amount of allocated memory in the internal buffer is <code>max[capacity_ctrl.min_capacity(),
489 min[capacity_ctrl.%capacity(), std::distance(first, last)]]</code>.
490 \param capacity_ctrl The capacity controller representing the maximum number of elements which can be stored in
491 the <code>circular_buffer_space_optimized</code> and the minimal allocated size of the
493 \param first The beginning of the range to be copied.
494 \param last The end of the range to be copied.
495 \param alloc The allocator.
496 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
498 Whatever <code>T::T(const T&)</code> throws.
500 Linear (in <code>std::distance(first, last)</code>; in
501 <code>min[capacity_ctrl.%capacity(), std::distance(first, last)]</code> if the <code>InputIterator</code>
502 is a <a href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">RandomAccessIterator</a>).
504 template <class InputIterator>
505 circular_buffer_space_optimized(capacity_type capacity_ctrl, InputIterator first, InputIterator last,
506 const allocator_type& alloc = allocator_type())
507 : circular_buffer<T, Alloc>(
508 init_capacity(capacity_ctrl, first, last, is_integral<InputIterator>()),
510 , m_capacity_ctrl(capacity_ctrl) {
512 is_same< BOOST_DEDUCED_TYPENAME iterator_category<InputIterator>::type, std::input_iterator_tag >());
515 #if defined(BOOST_CB_NEVER_DEFINED)
516 // This section will never be compiled - the default destructor will be generated instead.
517 // Declared only for documentation purpose.
521 Destroys the <code>circular_buffer_space_optimized</code>.
523 \par Iterator Invalidation
524 Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (including
525 iterators equal to <code>end()</code>).
527 Linear (in the size of the <code>circular_buffer_space_optimized</code>).
528 \sa <code>clear()</code>
530 ~circular_buffer_space_optimized();
533 void erase_begin(size_type n);
536 void erase_end(size_type n);
538 #endif // #if defined(BOOST_CB_NEVER_DEFINED)
540 //! The assign operator.
542 Makes this <code>circular_buffer_space_optimized</code> to become a copy of the specified
543 <code>circular_buffer_space_optimized</code>.
544 \post <code>*this == cb</code><br><br>
545 The amount of allocated memory in the internal buffer is <code>cb.size()</code>.
546 \param cb The <code>circular_buffer_space_optimized</code> to be copied.
547 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
549 \throws Whatever <code>T::T(const T&)</code> throws.
550 \par Exception Safety
552 \par Iterator Invalidation
553 Invalidates all iterators pointing to this <code>circular_buffer_space_optimized</code> (except iterators
554 equal to <code>end()</code>).
556 Linear (in the size of <code>cb</code>).
557 \sa <code>\link assign(size_type, param_value_type) assign(size_type, const_reference)\endlink</code>,
558 <code>\link assign(capacity_type, size_type, param_value_type)
559 assign(capacity_type, size_type, const_reference)\endlink</code>,
560 <code>assign(InputIterator, InputIterator)</code>,
561 <code>assign(capacity_type, InputIterator, InputIterator)</code>
563 circular_buffer_space_optimized<T, Alloc>& operator = (const circular_buffer_space_optimized<T, Alloc>& cb) {
566 circular_buffer<T, Alloc>::assign(cb.begin(), cb.end());
567 m_capacity_ctrl = cb.m_capacity_ctrl;
571 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
572 /*! \brief Move assigns content of <code>cb</code> to <code>*this</code>, leaving <code>cb</code> empty.
573 \pre C++ compiler with rvalue references support.
574 \post <code>cb.empty()</code>
575 \param cb <code>circular_buffer</code> to 'steal' value from.
580 circular_buffer_space_optimized<T, Alloc>& operator = (circular_buffer_space_optimized<T, Alloc>&& cb) BOOST_NOEXCEPT {
581 cb.swap(*this); // now `this` holds `cb`
582 circular_buffer<T, Alloc>(get_allocator()) // temprary that holds initial `cb` allocator
583 .swap(cb); // makes `cb` empty
586 #endif // BOOST_NO_CXX11_RVALUE_REFERENCES
589 //! Assign <code>n</code> items into the space optimized circular buffer.
591 The content of the <code>circular_buffer_space_optimized</code> will be removed and replaced with
592 <code>n</code> copies of the <code>item</code>.
593 \post <code>capacity().%capacity() == n \&\& capacity().min_capacity() == 0 \&\& size() == n \&\& (*this)[0] ==
594 item \&\& (*this)[1] == item \&\& ... \&\& (*this) [n - 1] == item</code><br><br>
595 The amount of allocated memory in the internal buffer is <code>n</code>.
596 \param n The number of elements the <code>circular_buffer_space_optimized</code> will be filled with.
597 \param item The element the <code>circular_buffer_space_optimized</code> will be filled with.
598 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
600 Whatever <code>T::T(const T&)</code> throws.
601 \par Exception Safety
603 \par Iterator Invalidation
604 Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
605 equal to <code>end()</code>).
607 Linear (in the <code>n</code>).
608 \sa <code>\link operator=(const circular_buffer_space_optimized&) operator=\endlink</code>,
609 <code>\link assign(capacity_type, size_type, param_value_type)
610 assign(capacity_type, size_type, const_reference)\endlink</code>,
611 <code>assign(InputIterator, InputIterator)</code>,
612 <code>assign(capacity_type, InputIterator, InputIterator)</code>
614 void assign(size_type n, param_value_type item) {
615 circular_buffer<T, Alloc>::assign(n, item);
616 m_capacity_ctrl = capacity_type(n);
619 //! Assign <code>n</code> items into the space optimized circular buffer specifying the capacity.
621 The capacity of the <code>circular_buffer_space_optimized</code> will be set to the specified value and the
622 content of the <code>circular_buffer_space_optimized</code> will be removed and replaced with <code>n</code>
623 copies of the <code>item</code>.
624 \pre <code>capacity_ctrl.%capacity() >= n</code>
625 \post <code>capacity() == capacity_ctrl \&\& size() == n \&\& (*this)[0] == item \&\& (*this)[1] == item
626 \&\& ... \&\& (*this) [n - 1] == item </code><br><br>
627 The amount of allocated memory will be <code>max[n, capacity_ctrl.min_capacity()]</code>.
628 \param capacity_ctrl The new capacity controller.
629 \param n The number of elements the <code>circular_buffer_space_optimized</code> will be filled with.
630 \param item The element the <code>circular_buffer_space_optimized</code> will be filled with.
631 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
633 Whatever <code>T::T(const T&)</code> throws.
634 \par Exception Safety
636 \par Iterator Invalidation
637 Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
638 equal to <code>end()</code>).
640 Linear (in the <code>n</code>).
641 \sa <code>\link operator=(const circular_buffer_space_optimized&) operator=\endlink</code>,
642 <code>\link assign(size_type, param_value_type) assign(size_type, const_reference)\endlink</code>,
643 <code>assign(InputIterator, InputIterator)</code>,
644 <code>assign(capacity_type, InputIterator, InputIterator)</code>
646 void assign(capacity_type capacity_ctrl, size_type n, param_value_type item) {
647 BOOST_CB_ASSERT(capacity_ctrl.capacity() >= n); // check for new capacity lower than n
648 circular_buffer<T, Alloc>::assign((std::max)(capacity_ctrl.min_capacity(), n), n, item);
649 m_capacity_ctrl = capacity_ctrl;
652 //! Assign a copy of the range into the space optimized circular buffer.
654 The content of the <code>circular_buffer_space_optimized</code> will be removed and replaced with copies of
655 elements from the specified range.
656 \pre Valid range <code>[first, last)</code>.<br>
657 <code>first</code> and <code>last</code> have to meet the requirements of
658 <a href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>.
659 \post <code>capacity().%capacity() == std::distance(first, last) \&\& capacity().min_capacity() == 0 \&\&
660 size() == std::distance(first, last) \&\& (*this)[0]== *first \&\& (*this)[1] == *(first + 1) \&\& ...
661 \&\& (*this)[std::distance(first, last) - 1] == *(last - 1)</code><br><br>
662 The amount of allocated memory in the internal buffer is <code>std::distance(first, last)</code>.
663 \param first The beginning of the range to be copied.
664 \param last The end of the range to be copied.
665 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
667 Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept and
668 <code>InputIterator</code> is a move iterator.
669 \par Exception Safety
671 \par Iterator Invalidation
672 Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
673 equal to <code>end()</code>).
675 Linear (in the <code>std::distance(first, last)</code>).
676 \sa <code>\link operator=(const circular_buffer_space_optimized&) operator=\endlink</code>,
677 <code>\link assign(size_type, param_value_type) assign(size_type, const_reference)\endlink</code>,
678 <code>\link assign(capacity_type, size_type, param_value_type)
679 assign(capacity_type, size_type, const_reference)\endlink</code>,
680 <code>assign(capacity_type, InputIterator, InputIterator)</code>
682 template <class InputIterator>
683 void assign(InputIterator first, InputIterator last) {
684 circular_buffer<T, Alloc>::assign(first, last);
685 m_capacity_ctrl = capacity_type(circular_buffer<T, Alloc>::capacity());
688 //! Assign a copy of the range into the space optimized circular buffer specifying the capacity.
690 The capacity of the <code>circular_buffer_space_optimized</code> will be set to the specified value and the
691 content of the <code>circular_buffer_space_optimized</code> will be removed and replaced with copies of
692 elements from the specified range.
693 \pre Valid range <code>[first, last)</code>.<br>
694 <code>first</code> and <code>last</code> have to meet the requirements of
695 <a href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>.
696 \post <code>capacity() == capacity_ctrl \&\& size() \<= std::distance(first, last) \&\&
697 (*this)[0]== *(last - capacity) \&\& (*this)[1] == *(last - capacity + 1) \&\& ... \&\&
698 (*this)[capacity - 1] == *(last - 1)</code><br><br>
699 If the number of items to be copied from the range <code>[first, last)</code> is greater than the
700 specified <code>capacity</code> then only elements from the range <code>[last - capacity, last)</code>
701 will be copied.<br><br> The amount of allocated memory in the internal buffer is
702 <code>max[std::distance(first, last), capacity_ctrl.min_capacity()]</code>.
703 \param capacity_ctrl The new capacity controller.
704 \param first The beginning of the range to be copied.
705 \param last The end of the range to be copied.
706 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
708 Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept and
709 <code>InputIterator</code> is a move iterator.
710 \par Exception Safety
712 \par Iterator Invalidation
713 Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
714 equal to <code>end()</code>).
716 Linear (in <code>std::distance(first, last)</code>; in
717 <code>min[capacity_ctrl.%capacity(), std::distance(first, last)]</code> if the <code>InputIterator</code>
718 is a <a href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">RandomAccessIterator</a>).
719 \sa <code>\link operator=(const circular_buffer_space_optimized&) operator=\endlink</code>,
720 <code>\link assign(size_type, param_value_type) assign(size_type, const_reference)\endlink</code>,
721 <code>\link assign(capacity_type, size_type, param_value_type)
722 assign(capacity_type, size_type, const_reference)\endlink</code>,
723 <code>assign(InputIterator, InputIterator)</code>
725 template <class InputIterator>
726 void assign(capacity_type capacity_ctrl, InputIterator first, InputIterator last) {
727 m_capacity_ctrl = capacity_ctrl;
728 circular_buffer<T, Alloc>::assign(capacity_ctrl, first, last);
731 //! Swap the contents of two space-optimized circular-buffers.
733 \post <code>this</code> contains elements of <code>cb</code> and vice versa; the capacity and the amount of
734 allocated memory in the internal buffer of <code>this</code> equal to the capacity and the amount of
735 allocated memory of <code>cb</code> and vice versa.
736 \param cb The <code>circular_buffer_space_optimized</code> whose content will be swapped.
738 \par Exception Safety
740 \par Iterator Invalidation
741 Invalidates all iterators of both <code>circular_buffer_space_optimized</code> containers. (On the other
742 hand the iterators still point to the same elements but within another container. If you want to rely on
743 this feature you have to turn the __debug_support off,
744 otherwise an assertion will report an error if such invalidated iterator is used.)
746 Constant (in the size of the <code>circular_buffer_space_optimized</code>).
747 \sa <code>swap(circular_buffer<T, Alloc>&, circular_buffer<T, Alloc>&)</code>,
748 <code>swap(circular_buffer_space_optimized<T, Alloc>&, circular_buffer_space_optimized<T, Alloc>&)</code>
752 // Note link does not work right. Asked on Doxygen forum for advice 23 May 2103.
754 void swap(circular_buffer_space_optimized<T, Alloc>& cb) BOOST_NOEXCEPT {
755 std::swap(m_capacity_ctrl, cb.m_capacity_ctrl);
756 circular_buffer<T, Alloc>::swap(cb);
759 //! Insert a new element at the end of the space optimized circular buffer.
761 \post if <code>capacity().%capacity() > 0</code> then <code>back() == item</code><br>
762 If the <code>circular_buffer_space_optimized</code> is full, the first element will be removed. If the
763 capacity is <code>0</code>, nothing will be inserted.<br><br>
764 The amount of allocated memory in the internal buffer may be predictively increased.
765 \param item The element to be inserted.
766 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
768 Whatever <code>T::T(const T&)</code> throws.
769 \par Exception Safety
771 \par Iterator Invalidation
772 Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
773 equal to <code>end()</code>).
775 Linear (in the size of the <code>circular_buffer_space_optimized</code>).
776 \sa <code>\link push_front() push_front(const_reference)\endlink</code>, <code>pop_back()</code>,
777 <code>pop_front()</code>
779 void push_back(param_value_type item) {
780 check_low_capacity();
781 circular_buffer<T, Alloc>::push_back(item);
784 //! Insert a new element at the end of the space optimized circular buffer.
786 \post if <code>capacity().%capacity() > 0</code> then <code>back() == item</code><br>
787 If the <code>circular_buffer_space_optimized</code> is full, the first element will be removed. If the
788 capacity is <code>0</code>, nothing will be inserted.<br><br>
789 The amount of allocated memory in the internal buffer may be predictively increased.
790 \param item The element to be inserted.
791 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
793 \par Exception Safety
795 \par Iterator Invalidation
796 Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
797 equal to <code>end()</code>).
799 Linear (in the size of the <code>circular_buffer_space_optimized</code>).
800 \sa <code>\link push_front() push_front(const_reference)\endlink</code>, <code>pop_back()</code>,
801 <code>pop_front()</code>
803 void push_back(rvalue_type item) {
804 check_low_capacity();
805 circular_buffer<T, Alloc>::push_back(boost::move(item));
808 //! Insert a new element at the end of the space optimized circular buffer.
810 \post if <code>capacity().%capacity() > 0</code> then <code>back() == item</code><br>
811 If the <code>circular_buffer_space_optimized</code> is full, the first element will be removed. If the
812 capacity is <code>0</code>, nothing will be inserted.<br><br>
813 The amount of allocated memory in the internal buffer may be predictively increased.
814 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
816 Whatever <code>T::T()</code> throws.
817 Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept.
818 \par Exception Safety
820 \par Iterator Invalidation
821 Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
822 equal to <code>end()</code>).
824 Linear (in the size of the <code>circular_buffer_space_optimized</code>).
825 \sa <code>\link push_front() push_front(const_reference)\endlink</code>, <code>pop_back()</code>,
826 <code>pop_front()</code>
829 check_low_capacity();
830 circular_buffer<T, Alloc>::push_back();
833 //! Insert a new element at the beginning of the space optimized circular buffer.
835 \post if <code>capacity().%capacity() > 0</code> then <code>front() == item</code><br>
836 If the <code>circular_buffer_space_optimized</code> is full, the last element will be removed. If the
837 capacity is <code>0</code>, nothing will be inserted.<br><br>
838 The amount of allocated memory in the internal buffer may be predictively increased.
839 \param item The element to be inserted.
840 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
842 Whatever <code>T::T(const T&)</code> throws.
843 \par Exception Safety
845 \par Iterator Invalidation
846 Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
847 equal to <code>end()</code>).
849 Linear (in the size of the <code>circular_buffer_space_optimized</code>).
850 \sa <code>\link push_back() push_back(const_reference)\endlink</code>, <code>pop_back()</code>,
851 <code>pop_front()</code>
853 void push_front(param_value_type item) {
854 check_low_capacity();
855 circular_buffer<T, Alloc>::push_front(item);
858 //! Insert a new element at the beginning of the space optimized circular buffer.
860 \post if <code>capacity().%capacity() > 0</code> then <code>front() == item</code><br>
861 If the <code>circular_buffer_space_optimized</code> is full, the last element will be removed. If the
862 capacity is <code>0</code>, nothing will be inserted.<br><br>
863 The amount of allocated memory in the internal buffer may be predictively increased.
864 \param item The element to be inserted.
865 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
867 Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept.
868 \par Exception Safety
870 \par Iterator Invalidation
871 Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
872 equal to <code>end()</code>).
874 Linear (in the size of the <code>circular_buffer_space_optimized</code>).
875 \sa <code>\link push_back() push_back(const_reference)\endlink</code>, <code>pop_back()</code>,
876 <code>pop_front()</code>
878 void push_front(rvalue_type item) {
879 check_low_capacity();
880 circular_buffer<T, Alloc>::push_front(boost::move(item));
883 //! Insert a new element at the beginning of the space optimized circular buffer.
885 \post if <code>capacity().%capacity() > 0</code> then <code>front() == item</code><br>
886 If the <code>circular_buffer_space_optimized</code> is full, the last element will be removed. If the
887 capacity is <code>0</code>, nothing will be inserted.<br><br>
888 The amount of allocated memory in the internal buffer may be predictively increased.
889 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
891 Whatever <code>T::T()</code> throws.
892 Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept.
893 \par Exception Safety
895 \par Iterator Invalidation
896 Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
897 equal to <code>end()</code>).
899 Linear (in the size of the <code>circular_buffer_space_optimized</code>).
900 \sa <code>\link push_back() push_back(const_reference)\endlink</code>, <code>pop_back()</code>,
901 <code>pop_front()</code>
904 check_low_capacity();
905 circular_buffer<T, Alloc>::push_front();
908 //! Remove the last element from the space optimized circular buffer.
910 \pre <code>!empty()</code>
911 \post The last element is removed from the <code>circular_buffer_space_optimized</code>.<br><br>
912 The amount of allocated memory in the internal buffer may be predictively decreased.
913 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
915 \par Exception Safety
917 \par Iterator Invalidation
918 Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
919 equal to <code>end()</code>).
921 Linear (in the size of the <code>circular_buffer_space_optimized</code>).
922 \sa <code>pop_front()</code>, <code>\link push_back() push_back(const_reference)\endlink</code>,
923 <code>\link push_front() push_front(const_reference)\endlink</code>
926 circular_buffer<T, Alloc>::pop_back();
927 check_high_capacity();
930 //! Remove the first element from the space optimized circular buffer.
932 \pre <code>!empty()</code>
933 \post The first element is removed from the <code>circular_buffer_space_optimized</code>.<br><br>
934 The amount of allocated memory in the internal buffer may be predictively decreased.
935 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
937 \par Exception Safety
939 \par Iterator Invalidation
940 Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
941 equal to <code>end()</code>).
943 Linear (in the size of the <code>circular_buffer_space_optimized</code>).
944 \sa <code>pop_back()</code>, <code>\link push_back() push_back(const_reference)\endlink</code>,
945 <code>\link push_front() push_front(const_reference)\endlink</code>
948 circular_buffer<T, Alloc>::pop_front();
949 check_high_capacity();
952 //! Insert an element at the specified position.
954 \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer_space_optimized</code> or its
956 \post The <code>item</code> will be inserted at the position <code>pos</code>.<br>
957 If the <code>circular_buffer_space_optimized</code> is full, the first element will be overwritten. If
958 the <code>circular_buffer_space_optimized</code> is full and the <code>pos</code> points to
959 <code>begin()</code>, then the <code>item</code> will not be inserted. If the capacity is <code>0</code>,
960 nothing will be inserted.<br><br>
961 The amount of allocated memory in the internal buffer may be predictively increased.
962 \param pos An iterator specifying the position where the <code>item</code> will be inserted.
963 \param item The element to be inserted.
964 \return Iterator to the inserted element or <code>begin()</code> if the <code>item</code> is not inserted. (See
966 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
968 Whatever <code>T::T(const T&)</code> throws.
969 Whatever <code>T::operator = (const T&)</code> throws.
970 \par Exception Safety
972 \par Iterator Invalidation
973 Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
974 equal to <code>end()</code>).
976 Linear (in the size of the <code>circular_buffer_space_optimized</code>).
977 \sa <code>\link insert(iterator, size_type, param_value_type)
978 insert(iterator, size_type, value_type)\endlink</code>,
979 <code>insert(iterator, InputIterator, InputIterator)</code>,
980 <code>\link rinsert(iterator, param_value_type) rinsert(iterator, value_type)\endlink</code>,
981 <code>\link rinsert(iterator, size_type, param_value_type)
982 rinsert(iterator, size_type, value_type)\endlink</code>,
983 <code>rinsert(iterator, InputIterator, InputIterator)</code>
985 iterator insert(iterator pos, param_value_type item) {
986 size_type index = pos - begin();
987 check_low_capacity();
988 return circular_buffer<T, Alloc>::insert(begin() + index, item);
991 //! Insert an element at the specified position.
993 \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer_space_optimized</code> or its
995 \post The <code>item</code> will be inserted at the position <code>pos</code>.<br>
996 If the <code>circular_buffer_space_optimized</code> is full, the first element will be overwritten. If
997 the <code>circular_buffer_space_optimized</code> is full and the <code>pos</code> points to
998 <code>begin()</code>, then the <code>item</code> will not be inserted. If the capacity is <code>0</code>,
999 nothing will be inserted.<br><br>
1000 The amount of allocated memory in the internal buffer may be predictively increased.
1001 \param pos An iterator specifying the position where the <code>item</code> will be inserted.
1002 \param item The element to be inserted.
1003 \return Iterator to the inserted element or <code>begin()</code> if the <code>item</code> is not inserted. (See
1005 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
1007 Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept.
1008 \par Exception Safety
1010 \par Iterator Invalidation
1011 Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
1012 equal to <code>end()</code>).
1014 Linear (in the size of the <code>circular_buffer_space_optimized</code>).
1015 \sa <code>\link insert(iterator, size_type, param_value_type)
1016 insert(iterator, size_type, value_type)\endlink</code>,
1017 <code>insert(iterator, InputIterator, InputIterator)</code>,
1018 <code>\link rinsert(iterator, param_value_type) rinsert(iterator, value_type)\endlink</code>,
1019 <code>\link rinsert(iterator, size_type, param_value_type)
1020 rinsert(iterator, size_type, value_type)\endlink</code>,
1021 <code>rinsert(iterator, InputIterator, InputIterator)</code>
1023 iterator insert(iterator pos, rvalue_type item) {
1024 size_type index = pos - begin();
1025 check_low_capacity();
1026 return circular_buffer<T, Alloc>::insert(begin() + index, boost::move(item));
1029 //! Insert an element at the specified position.
1031 \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer_space_optimized</code> or its
1033 \post The <code>item</code> will be inserted at the position <code>pos</code>.<br>
1034 If the <code>circular_buffer_space_optimized</code> is full, the first element will be overwritten. If
1035 the <code>circular_buffer_space_optimized</code> is full and the <code>pos</code> points to
1036 <code>begin()</code>, then the <code>item</code> will not be inserted. If the capacity is <code>0</code>,
1037 nothing will be inserted.<br><br>
1038 The amount of allocated memory in the internal buffer may be predictively increased.
1039 \param pos An iterator specifying the position where the <code>item</code> will be inserted.
1040 \return Iterator to the inserted element or <code>begin()</code> if the <code>item</code> is not inserted. (See
1042 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
1044 Whatever <code>T::T()</code> throws.
1045 Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept.
1046 \par Exception Safety
1048 \par Iterator Invalidation
1049 Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
1050 equal to <code>end()</code>).
1052 Linear (in the size of the <code>circular_buffer_space_optimized</code>).
1053 \sa <code>\link insert(iterator, size_type, param_value_type)
1054 insert(iterator, size_type, value_type)\endlink</code>,
1055 <code>insert(iterator, InputIterator, InputIterator)</code>,
1056 <code>\link rinsert(iterator, param_value_type) rinsert(iterator, value_type)\endlink</code>,
1057 <code>\link rinsert(iterator, size_type, param_value_type)
1058 rinsert(iterator, size_type, value_type)\endlink</code>,
1059 <code>rinsert(iterator, InputIterator, InputIterator)</code>
1061 iterator insert(iterator pos) {
1062 size_type index = pos - begin();
1063 check_low_capacity();
1064 return circular_buffer<T, Alloc>::insert(begin() + index);
1067 //! Insert <code>n</code> copies of the <code>item</code> at the specified position.
1069 \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer_space_optimized</code> or its
1071 \post The number of <code>min[n, (pos - begin()) + reserve()]</code> elements will be inserted at the position
1072 <code>pos</code>.<br>The number of <code>min[pos - begin(), max[0, n - reserve()]]</code> elements will
1073 be overwritten at the beginning of the <code>circular_buffer_space_optimized</code>.<br>(See
1074 <i>Example</i> for the explanation.)<br><br>
1075 The amount of allocated memory in the internal buffer may be predictively increased.
1076 \param pos An iterator specifying the position where the <code>item</code>s will be inserted.
1077 \param n The number of <code>item</code>s the to be inserted.
1078 \param item The element whose copies will be inserted.
1079 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
1081 Whatever <code>T::T(const T&)</code> throws.
1082 Whatever <code>T::operator = (const T&)</code> throws.
1083 \par Exception Safety
1085 \par Iterator Invalidation
1086 Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
1087 equal to <code>end()</code>).
1089 Linear (in <code>min[capacity().%capacity(), size() + n]</code>).
1091 Consider a <code>circular_buffer_space_optimized</code> with the capacity of 6 and the size of 4. Its
1092 internal buffer may look like the one below.<br><br>
1093 <code>|1|2|3|4| | |</code><br>
1094 <code>p ___^</code><br><br>After inserting 5 elements at the position <code>p</code>:<br><br>
1095 <code>insert(p, (size_t)5, 0);</code><br><br>actually only 4 elements get inserted and elements
1096 <code>1</code> and <code>2</code> are overwritten. This is due to the fact the insert operation preserves
1097 the capacity. After insertion the internal buffer looks like this:<br><br><code>|0|0|0|0|3|4|</code><br>
1098 <br>For comparison if the capacity would not be preserved the internal buffer would then result in
1099 <code>|1|2|0|0|0|0|0|3|4|</code>.
1100 \sa <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>,
1101 <code>insert(iterator, InputIterator, InputIterator)</code>,
1102 <code>\link rinsert(iterator, param_value_type) rinsert(iterator, value_type)\endlink</code>,
1103 <code>\link rinsert(iterator, size_type, param_value_type)
1104 rinsert(iterator, size_type, value_type)\endlink</code>,
1105 <code>rinsert(iterator, InputIterator, InputIterator)</code>
1107 void insert(iterator pos, size_type n, param_value_type item) {
1108 size_type index = pos - begin();
1109 check_low_capacity(n);
1110 circular_buffer<T, Alloc>::insert(begin() + index, n, item);
1113 //! Insert the range <code>[first, last)</code> at the specified position.
1115 \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer_space_optimized</code> or its
1116 end.<br>Valid range <code>[first, last)</code> where <code>first</code> and <code>last</code> meet the
1117 requirements of an <a href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>.
1118 \post Elements from the range
1119 <code>[first + max[0, distance(first, last) - (pos - begin()) - reserve()], last)</code> will be
1120 inserted at the position <code>pos</code>.<br>The number of <code>min[pos - begin(), max[0,
1121 distance(first, last) - reserve()]]</code> elements will be overwritten at the beginning of the
1122 <code>circular_buffer_space_optimized</code>.<br>(See <i>Example</i> for the explanation.)<br><br>
1123 The amount of allocated memory in the internal buffer may be predictively increased.
1124 \param pos An iterator specifying the position where the range will be inserted.
1125 \param first The beginning of the range to be inserted.
1126 \param last The end of the range to be inserted.
1127 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
1129 Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept.
1130 \par Exception Safety
1132 \par Iterator Invalidation
1133 Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
1134 equal to <code>end()</code>).
1136 Linear (in <code>[size() + std::distance(first, last)]</code>; in
1137 <code>min[capacity().%capacity(), size() + std::distance(first, last)]</code> if the
1138 <code>InputIterator</code> is a
1139 <a href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">RandomAccessIterator</a>).
1141 Consider a <code>circular_buffer_space_optimized</code> with the capacity of 6 and the size of 4. Its
1142 internal buffer may look like the one below.<br><br>
1143 <code>|1|2|3|4| | |</code><br>
1144 <code>p ___^</code><br><br>After inserting a range of elements at the position <code>p</code>:<br><br>
1145 <code>int array[] = { 5, 6, 7, 8, 9 };</code><br><code>insert(p, array, array + 5);</code><br><br>
1146 actually only elements <code>6</code>, <code>7</code>, <code>8</code> and <code>9</code> from the
1147 specified range get inserted and elements <code>1</code> and <code>2</code> are overwritten. This is due
1148 to the fact the insert operation preserves the capacity. After insertion the internal buffer looks like
1149 this:<br><br><code>|6|7|8|9|3|4|</code><br><br>For comparison if the capacity would not be preserved the
1150 internal buffer would then result in <code>|1|2|5|6|7|8|9|3|4|</code>.
1151 \sa <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>,
1152 <code>\link insert(iterator, size_type, param_value_type)
1153 insert(iterator, size_type, value_type)\endlink</code>, <code>\link rinsert(iterator, param_value_type)
1154 rinsert(iterator, value_type)\endlink</code>, <code>\link rinsert(iterator, size_type, param_value_type)
1155 rinsert(iterator, size_type, value_type)\endlink</code>,
1156 <code>rinsert(iterator, InputIterator, InputIterator)</code>
1158 template <class InputIterator>
1159 void insert(iterator pos, InputIterator first, InputIterator last) {
1160 insert(pos, first, last, is_integral<InputIterator>());
1163 //! Insert an element before the specified position.
1165 \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer_space_optimized</code> or its
1167 \post The <code>item</code> will be inserted before the position <code>pos</code>.<br>
1168 If the <code>circular_buffer_space_optimized</code> is full, the last element will be overwritten. If the
1169 <code>circular_buffer_space_optimized</code> is full and the <code>pos</code> points to
1170 <code>end()</code>, then the <code>item</code> will not be inserted. If the capacity is <code>0</code>,
1171 nothing will be inserted.<br><br>
1172 The amount of allocated memory in the internal buffer may be predictively increased.
1173 \param pos An iterator specifying the position before which the <code>item</code> will be inserted.
1174 \param item The element to be inserted.
1175 \return Iterator to the inserted element or <code>end()</code> if the <code>item</code> is not inserted. (See
1177 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
1179 Whatever <code>T::T(const T&)</code> throws.
1180 Whatever <code>T::operator = (const T&)</code> throws.
1181 \par Exception Safety
1183 \par Iterator Invalidation
1184 Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
1185 equal to <code>end()</code>).
1187 Linear (in the size of the <code>circular_buffer_space_optimized</code>).
1188 \sa <code>\link rinsert(iterator, size_type, param_value_type)
1189 rinsert(iterator, size_type, value_type)\endlink</code>,
1190 <code>rinsert(iterator, InputIterator, InputIterator)</code>,
1191 <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>,
1192 <code>\link insert(iterator, size_type, param_value_type)
1193 insert(iterator, size_type, value_type)\endlink</code>,
1194 <code>insert(iterator, InputIterator, InputIterator)</code>
1196 iterator rinsert(iterator pos, param_value_type item) {
1197 size_type index = pos - begin();
1198 check_low_capacity();
1199 return circular_buffer<T, Alloc>::rinsert(begin() + index, item);
1202 //! Insert an element before the specified position.
1204 \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer_space_optimized</code> or its
1206 \post The <code>item</code> will be inserted before the position <code>pos</code>.<br>
1207 If the <code>circular_buffer_space_optimized</code> is full, the last element will be overwritten. If the
1208 <code>circular_buffer_space_optimized</code> is full and the <code>pos</code> points to
1209 <code>end()</code>, then the <code>item</code> will not be inserted. If the capacity is <code>0</code>,
1210 nothing will be inserted.<br><br>
1211 The amount of allocated memory in the internal buffer may be predictively increased.
1212 \param pos An iterator specifying the position before which the <code>item</code> will be inserted.
1213 \param item The element to be inserted.
1214 \return Iterator to the inserted element or <code>end()</code> if the <code>item</code> is not inserted. (See
1216 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
1218 Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept.
1219 \par Exception Safety
1221 \par Iterator Invalidation
1222 Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
1223 equal to <code>end()</code>).
1225 Linear (in the size of the <code>circular_buffer_space_optimized</code>).
1226 \sa <code>\link rinsert(iterator, size_type, param_value_type)
1227 rinsert(iterator, size_type, value_type)\endlink</code>,
1228 <code>rinsert(iterator, InputIterator, InputIterator)</code>,
1229 <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>,
1230 <code>\link insert(iterator, size_type, param_value_type)
1231 insert(iterator, size_type, value_type)\endlink</code>,
1232 <code>insert(iterator, InputIterator, InputIterator)</code>
1234 iterator rinsert(iterator pos, rvalue_type item) {
1235 size_type index = pos - begin();
1236 check_low_capacity();
1237 return circular_buffer<T, Alloc>::rinsert(begin() + index, boost::move(item));
1240 //! Insert an element before the specified position.
1242 \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer_space_optimized</code> or its
1244 \post The <code>item</code> will be inserted before the position <code>pos</code>.<br>
1245 If the <code>circular_buffer_space_optimized</code> is full, the last element will be overwritten. If the
1246 <code>circular_buffer_space_optimized</code> is full and the <code>pos</code> points to
1247 <code>end()</code>, then the <code>item</code> will not be inserted. If the capacity is <code>0</code>,
1248 nothing will be inserted.<br><br>
1249 The amount of allocated memory in the internal buffer may be predictively increased.
1250 \param pos An iterator specifying the position before which the <code>item</code> will be inserted.
1251 \return Iterator to the inserted element or <code>end()</code> if the <code>item</code> is not inserted. (See
1253 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
1255 Whatever <code>T::T()</code> throws.
1256 Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept.
1257 \par Exception Safety
1259 \par Iterator Invalidation
1260 Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
1261 equal to <code>end()</code>).
1263 Linear (in the size of the <code>circular_buffer_space_optimized</code>).
1264 \sa <code>\link rinsert(iterator, size_type, param_value_type)
1265 rinsert(iterator, size_type, value_type)\endlink</code>,
1266 <code>rinsert(iterator, InputIterator, InputIterator)</code>,
1267 <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>,
1268 <code>\link insert(iterator, size_type, param_value_type)
1269 insert(iterator, size_type, value_type)\endlink</code>,
1270 <code>insert(iterator, InputIterator, InputIterator)</code>
1272 iterator rinsert(iterator pos) {
1273 size_type index = pos - begin();
1274 check_low_capacity();
1275 return circular_buffer<T, Alloc>::rinsert(begin() + index);
1278 //! Insert <code>n</code> copies of the <code>item</code> before the specified position.
1280 \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer_space_optimized</code> or its
1282 \post The number of <code>min[n, (end() - pos) + reserve()]</code> elements will be inserted before the
1283 position <code>pos</code>.<br>The number of <code>min[end() - pos, max[0, n - reserve()]]</code> elements
1284 will be overwritten at the end of the <code>circular_buffer_space_optimized</code>.<br>(See
1285 <i>Example</i> for the explanation.)<br><br>
1286 The amount of allocated memory in the internal buffer may be predictively increased.
1287 \param pos An iterator specifying the position where the <code>item</code>s will be inserted.
1288 \param n The number of <code>item</code>s the to be inserted.
1289 \param item The element whose copies will be inserted.
1290 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
1292 Whatever <code>T::T(const T&)</code> throws.
1293 Whatever <code>T::operator = (const T&)</code> throws.
1294 \par Exception Safety
1296 \par Iterator Invalidation
1297 Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
1298 equal to <code>end()</code>).
1300 Linear (in <code>min[capacity().%capacity(), size() + n]</code>).
1302 Consider a <code>circular_buffer_space_optimized</code> with the capacity of 6 and the size of 4. Its
1303 internal buffer may look like the one below.<br><br>
1304 <code>|1|2|3|4| | |</code><br>
1305 <code>p ___^</code><br><br>After inserting 5 elements before the position <code>p</code>:<br><br>
1306 <code>rinsert(p, (size_t)5, 0);</code><br><br>actually only 4 elements get inserted and elements
1307 <code>3</code> and <code>4</code> are overwritten. This is due to the fact the rinsert operation preserves
1308 the capacity. After insertion the internal buffer looks like this:<br><br><code>|1|2|0|0|0|0|</code><br>
1309 <br>For comparison if the capacity would not be preserved the internal buffer would then result in
1310 <code>|1|2|0|0|0|0|0|3|4|</code>.
1311 \sa <code>\link rinsert(iterator, param_value_type) rinsert(iterator, value_type)\endlink</code>,
1312 <code>rinsert(iterator, InputIterator, InputIterator)</code>,
1313 <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>,
1314 <code>\link insert(iterator, size_type, param_value_type)
1315 insert(iterator, size_type, value_type)\endlink</code>,
1316 <code>insert(iterator, InputIterator, InputIterator)</code>
1318 void rinsert(iterator pos, size_type n, param_value_type item) {
1319 size_type index = pos - begin();
1320 check_low_capacity(n);
1321 circular_buffer<T, Alloc>::rinsert(begin() + index, n, item);
1324 //! Insert the range <code>[first, last)</code> before the specified position.
1326 \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer_space_optimized</code> or its
1328 Valid range <code>[first, last)</code> where <code>first</code> and <code>last</code> meet the
1329 requirements of an <a href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>.
1330 \post Elements from the range
1331 <code>[first, last - max[0, distance(first, last) - (end() - pos) - reserve()])</code> will be inserted
1332 before the position <code>pos</code>.<br>The number of <code>min[end() - pos, max[0,
1333 distance(first, last) - reserve()]]</code> elements will be overwritten at the end of the
1334 <code>circular_buffer</code>.<br>(See <i>Example</i> for the explanation.)<br><br>
1335 The amount of allocated memory in the internal buffer may be predictively increased.
1336 \param pos An iterator specifying the position where the range will be inserted.
1337 \param first The beginning of the range to be inserted.
1338 \param last The end of the range to be inserted.
1339 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
1341 Whatever <code>T::T(const T&)</code> throws.
1342 Whatever <code>T::operator = (const T&)</code> throws.
1343 \par Exception Safety
1345 \par Iterator Invalidation
1346 Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
1347 equal to <code>end()</code>).
1349 Linear (in <code>[size() + std::distance(first, last)]</code>; in
1350 <code>min[capacity().%capacity(), size() + std::distance(first, last)]</code> if the
1351 <code>InputIterator</code> is a
1352 <a href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">RandomAccessIterator</a>).
1354 Consider a <code>circular_buffer_space_optimized</code> with the capacity of 6 and the size of 4. Its
1355 internal buffer may look like the one below.<br><br>
1356 <code>|1|2|3|4| | |</code><br>
1357 <code>p ___^</code><br><br>After inserting a range of elements before the position <code>p</code>:<br><br>
1358 <code>int array[] = { 5, 6, 7, 8, 9 };</code><br><code>insert(p, array, array + 5);</code><br><br>
1359 actually only elements <code>5</code>, <code>6</code>, <code>7</code> and <code>8</code> from the
1360 specified range get inserted and elements <code>3</code> and <code>4</code> are overwritten. This is due
1361 to the fact the rinsert operation preserves the capacity. After insertion the internal buffer looks like
1362 this:<br><br><code>|1|2|5|6|7|8|</code><br><br>For comparison if the capacity would not be preserved the
1363 internal buffer would then result in <code>|1|2|5|6|7|8|9|3|4|</code>.
1364 \sa <code>\link rinsert(iterator, param_value_type) rinsert(iterator, value_type)\endlink</code>,
1365 <code>\link rinsert(iterator, size_type, param_value_type)
1366 rinsert(iterator, size_type, value_type)\endlink</code>, <code>\link insert(iterator, param_value_type)
1367 insert(iterator, value_type)\endlink</code>, <code>\link insert(iterator, size_type, param_value_type)
1368 insert(iterator, size_type, value_type)\endlink</code>,
1369 <code>insert(iterator, InputIterator, InputIterator)</code>
1371 template <class InputIterator>
1372 void rinsert(iterator pos, InputIterator first, InputIterator last) {
1373 rinsert(pos, first, last, is_integral<InputIterator>());
1376 //! Remove an element at the specified position.
1378 \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer_space_optimized</code> (but not
1379 an <code>end()</code>).
1380 \post The element at the position <code>pos</code> is removed.<br><br>
1381 The amount of allocated memory in the internal buffer may be predictively decreased.
1382 \param pos An iterator pointing at the element to be removed.
1383 \return Iterator to the first element remaining beyond the removed element or <code>end()</code> if no such
1385 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
1387 Whatever <code>T::operator = (const T&)</code> throws or
1388 nothing if <code>T::operator = (T&&)</code> is noexcept.
1389 \par Exception Safety
1391 \par Iterator Invalidation
1392 Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
1393 equal to <code>end()</code>).
1395 Linear (in the size of the <code>circular_buffer_space_optimized</code>).
1396 \sa <code>erase(iterator, iterator)</code>, <code>rerase(iterator)</code>,
1397 <code>rerase(iterator, iterator)</code>, <code>clear()</code>
1399 iterator erase(iterator pos) {
1400 iterator it = circular_buffer<T, Alloc>::erase(pos);
1401 size_type index = it - begin();
1402 check_high_capacity();
1403 return begin() + index;
1406 //! Erase the range <code>[first, last)</code>.
1408 \pre Valid range <code>[first, last)</code>.
1409 \post The elements from the range <code>[first, last)</code> are removed. (If <code>first == last</code>
1410 nothing is removed.)<br><br>
1411 The amount of allocated memory in the internal buffer may be predictively decreased.
1412 \param first The beginning of the range to be removed.
1413 \param last The end of the range to be removed.
1414 \return Iterator to the first element remaining beyond the removed elements or <code>end()</code> if no such
1416 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
1418 Whatever <code>T::operator = (const T&)</code> throws or
1419 nothing if <code>T::operator = (T&&)</code> is noexcept.
1420 \par Exception Safety
1422 \par Iterator Invalidation
1423 Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
1424 equal to <code>end()</code>).
1426 Linear (in the size of the <code>circular_buffer_space_optimized</code>).
1427 \sa <code>erase(iterator)</code>, <code>rerase(iterator)</code>, <code>rerase(iterator, iterator)</code>,
1428 <code>clear()</code>
1430 iterator erase(iterator first, iterator last) {
1431 iterator it = circular_buffer<T, Alloc>::erase(first, last);
1432 size_type index = it - begin();
1433 check_high_capacity();
1434 return begin() + index;
1437 //! Remove an element at the specified position.
1439 \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer_space_optimized</code> (but not
1440 an <code>end()</code>).<br><br>
1441 The amount of allocated memory in the internal buffer may be predictively decreased.
1442 \post The element at the position <code>pos</code> is removed.
1443 \param pos An iterator pointing at the element to be removed.
1444 \return Iterator to the first element remaining in front of the removed element or <code>begin()</code> if no
1445 such element exists.
1446 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
1448 Whatever <code>T::operator = (const T&)</code> throws or
1449 nothing if <code>T::operator = (T&&)</code> is noexcept.
1450 \par Exception Safety
1452 \par Iterator Invalidation
1453 Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
1454 equal to <code>end()</code>).
1456 Linear (in the size of the <code>circular_buffer_space_optimized</code>).
1457 \note Basically there is no difference between <code>erase(iterator)</code> and this method. It is implemented
1458 only for consistency with the base <code>circular_buffer</code>.
1459 \sa <code>erase(iterator)</code>, <code>erase(iterator, iterator)</code>,
1460 <code>rerase(iterator, iterator)</code>, <code>clear()</code>
1462 iterator rerase(iterator pos) {
1463 iterator it = circular_buffer<T, Alloc>::rerase(pos);
1464 size_type index = it - begin();
1465 check_high_capacity();
1466 return begin() + index;
1469 //! Erase the range <code>[first, last)</code>.
1471 \pre Valid range <code>[first, last)</code>.
1472 \post The elements from the range <code>[first, last)</code> are removed. (If <code>first == last</code>
1473 nothing is removed.)<br><br>
1474 The amount of allocated memory in the internal buffer may be predictively decreased.
1475 \param first The beginning of the range to be removed.
1476 \param last The end of the range to be removed.
1477 \return Iterator to the first element remaining in front of the removed elements or <code>begin()</code> if no
1478 such element exists.
1479 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
1481 Whatever <code>T::operator = (const T&)</code> throws or
1482 nothing if <code>T::operator = (T&&)</code> is noexcept.
1483 \par Exception Safety
1485 \par Iterator Invalidation
1486 Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
1487 equal to <code>end()</code>).
1489 Linear (in the size of the <code>circular_buffer_space_optimized</code>).
1490 \note Basically there is no difference between <code>erase(iterator, iterator)</code> and this method. It is
1491 implemented only for consistency with the base
1492 <code><circular_buffer</code>.
1493 \sa <code>erase(iterator)</code>, <code>erase(iterator, iterator)</code>, <code>rerase(iterator)</code>,
1494 <code>clear()</code>
1496 iterator rerase(iterator first, iterator last) {
1497 iterator it = circular_buffer<T, Alloc>::rerase(first, last);
1498 size_type index = it - begin();
1499 check_high_capacity();
1500 return begin() + index;
1503 //! Remove all stored elements from the space optimized circular buffer.
1505 \post <code>size() == 0</code><br><br>
1506 The amount of allocated memory in the internal buffer may be predictively decreased.
1507 \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is
1509 \par Exception Safety
1511 \par Iterator Invalidation
1512 Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators
1513 equal to <code>end()</code>).
1515 Linear (in the size of the <code>circular_buffer_space_optimized</code>).
1516 \sa <code>~circular_buffer_space_optimized()</code>, <code>erase(iterator)</code>,
1517 <code>erase(iterator, iterator)</code>, <code>rerase(iterator)</code>,
1518 <code>rerase(iterator, iterator)</code>
1520 void clear() { erase(begin(), end()); }
1525 //! Adjust the amount of allocated memory.
1526 void adjust_min_capacity() {
1527 if (m_capacity_ctrl.min_capacity() > circular_buffer<T, Alloc>::capacity())
1528 circular_buffer<T, Alloc>::set_capacity(m_capacity_ctrl.min_capacity());
1530 check_high_capacity();
1533 //! Ensure the reserve for possible growth up.
1534 size_type ensure_reserve(size_type new_capacity, size_type buffer_size) const {
1535 if (buffer_size + new_capacity / 5 >= new_capacity)
1536 new_capacity *= 2; // ensure at least 20% reserve
1537 if (new_capacity > m_capacity_ctrl)
1538 return m_capacity_ctrl;
1539 return new_capacity;
1542 //! Check for low capacity.
1544 \post If the capacity is low it will be increased.
1546 void check_low_capacity(size_type n = 1) {
1547 size_type new_size = size() + n;
1548 size_type new_capacity = circular_buffer<T, Alloc>::capacity();
1549 if (new_size > new_capacity) {
1550 if (new_capacity == 0)
1552 for (; new_size > new_capacity; new_capacity *= 2) {}
1553 circular_buffer<T, Alloc>::set_capacity(
1554 ensure_reserve(new_capacity, new_size));
1556 #if BOOST_CB_ENABLE_DEBUG
1557 this->invalidate_iterators_except(end());
1561 //! Check for high capacity.
1563 \post If the capacity is high it will be decreased.
1565 void check_high_capacity() {
1566 size_type new_capacity = circular_buffer<T, Alloc>::capacity();
1567 while (new_capacity / 3 >= size()) { // (new_capacity / 3) -> avoid oscillations
1569 if (new_capacity <= m_capacity_ctrl.min_capacity()) {
1570 new_capacity = m_capacity_ctrl.min_capacity();
1574 circular_buffer<T, Alloc>::set_capacity(
1575 ensure_reserve(new_capacity, size()));
1576 #if BOOST_CB_ENABLE_DEBUG
1577 this->invalidate_iterators_except(end());
1581 //! Specialized method for reducing the capacity.
1582 void reduce_capacity(const true_type&) {
1583 circular_buffer<T, Alloc>::set_capacity((std::max)(m_capacity_ctrl.min_capacity(), size()));
1586 //! Specialized method for reducing the capacity.
1587 void reduce_capacity(const false_type&) {}
1589 //! Determine the initial capacity.
1590 static size_type init_capacity(const capacity_type& capacity_ctrl, size_type n) {
1591 BOOST_CB_ASSERT(capacity_ctrl.capacity() >= n); // check for capacity lower than n
1592 return (std::max)(capacity_ctrl.min_capacity(), n);
1595 //! Specialized method for determining the initial capacity.
1596 template <class IntegralType>
1597 static size_type init_capacity(const capacity_type& capacity_ctrl, IntegralType n, IntegralType,
1599 return init_capacity(capacity_ctrl, static_cast<size_type>(n));
1602 //! Specialized method for determining the initial capacity.
1603 template <class Iterator>
1604 static size_type init_capacity(const capacity_type& capacity_ctrl, Iterator first, Iterator last,
1605 const false_type&) {
1606 BOOST_CB_IS_CONVERTIBLE(Iterator, value_type); // check for invalid iterator type
1607 #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x581))
1608 return init_capacity(capacity_ctrl, first, last, iterator_category<Iterator>::type());
1610 return init_capacity(
1611 capacity_ctrl, first, last, BOOST_DEDUCED_TYPENAME iterator_category<Iterator>::type());
1615 //! Specialized method for determining the initial capacity.
1616 template <class InputIterator>
1617 static size_type init_capacity(const capacity_type& capacity_ctrl, InputIterator, InputIterator,
1618 const std::input_iterator_tag&) {
1619 return capacity_ctrl.capacity();
1622 //! Specialized method for determining the initial capacity.
1623 template <class ForwardIterator>
1624 static size_type init_capacity(const capacity_type& capacity_ctrl, ForwardIterator first, ForwardIterator last,
1625 const std::forward_iterator_tag&) {
1626 BOOST_CB_ASSERT(std::distance(first, last) >= 0); // check for wrong range
1627 return (std::max)(capacity_ctrl.min_capacity(),
1628 (std::min)(capacity_ctrl.capacity(), static_cast<size_type>(std::distance(first, last))));
1631 //! Specialized insert method.
1632 template <class IntegralType>
1633 void insert(const iterator& pos, IntegralType n, IntegralType item, const true_type&) {
1634 insert(pos, static_cast<size_type>(n), static_cast<value_type>(item));
1637 //! Specialized insert method.
1638 template <class Iterator>
1639 void insert(const iterator& pos, Iterator first, Iterator last, const false_type&) {
1640 size_type index = pos - begin();
1641 check_low_capacity(std::distance(first, last));
1642 circular_buffer<T, Alloc>::insert(begin() + index, first, last);
1645 //! Specialized rinsert method.
1646 template <class IntegralType>
1647 void rinsert(const iterator& pos, IntegralType n, IntegralType item, const true_type&) {
1648 rinsert(pos, static_cast<size_type>(n), static_cast<value_type>(item));
1651 //! Specialized rinsert method.
1652 template <class Iterator>
1653 void rinsert(const iterator& pos, Iterator first, Iterator last, const false_type&) {
1654 size_type index = pos - begin();
1655 check_low_capacity(std::distance(first, last));
1656 circular_buffer<T, Alloc>::rinsert(begin() + index, first, last);
1660 // Non-member functions
1662 //! Test two space optimized circular buffers for equality.
1663 template <class T, class Alloc>
1664 inline bool operator == (const circular_buffer_space_optimized<T, Alloc>& lhs,
1665 const circular_buffer_space_optimized<T, Alloc>& rhs) {
1666 return lhs.size() == rhs.size() &&
1667 std::equal(lhs.begin(), lhs.end(), rhs.begin());
1670 //! Lexicographical comparison.
1671 template <class T, class Alloc>
1672 inline bool operator < (const circular_buffer_space_optimized<T, Alloc>& lhs,
1673 const circular_buffer_space_optimized<T, Alloc>& rhs) {
1674 return std::lexicographical_compare(
1675 lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
1678 #if !defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING) || BOOST_WORKAROUND(BOOST_MSVC, BOOST_TESTED_AT(1310))
1680 //! Test two space optimized circular buffers for non-equality.
1681 template <class T, class Alloc>
1682 inline bool operator != (const circular_buffer_space_optimized<T, Alloc>& lhs,
1683 const circular_buffer_space_optimized<T, Alloc>& rhs) {
1684 return !(lhs == rhs);
1687 //! Lexicographical comparison.
1688 template <class T, class Alloc>
1689 inline bool operator > (const circular_buffer_space_optimized<T, Alloc>& lhs,
1690 const circular_buffer_space_optimized<T, Alloc>& rhs) {
1694 //! Lexicographical comparison.
1695 template <class T, class Alloc>
1696 inline bool operator <= (const circular_buffer_space_optimized<T, Alloc>& lhs,
1697 const circular_buffer_space_optimized<T, Alloc>& rhs) {
1698 return !(rhs < lhs);
1701 //! Lexicographical comparison.
1702 template <class T, class Alloc>
1703 inline bool operator >= (const circular_buffer_space_optimized<T, Alloc>& lhs,
1704 const circular_buffer_space_optimized<T, Alloc>& rhs) {
1705 return !(lhs < rhs);
1708 //! Swap the contents of two space optimized circular buffers.
1709 template <class T, class Alloc>
1710 inline void swap(circular_buffer_space_optimized<T, Alloc>& lhs,
1711 circular_buffer_space_optimized<T, Alloc>& rhs) BOOST_NOEXCEPT {
1715 #endif // #if !defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING) || BOOST_WORKAROUND(BOOST_MSVC, BOOST_TESTED_AT(1310))
1717 } // namespace boost
1719 #endif // #if !defined(BOOST_CIRCULAR_BUFFER_SPACE_OPTIMIZED_HPP)