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