1 //////////////////////////////////////////////////////////////////////////////
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)
8 // See http://www.boost.org/libs/container for documentation.
10 //////////////////////////////////////////////////////////////////////////////
12 #ifndef BOOST_CONTAINER_DEVECTOR_HPP
13 #define BOOST_CONTAINER_DEVECTOR_HPP
15 #include <boost/container/detail/config_begin.hpp>
16 #include <boost/container/detail/workaround.hpp>
18 //#include <algorithm>
19 #include <cstring> // memcpy
21 #include <boost/assert.hpp>
22 #include <boost/aligned_storage.hpp>
24 #include <boost/container/detail/copy_move_algo.hpp>
25 #include <boost/container/new_allocator.hpp> //new_allocator
26 #include <boost/container/allocator_traits.hpp> //allocator_traits
27 #include <boost/container/detail/algorithm.hpp> //equal()
28 #include <boost/container/throw_exception.hpp>
29 #include <boost/container/options.hpp>
31 #include <boost/container/detail/guards_dended.hpp>
32 #include <boost/container/detail/iterator.hpp>
33 #include <boost/container/detail/iterators.hpp>
34 #include <boost/container/detail/destroyers.hpp>
35 #include <boost/container/detail/min_max.hpp>
36 #include <boost/container/detail/next_capacity.hpp>
37 #include <boost/container/detail/alloc_helpers.hpp>
40 #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
41 #include <boost/move/detail/fwd_macros.hpp>
43 #include <boost/move/detail/move_helpers.hpp>
44 #include <boost/move/adl_move_swap.hpp>
45 #include <boost/move/iterator.hpp>
46 #include <boost/move/traits.hpp>
47 #include <boost/move/utility_core.hpp>
48 #include <boost/move/detail/to_raw_pointer.hpp>
49 #include <boost/move/algo/detail/merge.hpp>
50 #include <boost/move/detail/force_ptr.hpp>
52 #include <boost/type_traits/is_nothrow_move_constructible.hpp>
55 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
56 #include <initializer_list> //for std::initializer_list
62 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
64 struct growth_factor_60;
66 template<class Options, class AllocatorSizeType>
67 struct get_devector_opt
69 typedef devector_opt< typename default_if_void<typename Options::growth_factor_type, growth_factor_60>::type
70 , typename default_if_void<typename Options::stored_size_type, AllocatorSizeType>::type
74 template<class AllocatorSizeType>
75 struct get_devector_opt<void, AllocatorSizeType>
77 typedef vector_opt<growth_factor_60, AllocatorSizeType> type;
80 #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
82 struct reserve_only_tag_t {};
83 //struct unsafe_uninitialized_tag_t {};
86 * A vector-like sequence container providing front and back operations
87 * (e.g: `push_front`/`pop_front`/`push_back`/`pop_back`) with amortized constant complexity
88 * and unsafe methods geared towards additional performance.
90 * Models the [SequenceContainer], [ReversibleContainer], and [AllocatorAwareContainer] concepts.
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.
97 * **Definition**: `T` is `NothrowConstructible` if it's either nothrow move constructible or
98 * nothrow copy constructible.
100 * **Definition**: `T` is `NothrowAssignable` if it's either nothrow move assignable or
101 * nothrow copy assignable.
103 * **Exceptions**: The exception specifications assume `T` is nothrow [Destructible].
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.
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
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()`.
123 * **Remark**: If a method invalidates some iterators, it also invalidates references
124 * and pointers to the elements pointed by the invalidated iterators.
128 * @ref devector_growth_policy models the `GrowthFactor` concept.
130 * [SequenceContainer]: http://en.cppreference.com/w/cpp/concept/SequenceContainer
131 * [ReversibleContainer]: http://en.cppreference.com/w/cpp/concept/ReversibleContainer
132 * [AllocatorAwareContainer]: http://en.cppreference.com/w/cpp/concept/AllocatorAwareContainer
133 * [DefaultInsertable]: http://en.cppreference.com/w/cpp/concept/DefaultInsertable
134 * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
135 * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
136 * [Erasable]: http://en.cppreference.com/w/cpp/concept/Erasable
137 * [DefaultConstructible]: http://en.cppreference.com/w/cpp/concept/DefaultConstructible
138 * [Destructible]: http://en.cppreference.com/w/cpp/concept/Destructible
139 * [EmplaceConstructible]: http://en.cppreference.com/w/cpp/concept/EmplaceConstructible
140 * [MoveAssignable]: http://en.cppreference.com/w/cpp/concept/MoveAssignable
141 * [CopyAssignable]: http://en.cppreference.com/w/cpp/concept/CopyAssignable
143 template < typename T, class A BOOST_CONTAINER_DOCONLY(= void), class Options BOOST_CONTAINER_DOCONLY(= void)>
146 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
147 typedef boost::container::allocator_traits
148 <typename real_allocator<T, A>::type> allocator_traits_type;
149 typedef typename allocator_traits_type::size_type alloc_size_type;
150 typedef typename get_devector_opt<Options, alloc_size_type>::type options_type;
151 typedef typename options_type::growth_factor_type growth_factor_type;
152 typedef typename options_type::stored_size_type stored_size_type;
154 #endif // ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
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;
175 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
177 BOOST_COPYABLE_AND_MOVABLE(devector)
179 // Guard to deallocate buffer on exception
180 typedef typename detail::allocation_guard<allocator_type> allocation_guard;
182 // Random access pseudo iterator always yielding to the same result
183 typedef constant_iterator<T> cvalue_iterator;
185 #endif // ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
187 // Standard Interface
189 // construct/copy/destroy
192 * **Effects**: Constructs an empty devector.
194 * **Postcondition**: `empty() && front_free_capacity() == 0
195 * && back_free_capacity() == 0`.
197 * **Complexity**: Constant.
199 devector() BOOST_NOEXCEPT
204 * **Effects**: Constructs an empty devector, using the specified allocator.
206 * **Postcondition**: `empty() && front_free_capacity() == 0
207 * && back_free_capacity() == 0`.
209 * **Complexity**: Constant.
211 explicit devector(const allocator_type& allocator) BOOST_NOEXCEPT
216 * **Effects**: Constructs an empty devector, using the specified allocator
217 * and reserves `n` slots as if `reserve(n)` was called.
219 * **Postcondition**: `empty() && front_free_capacity() == 0
220 * && back_free_capacity() >= n`.
222 * **Exceptions**: Strong exception guarantee.
224 * **Complexity**: Constant.
226 devector(size_type n, reserve_only_tag_t, const allocator_type& allocator = allocator_type())
227 : m_(allocator, 0u, 0u, n)
231 * **Effects**: Constructs an empty devector, using the specified allocator
232 * and reserves `front_cap + back_cap` slots as if `reserve_front(front_cap)` and
233 * `reserve_back(back_cap)` was called.
235 * **Postcondition**: `empty() && front_free_capacity() == front_cap
236 * && back_free_capacity() >= back_cap`.
238 * **Exceptions**: Strong exception guarantee.
240 * **Complexity**: Constant.
242 devector(size_type front_cap, size_type back_cap, reserve_only_tag_t, const allocator_type& allocator = allocator_type())
243 : m_( allocator, front_cap, back_cap, front_cap + back_cap)
247 * [DefaultInsertable]: http://en.cppreference.com/w/cpp/concept/DefaultInsertable
249 * **Effects**: Constructs a devector with `n` default-inserted elements using the specified allocator.
251 * **Requires**: `T` shall be [DefaultInsertable] into `*this`.
253 * **Postcondition**: `size() == n && front_free_capacity() == 0`.
255 * **Exceptions**: Strong exception guarantee.
257 * **Complexity**: Linear in `n`.
259 explicit devector(size_type n, const allocator_type& allocator = allocator_type())
260 : m_(allocator, 0u, n, n)
262 // Cannot use construct_from_range/constant_iterator and copy_range,
263 // because we are not allowed to default construct T
264 allocation_guard buffer_guard(m_.buffer, m_.capacity, get_allocator_ref());
265 detail::construction_guard<allocator_type> copy_guard(m_.buffer, get_allocator_ref());
267 for (size_type i = 0; i < n; ++i)
269 this->alloc_construct(m_.buffer + i);
273 copy_guard.release();
274 buffer_guard.release();
276 BOOST_ASSERT(invariants_ok());
280 * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
282 * **Effects**: Constructs a devector with `n` copies of `value`, using the specified allocator.
284 * **Requires**: `T` shall be [CopyInsertable] into `*this`.
286 * **Postcondition**: `size() == n && front_free_capacity() == 0`.
288 * **Exceptions**: Strong exception guarantee.
290 * **Complexity**: Linear in `n`.
292 devector(size_type n, const T& value, const allocator_type& allocator = allocator_type())
293 : m_(allocator, n ? allocate(n): pointer(), 0u, n, n)
295 construct_from_range(cvalue_iterator(value, n), cvalue_iterator());
296 BOOST_ASSERT(invariants_ok());
300 * **Effects**: Constructs a devector equal to the range `[first,last)`, using the specified allocator.
302 * **Requires**: `T` shall be [EmplaceConstructible] into `*this` from `*first`. If the specified
303 * iterator does not meet the forward iterator requirements, `T` shall also be [MoveInsertable]
306 * **Postcondition**: `size() == boost::container::iterator_distance(first, last)
308 * **Exceptions**: Strong exception guarantee.
310 * **Complexity**: Makes only `N` calls to the copy constructor of `T` (where `N` is the distance between `first`
311 * and `last`), at most one allocation and no reallocations if iterators first and last are of forward,
312 * bidirectional, or random access categories. It makes `O(N)` calls to the copy constructor of `T`
313 * and `O(log(N)) reallocations if they are just input iterators.
315 * **Remarks**: Each iterator in the range `[first,last)` shall be dereferenced exactly once,
316 * unless an exception is thrown.
318 * [EmplaceConstructible]: http://en.cppreference.com/w/cpp/concept/EmplaceConstructible
319 * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
321 template <class InputIterator>
322 devector(InputIterator first, InputIterator last, const allocator_type& allocator = allocator_type()
324 BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_or
326 BOOST_MOVE_I dtl::is_convertible<InputIterator BOOST_MOVE_I size_type>
327 BOOST_MOVE_I dtl::is_not_input_iterator<InputIterator>
330 : m_(allocator, pointer(), 0u, 0u, 0u)
332 while (first != last) {
333 this->emplace_back(*first++);
336 BOOST_ASSERT(invariants_ok());
339 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
341 template <class ForwardIterator>
342 devector(ForwardIterator first, ForwardIterator last, const allocator_type& allocator = allocator_type()
344 BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_or
346 BOOST_MOVE_I dtl::is_convertible<ForwardIterator BOOST_MOVE_I size_type>
347 BOOST_MOVE_I dtl::is_input_iterator<ForwardIterator>
352 const size_type n = boost::container::iterator_udistance(first, last);
353 m_.buffer = n ? allocate(n) : pointer();
355 //this->allocate(n) will take care of overflows
358 //construct_from_range releases memory on failure
359 this->construct_from_range(first, last);
360 BOOST_ASSERT(invariants_ok());
363 #endif // ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
366 * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
368 * **Effects**: Copy constructs a devector.
370 * **Requires**: `T` shall be [CopyInsertable] into `*this`.
372 * **Postcondition**: `this->size() == x.size() && front_free_capacity() == 0`.
374 * **Exceptions**: Strong exception guarantee.
376 * **Complexity**: Linear in the size of `x`.
378 devector(const devector& x)
379 : m_( allocator_traits_type::select_on_container_copy_construction(x.get_allocator_ref()))
381 const size_type n = x.size();
382 m_.buffer = n ? allocate(n) : pointer();
384 //this->allocate(n) will take care of overflows
387 this->construct_from_range(x.begin(), x.end());
388 BOOST_ASSERT(invariants_ok());
392 * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
394 * **Effects**: Copy constructs a devector, using the specified allocator.
396 * **Requires**: `T` shall be [CopyInsertable] into `*this`.
398 * **Postcondition**: `this->size() == x.size() && front_free_capacity() == 0`.
400 * **Exceptions**: Strong exception guarantee.
402 * **Complexity**: Linear in the size of `x`.
404 devector(const devector& x, const allocator_type& allocator)
405 : m_(allocator, pointer(), 0u, 0u, 0u)
407 const size_type n = x.size();
408 m_.buffer = n ? this->allocate(n) : pointer();
410 //this->allocate(n) will take care of overflows
413 this->construct_from_range(x.begin(), x.end());
414 BOOST_ASSERT(invariants_ok());
418 * **Effects**: Moves `rhs`'s resources to `*this`.
420 * **Throws**: Nothing.
422 * **Postcondition**: `rhs` is left in an unspecified but valid state.
424 * **Exceptions**: Strong exception guarantee if not `noexcept`.
426 * **Complexity**: Constant.
428 devector(BOOST_RV_REF(devector) rhs) BOOST_NOEXCEPT_OR_NOTHROW
429 : m_(::boost::move(rhs.get_allocator_ref()), rhs.m_.buffer, rhs.m_.front_idx, rhs.m_.back_idx, rhs.capacity())
431 // buffer is already acquired, reset rhs
432 rhs.m_.capacity = 0u;
433 rhs.m_.buffer = pointer();
434 rhs.m_.front_idx = 0;
436 BOOST_ASSERT( invariants_ok());
437 BOOST_ASSERT(rhs.invariants_ok());
441 * **Effects**: Moves `rhs`'s resources to `*this`, using the specified allocator.
443 * **Throws**: If allocation or T's move constructor throws.
445 * **Postcondition**: `rhs` is left in an unspecified but valid state.
447 * **Exceptions**: Strong exception guarantee if not `noexcept`.
449 * **Complexity**: Linear if allocator != rhs.get_allocator(), otherwise constant.
451 devector(BOOST_RV_REF(devector) rhs, const allocator_type& allocator)
452 : m_(allocator, rhs.m_.buffer, rhs.m_.front_idx, rhs.m_.back_idx, rhs.capacity())
454 // TODO should move elems-by-elems if the two allocators differ
455 // buffer is already acquired, reset rhs
456 rhs.m_.capacity = 0u;
457 rhs.m_.buffer = pointer();
458 rhs.m_.front_idx = 0;
460 BOOST_ASSERT( invariants_ok());
461 BOOST_ASSERT(rhs.invariants_ok());
464 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
466 * **Equivalent to**: `devector(il.begin(), il.end())` or `devector(il.begin(), il.end(), allocator)`.
468 devector(const std::initializer_list<T>& il, const allocator_type& allocator = allocator_type())
471 const size_type n = il.size();
472 m_.buffer = n ? allocate(n) : pointer();
474 //this->allocate(n) will take care of overflows
477 //construct_from_range releases memory on failure
478 this->construct_from_range(il.begin(), il.end());
479 BOOST_ASSERT(invariants_ok());
484 * **Effects**: Destroys the devector. All stored values are destroyed and
485 * used memory, if any, deallocated.
487 * **Complexity**: Linear in the size of `*this`.
489 ~devector() BOOST_NOEXCEPT
491 destroy_elements(m_.buffer + m_.front_idx, m_.buffer + m_.back_idx);
496 * **Effects**: Copies elements of `x` to `*this`. Previously
497 * held elements get copy assigned to or destroyed.
499 * **Requires**: `T` shall be [CopyInsertable] into `*this`.
501 * **Postcondition**: `this->size() == x.size()`, the elements of
502 * `*this` are copies of elements in `x` in the same order.
504 * **Returns**: `*this`.
506 * **Exceptions**: Strong exception guarantee if `T` is `NothrowConstructible`
507 * and the allocator is allowed to be propagated
508 * ([propagate_on_container_copy_assignment] is true),
509 * Basic exception guarantee otherwise.
511 * **Complexity**: Linear in the size of `x` and `*this`.
513 * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
514 * [propagate_on_container_copy_assignment]: http://en.cppreference.com/w/cpp/memory/allocator_traits
517 BOOST_CONTAINER_FORCEINLINE devector& operator=(BOOST_COPY_ASSIGN_REF(devector) rhs)
519 const devector &x = rhs;
520 if (this == &x) { return *this; } // skip self
522 BOOST_IF_CONSTEXPR(allocator_traits_type::propagate_on_container_copy_assignment::value)
524 allocator_type &this_alloc = this->get_allocator_ref();
525 const allocator_type &other_alloc = x.get_allocator_ref();
526 if (this_alloc != other_alloc)
528 // new allocator cannot free existing storage
530 this->deallocate_buffer();
532 m_.buffer = pointer();
535 this_alloc = other_alloc;
538 size_type n = x.size();
541 this->overwrite_buffer(x.begin(), x.end());
545 this->allocate_and_copy_range(x.begin(), x.end());
548 BOOST_ASSERT(invariants_ok());
554 * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
556 * **Effects**: Moves elements of `x` to `*this`. Previously
557 * held elements get move/copy assigned to or destroyed.
559 * **Requires**: `T` shall be [MoveInsertable] into `*this`.
561 * **Postcondition**: `x` is left in an unspecified but valid state.
563 * **Returns**: `*this`.
565 * **Exceptions**: Basic exception guarantee if not `noexcept`.
567 * **Complexity**: Constant if allocator_traits_type::
568 * propagate_on_container_move_assignment is true or
569 * this->get>allocator() == x.get_allocator(). Linear otherwise.
571 devector& operator=(BOOST_RV_REF(devector) x)
572 BOOST_NOEXCEPT_IF(allocator_traits_type::propagate_on_container_move_assignment::value
573 || allocator_traits_type::is_always_equal::value)
575 BOOST_CONSTEXPR_OR_CONST bool copy_alloc = allocator_traits_type::propagate_on_container_move_assignment::value;
577 BOOST_IF_CONSTEXPR (copy_alloc || get_allocator_ref() == x.get_allocator_ref())
580 this->deallocate_buffer();
584 this->get_allocator_ref() = boost::move(x.get_allocator_ref());
587 m_.capacity = x.m_.capacity;
588 m_.buffer = x.m_.buffer;
589 m_.front_idx = x.m_.front_idx;
590 m_.back_idx = x.m_.back_idx;
592 // leave x in valid state
594 x.m_.buffer = pointer();
595 x.m_.back_idx = x.m_.front_idx = 0;
599 // if the allocator shouldn't be copied and they do not compare equal
600 // we can't steal memory.
602 move_iterator<iterator> xbegin = boost::make_move_iterator(x.begin());
603 move_iterator<iterator> xend = boost::make_move_iterator(x.end());
607 get_allocator_ref() = boost::move(x.get_allocator_ref());
610 if (capacity() >= x.size())
612 overwrite_buffer(xbegin, xend);
616 allocate_and_copy_range(xbegin, xend);
620 BOOST_ASSERT(invariants_ok());
625 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
627 * **Effects**: Copies elements of `il` to `*this`. Previously
628 * held elements get copy assigned to or destroyed.
630 * **Requires**: `T` shall be [CopyInsertable] into `*this` and [CopyAssignable].
632 * **Postcondition**: `this->size() == il.size()`, the elements of
633 * `*this` are copies of elements in `il` in the same order.
635 * **Exceptions**: Strong exception guarantee if `T` is nothrow copy assignable
636 * from `T` and `NothrowConstructible`, Basic exception guarantee otherwise.
638 * **Returns**: `*this`.
640 * **Complexity**: Linear in the size of `il` and `*this`.
642 * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
643 * [CopyAssignable]: http://en.cppreference.com/w/cpp/concept/CopyAssignable
645 devector& operator=(std::initializer_list<T> il)
647 assign(il.begin(), il.end());
653 * **Effects**: Replaces elements of `*this` with a copy of `[first,last)`.
654 * Previously held elements get copy assigned to or destroyed.
656 * **Requires**: `T` shall be [EmplaceConstructible] from `*first`. If the specified iterator
657 * does not meet the forward iterator requirements, `T` shall be also [MoveInsertable] into `*this`.
659 * **Precondition**: `first` and `last` are not iterators into `*this`.
661 * **Postcondition**: `size() == N`, where `N` is the distance between `first` and `last`.
663 * **Exceptions**: Strong exception guarantee if `T` is nothrow copy assignable
664 * from `*first` and `NothrowConstructible`, Basic exception guarantee otherwise.
666 * **Complexity**: Linear in the distance between `first` and `last`.
667 * Makes a single reallocation at most if the iterators `first` and `last`
668 * are of forward, bidirectional, or random access categories. It makes
669 * `O(log(N))` reallocations if they are just input iterators.
671 * **Remarks**: Each iterator in the range `[first,last)` shall be dereferenced exactly once,
672 * unless an exception is thrown.
674 * [EmplaceConstructible]: http://en.cppreference.com/w/cpp/concept/EmplaceConstructible
675 * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
677 template <class InputIterator>
678 void assign(InputIterator first, InputIterator last
680 BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_or
682 BOOST_MOVE_I dtl::is_convertible<InputIterator BOOST_MOVE_I size_type>
683 BOOST_MOVE_I dtl::is_not_input_iterator<InputIterator>
687 first = overwrite_buffer_impl(first, last, dtl::false_());
688 while (first != last)
690 this->emplace_back(*first++);
694 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
696 template <class ForwardIterator>
697 void assign(ForwardIterator first, ForwardIterator last
699 BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_or
701 BOOST_MOVE_I dtl::is_convertible<ForwardIterator BOOST_MOVE_I size_type>
702 BOOST_MOVE_I dtl::is_input_iterator<ForwardIterator>
706 const size_type n = boost::container::iterator_udistance(first, last);
710 overwrite_buffer(first, last);
714 allocate_and_copy_range(first, last);
717 BOOST_ASSERT(invariants_ok());
720 #endif // ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
723 * **Effects**: Replaces elements of `*this` with `n` copies of `u`.
724 * Previously held elements get copy assigned to or destroyed.
726 * **Requires**: `T` shall be [CopyInsertable] into `*this` and
729 * **Precondition**: `u` is not a reference into `*this`.
731 * **Postcondition**: `size() == n` and the elements of
732 * `*this` are copies of `u`.
734 * **Exceptions**: Strong exception guarantee if `T` is nothrow copy assignable
735 * from `u` and `NothrowConstructible`, Basic exception guarantee otherwise.
737 * **Complexity**: Linear in `n` and the size of `*this`.
739 * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
740 * [CopyAssignable]: http://en.cppreference.com/w/cpp/concept/CopyAssignable
742 void assign(size_type n, const T& u)
744 cvalue_iterator first(u, n);
745 cvalue_iterator last;
750 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
751 /** **Equivalent to**: `assign(il.begin(), il.end())`. */
752 void assign(std::initializer_list<T> il)
754 assign(il.begin(), il.end());
759 * **Returns**: A copy of the allocator associated with the container.
761 * **Complexity**: Constant.
763 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
764 allocator_type get_allocator() const BOOST_NOEXCEPT
766 return static_cast<const allocator_type&>(m_);
769 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
770 const allocator_type &get_stored_allocator() const BOOST_NOEXCEPT
772 return static_cast<const allocator_type&>(m_);
775 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
776 allocator_type &get_stored_allocator() BOOST_NOEXCEPT
778 return static_cast<allocator_type&>(m_);
784 * **Returns**: A iterator pointing to the first element in the devector,
785 * or the past the end iterator if the devector is empty.
787 * **Complexity**: Constant.
789 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
790 iterator begin() BOOST_NOEXCEPT
792 return m_.buffer + m_.front_idx;
796 * **Returns**: A constant iterator pointing to the first element in the devector,
797 * or the past the end iterator if the devector is empty.
799 * **Complexity**: Constant.
801 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
802 const_iterator begin() const BOOST_NOEXCEPT
804 return m_.buffer + m_.front_idx;
808 * **Returns**: An iterator pointing past the last element of the container.
810 * **Complexity**: Constant.
812 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
813 iterator end() BOOST_NOEXCEPT
815 return m_.buffer + m_.back_idx;
819 * **Returns**: A constant iterator pointing past the last element of the container.
821 * **Complexity**: Constant.
823 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
824 const_iterator end() const BOOST_NOEXCEPT
826 return m_.buffer + m_.back_idx;
830 * **Returns**: A reverse iterator pointing to the first element in the reversed devector,
831 * or the reverse past the end iterator if the devector is empty.
833 * **Complexity**: Constant.
835 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
836 reverse_iterator rbegin() BOOST_NOEXCEPT
838 return reverse_iterator(m_.buffer + m_.back_idx);
842 * **Returns**: A constant reverse iterator
843 * pointing to the first element in the reversed devector,
844 * or the reverse past the end iterator if the devector is empty.
846 * **Complexity**: Constant.
848 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
849 const_reverse_iterator rbegin() const BOOST_NOEXCEPT
851 return const_reverse_iterator(m_.buffer + m_.back_idx);
855 * **Returns**: A reverse iterator pointing past the last element in the
856 * reversed container, or to the beginning of the reversed container if it's empty.
858 * **Complexity**: Constant.
860 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
861 reverse_iterator rend() BOOST_NOEXCEPT
863 return reverse_iterator(m_.buffer + m_.front_idx);
867 * **Returns**: A constant reverse iterator pointing past the last element in the
868 * reversed container, or to the beginning of the reversed container if it's empty.
870 * **Complexity**: Constant.
872 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
873 const_reverse_iterator rend() const BOOST_NOEXCEPT
875 return const_reverse_iterator(m_.buffer + m_.front_idx);
879 * **Returns**: A constant iterator pointing to the first element in the devector,
880 * or the past the end iterator if the devector is empty.
882 * **Complexity**: Constant.
884 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
885 const_iterator cbegin() const BOOST_NOEXCEPT
887 return m_.buffer + m_.front_idx;
891 * **Returns**: A constant iterator pointing past the last element of the container.
893 * **Complexity**: Constant.
895 const_iterator cend() const BOOST_NOEXCEPT
897 return m_.buffer + m_.back_idx;
901 * **Returns**: A constant reverse iterator
902 * pointing to the first element in the reversed devector,
903 * or the reverse past the end iterator if the devector is empty.
905 * **Complexity**: Constant.
907 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
908 const_reverse_iterator crbegin() const BOOST_NOEXCEPT
910 return const_reverse_iterator(m_.buffer + m_.back_idx);
914 * **Returns**: A constant reverse iterator pointing past the last element in the
915 * reversed container, or to the beginning of the reversed container if it's empty.
917 * **Complexity**: Constant.
919 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
920 const_reverse_iterator crend() const BOOST_NOEXCEPT
922 return const_reverse_iterator(m_.buffer + m_.front_idx);
928 * **Returns**: True, if `size() == 0`, false otherwise.
930 * **Complexity**: Constant.
932 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
933 bool empty() const BOOST_NOEXCEPT
935 return m_.front_idx == m_.back_idx;
939 * **Returns**: The number of elements the devector contains.
941 * **Complexity**: Constant.
943 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
944 size_type size() const BOOST_NOEXCEPT
946 return size_type(m_.back_idx - m_.front_idx);
950 * **Returns**: The maximum number of elements the devector could possibly hold.
952 * **Complexity**: Constant.
954 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
955 size_type max_size() const BOOST_NOEXCEPT
957 size_type alloc_max = allocator_traits_type::max_size(get_allocator_ref());
958 size_type size_type_max = (size_type)-1;
959 return (alloc_max <= size_type_max) ? size_type(alloc_max) : size_type_max;
963 * **Returns**: The total number of elements that the devector can hold without requiring reallocation.
965 * **Complexity**: Constant.
967 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
968 size_type capacity() const BOOST_NOEXCEPT
974 * **Returns**: The total number of elements that can be pushed to the front of the
975 * devector without requiring reallocation.
977 * **Complexity**: Constant.
979 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
980 size_type front_free_capacity() const BOOST_NOEXCEPT
986 * **Returns**: The total number of elements that can be pushed to the back of the
987 * devector without requiring reallocation.
989 * **Complexity**: Constant.
991 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
992 size_type back_free_capacity() const BOOST_NOEXCEPT
994 return size_type(m_.capacity - m_.back_idx);
997 /** **Equivalent to**: `resize_back(sz)` */
998 void resize(size_type sz) { resize_back(sz); }
1000 /** **Equivalent to**: `resize_back(sz, c)` */
1001 void resize(size_type sz, const T& c) { resize_back(sz, c); }
1004 * **Effects**: If `sz` is greater than the size of `*this`,
1005 * additional value-initialized elements are inserted
1006 * to the front. Invalidates iterators if reallocation is needed.
1007 * If `sz` is smaller than than the size of `*this`,
1008 * elements are popped from the front.
1010 * **Requires**: T shall be [MoveInsertable] into *this and [DefaultConstructible].
1012 * **Postcondition**: `sz == size()`.
1014 * **Exceptions**: Strong exception guarantee.
1016 * **Complexity**: Linear in the size of `*this` and `sz`.
1018 * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
1019 * [DefaultConstructible]: http://en.cppreference.com/w/cpp/concept/DefaultConstructible
1021 void resize_front(size_type sz)
1023 resize_front_impl(sz);
1024 BOOST_ASSERT(invariants_ok());
1028 * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
1030 * **Effects**: If `sz` is greater than the size of `*this`,
1031 * copies of `c` are inserted to the front.
1032 * Invalidates iterators if reallocation is needed.
1033 * If `sz` is smaller than than the size of `*this`,
1034 * elements are popped from the front.
1036 * **Postcondition**: `sz == size()`.
1038 * **Requires**: `T` shall be [CopyInsertable] into `*this`.
1040 * **Exceptions**: Strong exception guarantee.
1042 * **Complexity**: Linear in the size of `*this` and `sz`.
1044 void resize_front(size_type sz, const T& c)
1046 resize_front_impl(sz, c);
1047 BOOST_ASSERT(invariants_ok());
1051 * **Effects**: If `sz` is greater than the size of `*this`,
1052 * additional value-initialized elements are inserted
1053 * to the back. Invalidates iterators if reallocation is needed.
1054 * If `sz` is smaller than than the size of `*this`,
1055 * elements are popped from the back.
1057 * **Requires**: T shall be [MoveInsertable] into *this and [DefaultConstructible].
1059 * **Postcondition**: `sz == size()`.
1061 * **Exceptions**: Strong exception guarantee.
1063 * **Complexity**: Linear in the size of `*this` and `sz`.
1065 * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
1066 * [DefaultConstructible]: http://en.cppreference.com/w/cpp/concept/DefaultConstructible
1068 void resize_back(size_type sz)
1070 resize_back_impl(sz);
1071 BOOST_ASSERT(invariants_ok());
1075 * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
1077 * **Effects**: If `sz` is greater than the size of `*this`,
1078 * copies of `c` are inserted to the back.
1079 * If `sz` is smaller than than the size of `*this`,
1080 * elements are popped from the back.
1082 * **Postcondition**: `sz == size()`.
1084 * **Requires**: `T` shall be [CopyInsertable] into `*this`.
1086 * **Exceptions**: Strong exception guarantee.
1088 * **Complexity**: Linear in the size of `*this` and `sz`.
1090 void resize_back(size_type sz, const T& c)
1092 resize_back_impl(sz, c);
1093 BOOST_ASSERT(invariants_ok());
1096 // unsafe uninitialized resize methods
1099 * **Unsafe method**, use with care.
1101 * **Effects**: Changes the size of the devector without properly
1102 * initializing the extra or destroying the superfluous elements.
1103 * If `n < size()`, elements are removed from the front without
1104 * getting destroyed; if `n > size()`, uninitialized elements are added
1105 * before the first element at the front.
1106 * Invalidates iterators if reallocation is needed.
1108 * **Postcondition**: `size() == n`.
1110 * **Exceptions**: Strong exception guarantee.
1112 * **Complexity**: Linear in `size()` if `capacity() < n`, constant otherwise.
1114 * **Remarks**: The devector does not keep track of initialization of the elements:
1115 * Elements without a trivial destructor must be manually destroyed before shrinking,
1116 * elements without a trivial constructor must be initialized after growing.
1119 void unsafe_uninitialized_resize_front(size_type n)
1123 unsafe_uninitialized_grow_front(n);
1127 unsafe_uninitialized_shrink_front(n);
1132 * **Unsafe method**, use with care.
1134 * **Effects**: Changes the size of the devector without properly
1135 * initializing the extra or destroying the superfluous elements.
1136 * If `n < size()`, elements are removed from the back without
1137 * getting destroyed; if `n > size()`, uninitialized elements are added
1138 * after the last element at the back.
1139 * Invalidates iterators if reallocation is needed.
1141 * **Postcondition**: `size() == n`.
1143 * **Exceptions**: Strong exception guarantee.
1145 * **Complexity**: Linear in `size()` if `capacity() < n`, constant otherwise.
1147 * **Remarks**: The devector does not keep track of initialization of the elements:
1148 * Elements without a trivial destructor must be manually destroyed before shrinking,
1149 * elements without a trivial constructor must be initialized after growing.
1152 void unsafe_uninitialized_resize_back(size_type n)
1156 unsafe_uninitialized_grow_back(n);
1160 unsafe_uninitialized_shrink_back(n);
1165 // after reserve_[front,back](n), n - size() push_[front,back] will not allocate
1167 /** **Equivalent to**: `reserve_back(new_capacity)` */
1168 void reserve(size_type new_capacity) { reserve_back(new_capacity); }
1171 * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
1173 * **Effects**: Ensures that `n` elements can be pushed to the front
1174 * without requiring reallocation, where `n` is `new_capacity - size()`,
1175 * if `n` is positive. Otherwise, there are no effects.
1176 * Invalidates iterators if reallocation is needed.
1178 * **Requires**: `T` shall be [MoveInsertable] into `*this`.
1180 * **Complexity**: Linear in the size of *this.
1182 * **Exceptions**: Strong exception guarantee.
1184 * **Throws**: `length_error` if `new_capacity > max_size()`.
1186 void reserve_front(size_type new_capacity)
1188 if (front_capacity() >= new_capacity) { return; }
1190 reallocate_at(new_capacity + back_free_capacity(), new_capacity - size());
1192 BOOST_ASSERT(invariants_ok());
1196 * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
1198 * **Effects**: Ensures that `n` elements can be pushed to the back
1199 * without requiring reallocation, where `n` is `new_capacity - size()`,
1200 * if `n` is positive. Otherwise, there are no effects.
1201 * Invalidates iterators if reallocation is needed.
1203 * **Requires**: `T` shall be [MoveInsertable] into `*this`.
1205 * **Complexity**: Linear in the size of *this.
1207 * **Exceptions**: Strong exception guarantee.
1209 * **Throws**: length_error if `new_capacity > max_size()`.
1211 void reserve_back(size_type new_capacity)
1213 if (back_capacity() >= new_capacity) { return; }
1215 reallocate_at(new_capacity + front_free_capacity(), m_.front_idx);
1217 BOOST_ASSERT(invariants_ok());
1222 * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
1224 * **Effects**: Reduces `capacity()` to `size()`. Invalidates iterators.
1226 * **Requires**: `T` shall be [MoveInsertable] into `*this`.
1228 * **Exceptions**: Strong exception guarantee.
1230 * **Complexity**: Linear in the size of *this.
1232 void shrink_to_fit()
1234 if(this->front_capacity() || this->back_capacity())
1235 this->reallocate_at(size(), 0);
1241 * **Returns**: A reference to the `n`th element in the devector.
1243 * **Precondition**: `n < size()`.
1245 * **Complexity**: Constant.
1247 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
1248 reference operator[](size_type n) BOOST_NOEXCEPT
1250 BOOST_ASSERT(n < size());
1251 return *(begin() + n);
1255 * **Returns**: A constant reference to the `n`th element in the devector.
1257 * **Precondition**: `n < size()`.
1259 * **Complexity**: Constant.
1261 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
1262 const_reference operator[](size_type n) const BOOST_NOEXCEPT
1264 BOOST_ASSERT(n < size());
1266 return *(begin() + n);
1270 * **Returns**: A reference to the `n`th element in the devector.
1272 * **Throws**: `out_of_range`, if `n >= size()`.
1274 * **Complexity**: Constant.
1276 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
1277 reference at(size_type n)
1280 throw_out_of_range("devector::at out of range");
1285 * **Returns**: A constant reference to the `n`th element in the devector.
1287 * **Throws**: `out_of_range`, if `n >= size()`.
1289 * **Complexity**: Constant.
1291 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
1292 const_reference at(size_type n) const
1295 throw_out_of_range("devector::at out of range");
1300 * **Returns**: A reference to the first element in the devector.
1302 * **Precondition**: `!empty()`.
1304 * **Complexity**: Constant.
1306 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
1307 reference front() BOOST_NOEXCEPT
1309 BOOST_ASSERT(!empty());
1311 return *(m_.buffer + m_.front_idx);
1315 * **Returns**: A constant reference to the first element in the devector.
1317 * **Precondition**: `!empty()`.
1319 * **Complexity**: Constant.
1321 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
1322 const_reference front() const BOOST_NOEXCEPT
1324 BOOST_ASSERT(!empty());
1326 return *(m_.buffer + m_.front_idx);
1330 * **Returns**: A reference to the last element in the devector.
1332 * **Precondition**: `!empty()`.
1334 * **Complexity**: Constant.
1336 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
1337 reference back() BOOST_NOEXCEPT
1339 BOOST_ASSERT(!empty());
1341 return *(m_.buffer + m_.back_idx -1);
1345 * **Returns**: A constant reference to the last element in the devector.
1347 * **Precondition**: `!empty()`.
1349 * **Complexity**: Constant.
1351 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
1352 const_reference back() const BOOST_NOEXCEPT
1354 BOOST_ASSERT(!empty());
1356 return *(m_.buffer + m_.back_idx -1);
1360 * **Returns**: A pointer to the underlying array serving as element storage.
1361 * The range `[data(); data() + size())` is always valid. For a non-empty devector,
1362 * `data() == &front()`.
1364 * **Complexity**: Constant.
1366 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
1367 T* data() BOOST_NOEXCEPT
1369 return boost::movelib::to_raw_pointer(m_.buffer) + m_.front_idx;
1373 * **Returns**: A constant pointer to the underlying array serving as element storage.
1374 * The range `[data(); data() + size())` is always valid. For a non-empty devector,
1375 * `data() == &front()`.
1377 * **Complexity**: Constant.
1379 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
1380 const T* data() const BOOST_NOEXCEPT
1382 return boost::movelib::to_raw_pointer(m_.buffer) + m_.front_idx;
1388 * **Effects**: Pushes a new element to the front of the devector.
1389 * The element is constructed in-place, using the perfect forwarded `args`
1390 * as constructor arguments. Invalidates iterators if reallocation is needed.
1391 * (`front_free_capacity() == 0`)
1393 * **Requires**: `T` shall be [EmplaceConstructible] from `args` and [MoveInsertable] into `*this`.
1395 * **Exceptions**: Strong exception guarantee.
1397 * **Complexity**: Amortized constant in the size of `*this`.
1398 * (Constant, if `front_free_capacity() > 0`)
1400 * [EmplaceConstructible]: http://en.cppreference.com/w/cpp/concept/EmplaceConstructible
1401 * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
1403 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1404 template <class... Args>
1405 void emplace_front(Args&&... args)
1407 if (front_free_capacity()) // fast path
1409 this->alloc_construct(m_.buffer + m_.front_idx - 1, boost::forward<Args>(args)...);
1414 this->emplace_reallocating_slow_path(true, 0, boost::forward<Args>(args)...);
1417 BOOST_ASSERT(invariants_ok());
1420 #else //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1422 #define BOOST_CONTAINER_DEVECTOR_EMPLACE_FRONT(N) \
1423 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1424 BOOST_CONTAINER_FORCEINLINE void emplace_front(BOOST_MOVE_UREF##N)\
1426 if (front_free_capacity())\
1428 this->alloc_construct(m_.buffer + m_.front_idx - 1 BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
1433 this->emplace_reallocating_slow_path(true, 0 BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
1436 BOOST_ASSERT(invariants_ok());\
1439 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_DEVECTOR_EMPLACE_FRONT)
1440 #undef BOOST_CONTAINER_DEVECTOR_EMPLACE_FRONT
1444 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1446 * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
1448 * **Effects**: Pushes the copy of `x` to the front of the devector.
1449 * Invalidates iterators if reallocation is needed.
1450 * (`front_free_capacity() == 0`)
1452 * **Requires**: `T` shall be [CopyInsertable] into `*this`.
1454 * **Exceptions**: Strong exception guarantee.
1456 * **Complexity**: Amortized constant in the size of `*this`.
1457 * (Constant, if `front_free_capacity() > 0`)
1459 void push_front(const T& x);
1462 * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
1464 * **Effects**: Move constructs a new element at the front of the devector using `x`.
1465 * Invalidates iterators if reallocation is needed.
1466 * (`front_free_capacity() == 0`)
1468 * **Requires**: `T` shall be [MoveInsertable] into `*this`.
1470 * **Exceptions**: Strong exception guarantee, not regarding the state of `x`.
1472 * **Complexity**: Amortized constant in the size of `*this`.
1473 * (Constant, if `front_free_capacity() > 0`)
1475 void push_front(T&& x);
1478 BOOST_MOVE_CONVERSION_AWARE_CATCH(push_front, T, void, priv_push_front)
1482 * **Effects**: Removes the first element of `*this`.
1484 * **Precondition**: `!empty()`.
1486 * **Postcondition**: `front_free_capacity()` is incremented by 1.
1488 * **Complexity**: Constant.
1490 void pop_front() BOOST_NOEXCEPT
1492 BOOST_ASSERT(! empty());
1493 allocator_traits_type::destroy(get_allocator_ref(), m_.buffer + m_.front_idx);
1495 BOOST_ASSERT(invariants_ok());
1499 * **Effects**: Pushes a new element to the back of the devector.
1500 * The element is constructed in-place, using the perfect forwarded `args`
1501 * as constructor arguments. Invalidates iterators if reallocation is needed.
1502 * (`back_free_capacity() == 0`)
1504 * **Requires**: `T` shall be [EmplaceConstructible] from `args` and [MoveInsertable] into `*this`,
1505 * and [MoveAssignable].
1507 * **Exceptions**: Strong exception guarantee.
1509 * **Complexity**: Amortized constant in the size of `*this`.
1510 * (Constant, if `back_free_capacity() > 0`)
1512 * [EmplaceConstructible]: http://en.cppreference.com/w/cpp/concept/EmplaceConstructible
1513 * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
1514 * [MoveAssignable]: http://en.cppreference.com/w/cpp/concept/MoveAssignable
1516 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1517 template <class... Args>
1518 BOOST_CONTAINER_FORCEINLINE void emplace_back(Args&&... args)
1520 if (this->back_free_capacity()){
1521 this->alloc_construct(m_.buffer + m_.back_idx, boost::forward<Args>(args)...);
1525 this->emplace_reallocating_slow_path(false, size(), boost::forward<Args>(args)...);
1527 BOOST_ASSERT(invariants_ok());
1530 #else //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1532 #define BOOST_CONTAINER_DEVECTOR_EMPLACE_BACK(N) \
1533 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1534 BOOST_CONTAINER_FORCEINLINE void emplace_back(BOOST_MOVE_UREF##N)\
1536 if (this->back_free_capacity()){\
1537 this->alloc_construct(m_.buffer + m_.back_idx BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
1541 this->emplace_reallocating_slow_path(false, size() BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
1543 BOOST_ASSERT(invariants_ok());\
1546 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_DEVECTOR_EMPLACE_BACK)
1547 #undef BOOST_CONTAINER_DEVECTOR_EMPLACE_BACK
1549 #endif //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1552 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1554 * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
1556 * **Effects**: Pushes the copy of `x` to the back of the devector.
1557 * Invalidates iterators if reallocation is needed.
1558 * (`back_free_capacity() == 0`)
1560 * **Requires**: `T` shall be [CopyInsertable] into `*this`.
1562 * **Exceptions**: Strong exception guarantee.
1564 * **Complexity**: Amortized constant in the size of `*this`.
1565 * (Constant, if `back_free_capacity() > 0`)
1567 void push_back(const T& x);
1570 * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
1572 * **Effects**: Move constructs a new element at the back of the devector using `x`.
1573 * Invalidates iterators if reallocation is needed.
1574 * (`back_free_capacity() == 0`)
1576 * **Requires**: `T` shall be [MoveInsertable] into `*this`.
1578 * **Exceptions**: Strong exception guarantee, not regarding the state of `x`.
1580 * **Complexity**: Amortized constant in the size of `*this`.
1581 * (Constant, if `back_free_capacity() > 0`)
1583 void push_back(T&& x);
1586 BOOST_MOVE_CONVERSION_AWARE_CATCH(push_back, T, void, priv_push_back)
1590 * **Effects**: Removes the last element of `*this`.
1592 * **Precondition**: `!empty()`.
1594 * **Postcondition**: `back_free_capacity()` is incremented by 1.
1596 * **Complexity**: Constant.
1598 void pop_back() BOOST_NOEXCEPT
1600 BOOST_ASSERT(! empty());
1602 allocator_traits_type::destroy(get_allocator_ref(), m_.buffer + m_.back_idx);
1603 BOOST_ASSERT(invariants_ok());
1607 * **Effects**: Constructs a new element before the element pointed by `position`.
1608 * The element is constructed in-place, using the perfect forwarded `args`
1609 * as constructor arguments. Invalidates iterators if reallocation is needed.
1611 * **Requires**: `T` shall be [EmplaceConstructible], and [MoveInsertable] into `*this`,
1612 * and [MoveAssignable].
1614 * **Returns**: Iterator pointing to the newly constructed element.
1616 * **Exceptions**: Strong exception guarantee if `T` is `NothrowConstructible`
1617 * and `NothrowAssignable`, Basic exception guarantee otherwise.
1619 * **Complexity**: Linear in the size of `*this`.
1621 * [EmplaceConstructible]: http://en.cppreference.com/w/cpp/concept/EmplaceConstructible
1622 * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
1623 * [MoveAssignable]: http://en.cppreference.com/w/cpp/concept/MoveAssignable
1625 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1626 template <class... Args>
1627 iterator emplace(const_iterator position, Args&&... args)
1629 BOOST_ASSERT(position >= begin());
1630 BOOST_ASSERT(position <= end());
1632 if (position == end() && back_free_capacity()) // fast path
1634 this->alloc_construct(m_.buffer + m_.back_idx, boost::forward<Args>(args)...);
1638 else if (position == begin() && front_free_capacity()) // secondary fast path
1640 this->alloc_construct(m_.buffer + (m_.front_idx - 1), boost::forward<Args>(args)...);
1646 size_type new_elem_index = size_type(position - begin());
1647 return this->emplace_slow_path(new_elem_index, boost::forward<Args>(args)...);
1651 #else //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1653 #define BOOST_CONTAINER_DEVECTOR_EMPLACE(N) \
1654 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1655 iterator emplace(const_iterator position BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
1657 BOOST_ASSERT(position >= begin());\
1658 BOOST_ASSERT(position <= end());\
1660 if (position == end() && back_free_capacity()){\
1661 this->alloc_construct(m_.buffer + m_.back_idx BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
1665 else if (position == begin() && front_free_capacity()){\
1666 this->alloc_construct(m_.buffer + m_.front_idx - 1 BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
1671 size_type new_elem_index = size_type(position - begin());\
1672 return this->emplace_slow_path(new_elem_index BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
1676 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_DEVECTOR_EMPLACE)
1677 #undef BOOST_CONTAINER_DEVECTOR_EMPLACE
1679 #endif //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1682 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1684 * **Effects**: Copy constructs a new element before the element pointed by `position`,
1685 * using `x` as constructor argument. Invalidates iterators if reallocation is needed.
1687 * **Requires**: `T` shall be [CopyInsertable] into `*this` and and [CopyAssignable].
1689 * **Returns**: Iterator pointing to the newly constructed element.
1691 * **Exceptions**: Strong exception guarantee if `T` is `NothrowConstructible`
1692 * and `NothrowAssignable`, Basic exception guarantee otherwise.
1694 * **Complexity**: Linear in the size of `*this`.
1696 * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
1697 * [CopyAssignable]: http://en.cppreference.com/w/cpp/concept/CopyAssignable
1699 iterator insert(const_iterator position, const T &x);
1702 * **Effects**: Move constructs a new element before the element pointed by `position`,
1703 * using `x` as constructor argument. Invalidates iterators if reallocation is needed.
1705 * **Requires**: `T` shall be [MoveInsertable] into `*this` and and [CopyAssignable].
1707 * **Returns**: Iterator pointing to the newly constructed element.
1709 * **Exceptions**: Strong exception guarantee if `T` is `NothrowConstructible`
1710 * and `NothrowAssignable` (not regarding the state of `x`),
1711 * Basic exception guarantee otherwise.
1713 * **Complexity**: Linear in the size of `*this`.
1715 * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
1716 * [CopyAssignable]: http://en.cppreference.com/w/cpp/concept/CopyAssignable
1718 iterator insert(const_iterator position, T &&x);
1720 BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, T, iterator, priv_insert, const_iterator, const_iterator)
1724 * **Effects**: Copy constructs `n` elements before the element pointed by `position`,
1725 * using `x` as constructor argument. Invalidates iterators if reallocation is needed.
1727 * **Requires**: `T` shall be [CopyInsertable] into `*this` and and [CopyAssignable].
1729 * **Returns**: Iterator pointing to the first inserted element, or `position`, if `n` is zero.
1731 * **Exceptions**: Strong exception guarantee if `T` is `NothrowConstructible`
1732 * and `NothrowAssignable`, Basic exception guarantee otherwise.
1734 * **Complexity**: Linear in the size of `*this` and `n`.
1736 * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
1737 * [CopyAssignable]: http://en.cppreference.com/w/cpp/concept/CopyAssignable
1739 iterator insert(const_iterator position, size_type n, const T& x)
1741 cvalue_iterator first(x, n);
1742 cvalue_iterator last = first + n;
1743 return insert_range(position, first, last);
1747 * **Effects**: Copy constructs elements before the element pointed by position
1748 * using each element in the rage pointed by `first` and `last` as constructor arguments.
1749 * Invalidates iterators if reallocation is needed.
1751 * **Requires**: `T` shall be [EmplaceConstructible] into `*this` from `*first`. If the specified iterator
1752 * does not meet the forward iterator requirements, `T` shall also be [MoveInsertable] into `*this`
1753 * and [MoveAssignable].
1755 * **Precondition**: `first` and `last` are not iterators into `*this`.
1757 * **Returns**: Iterator pointing to the first inserted element, or `position`, if `first == last`.
1759 * **Complexity**: Linear in the size of `*this` and `N` (where `N` is the distance between `first` and `last`).
1760 * Makes only `N` calls to the constructor of `T` and no reallocations if iterators `first` and `last`
1761 * are of forward, bidirectional, or random access categories. It makes 2N calls to the copy constructor of `T`
1762 * and allocates memory twice at most if they are just input iterators.
1764 * **Exceptions**: Strong exception guarantee if `T` is `NothrowConstructible`
1765 * and `NothrowAssignable`, Basic exception guarantee otherwise.
1767 * **Remarks**: Each iterator in the range `[first,last)` shall be dereferenced exactly once,
1768 * unless an exception is thrown.
1770 * [EmplaceConstructible]: http://en.cppreference.com/w/cpp/concept/EmplaceConstructible
1771 * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
1772 * [MoveAssignable]: http://en.cppreference.com/w/cpp/concept/MoveAssignable
1774 template <class InputIterator>
1775 iterator insert(const_iterator position, InputIterator first, InputIterator last
1777 BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_or
1779 BOOST_MOVE_I dtl::is_convertible<InputIterator BOOST_MOVE_I size_type>
1780 BOOST_MOVE_I dtl::is_not_input_iterator<InputIterator>
1784 if (position == end())
1786 size_type insert_index = size();
1788 for (; first != last; ++first)
1790 this->emplace_back(*first);
1793 return begin() + insert_index;
1797 const size_type insert_index = static_cast<size_type>(position - this->cbegin());
1798 const size_type old_size = static_cast<size_type>(this->size());
1800 for (; first != last; ++first) {
1801 this->emplace_back(*first);
1803 iterator rit (this->begin() + insert_index);
1804 boost::movelib::rotate_gcd(rit, this->begin() + old_size, this->begin() + this->size());
1809 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1811 template <class ForwardIterator>
1812 iterator insert(const_iterator position, ForwardIterator first, ForwardIterator last
1814 BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_or
1816 BOOST_MOVE_I dtl::is_convertible<ForwardIterator BOOST_MOVE_I size_type>
1817 BOOST_MOVE_I dtl::is_input_iterator<ForwardIterator>
1821 return insert_range(position, first, last);
1824 #endif // ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1826 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1827 /** **Equivalent to**: `insert(position, il.begin(), il.end())` */
1828 iterator insert(const_iterator position, std::initializer_list<T> il)
1830 return insert_range(position, il.begin(), il.end());
1835 * [MoveAssignable]: http://en.cppreference.com/w/cpp/concept/MoveAssignable
1837 * **Effects**: Destroys the element pointed by `position` and removes it from the devector.
1838 * Invalidates iterators.
1840 * **Requires**: `T` shall be [MoveAssignable].
1842 * **Precondition**: `position` must be in the range of `[begin(), end())`.
1844 * **Returns**: Iterator pointing to the element immediately following the erased element
1845 * prior to its erasure. If no such element exists, `end()` is returned.
1847 * **Exceptions**: Strong exception guarantee if `T` is `NothrowAssignable`,
1848 * Basic exception guarantee otherwise.
1850 * **Complexity**: Linear in half the size of `*this`.
1852 iterator erase(const_iterator position)
1854 return erase(position, position + 1);
1858 * [MoveAssignable]: http://en.cppreference.com/w/cpp/concept/MoveAssignable
1860 * **Effects**: Destroys the range `[first,last)` and removes it from the devector.
1861 * Invalidates iterators.
1863 * **Requires**: `T` shall be [MoveAssignable].
1865 * **Precondition**: `[first,last)` must be in the range of `[begin(), end())`.
1867 * **Returns**: Iterator pointing to the element pointed to by `last` prior to any elements
1868 * being erased. If no such element exists, `end()` is returned.
1870 * **Exceptions**: Strong exception guarantee if `T` is `NothrowAssignable`,
1871 * Basic exception guarantee otherwise.
1873 * **Complexity**: Linear in half the size of `*this`
1874 * plus the distance between `first` and `last`.
1876 iterator erase(const_iterator first, const_iterator last)
1878 iterator nc_first = begin() + (first - begin());
1879 iterator nc_last = begin() + (last - begin());
1880 return erase(nc_first, nc_last);
1884 * [MoveAssignable]: http://en.cppreference.com/w/cpp/concept/MoveAssignable
1886 * **Effects**: Destroys the range `[first,last)` and removes it from the devector.
1887 * Invalidates iterators.
1889 * **Requires**: `T` shall be [MoveAssignable].
1891 * **Precondition**: `[first,last)` must be in the range of `[begin(), end())`.
1893 * **Returns**: Iterator pointing to the element pointed to by `last` prior to any elements
1894 * being erased. If no such element exists, `end()` is returned.
1896 * **Exceptions**: Strong exception guarantee if `T` is `NothrowAssignable`,
1897 * Basic exception guarantee otherwise.
1899 * **Complexity**: Linear in half the size of `*this`.
1901 iterator erase(iterator first, iterator last)
1903 size_type front_distance = size_type(last - begin());
1904 size_type back_distance = size_type(end() - first);
1905 size_type n = boost::container::iterator_udistance(first, last);
1907 if (front_distance < back_distance)
1909 // move n to the right
1910 boost::container::move_backward(begin(), first, last);
1912 for (iterator i = begin(); i != begin() + n; ++i)
1914 allocator_traits_type::destroy(get_allocator_ref(), i);
1916 //n is always less than max stored_size_type
1917 m_.set_front_idx(m_.front_idx + n);
1919 BOOST_ASSERT(invariants_ok());
1923 // move n to the left
1924 boost::container::move(last, end(), first);
1926 for (iterator i = end() - n; i != end(); ++i)
1928 allocator_traits_type::destroy(get_allocator_ref(), i);
1930 //n is always less than max stored_size_type
1931 m_.set_back_idx(m_.back_idx - n);
1933 BOOST_ASSERT(invariants_ok());
1939 * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
1941 * **Effects**: exchanges the contents of `*this` and `b`.
1943 * **Requires**: instances of `T` must be swappable by unqualified call of `swap`
1944 * and `T` must be [MoveInsertable] into `*this`.
1946 * **Precondition**: The allocators should allow propagation or should compare equal.
1948 * **Exceptions**: Basic exceptions guarantee if not `noexcept`.
1950 * **Complexity**: Constant.
1952 void swap(devector& b)
1953 BOOST_NOEXCEPT_IF( allocator_traits_type::propagate_on_container_swap::value
1954 || allocator_traits_type::is_always_equal::value)
1956 BOOST_CONSTEXPR_OR_CONST bool propagate_alloc = allocator_traits_type::propagate_on_container_swap::value;
1957 BOOST_ASSERT(propagate_alloc || get_allocator_ref() == b.get_allocator_ref()); // else it's undefined behavior
1959 swap_big_big(*this, b);
1962 boost::adl_move_swap(m_.front_idx, b.m_.front_idx);
1963 boost::adl_move_swap(m_.back_idx, b.m_.back_idx);
1965 //And now swap the allocator
1966 dtl::swap_alloc(this->get_allocator_ref(), b.get_allocator_ref(), dtl::bool_<propagate_alloc>());
1968 BOOST_ASSERT( invariants_ok());
1969 BOOST_ASSERT(b.invariants_ok());
1973 * **Effects**: Destroys all elements in the devector.
1974 * Invalidates all references, pointers and iterators to the
1975 * elements of the devector.
1977 * **Postcondition**: `empty() && front_free_capacity() == 0
1978 * && back_free_capacity() == old capacity`.
1980 * **Complexity**: Linear in the size of `*this`.
1982 * **Remarks**: Does not free memory.
1984 void clear() BOOST_NOEXCEPT
1986 destroy_elements(begin(), end());
1987 m_.front_idx = m_.back_idx = 0;
1990 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
1991 friend bool operator==(const devector& x, const devector& y)
1992 { return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin()); }
1994 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
1995 friend bool operator!=(const devector& x, const devector& y)
1996 { return !(x == y); }
1998 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
1999 friend bool operator< (const devector& x, const devector& y)
2000 { return boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); }
2002 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
2003 friend bool operator>(const devector& x, const devector& y)
2006 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
2007 friend bool operator<=(const devector& x, const devector& y)
2008 { return !(y < x); }
2010 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
2011 friend bool operator>=(const devector& x, const devector& y)
2012 { return !(x < y); }
2014 BOOST_CONTAINER_FORCEINLINE friend void swap(devector& x, devector& y)
2015 BOOST_NOEXCEPT_IF( allocator_traits_type::propagate_on_container_swap::value
2016 || allocator_traits_type::is_always_equal::value)
2020 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
2022 BOOST_CONTAINER_FORCEINLINE T* raw_begin() BOOST_NOEXCEPT
2023 { return boost::movelib::to_raw_pointer(m_.buffer) + m_.front_idx; }
2025 BOOST_CONTAINER_FORCEINLINE T* raw_end() BOOST_NOEXCEPT
2026 { return boost::movelib::to_raw_pointer(m_.buffer) + m_.back_idx; }
2030 BOOST_CONTAINER_FORCEINLINE void priv_push_front(BOOST_FWD_REF(U) u)
2032 this->emplace_front(boost::forward<U>(u));
2036 BOOST_CONTAINER_FORCEINLINE void priv_push_back(BOOST_FWD_REF(U) u)
2038 this->emplace_back(boost::forward<U>(u));
2042 BOOST_CONTAINER_FORCEINLINE iterator priv_insert(const_iterator pos, BOOST_FWD_REF(U) u)
2044 return this->emplace(pos, boost::forward<U>(u));
2047 // allocator_type wrappers
2049 BOOST_CONTAINER_FORCEINLINE allocator_type& get_allocator_ref() BOOST_NOEXCEPT
2051 return static_cast<allocator_type&>(m_);
2054 BOOST_CONTAINER_FORCEINLINE const allocator_type& get_allocator_ref() const BOOST_NOEXCEPT
2056 return static_cast<const allocator_type&>(m_);
2059 pointer allocate(size_type capacity)
2061 pointer const p = impl::do_allocate(get_allocator_ref(), capacity);
2062 #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
2063 ++m_.capacity_alloc_count;
2064 #endif // BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
2068 void destroy_elements(pointer begin, pointer end)
2070 for (; begin != end; ++begin)
2072 allocator_traits_type::destroy(get_allocator_ref(), begin);
2076 void deallocate_buffer()
2080 allocator_traits_type::deallocate(get_allocator_ref(), m_.buffer, m_.capacity);
2084 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
2085 template <typename... Args>
2086 BOOST_CONTAINER_FORCEINLINE void alloc_construct(pointer dst, Args&&... args)
2088 allocator_traits_type::construct(
2089 get_allocator_ref(),
2091 boost::forward<Args>(args)...
2095 template <typename... Args>
2096 void construct_n(pointer buffer, size_type n, Args&&... args)
2098 detail::construction_guard<allocator_type> ctr_guard(buffer, get_allocator_ref());
2099 guarded_construct_n(buffer, n, ctr_guard, boost::forward<Args>(args)...);
2100 ctr_guard.release();
2103 template <typename... Args>
2104 void guarded_construct_n(pointer buffer, size_type n, detail::construction_guard<allocator_type>& ctr_guard, Args&&... args)
2106 for (size_type i = 0; i < n; ++i) {
2107 this->alloc_construct(buffer + i, boost::forward<Args>(args)...);
2112 #else //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
2114 #define BOOST_CONTAINER_DEVECTOR_ALLOC_CONSTRUCT(N) \
2115 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
2116 BOOST_CONTAINER_FORCEINLINE void alloc_construct(pointer dst BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
2118 allocator_traits_type::construct(\
2119 get_allocator_ref(), dst BOOST_MOVE_I##N BOOST_MOVE_FWD##N );\
2122 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
2123 void construct_n(pointer buffer, size_type n BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
2125 detail::construction_guard<allocator_type> ctr_guard(buffer, get_allocator_ref());\
2126 guarded_construct_n(buffer, n, ctr_guard BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
2127 ctr_guard.release();\
2130 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
2131 void guarded_construct_n(pointer buffer, size_type n, detail::construction_guard<allocator_type>& ctr_guard BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
2133 for (size_type i = 0; i < n; ++i) {\
2134 this->alloc_construct(buffer + i BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
2135 ctr_guard.extend();\
2139 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_DEVECTOR_ALLOC_CONSTRUCT)
2140 #undef BOOST_CONTAINER_DEVECTOR_ALLOC_CONSTRUCT
2142 #endif //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
2144 BOOST_CONTAINER_FORCEINLINE size_type front_capacity() const
2149 BOOST_CONTAINER_FORCEINLINE size_type back_capacity() const
2151 return size_type(m_.capacity - m_.front_idx);
2154 size_type calculate_new_capacity(size_type requested_capacity)
2156 size_type max = allocator_traits_type::max_size(this->get_allocator_ref());
2157 (clamp_by_stored_size_type)(max, stored_size_type());
2158 const size_type remaining_additional_cap = max - size_type(m_.capacity);
2159 const size_type min_additional_cap = requested_capacity - size_type(m_.capacity);
2160 if ( remaining_additional_cap < min_additional_cap )
2161 boost::container::throw_length_error("devector: get_next_capacity, max size exceeded");
2163 return growth_factor_type()( size_type(m_.capacity), min_additional_cap, max);
2166 void buffer_move_or_copy(pointer dst)
2168 detail::construction_guard<allocator_type> guard(dst, get_allocator_ref());
2170 buffer_move_or_copy(dst, guard);
2175 void buffer_move_or_copy(pointer dst, detail::construction_guard<allocator_type>& guard)
2177 opt_move_or_copy(begin(), end(), dst, guard);
2179 destroy_elements(data(), data() + size());
2180 deallocate_buffer();
2183 void opt_move_or_copy(pointer begin, pointer end, pointer dst)
2185 typedef typename dtl::if_c
2186 < boost::move_detail::is_nothrow_copy_constructible<T>::value || boost::is_nothrow_move_constructible<T>::value
2187 , detail::null_construction_guard
2188 , detail::construction_guard<allocator_type>
2191 guard_t guard(dst, get_allocator_ref());
2193 opt_move_or_copy(begin, end, dst, guard);
2198 template <typename Guard>
2199 void opt_move_or_copy(pointer begin, pointer end, pointer dst, Guard& guard)
2201 // if trivial copy and default allocator, memcpy
2202 boost::container::uninitialized_move_alloc(get_allocator_ref(), begin, end, dst);
2206 template <typename Iterator>
2207 void opt_copy(Iterator begin, Iterator end, pointer dst)
2209 typedef typename dtl::if_c
2210 < boost::move_detail::is_nothrow_copy_constructible<T>::value
2211 , detail::null_construction_guard
2212 , detail::construction_guard<allocator_type>
2215 guard_t guard(dst, get_allocator_ref());
2217 opt_copy(begin, end, dst, guard);
2222 template <typename Iterator, typename Guard>
2223 void opt_copy(Iterator begin, Iterator end, pointer dst, Guard& guard)
2225 while (begin != end)
2227 this->alloc_construct(dst++, *begin++);
2232 template <typename Guard>
2233 void opt_copy(const_pointer begin, const_pointer end, pointer dst, Guard& guard)
2235 // if trivial copy and default allocator, memcpy
2236 boost::container::uninitialized_copy_alloc(get_allocator_ref(), begin, end, dst);
2240 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
2242 template <typename... Args>
2243 void resize_front_impl(size_type sz , Args&&... args)
2247 const size_type n = sz - size();
2249 if (sz <= front_capacity())
2251 construct_n(m_.buffer + m_.front_idx - n, n, boost::forward<Args>(args)...);
2252 m_.set_front_idx(m_.front_idx - n);
2256 resize_front_slow_path(sz, n, boost::forward<Args>(args)...);
2260 while (this->size() > sz)
2267 template <typename... Args>
2268 void resize_front_slow_path(size_type sz, size_type n, Args&&... args)
2270 const size_type new_capacity = calculate_new_capacity(sz + back_free_capacity());
2271 pointer new_buffer = allocate(new_capacity);
2272 allocation_guard new_buffer_guard(new_buffer, new_capacity, get_allocator_ref());
2274 const size_type new_old_elem_index = new_capacity - size();
2275 const size_type new_elem_index = new_old_elem_index - n;
2277 detail::construction_guard<allocator_type> guard(new_buffer + new_elem_index, get_allocator_ref());
2278 guarded_construct_n(new_buffer + new_elem_index, n, guard, boost::forward<Args>(args)...);
2280 buffer_move_or_copy(new_buffer + new_old_elem_index, guard);
2283 new_buffer_guard.release();
2285 m_.buffer = new_buffer;
2286 m_.set_capacity(new_capacity);
2287 m_.set_back_idx(new_old_elem_index + m_.back_idx - m_.front_idx);
2288 m_.set_front_idx(new_elem_index);
2291 template <typename... Args>
2292 void resize_back_impl(size_type sz, Args&&... args)
2296 const size_type n = sz - size();
2298 if (sz <= back_capacity())
2300 construct_n(m_.buffer + m_.back_idx, n, boost::forward<Args>(args)...);
2301 m_.set_back_idx(m_.back_idx + n);
2305 resize_back_slow_path(sz, n, boost::forward<Args>(args)...);
2317 template <typename... Args>
2318 void resize_back_slow_path(size_type sz, size_type n, Args&&... args)
2320 const size_type new_capacity = calculate_new_capacity(sz + front_free_capacity());
2321 pointer new_buffer = allocate(new_capacity);
2322 allocation_guard new_buffer_guard(new_buffer, new_capacity, get_allocator_ref());
2324 detail::construction_guard<allocator_type> guard(new_buffer + m_.back_idx, get_allocator_ref());
2325 guarded_construct_n(new_buffer + m_.back_idx, n, guard, boost::forward<Args>(args)...);
2327 buffer_move_or_copy(new_buffer + m_.front_idx);
2330 new_buffer_guard.release();
2332 m_.buffer = new_buffer;
2333 m_.set_capacity(new_capacity);
2334 m_.set_back_idx(m_.back_idx + n);
2337 template <typename... Args>
2338 iterator emplace_slow_path(size_type new_elem_index, Args&&... args)
2340 pointer position = begin() + new_elem_index;
2342 // prefer moving front to access memory forward if there are less elems to move
2343 bool prefer_move_front = new_elem_index <= size()/2;
2345 if (front_free_capacity() && (!back_free_capacity() || prefer_move_front))
2347 BOOST_ASSERT(size() >= 1);
2349 // move things closer to the front a bit
2351 // avoid invalidating any reference in args later
2352 T tmp(boost::forward<Args>(args)...);
2354 // construct at front - 1 from front (no guard)
2355 this->alloc_construct(begin() - 1, boost::move(*begin()));
2357 // move front half left
2358 boost::move(begin() + 1, position, begin());
2361 // move assign new elem before pos
2363 *position = boost::move(tmp);
2367 else if (back_free_capacity()) {
2368 BOOST_ASSERT(size() >= 1);
2370 // move things closer to the end a bit
2372 // avoid invalidating any reference in args later
2373 T tmp(boost::forward<Args>(args)...);
2375 // construct at back + 1 from back (no guard)
2376 this->alloc_construct(end(), boost::move(back()));
2378 // move back half right
2379 boost::container::move_backward(position, end() - 1, end());
2382 // move assign new elem to pos
2383 *position = boost::move(tmp);
2389 return emplace_reallocating_slow_path(prefer_move_front, new_elem_index, boost::forward<Args>(args)...);
2393 template <typename... Args>
2394 pointer emplace_reallocating_slow_path(bool make_front_free, size_type new_elem_index, Args&&... args)
2397 size_type new_capacity = calculate_new_capacity(capacity() + 1);
2398 pointer new_buffer = allocate(new_capacity);
2401 allocation_guard new_buffer_guard(new_buffer, new_capacity, get_allocator_ref());
2403 size_type new_front_index = (make_front_free)
2404 ? new_capacity - back_free_capacity() - size() - 1
2407 iterator new_begin = new_buffer + new_front_index;
2408 iterator new_position = new_begin + new_elem_index;
2409 iterator old_position = begin() + new_elem_index;
2411 // construct new element (and guard it)
2412 this->alloc_construct(new_position, boost::forward<Args>(args)...);
2414 detail::construction_guard<allocator_type> second_half_guard(new_position, get_allocator_ref());
2415 second_half_guard.extend();
2417 // move front-pos (possibly guarded)
2418 detail::construction_guard<allocator_type> first_half_guard(new_begin, get_allocator_ref());
2419 opt_move_or_copy(begin(), old_position, new_begin, first_half_guard);
2421 // move pos+1-end (possibly guarded)
2422 opt_move_or_copy(old_position, end(), new_position + 1, second_half_guard);
2425 destroy_elements(begin(), end());
2426 deallocate_buffer();
2428 // release alloc and other guards
2429 second_half_guard.release();
2430 first_half_guard.release();
2431 new_buffer_guard.release();
2434 m_.set_capacity(new_capacity);
2435 m_.buffer = new_buffer;
2436 m_.set_back_idx(new_front_index + size() + 1);
2437 m_.set_front_idx(new_front_index);
2439 return new_position;
2442 #else //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
2444 #define BOOST_CONTAINER_DEVECTOR_SLOW_PATH(N) \
2445 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
2446 void resize_front_impl(size_type sz BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
2450 const size_type n = sz - size();\
2451 if (sz <= front_capacity()){\
2452 construct_n(m_.buffer + m_.front_idx - n, n BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
2453 m_.set_front_idx(m_.front_idx - n);\
2457 resize_front_slow_path(sz, n BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
2461 while (this->size() > sz)\
2468 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
2469 void resize_front_slow_path(size_type sz, size_type n BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
2471 const size_type new_capacity = calculate_new_capacity(sz + back_free_capacity());\
2472 pointer new_buffer = allocate(new_capacity);\
2473 allocation_guard new_buffer_guard(new_buffer, new_capacity, get_allocator_ref());\
2475 const size_type new_old_elem_index = new_capacity - size();\
2476 const size_type new_elem_index = new_old_elem_index - n;\
2478 detail::construction_guard<allocator_type> guard(new_buffer + new_elem_index, get_allocator_ref());\
2479 guarded_construct_n(new_buffer + new_elem_index, n, guard BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
2481 buffer_move_or_copy(new_buffer + new_old_elem_index, guard);\
2484 new_buffer_guard.release();\
2485 m_.buffer = new_buffer;\
2486 m_.set_capacity(new_capacity);\
2487 m_.set_back_idx(new_old_elem_index + m_.back_idx - m_.front_idx);\
2488 m_.set_front_idx(new_elem_index);\
2491 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
2492 void resize_back_impl(size_type sz BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
2496 const size_type n = sz - size();\
2498 if (sz <= back_capacity())\
2500 construct_n(m_.buffer + m_.back_idx, n BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
2501 m_.set_back_idx(m_.back_idx + n);\
2505 resize_back_slow_path(sz, n BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
2510 while (size() > sz)\
2517 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
2518 void resize_back_slow_path(size_type sz, size_type n BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
2520 const size_type new_capacity = calculate_new_capacity(sz + front_free_capacity());\
2521 pointer new_buffer = allocate(new_capacity);\
2522 allocation_guard new_buffer_guard(new_buffer, new_capacity, get_allocator_ref());\
2524 detail::construction_guard<allocator_type> guard(new_buffer + m_.back_idx, get_allocator_ref());\
2525 guarded_construct_n(new_buffer + m_.back_idx, n, guard BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
2527 buffer_move_or_copy(new_buffer + m_.front_idx);\
2530 new_buffer_guard.release();\
2532 m_.buffer = new_buffer;\
2533 m_.set_capacity(new_capacity);\
2534 m_.set_back_idx(m_.back_idx + n);\
2537 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
2538 iterator emplace_slow_path(size_type new_elem_index BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
2540 pointer position = begin() + new_elem_index;\
2542 bool prefer_move_front = new_elem_index <= size()/2;\
2544 if (front_free_capacity() && (!back_free_capacity() || prefer_move_front))\
2546 BOOST_ASSERT(size() >= 1);\
2547 typename dtl::aligned_storage<sizeof(T), dtl::alignment_of<T>::value>::type v;\
2548 T *vp = move_detail::force_ptr<T *>(v.data);\
2549 allocator_traits_type::construct(get_stored_allocator(), vp BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
2551 dtl::value_destructor<allocator_type> on_exit(get_stored_allocator(), tmp); (void)on_exit;\
2553 this->alloc_construct(begin() - 1, boost::move(*begin()));\
2554 boost::move(begin() + 1, position, begin());\
2557 *position = boost::move(tmp);\
2560 else if (back_free_capacity()) {\
2561 BOOST_ASSERT(size() >= 1);\
2562 typename dtl::aligned_storage<sizeof(T), dtl::alignment_of<T>::value>::type v;\
2563 T *vp = move_detail::force_ptr<T *>(v.data);\
2564 allocator_traits_type::construct(get_stored_allocator(), vp BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
2566 dtl::value_destructor<allocator_type> on_exit(get_stored_allocator(), tmp); (void)on_exit;\
2567 this->alloc_construct(end(), boost::move(back()));\
2568 boost::container::move_backward(position, end() - 1, end());\
2570 *position = boost::move(tmp);\
2574 return emplace_reallocating_slow_path(prefer_move_front, new_elem_index BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
2578 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
2579 pointer emplace_reallocating_slow_path(bool make_front_free, size_type new_elem_index BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
2581 size_type new_capacity = calculate_new_capacity(capacity() + 1);\
2582 pointer new_buffer = allocate(new_capacity);\
2583 allocation_guard new_buffer_guard(new_buffer, new_capacity, get_allocator_ref());\
2584 size_type new_front_index = (make_front_free)\
2585 ? new_capacity - back_free_capacity() - size() - 1\
2587 iterator new_begin = new_buffer + new_front_index;\
2588 iterator new_position = new_begin + new_elem_index;\
2589 iterator old_position = begin() + new_elem_index;\
2590 this->alloc_construct(new_position BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
2591 detail::construction_guard<allocator_type> second_half_guard(new_position, get_allocator_ref());\
2592 second_half_guard.extend();\
2593 detail::construction_guard<allocator_type> first_half_guard(new_begin, get_allocator_ref());\
2594 opt_move_or_copy(begin(), old_position, new_begin, first_half_guard);\
2595 opt_move_or_copy(old_position, end(), new_position + 1, second_half_guard);\
2596 destroy_elements(begin(), end());\
2597 deallocate_buffer();\
2598 second_half_guard.release();\
2599 first_half_guard.release();\
2600 new_buffer_guard.release();\
2601 m_.set_capacity(new_capacity);\
2602 m_.buffer = new_buffer;\
2603 m_.set_back_idx(new_front_index + size() + 1);\
2604 m_.set_front_idx(new_front_index);\
2605 return new_position;\
2608 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_DEVECTOR_SLOW_PATH)
2609 #undef BOOST_CONTAINER_DEVECTOR_SLOW_PATH
2611 #endif //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
2613 void unsafe_uninitialized_grow_front(size_type n)
2615 BOOST_ASSERT(n >= size());
2617 size_type need = n - size();
2619 if (need > front_free_capacity())
2621 reallocate_at(n + back_free_capacity(), need);
2624 m_.set_front_idx(m_.front_idx - need);
2627 void unsafe_uninitialized_shrink_front(size_type n)
2629 BOOST_ASSERT(n <= size());
2631 size_type doesnt_need = size() - n;
2632 m_.set_front_idx(m_.front_idx + doesnt_need);
2635 void unsafe_uninitialized_grow_back(size_type n)
2637 BOOST_ASSERT(n >= size());
2639 size_type need = n - size();
2641 if (need > back_free_capacity())
2643 reallocate_at(n + front_free_capacity(), front_free_capacity());
2646 m_.set_back_idx(m_.back_idx + need);
2649 void unsafe_uninitialized_shrink_back(size_type n)
2651 BOOST_ASSERT(n <= size());
2653 size_type doesnt_need = size() - n;
2654 m_.set_back_idx(m_.back_idx - doesnt_need);
2658 void reallocate_at(size_type new_capacity, size_type buffer_offset)
2660 pointer new_buffer = allocate(new_capacity);
2661 allocation_guard new_buffer_guard(new_buffer, new_capacity, get_allocator_ref());
2663 buffer_move_or_copy(new_buffer + buffer_offset);
2665 new_buffer_guard.release();
2667 m_.buffer = new_buffer;
2668 //Safe cast, allocate() will handle stored_size_type overflow
2669 m_.set_capacity(new_capacity);
2670 m_.set_back_idx(size_type(m_.back_idx - m_.front_idx) + buffer_offset);
2671 m_.set_front_idx(buffer_offset);
2673 BOOST_ASSERT(invariants_ok());
2676 template <typename ForwardIterator>
2677 iterator insert_range(const_iterator position, ForwardIterator first, ForwardIterator last)
2679 size_type n = boost::container::iterator_udistance(first, last);
2681 if (position == end() && back_free_capacity() >= n) {// fast path
2682 iterator r(this->end());
2683 boost::container::uninitialized_copy_alloc(get_allocator_ref(), first, last, this->raw_end());
2684 m_.set_back_idx(m_.back_idx + n);
2687 else if (position == begin() && front_free_capacity() >= n) { // secondary fast path
2688 boost::container::uninitialized_copy_alloc(get_allocator_ref(), first, last, this->raw_begin() - n);
2689 m_.set_front_idx(m_.front_idx - n);
2693 return insert_range_slow_path(position, first, last);
2697 template <typename ForwardIterator>
2698 iterator insert_range_slow_path(const_iterator position, ForwardIterator first, ForwardIterator last)
2700 size_type n = boost::container::iterator_udistance(first, last);
2701 size_type index = size_type(position - begin());
2703 if (front_free_capacity() + back_free_capacity() >= n) {
2704 // if we move enough, it can be done without reallocation
2706 iterator middle = begin() + index;
2707 n -= insert_range_slow_path_near_front(middle, first, n);
2710 insert_range_slow_path_near_back(middle, first, n);
2713 BOOST_ASSERT(first == last);
2714 return begin() + index;
2717 const bool prefer_move_front = 2 * index <= size();
2718 return insert_range_reallocating_slow_path(prefer_move_front, index, first, n);
2722 template <typename Iterator>
2723 size_type insert_range_slow_path_near_front(iterator position, Iterator& first, size_type n)
2725 size_type n_front = dtl::min_value(front_free_capacity(), n);
2726 iterator new_begin = begin() - n_front;
2727 iterator ctr_pos = new_begin;
2728 detail::construction_guard<allocator_type> ctr_guard(ctr_pos, get_allocator_ref());
2730 while (ctr_pos != begin()) {
2731 this->alloc_construct(ctr_pos++, *(first++));
2735 boost::movelib::rotate_gcd(new_begin, ctr_pos, position);
2736 m_.set_front_idx(m_.front_idx - n_front);
2738 ctr_guard.release();
2740 BOOST_ASSERT(invariants_ok());
2745 template <typename Iterator>
2746 size_type insert_range_slow_path_near_back(iterator position, Iterator& first, size_type n)
2748 const size_type n_back = dtl::min_value(back_free_capacity(), n);
2749 iterator ctr_pos = end();
2751 detail::construction_guard<allocator_type> ctr_guard(ctr_pos, get_allocator_ref());
2753 for (size_type i = 0; i < n_back; ++i) {
2754 this->alloc_construct(ctr_pos++, *first++);
2758 boost::movelib::rotate_gcd(position, end(), ctr_pos);
2759 m_.set_back_idx(m_.back_idx + n_back);
2761 ctr_guard.release();
2763 BOOST_ASSERT(invariants_ok());
2768 template <typename Iterator>
2769 iterator insert_range_reallocating_slow_path
2770 (bool make_front_free, size_type new_elem_index, Iterator elems, size_type n)
2773 const size_type new_capacity = calculate_new_capacity(capacity() + n);
2774 pointer new_buffer = allocate(new_capacity);
2777 allocation_guard new_buffer_guard(new_buffer, new_capacity, get_allocator_ref());
2779 const size_type new_front_index = (make_front_free)
2780 ? new_capacity - back_free_capacity() - size() - n
2783 const iterator new_begin = new_buffer + new_front_index;
2784 const iterator new_position = new_begin + new_elem_index;
2785 const iterator old_position = begin() + new_elem_index;
2787 // construct new element (and guard it)
2788 iterator second_half_position = new_position;
2789 detail::construction_guard<allocator_type> second_half_guard(second_half_position, get_allocator_ref());
2791 for (size_type i = 0; i < n; ++i) {
2792 this->alloc_construct(second_half_position++, *(elems++));
2793 second_half_guard.extend();
2796 // move front-pos (possibly guarded)
2797 detail::construction_guard<allocator_type> first_half_guard(new_begin, get_allocator_ref());
2798 opt_move_or_copy(begin(), old_position, new_begin, first_half_guard);
2800 // move pos+1-end (possibly guarded)
2801 opt_move_or_copy(old_position, end(), second_half_position, second_half_guard);
2804 destroy_elements(begin(), end());
2805 deallocate_buffer();
2807 // release alloc and other guards
2808 second_half_guard.release();
2809 first_half_guard.release();
2810 new_buffer_guard.release();
2813 m_.set_capacity(new_capacity);
2814 m_.buffer = new_buffer;
2815 m_.set_back_idx(new_front_index + size() + n);
2816 m_.set_front_idx(new_front_index);
2818 return new_position;
2821 template <typename Iterator>
2822 void construct_from_range(Iterator begin, Iterator end)
2824 allocation_guard buffer_guard(m_.buffer, m_.capacity, get_allocator_ref());
2825 opt_copy(begin, end, m_.buffer);
2827 buffer_guard.release();
2830 template <typename ForwardIterator>
2831 void allocate_and_copy_range(ForwardIterator first, ForwardIterator last)
2833 size_type n = boost::container::iterator_udistance(first, last);
2835 pointer new_buffer = n ? allocate(n) : pointer();
2836 allocation_guard new_buffer_guard(new_buffer, n, get_allocator_ref());
2838 opt_copy(first, last, new_buffer);
2840 destroy_elements(begin(), end());
2841 deallocate_buffer();
2844 m_.buffer = new_buffer;
2848 new_buffer_guard.release();
2851 static void swap_big_big(devector& a, devector& b) BOOST_NOEXCEPT
2853 boost::adl_move_swap(a.m_.capacity, b.m_.capacity);
2854 boost::adl_move_swap(a.m_.buffer, b.m_.buffer);
2857 template <typename ForwardIterator>
2858 void overwrite_buffer_impl(ForwardIterator first, ForwardIterator last, dtl::true_)
2860 const size_type n = boost::container::iterator_udistance(first, last);
2862 BOOST_ASSERT(capacity() >= n);
2863 boost::container::uninitialized_copy_alloc_n
2864 ( get_allocator_ref(), boost::movelib::iterator_to_raw_pointer(first)
2865 , n, boost::movelib::iterator_to_raw_pointer(m_.buffer));
2870 template <typename InputIterator>
2871 InputIterator overwrite_buffer_impl(InputIterator first, InputIterator last, dtl::false_)
2873 pointer pos = m_.buffer;
2874 detail::construction_guard<allocator_type> front_guard(pos, get_allocator_ref());
2876 while (first != last && pos != begin()) {
2877 this->alloc_construct(pos++, *first++);
2878 front_guard.extend();
2881 while (first != last && pos != end()) {
2885 detail::construction_guard<allocator_type> back_guard(pos, get_allocator_ref());
2887 iterator capacity_end = m_.buffer + capacity();
2888 while (first != last && pos != capacity_end) {
2889 this->alloc_construct(pos++, *first++);
2890 back_guard.extend();
2893 pointer destroy_after = dtl::min_value(dtl::max_value(begin(), pos), end());
2894 destroy_elements(destroy_after, end());
2896 front_guard.release();
2897 back_guard.release();
2900 m_.set_back_idx(size_type(pos - begin()));
2904 template <typename ForwardIterator>
2905 BOOST_CONTAINER_FORCEINLINE void overwrite_buffer(ForwardIterator first, ForwardIterator last)
2907 this->overwrite_buffer_impl(first, last,
2908 dtl::bool_<dtl::is_trivially_destructible<T>::value>());
2911 bool invariants_ok()
2913 return (!m_.capacity || m_.buffer)
2914 && m_.front_idx <= m_.back_idx
2915 && m_.back_idx <= m_.capacity;
2918 struct impl : allocator_type
2921 impl(const impl &i);
2924 allocator_type &get_al()
2927 static pointer do_allocate(allocator_type &a, size_type cap)
2930 //First detect overflow on smaller stored_size_types
2931 if (cap > stored_size_type(-1)){
2932 boost::container::throw_length_error("get_next_capacity, allocator's max size reached");
2934 return allocator_traits_type::allocate(a, cap);
2942 : allocator_type(), buffer(), front_idx(), back_idx(), capacity()
2943 #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
2944 , capacity_alloc_count(0)
2948 explicit impl(const allocator_type &a)
2949 : allocator_type(a), buffer(), front_idx(), back_idx(), capacity()
2950 #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
2951 , capacity_alloc_count(0)
2955 impl(const allocator_type &a, size_type f, size_type b, size_type c)
2956 : allocator_type(a), buffer(do_allocate(get_al(), c))
2957 //static cast sizes, as the allocation function will take care of overflows
2958 , front_idx(static_cast<stored_size_type>(f))
2959 , back_idx(static_cast<stored_size_type>(b))
2960 , capacity(static_cast<stored_size_type>(c))
2961 #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
2962 , capacity_alloc_count(size_type(buffer != pointer()))
2966 impl(const allocator_type &a, pointer p, size_type f, size_type b, size_type c)
2967 : allocator_type(a), buffer(p)
2968 //static cast sizes, as the allocation function will take care of overflows
2969 , front_idx(static_cast<stored_size_type>(f))
2970 , back_idx(static_cast<stored_size_type>(b))
2971 , capacity(static_cast<stored_size_type>(c))
2972 #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
2973 , capacity_alloc_count(0)
2977 impl(BOOST_RV_REF(allocator_type) a, pointer p, size_type f, size_type b, size_type c)
2978 : allocator_type(boost::move(a)), buffer(p)
2979 //static cast sizes, as the allocation function will take care of overflows
2980 , front_idx(static_cast<stored_size_type>(f))
2981 , back_idx(static_cast<stored_size_type>(b))
2982 , capacity(static_cast<stored_size_type>(c))
2983 #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
2984 , capacity_alloc_count(0)
2988 void set_back_idx(size_type bi)
2989 { back_idx = static_cast<stored_size_type>(bi);}
2991 void set_front_idx(size_type fi)
2992 { front_idx = static_cast<stored_size_type>(fi);}
2994 void set_capacity(size_type c)
2995 { capacity = static_cast<stored_size_type>(c);}
2998 stored_size_type front_idx;
2999 stored_size_type back_idx;
3000 stored_size_type capacity;
3001 #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
3002 size_type capacity_alloc_count;
3007 #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
3009 void reset_alloc_stats()
3011 m_.capacity_alloc_count = 0;
3014 size_type get_alloc_count() const
3016 return m_.capacity_alloc_count;
3019 #endif // ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
3021 #endif // ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
3024 }} // namespace boost::container
3026 #include <boost/container/detail/config_end.hpp>
3028 #endif // BOOST_CONTAINER_DEVECTOR_HPP