]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Implementation of the circular buffer adaptor. |
2 | ||
3 | // Copyright (c) 2003-2008 Jan Gaspar | |
4 | // Copyright (c) 2013 Paul A. Bristow // Doxygen comments changed for new version of documentation. | |
5 | // Copyright (c) 2013 Antony Polukhin // Move semantics implementation. | |
6 | ||
7 | // Use, modification, and distribution is subject to the Boost Software | |
8 | // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
9 | // http://www.boost.org/LICENSE_1_0.txt) | |
10 | ||
11 | #if !defined(BOOST_CIRCULAR_BUFFER_SPACE_OPTIMIZED_HPP) | |
12 | #define BOOST_CIRCULAR_BUFFER_SPACE_OPTIMIZED_HPP | |
13 | ||
14 | #if defined(_MSC_VER) | |
15 | #pragma once | |
16 | #endif | |
17 | ||
18 | #include <boost/type_traits/is_same.hpp> | |
19 | #include <boost/detail/workaround.hpp> | |
20 | ||
21 | namespace boost { | |
22 | ||
23 | /*! | |
24 | \class circular_buffer_space_optimized | |
25 | \brief Space optimized circular buffer container adaptor. | |
26 | <code>T</code> must be a copyable class or must have an noexcept move constructor | |
27 | and move assignment operator. | |
28 | */ | |
29 | template <class T, class Alloc> | |
30 | class circular_buffer_space_optimized : | |
31 | /*! \cond */ | |
32 | #if BOOST_CB_ENABLE_DEBUG | |
33 | public | |
34 | #endif | |
35 | /*! \endcond */ | |
36 | circular_buffer<T, Alloc> { | |
37 | public: | |
38 | // Typedefs | |
39 | ||
40 | typedef typename circular_buffer<T, Alloc>::value_type value_type; | |
41 | typedef typename circular_buffer<T, Alloc>::pointer pointer; | |
42 | typedef typename circular_buffer<T, Alloc>::const_pointer const_pointer; | |
43 | typedef typename circular_buffer<T, Alloc>::reference reference; | |
44 | typedef typename circular_buffer<T, Alloc>::const_reference const_reference; | |
45 | typedef typename circular_buffer<T, Alloc>::size_type size_type; | |
46 | typedef typename circular_buffer<T, Alloc>::difference_type difference_type; | |
47 | typedef typename circular_buffer<T, Alloc>::allocator_type allocator_type; | |
48 | typedef typename circular_buffer<T, Alloc>::const_iterator const_iterator; | |
49 | typedef typename circular_buffer<T, Alloc>::iterator iterator; | |
50 | typedef typename circular_buffer<T, Alloc>::const_reverse_iterator const_reverse_iterator; | |
51 | typedef typename circular_buffer<T, Alloc>::reverse_iterator reverse_iterator; | |
52 | typedef typename circular_buffer<T, Alloc>::array_range array_range; | |
53 | typedef typename circular_buffer<T, Alloc>::const_array_range const_array_range; | |
54 | typedef typename circular_buffer<T, Alloc>::param_value_type param_value_type; | |
55 | typedef typename circular_buffer<T, Alloc>::rvalue_type rvalue_type; | |
56 | //typedef typename circular_buffer<T, Alloc>::return_value_type return_value_type; | |
57 | ||
58 | /* <pre> is not passed through to html or pdf. So <br> is used in code section below. Ugly :-( | |
59 | Ideally want a link to capacity_control, but this would require include details | |
60 | and this would expose all the functions in details. | |
61 | There must be a better way of doing this. | |
62 | */ | |
63 | ||
64 | /*! Capacity controller of the space optimized circular buffer. | |
65 | ||
66 | \see capacity_control in details.hpp. | |
67 | <p> | |
68 | <code> | |
69 | class capacity_control<br> | |
70 | {<br> | |
71 | size_type m_capacity; // Available capacity.<br> | |
72 | size_type m_min_capacity; // Minimum capacity.<br> | |
73 | public:<br> | |
74 | capacity_control(size_type capacity, size_type min_capacity = 0)<br> | |
75 | : m_capacity(capacity), m_min_capacity(min_capacity)<br> | |
76 | {};<br> | |
77 | size_type %capacity() const { return m_capacity; }<br> | |
78 | size_type min_capacity() const { return m_min_capacity; }<br> | |
79 | operator size_type() const { return m_capacity; }<br> | |
80 | };<br> | |
81 | </code> | |
82 | </p> | |
83 | ||
84 | ||
85 | <p>Always | |
86 | <code>capacity >= min_capacity</code>. | |
87 | </p> | |
88 | <p> | |
89 | The <code>capacity()</code> represents the capacity | |
90 | of the <code>circular_buffer_space_optimized</code> and | |
91 | the <code>min_capacity()</code> determines the minimal allocated size of its internal buffer. | |
92 | </p> | |
93 | <p>The converting constructor of the <code>capacity_control</code> allows implicit conversion from | |
94 | <code>size_type</code>-like types which ensures compatibility of creating an instance of the | |
95 | <code>circular_buffer_space_optimized</code> with other STL containers. | |
96 | ||
97 | On the other hand the operator <code>%size_type()</code> | |
98 | provides implicit conversion to the <code>size_type</code> which allows to treat the | |
99 | capacity of the <code>circular_buffer_space_optimized</code> the same way as in the | |
100 | <code>circular_buffer</a></code>. | |
101 | </p> | |
102 | */ | |
103 | typedef cb_details::capacity_control<size_type> capacity_type; | |
104 | ||
105 | // Inherited | |
106 | ||
107 | using circular_buffer<T, Alloc>::get_allocator; | |
108 | using circular_buffer<T, Alloc>::begin; | |
109 | using circular_buffer<T, Alloc>::end; | |
110 | using circular_buffer<T, Alloc>::rbegin; | |
111 | using circular_buffer<T, Alloc>::rend; | |
112 | using circular_buffer<T, Alloc>::at; | |
113 | using circular_buffer<T, Alloc>::front; | |
114 | using circular_buffer<T, Alloc>::back; | |
115 | using circular_buffer<T, Alloc>::array_one; | |
116 | using circular_buffer<T, Alloc>::array_two; | |
117 | using circular_buffer<T, Alloc>::linearize; | |
118 | using circular_buffer<T, Alloc>::is_linearized; | |
119 | using circular_buffer<T, Alloc>::rotate; | |
120 | using circular_buffer<T, Alloc>::size; | |
121 | using circular_buffer<T, Alloc>::max_size; | |
122 | using circular_buffer<T, Alloc>::empty; | |
123 | ||
124 | #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564)) | |
125 | reference operator [] (size_type n) { return circular_buffer<T, Alloc>::operator[](n); } | |
126 | const_reference operator [] (size_type n) const { return circular_buffer<T, Alloc>::operator[](n); } | |
127 | #else | |
128 | using circular_buffer<T, Alloc>::operator[]; | |
129 | #endif | |
130 | ||
131 | private: | |
132 | // Member variables | |
133 | ||
134 | //! The capacity controller of the space optimized circular buffer. | |
135 | capacity_type m_capacity_ctrl; | |
136 | ||
137 | public: | |
138 | // Overridden | |
139 | ||
140 | //! Is the <code>circular_buffer_space_optimized</code> full? | |
141 | /*! | |
142 | \return <code>true</code> if the number of elements stored in the <code>circular_buffer_space_optimized</code> | |
143 | equals the capacity of the <code>circular_buffer_space_optimized</code>; <code>false</code> otherwise. | |
144 | \throws Nothing. | |
145 | \par Exception Safety | |
146 | No-throw. | |
147 | \par Iterator Invalidation | |
148 | Does not invalidate any iterators. | |
149 | \par Complexity | |
150 | Constant (in the size of the <code>circular_buffer_space_optimized</code>). | |
151 | \sa <code>empty()</code> | |
152 | */ | |
153 | bool full() const BOOST_NOEXCEPT { return m_capacity_ctrl == size(); } | |
154 | ||
155 | /*! \brief Get the maximum number of elements which can be inserted into the | |
156 | <code>circular_buffer_space_optimized</code> without overwriting any of already stored elements. | |
157 | \return <code>capacity().%capacity() - size()</code> | |
158 | \throws Nothing. | |
159 | \par Exception Safety | |
160 | No-throw. | |
161 | \par Iterator Invalidation | |
162 | Does not invalidate any iterators. | |
163 | \par Complexity | |
164 | Constant (in the size of the <code>circular_buffer_space_optimized</code>). | |
165 | \sa <code>capacity()</code>, <code>size()</code>, <code>max_size()</code> | |
166 | */ | |
167 | size_type reserve() const BOOST_NOEXCEPT { return m_capacity_ctrl - size(); } | |
168 | ||
169 | //! Get the capacity of the <code>circular_buffer_space_optimized</code>. | |
170 | /*! | |
171 | \return The capacity controller representing the maximum number of elements which can be stored in the | |
172 | <code>circular_buffer_space_optimized</code> and the minimal allocated size of the internal buffer. | |
173 | \throws Nothing. | |
174 | \par Exception Safety | |
175 | No-throw. | |
176 | \par Iterator Invalidation | |
177 | Does not invalidate any iterators. | |
178 | \par Complexity | |
179 | Constant (in the size of the <code>circular_buffer_space_optimized</code>). | |
180 | \sa <code>reserve()</code>, <code>size()</code>, <code>max_size()</code>, | |
181 | <code>set_capacity(const capacity_type&)</code> | |
182 | */ | |
183 | const capacity_type& capacity() const BOOST_NOEXCEPT { return m_capacity_ctrl; } | |
184 | ||
185 | #if defined(BOOST_CB_TEST) | |
186 | ||
187 | // Return the current capacity of the adapted circular buffer. | |
188 | /* | |
189 | \note This method is not intended to be used directly by the user. | |
190 | It is defined only for testing purposes. | |
191 | */ | |
192 | size_type internal_capacity() const BOOST_NOEXCEPT { return circular_buffer<T, Alloc>::capacity(); } | |
193 | ||
194 | #endif // #if defined(BOOST_CB_TEST) | |
195 | ||
196 | /*! \brief Change the capacity (and the minimal guaranteed amount of allocated memory) of the | |
197 | <code>circular_buffer_space_optimized</code>. | |
198 | \post <code>capacity() == capacity_ctrl \&\& size() \<= capacity_ctrl.capacity()</code><br><br> | |
199 | If the current number of elements stored in the <code>circular_buffer_space_optimized</code> is greater | |
200 | than the desired new capacity then number of <code>[size() - capacity_ctrl.capacity()]</code> <b>last</b> | |
201 | elements will be removed and the new size will be equal to <code>capacity_ctrl.capacity()</code>.<br><br> | |
202 | If the current number of elements stored in the <code>circular_buffer_space_optimized</code> is lower | |
203 | than the new capacity then the amount of allocated memory in the internal buffer may be accommodated as | |
204 | necessary but it will never drop below <code>capacity_ctrl.min_capacity()</code>. | |
205 | \param capacity_ctrl The new capacity controller. | |
206 | \throws "An allocation error" if memory is exhausted, (<code>std::bad_alloc</code> if the standard allocator is | |
207 | used). | |
208 | Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept. | |
209 | \par Exception Safety | |
210 | Strong. | |
211 | \par Iterator Invalidation | |
212 | Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators | |
213 | equal to <code>end()</code>). | |
214 | \par Complexity | |
215 | Linear (in <code>min[size(), capacity_ctrl.%capacity()]</code>). | |
216 | \note To explicitly clear the extra allocated memory use the <b>shrink-to-fit</b> technique:<br><br> | |
217 | <code>%boost::%circular_buffer_space_optimized\<int\> cb(1000);<br> | |
218 | ...<br> | |
219 | %boost::%circular_buffer_space_optimized\<int\>(cb).swap(cb);</code><br><br> | |
220 | For more information about the shrink-to-fit technique in STL see | |
221 | <a href="http://www.gotw.ca/gotw/054.htm">http://www.gotw.ca/gotw/054.htm</a>. | |
222 | \sa <code>rset_capacity(const capacity_type&)</code>, | |
223 | <code>\link resize() resize(size_type, const_reference)\endlink</code> | |
224 | */ | |
225 | void set_capacity(const capacity_type& capacity_ctrl) { | |
226 | m_capacity_ctrl = capacity_ctrl; | |
227 | if (capacity_ctrl < size()) { | |
228 | iterator e = end(); | |
229 | circular_buffer<T, Alloc>::erase(e - (size() - capacity_ctrl), e); | |
230 | } | |
231 | adjust_min_capacity(); | |
232 | } | |
233 | ||
234 | //! Change the size of the <code>circular_buffer_space_optimized</code>. | |
235 | /*! | |
236 | \post <code>size() == new_size \&\& capacity().%capacity() >= new_size</code><br><br> | |
237 | If the new size is greater than the current size, copies of <code>item</code> will be inserted at the | |
238 | <b>back</b> of the of the <code>circular_buffer_space_optimized</code> in order to achieve the desired | |
239 | size. In the case the resulting size exceeds the current capacity the capacity will be set to | |
240 | <code>new_size</code>.<br><br> | |
241 | If the current number of elements stored in the <code>circular_buffer_space_optimized</code> is greater | |
242 | than the desired new size then number of <code>[size() - new_size]</code> <b>last</b> elements will be | |
243 | removed. (The capacity will remain unchanged.)<br><br> | |
244 | The amount of allocated memory in the internal buffer may be accommodated as necessary. | |
245 | \param new_size The new size. | |
246 | \param item The element the <code>circular_buffer_space_optimized</code> will be filled with in order to gain | |
247 | the requested size. (See the <i>Effect</i>.) | |
248 | \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is | |
249 | used). | |
250 | Whatever <code>T::T(const T&)</code> throws. | |
251 | \par Exception Safety | |
252 | Basic. | |
253 | \par Iterator Invalidation | |
254 | Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators | |
255 | equal to <code>end()</code>). | |
256 | \par Complexity | |
257 | Linear (in the new size of the <code>circular_buffer_space_optimized</code>). | |
258 | \sa <code>\link rresize() rresize(size_type, const_reference)\endlink</code>, | |
259 | <code>set_capacity(const capacity_type&)</code> | |
260 | */ | |
261 | void resize(size_type new_size, param_value_type item = value_type()) { | |
262 | if (new_size > size()) { | |
263 | if (new_size > m_capacity_ctrl) | |
264 | m_capacity_ctrl = capacity_type(new_size, m_capacity_ctrl.min_capacity()); | |
265 | insert(end(), new_size - size(), item); | |
266 | } else { | |
267 | iterator e = end(); | |
268 | erase(e - (size() - new_size), e); | |
269 | } | |
270 | } | |
271 | ||
272 | /*! \brief Change the capacity (and the minimal guaranteed amount of allocated memory) of the | |
273 | <code>circular_buffer_space_optimized</code>. | |
274 | \post <code>capacity() == capacity_ctrl \&\& size() \<= capacity_ctrl</code><br><br> | |
275 | If the current number of elements stored in the <code>circular_buffer_space_optimized</code> is greater | |
276 | than the desired new capacity then number of <code>[size() - capacity_ctrl.capacity()]</code> | |
277 | <b>first</b> elements will be removed and the new size will be equal to | |
278 | <code>capacity_ctrl.capacity()</code>.<br><br> | |
279 | If the current number of elements stored in the <code>circular_buffer_space_optimized</code> is lower | |
280 | than the new capacity then the amount of allocated memory in the internal buffer may be accommodated as | |
281 | necessary but it will never drop below <code>capacity_ctrl.min_capacity()</code>. | |
282 | \param capacity_ctrl The new capacity controller. | |
283 | \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is | |
284 | used). | |
285 | Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept. | |
286 | \par Exception Safety | |
287 | Strong. | |
288 | \par Iterator Invalidation | |
289 | Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators | |
290 | equal to <code>end()</code>). | |
291 | \par Complexity | |
292 | Linear (in <code>min[size(), capacity_ctrl.%capacity()]</code>). | |
293 | \sa <code>set_capacity(const capacity_type&)</code>, | |
294 | <code>\link rresize() rresize(size_type, const_reference)\endlink</code> | |
295 | */ | |
296 | void rset_capacity(const capacity_type& capacity_ctrl) { | |
297 | m_capacity_ctrl = capacity_ctrl; | |
298 | if (capacity_ctrl < size()) { | |
299 | iterator b = begin(); | |
300 | circular_buffer<T, Alloc>::rerase(b, b + (size() - capacity_ctrl)); | |
301 | } | |
302 | adjust_min_capacity(); | |
303 | } | |
304 | ||
305 | //! Change the size of the <code>circular_buffer_space_optimized</code>. | |
306 | /*! | |
307 | \post <code>size() == new_size \&\& capacity().%capacity() >= new_size</code><br><br> | |
308 | If the new size is greater than the current size, copies of <code>item</code> will be inserted at the | |
309 | <b>front</b> of the of the <code>circular_buffer_space_optimized</code> in order to achieve the desired | |
310 | size. In the case the resulting size exceeds the current capacity the capacity will be set to | |
311 | <code>new_size</code>.<br><br> | |
312 | If the current number of elements stored in the <code>circular_buffer_space_optimized</code> is greater | |
313 | than the desired new size then number of <code>[size() - new_size]</code> <b>first</b> elements will be | |
314 | removed. (The capacity will remain unchanged.)<br><br> | |
315 | The amount of allocated memory in the internal buffer may be accommodated as necessary. | |
316 | \param new_size The new size. | |
317 | \param item The element the <code>circular_buffer_space_optimized</code> will be filled with in order to gain | |
318 | the requested size. (See the <i>Effect</i>.) | |
319 | \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is | |
320 | used). | |
321 | Whatever <code>T::T(const T&)</code> throws. | |
322 | \par Exception Safety | |
323 | Basic. | |
324 | \par Iterator Invalidation | |
325 | Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators | |
326 | equal to <code>end()</code>). | |
327 | \par Complexity | |
328 | Linear (in the new size of the <code>circular_buffer_space_optimized</code>). | |
329 | \sa <code>\link resize() resize(size_type, const_reference)\endlink</code>, | |
330 | <code>rset_capacity(const capacity_type&)</code> | |
331 | */ | |
332 | void rresize(size_type new_size, param_value_type item = value_type()) { | |
333 | if (new_size > size()) { | |
334 | if (new_size > m_capacity_ctrl) | |
335 | m_capacity_ctrl = capacity_type(new_size, m_capacity_ctrl.min_capacity()); | |
336 | rinsert(begin(), new_size - size(), item); | |
337 | } else { | |
338 | rerase(begin(), end() - new_size); | |
339 | } | |
340 | } | |
341 | ||
342 | //! Create an empty space optimized circular buffer with zero capacity. | |
343 | /*! | |
344 | \post <code>capacity().%capacity() == 0 \&\& capacity().min_capacity() == 0 \&\& size() == 0</code> | |
345 | \param alloc The allocator. | |
346 | \throws Nothing. | |
347 | \par Complexity | |
348 | Constant. | |
349 | \warning Since Boost version 1.36 the behaviour of this constructor has changed. Now it creates a space | |
350 | optimized circular buffer with zero capacity. | |
351 | */ | |
352 | explicit circular_buffer_space_optimized(const allocator_type& alloc = allocator_type()) BOOST_NOEXCEPT | |
353 | : circular_buffer<T, Alloc>(0, alloc) | |
354 | , m_capacity_ctrl(0) {} | |
355 | ||
356 | //! Create an empty space optimized circular buffer with the specified capacity. | |
357 | /*! | |
358 | \post <code>capacity() == capacity_ctrl \&\& size() == 0</code><br><br> | |
359 | The amount of allocated memory in the internal buffer is <code>capacity_ctrl.min_capacity()</code>. | |
360 | \param capacity_ctrl The capacity controller representing the maximum number of elements which can be stored in | |
361 | the <code>circular_buffer_space_optimized</code> and the minimal allocated size of the | |
362 | internal buffer. | |
363 | \param alloc The allocator. | |
364 | \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is | |
365 | used). | |
366 | \par Complexity | |
367 | Constant. | |
368 | */ | |
369 | explicit circular_buffer_space_optimized(capacity_type capacity_ctrl, | |
370 | const allocator_type& alloc = allocator_type()) | |
371 | : circular_buffer<T, Alloc>(capacity_ctrl.min_capacity(), alloc) | |
372 | , m_capacity_ctrl(capacity_ctrl) {} | |
373 | ||
374 | /*! \brief Create a full space optimized circular buffer with the specified capacity filled with | |
375 | <code>capacity_ctrl.%capacity()</code> copies of <code>item</code>. | |
376 | \post <code>capacity() == capacity_ctrl \&\& full() \&\& (*this)[0] == item \&\& (*this)[1] == item \&\& ... | |
377 | \&\& (*this) [capacity_ctrl.%capacity() - 1] == item </code><br><br> | |
378 | The amount of allocated memory in the internal buffer is <code>capacity_ctrl.capacity()</code>. | |
379 | \param capacity_ctrl The capacity controller representing the maximum number of elements which can be stored in | |
380 | the <code>circular_buffer_space_optimized</code> and the minimal allocated size of the | |
381 | internal buffer. | |
382 | \param item The element the created <code>circular_buffer_space_optimized</code> will be filled with. | |
383 | \param alloc The allocator. | |
384 | \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is | |
385 | used). | |
386 | \throws Whatever <code>T::T(const T&)</code> throws. | |
387 | \par Complexity | |
388 | Linear (in the <code>capacity_ctrl.%capacity()</code>). | |
389 | */ | |
390 | circular_buffer_space_optimized(capacity_type capacity_ctrl, param_value_type item, | |
391 | const allocator_type& alloc = allocator_type()) | |
392 | : circular_buffer<T, Alloc>(capacity_ctrl.capacity(), item, alloc) | |
393 | , m_capacity_ctrl(capacity_ctrl) {} | |
394 | ||
395 | /*! \brief Create a space optimized circular buffer with the specified capacity filled with <code>n</code> copies | |
396 | of <code>item</code>. | |
397 | \pre <code>capacity_ctrl.%capacity() >= n</code> | |
398 | \post <code>capacity() == capacity_ctrl \&\& size() == n \&\& (*this)[0] == item \&\& (*this)[1] == item | |
399 | \&\& ... \&\& (*this)[n - 1] == item</code><br><br> | |
400 | The amount of allocated memory in the internal buffer is | |
401 | <code>max[n, capacity_ctrl.min_capacity()]</code>. | |
402 | \param capacity_ctrl The capacity controller representing the maximum number of elements which can be stored in | |
403 | the <code>circular_buffer_space_optimized</code> and the minimal allocated size of the | |
404 | internal buffer. | |
405 | \param n The number of elements the created <code>circular_buffer_space_optimized</code> will be filled with. | |
406 | \param item The element the created <code>circular_buffer_space_optimized</code> will be filled with. | |
407 | \param alloc The allocator. | |
408 | \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is | |
409 | used). | |
410 | Whatever <code>T::T(const T&)</code> throws. | |
411 | \par Complexity | |
412 | Linear (in the <code>n</code>). | |
413 | */ | |
414 | circular_buffer_space_optimized(capacity_type capacity_ctrl, size_type n, param_value_type item, | |
415 | const allocator_type& alloc = allocator_type()) | |
416 | : circular_buffer<T, Alloc>(init_capacity(capacity_ctrl, n), n, item, alloc) | |
417 | , m_capacity_ctrl(capacity_ctrl) {} | |
418 | ||
419 | //! The copy constructor. | |
420 | /*! | |
421 | Creates a copy of the specified <code>circular_buffer_space_optimized</code>. | |
422 | \post <code>*this == cb</code><br><br> | |
423 | The amount of allocated memory in the internal buffer is <code>cb.size()</code>. | |
424 | \param cb The <code>circular_buffer_space_optimized</code> to be copied. | |
425 | \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is | |
426 | used). | |
427 | Whatever <code>T::T(const T&)</code> throws. | |
428 | \par Complexity | |
429 | Linear (in the size of <code>cb</code>). | |
430 | */ | |
431 | circular_buffer_space_optimized(const circular_buffer_space_optimized<T, Alloc>& cb) | |
432 | : circular_buffer<T, Alloc>(cb.begin(), cb.end(), cb.get_allocator()) | |
433 | , m_capacity_ctrl(cb.m_capacity_ctrl) {} | |
434 | ||
435 | #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES | |
436 | //! The move constructor. | |
437 | /*! \brief Move constructs a <code>circular_buffer_space_optimized</code> from <code>cb</code>, | |
438 | leaving <code>cb</code> empty. | |
439 | \pre C++ compiler with rvalue references support. | |
440 | \post <code>cb.empty()</code> | |
441 | \param cb <code>circular_buffer</code> to 'steal' value from. | |
442 | \throws Nothing. | |
443 | \par Constant. | |
444 | */ | |
445 | circular_buffer_space_optimized(circular_buffer_space_optimized<T, Alloc>&& cb) BOOST_NOEXCEPT | |
446 | : circular_buffer<T, Alloc>() | |
447 | , m_capacity_ctrl(0) { | |
448 | cb.swap(*this); | |
449 | } | |
450 | #endif // BOOST_NO_CXX11_RVALUE_REFERENCES | |
451 | ||
452 | //! Create a full space optimized circular buffer filled with a copy of the range. | |
453 | /*! | |
454 | \pre Valid range <code>[first, last)</code>.<br> | |
455 | <code>first</code> and <code>last</code> have to meet the requirements of | |
456 | <a href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>. | |
457 | \post <code>capacity().%capacity() == std::distance(first, last) \&\& capacity().min_capacity() == 0 \&\& | |
458 | full() \&\& (*this)[0]== *first \&\& (*this)[1] == *(first + 1) \&\& ... \&\& | |
459 | (*this)[std::distance(first, last) - 1] == *(last - 1)</code><br><br> | |
460 | The amount of allocated memory in the internal buffer is <code>std::distance(first, last)</code>. | |
461 | \param first The beginning of the range to be copied. | |
462 | \param last The end of the range to be copied. | |
463 | \param alloc The allocator. | |
464 | \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is | |
465 | used). | |
466 | Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept | |
467 | and <code>InputIterator</code> is a move iterator. | |
468 | \par Complexity | |
469 | Linear (in the <code>std::distance(first, last)</code>). | |
470 | */ | |
471 | template <class InputIterator> | |
472 | circular_buffer_space_optimized(InputIterator first, InputIterator last, | |
473 | const allocator_type& alloc = allocator_type()) | |
474 | : circular_buffer<T, Alloc>(first, last, alloc) | |
475 | , m_capacity_ctrl(circular_buffer<T, Alloc>::capacity()) {} | |
476 | ||
477 | /*! \brief Create a space optimized circular buffer with the specified capacity (and the minimal guaranteed amount | |
478 | of allocated memory) filled with a copy of the range. | |
479 | \pre Valid range <code>[first, last)</code>.<br> | |
480 | <code>first</code> and <code>last</code> have to meet the requirements of | |
481 | <a href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>. | |
482 | \post <code>capacity() == capacity_ctrl \&\& size() \<= std::distance(first, last) \&\& (*this)[0]== | |
483 | *(last - capacity_ctrl.%capacity()) \&\& (*this)[1] == *(last - capacity_ctrl.%capacity() + 1) \&\& ... | |
484 | \&\& (*this)[capacity_ctrl.%capacity() - 1] == *(last - 1)</code><br><br> | |
485 | If the number of items to be copied from the range <code>[first, last)</code> is greater than the | |
486 | specified <code>capacity_ctrl.%capacity()</code> then only elements from the range | |
487 | <code>[last - capacity_ctrl.%capacity(), last)</code> will be copied.<br><br> | |
488 | The amount of allocated memory in the internal buffer is <code>max[capacity_ctrl.min_capacity(), | |
489 | min[capacity_ctrl.%capacity(), std::distance(first, last)]]</code>. | |
490 | \param capacity_ctrl The capacity controller representing the maximum number of elements which can be stored in | |
491 | the <code>circular_buffer_space_optimized</code> and the minimal allocated size of the | |
492 | internal buffer. | |
493 | \param first The beginning of the range to be copied. | |
494 | \param last The end of the range to be copied. | |
495 | \param alloc The allocator. | |
496 | \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is | |
497 | used). | |
498 | Whatever <code>T::T(const T&)</code> throws. | |
499 | \par Complexity | |
500 | Linear (in <code>std::distance(first, last)</code>; in | |
501 | <code>min[capacity_ctrl.%capacity(), std::distance(first, last)]</code> if the <code>InputIterator</code> | |
502 | is a <a href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">RandomAccessIterator</a>). | |
503 | */ | |
504 | template <class InputIterator> | |
505 | circular_buffer_space_optimized(capacity_type capacity_ctrl, InputIterator first, InputIterator last, | |
506 | const allocator_type& alloc = allocator_type()) | |
507 | : circular_buffer<T, Alloc>( | |
508 | init_capacity(capacity_ctrl, first, last, is_integral<InputIterator>()), | |
509 | first, last, alloc) | |
510 | , m_capacity_ctrl(capacity_ctrl) { | |
511 | reduce_capacity( | |
512 | is_same< BOOST_DEDUCED_TYPENAME iterator_category<InputIterator>::type, std::input_iterator_tag >()); | |
513 | } | |
514 | ||
515 | #if defined(BOOST_CB_NEVER_DEFINED) | |
516 | // This section will never be compiled - the default destructor will be generated instead. | |
517 | // Declared only for documentation purpose. | |
518 | ||
519 | //! The destructor. | |
520 | /*! | |
521 | Destroys the <code>circular_buffer_space_optimized</code>. | |
522 | \throws Nothing. | |
523 | \par Iterator Invalidation | |
524 | Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (including | |
525 | iterators equal to <code>end()</code>). | |
526 | \par Complexity | |
527 | Linear (in the size of the <code>circular_buffer_space_optimized</code>). | |
528 | \sa <code>clear()</code> | |
529 | */ | |
530 | ~circular_buffer_space_optimized(); | |
531 | ||
532 | //! no-comment | |
533 | void erase_begin(size_type n); | |
534 | ||
535 | //! no-comment | |
536 | void erase_end(size_type n); | |
537 | ||
538 | #endif // #if defined(BOOST_CB_NEVER_DEFINED) | |
539 | ||
540 | //! The assign operator. | |
541 | /*! | |
542 | Makes this <code>circular_buffer_space_optimized</code> to become a copy of the specified | |
543 | <code>circular_buffer_space_optimized</code>. | |
544 | \post <code>*this == cb</code><br><br> | |
545 | The amount of allocated memory in the internal buffer is <code>cb.size()</code>. | |
546 | \param cb The <code>circular_buffer_space_optimized</code> to be copied. | |
547 | \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is | |
548 | used). | |
549 | \throws Whatever <code>T::T(const T&)</code> throws. | |
550 | \par Exception Safety | |
551 | Strong. | |
552 | \par Iterator Invalidation | |
553 | Invalidates all iterators pointing to this <code>circular_buffer_space_optimized</code> (except iterators | |
554 | equal to <code>end()</code>). | |
555 | \par Complexity | |
556 | Linear (in the size of <code>cb</code>). | |
557 | \sa <code>\link assign(size_type, param_value_type) assign(size_type, const_reference)\endlink</code>, | |
558 | <code>\link assign(capacity_type, size_type, param_value_type) | |
559 | assign(capacity_type, size_type, const_reference)\endlink</code>, | |
560 | <code>assign(InputIterator, InputIterator)</code>, | |
561 | <code>assign(capacity_type, InputIterator, InputIterator)</code> | |
562 | */ | |
563 | circular_buffer_space_optimized<T, Alloc>& operator = (const circular_buffer_space_optimized<T, Alloc>& cb) { | |
564 | if (this == &cb) | |
565 | return *this; | |
566 | circular_buffer<T, Alloc>::assign(cb.begin(), cb.end()); | |
567 | m_capacity_ctrl = cb.m_capacity_ctrl; | |
568 | return *this; | |
569 | } | |
570 | ||
571 | #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES | |
572 | /*! \brief Move assigns content of <code>cb</code> to <code>*this</code>, leaving <code>cb</code> empty. | |
573 | \pre C++ compiler with rvalue references support. | |
574 | \post <code>cb.empty()</code> | |
575 | \param cb <code>circular_buffer</code> to 'steal' value from. | |
576 | \throws Nothing. | |
577 | \par Complexity | |
578 | Constant. | |
579 | */ | |
580 | circular_buffer_space_optimized<T, Alloc>& operator = (circular_buffer_space_optimized<T, Alloc>&& cb) BOOST_NOEXCEPT { | |
581 | cb.swap(*this); // now `this` holds `cb` | |
582 | circular_buffer<T, Alloc>(get_allocator()) // temprary that holds initial `cb` allocator | |
583 | .swap(cb); // makes `cb` empty | |
584 | return *this; | |
585 | } | |
586 | #endif // BOOST_NO_CXX11_RVALUE_REFERENCES | |
587 | ||
588 | ||
589 | //! Assign <code>n</code> items into the space optimized circular buffer. | |
590 | /*! | |
591 | The content of the <code>circular_buffer_space_optimized</code> will be removed and replaced with | |
592 | <code>n</code> copies of the <code>item</code>. | |
593 | \post <code>capacity().%capacity() == n \&\& capacity().min_capacity() == 0 \&\& size() == n \&\& (*this)[0] == | |
594 | item \&\& (*this)[1] == item \&\& ... \&\& (*this) [n - 1] == item</code><br><br> | |
595 | The amount of allocated memory in the internal buffer is <code>n</code>. | |
596 | \param n The number of elements the <code>circular_buffer_space_optimized</code> will be filled with. | |
597 | \param item The element the <code>circular_buffer_space_optimized</code> will be filled with. | |
598 | \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is | |
599 | used). | |
600 | Whatever <code>T::T(const T&)</code> throws. | |
601 | \par Exception Safety | |
602 | Basic. | |
603 | \par Iterator Invalidation | |
604 | Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators | |
605 | equal to <code>end()</code>). | |
606 | \par Complexity | |
607 | Linear (in the <code>n</code>). | |
608 | \sa <code>\link operator=(const circular_buffer_space_optimized&) operator=\endlink</code>, | |
609 | <code>\link assign(capacity_type, size_type, param_value_type) | |
610 | assign(capacity_type, size_type, const_reference)\endlink</code>, | |
611 | <code>assign(InputIterator, InputIterator)</code>, | |
612 | <code>assign(capacity_type, InputIterator, InputIterator)</code> | |
613 | */ | |
614 | void assign(size_type n, param_value_type item) { | |
615 | circular_buffer<T, Alloc>::assign(n, item); | |
616 | m_capacity_ctrl = capacity_type(n); | |
617 | } | |
618 | ||
619 | //! Assign <code>n</code> items into the space optimized circular buffer specifying the capacity. | |
620 | /*! | |
621 | The capacity of the <code>circular_buffer_space_optimized</code> will be set to the specified value and the | |
622 | content of the <code>circular_buffer_space_optimized</code> will be removed and replaced with <code>n</code> | |
623 | copies of the <code>item</code>. | |
624 | \pre <code>capacity_ctrl.%capacity() >= n</code> | |
625 | \post <code>capacity() == capacity_ctrl \&\& size() == n \&\& (*this)[0] == item \&\& (*this)[1] == item | |
626 | \&\& ... \&\& (*this) [n - 1] == item </code><br><br> | |
627 | The amount of allocated memory will be <code>max[n, capacity_ctrl.min_capacity()]</code>. | |
628 | \param capacity_ctrl The new capacity controller. | |
629 | \param n The number of elements the <code>circular_buffer_space_optimized</code> will be filled with. | |
630 | \param item The element the <code>circular_buffer_space_optimized</code> will be filled with. | |
631 | \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is | |
632 | used). | |
633 | Whatever <code>T::T(const T&)</code> throws. | |
634 | \par Exception Safety | |
635 | Basic. | |
636 | \par Iterator Invalidation | |
637 | Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators | |
638 | equal to <code>end()</code>). | |
639 | \par Complexity | |
640 | Linear (in the <code>n</code>). | |
641 | \sa <code>\link operator=(const circular_buffer_space_optimized&) operator=\endlink</code>, | |
642 | <code>\link assign(size_type, param_value_type) assign(size_type, const_reference)\endlink</code>, | |
643 | <code>assign(InputIterator, InputIterator)</code>, | |
644 | <code>assign(capacity_type, InputIterator, InputIterator)</code> | |
645 | */ | |
646 | void assign(capacity_type capacity_ctrl, size_type n, param_value_type item) { | |
647 | BOOST_CB_ASSERT(capacity_ctrl.capacity() >= n); // check for new capacity lower than n | |
648 | circular_buffer<T, Alloc>::assign((std::max)(capacity_ctrl.min_capacity(), n), n, item); | |
649 | m_capacity_ctrl = capacity_ctrl; | |
650 | } | |
651 | ||
652 | //! Assign a copy of the range into the space optimized circular buffer. | |
653 | /*! | |
654 | The content of the <code>circular_buffer_space_optimized</code> will be removed and replaced with copies of | |
655 | elements from the specified range. | |
656 | \pre Valid range <code>[first, last)</code>.<br> | |
657 | <code>first</code> and <code>last</code> have to meet the requirements of | |
658 | <a href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>. | |
659 | \post <code>capacity().%capacity() == std::distance(first, last) \&\& capacity().min_capacity() == 0 \&\& | |
660 | size() == std::distance(first, last) \&\& (*this)[0]== *first \&\& (*this)[1] == *(first + 1) \&\& ... | |
661 | \&\& (*this)[std::distance(first, last) - 1] == *(last - 1)</code><br><br> | |
662 | The amount of allocated memory in the internal buffer is <code>std::distance(first, last)</code>. | |
663 | \param first The beginning of the range to be copied. | |
664 | \param last The end of the range to be copied. | |
665 | \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is | |
666 | used). | |
667 | Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept and | |
668 | <code>InputIterator</code> is a move iterator. | |
669 | \par Exception Safety | |
670 | Basic. | |
671 | \par Iterator Invalidation | |
672 | Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators | |
673 | equal to <code>end()</code>). | |
674 | \par Complexity | |
675 | Linear (in the <code>std::distance(first, last)</code>). | |
676 | \sa <code>\link operator=(const circular_buffer_space_optimized&) operator=\endlink</code>, | |
677 | <code>\link assign(size_type, param_value_type) assign(size_type, const_reference)\endlink</code>, | |
678 | <code>\link assign(capacity_type, size_type, param_value_type) | |
679 | assign(capacity_type, size_type, const_reference)\endlink</code>, | |
680 | <code>assign(capacity_type, InputIterator, InputIterator)</code> | |
681 | */ | |
682 | template <class InputIterator> | |
683 | void assign(InputIterator first, InputIterator last) { | |
684 | circular_buffer<T, Alloc>::assign(first, last); | |
685 | m_capacity_ctrl = capacity_type(circular_buffer<T, Alloc>::capacity()); | |
686 | } | |
687 | ||
688 | //! Assign a copy of the range into the space optimized circular buffer specifying the capacity. | |
689 | /*! | |
690 | The capacity of the <code>circular_buffer_space_optimized</code> will be set to the specified value and the | |
691 | content of the <code>circular_buffer_space_optimized</code> will be removed and replaced with copies of | |
692 | elements from the specified range. | |
693 | \pre Valid range <code>[first, last)</code>.<br> | |
694 | <code>first</code> and <code>last</code> have to meet the requirements of | |
695 | <a href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>. | |
696 | \post <code>capacity() == capacity_ctrl \&\& size() \<= std::distance(first, last) \&\& | |
697 | (*this)[0]== *(last - capacity) \&\& (*this)[1] == *(last - capacity + 1) \&\& ... \&\& | |
698 | (*this)[capacity - 1] == *(last - 1)</code><br><br> | |
699 | If the number of items to be copied from the range <code>[first, last)</code> is greater than the | |
700 | specified <code>capacity</code> then only elements from the range <code>[last - capacity, last)</code> | |
701 | will be copied.<br><br> The amount of allocated memory in the internal buffer is | |
702 | <code>max[std::distance(first, last), capacity_ctrl.min_capacity()]</code>. | |
703 | \param capacity_ctrl The new capacity controller. | |
704 | \param first The beginning of the range to be copied. | |
705 | \param last The end of the range to be copied. | |
706 | \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is | |
707 | used). | |
708 | Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept and | |
709 | <code>InputIterator</code> is a move iterator. | |
710 | \par Exception Safety | |
711 | Basic. | |
712 | \par Iterator Invalidation | |
713 | Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators | |
714 | equal to <code>end()</code>). | |
715 | \par Complexity | |
716 | Linear (in <code>std::distance(first, last)</code>; in | |
717 | <code>min[capacity_ctrl.%capacity(), std::distance(first, last)]</code> if the <code>InputIterator</code> | |
718 | is a <a href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">RandomAccessIterator</a>). | |
719 | \sa <code>\link operator=(const circular_buffer_space_optimized&) operator=\endlink</code>, | |
720 | <code>\link assign(size_type, param_value_type) assign(size_type, const_reference)\endlink</code>, | |
721 | <code>\link assign(capacity_type, size_type, param_value_type) | |
722 | assign(capacity_type, size_type, const_reference)\endlink</code>, | |
723 | <code>assign(InputIterator, InputIterator)</code> | |
724 | */ | |
725 | template <class InputIterator> | |
726 | void assign(capacity_type capacity_ctrl, InputIterator first, InputIterator last) { | |
727 | m_capacity_ctrl = capacity_ctrl; | |
728 | circular_buffer<T, Alloc>::assign(capacity_ctrl, first, last); | |
729 | } | |
730 | ||
731 | //! Swap the contents of two space-optimized circular-buffers. | |
732 | /*! | |
733 | \post <code>this</code> contains elements of <code>cb</code> and vice versa; the capacity and the amount of | |
734 | allocated memory in the internal buffer of <code>this</code> equal to the capacity and the amount of | |
735 | allocated memory of <code>cb</code> and vice versa. | |
736 | \param cb The <code>circular_buffer_space_optimized</code> whose content will be swapped. | |
737 | \throws Nothing. | |
738 | \par Exception Safety | |
739 | No-throw. | |
740 | \par Iterator Invalidation | |
741 | Invalidates all iterators of both <code>circular_buffer_space_optimized</code> containers. (On the other | |
742 | hand the iterators still point to the same elements but within another container. If you want to rely on | |
743 | this feature you have to turn the __debug_support off, | |
744 | otherwise an assertion will report an error if such invalidated iterator is used.) | |
745 | \par Complexity | |
746 | Constant (in the size of the <code>circular_buffer_space_optimized</code>). | |
747 | \sa <code>swap(circular_buffer<T, Alloc>&, circular_buffer<T, Alloc>&)</code>, | |
748 | <code>swap(circular_buffer_space_optimized<T, Alloc>&, circular_buffer_space_optimized<T, Alloc>&)</code> | |
749 | ||
750 | ||
751 | */ | |
752 | // Note link does not work right. Asked on Doxygen forum for advice 23 May 2103. | |
753 | ||
754 | void swap(circular_buffer_space_optimized<T, Alloc>& cb) BOOST_NOEXCEPT { | |
755 | std::swap(m_capacity_ctrl, cb.m_capacity_ctrl); | |
756 | circular_buffer<T, Alloc>::swap(cb); | |
757 | } | |
758 | ||
759 | //! Insert a new element at the end of the space optimized circular buffer. | |
760 | /*! | |
761 | \post if <code>capacity().%capacity() > 0</code> then <code>back() == item</code><br> | |
762 | If the <code>circular_buffer_space_optimized</code> is full, the first element will be removed. If the | |
763 | capacity is <code>0</code>, nothing will be inserted.<br><br> | |
764 | The amount of allocated memory in the internal buffer may be predictively increased. | |
765 | \param item The element to be inserted. | |
766 | \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is | |
767 | used). | |
768 | Whatever <code>T::T(const T&)</code> throws. | |
769 | \par Exception Safety | |
770 | Basic. | |
771 | \par Iterator Invalidation | |
772 | Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators | |
773 | equal to <code>end()</code>). | |
774 | \par Complexity | |
775 | Linear (in the size of the <code>circular_buffer_space_optimized</code>). | |
776 | \sa <code>\link push_front() push_front(const_reference)\endlink</code>, <code>pop_back()</code>, | |
777 | <code>pop_front()</code> | |
778 | */ | |
779 | void push_back(param_value_type item) { | |
780 | check_low_capacity(); | |
781 | circular_buffer<T, Alloc>::push_back(item); | |
782 | } | |
783 | ||
784 | //! Insert a new element at the end of the space optimized circular buffer. | |
785 | /*! | |
786 | \post if <code>capacity().%capacity() > 0</code> then <code>back() == item</code><br> | |
787 | If the <code>circular_buffer_space_optimized</code> is full, the first element will be removed. If the | |
788 | capacity is <code>0</code>, nothing will be inserted.<br><br> | |
789 | The amount of allocated memory in the internal buffer may be predictively increased. | |
790 | \param item The element to be inserted. | |
791 | \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is | |
792 | used). | |
793 | \par Exception Safety | |
794 | Basic. | |
795 | \par Iterator Invalidation | |
796 | Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators | |
797 | equal to <code>end()</code>). | |
798 | \par Complexity | |
799 | Linear (in the size of the <code>circular_buffer_space_optimized</code>). | |
800 | \sa <code>\link push_front() push_front(const_reference)\endlink</code>, <code>pop_back()</code>, | |
801 | <code>pop_front()</code> | |
802 | */ | |
803 | void push_back(rvalue_type item) { | |
804 | check_low_capacity(); | |
805 | circular_buffer<T, Alloc>::push_back(boost::move(item)); | |
806 | } | |
807 | ||
808 | //! Insert a new element at the end of the space optimized circular buffer. | |
809 | /*! | |
810 | \post if <code>capacity().%capacity() > 0</code> then <code>back() == item</code><br> | |
811 | If the <code>circular_buffer_space_optimized</code> is full, the first element will be removed. If the | |
812 | capacity is <code>0</code>, nothing will be inserted.<br><br> | |
813 | The amount of allocated memory in the internal buffer may be predictively increased. | |
814 | \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is | |
815 | used). | |
816 | Whatever <code>T::T()</code> throws. | |
817 | Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept. | |
818 | \par Exception Safety | |
819 | Basic. | |
820 | \par Iterator Invalidation | |
821 | Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators | |
822 | equal to <code>end()</code>). | |
823 | \par Complexity | |
824 | Linear (in the size of the <code>circular_buffer_space_optimized</code>). | |
825 | \sa <code>\link push_front() push_front(const_reference)\endlink</code>, <code>pop_back()</code>, | |
826 | <code>pop_front()</code> | |
827 | */ | |
828 | void push_back() { | |
829 | check_low_capacity(); | |
830 | circular_buffer<T, Alloc>::push_back(); | |
831 | } | |
832 | ||
833 | //! Insert a new element at the beginning of the space optimized circular buffer. | |
834 | /*! | |
835 | \post if <code>capacity().%capacity() > 0</code> then <code>front() == item</code><br> | |
836 | If the <code>circular_buffer_space_optimized</code> is full, the last element will be removed. If the | |
837 | capacity is <code>0</code>, nothing will be inserted.<br><br> | |
838 | The amount of allocated memory in the internal buffer may be predictively increased. | |
839 | \param item The element to be inserted. | |
840 | \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is | |
841 | used). | |
842 | Whatever <code>T::T(const T&)</code> throws. | |
843 | \par Exception Safety | |
844 | Basic. | |
845 | \par Iterator Invalidation | |
846 | Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators | |
847 | equal to <code>end()</code>). | |
848 | \par Complexity | |
849 | Linear (in the size of the <code>circular_buffer_space_optimized</code>). | |
850 | \sa <code>\link push_back() push_back(const_reference)\endlink</code>, <code>pop_back()</code>, | |
851 | <code>pop_front()</code> | |
852 | */ | |
853 | void push_front(param_value_type item) { | |
854 | check_low_capacity(); | |
855 | circular_buffer<T, Alloc>::push_front(item); | |
856 | } | |
857 | ||
858 | //! Insert a new element at the beginning of the space optimized circular buffer. | |
859 | /*! | |
860 | \post if <code>capacity().%capacity() > 0</code> then <code>front() == item</code><br> | |
861 | If the <code>circular_buffer_space_optimized</code> is full, the last element will be removed. If the | |
862 | capacity is <code>0</code>, nothing will be inserted.<br><br> | |
863 | The amount of allocated memory in the internal buffer may be predictively increased. | |
864 | \param item The element to be inserted. | |
865 | \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is | |
866 | used). | |
867 | Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept. | |
868 | \par Exception Safety | |
869 | Basic. | |
870 | \par Iterator Invalidation | |
871 | Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators | |
872 | equal to <code>end()</code>). | |
873 | \par Complexity | |
874 | Linear (in the size of the <code>circular_buffer_space_optimized</code>). | |
875 | \sa <code>\link push_back() push_back(const_reference)\endlink</code>, <code>pop_back()</code>, | |
876 | <code>pop_front()</code> | |
877 | */ | |
878 | void push_front(rvalue_type item) { | |
879 | check_low_capacity(); | |
880 | circular_buffer<T, Alloc>::push_front(boost::move(item)); | |
881 | } | |
882 | ||
883 | //! Insert a new element at the beginning of the space optimized circular buffer. | |
884 | /*! | |
885 | \post if <code>capacity().%capacity() > 0</code> then <code>front() == item</code><br> | |
886 | If the <code>circular_buffer_space_optimized</code> is full, the last element will be removed. If the | |
887 | capacity is <code>0</code>, nothing will be inserted.<br><br> | |
888 | The amount of allocated memory in the internal buffer may be predictively increased. | |
889 | \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is | |
890 | used). | |
891 | Whatever <code>T::T()</code> throws. | |
892 | Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept. | |
893 | \par Exception Safety | |
894 | Basic. | |
895 | \par Iterator Invalidation | |
896 | Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators | |
897 | equal to <code>end()</code>). | |
898 | \par Complexity | |
899 | Linear (in the size of the <code>circular_buffer_space_optimized</code>). | |
900 | \sa <code>\link push_back() push_back(const_reference)\endlink</code>, <code>pop_back()</code>, | |
901 | <code>pop_front()</code> | |
902 | */ | |
903 | void push_front() { | |
904 | check_low_capacity(); | |
905 | circular_buffer<T, Alloc>::push_front(); | |
906 | } | |
907 | ||
908 | //! Remove the last element from the space optimized circular buffer. | |
909 | /*! | |
910 | \pre <code>!empty()</code> | |
911 | \post The last element is removed from the <code>circular_buffer_space_optimized</code>.<br><br> | |
912 | The amount of allocated memory in the internal buffer may be predictively decreased. | |
913 | \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is | |
914 | used). | |
915 | \par Exception Safety | |
916 | Basic. | |
917 | \par Iterator Invalidation | |
918 | Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators | |
919 | equal to <code>end()</code>). | |
920 | \par Complexity | |
921 | Linear (in the size of the <code>circular_buffer_space_optimized</code>). | |
922 | \sa <code>pop_front()</code>, <code>\link push_back() push_back(const_reference)\endlink</code>, | |
923 | <code>\link push_front() push_front(const_reference)\endlink</code> | |
924 | */ | |
925 | void pop_back() { | |
926 | circular_buffer<T, Alloc>::pop_back(); | |
927 | check_high_capacity(); | |
928 | } | |
929 | ||
930 | //! Remove the first element from the space optimized circular buffer. | |
931 | /*! | |
932 | \pre <code>!empty()</code> | |
933 | \post The first element is removed from the <code>circular_buffer_space_optimized</code>.<br><br> | |
934 | The amount of allocated memory in the internal buffer may be predictively decreased. | |
935 | \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is | |
936 | used). | |
937 | \par Exception Safety | |
938 | Basic. | |
939 | \par Iterator Invalidation | |
940 | Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators | |
941 | equal to <code>end()</code>). | |
942 | \par Complexity | |
943 | Linear (in the size of the <code>circular_buffer_space_optimized</code>). | |
944 | \sa <code>pop_back()</code>, <code>\link push_back() push_back(const_reference)\endlink</code>, | |
945 | <code>\link push_front() push_front(const_reference)\endlink</code> | |
946 | */ | |
947 | void pop_front() { | |
948 | circular_buffer<T, Alloc>::pop_front(); | |
949 | check_high_capacity(); | |
950 | } | |
951 | ||
952 | //! Insert an element at the specified position. | |
953 | /*! | |
954 | \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer_space_optimized</code> or its | |
955 | end. | |
956 | \post The <code>item</code> will be inserted at the position <code>pos</code>.<br> | |
957 | If the <code>circular_buffer_space_optimized</code> is full, the first element will be overwritten. If | |
958 | the <code>circular_buffer_space_optimized</code> is full and the <code>pos</code> points to | |
959 | <code>begin()</code>, then the <code>item</code> will not be inserted. If the capacity is <code>0</code>, | |
960 | nothing will be inserted.<br><br> | |
961 | The amount of allocated memory in the internal buffer may be predictively increased. | |
962 | \param pos An iterator specifying the position where the <code>item</code> will be inserted. | |
963 | \param item The element to be inserted. | |
964 | \return Iterator to the inserted element or <code>begin()</code> if the <code>item</code> is not inserted. (See | |
965 | the <i>Effect</i>.) | |
966 | \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is | |
967 | used). | |
968 | Whatever <code>T::T(const T&)</code> throws. | |
969 | Whatever <code>T::operator = (const T&)</code> throws. | |
970 | \par Exception Safety | |
971 | Basic. | |
972 | \par Iterator Invalidation | |
973 | Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators | |
974 | equal to <code>end()</code>). | |
975 | \par Complexity | |
976 | Linear (in the size of the <code>circular_buffer_space_optimized</code>). | |
977 | \sa <code>\link insert(iterator, size_type, param_value_type) | |
978 | insert(iterator, size_type, value_type)\endlink</code>, | |
979 | <code>insert(iterator, InputIterator, InputIterator)</code>, | |
980 | <code>\link rinsert(iterator, param_value_type) rinsert(iterator, value_type)\endlink</code>, | |
981 | <code>\link rinsert(iterator, size_type, param_value_type) | |
982 | rinsert(iterator, size_type, value_type)\endlink</code>, | |
983 | <code>rinsert(iterator, InputIterator, InputIterator)</code> | |
984 | */ | |
985 | iterator insert(iterator pos, param_value_type item) { | |
986 | size_type index = pos - begin(); | |
987 | check_low_capacity(); | |
988 | return circular_buffer<T, Alloc>::insert(begin() + index, item); | |
989 | } | |
990 | ||
991 | //! Insert an element at the specified position. | |
992 | /*! | |
993 | \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer_space_optimized</code> or its | |
994 | end. | |
995 | \post The <code>item</code> will be inserted at the position <code>pos</code>.<br> | |
996 | If the <code>circular_buffer_space_optimized</code> is full, the first element will be overwritten. If | |
997 | the <code>circular_buffer_space_optimized</code> is full and the <code>pos</code> points to | |
998 | <code>begin()</code>, then the <code>item</code> will not be inserted. If the capacity is <code>0</code>, | |
999 | nothing will be inserted.<br><br> | |
1000 | The amount of allocated memory in the internal buffer may be predictively increased. | |
1001 | \param pos An iterator specifying the position where the <code>item</code> will be inserted. | |
1002 | \param item The element to be inserted. | |
1003 | \return Iterator to the inserted element or <code>begin()</code> if the <code>item</code> is not inserted. (See | |
1004 | the <i>Effect</i>.) | |
1005 | \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is | |
1006 | used). | |
1007 | Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept. | |
1008 | \par Exception Safety | |
1009 | Basic. | |
1010 | \par Iterator Invalidation | |
1011 | Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators | |
1012 | equal to <code>end()</code>). | |
1013 | \par Complexity | |
1014 | Linear (in the size of the <code>circular_buffer_space_optimized</code>). | |
1015 | \sa <code>\link insert(iterator, size_type, param_value_type) | |
1016 | insert(iterator, size_type, value_type)\endlink</code>, | |
1017 | <code>insert(iterator, InputIterator, InputIterator)</code>, | |
1018 | <code>\link rinsert(iterator, param_value_type) rinsert(iterator, value_type)\endlink</code>, | |
1019 | <code>\link rinsert(iterator, size_type, param_value_type) | |
1020 | rinsert(iterator, size_type, value_type)\endlink</code>, | |
1021 | <code>rinsert(iterator, InputIterator, InputIterator)</code> | |
1022 | */ | |
1023 | iterator insert(iterator pos, rvalue_type item) { | |
1024 | size_type index = pos - begin(); | |
1025 | check_low_capacity(); | |
1026 | return circular_buffer<T, Alloc>::insert(begin() + index, boost::move(item)); | |
1027 | } | |
1028 | ||
1029 | //! Insert an element at the specified position. | |
1030 | /*! | |
1031 | \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer_space_optimized</code> or its | |
1032 | end. | |
1033 | \post The <code>item</code> will be inserted at the position <code>pos</code>.<br> | |
1034 | If the <code>circular_buffer_space_optimized</code> is full, the first element will be overwritten. If | |
1035 | the <code>circular_buffer_space_optimized</code> is full and the <code>pos</code> points to | |
1036 | <code>begin()</code>, then the <code>item</code> will not be inserted. If the capacity is <code>0</code>, | |
1037 | nothing will be inserted.<br><br> | |
1038 | The amount of allocated memory in the internal buffer may be predictively increased. | |
1039 | \param pos An iterator specifying the position where the <code>item</code> will be inserted. | |
1040 | \return Iterator to the inserted element or <code>begin()</code> if the <code>item</code> is not inserted. (See | |
1041 | the <i>Effect</i>.) | |
1042 | \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is | |
1043 | used). | |
1044 | Whatever <code>T::T()</code> throws. | |
1045 | Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept. | |
1046 | \par Exception Safety | |
1047 | Basic. | |
1048 | \par Iterator Invalidation | |
1049 | Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators | |
1050 | equal to <code>end()</code>). | |
1051 | \par Complexity | |
1052 | Linear (in the size of the <code>circular_buffer_space_optimized</code>). | |
1053 | \sa <code>\link insert(iterator, size_type, param_value_type) | |
1054 | insert(iterator, size_type, value_type)\endlink</code>, | |
1055 | <code>insert(iterator, InputIterator, InputIterator)</code>, | |
1056 | <code>\link rinsert(iterator, param_value_type) rinsert(iterator, value_type)\endlink</code>, | |
1057 | <code>\link rinsert(iterator, size_type, param_value_type) | |
1058 | rinsert(iterator, size_type, value_type)\endlink</code>, | |
1059 | <code>rinsert(iterator, InputIterator, InputIterator)</code> | |
1060 | */ | |
1061 | iterator insert(iterator pos) { | |
1062 | size_type index = pos - begin(); | |
1063 | check_low_capacity(); | |
1064 | return circular_buffer<T, Alloc>::insert(begin() + index); | |
1065 | } | |
1066 | ||
1067 | //! Insert <code>n</code> copies of the <code>item</code> at the specified position. | |
1068 | /*! | |
1069 | \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer_space_optimized</code> or its | |
1070 | end. | |
1071 | \post The number of <code>min[n, (pos - begin()) + reserve()]</code> elements will be inserted at the position | |
1072 | <code>pos</code>.<br>The number of <code>min[pos - begin(), max[0, n - reserve()]]</code> elements will | |
1073 | be overwritten at the beginning of the <code>circular_buffer_space_optimized</code>.<br>(See | |
1074 | <i>Example</i> for the explanation.)<br><br> | |
1075 | The amount of allocated memory in the internal buffer may be predictively increased. | |
1076 | \param pos An iterator specifying the position where the <code>item</code>s will be inserted. | |
1077 | \param n The number of <code>item</code>s the to be inserted. | |
1078 | \param item The element whose copies will be inserted. | |
1079 | \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is | |
1080 | used). | |
1081 | Whatever <code>T::T(const T&)</code> throws. | |
1082 | Whatever <code>T::operator = (const T&)</code> throws. | |
1083 | \par Exception Safety | |
1084 | Basic. | |
1085 | \par Iterator Invalidation | |
1086 | Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators | |
1087 | equal to <code>end()</code>). | |
1088 | \par Complexity | |
1089 | Linear (in <code>min[capacity().%capacity(), size() + n]</code>). | |
1090 | \par Example | |
1091 | Consider a <code>circular_buffer_space_optimized</code> with the capacity of 6 and the size of 4. Its | |
1092 | internal buffer may look like the one below.<br><br> | |
1093 | <code>|1|2|3|4| | |</code><br> | |
1094 | <code>p ___^</code><br><br>After inserting 5 elements at the position <code>p</code>:<br><br> | |
1095 | <code>insert(p, (size_t)5, 0);</code><br><br>actually only 4 elements get inserted and elements | |
1096 | <code>1</code> and <code>2</code> are overwritten. This is due to the fact the insert operation preserves | |
1097 | the capacity. After insertion the internal buffer looks like this:<br><br><code>|0|0|0|0|3|4|</code><br> | |
1098 | <br>For comparison if the capacity would not be preserved the internal buffer would then result in | |
1099 | <code>|1|2|0|0|0|0|0|3|4|</code>. | |
1100 | \sa <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>, | |
1101 | <code>insert(iterator, InputIterator, InputIterator)</code>, | |
1102 | <code>\link rinsert(iterator, param_value_type) rinsert(iterator, value_type)\endlink</code>, | |
1103 | <code>\link rinsert(iterator, size_type, param_value_type) | |
1104 | rinsert(iterator, size_type, value_type)\endlink</code>, | |
1105 | <code>rinsert(iterator, InputIterator, InputIterator)</code> | |
1106 | */ | |
1107 | void insert(iterator pos, size_type n, param_value_type item) { | |
1108 | size_type index = pos - begin(); | |
1109 | check_low_capacity(n); | |
1110 | circular_buffer<T, Alloc>::insert(begin() + index, n, item); | |
1111 | } | |
1112 | ||
1113 | //! Insert the range <code>[first, last)</code> at the specified position. | |
1114 | /*! | |
1115 | \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer_space_optimized</code> or its | |
1116 | end.<br>Valid range <code>[first, last)</code> where <code>first</code> and <code>last</code> meet the | |
1117 | requirements of an <a href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>. | |
1118 | \post Elements from the range | |
1119 | <code>[first + max[0, distance(first, last) - (pos - begin()) - reserve()], last)</code> will be | |
1120 | inserted at the position <code>pos</code>.<br>The number of <code>min[pos - begin(), max[0, | |
1121 | distance(first, last) - reserve()]]</code> elements will be overwritten at the beginning of the | |
1122 | <code>circular_buffer_space_optimized</code>.<br>(See <i>Example</i> for the explanation.)<br><br> | |
1123 | The amount of allocated memory in the internal buffer may be predictively increased. | |
1124 | \param pos An iterator specifying the position where the range will be inserted. | |
1125 | \param first The beginning of the range to be inserted. | |
1126 | \param last The end of the range to be inserted. | |
1127 | \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is | |
1128 | used). | |
1129 | Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept. | |
1130 | \par Exception Safety | |
1131 | Basic. | |
1132 | \par Iterator Invalidation | |
1133 | Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators | |
1134 | equal to <code>end()</code>). | |
1135 | \par Complexity | |
1136 | Linear (in <code>[size() + std::distance(first, last)]</code>; in | |
1137 | <code>min[capacity().%capacity(), size() + std::distance(first, last)]</code> if the | |
1138 | <code>InputIterator</code> is a | |
1139 | <a href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">RandomAccessIterator</a>). | |
1140 | \par Example | |
1141 | Consider a <code>circular_buffer_space_optimized</code> with the capacity of 6 and the size of 4. Its | |
1142 | internal buffer may look like the one below.<br><br> | |
1143 | <code>|1|2|3|4| | |</code><br> | |
1144 | <code>p ___^</code><br><br>After inserting a range of elements at the position <code>p</code>:<br><br> | |
1145 | <code>int array[] = { 5, 6, 7, 8, 9 };</code><br><code>insert(p, array, array + 5);</code><br><br> | |
1146 | actually only elements <code>6</code>, <code>7</code>, <code>8</code> and <code>9</code> from the | |
1147 | specified range get inserted and elements <code>1</code> and <code>2</code> are overwritten. This is due | |
1148 | to the fact the insert operation preserves the capacity. After insertion the internal buffer looks like | |
1149 | this:<br><br><code>|6|7|8|9|3|4|</code><br><br>For comparison if the capacity would not be preserved the | |
1150 | internal buffer would then result in <code>|1|2|5|6|7|8|9|3|4|</code>. | |
1151 | \sa <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>, | |
1152 | <code>\link insert(iterator, size_type, param_value_type) | |
1153 | insert(iterator, size_type, value_type)\endlink</code>, <code>\link rinsert(iterator, param_value_type) | |
1154 | rinsert(iterator, value_type)\endlink</code>, <code>\link rinsert(iterator, size_type, param_value_type) | |
1155 | rinsert(iterator, size_type, value_type)\endlink</code>, | |
1156 | <code>rinsert(iterator, InputIterator, InputIterator)</code> | |
1157 | */ | |
1158 | template <class InputIterator> | |
1159 | void insert(iterator pos, InputIterator first, InputIterator last) { | |
1160 | insert(pos, first, last, is_integral<InputIterator>()); | |
1161 | } | |
1162 | ||
1163 | //! Insert an element before the specified position. | |
1164 | /*! | |
1165 | \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer_space_optimized</code> or its | |
1166 | end. | |
1167 | \post The <code>item</code> will be inserted before the position <code>pos</code>.<br> | |
1168 | If the <code>circular_buffer_space_optimized</code> is full, the last element will be overwritten. If the | |
1169 | <code>circular_buffer_space_optimized</code> is full and the <code>pos</code> points to | |
1170 | <code>end()</code>, then the <code>item</code> will not be inserted. If the capacity is <code>0</code>, | |
1171 | nothing will be inserted.<br><br> | |
1172 | The amount of allocated memory in the internal buffer may be predictively increased. | |
1173 | \param pos An iterator specifying the position before which the <code>item</code> will be inserted. | |
1174 | \param item The element to be inserted. | |
1175 | \return Iterator to the inserted element or <code>end()</code> if the <code>item</code> is not inserted. (See | |
1176 | the <i>Effect</i>.) | |
1177 | \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is | |
1178 | used). | |
1179 | Whatever <code>T::T(const T&)</code> throws. | |
1180 | Whatever <code>T::operator = (const T&)</code> throws. | |
1181 | \par Exception Safety | |
1182 | Basic. | |
1183 | \par Iterator Invalidation | |
1184 | Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators | |
1185 | equal to <code>end()</code>). | |
1186 | \par Complexity | |
1187 | Linear (in the size of the <code>circular_buffer_space_optimized</code>). | |
1188 | \sa <code>\link rinsert(iterator, size_type, param_value_type) | |
1189 | rinsert(iterator, size_type, value_type)\endlink</code>, | |
1190 | <code>rinsert(iterator, InputIterator, InputIterator)</code>, | |
1191 | <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>, | |
1192 | <code>\link insert(iterator, size_type, param_value_type) | |
1193 | insert(iterator, size_type, value_type)\endlink</code>, | |
1194 | <code>insert(iterator, InputIterator, InputIterator)</code> | |
1195 | */ | |
1196 | iterator rinsert(iterator pos, param_value_type item) { | |
1197 | size_type index = pos - begin(); | |
1198 | check_low_capacity(); | |
1199 | return circular_buffer<T, Alloc>::rinsert(begin() + index, item); | |
1200 | } | |
1201 | ||
1202 | //! Insert an element before the specified position. | |
1203 | /*! | |
1204 | \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer_space_optimized</code> or its | |
1205 | end. | |
1206 | \post The <code>item</code> will be inserted before the position <code>pos</code>.<br> | |
1207 | If the <code>circular_buffer_space_optimized</code> is full, the last element will be overwritten. If the | |
1208 | <code>circular_buffer_space_optimized</code> is full and the <code>pos</code> points to | |
1209 | <code>end()</code>, then the <code>item</code> will not be inserted. If the capacity is <code>0</code>, | |
1210 | nothing will be inserted.<br><br> | |
1211 | The amount of allocated memory in the internal buffer may be predictively increased. | |
1212 | \param pos An iterator specifying the position before which the <code>item</code> will be inserted. | |
1213 | \param item The element to be inserted. | |
1214 | \return Iterator to the inserted element or <code>end()</code> if the <code>item</code> is not inserted. (See | |
1215 | the <i>Effect</i>.) | |
1216 | \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is | |
1217 | used). | |
1218 | Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept. | |
1219 | \par Exception Safety | |
1220 | Basic. | |
1221 | \par Iterator Invalidation | |
1222 | Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators | |
1223 | equal to <code>end()</code>). | |
1224 | \par Complexity | |
1225 | Linear (in the size of the <code>circular_buffer_space_optimized</code>). | |
1226 | \sa <code>\link rinsert(iterator, size_type, param_value_type) | |
1227 | rinsert(iterator, size_type, value_type)\endlink</code>, | |
1228 | <code>rinsert(iterator, InputIterator, InputIterator)</code>, | |
1229 | <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>, | |
1230 | <code>\link insert(iterator, size_type, param_value_type) | |
1231 | insert(iterator, size_type, value_type)\endlink</code>, | |
1232 | <code>insert(iterator, InputIterator, InputIterator)</code> | |
1233 | */ | |
1234 | iterator rinsert(iterator pos, rvalue_type item) { | |
1235 | size_type index = pos - begin(); | |
1236 | check_low_capacity(); | |
1237 | return circular_buffer<T, Alloc>::rinsert(begin() + index, boost::move(item)); | |
1238 | } | |
1239 | ||
1240 | //! Insert an element before the specified position. | |
1241 | /*! | |
1242 | \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer_space_optimized</code> or its | |
1243 | end. | |
1244 | \post The <code>item</code> will be inserted before the position <code>pos</code>.<br> | |
1245 | If the <code>circular_buffer_space_optimized</code> is full, the last element will be overwritten. If the | |
1246 | <code>circular_buffer_space_optimized</code> is full and the <code>pos</code> points to | |
1247 | <code>end()</code>, then the <code>item</code> will not be inserted. If the capacity is <code>0</code>, | |
1248 | nothing will be inserted.<br><br> | |
1249 | The amount of allocated memory in the internal buffer may be predictively increased. | |
1250 | \param pos An iterator specifying the position before which the <code>item</code> will be inserted. | |
1251 | \return Iterator to the inserted element or <code>end()</code> if the <code>item</code> is not inserted. (See | |
1252 | the <i>Effect</i>.) | |
1253 | \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is | |
1254 | used). | |
1255 | Whatever <code>T::T()</code> throws. | |
1256 | Whatever <code>T::T(const T&)</code> throws or nothing if <code>T::T(T&&)</code> is noexcept. | |
1257 | \par Exception Safety | |
1258 | Basic. | |
1259 | \par Iterator Invalidation | |
1260 | Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators | |
1261 | equal to <code>end()</code>). | |
1262 | \par Complexity | |
1263 | Linear (in the size of the <code>circular_buffer_space_optimized</code>). | |
1264 | \sa <code>\link rinsert(iterator, size_type, param_value_type) | |
1265 | rinsert(iterator, size_type, value_type)\endlink</code>, | |
1266 | <code>rinsert(iterator, InputIterator, InputIterator)</code>, | |
1267 | <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>, | |
1268 | <code>\link insert(iterator, size_type, param_value_type) | |
1269 | insert(iterator, size_type, value_type)\endlink</code>, | |
1270 | <code>insert(iterator, InputIterator, InputIterator)</code> | |
1271 | */ | |
1272 | iterator rinsert(iterator pos) { | |
1273 | size_type index = pos - begin(); | |
1274 | check_low_capacity(); | |
1275 | return circular_buffer<T, Alloc>::rinsert(begin() + index); | |
1276 | } | |
1277 | ||
1278 | //! Insert <code>n</code> copies of the <code>item</code> before the specified position. | |
1279 | /*! | |
1280 | \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer_space_optimized</code> or its | |
1281 | end. | |
1282 | \post The number of <code>min[n, (end() - pos) + reserve()]</code> elements will be inserted before the | |
1283 | position <code>pos</code>.<br>The number of <code>min[end() - pos, max[0, n - reserve()]]</code> elements | |
1284 | will be overwritten at the end of the <code>circular_buffer_space_optimized</code>.<br>(See | |
1285 | <i>Example</i> for the explanation.)<br><br> | |
1286 | The amount of allocated memory in the internal buffer may be predictively increased. | |
1287 | \param pos An iterator specifying the position where the <code>item</code>s will be inserted. | |
1288 | \param n The number of <code>item</code>s the to be inserted. | |
1289 | \param item The element whose copies will be inserted. | |
1290 | \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is | |
1291 | used). | |
1292 | Whatever <code>T::T(const T&)</code> throws. | |
1293 | Whatever <code>T::operator = (const T&)</code> throws. | |
1294 | \par Exception Safety | |
1295 | Basic. | |
1296 | \par Iterator Invalidation | |
1297 | Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators | |
1298 | equal to <code>end()</code>). | |
1299 | \par Complexity | |
1300 | Linear (in <code>min[capacity().%capacity(), size() + n]</code>). | |
1301 | \par Example | |
1302 | Consider a <code>circular_buffer_space_optimized</code> with the capacity of 6 and the size of 4. Its | |
1303 | internal buffer may look like the one below.<br><br> | |
1304 | <code>|1|2|3|4| | |</code><br> | |
1305 | <code>p ___^</code><br><br>After inserting 5 elements before the position <code>p</code>:<br><br> | |
1306 | <code>rinsert(p, (size_t)5, 0);</code><br><br>actually only 4 elements get inserted and elements | |
1307 | <code>3</code> and <code>4</code> are overwritten. This is due to the fact the rinsert operation preserves | |
1308 | the capacity. After insertion the internal buffer looks like this:<br><br><code>|1|2|0|0|0|0|</code><br> | |
1309 | <br>For comparison if the capacity would not be preserved the internal buffer would then result in | |
1310 | <code>|1|2|0|0|0|0|0|3|4|</code>. | |
1311 | \sa <code>\link rinsert(iterator, param_value_type) rinsert(iterator, value_type)\endlink</code>, | |
1312 | <code>rinsert(iterator, InputIterator, InputIterator)</code>, | |
1313 | <code>\link insert(iterator, param_value_type) insert(iterator, value_type)\endlink</code>, | |
1314 | <code>\link insert(iterator, size_type, param_value_type) | |
1315 | insert(iterator, size_type, value_type)\endlink</code>, | |
1316 | <code>insert(iterator, InputIterator, InputIterator)</code> | |
1317 | */ | |
1318 | void rinsert(iterator pos, size_type n, param_value_type item) { | |
1319 | size_type index = pos - begin(); | |
1320 | check_low_capacity(n); | |
1321 | circular_buffer<T, Alloc>::rinsert(begin() + index, n, item); | |
1322 | } | |
1323 | ||
1324 | //! Insert the range <code>[first, last)</code> before the specified position. | |
1325 | /*! | |
1326 | \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer_space_optimized</code> or its | |
1327 | end.<br> | |
1328 | Valid range <code>[first, last)</code> where <code>first</code> and <code>last</code> meet the | |
1329 | requirements of an <a href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>. | |
1330 | \post Elements from the range | |
1331 | <code>[first, last - max[0, distance(first, last) - (end() - pos) - reserve()])</code> will be inserted | |
1332 | before the position <code>pos</code>.<br>The number of <code>min[end() - pos, max[0, | |
1333 | distance(first, last) - reserve()]]</code> elements will be overwritten at the end of the | |
1334 | <code>circular_buffer</code>.<br>(See <i>Example</i> for the explanation.)<br><br> | |
1335 | The amount of allocated memory in the internal buffer may be predictively increased. | |
1336 | \param pos An iterator specifying the position where the range will be inserted. | |
1337 | \param first The beginning of the range to be inserted. | |
1338 | \param last The end of the range to be inserted. | |
1339 | \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is | |
1340 | used). | |
1341 | Whatever <code>T::T(const T&)</code> throws. | |
1342 | Whatever <code>T::operator = (const T&)</code> throws. | |
1343 | \par Exception Safety | |
1344 | Basic. | |
1345 | \par Iterator Invalidation | |
1346 | Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators | |
1347 | equal to <code>end()</code>). | |
1348 | \par Complexity | |
1349 | Linear (in <code>[size() + std::distance(first, last)]</code>; in | |
1350 | <code>min[capacity().%capacity(), size() + std::distance(first, last)]</code> if the | |
1351 | <code>InputIterator</code> is a | |
1352 | <a href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">RandomAccessIterator</a>). | |
1353 | \par Example | |
1354 | Consider a <code>circular_buffer_space_optimized</code> with the capacity of 6 and the size of 4. Its | |
1355 | internal buffer may look like the one below.<br><br> | |
1356 | <code>|1|2|3|4| | |</code><br> | |
1357 | <code>p ___^</code><br><br>After inserting a range of elements before the position <code>p</code>:<br><br> | |
1358 | <code>int array[] = { 5, 6, 7, 8, 9 };</code><br><code>insert(p, array, array + 5);</code><br><br> | |
1359 | actually only elements <code>5</code>, <code>6</code>, <code>7</code> and <code>8</code> from the | |
1360 | specified range get inserted and elements <code>3</code> and <code>4</code> are overwritten. This is due | |
1361 | to the fact the rinsert operation preserves the capacity. After insertion the internal buffer looks like | |
1362 | this:<br><br><code>|1|2|5|6|7|8|</code><br><br>For comparison if the capacity would not be preserved the | |
1363 | internal buffer would then result in <code>|1|2|5|6|7|8|9|3|4|</code>. | |
1364 | \sa <code>\link rinsert(iterator, param_value_type) rinsert(iterator, value_type)\endlink</code>, | |
1365 | <code>\link rinsert(iterator, size_type, param_value_type) | |
1366 | rinsert(iterator, size_type, value_type)\endlink</code>, <code>\link insert(iterator, param_value_type) | |
1367 | insert(iterator, value_type)\endlink</code>, <code>\link insert(iterator, size_type, param_value_type) | |
1368 | insert(iterator, size_type, value_type)\endlink</code>, | |
1369 | <code>insert(iterator, InputIterator, InputIterator)</code> | |
1370 | */ | |
1371 | template <class InputIterator> | |
1372 | void rinsert(iterator pos, InputIterator first, InputIterator last) { | |
1373 | rinsert(pos, first, last, is_integral<InputIterator>()); | |
1374 | } | |
1375 | ||
1376 | //! Remove an element at the specified position. | |
1377 | /*! | |
1378 | \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer_space_optimized</code> (but not | |
1379 | an <code>end()</code>). | |
1380 | \post The element at the position <code>pos</code> is removed.<br><br> | |
1381 | The amount of allocated memory in the internal buffer may be predictively decreased. | |
1382 | \param pos An iterator pointing at the element to be removed. | |
1383 | \return Iterator to the first element remaining beyond the removed element or <code>end()</code> if no such | |
1384 | element exists. | |
1385 | \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is | |
1386 | used). | |
1387 | Whatever <code>T::operator = (const T&)</code> throws or | |
1388 | nothing if <code>T::operator = (T&&)</code> is noexcept. | |
1389 | \par Exception Safety | |
1390 | Basic. | |
1391 | \par Iterator Invalidation | |
1392 | Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators | |
1393 | equal to <code>end()</code>). | |
1394 | \par Complexity | |
1395 | Linear (in the size of the <code>circular_buffer_space_optimized</code>). | |
1396 | \sa <code>erase(iterator, iterator)</code>, <code>rerase(iterator)</code>, | |
1397 | <code>rerase(iterator, iterator)</code>, <code>clear()</code> | |
1398 | */ | |
1399 | iterator erase(iterator pos) { | |
1400 | iterator it = circular_buffer<T, Alloc>::erase(pos); | |
1401 | size_type index = it - begin(); | |
1402 | check_high_capacity(); | |
1403 | return begin() + index; | |
1404 | } | |
1405 | ||
1406 | //! Erase the range <code>[first, last)</code>. | |
1407 | /*! | |
1408 | \pre Valid range <code>[first, last)</code>. | |
1409 | \post The elements from the range <code>[first, last)</code> are removed. (If <code>first == last</code> | |
1410 | nothing is removed.)<br><br> | |
1411 | The amount of allocated memory in the internal buffer may be predictively decreased. | |
1412 | \param first The beginning of the range to be removed. | |
1413 | \param last The end of the range to be removed. | |
1414 | \return Iterator to the first element remaining beyond the removed elements or <code>end()</code> if no such | |
1415 | element exists. | |
1416 | \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is | |
1417 | used). | |
1418 | Whatever <code>T::operator = (const T&)</code> throws or | |
1419 | nothing if <code>T::operator = (T&&)</code> is noexcept. | |
1420 | \par Exception Safety | |
1421 | Basic. | |
1422 | \par Iterator Invalidation | |
1423 | Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators | |
1424 | equal to <code>end()</code>). | |
1425 | \par Complexity | |
1426 | Linear (in the size of the <code>circular_buffer_space_optimized</code>). | |
1427 | \sa <code>erase(iterator)</code>, <code>rerase(iterator)</code>, <code>rerase(iterator, iterator)</code>, | |
1428 | <code>clear()</code> | |
1429 | */ | |
1430 | iterator erase(iterator first, iterator last) { | |
1431 | iterator it = circular_buffer<T, Alloc>::erase(first, last); | |
1432 | size_type index = it - begin(); | |
1433 | check_high_capacity(); | |
1434 | return begin() + index; | |
1435 | } | |
1436 | ||
1437 | //! Remove an element at the specified position. | |
1438 | /*! | |
1439 | \pre <code>pos</code> is a valid iterator pointing to the <code>circular_buffer_space_optimized</code> (but not | |
1440 | an <code>end()</code>).<br><br> | |
1441 | The amount of allocated memory in the internal buffer may be predictively decreased. | |
1442 | \post The element at the position <code>pos</code> is removed. | |
1443 | \param pos An iterator pointing at the element to be removed. | |
1444 | \return Iterator to the first element remaining in front of the removed element or <code>begin()</code> if no | |
1445 | such element exists. | |
1446 | \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is | |
1447 | used). | |
1448 | Whatever <code>T::operator = (const T&)</code> throws or | |
1449 | nothing if <code>T::operator = (T&&)</code> is noexcept. | |
1450 | \par Exception Safety | |
1451 | Basic. | |
1452 | \par Iterator Invalidation | |
1453 | Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators | |
1454 | equal to <code>end()</code>). | |
1455 | \par Complexity | |
1456 | Linear (in the size of the <code>circular_buffer_space_optimized</code>). | |
1457 | \note Basically there is no difference between <code>erase(iterator)</code> and this method. It is implemented | |
1458 | only for consistency with the base <code>circular_buffer</code>. | |
1459 | \sa <code>erase(iterator)</code>, <code>erase(iterator, iterator)</code>, | |
1460 | <code>rerase(iterator, iterator)</code>, <code>clear()</code> | |
1461 | */ | |
1462 | iterator rerase(iterator pos) { | |
1463 | iterator it = circular_buffer<T, Alloc>::rerase(pos); | |
1464 | size_type index = it - begin(); | |
1465 | check_high_capacity(); | |
1466 | return begin() + index; | |
1467 | } | |
1468 | ||
1469 | //! Erase the range <code>[first, last)</code>. | |
1470 | /*! | |
1471 | \pre Valid range <code>[first, last)</code>. | |
1472 | \post The elements from the range <code>[first, last)</code> are removed. (If <code>first == last</code> | |
1473 | nothing is removed.)<br><br> | |
1474 | The amount of allocated memory in the internal buffer may be predictively decreased. | |
1475 | \param first The beginning of the range to be removed. | |
1476 | \param last The end of the range to be removed. | |
1477 | \return Iterator to the first element remaining in front of the removed elements or <code>begin()</code> if no | |
1478 | such element exists. | |
1479 | \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is | |
1480 | used). | |
1481 | Whatever <code>T::operator = (const T&)</code> throws or | |
1482 | nothing if <code>T::operator = (T&&)</code> is noexcept. | |
1483 | \par Exception Safety | |
1484 | Basic. | |
1485 | \par Iterator Invalidation | |
1486 | Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators | |
1487 | equal to <code>end()</code>). | |
1488 | \par Complexity | |
1489 | Linear (in the size of the <code>circular_buffer_space_optimized</code>). | |
1490 | \note Basically there is no difference between <code>erase(iterator, iterator)</code> and this method. It is | |
1491 | implemented only for consistency with the base | |
1492 | <code><circular_buffer</code>. | |
1493 | \sa <code>erase(iterator)</code>, <code>erase(iterator, iterator)</code>, <code>rerase(iterator)</code>, | |
1494 | <code>clear()</code> | |
1495 | */ | |
1496 | iterator rerase(iterator first, iterator last) { | |
1497 | iterator it = circular_buffer<T, Alloc>::rerase(first, last); | |
1498 | size_type index = it - begin(); | |
1499 | check_high_capacity(); | |
1500 | return begin() + index; | |
1501 | } | |
1502 | ||
1503 | //! Remove all stored elements from the space optimized circular buffer. | |
1504 | /*! | |
1505 | \post <code>size() == 0</code><br><br> | |
1506 | The amount of allocated memory in the internal buffer may be predictively decreased. | |
1507 | \throws "An allocation error" if memory is exhausted (<code>std::bad_alloc</code> if the standard allocator is | |
1508 | used). | |
1509 | \par Exception Safety | |
1510 | Basic. | |
1511 | \par Iterator Invalidation | |
1512 | Invalidates all iterators pointing to the <code>circular_buffer_space_optimized</code> (except iterators | |
1513 | equal to <code>end()</code>). | |
1514 | \par Complexity | |
1515 | Linear (in the size of the <code>circular_buffer_space_optimized</code>). | |
1516 | \sa <code>~circular_buffer_space_optimized()</code>, <code>erase(iterator)</code>, | |
1517 | <code>erase(iterator, iterator)</code>, <code>rerase(iterator)</code>, | |
1518 | <code>rerase(iterator, iterator)</code> | |
1519 | */ | |
1520 | void clear() { erase(begin(), end()); } | |
1521 | ||
1522 | private: | |
1523 | // Helper methods | |
1524 | ||
1525 | //! Adjust the amount of allocated memory. | |
1526 | void adjust_min_capacity() { | |
1527 | if (m_capacity_ctrl.min_capacity() > circular_buffer<T, Alloc>::capacity()) | |
1528 | circular_buffer<T, Alloc>::set_capacity(m_capacity_ctrl.min_capacity()); | |
1529 | else | |
1530 | check_high_capacity(); | |
1531 | } | |
1532 | ||
1533 | //! Ensure the reserve for possible growth up. | |
1534 | size_type ensure_reserve(size_type new_capacity, size_type buffer_size) const { | |
1535 | if (buffer_size + new_capacity / 5 >= new_capacity) | |
1536 | new_capacity *= 2; // ensure at least 20% reserve | |
1537 | if (new_capacity > m_capacity_ctrl) | |
1538 | return m_capacity_ctrl; | |
1539 | return new_capacity; | |
1540 | } | |
1541 | ||
1542 | //! Check for low capacity. | |
1543 | /* | |
1544 | \post If the capacity is low it will be increased. | |
1545 | */ | |
1546 | void check_low_capacity(size_type n = 1) { | |
1547 | size_type new_size = size() + n; | |
1548 | size_type new_capacity = circular_buffer<T, Alloc>::capacity(); | |
1549 | if (new_size > new_capacity) { | |
1550 | if (new_capacity == 0) | |
1551 | new_capacity = 1; | |
1552 | for (; new_size > new_capacity; new_capacity *= 2) {} | |
1553 | circular_buffer<T, Alloc>::set_capacity( | |
1554 | ensure_reserve(new_capacity, new_size)); | |
1555 | } | |
1556 | #if BOOST_CB_ENABLE_DEBUG | |
1557 | this->invalidate_iterators_except(end()); | |
1558 | #endif | |
1559 | } | |
1560 | ||
1561 | //! Check for high capacity. | |
1562 | /* | |
1563 | \post If the capacity is high it will be decreased. | |
1564 | */ | |
1565 | void check_high_capacity() { | |
1566 | size_type new_capacity = circular_buffer<T, Alloc>::capacity(); | |
1567 | while (new_capacity / 3 >= size()) { // (new_capacity / 3) -> avoid oscillations | |
1568 | new_capacity /= 2; | |
1569 | if (new_capacity <= m_capacity_ctrl.min_capacity()) { | |
1570 | new_capacity = m_capacity_ctrl.min_capacity(); | |
1571 | break; | |
1572 | } | |
1573 | } | |
1574 | circular_buffer<T, Alloc>::set_capacity( | |
1575 | ensure_reserve(new_capacity, size())); | |
1576 | #if BOOST_CB_ENABLE_DEBUG | |
1577 | this->invalidate_iterators_except(end()); | |
1578 | #endif | |
1579 | } | |
1580 | ||
1581 | //! Specialized method for reducing the capacity. | |
1582 | void reduce_capacity(const true_type&) { | |
1583 | circular_buffer<T, Alloc>::set_capacity((std::max)(m_capacity_ctrl.min_capacity(), size())); | |
1584 | } | |
1585 | ||
1586 | //! Specialized method for reducing the capacity. | |
1587 | void reduce_capacity(const false_type&) {} | |
1588 | ||
1589 | //! Determine the initial capacity. | |
1590 | static size_type init_capacity(const capacity_type& capacity_ctrl, size_type n) { | |
1591 | BOOST_CB_ASSERT(capacity_ctrl.capacity() >= n); // check for capacity lower than n | |
1592 | return (std::max)(capacity_ctrl.min_capacity(), n); | |
1593 | } | |
1594 | ||
1595 | //! Specialized method for determining the initial capacity. | |
1596 | template <class IntegralType> | |
1597 | static size_type init_capacity(const capacity_type& capacity_ctrl, IntegralType n, IntegralType, | |
1598 | const true_type&) { | |
1599 | return init_capacity(capacity_ctrl, static_cast<size_type>(n)); | |
1600 | } | |
1601 | ||
1602 | //! Specialized method for determining the initial capacity. | |
1603 | template <class Iterator> | |
1604 | static size_type init_capacity(const capacity_type& capacity_ctrl, Iterator first, Iterator last, | |
1605 | const false_type&) { | |
1606 | BOOST_CB_IS_CONVERTIBLE(Iterator, value_type); // check for invalid iterator type | |
1607 | #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x581)) | |
1608 | return init_capacity(capacity_ctrl, first, last, iterator_category<Iterator>::type()); | |
1609 | #else | |
1610 | return init_capacity( | |
1611 | capacity_ctrl, first, last, BOOST_DEDUCED_TYPENAME iterator_category<Iterator>::type()); | |
1612 | #endif | |
1613 | } | |
1614 | ||
1615 | //! Specialized method for determining the initial capacity. | |
1616 | template <class InputIterator> | |
1617 | static size_type init_capacity(const capacity_type& capacity_ctrl, InputIterator, InputIterator, | |
1618 | const std::input_iterator_tag&) { | |
1619 | return capacity_ctrl.capacity(); | |
1620 | } | |
1621 | ||
1622 | //! Specialized method for determining the initial capacity. | |
1623 | template <class ForwardIterator> | |
1624 | static size_type init_capacity(const capacity_type& capacity_ctrl, ForwardIterator first, ForwardIterator last, | |
1625 | const std::forward_iterator_tag&) { | |
1626 | BOOST_CB_ASSERT(std::distance(first, last) >= 0); // check for wrong range | |
1627 | return (std::max)(capacity_ctrl.min_capacity(), | |
1628 | (std::min)(capacity_ctrl.capacity(), static_cast<size_type>(std::distance(first, last)))); | |
1629 | } | |
1630 | ||
1631 | //! Specialized insert method. | |
1632 | template <class IntegralType> | |
1633 | void insert(const iterator& pos, IntegralType n, IntegralType item, const true_type&) { | |
1634 | insert(pos, static_cast<size_type>(n), static_cast<value_type>(item)); | |
1635 | } | |
1636 | ||
1637 | //! Specialized insert method. | |
1638 | template <class Iterator> | |
1639 | void insert(const iterator& pos, Iterator first, Iterator last, const false_type&) { | |
1640 | size_type index = pos - begin(); | |
1641 | check_low_capacity(std::distance(first, last)); | |
1642 | circular_buffer<T, Alloc>::insert(begin() + index, first, last); | |
1643 | } | |
1644 | ||
1645 | //! Specialized rinsert method. | |
1646 | template <class IntegralType> | |
1647 | void rinsert(const iterator& pos, IntegralType n, IntegralType item, const true_type&) { | |
1648 | rinsert(pos, static_cast<size_type>(n), static_cast<value_type>(item)); | |
1649 | } | |
1650 | ||
1651 | //! Specialized rinsert method. | |
1652 | template <class Iterator> | |
1653 | void rinsert(const iterator& pos, Iterator first, Iterator last, const false_type&) { | |
1654 | size_type index = pos - begin(); | |
1655 | check_low_capacity(std::distance(first, last)); | |
1656 | circular_buffer<T, Alloc>::rinsert(begin() + index, first, last); | |
1657 | } | |
1658 | }; | |
1659 | ||
1660 | // Non-member functions | |
1661 | ||
1662 | //! Test two space optimized circular buffers for equality. | |
1663 | template <class T, class Alloc> | |
1664 | inline bool operator == (const circular_buffer_space_optimized<T, Alloc>& lhs, | |
1665 | const circular_buffer_space_optimized<T, Alloc>& rhs) { | |
1666 | return lhs.size() == rhs.size() && | |
1667 | std::equal(lhs.begin(), lhs.end(), rhs.begin()); | |
1668 | } | |
1669 | ||
1670 | //! Lexicographical comparison. | |
1671 | template <class T, class Alloc> | |
1672 | inline bool operator < (const circular_buffer_space_optimized<T, Alloc>& lhs, | |
1673 | const circular_buffer_space_optimized<T, Alloc>& rhs) { | |
1674 | return std::lexicographical_compare( | |
1675 | lhs.begin(), lhs.end(), rhs.begin(), rhs.end()); | |
1676 | } | |
1677 | ||
1678 | #if !defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING) || BOOST_WORKAROUND(BOOST_MSVC, BOOST_TESTED_AT(1310)) | |
1679 | ||
1680 | //! Test two space optimized circular buffers for non-equality. | |
1681 | template <class T, class Alloc> | |
1682 | inline bool operator != (const circular_buffer_space_optimized<T, Alloc>& lhs, | |
1683 | const circular_buffer_space_optimized<T, Alloc>& rhs) { | |
1684 | return !(lhs == rhs); | |
1685 | } | |
1686 | ||
1687 | //! Lexicographical comparison. | |
1688 | template <class T, class Alloc> | |
1689 | inline bool operator > (const circular_buffer_space_optimized<T, Alloc>& lhs, | |
1690 | const circular_buffer_space_optimized<T, Alloc>& rhs) { | |
1691 | return rhs < lhs; | |
1692 | } | |
1693 | ||
1694 | //! Lexicographical comparison. | |
1695 | template <class T, class Alloc> | |
1696 | inline bool operator <= (const circular_buffer_space_optimized<T, Alloc>& lhs, | |
1697 | const circular_buffer_space_optimized<T, Alloc>& rhs) { | |
1698 | return !(rhs < lhs); | |
1699 | } | |
1700 | ||
1701 | //! Lexicographical comparison. | |
1702 | template <class T, class Alloc> | |
1703 | inline bool operator >= (const circular_buffer_space_optimized<T, Alloc>& lhs, | |
1704 | const circular_buffer_space_optimized<T, Alloc>& rhs) { | |
1705 | return !(lhs < rhs); | |
1706 | } | |
1707 | ||
1708 | //! Swap the contents of two space optimized circular buffers. | |
1709 | template <class T, class Alloc> | |
1710 | inline void swap(circular_buffer_space_optimized<T, Alloc>& lhs, | |
1711 | circular_buffer_space_optimized<T, Alloc>& rhs) BOOST_NOEXCEPT { | |
1712 | lhs.swap(rhs); | |
1713 | } | |
1714 | ||
1715 | #endif // #if !defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING) || BOOST_WORKAROUND(BOOST_MSVC, BOOST_TESTED_AT(1310)) | |
1716 | ||
1717 | } // namespace boost | |
1718 | ||
1719 | #endif // #if !defined(BOOST_CIRCULAR_BUFFER_SPACE_OPTIMIZED_HPP) |