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