1	//////////////////////////////////////////////////////////////////////////////
2	//
3	// (C) Copyright Benedek Thaler 2015-2016
4	// (C) Copyright Ion Gaztanaga 2019-2020. Distributed under the Boost
5	// Software License, Version 1.0. (See accompanying file
6	// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
7	//
8	// See http://www.boost.org/libs/container for documentation.
9	//
10	//////////////////////////////////////////////////////////////////////////////
11
12	#ifndef BOOST_CONTAINER_DEVECTOR_HPP
13	#define BOOST_CONTAINER_DEVECTOR_HPP
14
15	#include <boost/container/detail/config_begin.hpp>
16	#include <boost/container/detail/workaround.hpp>
17
18	#include <cstring> // memcpy
19
20	#include <boost/assert.hpp>
21
22	#include <boost/container/detail/copy_move_algo.hpp>
23	#include <boost/container/new_allocator.hpp> //new_allocator
24	#include <boost/container/allocator_traits.hpp> //allocator_traits
25	#include <boost/container/detail/algorithm.hpp> //equal()
26	#include <boost/container/throw_exception.hpp>
27	#include <boost/container/options.hpp>
28
29	#include <boost/container/detail/guards_dended.hpp>
30	#include <boost/container/detail/iterator.hpp>
31	#include <boost/container/detail/iterators.hpp>
32	#include <boost/container/detail/destroyers.hpp>
33	#include <boost/container/detail/min_max.hpp>
34	#include <boost/container/detail/next_capacity.hpp>
35	#include <boost/container/detail/alloc_helpers.hpp>
36	#include <boost/container/detail/advanced_insert_int.hpp>
37
38	// move
39	#if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
40	#include <boost/move/detail/fwd_macros.hpp>
41	#endif
42	#include <boost/move/detail/move_helpers.hpp>
43	#include <boost/move/adl_move_swap.hpp>
44	#include <boost/move/iterator.hpp>
45	#include <boost/move/traits.hpp>
46	#include <boost/move/utility_core.hpp>
47	#include <boost/move/detail/to_raw_pointer.hpp>
48	#include <boost/move/algo/detail/merge.hpp>
49	#include <boost/move/detail/force_ptr.hpp>
50
51	//std
52	#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
53	#include <initializer_list> //for std::initializer_list
54	#endif
55
56	namespace boost {
57	namespace container {
58
59	#if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
60
61	struct growth_factor_60;
62
63	template<class Options, class AllocatorSizeType>
64	struct get_devector_opt
65	{
66	typedef devector_opt< typename default_if_void<typename Options::growth_factor_type, growth_factor_60>::type
67	, typename default_if_void<typename Options::stored_size_type, AllocatorSizeType>::type
68	, default_if_zero<Options::free_fraction, relocate_on_90::value>::value
69	> type;
70	};
71
72	template<class AllocatorSizeType>
73	struct get_devector_opt<void, AllocatorSizeType>
74	{
75	typedef devector_opt< growth_factor_60, AllocatorSizeType, relocate_on_90::value> type;
76	};
77
78	#endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
79
80	struct reserve_only_tag_t {};
81	struct reserve_uninitialized_t {};
82	struct review_implementation_t {};
83
84	//struct unsafe_uninitialized_tag_t {};
85
86	/**
87	* A vector-like sequence container providing front and back operations
88	* (e.g: `push_front`/`pop_front`/`push_back`/`pop_back`) with amortized constant complexity.
89	*
90	* Models the [SequenceContainer], [ReversibleContainer], and [AllocatorAwareContainer] concepts.
91	*
92	* **Requires**:
93	* - `T` shall be [MoveInsertable] into the devector.
94	* - `T` shall be [Erasable] from any `devector<T, allocator_type, GP>`.
95	* - `GrowthFactor`, and `Allocator` must model the concepts with the same names or be void.
96	*
97	* **Definition**: `T` is `NothrowConstructible` if it's either nothrow move constructible or
98	* nothrow copy constructible.
99	*
100	* **Definition**: `T` is `NothrowAssignable` if it's either nothrow move assignable or
101	* nothrow copy assignable.
102	*
103	* **Exceptions**: The exception specifications assume `T` is nothrow [Destructible].
104	*
105	* Most methods providing the strong exception guarantee assume `T` either has a move
106	* constructor marked noexcept or is [CopyInsertable] into the devector. If it isn't true,
107	* and the move constructor throws, the guarantee is waived and the effects are unspecified.
108	*
109	* In addition to the exceptions specified in the **Throws** clause, the following operations
110	* of `T` can throw when any of the specified concept is required:
111	* - [DefaultInsertable][]: Default constructor
112	* - [MoveInsertable][]: Move constructor
113	* - [CopyInsertable][]: Copy constructor
114	* - [DefaultConstructible][]: Default constructor
115	* - [EmplaceConstructible][]: Constructor selected by the given arguments
116	* - [MoveAssignable][]: Move assignment operator
117	* - [CopyAssignable][]: Copy assignment operator
118	*
119	* Furthermore, not `noexcept` methods throws whatever the allocator throws
120	* if memory allocation fails. Such methods also throw `length_error` if the capacity
121	* exceeds `max_size()`.
122	*
123	* **Remark**: If a method invalidates some iterators, it also invalidates references
124	* and pointers to the elements pointed by the invalidated iterators.
125	*
126	*! \tparam Options A type produced from \c boost::container::devector_options.
127	*
128	* [SequenceContainer]: http://en.cppreference.com/w/cpp/concept/SequenceContainer
129	* [ReversibleContainer]: http://en.cppreference.com/w/cpp/concept/ReversibleContainer
130	* [AllocatorAwareContainer]: http://en.cppreference.com/w/cpp/concept/AllocatorAwareContainer
131	* [DefaultInsertable]: http://en.cppreference.com/w/cpp/concept/DefaultInsertable
132	* [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
133	* [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
134	* [Erasable]: http://en.cppreference.com/w/cpp/concept/Erasable
135	* [DefaultConstructible]: http://en.cppreference.com/w/cpp/concept/DefaultConstructible
136	* [Destructible]: http://en.cppreference.com/w/cpp/concept/Destructible
137	* [EmplaceConstructible]: http://en.cppreference.com/w/cpp/concept/EmplaceConstructible
138	* [MoveAssignable]: http://en.cppreference.com/w/cpp/concept/MoveAssignable
139	* [CopyAssignable]: http://en.cppreference.com/w/cpp/concept/CopyAssignable
140	*/
141	template < typename T, class A BOOST_CONTAINER_DOCONLY(= void), class Options BOOST_CONTAINER_DOCONLY(= void)>
142	class devector
143	{
144	#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
145	typedef boost::container::allocator_traits
146	<typename real_allocator<T, A>::type> allocator_traits_type;
147	typedef typename allocator_traits_type::size_type alloc_size_type;
148	typedef typename get_devector_opt<Options, alloc_size_type>::type options_type;
149	typedef typename options_type::growth_factor_type growth_factor_type;
150	typedef typename options_type::stored_size_type stored_size_type;
151	static const std::size_t devector_min_free_fraction =
152	options_type::free_fraction;
153
154	#endif // ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
155
156	public:
157	// Standard Interface Types:
158	typedef T value_type;
159	typedef BOOST_CONTAINER_IMPDEF
160	(typename real_allocator<T BOOST_MOVE_I A>::type) allocator_type;
161	typedef allocator_type stored_allocator_type;
162	typedef typename allocator_traits<allocator_type>::pointer pointer;
163	typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
164	typedef typename allocator_traits<allocator_type>::reference reference;
165	typedef typename allocator_traits<allocator_type>::const_reference const_reference;
166	typedef typename allocator_traits<allocator_type>::size_type size_type;
167	typedef typename allocator_traits<allocator_type>::difference_type difference_type;
168	typedef pointer iterator;
169	typedef const_pointer const_iterator;
170	typedef BOOST_CONTAINER_IMPDEF
171	(boost::container::reverse_iterator<iterator>) reverse_iterator;
172	typedef BOOST_CONTAINER_IMPDEF
173	(boost::container::reverse_iterator<const_iterator>) const_reverse_iterator;
174
175	#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
176	private:
177	BOOST_COPYABLE_AND_MOVABLE(devector)
178
179	// Guard to deallocate buffer on exception
180	typedef typename detail::allocation_guard<allocator_type> allocation_guard;
181
182	// Random access pseudo iterator always yielding to the same result
183	typedef constant_iterator<T> cvalue_iterator;
184
185	static size_type to_internal_capacity(size_type desired_capacity)
186	{
187	const size_type rounder = devector_min_free_fraction - 2u;
188	const size_type divisor = devector_min_free_fraction - 1u;
189	size_type const nc = ((desired_capacity + rounder) / divisor) * devector_min_free_fraction;
190	BOOST_ASSERT(desired_capacity <= (nc - nc / devector_min_free_fraction));
191	return nc;
192	}
193
194	#endif // ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
195
196	// Standard Interface
197	public:
198	// construct/copy/destroy
199
200	/**
201	* **Effects**: Constructs an empty devector.
202	*
203	* **Postcondition**: `empty() && front_free_capacity() == 0
204	* && back_free_capacity() == 0`.
205	*
206	* **Complexity**: Constant.
207	*/
208	devector() BOOST_NOEXCEPT
209	: m_()
210	{}
211
212	/**
213	* **Effects**: Constructs an empty devector, using the specified allocator.
214	*
215	* **Postcondition**: `empty() && front_free_capacity() == 0
216	* && back_free_capacity() == 0`.
217	*
218	* **Complexity**: Constant.
219	*/
220	explicit devector(const allocator_type& allocator) BOOST_NOEXCEPT
221	: m_(allocator)
222	{}
223
224	/**
225	* **Effects**: Constructs an empty devector, using the specified allocator
226	* and reserves `n` slots as if `reserve(n)` was called.
227	*
228	* **Postcondition**: `empty() && capacity() >= n`.
229	*
230	* **Exceptions**: Strong exception guarantee.
231	*
232	* **Complexity**: Constant.
233	*/
234	devector(size_type n, reserve_only_tag_t, const allocator_type& allocator = allocator_type())
235	: m_(reserve_only_tag_t(), allocator, to_internal_capacity(desired_capacity: n))
236	{}
237
238	/**
239	* **Effects**: Constructs an empty devector, using the specified allocator
240	* and reserves at least `front_free_cap + back_free_cap` slots as if `reserve_front(front_cap)` and
241	* `reserve_back(back_cap)` was called.
242	*
243	* **Postcondition**: `empty() && front_free_capacity() >= front_free_cap
244	* && back_free_capacity() >= back_free_cap`.
245	*
246	* **Exceptions**: Strong exception guarantee.
247	*
248	* **Complexity**: Constant.
249	*/
250	devector(size_type front_free_cap, size_type back_free_cap, reserve_only_tag_t, const allocator_type& allocator = allocator_type())
251	: m_(reserve_only_tag_t(), allocator, front_free_cap, back_free_cap)
252	{}
253
254	/**
255	* [DefaultInsertable]: http://en.cppreference.com/w/cpp/concept/DefaultInsertable
256	*
257	* **Effects**: Constructs a devector with `n` value_initialized elements using the specified allocator.
258	*
259	* **Requires**: `T` shall be [DefaultInsertable] into `*this`.
260	*
261	* **Postcondition**: `size() == n`.
262	*
263	* **Exceptions**: Strong exception guarantee.
264	*
265	* **Complexity**: Linear in `n`.
266	*/
267	explicit devector(size_type n, const allocator_type& allocator = allocator_type())
268	: m_(reserve_uninitialized_t(), allocator, n)
269	{
270	allocation_guard buffer_guard(m_.buffer, m_.capacity, get_allocator_ref());
271	boost::container::uninitialized_value_init_alloc_n(get_allocator_ref(), n, this->priv_raw_begin());
272	buffer_guard.release();
273	BOOST_ASSERT(invariants_ok());
274	}
275
276	/**
277	* **Effects**: Constructs a devector with `n` default-initialized elements using the specified allocator.
278	*
279	* **Requires**: `T` shall be [DefaultInsertable] into `*this`.
280	*
281	* **Postcondition**: `size() == n`.
282	*
283	* **Exceptions**: Strong exception guarantee.
284	*
285	* **Complexity**: Linear in `n`.
286	*/
287	explicit devector(size_type n, default_init_t, const allocator_type& allocator = allocator_type())
288	: m_(reserve_uninitialized_t(), allocator, n)
289	{
290	allocation_guard buffer_guard(m_.buffer, m_.capacity, get_allocator_ref());
291	boost::container::uninitialized_default_init_alloc_n(get_allocator_ref(), n, this->priv_raw_begin());
292	buffer_guard.release();
293	BOOST_ASSERT(invariants_ok());
294	}
295
296	/**
297	* [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
298	*
299	* **Effects**: Constructs a devector with `n` copies of `value`, using the specified allocator.
300	*
301	* **Requires**: `T` shall be [CopyInsertable] into `*this`.
302	*
303	* **Postcondition**: `size() == n`.
304	*
305	* **Exceptions**: Strong exception guarantee.
306	*
307	* **Complexity**: Linear in `n`.
308	*/
309	devector(size_type n, const T& value, const allocator_type& allocator = allocator_type())
310	: m_(reserve_uninitialized_t(), allocator, n)
311	{
312	construct_from_range(cvalue_iterator(value, n), cvalue_iterator());
313	BOOST_ASSERT(invariants_ok());
314	}
315
316	/**
317	* **Effects**: Constructs a devector equal to the range `[first,last)`, using the specified allocator.
318	*
319	* **Requires**: `T` shall be [EmplaceConstructible] into `*this` from `*first`. If the specified
320	* iterator does not meet the forward iterator requirements, `T` shall also be [MoveInsertable]
321	* into `*this`.
322	*
323	* **Postcondition**: `size() == boost::container::iterator_distance(first, last)
324	*
325	* **Exceptions**: Strong exception guarantee.
326	*
327	* **Complexity**: Makes only `N` calls to the copy constructor of `T` (where `N` is the distance between `first`
328	* and `last`), at most one allocation and no reallocations if iterators first and last are of forward,
329	* bidirectional, or random access categories. It makes `O(N)` calls to the copy constructor of `T`
330	* and `O(log(N)) reallocations if they are just input iterators.
331	*
332	* **Remarks**: Each iterator in the range `[first,last)` shall be dereferenced exactly once,
333	* unless an exception is thrown.
334	*
335	* [EmplaceConstructible]: http://en.cppreference.com/w/cpp/concept/EmplaceConstructible
336	* [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
337	*/
338	template <class InputIterator>
339	devector(InputIterator first, InputIterator last, const allocator_type& allocator = allocator_type()
340	//Input iterators
341	BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_or
342	< void
343	BOOST_MOVE_I dtl::is_convertible<InputIterator BOOST_MOVE_I size_type>
344	BOOST_MOVE_I dtl::is_not_input_iterator<InputIterator>
345	>::type * = 0)
346	)
347	: m_(allocator)
348	{
349	BOOST_CONTAINER_TRY{
350	while (first != last) {
351	this->emplace_back(*first++);
352	}
353	BOOST_ASSERT(invariants_ok());
354	}
355	BOOST_CONTAINER_CATCH(...){
356	this->destroy_elements(m_.buffer + m_.front_idx, m_.buffer + m_.back_idx);
357	this->deallocate_buffer();
358	}
359	BOOST_CONTAINER_CATCH_END
360	}
361
362	#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
363
364	template <class ForwardIterator>
365	devector(ForwardIterator first, ForwardIterator last, const allocator_type& allocator = allocator_type()
366	//Other iterators
367	BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_or
368	< void
369	BOOST_MOVE_I dtl::is_convertible<ForwardIterator BOOST_MOVE_I size_type>
370	BOOST_MOVE_I dtl::is_input_iterator<ForwardIterator>
371	>::type * = 0)
372	)
373	: m_(reserve_uninitialized_t(), allocator, boost::container::iterator_udistance(first, last))
374	{
375	this->construct_from_range(first, last);
376	BOOST_ASSERT(invariants_ok());
377	}
378
379	#endif // ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
380
381	/**
382	* [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
383	*
384	* **Effects**: Copy constructs a devector.
385	*
386	* **Requires**: `T` shall be [CopyInsertable] into `*this`.
387	*
388	* **Postcondition**: `this->size() == x.size()`.
389	*
390	* **Exceptions**: Strong exception guarantee.
391	*
392	* **Complexity**: Linear in the size of `x`.
393	*/
394	devector(const devector& x)
395	: m_(reserve_uninitialized_t(), allocator_traits_type::select_on_container_copy_construction(x.get_allocator_ref()), x.size())
396	{
397	this->construct_from_range(x.begin(), x.end());
398	BOOST_ASSERT(invariants_ok());
399	}
400
401	/**
402	* [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
403	*
404	* **Effects**: Copy constructs a devector, using the specified allocator.
405	*
406	* **Requires**: `T` shall be [CopyInsertable] into `*this`.
407	*
408	* **Postcondition**: `*this == x`.
409	*
410	* **Exceptions**: Strong exception guarantee.
411	*
412	* **Complexity**: Linear in the size of `x`.
413	*/
414	devector(const devector& x, const allocator_type& allocator)
415	: m_(reserve_uninitialized_t(), allocator, x.size())
416	{
417	this->construct_from_range(x.begin(), x.end());
418	BOOST_ASSERT(invariants_ok());
419	}
420
421	/**
422	* **Effects**: Moves `rhs`'s resources to `*this`.
423	*
424	* **Throws**: Nothing.
425	*
426	* **Postcondition**: *this has the same value `rhs` had before the operation.
427	* `rhs` is left in an unspecified but valid state.
428	*
429	* **Exceptions**: Strong exception guarantee if not `noexcept`.
430	*
431	* **Complexity**: Constant.
432	*/
433	devector(BOOST_RV_REF(devector) rhs) BOOST_NOEXCEPT_OR_NOTHROW
434	: m_(::boost::move(rhs.m_))
435	{
436	BOOST_ASSERT( invariants_ok());
437	BOOST_ASSERT(rhs.invariants_ok());
438	}
439
440	/**
441	* **Effects**: Moves `rhs`'s resources to `*this`, using the specified allocator.
442	*
443	* **Throws**: If allocation or T's move constructor throws.
444	*
445	* **Postcondition**: *this has the same value `rhs` had before the operation.
446	* `rhs` is left in an unspecified but valid state.
447	*
448	* **Exceptions**: Strong exception guarantee if not `noexcept`.
449	*
450	* **Complexity**: Linear if allocator != rhs.get_allocator(), otherwise constant.
451	*/
452	devector(BOOST_RV_REF(devector) rhs, const allocator_type& allocator)
453	: m_(review_implementation_t(), allocator, rhs.m_.buffer, rhs.m_.front_idx, rhs.m_.back_idx, rhs.m_.capacity)
454	{
455	// TODO should move elems-by-elems if the two allocators differ
456	// buffer is already acquired, reset rhs
457	rhs.m_.capacity = 0u;
458	rhs.m_.buffer = pointer();
459	rhs.m_.front_idx = 0;
460	rhs.m_.back_idx = 0;
461	BOOST_ASSERT( invariants_ok());
462	BOOST_ASSERT(rhs.invariants_ok());
463	}
464
465	#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
466	/**
467	* **Equivalent to**: `devector(il.begin(), il.end(), allocator)`.
468	*/
469	devector(const std::initializer_list<T>& il, const allocator_type& allocator = allocator_type())
470	: m_(reserve_uninitialized_t(), allocator, il.size())
471	{
472	this->construct_from_range(il.begin(), il.end());
473	BOOST_ASSERT(invariants_ok());
474	}
475	#endif
476
477	/**
478	* **Effects**: Destroys the devector. All stored values are destroyed and
479	* used memory, if any, deallocated.
480	*
481	* **Complexity**: Linear in the size of `*this`.
482	*/
483	~devector() BOOST_NOEXCEPT
484	{
485	destroy_elements(begin: m_.buffer + m_.front_idx, end: m_.buffer + m_.back_idx);
486	deallocate_buffer();
487	}
488
489	/**
490	* **Effects**: Copies elements of `x` to `*this`. Previously
491	* held elements get copy assigned to or destroyed.
492	*
493	* **Requires**: `T` shall be [CopyInsertable] into `*this`.
494	*
495	* **Postcondition**: `this->size() == x.size()`, the elements of
496	* `*this` are copies of elements in `x` in the same order.
497	*
498	* **Returns**: `*this`.
499	*
500	* **Exceptions**: Strong exception guarantee if `T` is `NothrowConstructible`
501	* and the allocator is allowed to be propagated
502	* ([propagate_on_container_copy_assignment] is true),
503	* Basic exception guarantee otherwise.
504	*
505	* **Complexity**: Linear in the size of `x` and `*this`.
506	*
507	* [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
508	* [propagate_on_container_copy_assignment]: http://en.cppreference.com/w/cpp/memory/allocator_traits
509	*/
510
511	inline devector& operator=(BOOST_COPY_ASSIGN_REF(devector) rhs)
512	{
513	const devector &x = rhs;
514	if (this == &x) { return *this; } // skip self
515
516	BOOST_IF_CONSTEXPR(allocator_traits_type::propagate_on_container_copy_assignment::value)
517	{
518	allocator_type &this_alloc = this->get_allocator_ref();
519	const allocator_type &other_alloc = x.get_allocator_ref();
520	if (this_alloc != other_alloc)
521	{
522	// new allocator cannot free existing storage
523	this->clear();
524	this->deallocate_buffer();
525	m_.capacity = 0u;
526	m_.buffer = pointer();
527	}
528
529	this_alloc = other_alloc;
530	}
531
532	size_type n = x.size();
533	if (m_.capacity >= n)
534	{
535	this->overwrite_buffer(x.begin(), x.end());
536	}
537	else
538	{
539	this->allocate_and_copy_range(x.begin(), x.end());
540	}
541
542	BOOST_ASSERT(invariants_ok());
543
544	return *this;
545	}
546
547	/**
548	* [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
549	*
550	* **Effects**: Moves elements of `x` to `*this`. Previously
551	* held elements get move/copy assigned to or destroyed.
552	*
553	* **Requires**: `T` shall be [MoveInsertable] into `*this`.
554	*
555	* **Postcondition**: `x` is left in an unspecified but valid state.
556	*
557	* **Returns**: `*this`.
558	*
559	* **Exceptions**: Basic exception guarantee if not `noexcept`.
560	*
561	* **Complexity**: Constant if allocator_traits_type::
562	* propagate_on_container_move_assignment is true or
563	* this->get>allocator() == x.get_allocator(). Linear otherwise.
564	*/
565	devector& operator=(BOOST_RV_REF(devector) x)
566	BOOST_NOEXCEPT_IF(allocator_traits_type::propagate_on_container_move_assignment::value
567	|| allocator_traits_type::is_always_equal::value)
568	{
569	BOOST_CONSTEXPR_OR_CONST bool copy_alloc = allocator_traits_type::propagate_on_container_move_assignment::value;
570
571	BOOST_IF_CONSTEXPR (copy_alloc || get_allocator_ref() == x.get_allocator_ref())
572	{
573	this->clear();
574	this->deallocate_buffer();
575
576	if (copy_alloc)
577	{
578	this->get_allocator_ref() = boost::move(x.get_allocator_ref());
579	}
580
581	m_.capacity = x.m_.capacity;
582	m_.buffer = x.m_.buffer;
583	m_.front_idx = x.m_.front_idx;
584	m_.back_idx = x.m_.back_idx;
585
586	// leave x in valid state
587	x.m_.capacity = 0u;
588	x.m_.buffer = pointer();
589	x.m_.back_idx = x.m_.front_idx = 0;
590	}
591	else
592	{
593	// if the allocator shouldn't be copied and they do not compare equal
594	// we can't steal memory.
595
596	move_iterator<iterator> xbegin = boost::make_move_iterator(x.begin());
597	move_iterator<iterator> xend = boost::make_move_iterator(x.end());
598
599	if (copy_alloc)
600	{
601	get_allocator_ref() = boost::move(x.get_allocator_ref());
602	}
603
604	if (m_.capacity >= x.size())
605	{
606	overwrite_buffer(xbegin, xend);
607	}
608	else
609	{
610	allocate_and_copy_range(xbegin, xend);
611	}
612	}
613
614	BOOST_ASSERT(invariants_ok());
615
616	return *this;
617	}
618
619	#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
620	/**
621	* **Effects**: Copies elements of `il` to `*this`. Previously
622	* held elements get copy assigned to or destroyed.
623	*
624	* **Requires**: `T` shall be [CopyInsertable] into `*this` and [CopyAssignable].
625	*
626	* **Postcondition**: `this->size() == il.size()`, the elements of
627	* `*this` are copies of elements in `il` in the same order.
628	*
629	* **Exceptions**: Strong exception guarantee if `T` is nothrow copy assignable
630	* from `T` and `NothrowConstructible`, Basic exception guarantee otherwise.
631	*
632	* **Returns**: `*this`.
633	*
634	* **Complexity**: Linear in the size of `il` and `*this`.
635	*
636	* [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
637	* [CopyAssignable]: http://en.cppreference.com/w/cpp/concept/CopyAssignable
638	*/
639	inline devector& operator=(std::initializer_list<T> il)
640	{
641	this->assign(il.begin(), il.end());
642	return *this;
643	}
644	#endif
645
646	/**
647	* **Effects**: Replaces elements of `*this` with a copy of `[first,last)`.
648	* Previously held elements get copy assigned to or destroyed.
649	*
650	* **Requires**: `T` shall be [EmplaceConstructible] from `*first`. If the specified iterator
651	* does not meet the forward iterator requirements, `T` shall be also [MoveInsertable] into `*this`.
652	*
653	* **Precondition**: `first` and `last` are not iterators into `*this`.
654	*
655	* **Postcondition**: `size() == N`, where `N` is the distance between `first` and `last`.
656	*
657	* **Exceptions**: Strong exception guarantee if `T` is nothrow copy assignable
658	* from `*first` and `NothrowConstructible`, Basic exception guarantee otherwise.
659	*
660	* **Complexity**: Linear in the distance between `first` and `last`.
661	* Makes a single reallocation at most if the iterators `first` and `last`
662	* are of forward, bidirectional, or random access categories. It makes
663	* `O(log(N))` reallocations if they are just input iterators.
664	*
665	* **Remarks**: Each iterator in the range `[first,last)` shall be dereferenced exactly once,
666	* unless an exception is thrown.
667	*
668	* [EmplaceConstructible]: http://en.cppreference.com/w/cpp/concept/EmplaceConstructible
669	* [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
670	*/
671	template <class InputIterator>
672	void assign(InputIterator first, InputIterator last
673	//Input iterators
674	BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_or
675	< void
676	BOOST_MOVE_I dtl::is_convertible<InputIterator BOOST_MOVE_I size_type>
677	BOOST_MOVE_I dtl::is_not_input_iterator<InputIterator>
678	>::type * = 0)
679	)
680	{
681	first = overwrite_buffer_impl(first, last, dtl::false_());
682	while (first != last)
683	{
684	this->emplace_back(*first++);
685	}
686	}
687
688	#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
689
690	template <class ForwardIterator>
691	void assign(ForwardIterator first, ForwardIterator last
692	//Other iterators
693	BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_or
694	< void
695	BOOST_MOVE_I dtl::is_convertible<ForwardIterator BOOST_MOVE_I size_type>
696	BOOST_MOVE_I dtl::is_input_iterator<ForwardIterator>
697	>::type * = 0)
698	)
699	{
700	const size_type n = boost::container::iterator_udistance(first, last);
701
702	if (m_.capacity >= n)
703	{
704	overwrite_buffer(first, last);
705	}
706	else
707	{
708	allocate_and_copy_range(first, last);
709	}
710
711	BOOST_ASSERT(invariants_ok());
712	}
713
714	#endif // ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
715
716	/**
717	* **Effects**: Replaces elements of `*this` with `n` copies of `u`.
718	* Previously held elements get copy assigned to or destroyed.
719	*
720	* **Requires**: `T` shall be [CopyInsertable] into `*this` and
721	* [CopyAssignable].
722	*
723	* **Precondition**: `u` is not a reference into `*this`.
724	*
725	* **Postcondition**: `size() == n` and the elements of
726	* `*this` are copies of `u`.
727	*
728	* **Exceptions**: Strong exception guarantee if `T` is nothrow copy assignable
729	* from `u` and `NothrowConstructible`, Basic exception guarantee otherwise.
730	*
731	* **Complexity**: Linear in `n` and the size of `*this`.
732	*
733	* [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
734	* [CopyAssignable]: http://en.cppreference.com/w/cpp/concept/CopyAssignable
735	*/
736	inline void assign(size_type n, const T& u)
737	{
738	cvalue_iterator first(u, n);
739	cvalue_iterator last;
740	this->assign(first, last);
741	}
742
743	#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
744	/** **Equivalent to**: `assign(il.begin(), il.end())`. */
745	inline void assign(std::initializer_list<T> il)
746	{
747	this->assign(il.begin(), il.end());
748	}
749	#endif
750
751	/**
752	* **Returns**: A copy of the allocator associated with the container.
753	*
754	* **Complexity**: Constant.
755	*/
756	BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
757	allocator_type get_allocator() const BOOST_NOEXCEPT
758	{
759	return static_cast<const allocator_type&>(m_);
760	}
761
762	BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
763	const allocator_type &get_stored_allocator() const BOOST_NOEXCEPT
764	{
765	return static_cast<const allocator_type&>(m_);
766	}
767
768	BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
769	allocator_type &get_stored_allocator() BOOST_NOEXCEPT
770	{
771	return static_cast<allocator_type&>(m_);
772	}
773
774	// iterators
775
776	/**
777	* **Returns**: A iterator pointing to the first element in the devector,
778	* or the past the end iterator if the devector is empty.
779	*
780	* **Complexity**: Constant.
781	*/
782	BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
783	iterator begin() BOOST_NOEXCEPT
784	{
785	return m_.buffer + m_.front_idx;
786	}
787
788	/**
789	* **Returns**: A constant iterator pointing to the first element in the devector,
790	* or the past the end iterator if the devector is empty.
791	*
792	* **Complexity**: Constant.
793	*/
794	BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
795	const_iterator begin() const BOOST_NOEXCEPT
796	{
797	return m_.buffer + m_.front_idx;
798	}
799
800	/**
801	* **Returns**: An iterator pointing past the last element of the container.
802	*
803	* **Complexity**: Constant.
804	*/
805	BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
806	iterator end() BOOST_NOEXCEPT
807	{
808	return m_.buffer + m_.back_idx;
809	}
810
811	/**
812	* **Returns**: A constant iterator pointing past the last element of the container.
813	*
814	* **Complexity**: Constant.
815	*/
816	BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
817	const_iterator end() const BOOST_NOEXCEPT
818	{
819	return m_.buffer + m_.back_idx;
820	}
821
822	/**
823	* **Returns**: A reverse iterator pointing to the first element in the reversed devector,
824	* or the reverse past the end iterator if the devector is empty.
825	*
826	* **Complexity**: Constant.
827	*/
828	BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
829	reverse_iterator rbegin() BOOST_NOEXCEPT
830	{
831	return reverse_iterator(m_.buffer + m_.back_idx);
832	}
833
834	/**
835	* **Returns**: A constant reverse iterator
836	* pointing to the first element in the reversed devector,
837	* or the reverse past the end iterator if the devector is empty.
838	*
839	* **Complexity**: Constant.
840	*/
841	BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
842	const_reverse_iterator rbegin() const BOOST_NOEXCEPT
843	{
844	return const_reverse_iterator(m_.buffer + m_.back_idx);
845	}
846
847	/**
848	* **Returns**: A reverse iterator pointing past the last element in the
849	* reversed container, or to the beginning of the reversed container if it's empty.
850	*
851	* **Complexity**: Constant.
852	*/
853	BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
854	reverse_iterator rend() BOOST_NOEXCEPT
855	{
856	return reverse_iterator(m_.buffer + m_.front_idx);
857	}
858
859	/**
860	* **Returns**: A constant reverse iterator pointing past the last element in the
861	* reversed container, or to the beginning of the reversed container if it's empty.
862	*
863	* **Complexity**: Constant.
864	*/
865	BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
866	const_reverse_iterator rend() const BOOST_NOEXCEPT
867	{
868	return const_reverse_iterator(m_.buffer + m_.front_idx);
869	}
870
871	/**
872	* **Returns**: A constant iterator pointing to the first element in the devector,
873	* or the past the end iterator if the devector is empty.
874	*
875	* **Complexity**: Constant.
876	*/
877	BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
878	const_iterator cbegin() const BOOST_NOEXCEPT
879	{
880	return m_.buffer + m_.front_idx;
881	}
882
883	/**
884	* **Returns**: A constant iterator pointing past the last element of the container.
885	*
886	* **Complexity**: Constant.
887	*/
888	const_iterator cend() const BOOST_NOEXCEPT
889	{
890	return m_.buffer + m_.back_idx;
891	}
892
893	/**
894	* **Returns**: A constant reverse iterator
895	* pointing to the first element in the reversed devector,
896	* or the reverse past the end iterator if the devector is empty.
897	*
898	* **Complexity**: Constant.
899	*/
900	BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
901	const_reverse_iterator crbegin() const BOOST_NOEXCEPT
902	{
903	return const_reverse_iterator(m_.buffer + m_.back_idx);
904	}
905
906	/**
907	* **Returns**: A constant reverse iterator pointing past the last element in the
908	* reversed container, or to the beginning of the reversed container if it's empty.
909	*
910	* **Complexity**: Constant.
911	*/
912	BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
913	const_reverse_iterator crend() const BOOST_NOEXCEPT
914	{
915	return const_reverse_iterator(m_.buffer + m_.front_idx);
916	}
917
918	// capacity
919
920	/**
921	* **Returns**: True, if `size() == 0`, false otherwise.
922	*
923	* **Complexity**: Constant.
924	*/
925	BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
926	bool empty() const BOOST_NOEXCEPT
927	{
928	return m_.front_idx == m_.back_idx;
929	}
930
931	/**
932	* **Returns**: The number of elements the devector contains.
933	*
934	* **Complexity**: Constant.
935	*/
936	BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
937	size_type size() const BOOST_NOEXCEPT
938	{
939	return size_type(m_.back_idx - m_.front_idx);
940	}
941
942	/**
943	* **Returns**: The maximum number of elements the devector could possibly hold.
944	*
945	* **Complexity**: Constant.
946	*/
947	BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
948	size_type max_size() const BOOST_NOEXCEPT
949	{
950	size_type alloc_max = allocator_traits_type::max_size(get_allocator_ref());
951	size_type size_type_max = (size_type)-1;
952	return (alloc_max <= size_type_max) ? size_type(alloc_max) : size_type_max;
953	}
954
955	/**
956	* **Returns**: The *minimum* number of elements that can be inserted into devector using
957	* position-based insertions without requiring a reallocation. Note that, unlike in
958	* typical sequence containers like `vector`, `capacity()`, `capacity()` can be smaller than `size()`.
959	* This can happen if a user inserts elements in a particular way (usually inserting at
960	* front up to front_free_capacity() and at back up to back_free_capacity()).
961	*
962	* **Complexity**: Constant.
963	*/
964	BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
965	size_type capacity() const BOOST_NOEXCEPT
966	{
967	size_type const cap_reserve = m_.capacity/devector_min_free_fraction;
968	return m_.capacity > cap_reserve ? (m_.capacity - cap_reserve) : 0u;
969	}
970
971	/**
972	* **Returns**: The total number of elements that can be pushed to the front of the
973	* devector without requiring reallocation.
974	*
975	* **Complexity**: Constant.
976	*/
977	BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
978	size_type front_free_capacity() const BOOST_NOEXCEPT
979	{
980	return m_.front_idx;
981	}
982
983	/**
984	* **Returns**: The total number of elements that can be pushed to the back of the
985	* devector without requiring reallocation.
986	*
987	* **Complexity**: Constant.
988	*/
989	BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
990	size_type back_free_capacity() const BOOST_NOEXCEPT
991	{
992	return size_type(m_.capacity - m_.back_idx);
993	}
994
995	/**
996	* **Effects**: If `sz` is greater than the size of `*this`,
997	* additional value-initialized elements are inserted. Invalidates iterators
998	* if reallocation is needed. If `sz` is smaller than than the size of `*this`,
999	* elements are erased from the extremes.
1000	*
1001	* **Requires**: T shall be [MoveInsertable] into *this and [DefaultConstructible].
1002	*
1003	* **Postcondition**: `sz == size()`.
1004	*
1005	* **Exceptions**: Strong exception guarantee.
1006	*
1007	* **Complexity**: Linear in the size of `*this` and `sz`.
1008	*
1009	* [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
1010	* [DefaultConstructible]: http://en.cppreference.com/w/cpp/concept/DefaultConstructible
1011	*/
1012	inline void resize(size_type sz)
1013	{
1014	this->resize_back(sz);
1015	}
1016
1017	/**
1018	* **Effects**: Same as resize(sz) but creates default-initialized
1019	* value-initialized.
1020	*/
1021	inline void resize(size_type sz, default_init_t)
1022	{
1023	this->resize_back(sz, default_init);
1024	}
1025
1026	/**
1027	* [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
1028	*
1029	* **Effects**: If `sz` is greater than the size of `*this`,
1030	* copies of `c` are inserted at extremes.
1031	* If `sz` is smaller than than the size of `*this`,
1032	* elements are popped from the extremes.
1033	*
1034	* **Postcondition**: `sz == size()`.
1035	*
1036	* **Requires**: `T` shall be [CopyInsertable] into `*this`.
1037	*
1038	* **Exceptions**: Strong exception guarantee.
1039	*
1040	* **Complexity**: Linear in the size of `*this` and `sz`.
1041	*/
1042	inline void resize(size_type sz, const T& c)
1043	{
1044	this->resize_back(sz, c);
1045	}
1046
1047	/**
1048	* **Effects**: If `sz` is greater than the size of `*this`,
1049	* additional value-initialized elements are inserted
1050	* to the front. Invalidates iterators if reallocation is needed.
1051	* If `sz` is smaller than than the size of `*this`,
1052	* elements are popped from the front.
1053	*
1054	* **Requires**: T shall be [MoveInsertable] into *this and [DefaultConstructible].
1055	*
1056	* **Postcondition**: `sz == size()`.
1057	*
1058	* **Exceptions**: Strong exception guarantee.
1059	*
1060	* **Complexity**: Linear in the size of `*this` and `sz`.
1061	*
1062	* [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
1063	* [DefaultConstructible]: http://en.cppreference.com/w/cpp/concept/DefaultConstructible
1064	*/
1065	inline void resize_front(size_type sz)
1066	{
1067	resize_front_impl(sz);
1068	BOOST_ASSERT(invariants_ok());
1069	}
1070
1071	/**
1072	* **Effects**: If `sz` is greater than the size of `*this`,
1073	* additional value-initialized elements are inserted
1074	* to the front. Invalidates iterators if reallocation is needed.
1075	* If `sz` is smaller than than the size of `*this`,
1076	* elements are popped from the front.
1077	*
1078	* **Requires**: T shall be [MoveInsertable] into *this and default_initializable.
1079	*
1080	* **Postcondition**: `sz == size()`.
1081	*
1082	* **Exceptions**: Strong exception guarantee.
1083	*
1084	* **Complexity**: Linear in the size of `*this` and `sz`.
1085	*
1086	* [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
1087	*/
1088	inline void resize_front(size_type sz, default_init_t)
1089	{
1090	resize_front_impl(sz, default_init);
1091	BOOST_ASSERT(invariants_ok());
1092	}
1093
1094	/**
1095	* [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
1096	*
1097	* **Effects**: If `sz` is greater than the size of `*this`,
1098	* copies of `c` are inserted to the front.
1099	* Invalidates iterators if reallocation is needed.
1100	* If `sz` is smaller than than the size of `*this`,
1101	* elements are popped from the front.
1102	*
1103	* **Postcondition**: `sz == size()`.
1104	*
1105	* **Requires**: `T` shall be [CopyInsertable] into `*this`.
1106	*
1107	* **Exceptions**: Strong exception guarantee.
1108	*
1109	* **Complexity**: Linear in the size of `*this` and `sz`.
1110	*/
1111	inline void resize_front(size_type sz, const T& c)
1112	{
1113	resize_front_impl(sz, c);
1114	BOOST_ASSERT(invariants_ok());
1115	}
1116
1117	/**
1118	* **Effects**: If `sz` is greater than the size of `*this`,
1119	* additional value-initialized elements are inserted
1120	* to the back. Invalidates iterators if reallocation is needed.
1121	* If `sz` is smaller than than the size of `*this`,
1122	* elements are popped from the back.
1123	*
1124	* **Requires**: T shall be [MoveInsertable] into *this and [DefaultConstructible].
1125	*
1126	* **Postcondition**: `sz == size()`.
1127	*
1128	* **Exceptions**: Strong exception guarantee.
1129	*
1130	* **Complexity**: Linear in the size of `*this` and `sz`.
1131	*
1132	* [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
1133	* [DefaultConstructible]: http://en.cppreference.com/w/cpp/concept/DefaultConstructible
1134	*/
1135	inline void resize_back(size_type sz)
1136	{
1137	resize_back_impl(sz);
1138	BOOST_ASSERT(invariants_ok());
1139	}
1140
1141	/**
1142	* **Effects**: If `sz` is greater than the size of `*this`,
1143	* additional value-initialized elements are inserted
1144	* to the back. Invalidates iterators if reallocation is needed.
1145	* If `sz` is smaller than than the size of `*this`,
1146	* elements are popped from the back.
1147	*
1148	* **Requires**: T shall be [MoveInsertable] into *this and default initializable.
1149	*
1150	* **Postcondition**: `sz == size()`.
1151	*
1152	* **Exceptions**: Strong exception guarantee.
1153	*
1154	* **Complexity**: Linear in the size of `*this` and `sz`.
1155	*
1156	* [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
1157	*/
1158	inline void resize_back(size_type sz, default_init_t)
1159	{
1160	resize_back_impl(sz, default_init);
1161	BOOST_ASSERT(invariants_ok());
1162	}
1163
1164	/**
1165	* [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
1166	*
1167	* **Effects**: If `sz` is greater than the size of `*this`,
1168	* copies of `c` are inserted to the back.
1169	* If `sz` is smaller than than the size of `*this`,
1170	* elements are popped from the back.
1171	*
1172	* **Postcondition**: `sz == size()`.
1173	*
1174	* **Requires**: `T` shall be [CopyInsertable] into `*this`.
1175	*
1176	* **Exceptions**: Strong exception guarantee.
1177	*
1178	* **Complexity**: Linear in the size of `*this` and `sz`.
1179	*/
1180	inline void resize_back(size_type sz, const T& c)
1181	{
1182	resize_back_impl(sz, c);
1183	BOOST_ASSERT(invariants_ok());
1184	}
1185
1186	/**
1187	* [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
1188	*
1189	* **Effects**: Ensures that at least `n` elements can be inserted
1190	* without requiring reallocation, where `n` is `new_capacity - size()`,
1191	* if `n` is positive. Otherwise, there are no effects.
1192	* Invalidates iterators if reallocation is needed.
1193	*
1194	* **Requires**: `T` shall be [MoveInsertable] into `*this`.
1195	*
1196	* **Complexity**: Linear in the size of *this.
1197	*
1198	* **Exceptions**: Strong exception guarantee.
1199	*
1200	* **Throws**: length_error if `new_capacity > max_size()`.
1201	*/
1202	inline void reserve(size_type new_capacity)
1203	{
1204	if (this->capacity() < new_capacity) {
1205	const size_type rounder = devector_min_free_fraction - 2u;
1206	const size_type divisor = devector_min_free_fraction - 1u;
1207	size_type const nc = ((new_capacity + rounder)/divisor)*devector_min_free_fraction;
1208	BOOST_ASSERT(new_capacity <= (nc - nc / devector_min_free_fraction));
1209	size_type const sz = this->size();
1210	reallocate_at(new_capacity: nc, buffer_offset: (nc-sz)/2u);
1211	}
1212	BOOST_ASSERT(invariants_ok());
1213	}
1214
1215	/**
1216	* [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
1217	*
1218	* **Effects**: Ensures that `n` elements can be pushed to the front
1219	* without requiring reallocation, where `n` is `new_capacity - size()`,
1220	* if `n` is positive. Otherwise, there are no effects.
1221	* Invalidates iterators if reallocation is needed.
1222	*
1223	* **Requires**: `T` shall be [MoveInsertable] into `*this`.
1224	*
1225	* **Complexity**: Linear in the size of *this.
1226	*
1227	* **Exceptions**: Strong exception guarantee.
1228	*
1229	* **Throws**: `length_error` if `new_capacity > max_size()`.
1230	*/
1231	inline void reserve_front(size_type new_capacity)
1232	{
1233	if (front_capacity() >= new_capacity) { return; }
1234
1235	reallocate_at(new_capacity: new_capacity + back_free_capacity(), buffer_offset: new_capacity - size());
1236
1237	BOOST_ASSERT(invariants_ok());
1238	}
1239
1240	/**
1241	* [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
1242	*
1243	* **Effects**: Ensures that `n` elements can be pushed to the back
1244	* without requiring reallocation, where `n` is `new_capacity - size()`,
1245	* if `n` is positive. Otherwise, there are no effects.
1246	* Invalidates iterators if reallocation is needed.
1247	*
1248	* **Requires**: `T` shall be [MoveInsertable] into `*this`.
1249	*
1250	* **Complexity**: Linear in the size of *this.
1251	*
1252	* **Exceptions**: Strong exception guarantee.
1253	*
1254	* **Throws**: length_error if `new_capacity > max_size()`.
1255	*/
1256	inline void reserve_back(size_type new_capacity)
1257	{
1258	if (back_capacity() >= new_capacity) { return; }
1259
1260	reallocate_at(new_capacity: new_capacity + front_free_capacity(), buffer_offset: m_.front_idx);
1261
1262	BOOST_ASSERT(invariants_ok());
1263	}
1264
1265
1266	/**
1267	* [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
1268	*
1269	* **Effects**: Reduces `capacity()` to `size()`. Invalidates iterators.
1270	*
1271	* **Requires**: `T` shall be [MoveInsertable] into `*this`.
1272	*
1273	* **Exceptions**: Strong exception guarantee.
1274	*
1275	* **Complexity**: Linear in the size of *this.
1276	*/
1277	inline void shrink_to_fit()
1278	{
1279	if(this->front_capacity() || this->back_capacity())
1280	this->reallocate_at(size(), 0);
1281	}
1282
1283	// element access:
1284
1285	/**
1286	* **Returns**: A reference to the `n`th element in the devector.
1287	*
1288	* **Precondition**: `n < size()`.
1289	*
1290	* **Complexity**: Constant.
1291	*/
1292	BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1293	reference operator[](size_type n) BOOST_NOEXCEPT
1294	{
1295	BOOST_ASSERT(n < size());
1296	return m_.buffer[m_.front_idx + n];
1297	}
1298
1299	/**
1300	* **Returns**: A constant reference to the `n`th element in the devector.
1301	*
1302	* **Precondition**: `n < size()`.
1303	*
1304	* **Complexity**: Constant.
1305	*/
1306	BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1307	const_reference operator[](size_type n) const BOOST_NOEXCEPT
1308	{
1309	BOOST_ASSERT(n < size());
1310	return m_.buffer[m_.front_idx + n];
1311	}
1312
1313	/**
1314	* **Returns**: A reference to the `n`th element in the devector.
1315	*
1316	* **Throws**: `out_of_range`, if `n >= size()`.
1317	*
1318	* **Complexity**: Constant.
1319	*/
1320	BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1321	reference at(size_type n)
1322	{
1323	if (size() <= n)
1324	throw_out_of_range(str: "devector::at out of range");
1325	return (*this)[n];
1326	}
1327
1328	/**
1329	* **Returns**: A constant reference to the `n`th element in the devector.
1330	*
1331	* **Throws**: `out_of_range`, if `n >= size()`.
1332	*
1333	* **Complexity**: Constant.
1334	*/
1335	BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1336	const_reference at(size_type n) const
1337	{
1338	if (size() <= n)
1339	throw_out_of_range(str: "devector::at out of range");
1340	return (*this)[n];
1341	}
1342
1343	/**
1344	* **Returns**: A reference to the first element in the devector.
1345	*
1346	* **Precondition**: `!empty()`.
1347	*
1348	* **Complexity**: Constant.
1349	*/
1350	BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1351	reference front() BOOST_NOEXCEPT
1352	{
1353	BOOST_ASSERT(!empty());
1354
1355	return m_.buffer[m_.front_idx];
1356	}
1357
1358	/**
1359	* **Returns**: A constant reference to the first element in the devector.
1360	*
1361	* **Precondition**: `!empty()`.
1362	*
1363	* **Complexity**: Constant.
1364	*/
1365	BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1366	const_reference front() const BOOST_NOEXCEPT
1367	{
1368	BOOST_ASSERT(!empty());
1369
1370	return m_.buffer[m_.front_idx];
1371	}
1372
1373	/**
1374	* **Returns**: A reference to the last element in the devector.
1375	*
1376	* **Precondition**: `!empty()`.
1377	*
1378	* **Complexity**: Constant.
1379	*/
1380	BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1381	reference back() BOOST_NOEXCEPT
1382	{
1383	BOOST_ASSERT(!empty());
1384
1385	return m_.buffer[m_.back_idx - 1u];
1386	}
1387
1388	/**
1389	* **Returns**: A constant reference to the last element in the devector.
1390	*
1391	* **Precondition**: `!empty()`.
1392	*
1393	* **Complexity**: Constant.
1394	*/
1395	BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1396	const_reference back() const BOOST_NOEXCEPT
1397	{
1398	BOOST_ASSERT(!empty());
1399
1400	return m_.buffer[m_.back_idx - 1u];
1401	}
1402
1403	/**
1404	* **Returns**: A pointer to the underlying array serving as element storage.
1405	* The range `[data(); data() + size())` is always valid. For a non-empty devector,
1406	* `data() == &front()`.
1407	*
1408	* **Complexity**: Constant.
1409	*/
1410	BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1411	T* data() BOOST_NOEXCEPT
1412	{
1413	return boost::movelib::to_raw_pointer(m_.buffer) + m_.front_idx;
1414	}
1415
1416	/**
1417	* **Returns**: A constant pointer to the underlying array serving as element storage.
1418	* The range `[data(); data() + size())` is always valid. For a non-empty devector,
1419	* `data() == &front()`.
1420	*
1421	* **Complexity**: Constant.
1422	*/
1423	BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1424	const T* data() const BOOST_NOEXCEPT
1425	{
1426	return boost::movelib::to_raw_pointer(m_.buffer) + m_.front_idx;
1427	}
1428
1429	// modifiers:
1430
1431	/**
1432	* **Effects**: Pushes a new element to the front of the devector.
1433	* The element is constructed in-place, using the perfect forwarded `args`
1434	* as constructor arguments. Invalidates iterators if reallocation is needed.
1435	* (`front_free_capacity() == 0`)
1436	*
1437	* **Requires**: `T` shall be [EmplaceConstructible] from `args` and [MoveInsertable] into `*this`.
1438	*
1439	* **Exceptions**: Strong exception guarantee.
1440	*
1441	* **Complexity**: Amortized constant in the size of `*this`.
1442	* (Constant, if `front_free_capacity() > 0`)
1443	*
1444	* [EmplaceConstructible]: http://en.cppreference.com/w/cpp/concept/EmplaceConstructible
1445	* [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
1446	*/
1447	#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1448	template <class... Args>
1449	reference emplace_front(Args&&... args)
1450	{
1451	if (BOOST_LIKELY(front_free_capacity() != 0)) // fast path
1452	{
1453	pointer const p = m_.buffer + (m_.front_idx - 1u);
1454	this->alloc_construct(p, boost::forward<Args>(args)...);
1455	--m_.front_idx;
1456	BOOST_ASSERT(invariants_ok());
1457	return *p;
1458	}
1459	else
1460	{
1461	typedef dtl::insert_emplace_proxy<allocator_type, Args...> proxy_t;
1462	return *this->insert_range_slow_path(this->begin(), 1, proxy_t(::boost::forward<Args>(args)...));
1463	}
1464	}
1465
1466	#else //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1467
1468	#define BOOST_CONTAINER_DEVECTOR_EMPLACE_FRONT(N) \
1469	BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1470	inline reference emplace_front(BOOST_MOVE_UREF##N)\
1471	{\
1472	if (front_free_capacity())\
1473	{\
1474	pointer const p = m_.buffer + (m_.front_idx - 1u);\
1475	this->alloc_construct(p BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
1476	--m_.front_idx;\
1477	return *p;\
1478	}\
1479	else\
1480	{\
1481	typedef dtl::insert_emplace_proxy_arg##N<allocator_type BOOST_MOVE_I##N BOOST_MOVE_TARG##N> proxy_t;\
1482	return *this->insert_range_slow_path(this->begin(), 1, proxy_t(BOOST_MOVE_FWD##N));\
1483	}\
1484	}\
1485	//
1486	BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_DEVECTOR_EMPLACE_FRONT)
1487	#undef BOOST_CONTAINER_DEVECTOR_EMPLACE_FRONT
1488
1489	#endif
1490
1491	#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1492	/**
1493	* [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
1494	*
1495	* **Effects**: Pushes the copy of `x` to the front of the devector.
1496	* Invalidates iterators if reallocation is needed.
1497	* (`front_free_capacity() == 0`)
1498	*
1499	* **Requires**: `T` shall be [CopyInsertable] into `*this`.
1500	*
1501	* **Exceptions**: Strong exception guarantee.
1502	*
1503	* **Complexity**: Amortized constant in the size of `*this`.
1504	* (Constant, if `front_free_capacity() > 0`)
1505	*/
1506	void push_front(const T& x);
1507
1508	/**
1509	* [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
1510	*
1511	* **Effects**: Move constructs a new element at the front of the devector using `x`.
1512	* Invalidates iterators if reallocation is needed.
1513	* (`front_free_capacity() == 0`)
1514	*
1515	* **Requires**: `T` shall be [MoveInsertable] into `*this`.
1516	*
1517	* **Exceptions**: Strong exception guarantee, not regarding the state of `x`.
1518	*
1519	* **Complexity**: Amortized constant in the size of `*this`.
1520	* (Constant, if `front_free_capacity() > 0`)
1521	*/
1522	void push_front(T&& x);
1523
1524	#else
1525	BOOST_MOVE_CONVERSION_AWARE_CATCH(push_front, T, void, priv_push_front)
1526	#endif
1527
1528	/**
1529	* **Effects**: Removes the first element of `*this`.
1530	*
1531	* **Precondition**: `!empty()`.
1532	*
1533	* **Postcondition**: `front_free_capacity()` is incremented by 1.
1534	*
1535	* **Complexity**: Constant.
1536	*/
1537	void pop_front() BOOST_NOEXCEPT
1538	{
1539	BOOST_ASSERT(!empty());
1540	allocator_traits_type::destroy(get_allocator_ref(), boost::movelib::to_raw_pointer(m_.buffer + m_.front_idx));
1541	++m_.front_idx;
1542	BOOST_ASSERT(invariants_ok());
1543	}
1544
1545	/**
1546	* **Effects**: Pushes a new element to the back of the devector.
1547	* The element is constructed in-place, using the perfect forwarded `args`
1548	* as constructor arguments. Invalidates iterators if reallocation is needed.
1549	* (`back_free_capacity() == 0`)
1550	*
1551	* **Requires**: `T` shall be [EmplaceConstructible] from `args` and [MoveInsertable] into `*this`,
1552	* and [MoveAssignable].
1553	*
1554	* **Exceptions**: Strong exception guarantee.
1555	*
1556	* **Complexity**: Amortized constant in the size of `*this`.
1557	* (Constant, if `back_free_capacity() > 0`)
1558	*
1559	* [EmplaceConstructible]: http://en.cppreference.com/w/cpp/concept/EmplaceConstructible
1560	* [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
1561	* [MoveAssignable]: http://en.cppreference.com/w/cpp/concept/MoveAssignable
1562	*/
1563	#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1564	template <class... Args>
1565	inline reference emplace_back(Args&&... args)
1566	{
1567	if (BOOST_LIKELY(this->back_free_capacity() != 0)){
1568	pointer const p = m_.buffer + m_.back_idx;
1569	this->alloc_construct(p, boost::forward<Args>(args)...);
1570	++m_.back_idx;
1571	BOOST_ASSERT(invariants_ok());
1572	return *p;
1573	}
1574	else {
1575	typedef dtl::insert_emplace_proxy<allocator_type, Args...> proxy_t;
1576	return *this->insert_range_slow_path(this->end(), 1, proxy_t(::boost::forward<Args>(args)...));
1577	}
1578	}
1579
1580	#else //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1581
1582	#define BOOST_CONTAINER_DEVECTOR_EMPLACE_BACK(N) \
1583	BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1584	inline reference emplace_back(BOOST_MOVE_UREF##N)\
1585	{\
1586	if (this->back_free_capacity()){\
1587	pointer const p = m_.buffer + m_.back_idx;\
1588	this->alloc_construct(p BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
1589	++m_.back_idx;\
1590	return *p;\
1591	}\
1592	else {\
1593	typedef dtl::insert_emplace_proxy_arg##N<allocator_type BOOST_MOVE_I##N BOOST_MOVE_TARG##N> proxy_t;\
1594	return *this->insert_range_slow_path(this->end(), 1, proxy_t(BOOST_MOVE_FWD##N));\
1595	}\
1596	}\
1597	//
1598	BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_DEVECTOR_EMPLACE_BACK)
1599	#undef BOOST_CONTAINER_DEVECTOR_EMPLACE_BACK
1600
1601	#endif //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1602
1603
1604	#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1605	/**
1606	* [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
1607	*
1608	* **Effects**: Pushes the copy of `x` to the back of the devector.
1609	* Invalidates iterators if reallocation is needed.
1610	* (`back_free_capacity() == 0`)
1611	*
1612	* **Requires**: `T` shall be [CopyInsertable] into `*this`.
1613	*
1614	* **Exceptions**: Strong exception guarantee.
1615	*
1616	* **Complexity**: Amortized constant in the size of `*this`.
1617	* (Constant, if `back_free_capacity() > 0`)
1618	*/
1619	void push_back(const T& x);
1620
1621	/**
1622	* [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
1623	*
1624	* **Effects**: Move constructs a new element at the back of the devector using `x`.
1625	* Invalidates iterators if reallocation is needed.
1626	* (`back_free_capacity() == 0`)
1627	*
1628	* **Requires**: `T` shall be [MoveInsertable] into `*this`.
1629	*
1630	* **Exceptions**: Strong exception guarantee, not regarding the state of `x`.
1631	*
1632	* **Complexity**: Amortized constant in the size of `*this`.
1633	* (Constant, if `back_free_capacity() > 0`)
1634	*/
1635	void push_back(T&& x);
1636
1637	#else
1638	BOOST_MOVE_CONVERSION_AWARE_CATCH(push_back, T, void, priv_push_back)
1639	#endif
1640
1641	/**
1642	* **Effects**: Removes the last element of `*this`.
1643	*
1644	* **Precondition**: `!empty()`.
1645	*
1646	* **Postcondition**: `back_free_capacity()` is incremented by 1.
1647	*
1648	* **Complexity**: Constant.
1649	*/
1650	void pop_back() BOOST_NOEXCEPT
1651	{
1652	BOOST_ASSERT(! empty());
1653	--m_.back_idx;
1654	allocator_traits_type::destroy(get_allocator_ref(), boost::movelib::to_raw_pointer(m_.buffer + m_.back_idx));
1655	BOOST_ASSERT(invariants_ok());
1656	}
1657
1658	/**
1659	* **Effects**: Constructs a new element before the element pointed by `position`.
1660	* The element is constructed in-place, using the perfect forwarded `args`
1661	* as constructor arguments. Invalidates iterators if reallocation is needed.
1662	*
1663	* **Requires**: `T` shall be [EmplaceConstructible], and [MoveInsertable] into `*this`,
1664	* and [MoveAssignable].
1665	*
1666	* **Returns**: Iterator pointing to the newly constructed element.
1667	*
1668	* **Exceptions**: Strong exception guarantee if `T` is `NothrowConstructible`
1669	* and `NothrowAssignable`, Basic exception guarantee otherwise.
1670	*
1671	* **Complexity**: Linear in the size of `*this`.
1672	*
1673	* [EmplaceConstructible]: http://en.cppreference.com/w/cpp/concept/EmplaceConstructible
1674	* [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
1675	* [MoveAssignable]: http://en.cppreference.com/w/cpp/concept/MoveAssignable
1676	*/
1677	#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1678	template <class... Args>
1679	iterator emplace(const_iterator position, Args&&... args)
1680	{
1681	BOOST_ASSERT(position >= begin());
1682	BOOST_ASSERT(position <= end());
1683	typedef dtl::insert_emplace_proxy<allocator_type, Args...> proxy_t;
1684	bool prefer_move_back;
1685	if (position == end()){
1686	if(back_free_capacity()) // fast path
1687	{
1688	pointer const p = m_.buffer + m_.back_idx;
1689	this->alloc_construct(p, boost::forward<Args>(args)...);
1690	++m_.back_idx;
1691	return iterator(p);
1692	}
1693	prefer_move_back = true;
1694	}
1695	else if (position == begin()){
1696	if(front_free_capacity()) // secondary fast path
1697	{
1698	pointer const p = m_.buffer + (m_.front_idx - 1);
1699	this->alloc_construct(p, boost::forward<Args>(args)...);
1700	--m_.front_idx;
1701	return iterator(p);
1702	}
1703	prefer_move_back = false;
1704	}
1705	else{
1706	iterator nonconst_pos = unconst_iterator(i: position);
1707	prefer_move_back = should_move_back(i: position);
1708
1709	if(prefer_move_back){
1710	if(back_free_capacity()){
1711	boost::container::expand_forward_and_insert_nonempty_middle_alloc
1712	( get_allocator_ref()
1713	, boost::movelib::to_raw_pointer(nonconst_pos)
1714	, this->priv_raw_end()
1715	, 1, proxy_t(::boost::forward<Args>(args)...));
1716	++m_.back_idx;
1717	return nonconst_pos;
1718	}
1719	}
1720	else{
1721	if (front_free_capacity()){
1722	boost::container::expand_backward_and_insert_nonempty_middle_alloc
1723	(get_allocator_ref()
1724	, this->priv_raw_begin()
1725	, boost::movelib::to_raw_pointer(nonconst_pos)
1726	, 1, proxy_t(::boost::forward<Args>(args)...));
1727	--m_.front_idx;
1728	return --nonconst_pos;
1729	}
1730	}
1731	}
1732	return this->insert_range_slow_path(position, 1, proxy_t(::boost::forward<Args>(args)...));
1733	}
1734
1735	#else //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1736
1737	#define BOOST_CONTAINER_DEVECTOR_EMPLACE(N) \
1738	BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1739	iterator emplace(const_iterator position BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
1740	{\
1741	BOOST_ASSERT(position >= begin());\
1742	BOOST_ASSERT(position <= end());\
1743	typedef dtl::insert_emplace_proxy_arg##N<allocator_type BOOST_MOVE_I##N BOOST_MOVE_TARG##N> proxy_t;\
1744	bool prefer_move_back;\
1745	if (position == end()){\
1746	if(back_free_capacity())\
1747	{\
1748	pointer const p = m_.buffer + m_.back_idx;\
1749	this->alloc_construct(p BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
1750	++m_.back_idx;\
1751	return iterator(p);\
1752	}\
1753	prefer_move_back = true;\
1754	}\
1755	else if (position == begin()){\
1756	if(front_free_capacity())\
1757	{\
1758	pointer const p = m_.buffer + (m_.front_idx - 1);\
1759	this->alloc_construct(p BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
1760	--m_.front_idx;\
1761	return iterator(p);\
1762	}\
1763	prefer_move_back = false;\
1764	}\
1765	else{\
1766	iterator nonconst_pos = unconst_iterator(position);\
1767	prefer_move_back = should_move_back(position);\
1768	\
1769	if(prefer_move_back){\
1770	if(back_free_capacity()){\
1771	boost::container::expand_forward_and_insert_nonempty_middle_alloc\
1772	( get_allocator_ref()\
1773	, boost::movelib::to_raw_pointer(nonconst_pos)\
1774	, this->priv_raw_end()\
1775	, 1, proxy_t(BOOST_MOVE_FWD##N));\
1776	++m_.back_idx;\
1777	return nonconst_pos;\
1778	}\
1779	}\
1780	else{\
1781	if (front_free_capacity()){\
1782	boost::container::expand_backward_and_insert_nonempty_middle_alloc\
1783	(get_allocator_ref()\
1784	, this->priv_raw_begin()\
1785	, boost::movelib::to_raw_pointer(nonconst_pos)\
1786	, 1, proxy_t(BOOST_MOVE_FWD##N));\
1787	--m_.front_idx;\
1788	return --nonconst_pos;\
1789	}\
1790	}\
1791	}\
1792	return this->insert_range_slow_path(position, 1, proxy_t(BOOST_MOVE_FWD##N));\
1793	}\
1794	//
1795	BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_DEVECTOR_EMPLACE)
1796	#undef BOOST_CONTAINER_DEVECTOR_EMPLACE
1797
1798	#endif //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1799
1800
1801	#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1802	/**
1803	* **Effects**: Copy constructs a new element before the element pointed by `position`,
1804	* using `x` as constructor argument. Invalidates iterators if reallocation is needed.
1805	*
1806	* **Requires**: `T` shall be [CopyInsertable] into `*this` and and [CopyAssignable].
1807	*
1808	* **Returns**: Iterator pointing to the newly constructed element.
1809	*
1810	* **Exceptions**: Strong exception guarantee if `T` is `NothrowConstructible`
1811	* and `NothrowAssignable`, Basic exception guarantee otherwise.
1812	*
1813	* **Complexity**: Linear in the size of `*this`.
1814	*
1815	* [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
1816	* [CopyAssignable]: http://en.cppreference.com/w/cpp/concept/CopyAssignable
1817	*/
1818	iterator insert(const_iterator position, const T &x);
1819
1820	/**
1821	* **Effects**: Move constructs a new element before the element pointed by `position`,
1822	* using `x` as constructor argument. Invalidates iterators if reallocation is needed.
1823	*
1824	* **Requires**: `T` shall be [MoveInsertable] into `*this` and and [CopyAssignable].
1825	*
1826	* **Returns**: Iterator pointing to the newly constructed element.
1827	*
1828	* **Exceptions**: Strong exception guarantee if `T` is `NothrowConstructible`
1829	* and `NothrowAssignable` (not regarding the state of `x`),
1830	* Basic exception guarantee otherwise.
1831	*
1832	* **Complexity**: Linear in the size of `*this`.
1833	*
1834	* [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
1835	* [CopyAssignable]: http://en.cppreference.com/w/cpp/concept/CopyAssignable
1836	*/
1837	iterator insert(const_iterator position, T &&x);
1838	#else
1839	BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, T, iterator, priv_insert, const_iterator, const_iterator)
1840	#endif
1841
1842	/**
1843	* **Effects**: Copy constructs `n` elements before the element pointed by `position`,
1844	* using `x` as constructor argument. Invalidates iterators if reallocation is needed.
1845	*
1846	* **Requires**: `T` shall be [CopyInsertable] into `*this` and and [CopyAssignable].
1847	*
1848	* **Returns**: Iterator pointing to the first inserted element, or `position`, if `n` is zero.
1849	*
1850	* **Exceptions**: Strong exception guarantee if `T` is `NothrowConstructible`
1851	* and `NothrowAssignable`, Basic exception guarantee otherwise.
1852	*
1853	* **Complexity**: Linear in the size of `*this` and `n`.
1854	*
1855	* [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
1856	* [CopyAssignable]: http://en.cppreference.com/w/cpp/concept/CopyAssignable
1857	*/
1858	inline iterator insert(const_iterator position, size_type n, const T& x)
1859	{
1860	cvalue_iterator first(x, n);
1861	cvalue_iterator last = first + n;
1862	return this->insert_range(position, first, last);
1863	}
1864
1865	/**
1866	* **Effects**: Copy constructs elements before the element pointed by position
1867	* using each element in the range pointed by `first` and `last` as constructor arguments.
1868	* Invalidates iterators if reallocation is needed.
1869	*
1870	* **Requires**: `T` shall be [EmplaceConstructible] into `*this` from `*first`. If the specified iterator
1871	* does not meet the forward iterator requirements, `T` shall also be [MoveInsertable] into `*this`
1872	* and [MoveAssignable].
1873	*
1874	* **Precondition**: `first` and `last` are not iterators into `*this`.
1875	*
1876	* **Returns**: Iterator pointing to the first inserted element, or `position`, if `first == last`.
1877	*
1878	* **Complexity**: Linear in the size of `*this` and `N` (where `N` is the distance between `first` and `last`).
1879	* Makes only `N` calls to the constructor of `T` and no reallocations if iterators `first` and `last`
1880	* are of forward, bidirectional, or random access categories. It makes 2N calls to the copy constructor of `T`
1881	* and `O(log(N)) reallocations if they are just input iterators.
1882	*
1883	* **Exceptions**: Strong exception guarantee if `T` is `NothrowConstructible`
1884	* and `NothrowAssignable`, Basic exception guarantee otherwise.
1885	*
1886	* **Remarks**: Each iterator in the range `[first,last)` shall be dereferenced exactly once,
1887	* unless an exception is thrown.
1888	*
1889	* [EmplaceConstructible]: http://en.cppreference.com/w/cpp/concept/EmplaceConstructible
1890	* [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
1891	* [MoveAssignable]: http://en.cppreference.com/w/cpp/concept/MoveAssignable
1892	*/
1893	template <class InputIterator>
1894	iterator insert(const_iterator position, InputIterator first, InputIterator last
1895	//Input iterators
1896	BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_or
1897	< void
1898	BOOST_MOVE_I dtl::is_convertible<InputIterator BOOST_MOVE_I size_type>
1899	BOOST_MOVE_I dtl::is_not_input_iterator<InputIterator>
1900	>::type * = 0)
1901	)
1902	{
1903	if (position == end())
1904	{
1905	size_type insert_index = size();
1906
1907	for (; first != last; ++first)
1908	{
1909	this->emplace_back(*first);
1910	}
1911
1912	return begin() + insert_index;
1913	}
1914	else
1915	{
1916	const size_type insert_index = static_cast<size_type>(position - this->cbegin());
1917	const size_type old_size = static_cast<size_type>(this->size());
1918
1919	for (; first != last; ++first) {
1920	this->emplace_back(*first);
1921	}
1922	iterator rit (this->begin() + insert_index);
1923	boost::movelib::rotate_gcd(rit, this->begin() + old_size, this->begin() + this->size());
1924	return rit;
1925	}
1926	}
1927
1928	#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1929
1930	template <class ForwardIterator>
1931	inline iterator insert(const_iterator position, ForwardIterator first, ForwardIterator last
1932	//Other iterators
1933	BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_or
1934	< void
1935	BOOST_MOVE_I dtl::is_convertible<ForwardIterator BOOST_MOVE_I size_type>
1936	BOOST_MOVE_I dtl::is_input_iterator<ForwardIterator>
1937	>::type * = 0)
1938	)
1939	{
1940	return insert_range(position, first, last);
1941	}
1942
1943	#endif // ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1944
1945	#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1946	/** **Equivalent to**: `insert(position, il.begin(), il.end())` */
1947	inline iterator insert(const_iterator position, std::initializer_list<T> il)
1948	{
1949	return this->insert(position, il.begin(), il.end());
1950	}
1951	#endif
1952
1953	/**
1954	* [MoveAssignable]: http://en.cppreference.com/w/cpp/concept/MoveAssignable
1955	*
1956	* **Effects**: Destroys the element pointed by `position` and removes it from the devector.
1957	* Invalidates iterators.
1958	*
1959	* **Requires**: `T` shall be [MoveAssignable].
1960	*
1961	* **Precondition**: `position` must be in the range of `[begin(), end())`.
1962	*
1963	* **Returns**: Iterator pointing to the element immediately following the erased element
1964	* prior to its erasure. If no such element exists, `end()` is returned.
1965	*
1966	* **Exceptions**: Strong exception guarantee if `T` is `NothrowAssignable`,
1967	* Basic exception guarantee otherwise.
1968	*
1969	* **Complexity**: Linear in half the size of `*this`.
1970	*/
1971	iterator erase(const_iterator position)
1972	{
1973	return erase(position, position + 1);
1974	}
1975
1976	/**
1977	* [MoveAssignable]: http://en.cppreference.com/w/cpp/concept/MoveAssignable
1978	*
1979	* **Effects**: Destroys the range `[first,last)` and removes it from the devector.
1980	* Invalidates iterators.
1981	*
1982	* **Requires**: `T` shall be [MoveAssignable].
1983	*
1984	* **Precondition**: `[first,last)` must be in the range of `[begin(), end())`.
1985	*
1986	* **Returns**: Iterator pointing to the element pointed to by `last` prior to any elements
1987	* being erased. If no such element exists, `end()` is returned.
1988	*
1989	* **Exceptions**: Strong exception guarantee if `T` is `NothrowAssignable`,
1990	* Basic exception guarantee otherwise.
1991	*
1992	* **Complexity**: Linear in half the size of `*this`
1993	* plus the distance between `first` and `last`.
1994	*/
1995	iterator erase(const_iterator first, const_iterator last)
1996	{
1997	iterator nc_first = unconst_iterator(i: first);
1998	iterator nc_last = unconst_iterator(i: last);
1999	return erase(nc_first, nc_last);
2000	}
2001
2002	/**
2003	* [MoveAssignable]: http://en.cppreference.com/w/cpp/concept/MoveAssignable
2004	*
2005	* **Effects**: Destroys the range `[first,last)` and removes it from the devector.
2006	* Invalidates iterators.
2007	*
2008	* **Requires**: `T` shall be [MoveAssignable].
2009	*
2010	* **Precondition**: `[first,last)` must be in the range of `[begin(), end())`.
2011	*
2012	* **Returns**: Iterator pointing to the element pointed to by `last` prior to any elements
2013	* being erased. If no such element exists, `end()` is returned.
2014	*
2015	* **Exceptions**: Strong exception guarantee if `T` is `NothrowAssignable`,
2016	* Basic exception guarantee otherwise.
2017	*
2018	* **Complexity**: Linear in half the size of `*this`.
2019	*/
2020	iterator erase(iterator first, iterator last)
2021	{
2022	size_type front_distance = pos_to_index(i: last);
2023	size_type back_distance = size_type(end() - first);
2024	size_type n = boost::container::iterator_udistance(first, last);
2025
2026	if (front_distance < back_distance)
2027	{
2028	// move n to the right
2029	boost::container::move_backward(begin(), first, last);
2030
2031	for (iterator i = begin(); i != begin() + n; ++i)
2032	{
2033	allocator_traits_type::destroy(get_allocator_ref(), boost::movelib::to_raw_pointer(i));
2034	}
2035	//n is always less than max stored_size_type
2036	m_.set_front_idx(m_.front_idx + n);
2037
2038	BOOST_ASSERT(invariants_ok());
2039	return last;
2040	}
2041	else {
2042	// move n to the left
2043	boost::container::move(last, end(), first);
2044
2045	for (iterator i = end() - n; i != end(); ++i)
2046	{
2047	allocator_traits_type::destroy(get_allocator_ref(), boost::movelib::to_raw_pointer(i));
2048	}
2049	//n is always less than max stored_size_type
2050	m_.set_back_idx(m_.back_idx - n);
2051
2052	BOOST_ASSERT(invariants_ok());
2053	return first;
2054	}
2055	}
2056
2057	/**
2058	* [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
2059	*
2060	* **Effects**: exchanges the contents of `*this` and `b`.
2061	*
2062	* **Requires**: instances of `T` must be swappable by unqualified call of `swap`
2063	* and `T` must be [MoveInsertable] into `*this`.
2064	*
2065	* **Precondition**: The allocators should allow propagation or should compare equal.
2066	*
2067	* **Exceptions**: Basic exceptions guarantee if not `noexcept`.
2068	*
2069	* **Complexity**: Constant.
2070	*/
2071	void swap(devector& b)
2072	BOOST_NOEXCEPT_IF( allocator_traits_type::propagate_on_container_swap::value
2073	|| allocator_traits_type::is_always_equal::value)
2074	{
2075	BOOST_CONSTEXPR_OR_CONST bool propagate_alloc = allocator_traits_type::propagate_on_container_swap::value;
2076	BOOST_ASSERT(propagate_alloc || get_allocator_ref() == b.get_allocator_ref()); // else it's undefined behavior
2077
2078	swap_big_big(a&: *this, b);
2079
2080	// swap indices
2081	boost::adl_move_swap(m_.front_idx, b.m_.front_idx);
2082	boost::adl_move_swap(m_.back_idx, b.m_.back_idx);
2083
2084	//And now swap the allocator
2085	dtl::swap_alloc(this->get_allocator_ref(), b.get_allocator_ref(), dtl::bool_<propagate_alloc>());
2086
2087	BOOST_ASSERT( invariants_ok());
2088	BOOST_ASSERT(b.invariants_ok());
2089	}
2090
2091	/**
2092	* **Effects**: Destroys all elements in the devector.
2093	* Invalidates all references, pointers and iterators to the
2094	* elements of the devector.
2095	*
2096	* **Postcondition**: `empty() && front_free_capacity() == 0
2097	* && back_free_capacity() == old capacity`.
2098	*
2099	* **Complexity**: Linear in the size of `*this`.
2100	*
2101	* **Remarks**: Does not free memory.
2102	*/
2103	void clear() BOOST_NOEXCEPT
2104	{
2105	destroy_elements(begin: begin(), end: end());
2106	m_.front_idx = m_.back_idx = 0;
2107	}
2108
2109	BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
2110	friend bool operator==(const devector& x, const devector& y)
2111	{ return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin()); }
2112
2113	BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
2114	friend bool operator!=(const devector& x, const devector& y)
2115	{ return !(x == y); }
2116
2117	BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
2118	friend bool operator< (const devector& x, const devector& y)
2119	{ return boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); }
2120
2121	BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
2122	friend bool operator>(const devector& x, const devector& y)
2123	{ return y < x; }
2124
2125	BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
2126	friend bool operator<=(const devector& x, const devector& y)
2127	{ return !(y < x); }
2128
2129	BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
2130	friend bool operator>=(const devector& x, const devector& y)
2131	{ return !(x < y); }
2132
2133	inline friend void swap(devector& x, devector& y)
2134	BOOST_NOEXCEPT_IF( allocator_traits_type::propagate_on_container_swap::value
2135	|| allocator_traits_type::is_always_equal::value)
2136	{ x.swap(y); }
2137
2138	private:
2139
2140	BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
2141	size_type pos_to_index(const_iterator i) const
2142	{
2143	return static_cast<size_type>(i - cbegin());
2144	}
2145
2146	BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
2147	bool should_move_back(const_iterator i) const
2148	{
2149	return static_cast<size_type>(this->pos_to_index(i)) >= this->size()/2u;
2150	}
2151
2152	inline static iterator unconst_iterator(const_iterator i)
2153	{
2154	return boost::intrusive::pointer_traits<pointer>::const_cast_from(i);
2155	}
2156
2157	inline size_type front_capacity() const
2158	{
2159	return m_.back_idx;
2160	}
2161
2162	inline size_type back_capacity() const
2163	{
2164	return size_type(m_.capacity - m_.front_idx);
2165	}
2166
2167	#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
2168
2169	inline T* priv_raw_begin() BOOST_NOEXCEPT
2170	{ return boost::movelib::to_raw_pointer(m_.buffer) + m_.front_idx; }
2171
2172	inline T* priv_raw_end() BOOST_NOEXCEPT
2173	{ return boost::movelib::to_raw_pointer(m_.buffer) + m_.back_idx; }
2174
2175
2176	template <class U>
2177	inline void priv_push_front(BOOST_FWD_REF(U) u)
2178	{
2179	this->emplace_front(boost::forward<U>(u));
2180	}
2181
2182	template <class U>
2183	inline void priv_push_back(BOOST_FWD_REF(U) u)
2184	{
2185	this->emplace_back(boost::forward<U>(u));
2186	}
2187
2188	template <class U>
2189	inline iterator priv_insert(const_iterator pos, BOOST_FWD_REF(U) u)
2190	{
2191	return this->emplace(pos, boost::forward<U>(u));
2192	}
2193
2194	// allocator_type wrappers
2195
2196	inline allocator_type& get_allocator_ref() BOOST_NOEXCEPT
2197	{
2198	return static_cast<allocator_type&>(m_);
2199	}
2200
2201	inline const allocator_type& get_allocator_ref() const BOOST_NOEXCEPT
2202	{
2203	return static_cast<const allocator_type&>(m_);
2204	}
2205
2206	pointer allocate(size_type capacity)
2207	{
2208	pointer const p = impl::do_allocate(get_allocator_ref(), capacity);
2209	#ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
2210	++m_.capacity_alloc_count;
2211	#endif // BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
2212	return p;
2213	}
2214
2215	void destroy_elements(pointer begin, pointer end)
2216	{
2217	for (; begin != end; ++begin)
2218	{
2219	allocator_traits_type::destroy(get_allocator_ref(), boost::movelib::to_raw_pointer(begin));
2220	}
2221	}
2222
2223	void deallocate_buffer()
2224	{
2225	if (m_.buffer)
2226	{
2227	allocator_traits_type::deallocate(get_allocator_ref(), m_.buffer, m_.capacity);
2228	}
2229	}
2230
2231	#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
2232	template <typename... Args>
2233	inline void alloc_construct(pointer dst, Args&&... args)
2234	{
2235	allocator_traits_type::construct(
2236	get_allocator_ref(),
2237	boost::movelib::to_raw_pointer(dst),
2238	boost::forward<Args>(args)...
2239	);
2240	}
2241
2242	template <typename... Args>
2243	void construct_n(pointer buffer, size_type n, Args&&... args)
2244	{
2245	detail::construction_guard<allocator_type> ctr_guard(buffer, get_allocator_ref());
2246	guarded_construct_n(buffer, n, ctr_guard, boost::forward<Args>(args)...);
2247	ctr_guard.release();
2248	}
2249
2250	template <typename... Args>
2251	void guarded_construct_n(pointer buffer, size_type n, detail::construction_guard<allocator_type>& ctr_guard, Args&&... args)
2252	{
2253	for (size_type i = 0; i < n; ++i) {
2254	this->alloc_construct(buffer + i, boost::forward<Args>(args)...);
2255	ctr_guard.extend();
2256	}
2257	}
2258
2259	#else //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
2260
2261	#define BOOST_CONTAINER_DEVECTOR_ALLOC_CONSTRUCT(N) \
2262	BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
2263	inline void alloc_construct(pointer dst BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
2264	{\
2265	allocator_traits_type::construct(\
2266	get_allocator_ref(), boost::movelib::to_raw_pointer(dst) BOOST_MOVE_I##N BOOST_MOVE_FWD##N );\
2267	}\
2268	\
2269	BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
2270	void construct_n(pointer buffer, size_type n BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
2271	{\
2272	detail::construction_guard<allocator_type> ctr_guard(buffer, get_allocator_ref());\
2273	guarded_construct_n(buffer, n, ctr_guard BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
2274	ctr_guard.release();\
2275	}\
2276	\
2277	BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
2278	void guarded_construct_n(pointer buffer, size_type n, detail::construction_guard<allocator_type>& ctr_guard BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
2279	{\
2280	for (size_type i = 0; i < n; ++i) {\
2281	this->alloc_construct(buffer + i BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
2282	ctr_guard.extend();\
2283	}\
2284	}
2285	//
2286	BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_DEVECTOR_ALLOC_CONSTRUCT)
2287	#undef BOOST_CONTAINER_DEVECTOR_ALLOC_CONSTRUCT
2288
2289	#endif //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
2290
2291	size_type calculate_new_capacity(size_type requested_capacity)
2292	{
2293	size_type max = allocator_traits_type::max_size(this->get_allocator_ref());
2294	(clamp_by_stored_size_type)(max, stored_size_type());
2295	const size_type remaining_additional_cap = max - size_type(m_.capacity);
2296	const size_type min_additional_cap = requested_capacity - size_type(m_.capacity);
2297	if ( remaining_additional_cap < min_additional_cap )
2298	boost::container::throw_length_error(str: "devector: get_next_capacity, max size exceeded");
2299
2300	return growth_factor_type()( size_type(m_.capacity), min_additional_cap, max);
2301	}
2302
2303	void buffer_move_or_copy(pointer dst)
2304	{
2305	detail::construction_guard<allocator_type> guard(dst, get_allocator_ref());
2306
2307	buffer_move_or_copy(dst, guard);
2308
2309	guard.release();
2310	}
2311
2312	void buffer_move_or_copy(pointer dst, detail::construction_guard<allocator_type>& guard)
2313	{
2314	opt_move_or_copy(begin(), end(), dst, guard);
2315
2316	destroy_elements(begin: data(), end: data() + size());
2317	deallocate_buffer();
2318	}
2319
2320	template <typename Guard>
2321	void opt_move_or_copy(pointer begin, pointer end, pointer dst, Guard& guard)
2322	{
2323	// if trivial copy and default allocator, memcpy
2324	boost::container::uninitialized_move_alloc(get_allocator_ref(), begin, end, dst);
2325	guard.extend();
2326	}
2327
2328	#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
2329
2330	template <typename... Args>
2331	void resize_impl(size_type sz, Args&&... args)
2332	{
2333	const size_type old_sz = this->size();
2334	if (sz > old_sz)
2335	{
2336	const size_type n = sz - old_sz;
2337
2338	if (sz <= m_.capacity)
2339	{
2340	//Construct at back
2341	const size_type bfc = this->back_free_capacity();
2342	const size_type b = n < bfc ? n : bfc;
2343	construct_n(m_.buffer + m_.back_idx, b, boost::forward<Args>(args)...);
2344	m_.set_back_idx(m_.back_idx + b);
2345
2346	//Construct remaining at front
2347	const size_type f = n - b;
2348	construct_n(m_.buffer + m_.front_idx - f, f, boost::forward<Args>(args)...);
2349	m_.set_front_idx(m_.front_idx - f);
2350	}
2351	else
2352	{
2353	resize_back_slow_path(sz, n, boost::forward<Args>(args)...);
2354	}
2355	}
2356	else
2357	{
2358	const size_type n = old_sz - sz;
2359	const size_type new_bidx = m_.back_idx - n;
2360	destroy_elements(begin: m_.buffer + new_bidx, end: m_.buffer + m_.back_idx);
2361	m_.set_back_idx(new_bidx);
2362	}
2363	}
2364
2365	template <typename... Args>
2366	void resize_front_impl(size_type sz , Args&&... args)
2367	{
2368	const size_type old_sz = this->size();
2369	if (sz > old_sz)
2370	{
2371	const size_type n = sz - old_sz;
2372
2373	if (sz <= this->front_capacity())
2374	{
2375	construct_n(m_.buffer + m_.front_idx - n, n, boost::forward<Args>(args)...);
2376	m_.set_front_idx(m_.front_idx - n);
2377	}
2378	else
2379	{
2380	resize_front_slow_path(sz, n, boost::forward<Args>(args)...);
2381	}
2382	}
2383	else {
2384	const size_type n = old_sz - sz;
2385	const size_type new_fidx = m_.front_idx + n;
2386	destroy_elements(begin: m_.buffer + m_.front_idx, end: m_.buffer + new_fidx);
2387	m_.set_front_idx(new_fidx);
2388	}
2389	}
2390
2391	template <typename... Args>
2392	void resize_front_slow_path(size_type sz, size_type n, Args&&... args)
2393	{
2394	const size_type new_capacity = calculate_new_capacity(requested_capacity: sz + back_free_capacity());
2395	pointer new_buffer = allocate(capacity: new_capacity);
2396	allocation_guard new_buffer_guard(new_buffer, new_capacity, get_allocator_ref());
2397
2398	const size_type old_sz = this->size();
2399	const size_type new_old_elem_index = new_capacity - old_sz;
2400	const size_type new_elem_index = new_old_elem_index - n;
2401
2402	detail::construction_guard<allocator_type> guard(new_buffer + new_elem_index, get_allocator_ref());
2403	guarded_construct_n(new_buffer + new_elem_index, n, guard, boost::forward<Args>(args)...);
2404
2405	buffer_move_or_copy(new_buffer + new_old_elem_index, guard);
2406
2407	guard.release();
2408	new_buffer_guard.release();
2409
2410	m_.buffer = new_buffer;
2411	m_.set_capacity(new_capacity);
2412	m_.set_front_idx(new_elem_index);
2413	m_.set_back_idx(new_elem_index + old_sz + n);
2414	}
2415
2416	template <typename... Args>
2417	void resize_back_impl(size_type sz, Args&&... args)
2418	{
2419	const size_type old_sz = this->size();
2420	if (sz > old_sz)
2421	{
2422	const size_type n = sz - old_sz;
2423
2424	if (sz <= this->back_capacity())
2425	{
2426	construct_n(m_.buffer + m_.back_idx, n, boost::forward<Args>(args)...);
2427	m_.set_back_idx(m_.back_idx + n);
2428	}
2429	else
2430	{
2431	resize_back_slow_path(sz, n, boost::forward<Args>(args)...);
2432	}
2433	}
2434	else
2435	{
2436	const size_type n = old_sz - sz;
2437	const size_type new_bidx = m_.back_idx - n;
2438	destroy_elements(begin: m_.buffer + new_bidx, end: m_.buffer + m_.back_idx);
2439	m_.set_back_idx(new_bidx);
2440	}
2441	}
2442
2443	template <typename... Args>
2444	void resize_back_slow_path(size_type sz, size_type n, Args&&... args)
2445	{
2446	const size_type new_capacity = calculate_new_capacity(requested_capacity: sz + front_free_capacity());
2447	pointer new_buffer = allocate(capacity: new_capacity);
2448	allocation_guard new_buffer_guard(new_buffer, new_capacity, get_allocator_ref());
2449
2450	detail::construction_guard<allocator_type> guard(new_buffer + m_.back_idx, get_allocator_ref());
2451	guarded_construct_n(new_buffer + m_.back_idx, n, guard, boost::forward<Args>(args)...);
2452
2453	buffer_move_or_copy(new_buffer + m_.front_idx);
2454
2455	guard.release();
2456	new_buffer_guard.release();
2457
2458	m_.buffer = new_buffer;
2459	m_.set_capacity(new_capacity);
2460	m_.set_back_idx(m_.back_idx + n);
2461	}
2462
2463	#else //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
2464
2465	#define BOOST_CONTAINER_DEVECTOR_SLOW_PATH(N) \
2466	BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
2467	void resize_front_impl(size_type sz BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
2468	{\
2469	if (sz > size())\
2470	{\
2471	const size_type n = sz - size();\
2472	if (sz <= front_capacity()){\
2473	construct_n(m_.buffer + m_.front_idx - n, n BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
2474	m_.set_front_idx(m_.front_idx - n);\
2475	}\
2476	else\
2477	{\
2478	resize_front_slow_path(sz, n BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
2479	}\
2480	}\
2481	else {\
2482	while (this->size() > sz)\
2483	{\
2484	this->pop_front();\
2485	}\
2486	}\
2487	}\
2488	\
2489	BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
2490	void resize_front_slow_path(size_type sz, size_type n BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
2491	{\
2492	const size_type new_capacity = calculate_new_capacity(sz + back_free_capacity());\
2493	pointer new_buffer = allocate(new_capacity);\
2494	allocation_guard new_buffer_guard(new_buffer, new_capacity, get_allocator_ref());\
2495	\
2496	const size_type new_old_elem_index = new_capacity - size();\
2497	const size_type new_elem_index = new_old_elem_index - n;\
2498	\
2499	detail::construction_guard<allocator_type> guard(new_buffer + new_elem_index, get_allocator_ref());\
2500	guarded_construct_n(new_buffer + new_elem_index, n, guard BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
2501	\
2502	buffer_move_or_copy(new_buffer + new_old_elem_index, guard);\
2503	\
2504	guard.release();\
2505	new_buffer_guard.release();\
2506	m_.buffer = new_buffer;\
2507	m_.set_capacity(new_capacity);\
2508	m_.set_back_idx(new_old_elem_index + m_.back_idx - m_.front_idx);\
2509	m_.set_front_idx(new_elem_index);\
2510	}\
2511	\
2512	BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
2513	void resize_back_impl(size_type sz BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
2514	{\
2515	if (sz > size())\
2516	{\
2517	const size_type n = sz - size();\
2518	\
2519	if (sz <= back_capacity())\
2520	{\
2521	construct_n(m_.buffer + m_.back_idx, n BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
2522	m_.set_back_idx(m_.back_idx + n);\
2523	}\
2524	else\
2525	{\
2526	resize_back_slow_path(sz, n BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
2527	}\
2528	}\
2529	else\
2530	{\
2531	while (size() > sz)\
2532	{\
2533	pop_back();\
2534	}\
2535	}\
2536	}\
2537	\
2538	BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
2539	void resize_back_slow_path(size_type sz, size_type n BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
2540	{\
2541	const size_type new_capacity = calculate_new_capacity(sz + front_free_capacity());\
2542	pointer new_buffer = allocate(new_capacity);\
2543	allocation_guard new_buffer_guard(new_buffer, new_capacity, get_allocator_ref());\
2544	\
2545	detail::construction_guard<allocator_type> guard(new_buffer + m_.back_idx, get_allocator_ref());\
2546	guarded_construct_n(new_buffer + m_.back_idx, n, guard BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
2547	\
2548	buffer_move_or_copy(new_buffer + m_.front_idx);\
2549	\
2550	guard.release();\
2551	new_buffer_guard.release();\
2552	\
2553	m_.buffer = new_buffer;\
2554	m_.set_capacity(new_capacity);\
2555	m_.set_back_idx(m_.back_idx + n);\
2556	}\
2557	\
2558	//
2559	BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_DEVECTOR_SLOW_PATH)
2560	#undef BOOST_CONTAINER_DEVECTOR_SLOW_PATH
2561
2562	#endif //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
2563
2564	void reallocate_at(size_type new_capacity, size_type buffer_offset)
2565	{
2566	pointer new_buffer = allocate(capacity: new_capacity);
2567	{
2568	allocation_guard new_buffer_guard(new_buffer, new_capacity, get_allocator_ref());
2569	boost::container::uninitialized_move_alloc(get_allocator_ref(), this->begin(), this->end(), new_buffer + buffer_offset);
2570	new_buffer_guard.release();
2571	}
2572	destroy_elements(begin: m_.buffer + m_.front_idx, end: m_.buffer + m_.back_idx);
2573	deallocate_buffer();
2574
2575	m_.buffer = new_buffer;
2576	//Safe cast, allocate() will handle stored_size_type overflow
2577	m_.set_capacity(new_capacity);
2578	m_.set_back_idx(size_type(m_.back_idx - m_.front_idx) + buffer_offset);
2579	m_.set_front_idx(buffer_offset);
2580
2581	BOOST_ASSERT(invariants_ok());
2582	}
2583
2584	template <typename ForwardIterator>
2585	iterator insert_range(const_iterator position, ForwardIterator first, ForwardIterator last)
2586	{
2587	BOOST_ASSERT(position >= begin());
2588	BOOST_ASSERT(position <= end());
2589	typedef dtl::insert_range_proxy<allocator_type, ForwardIterator> proxy_t;
2590
2591	size_type const n = boost::container::iterator_udistance(first, last);
2592	bool prefer_move_back;
2593	if (BOOST_UNLIKELY(!n)) {
2594	return begin() + size_type(position - cbegin());
2595	}
2596	else if (position == end()) {
2597	if(back_free_capacity() >= n) // fast path
2598	{
2599	iterator r(this->end());
2600	boost::container::uninitialized_copy_alloc(get_allocator_ref(), first, last, this->priv_raw_end());
2601	m_.set_back_idx(m_.back_idx + n);
2602	return r;
2603	}
2604	prefer_move_back = true;
2605	}
2606	else if (position == begin()) {
2607	if(front_free_capacity() >= n) {// secondary fast path
2608	boost::container::uninitialized_copy_alloc(get_allocator_ref(), first, last, this->priv_raw_begin() - n);
2609	m_.set_front_idx(m_.front_idx - n);
2610	return begin();
2611	}
2612	prefer_move_back = false;
2613	}
2614	else{
2615	iterator nonconst_pos = unconst_iterator(i: position);
2616	prefer_move_back = should_move_back(i: position);
2617
2618	if(prefer_move_back){
2619	if(back_free_capacity() >= n){
2620	boost::container::expand_forward_and_insert_nonempty_middle_alloc
2621	( get_allocator_ref()
2622	, boost::movelib::to_raw_pointer(nonconst_pos)
2623	, this->priv_raw_end()
2624	, n, proxy_t(first));
2625	m_.set_back_idx(m_.back_idx + n);
2626	return nonconst_pos;
2627	}
2628	}
2629	else{
2630	if (front_free_capacity() >= n){
2631	boost::container::expand_backward_and_insert_nonempty_middle_alloc
2632	( get_allocator_ref()
2633	, this->priv_raw_begin()
2634	, boost::movelib::to_raw_pointer(nonconst_pos)
2635	, n, proxy_t(first));
2636	m_.set_front_idx(m_.front_idx - n);
2637	return (nonconst_pos -= n);
2638	}
2639	}
2640	}
2641	return this->insert_range_slow_path(position, n, proxy_t(first));
2642	}
2643
2644	template <class InsertionProxy>
2645	BOOST_CONTAINER_NOINLINE iterator insert_range_slow_path
2646	(const_iterator p, const size_type n, const InsertionProxy proxy)
2647	{
2648	size_type const back_free_cap = back_free_capacity();
2649	size_type const front_free_cap = front_free_capacity();
2650	size_type const free_cap = front_free_cap + back_free_cap;
2651	size_type const index = size_type(p - cbegin());
2652
2653	size_type const cap = m_.capacity;
2654	//Test if enough free memory would be left
2655	if (free_cap >= n && (free_cap - n) >= cap/devector_min_free_fraction) {
2656	//Make sure relocation is happening because there was no enough space
2657	size_type const old_size = this->size();
2658	BOOST_ASSERT(should_move_back(p) ? (back_free_cap < n) : (front_free_cap < n));
2659
2660	T* const raw_pos = const_cast<T*>(boost::movelib::to_raw_pointer(p));
2661	size_type const new_size = old_size + n;
2662	size_type const new_front_idx = (cap - new_size) / 2u;
2663
2664	T* const raw_beg = this->priv_raw_begin();
2665	T* const new_raw_beg = raw_beg - std::ptrdiff_t(m_.front_idx - new_front_idx);
2666	m_.back_idx = 0u;
2667	m_.front_idx = 0u;
2668	boost::container::expand_backward_forward_and_insert_alloc
2669	(raw_beg, old_size, new_raw_beg, raw_pos, n, proxy, get_allocator_ref());
2670	m_.set_front_idx(new_front_idx);
2671	m_.set_back_idx(new_front_idx + new_size);
2672	}
2673	else {
2674	// reallocate
2675	const size_type new_capacity = calculate_new_capacity(requested_capacity: m_.capacity + n);
2676	pointer new_buffer = allocate(capacity: new_capacity);
2677
2678	// guard allocation
2679	allocation_guard new_buffer_guard(new_buffer, new_capacity, get_allocator_ref());
2680
2681	size_type const old_size = this->size();
2682	const size_type new_front_index = (new_capacity - old_size - n) / 2u;
2683
2684	T* const raw_pos = const_cast<T*>(boost::movelib::to_raw_pointer(p));
2685	T* const raw_new_start = const_cast<T*>(boost::movelib::to_raw_pointer(new_buffer)) + new_front_index;
2686
2687	boost::container::uninitialized_move_and_insert_alloc
2688	(get_allocator_ref(), this->priv_raw_begin(), raw_pos, this->priv_raw_end(), raw_new_start, n, proxy);
2689	new_buffer_guard.release();
2690
2691	// cleanup
2692	destroy_elements(begin: begin(), end: end());
2693	deallocate_buffer();
2694
2695	// rebind members
2696	m_.set_capacity(new_capacity);
2697	m_.buffer = new_buffer;
2698	m_.set_back_idx(new_front_index + old_size + n);
2699	m_.set_front_idx(new_front_index);
2700	}
2701	return begin() + index;
2702	}
2703
2704
2705	template <typename Iterator>
2706	void construct_from_range(Iterator begin, Iterator end)
2707	{
2708	allocation_guard buffer_guard(m_.buffer, m_.capacity, get_allocator_ref());
2709	boost::container::uninitialized_copy_alloc(get_allocator_ref(), begin, end, m_.buffer);
2710	buffer_guard.release();
2711	}
2712
2713	template <typename ForwardIterator>
2714	void allocate_and_copy_range(ForwardIterator first, ForwardIterator last)
2715	{
2716	size_type n = boost::container::iterator_udistance(first, last);
2717
2718	pointer new_buffer = n ? allocate(capacity: n) : pointer();
2719	allocation_guard new_buffer_guard(new_buffer, n, get_allocator_ref());
2720	boost::container::uninitialized_copy_alloc(get_allocator_ref(), first, last, new_buffer);
2721	destroy_elements(begin: begin(), end: end());
2722	deallocate_buffer();
2723
2724	m_.set_capacity(n);
2725	m_.buffer = new_buffer;
2726	m_.front_idx = 0;
2727	m_.set_back_idx(n);
2728
2729	new_buffer_guard.release();
2730	}
2731
2732	static void swap_big_big(devector& a, devector& b) BOOST_NOEXCEPT
2733	{
2734	boost::adl_move_swap(a.m_.capacity, b.m_.capacity);
2735	boost::adl_move_swap(a.m_.buffer, b.m_.buffer);
2736	}
2737
2738	template <typename ForwardIterator>
2739	void overwrite_buffer_impl(ForwardIterator first, ForwardIterator last, dtl::true_)
2740	{
2741	const size_type n = boost::container::iterator_udistance(first, last);
2742
2743	BOOST_ASSERT(m_.capacity >= n);
2744	boost::container::uninitialized_copy_alloc_n
2745	( get_allocator_ref(), first
2746	, n, boost::movelib::to_raw_pointer(m_.buffer));
2747	m_.front_idx = 0;
2748	m_.set_back_idx(n);
2749	}
2750
2751	template <typename InputIterator>
2752	InputIterator overwrite_buffer_impl(InputIterator first, InputIterator last, dtl::false_)
2753	{
2754	pointer pos = m_.buffer;
2755	detail::construction_guard<allocator_type> front_guard(pos, get_allocator_ref());
2756
2757	while (first != last && pos != begin()) {
2758	this->alloc_construct(pos++, *first++);
2759	front_guard.extend();
2760	}
2761
2762	while (first != last && pos != end()) {
2763	*pos++ = *first++;
2764	}
2765
2766	detail::construction_guard<allocator_type> back_guard(pos, get_allocator_ref());
2767
2768	iterator capacity_end = m_.buffer + m_.capacity;
2769	while (first != last && pos != capacity_end) {
2770	this->alloc_construct(pos++, *first++);
2771	back_guard.extend();
2772	}
2773
2774	pointer destroy_after = dtl::min_value(dtl::max_value(begin(), pos), end());
2775	destroy_elements(begin: destroy_after, end: end());
2776
2777	front_guard.release();
2778	back_guard.release();
2779
2780	m_.front_idx = 0;
2781	m_.set_back_idx(pos_to_index(i: pos));
2782	return first;
2783	}
2784
2785	template <typename ForwardIterator>
2786	inline void overwrite_buffer(ForwardIterator first, ForwardIterator last)
2787	{
2788	this->overwrite_buffer_impl(first, last,
2789	dtl::bool_<dtl::is_trivially_destructible<T>::value>());
2790	}
2791
2792	bool invariants_ok()
2793	{
2794	return (! m_.capacity || m_.buffer )
2795	&& m_.front_idx <= m_.back_idx
2796	&& m_.back_idx <= m_.capacity;
2797	}
2798
2799	struct impl : allocator_type
2800	{
2801	BOOST_MOVABLE_BUT_NOT_COPYABLE(impl)
2802
2803	public:
2804	allocator_type &get_al()
2805	{ return *this; }
2806
2807	static pointer do_allocate(allocator_type &a, size_type cap)
2808	{
2809	if (cap) {
2810	//First detect overflow on smaller stored_size_types
2811	if (cap > stored_size_type(-1)){
2812	boost::container::throw_length_error(str: "get_next_capacity, allocator's max size reached");
2813	}
2814	return allocator_traits_type::allocate(a, cap);
2815	}
2816	else {
2817	return pointer();
2818	}
2819	}
2820
2821	impl()
2822	: allocator_type(), buffer(), front_idx(), back_idx(), capacity()
2823	#ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
2824	, capacity_alloc_count(0)
2825	#endif
2826	{}
2827
2828	explicit impl(const allocator_type &a)
2829	: allocator_type(a), buffer(), front_idx(), back_idx(), capacity()
2830	#ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
2831	, capacity_alloc_count(0)
2832	#endif
2833	{}
2834
2835	impl(reserve_uninitialized_t, const allocator_type& a, size_type c)
2836	: allocator_type(a), buffer(do_allocate(a&: get_al(), cap: c) )
2837	//static cast sizes, as the allocation function will take care of overflows
2838	, front_idx(static_cast<stored_size_type>(0u))
2839	, back_idx(static_cast<stored_size_type>(c))
2840	, capacity(static_cast<stored_size_type>(c))
2841	#ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
2842	, capacity_alloc_count(size_type(buffer != pointer()))
2843	#endif
2844	{}
2845
2846	impl(reserve_only_tag_t, const allocator_type &a, size_type const ffc, size_type const bfc)
2847	: allocator_type(a), buffer(do_allocate(a&: get_al(), cap: ffc+bfc) )
2848	//static cast sizes, as the allocation function will take care of overflows
2849	, front_idx(static_cast<stored_size_type>(ffc))
2850	, back_idx(static_cast<stored_size_type>(ffc))
2851	, capacity(static_cast<stored_size_type>(ffc + bfc))
2852	#ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
2853	, capacity_alloc_count(size_type(buffer != pointer()))
2854	#endif
2855	{}
2856
2857	impl(reserve_only_tag_t, const allocator_type &a, size_type const c)
2858	: allocator_type(a), buffer(do_allocate(a&: get_al(), cap: c) )
2859	//static cast sizes, as the allocation function will take care of overflows
2860	, front_idx(static_cast<stored_size_type>(c/2u))
2861	, back_idx(static_cast<stored_size_type>(c/2u))
2862	, capacity(static_cast<stored_size_type>(c))
2863	#ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
2864	, capacity_alloc_count(size_type(buffer != pointer()))
2865	#endif
2866	{}
2867
2868	impl(review_implementation_t, const allocator_type &a, pointer p, size_type fi, size_type bi, size_type c)
2869	: allocator_type(a), buffer(p)
2870	//static cast sizes, as the allocation function will take care of overflows
2871	, front_idx(static_cast<stored_size_type>(fi))
2872	, back_idx(static_cast<stored_size_type>(bi))
2873	, capacity(static_cast<stored_size_type>(c))
2874	#ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
2875	, capacity_alloc_count(0)
2876	#endif
2877	{}
2878
2879	impl(BOOST_RV_REF(impl) m)
2880	: allocator_type(BOOST_MOVE_BASE(allocator_type, m))
2881	, buffer(static_cast<impl&>(m).buffer)
2882	, front_idx(static_cast<impl&>(m).front_idx)
2883	, back_idx(static_cast<impl&>(m).back_idx)
2884	, capacity(static_cast<impl&>(m).capacity)
2885	#ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
2886	, capacity_alloc_count(0)
2887	#endif
2888	{
2889	impl &i = static_cast<impl&>(m);
2890	// buffer is already acquired, reset rhs
2891	i.capacity = 0u;
2892	i.buffer = pointer();
2893	i.front_idx = 0;
2894	i.back_idx = 0;
2895	}
2896
2897	inline void set_back_idx(size_type bi)
2898	{
2899	back_idx = static_cast<stored_size_type>(bi);
2900	}
2901
2902	inline void set_front_idx(size_type fi)
2903	{
2904	front_idx = static_cast<stored_size_type>(fi);
2905	}
2906
2907	inline void set_capacity(size_type c)
2908	{
2909	capacity = static_cast<stored_size_type>(c);
2910	}
2911
2912	pointer buffer;
2913	stored_size_type front_idx;
2914	stored_size_type back_idx;
2915	stored_size_type capacity;
2916	#ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
2917	size_type capacity_alloc_count;
2918	#endif
2919	} m_;
2920
2921	#ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
2922	public:
2923	void reset_alloc_stats()
2924	{
2925	m_.capacity_alloc_count = 0;
2926	}
2927
2928	size_type get_alloc_count() const
2929	{
2930	return m_.capacity_alloc_count;
2931	}
2932
2933	#endif // ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
2934
2935	#endif // ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
2936	};
2937
2938	}} // namespace boost::container
2939
2940	#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
2941
2942	namespace boost {
2943
2944	//!has_trivial_destructor_after_move<> == true_type
2945	//!specialization for optimizations
2946	template <class T, class Allocator, class Options>
2947	struct has_trivial_destructor_after_move<boost::container::devector<T, Allocator, Options> >
2948	{
2949	typedef typename boost::container::devector<T, Allocator, Options>::allocator_type allocator_type;
2950	typedef typename ::boost::container::allocator_traits<allocator_type>::pointer pointer;
2951	static const bool value = ::boost::has_trivial_destructor_after_move<allocator_type>::value &&
2952	::boost::has_trivial_destructor_after_move<pointer>::value;
2953	};
2954
2955	}
2956
2957	#endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
2958
2959	#include <boost/container/detail/config_end.hpp>
2960
2961	#endif // BOOST_CONTAINER_DEVECTOR_HPP
2962