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/config/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="https://www.boost.org/sgi/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="https://www.boost.org/sgi/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="https://www.boost.org/sgi/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 std::iterator_traits<InputIterator>::iterator_category, 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()) // temporary 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="https://www.boost.org/sgi/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="https://www.boost.org/sgi/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="https://www.boost.org/sgi/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="https://www.boost.org/sgi/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="https://www.boost.org/sgi/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="https://www.boost.org/sgi/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="https://www.boost.org/sgi/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	/*! INTERNAL ONLY */
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	/*! INTERNAL ONLY */
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	/*! INTERNAL ONLY */
1543	void check_low_capacity(size_type n = 1) {
1544	size_type new_size = size() + n;
1545	size_type new_capacity = circular_buffer<T, Alloc>::capacity();
1546	if (new_size > new_capacity) {
1547	if (new_capacity == 0)
1548	new_capacity = 1;
1549	for (; new_size > new_capacity; new_capacity *= 2) {}
1550	circular_buffer<T, Alloc>::set_capacity(
1551	ensure_reserve(new_capacity, buffer_size: new_size));
1552	}
1553	#if BOOST_CB_ENABLE_DEBUG
1554	this->invalidate_iterators_except(end());
1555	#endif
1556	}
1557
1558	/*! INTERNAL ONLY */
1559	void check_high_capacity() {
1560	size_type new_capacity = circular_buffer<T, Alloc>::capacity();
1561	while (new_capacity / 3 >= size()) { // (new_capacity / 3) -> avoid oscillations
1562	new_capacity /= 2;
1563	if (new_capacity <= m_capacity_ctrl.min_capacity()) {
1564	new_capacity = m_capacity_ctrl.min_capacity();
1565	break;
1566	}
1567	}
1568	circular_buffer<T, Alloc>::set_capacity(
1569	ensure_reserve(new_capacity, buffer_size: size()));
1570	#if BOOST_CB_ENABLE_DEBUG
1571	this->invalidate_iterators_except(end());
1572	#endif
1573	}
1574
1575	/*! INTERNAL ONLY */
1576	void reduce_capacity(const true_type&) {
1577	circular_buffer<T, Alloc>::set_capacity((std::max)(m_capacity_ctrl.min_capacity(), size()));
1578	}
1579
1580	/*! INTERNAL ONLY */
1581	void reduce_capacity(const false_type&) {}
1582
1583	/*! INTERNAL ONLY */
1584	static size_type init_capacity(const capacity_type& capacity_ctrl, size_type n) {
1585	BOOST_CB_ASSERT(capacity_ctrl.capacity() >= n); // check for capacity lower than n
1586	return (std::max)(capacity_ctrl.min_capacity(), n);
1587	}
1588
1589	/*! INTERNAL ONLY */
1590	template <class IntegralType>
1591	static size_type init_capacity(const capacity_type& capacity_ctrl, IntegralType n, IntegralType,
1592	const true_type&) {
1593	return init_capacity(capacity_ctrl, static_cast<size_type>(n));
1594	}
1595
1596	/*! INTERNAL ONLY */
1597	template <class Iterator>
1598	static size_type init_capacity(const capacity_type& capacity_ctrl, Iterator first, Iterator last,
1599	const false_type&) {
1600	BOOST_CB_IS_CONVERTIBLE(Iterator, value_type); // check for invalid iterator type
1601	#if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x581))
1602	return init_capacity(capacity_ctrl, first, last, std::iterator_traits<Iterator>::iterator_category());
1603	#else
1604	return init_capacity(
1605	capacity_ctrl, first, last, BOOST_DEDUCED_TYPENAME std::iterator_traits<Iterator>::iterator_category());
1606	#endif
1607	}
1608
1609	/*! INTERNAL ONLY */
1610	template <class InputIterator>
1611	static size_type init_capacity(const capacity_type& capacity_ctrl, InputIterator, InputIterator,
1612	const std::input_iterator_tag&) {
1613	return capacity_ctrl.capacity();
1614	}
1615
1616	/*! INTERNAL ONLY */
1617	template <class ForwardIterator>
1618	static size_type init_capacity(const capacity_type& capacity_ctrl, ForwardIterator first, ForwardIterator last,
1619	const std::forward_iterator_tag&) {
1620	BOOST_CB_ASSERT(std::distance(first, last) >= 0); // check for wrong range
1621	return (std::max)(capacity_ctrl.min_capacity(),
1622	(std::min)(capacity_ctrl.capacity(), static_cast<size_type>(std::distance(first, last))));
1623	}
1624
1625	/*! INTERNAL ONLY */
1626	template <class IntegralType>
1627	void insert(const iterator& pos, IntegralType n, IntegralType item, const true_type&) {
1628	insert(pos, static_cast<size_type>(n), static_cast<value_type>(item));
1629	}
1630
1631	/*! INTERNAL ONLY */
1632	template <class Iterator>
1633	void insert(const iterator& pos, Iterator first, Iterator last, const false_type&) {
1634	size_type index = pos - begin();
1635	check_low_capacity(n: std::distance(first, last));
1636	circular_buffer<T, Alloc>::insert(begin() + index, first, last);
1637	}
1638
1639	/*! INTERNAL ONLY */
1640	template <class IntegralType>
1641	void rinsert(const iterator& pos, IntegralType n, IntegralType item, const true_type&) {
1642	rinsert(pos, static_cast<size_type>(n), static_cast<value_type>(item));
1643	}
1644
1645	/*! INTERNAL ONLY */
1646	template <class Iterator>
1647	void rinsert(const iterator& pos, Iterator first, Iterator last, const false_type&) {
1648	size_type index = pos - begin();
1649	check_low_capacity(n: std::distance(first, last));
1650	circular_buffer<T, Alloc>::rinsert(begin() + index, first, last);
1651	}
1652	};
1653
1654	// Non-member functions
1655
1656	//! Test two space optimized circular buffers for equality.
1657	template <class T, class Alloc>
1658	inline bool operator == (const circular_buffer_space_optimized<T, Alloc>& lhs,
1659	const circular_buffer_space_optimized<T, Alloc>& rhs) {
1660	return lhs.size() == rhs.size() &&
1661	std::equal(lhs.begin(), lhs.end(), rhs.begin());
1662	}
1663
1664	//! Lexicographical comparison.
1665	template <class T, class Alloc>
1666	inline bool operator < (const circular_buffer_space_optimized<T, Alloc>& lhs,
1667	const circular_buffer_space_optimized<T, Alloc>& rhs) {
1668	return std::lexicographical_compare(
1669	lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
1670	}
1671
1672	#if !defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING) || BOOST_WORKAROUND(BOOST_MSVC, BOOST_TESTED_AT(1310))
1673
1674	//! Test two space optimized circular buffers for non-equality.
1675	template <class T, class Alloc>
1676	inline bool operator != (const circular_buffer_space_optimized<T, Alloc>& lhs,
1677	const circular_buffer_space_optimized<T, Alloc>& rhs) {
1678	return !(lhs == rhs);
1679	}
1680
1681	//! Lexicographical comparison.
1682	template <class T, class Alloc>
1683	inline bool operator > (const circular_buffer_space_optimized<T, Alloc>& lhs,
1684	const circular_buffer_space_optimized<T, Alloc>& rhs) {
1685	return rhs < lhs;
1686	}
1687
1688	//! Lexicographical comparison.
1689	template <class T, class Alloc>
1690	inline bool operator <= (const circular_buffer_space_optimized<T, Alloc>& lhs,
1691	const circular_buffer_space_optimized<T, Alloc>& rhs) {
1692	return !(rhs < lhs);
1693	}
1694
1695	//! Lexicographical comparison.
1696	template <class T, class Alloc>
1697	inline bool operator >= (const circular_buffer_space_optimized<T, Alloc>& lhs,
1698	const circular_buffer_space_optimized<T, Alloc>& rhs) {
1699	return !(lhs < rhs);
1700	}
1701
1702	//! Swap the contents of two space optimized circular buffers.
1703	template <class T, class Alloc>
1704	inline void swap(circular_buffer_space_optimized<T, Alloc>& lhs,
1705	circular_buffer_space_optimized<T, Alloc>& rhs) BOOST_NOEXCEPT {
1706	lhs.swap(rhs);
1707	}
1708
1709	#endif // #if !defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING) || BOOST_WORKAROUND(BOOST_MSVC, BOOST_TESTED_AT(1310))
1710
1711	} // namespace boost
1712
1713	#endif // #if !defined(BOOST_CIRCULAR_BUFFER_SPACE_OPTIMIZED_HPP)
1714