Back to home page

EIC code displayed by LXR

 
 

    


File indexing completed on 2025-07-01 08:10:21

0001 //////////////////////////////////////////////////////////////////////////////
0002 //
0003 // (C) Copyright Benedek Thaler 2015-2016
0004 // (C) Copyright Ion Gaztanaga 2019-2020. Distributed under the Boost
0005 // Software License, Version 1.0. (See accompanying file
0006 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0007 //
0008 // See http://www.boost.org/libs/container for documentation.
0009 //
0010 //////////////////////////////////////////////////////////////////////////////
0011 
0012 #ifndef BOOST_CONTAINER_DEVECTOR_HPP
0013 #define BOOST_CONTAINER_DEVECTOR_HPP
0014 
0015 #include <boost/container/detail/config_begin.hpp>
0016 #include <boost/container/detail/workaround.hpp>
0017 
0018 #include <cstring> // memcpy
0019 
0020 #include <boost/assert.hpp>
0021 
0022 #include <boost/container/detail/copy_move_algo.hpp>
0023 #include <boost/container/new_allocator.hpp> //new_allocator
0024 #include <boost/container/allocator_traits.hpp> //allocator_traits
0025 #include <boost/container/detail/algorithm.hpp> //equal()
0026 #include <boost/container/throw_exception.hpp>
0027 #include <boost/container/options.hpp>
0028 
0029 #include <boost/container/detail/guards_dended.hpp>
0030 #include <boost/container/detail/iterator.hpp>
0031 #include <boost/container/detail/iterators.hpp>
0032 #include <boost/container/detail/destroyers.hpp>
0033 #include <boost/container/detail/min_max.hpp>
0034 #include <boost/container/detail/next_capacity.hpp>
0035 #include <boost/container/detail/alloc_helpers.hpp>
0036 #include <boost/container/detail/advanced_insert_int.hpp>
0037 
0038 // move
0039 #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
0040 #include <boost/move/detail/fwd_macros.hpp>
0041 #endif
0042 #include <boost/move/detail/move_helpers.hpp>
0043 #include <boost/move/adl_move_swap.hpp>
0044 #include <boost/move/iterator.hpp>
0045 #include <boost/move/traits.hpp>
0046 #include <boost/move/utility_core.hpp>
0047 #include <boost/move/detail/to_raw_pointer.hpp>
0048 #include <boost/move/algo/detail/merge.hpp>
0049 
0050 //std
0051 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
0052 #include <initializer_list>    //for std::initializer_list
0053 #endif
0054 
0055 namespace boost {
0056 namespace container {
0057 
0058 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
0059 
0060 struct growth_factor_60;
0061 
0062 template<class Options, class AllocatorSizeType>
0063 struct get_devector_opt
0064 {
0065     typedef devector_opt< typename default_if_void<typename Options::growth_factor_type, growth_factor_60>::type
0066                         , typename default_if_void<typename Options::stored_size_type, AllocatorSizeType>::type
0067                         , default_if_zero<Options::free_fraction, relocate_on_90::value>::value
0068                         > type;
0069 };
0070 
0071 template<class AllocatorSizeType>
0072 struct get_devector_opt<void, AllocatorSizeType>
0073 {
0074     typedef devector_opt< growth_factor_60, AllocatorSizeType, relocate_on_90::value> type;
0075 };
0076 
0077 #endif    //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
0078 
0079 struct reserve_only_tag_t {};
0080 struct reserve_uninitialized_t {};
0081 struct review_implementation_t {};
0082 
0083 //struct unsafe_uninitialized_tag_t {};
0084 
0085 /**
0086  * A vector-like sequence container providing front and back operations
0087  * (e.g: `push_front`/`pop_front`/`push_back`/`pop_back`) with amortized constant complexity.
0088  *
0089  * Models the [SequenceContainer], [ReversibleContainer], and [AllocatorAwareContainer] concepts.
0090  *
0091  * **Requires**:
0092  *   - `T` shall be [MoveInsertable] into the devector.
0093  *   - `T` shall be [Erasable] from any `devector<T, allocator_type, GP>`.
0094  *   - `GrowthFactor`, and `Allocator` must model the concepts with the same names or be void.
0095  *
0096  * **Definition**: `T` is `NothrowConstructible` if it's either nothrow move constructible or
0097  * nothrow copy constructible.
0098  *
0099  * **Definition**: `T` is `NothrowAssignable` if it's either nothrow move assignable or
0100  * nothrow copy assignable.
0101  *
0102  * **Exceptions**: The exception specifications assume `T` is nothrow [Destructible].
0103  *
0104  * Most methods providing the strong exception guarantee assume `T` either has a move
0105  * constructor marked noexcept or is [CopyInsertable] into the devector. If it isn't true,
0106  * and the move constructor throws, the guarantee is waived and the effects are unspecified.
0107  *
0108  * In addition to the exceptions specified in the **Throws** clause, the following operations
0109  * of `T` can throw when any of the specified concept is required:
0110  *   - [DefaultInsertable][]: Default constructor
0111  *   - [MoveInsertable][]: Move constructor
0112  *   - [CopyInsertable][]: Copy constructor
0113  *   - [DefaultConstructible][]: Default constructor
0114  *   - [EmplaceConstructible][]: Constructor selected by the given arguments
0115  *   - [MoveAssignable][]: Move assignment operator
0116  *   - [CopyAssignable][]: Copy assignment operator
0117  *
0118  * Furthermore, not `noexcept` methods throws whatever the allocator throws
0119  * if memory allocation fails. Such methods also throw `length_error` if the capacity
0120  * exceeds `max_size()`.
0121  *
0122  * **Remark**: If a method invalidates some iterators, it also invalidates references
0123  * and pointers to the elements pointed by the invalidated iterators.
0124  *
0125  *! \tparam Options A type produced from \c boost::container::devector_options.
0126  *
0127  * [SequenceContainer]: http://en.cppreference.com/w/cpp/concept/SequenceContainer
0128  * [ReversibleContainer]: http://en.cppreference.com/w/cpp/concept/ReversibleContainer
0129  * [AllocatorAwareContainer]: http://en.cppreference.com/w/cpp/concept/AllocatorAwareContainer
0130  * [DefaultInsertable]: http://en.cppreference.com/w/cpp/concept/DefaultInsertable
0131  * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
0132  * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
0133  * [Erasable]: http://en.cppreference.com/w/cpp/concept/Erasable
0134  * [DefaultConstructible]: http://en.cppreference.com/w/cpp/concept/DefaultConstructible
0135  * [Destructible]: http://en.cppreference.com/w/cpp/concept/Destructible
0136  * [EmplaceConstructible]: http://en.cppreference.com/w/cpp/concept/EmplaceConstructible
0137  * [MoveAssignable]: http://en.cppreference.com/w/cpp/concept/MoveAssignable
0138  * [CopyAssignable]: http://en.cppreference.com/w/cpp/concept/CopyAssignable
0139  */
0140 template < typename T, class A BOOST_CONTAINER_DOCONLY(= void), class Options BOOST_CONTAINER_DOCONLY(= void)>
0141 class devector
0142 {
0143    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
0144    typedef boost::container::allocator_traits
0145       <typename real_allocator<T, A>::type>                                      allocator_traits_type;
0146    typedef typename allocator_traits_type::size_type                             alloc_size_type;
0147    typedef typename get_devector_opt<Options, alloc_size_type>::type             options_type;
0148    typedef typename options_type::growth_factor_type                             growth_factor_type;
0149    typedef typename options_type::stored_size_type                               stored_size_type;
0150    BOOST_STATIC_CONSTEXPR std::size_t devector_min_free_fraction =
0151       options_type::free_fraction;
0152 
0153    #endif // ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
0154 
0155    public:
0156    // Standard Interface Types:
0157    typedef T                                                                     value_type;
0158    typedef BOOST_CONTAINER_IMPDEF
0159       (typename real_allocator<T BOOST_MOVE_I A>::type)                          allocator_type;
0160    typedef allocator_type                                                        stored_allocator_type;
0161    typedef typename    allocator_traits<allocator_type>::pointer                 pointer;
0162    typedef typename    allocator_traits<allocator_type>::const_pointer           const_pointer;
0163    typedef typename    allocator_traits<allocator_type>::reference               reference;
0164    typedef typename    allocator_traits<allocator_type>::const_reference         const_reference;
0165    typedef typename    allocator_traits<allocator_type>::size_type               size_type;
0166    typedef typename    allocator_traits<allocator_type>::difference_type         difference_type;
0167    typedef pointer                                                               iterator;
0168    typedef const_pointer                                                         const_iterator;
0169    typedef BOOST_CONTAINER_IMPDEF
0170       (boost::container::reverse_iterator<iterator>)                             reverse_iterator;
0171    typedef BOOST_CONTAINER_IMPDEF
0172       (boost::container::reverse_iterator<const_iterator>)                       const_reverse_iterator;
0173 
0174    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
0175    private:
0176    BOOST_COPYABLE_AND_MOVABLE(devector)
0177 
0178    // Guard to deallocate buffer on exception
0179    typedef typename detail::allocation_guard<allocator_type> allocation_guard;
0180 
0181    // Random access pseudo iterator always yielding to the same result
0182    typedef constant_iterator<T> cvalue_iterator;
0183 
0184    static size_type to_internal_capacity(size_type desired_capacity)
0185    {
0186       const size_type rounder = devector_min_free_fraction - 2u;
0187       const size_type divisor = devector_min_free_fraction - 1u;
0188       size_type const nc = ((desired_capacity + rounder) / divisor) * devector_min_free_fraction;
0189       BOOST_ASSERT(desired_capacity <= (nc - nc / devector_min_free_fraction));
0190       return nc;
0191    }
0192 
0193    #endif // ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
0194 
0195    // Standard Interface
0196    public:
0197    // construct/copy/destroy
0198 
0199    /**
0200    * **Effects**: Constructs an empty devector.
0201    *
0202    * **Postcondition**: `empty() && front_free_capacity() == 0
0203    * && back_free_capacity() == 0`.
0204    *
0205    * **Complexity**: Constant.
0206    */
0207    devector() BOOST_NOEXCEPT
0208       : m_()
0209    {}
0210 
0211    /**
0212    * **Effects**: Constructs an empty devector, using the specified allocator.
0213    *
0214    * **Postcondition**: `empty() && front_free_capacity() == 0
0215    * && back_free_capacity() == 0`.
0216    *
0217    * **Complexity**: Constant.
0218    */
0219    explicit devector(const allocator_type& allocator) BOOST_NOEXCEPT
0220       : m_(allocator)
0221    {}
0222 
0223    /**
0224    * **Effects**: Constructs an empty devector, using the specified allocator
0225    * and reserves `n` slots as if `reserve(n)` was called.
0226    *
0227    * **Postcondition**: `empty() && capacity() >= n`.
0228    *
0229    * **Exceptions**: Strong exception guarantee.
0230    *
0231    * **Complexity**: Constant.
0232    */
0233    devector(size_type n, reserve_only_tag_t, const allocator_type& allocator = allocator_type())
0234       : m_(reserve_only_tag_t(), allocator, to_internal_capacity(n))
0235    {}
0236 
0237    /**
0238    * **Effects**: Constructs an empty devector, using the specified allocator
0239    * and reserves at least `front_free_cap + back_free_cap` slots as if `reserve_front(front_cap)` and
0240    * `reserve_back(back_cap)` was called.
0241    *
0242    * **Postcondition**: `empty() && front_free_capacity() >= front_free_cap
0243    * && back_free_capacity() >= back_free_cap`.
0244    *
0245    * **Exceptions**: Strong exception guarantee.
0246    *
0247    * **Complexity**: Constant.
0248    */
0249    devector(size_type front_free_cap, size_type back_free_cap, reserve_only_tag_t, const allocator_type& allocator = allocator_type())
0250       : m_(reserve_only_tag_t(), allocator, front_free_cap, back_free_cap)
0251    {}
0252 
0253    /**
0254    * [DefaultInsertable]: http://en.cppreference.com/w/cpp/concept/DefaultInsertable
0255    *
0256    * **Effects**: Constructs a devector with `n` value_initialized elements using the specified allocator.
0257    *
0258    * **Requires**: `T` shall be [DefaultInsertable] into `*this`.
0259    *
0260    * **Postcondition**: `size() == n`.
0261    *
0262    * **Exceptions**: Strong exception guarantee.
0263    *
0264    * **Complexity**: Linear in `n`.
0265    */
0266    explicit devector(size_type n, const allocator_type& allocator = allocator_type())
0267       : m_(reserve_uninitialized_t(), allocator, n)
0268    {
0269       allocation_guard buffer_guard(m_.buffer, m_.capacity, get_allocator_ref());
0270       boost::container::uninitialized_value_init_alloc_n(get_allocator_ref(), n, this->priv_raw_begin());
0271       buffer_guard.release();
0272       BOOST_ASSERT(invariants_ok());
0273    }
0274 
0275    /**
0276    * **Effects**: Constructs a devector with `n` default-initialized elements using the specified allocator.
0277    *
0278    * **Requires**: `T` shall be [DefaultInsertable] into `*this`.
0279    *
0280    * **Postcondition**: `size() == n`.
0281    *
0282    * **Exceptions**: Strong exception guarantee.
0283    *
0284    * **Complexity**: Linear in `n`.
0285    */
0286    explicit devector(size_type n, default_init_t, const allocator_type& allocator = allocator_type())
0287       : m_(reserve_uninitialized_t(), allocator, n)
0288    {
0289       allocation_guard buffer_guard(m_.buffer, m_.capacity, get_allocator_ref());
0290       boost::container::uninitialized_default_init_alloc_n(get_allocator_ref(), n, this->priv_raw_begin());
0291       buffer_guard.release();
0292       BOOST_ASSERT(invariants_ok());
0293    }
0294 
0295    /**
0296    * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
0297    *
0298    * **Effects**: Constructs a devector with `n` copies of `value`, using the specified allocator.
0299    *
0300    * **Requires**: `T` shall be [CopyInsertable] into `*this`.
0301    *
0302    * **Postcondition**: `size() == n`.
0303    *
0304    * **Exceptions**: Strong exception guarantee.
0305    *
0306    * **Complexity**: Linear in `n`.
0307    */
0308    devector(size_type n, const T& value, const allocator_type& allocator = allocator_type())
0309       : m_(reserve_uninitialized_t(), allocator, n)
0310    {
0311       construct_from_range(cvalue_iterator(value, n), cvalue_iterator());
0312       BOOST_ASSERT(invariants_ok());
0313    }
0314 
0315    /**
0316    * **Effects**: Constructs a devector equal to the range `[first,last)`, using the specified allocator.
0317    *
0318    * **Requires**: `T` shall be [EmplaceConstructible] into `*this` from `*first`. If the specified
0319    * iterator does not meet the forward iterator requirements, `T` shall also be [MoveInsertable]
0320    * into `*this`.
0321    *
0322    * **Postcondition**: `size() == boost::container::iterator_distance(first, last)
0323    *
0324    * **Exceptions**: Strong exception guarantee.
0325    *
0326    * **Complexity**: Makes only `N` calls to the copy constructor of `T` (where `N` is the distance between `first`
0327    * and `last`), at most one allocation and no reallocations if iterators first and last are of forward,
0328    * bidirectional, or random access categories. It makes `O(N)` calls to the copy constructor of `T`
0329    * and `O(log(N)) reallocations if they are just input iterators.
0330    *
0331    * **Remarks**: Each iterator in the range `[first,last)` shall be dereferenced exactly once,
0332    * unless an exception is thrown.
0333    *
0334    * [EmplaceConstructible]: http://en.cppreference.com/w/cpp/concept/EmplaceConstructible
0335    * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
0336    */
0337    template <class InputIterator>
0338    devector(InputIterator first, InputIterator last, const allocator_type& allocator = allocator_type()
0339       //Input iterators
0340       BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_or
0341             < void
0342             BOOST_MOVE_I dtl::is_convertible<InputIterator BOOST_MOVE_I size_type>
0343             BOOST_MOVE_I dtl::is_not_input_iterator<InputIterator>
0344             >::type * = 0)
0345       )
0346       : m_(allocator)
0347    {
0348       BOOST_CONTAINER_TRY{
0349          while (first != last) {
0350             this->emplace_back(*first++);
0351          }
0352          BOOST_ASSERT(invariants_ok());
0353       }
0354       BOOST_CONTAINER_CATCH(...){
0355          this->destroy_elements(m_.buffer + m_.front_idx, m_.buffer + m_.back_idx);
0356          this->deallocate_buffer();
0357       }
0358       BOOST_CONTAINER_CATCH_END
0359    }
0360 
0361    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
0362 
0363    template <class ForwardIterator>
0364    devector(ForwardIterator first, ForwardIterator last, const allocator_type& allocator = allocator_type()
0365       //Other iterators
0366       BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_or
0367             < void
0368             BOOST_MOVE_I dtl::is_convertible<ForwardIterator BOOST_MOVE_I size_type>
0369             BOOST_MOVE_I dtl::is_input_iterator<ForwardIterator>
0370             >::type * = 0)
0371       )
0372       : m_(reserve_uninitialized_t(), allocator, boost::container::iterator_udistance(first, last))
0373    {
0374       this->construct_from_range(first, last);
0375       BOOST_ASSERT(invariants_ok());
0376    }
0377 
0378    #endif // ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
0379 
0380    /**
0381    * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
0382    *
0383    * **Effects**: Copy constructs a devector.
0384    *
0385    * **Requires**: `T` shall be [CopyInsertable] into `*this`.
0386    *
0387    * **Postcondition**: `this->size() == x.size()`.
0388    *
0389    * **Exceptions**: Strong exception guarantee.
0390    *
0391    * **Complexity**: Linear in the size of `x`.
0392    */
0393    devector(const devector& x)
0394       : m_(reserve_uninitialized_t(), allocator_traits_type::select_on_container_copy_construction(x.get_allocator_ref()), x.size())
0395    {
0396       this->construct_from_range(x.begin(), x.end());
0397       BOOST_ASSERT(invariants_ok());
0398    }
0399 
0400    /**
0401    * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
0402    *
0403    * **Effects**: Copy constructs a devector, using the specified allocator.
0404    *
0405    * **Requires**: `T` shall be [CopyInsertable] into `*this`.
0406    *
0407    * **Postcondition**: `*this == x`.
0408    *
0409    * **Exceptions**: Strong exception guarantee.
0410    *
0411    * **Complexity**: Linear in the size of `x`.
0412    */
0413    devector(const devector& x, const allocator_type& allocator)
0414       : m_(reserve_uninitialized_t(), allocator, x.size())
0415    {
0416       this->construct_from_range(x.begin(), x.end());
0417       BOOST_ASSERT(invariants_ok());
0418    }
0419 
0420    /**
0421    * **Effects**: Moves `rhs`'s resources to `*this`.
0422    *
0423    * **Throws**: Nothing.
0424    *
0425    * **Postcondition**: *this has the same value `rhs` had before the operation.
0426    *                    `rhs` is left in an unspecified but valid state.
0427    *
0428    * **Exceptions**: Strong exception guarantee if not `noexcept`.
0429    *
0430    * **Complexity**: Constant.
0431    */
0432    devector(BOOST_RV_REF(devector) rhs) BOOST_NOEXCEPT_OR_NOTHROW
0433       : m_(::boost::move(rhs.m_))
0434    {
0435       BOOST_ASSERT(      invariants_ok());
0436       BOOST_ASSERT(rhs.invariants_ok());
0437    }
0438 
0439    /**
0440    * **Effects**: Moves `rhs`'s resources to `*this`, using the specified allocator.
0441    *
0442    * **Throws**: If allocation or T's move constructor throws.
0443    *
0444    * **Postcondition**: *this has the same value `rhs` had before the operation.
0445    *                    `rhs` is left in an unspecified but valid state.
0446    *
0447    * **Exceptions**: Strong exception guarantee if not `noexcept`.
0448    *
0449    * **Complexity**: Linear if allocator != rhs.get_allocator(), otherwise constant.
0450    */
0451    devector(BOOST_RV_REF(devector) rhs, const allocator_type& allocator)
0452       : m_(review_implementation_t(), allocator, rhs.m_.buffer, rhs.m_.front_idx, rhs.m_.back_idx, rhs.m_.capacity)
0453    {
0454       // TODO should move elems-by-elems if the two allocators differ
0455       // buffer is already acquired, reset rhs
0456       rhs.m_.capacity = 0u;
0457       rhs.m_.buffer = pointer();
0458       rhs.m_.front_idx = 0;
0459       rhs.m_.back_idx = 0;
0460       BOOST_ASSERT(      invariants_ok());
0461       BOOST_ASSERT(rhs.invariants_ok());
0462    }
0463 
0464    #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
0465    /**
0466    * **Equivalent to**: `devector(il.begin(), il.end(), allocator)`.
0467    */
0468    devector(const std::initializer_list<T>& il, const allocator_type& allocator = allocator_type())
0469       : m_(reserve_uninitialized_t(), allocator, il.size())
0470    {
0471       this->construct_from_range(il.begin(), il.end());
0472       BOOST_ASSERT(invariants_ok());
0473    }
0474    #endif
0475 
0476 /**
0477    * **Effects**: Destroys the devector. All stored values are destroyed and
0478    * used memory, if any, deallocated.
0479    *
0480    * **Complexity**: Linear in the size of `*this`.
0481    */
0482 ~devector() BOOST_NOEXCEPT
0483 {
0484    destroy_elements(m_.buffer + m_.front_idx, m_.buffer + m_.back_idx);
0485    deallocate_buffer();
0486 }
0487 
0488 /**
0489    * **Effects**: Copies elements of `x` to `*this`. Previously
0490    * held elements get copy assigned to or destroyed.
0491    *
0492    * **Requires**: `T` shall be [CopyInsertable] into `*this`.
0493    *
0494    * **Postcondition**: `this->size() == x.size()`, the elements of
0495    * `*this` are copies of elements in `x` in the same order.
0496    *
0497    * **Returns**: `*this`.
0498    *
0499    * **Exceptions**: Strong exception guarantee if `T` is `NothrowConstructible`
0500    * and the allocator is allowed to be propagated
0501    * ([propagate_on_container_copy_assignment] is true),
0502    * Basic exception guarantee otherwise.
0503    *
0504    * **Complexity**: Linear in the size of `x` and `*this`.
0505    *
0506    * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
0507    * [propagate_on_container_copy_assignment]: http://en.cppreference.com/w/cpp/memory/allocator_traits
0508    */
0509 
0510    inline devector& operator=(BOOST_COPY_ASSIGN_REF(devector) rhs)
0511    {
0512       const devector &x = rhs;
0513       if (this == &x) { return *this; } // skip self
0514 
0515       const bool do_propagate = allocator_traits_type::propagate_on_container_copy_assignment::value;
0516       BOOST_IF_CONSTEXPR(do_propagate)
0517       {
0518          allocator_type &this_alloc = this->get_allocator_ref();
0519          const allocator_type &other_alloc = x.get_allocator_ref();
0520          if (this_alloc != other_alloc)
0521          {
0522             // new allocator cannot free existing storage
0523             this->clear();
0524             this->deallocate_buffer();
0525             m_.capacity = 0u;
0526             m_.buffer = pointer();
0527          }
0528          dtl::bool_<do_propagate> flag;
0529          dtl::assign_alloc(this_alloc, other_alloc, flag);
0530       }
0531 
0532       size_type n = x.size();
0533       if (m_.capacity >= n)
0534       {
0535             this->overwrite_buffer(x.begin(), x.end());
0536       }
0537       else
0538       {
0539             this->allocate_and_copy_range(x.begin(), x.end());
0540       }
0541 
0542       BOOST_ASSERT(invariants_ok());
0543 
0544       return *this;
0545    }
0546 
0547    /**
0548    * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
0549    *
0550    * **Effects**: Moves elements of `x` to `*this`. Previously
0551    * held elements get move/copy assigned to or destroyed.
0552    *
0553    * **Requires**: `T` shall be [MoveInsertable] into `*this`.
0554    *
0555    * **Postcondition**: `x` is left in an unspecified but valid state.
0556    *
0557    * **Returns**: `*this`.
0558    *
0559    * **Exceptions**: Basic exception guarantee if not `noexcept`.
0560    *
0561    * **Complexity**: Constant if allocator_traits_type::
0562    *   propagate_on_container_move_assignment is true or
0563    *   this->get>allocator() == x.get_allocator(). Linear otherwise.
0564    */
0565    devector& operator=(BOOST_RV_REF(devector) x)
0566       BOOST_NOEXCEPT_IF(allocator_traits_type::propagate_on_container_move_assignment::value
0567                                  || allocator_traits_type::is_always_equal::value)
0568    {
0569       if (BOOST_LIKELY(this != &x)) {
0570          //We know resources can be transferred at comiple time if both allocators are
0571          //always equal or the allocator is going to be propagated
0572          const bool can_steal_resources_alloc
0573             = allocator_traits_type::propagate_on_container_move_assignment::value
0574             || allocator_traits_type::is_always_equal::value;
0575          dtl::bool_<can_steal_resources_alloc> flag;
0576          this->priv_move_assign(boost::move(x), flag);
0577       }
0578       BOOST_ASSERT(invariants_ok());
0579       return *this;
0580    }
0581 
0582    #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
0583    /**
0584    * **Effects**: Copies elements of `il` to `*this`. Previously
0585    * held elements get copy assigned to or destroyed.
0586    *
0587    * **Requires**: `T` shall be [CopyInsertable] into `*this` and [CopyAssignable].
0588    *
0589    * **Postcondition**: `this->size() == il.size()`, the elements of
0590    * `*this` are copies of elements in `il` in the same order.
0591    *
0592    * **Exceptions**: Strong exception guarantee if `T` is nothrow copy assignable
0593    * from `T` and `NothrowConstructible`, Basic exception guarantee otherwise.
0594    *
0595    * **Returns**: `*this`.
0596    *
0597    * **Complexity**: Linear in the size of `il` and `*this`.
0598    *
0599    * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
0600    * [CopyAssignable]: http://en.cppreference.com/w/cpp/concept/CopyAssignable
0601    */
0602    inline devector& operator=(std::initializer_list<T> il)
0603    {
0604       this->assign(il.begin(), il.end());
0605       return *this;
0606    }
0607    #endif
0608 
0609    /**
0610    * **Effects**: Replaces elements of `*this` with a copy of `[first,last)`.
0611    * Previously held elements get copy assigned to or destroyed.
0612    *
0613    * **Requires**: `T` shall be [EmplaceConstructible] from `*first`. If the specified iterator
0614    * does not meet the forward iterator requirements, `T` shall be also [MoveInsertable] into `*this`.
0615    *
0616    * **Precondition**: `first` and `last` are not iterators into `*this`.
0617    *
0618    * **Postcondition**: `size() == N`, where `N` is the distance between `first` and `last`.
0619    *
0620    * **Exceptions**: Strong exception guarantee if `T` is nothrow copy assignable
0621    * from `*first` and `NothrowConstructible`, Basic exception guarantee otherwise.
0622    *
0623    * **Complexity**: Linear in the distance between `first` and `last`.
0624    * Makes a single reallocation at most if the iterators `first` and `last`
0625    * are of forward, bidirectional, or random access categories. It makes
0626    * `O(log(N))` reallocations if they are just input iterators.
0627    *
0628    * **Remarks**: Each iterator in the range `[first,last)` shall be dereferenced exactly once,
0629    * unless an exception is thrown.
0630    *
0631    * [EmplaceConstructible]: http://en.cppreference.com/w/cpp/concept/EmplaceConstructible
0632    * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
0633    */
0634    template <class InputIterator>
0635    void assign(InputIterator first, InputIterator last
0636       //Input iterators
0637       BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_or
0638             < void
0639             BOOST_MOVE_I dtl::is_convertible<InputIterator BOOST_MOVE_I size_type>
0640             BOOST_MOVE_I dtl::is_not_input_iterator<InputIterator>
0641             >::type * = 0)
0642       )
0643    {
0644       first = overwrite_buffer_impl(first, last, dtl::false_());
0645       while (first != last)
0646       {
0647          this->emplace_back(*first++);
0648       }
0649    }
0650 
0651    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
0652 
0653    template <class ForwardIterator>
0654    void assign(ForwardIterator first, ForwardIterator last
0655       //Other iterators
0656       BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_or
0657             < void
0658             BOOST_MOVE_I dtl::is_convertible<ForwardIterator BOOST_MOVE_I size_type>
0659             BOOST_MOVE_I dtl::is_input_iterator<ForwardIterator>
0660             >::type * = 0)
0661       )
0662    {
0663       const size_type n = boost::container::iterator_udistance(first, last);
0664 
0665       if (m_.capacity >= n)
0666       {
0667          overwrite_buffer(first, last);
0668       }
0669       else
0670       {
0671          allocate_and_copy_range(first, last);
0672       }
0673 
0674       BOOST_ASSERT(invariants_ok());
0675    }
0676 
0677    #endif // ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
0678 
0679    /**
0680     * **Effects**: Replaces elements of `*this` with `n` copies of `u`.
0681     * Previously held elements get copy assigned to or destroyed.
0682     *
0683     * **Requires**: `T` shall be [CopyInsertable] into `*this` and
0684     * [CopyAssignable].
0685     *
0686     * **Precondition**: `u` is not a reference into `*this`.
0687     *
0688     * **Postcondition**: `size() == n` and the elements of
0689     * `*this` are copies of `u`.
0690     *
0691     * **Exceptions**: Strong exception guarantee if `T` is nothrow copy assignable
0692     * from `u` and `NothrowConstructible`, Basic exception guarantee otherwise.
0693     *
0694     * **Complexity**: Linear in `n` and the size of `*this`.
0695     *
0696     * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
0697     * [CopyAssignable]: http://en.cppreference.com/w/cpp/concept/CopyAssignable
0698     */
0699    inline void assign(size_type n, const T& u)
0700    {
0701       cvalue_iterator first(u, n);
0702       cvalue_iterator last;
0703       this->assign(first, last);
0704    }
0705 
0706     #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
0707     /** **Equivalent to**: `assign(il.begin(), il.end())`. */
0708    inline void assign(std::initializer_list<T> il)
0709     {
0710          this->assign(il.begin(), il.end());
0711     }
0712     #endif
0713 
0714    /**
0715     * **Returns**: A copy of the allocator associated with the container.
0716     *
0717     * **Complexity**: Constant.
0718     */
0719    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0720     allocator_type get_allocator() const BOOST_NOEXCEPT
0721    {
0722       return static_cast<const allocator_type&>(m_);
0723    }
0724 
0725    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0726     const allocator_type &get_stored_allocator() const BOOST_NOEXCEPT
0727    {
0728       return static_cast<const allocator_type&>(m_);
0729    }
0730 
0731    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0732          allocator_type &get_stored_allocator() BOOST_NOEXCEPT
0733    {
0734       return static_cast<allocator_type&>(m_);
0735    }
0736 
0737    // iterators
0738 
0739    /**
0740     * **Returns**: A iterator pointing to the first element in the devector,
0741     * or the past the end iterator if the devector is empty.
0742     *
0743     * **Complexity**: Constant.
0744     */
0745    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0746          iterator begin() BOOST_NOEXCEPT
0747    {
0748       return m_.buffer + m_.front_idx;
0749    }
0750 
0751    /**
0752     * **Returns**: A constant iterator pointing to the first element in the devector,
0753     * or the past the end iterator if the devector is empty.
0754     *
0755     * **Complexity**: Constant.
0756     */
0757    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0758     const_iterator begin() const BOOST_NOEXCEPT
0759    {
0760       return m_.buffer + m_.front_idx;
0761    }
0762 
0763    /**
0764     * **Returns**: An iterator pointing past the last element of the container.
0765     *
0766     * **Complexity**: Constant.
0767     */
0768    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0769          iterator end() BOOST_NOEXCEPT
0770    {
0771       return m_.buffer + m_.back_idx;
0772    }
0773 
0774    /**
0775     * **Returns**: A constant iterator pointing past the last element of the container.
0776     *
0777     * **Complexity**: Constant.
0778     */
0779    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0780     const_iterator end() const BOOST_NOEXCEPT
0781    {
0782       return m_.buffer + m_.back_idx;
0783    }
0784 
0785    /**
0786     * **Returns**: A reverse iterator pointing to the first element in the reversed devector,
0787     * or the reverse past the end iterator if the devector is empty.
0788     *
0789     * **Complexity**: Constant.
0790     */
0791    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0792     reverse_iterator rbegin() BOOST_NOEXCEPT
0793    {
0794       return reverse_iterator(m_.buffer + m_.back_idx);
0795    }
0796 
0797    /**
0798     * **Returns**: A constant reverse iterator
0799     * pointing to the first element in the reversed devector,
0800     * or the reverse past the end iterator if the devector is empty.
0801     *
0802     * **Complexity**: Constant.
0803     */
0804    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0805     const_reverse_iterator rbegin() const BOOST_NOEXCEPT
0806    {
0807       return const_reverse_iterator(m_.buffer + m_.back_idx);
0808    }
0809 
0810    /**
0811     * **Returns**: A reverse iterator pointing past the last element in the
0812     * reversed container, or to the beginning of the reversed container if it's empty.
0813     *
0814     * **Complexity**: Constant.
0815     */
0816    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0817     reverse_iterator rend() BOOST_NOEXCEPT
0818    {
0819       return reverse_iterator(m_.buffer + m_.front_idx);
0820    }
0821 
0822    /**
0823     * **Returns**: A constant reverse iterator pointing past the last element in the
0824     * reversed container, or to the beginning of the reversed container if it's empty.
0825     *
0826     * **Complexity**: Constant.
0827     */
0828    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0829     const_reverse_iterator rend() const BOOST_NOEXCEPT
0830    {
0831       return const_reverse_iterator(m_.buffer + m_.front_idx);
0832    }
0833 
0834    /**
0835     * **Returns**: A constant iterator pointing to the first element in the devector,
0836     * or the past the end iterator if the devector is empty.
0837     *
0838     * **Complexity**: Constant.
0839     */
0840    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0841     const_iterator cbegin() const BOOST_NOEXCEPT
0842    {
0843       return m_.buffer + m_.front_idx;
0844    }
0845 
0846    /**
0847     * **Returns**: A constant iterator pointing past the last element of the container.
0848     *
0849     * **Complexity**: Constant.
0850     */
0851    const_iterator cend() const BOOST_NOEXCEPT
0852    {
0853       return m_.buffer + m_.back_idx;
0854    }
0855 
0856    /**
0857     * **Returns**: A constant reverse iterator
0858     * pointing to the first element in the reversed devector,
0859     * or the reverse past the end iterator if the devector is empty.
0860     *
0861     * **Complexity**: Constant.
0862     */
0863    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0864     const_reverse_iterator crbegin() const BOOST_NOEXCEPT
0865    {
0866       return const_reverse_iterator(m_.buffer + m_.back_idx);
0867    }
0868 
0869    /**
0870     * **Returns**: A constant reverse iterator pointing past the last element in the
0871     * reversed container, or to the beginning of the reversed container if it's empty.
0872     *
0873     * **Complexity**: Constant.
0874     */
0875    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0876     const_reverse_iterator crend() const BOOST_NOEXCEPT
0877    {
0878       return const_reverse_iterator(m_.buffer + m_.front_idx);
0879    }
0880 
0881    // capacity
0882 
0883    /**
0884     * **Returns**: True, if `size() == 0`, false otherwise.
0885     *
0886     * **Complexity**: Constant.
0887     */
0888    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0889     bool empty() const BOOST_NOEXCEPT
0890    {
0891       return m_.front_idx == m_.back_idx;
0892    }
0893 
0894    /**
0895     * **Returns**: The number of elements the devector contains.
0896     *
0897     * **Complexity**: Constant.
0898     */
0899    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0900     size_type size() const BOOST_NOEXCEPT
0901    {
0902       return size_type(m_.back_idx - m_.front_idx);
0903    }
0904 
0905    /**
0906     * **Returns**: The maximum number of elements the devector could possibly hold.
0907     *
0908     * **Complexity**: Constant.
0909     */
0910    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0911     size_type max_size() const BOOST_NOEXCEPT
0912    {
0913       size_type alloc_max = allocator_traits_type::max_size(get_allocator_ref());
0914       size_type size_type_max = (size_type)-1;
0915       return (alloc_max <= size_type_max) ? size_type(alloc_max) : size_type_max;
0916    }
0917 
0918    /**
0919    * **Returns**: The *minimum* number of elements that can be inserted into devector using
0920    *   position-based insertions without requiring a reallocation. Note that, unlike in 
0921    *   typical sequence containers like `vector`, `capacity()`, `capacity()` can be smaller than `size()`.
0922    *   This can happen if a user inserts elements in a particular way (usually inserting at
0923    *   front up to front_free_capacity() and at back up to back_free_capacity()).
0924    * 
0925    * **Complexity**: Constant.
0926    */
0927    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0928    size_type capacity() const BOOST_NOEXCEPT
0929    {
0930       size_type const cap_reserve = m_.capacity/devector_min_free_fraction;
0931       return m_.capacity > cap_reserve ? (m_.capacity - cap_reserve) : 0u;
0932    }
0933 
0934    /**
0935     * **Returns**: The total number of elements that can be pushed to the front of the
0936     * devector without requiring reallocation.
0937     *
0938     * **Complexity**: Constant.
0939     */
0940    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0941    size_type front_free_capacity() const BOOST_NOEXCEPT
0942    {
0943       return m_.front_idx;
0944    }
0945 
0946    /**
0947     * **Returns**: The total number of elements that can be pushed to the back of the
0948     * devector without requiring reallocation.
0949     *
0950     * **Complexity**: Constant.
0951     */
0952    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0953     size_type back_free_capacity() const BOOST_NOEXCEPT
0954    {
0955       return size_type(m_.capacity - m_.back_idx);
0956    }
0957 
0958    /**
0959    * **Effects**: If `sz` is greater than the size of `*this`,
0960    * additional value-initialized elements are inserted. Invalidates iterators
0961    * if reallocation is needed. If `sz` is smaller than than the size of `*this`,
0962    * elements are erased from the extremes.
0963    *
0964    * **Requires**: T shall be [MoveInsertable] into *this and [DefaultConstructible].
0965    *
0966    * **Postcondition**: `sz == size()`.
0967    *
0968    * **Exceptions**: Strong exception guarantee.
0969    *
0970    * **Complexity**: Linear in the size of `*this` and `sz`.
0971    *
0972    * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
0973    * [DefaultConstructible]: http://en.cppreference.com/w/cpp/concept/DefaultConstructible
0974    */
0975    inline void resize(size_type sz)
0976    {
0977       this->resize_back(sz);
0978    }
0979 
0980    /**
0981     * **Effects**: Same as resize(sz) but creates default-initialized
0982     * value-initialized.
0983     */
0984    inline void resize(size_type sz, default_init_t)
0985    {
0986       this->resize_back(sz, default_init);
0987    }
0988 
0989    /**
0990    * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
0991    *
0992    * **Effects**: If `sz` is greater than the size of `*this`,
0993    * copies of `c` are inserted at extremes.
0994    * If `sz` is smaller than than the size of `*this`,
0995    * elements are popped from the extremes.
0996    *
0997    * **Postcondition**: `sz == size()`.
0998    *
0999    * **Requires**: `T` shall be [CopyInsertable] into `*this`.
1000    *
1001    * **Exceptions**: Strong exception guarantee.
1002    *
1003    * **Complexity**: Linear in the size of `*this` and `sz`.
1004    */
1005    inline void resize(size_type sz, const T& c)
1006    {
1007       this->resize_back(sz, c);
1008    }
1009 
1010    /**
1011     * **Effects**: If `sz` is greater than the size of `*this`,
1012     * additional value-initialized elements are inserted
1013     * to the front. Invalidates iterators if reallocation is needed.
1014     * If `sz` is smaller than than the size of `*this`,
1015     * elements are popped from the front.
1016     *
1017     * **Requires**: T shall be [MoveInsertable] into *this and [DefaultConstructible].
1018     *
1019     * **Postcondition**: `sz == size()`.
1020     *
1021     * **Exceptions**: Strong exception guarantee.
1022     *
1023     * **Complexity**: Linear in the size of `*this` and `sz`.
1024     *
1025     * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
1026     * [DefaultConstructible]: http://en.cppreference.com/w/cpp/concept/DefaultConstructible
1027     */
1028    inline void resize_front(size_type sz)
1029    {
1030       resize_front_impl(sz);
1031       BOOST_ASSERT(invariants_ok());
1032    }
1033 
1034    /**
1035     * **Effects**: If `sz` is greater than the size of `*this`,
1036     * additional value-initialized elements are inserted
1037     * to the front. Invalidates iterators if reallocation is needed.
1038     * If `sz` is smaller than than the size of `*this`,
1039     * elements are popped from the front.
1040     *
1041     * **Requires**: T shall be [MoveInsertable] into *this and default_initializable.
1042     *
1043     * **Postcondition**: `sz == size()`.
1044     *
1045     * **Exceptions**: Strong exception guarantee.
1046     *
1047     * **Complexity**: Linear in the size of `*this` and `sz`.
1048     *
1049     * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
1050     */
1051    inline void resize_front(size_type sz, default_init_t)
1052    {
1053       resize_front_impl(sz, default_init);
1054       BOOST_ASSERT(invariants_ok());
1055    }
1056 
1057    /**
1058     * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
1059     *
1060     * **Effects**: If `sz` is greater than the size of `*this`,
1061     * copies of `c` are inserted to the front.
1062     * Invalidates iterators if reallocation is needed.
1063     * If `sz` is smaller than than the size of `*this`,
1064     * elements are popped from the front.
1065     *
1066     * **Postcondition**: `sz == size()`.
1067     *
1068     * **Requires**: `T` shall be [CopyInsertable] into `*this`.
1069     *
1070     * **Exceptions**: Strong exception guarantee.
1071     *
1072     * **Complexity**: Linear in the size of `*this` and `sz`.
1073     */
1074    inline void resize_front(size_type sz, const T& c)
1075    {
1076       resize_front_impl(sz, c);
1077       BOOST_ASSERT(invariants_ok());
1078    }
1079 
1080    /**
1081     * **Effects**: If `sz` is greater than the size of `*this`,
1082     * additional value-initialized elements are inserted
1083     * to the back. Invalidates iterators if reallocation is needed.
1084     * If `sz` is smaller than than the size of `*this`,
1085     * elements are popped from the back.
1086     *
1087     * **Requires**: T shall be [MoveInsertable] into *this and [DefaultConstructible].
1088     *
1089     * **Postcondition**: `sz == size()`.
1090     *
1091     * **Exceptions**: Strong exception guarantee.
1092     *
1093     * **Complexity**: Linear in the size of `*this` and `sz`.
1094     *
1095     * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
1096     * [DefaultConstructible]: http://en.cppreference.com/w/cpp/concept/DefaultConstructible
1097     */
1098    inline void resize_back(size_type sz)
1099    {
1100       resize_back_impl(sz);
1101       BOOST_ASSERT(invariants_ok());
1102    }
1103 
1104    /**
1105     * **Effects**: If `sz` is greater than the size of `*this`,
1106     * additional value-initialized elements are inserted
1107     * to the back. Invalidates iterators if reallocation is needed.
1108     * If `sz` is smaller than than the size of `*this`,
1109     * elements are popped from the back.
1110     *
1111     * **Requires**: T shall be [MoveInsertable] into *this and default initializable.
1112     *
1113     * **Postcondition**: `sz == size()`.
1114     *
1115     * **Exceptions**: Strong exception guarantee.
1116     *
1117     * **Complexity**: Linear in the size of `*this` and `sz`.
1118     *
1119     * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
1120     */
1121    inline void resize_back(size_type sz, default_init_t)
1122    {
1123       resize_back_impl(sz, default_init);
1124       BOOST_ASSERT(invariants_ok());
1125    }
1126 
1127    /**
1128     * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
1129     *
1130     * **Effects**: If `sz` is greater than the size of `*this`,
1131     * copies of `c` are inserted to the back.
1132     * If `sz` is smaller than than the size of `*this`,
1133     * elements are popped from the back.
1134     *
1135     * **Postcondition**: `sz == size()`.
1136     *
1137     * **Requires**: `T` shall be [CopyInsertable] into `*this`.
1138     *
1139     * **Exceptions**: Strong exception guarantee.
1140     *
1141     * **Complexity**: Linear in the size of `*this` and `sz`.
1142     */
1143    inline void resize_back(size_type sz, const T& c)
1144    {
1145       resize_back_impl(sz, c);
1146       BOOST_ASSERT(invariants_ok());
1147    }
1148 
1149    /**
1150     * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
1151     *
1152     * **Effects**: Ensures that at least `n` elements can be inserted
1153     * without requiring reallocation, where `n` is `new_capacity - size()`,
1154     * if `n` is positive. Otherwise, there are no effects.
1155     * Invalidates iterators if reallocation is needed.
1156     *
1157     * **Requires**: `T` shall be [MoveInsertable] into `*this`.
1158     *
1159     * **Complexity**: Linear in the size of *this.
1160     *
1161     * **Exceptions**: Strong exception guarantee.
1162     *
1163     * **Throws**: length_error if `new_capacity > max_size()`.
1164     */
1165    inline void reserve(size_type new_capacity)
1166    {
1167       if (this->capacity() < new_capacity) {
1168          const size_type rounder = devector_min_free_fraction - 2u;
1169          const size_type divisor = devector_min_free_fraction - 1u;
1170          size_type const nc = ((new_capacity + rounder)/divisor)*devector_min_free_fraction;
1171          BOOST_ASSERT(new_capacity <= (nc - nc / devector_min_free_fraction));
1172          size_type const sz = this->size();
1173          reallocate_at(nc, (nc-sz)/2u);
1174       }
1175       BOOST_ASSERT(invariants_ok());
1176    }
1177 
1178    /**
1179     * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
1180     *
1181     * **Effects**: Ensures that `n` elements can be pushed to the front
1182     * without requiring reallocation, where `n` is `new_capacity - size()`,
1183     * if `n` is positive. Otherwise, there are no effects.
1184     * Invalidates iterators if reallocation is needed.
1185     *
1186     * **Requires**: `T` shall be [MoveInsertable] into `*this`.
1187     *
1188     * **Complexity**: Linear in the size of *this.
1189     *
1190     * **Exceptions**: Strong exception guarantee.
1191     *
1192     * **Throws**: `length_error` if `new_capacity > max_size()`.
1193     */
1194    inline void reserve_front(size_type new_capacity)
1195    {
1196       if (front_capacity() >= new_capacity) { return; }
1197 
1198       reallocate_at(new_capacity + back_free_capacity(), new_capacity - size());
1199 
1200       BOOST_ASSERT(invariants_ok());
1201    }
1202 
1203    /**
1204     * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
1205     *
1206     * **Effects**: Ensures that `n` elements can be pushed to the back
1207     * without requiring reallocation, where `n` is `new_capacity - size()`,
1208     * if `n` is positive. Otherwise, there are no effects.
1209     * Invalidates iterators if reallocation is needed.
1210     *
1211     * **Requires**: `T` shall be [MoveInsertable] into `*this`.
1212     *
1213     * **Complexity**: Linear in the size of *this.
1214     *
1215     * **Exceptions**: Strong exception guarantee.
1216     *
1217     * **Throws**: length_error if `new_capacity > max_size()`.
1218     */
1219    inline void reserve_back(size_type new_capacity)
1220    {
1221       if (back_capacity() >= new_capacity) { return; }
1222 
1223       reallocate_at(new_capacity + front_free_capacity(), m_.front_idx);
1224 
1225       BOOST_ASSERT(invariants_ok());
1226    }
1227 
1228 
1229    /**
1230     * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
1231     *
1232     * **Effects**: Reduces `capacity()` to `size()`. Invalidates iterators.
1233     *
1234     * **Requires**: `T` shall be [MoveInsertable] into `*this`.
1235     *
1236     * **Exceptions**: Strong exception guarantee.
1237     *
1238     * **Complexity**: Linear in the size of *this.
1239     */
1240    inline void shrink_to_fit()
1241    {
1242       if(this->front_capacity() || this->back_capacity())
1243             this->reallocate_at(size(), 0);
1244    }
1245 
1246    // element access:
1247 
1248    /**
1249     * **Returns**: A reference to the `n`th element in the devector.
1250     *
1251     * **Precondition**: `n < size()`.
1252     *
1253     * **Complexity**: Constant.
1254     */
1255    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1256    reference operator[](size_type n) BOOST_NOEXCEPT
1257    {
1258       BOOST_ASSERT(n < size());
1259       return m_.buffer[m_.front_idx + n];
1260    }
1261 
1262    /**
1263     * **Returns**: A constant reference to the `n`th element in the devector.
1264     *
1265     * **Precondition**: `n < size()`.
1266     *
1267     * **Complexity**: Constant.
1268     */
1269    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1270    const_reference operator[](size_type n) const BOOST_NOEXCEPT
1271    {
1272       BOOST_ASSERT(n < size());
1273       return m_.buffer[m_.front_idx + n];
1274    }
1275 
1276    //! <b>Requires</b>: size() >= n.
1277    //!
1278    //! <b>Effects</b>: Returns an iterator to the nth element
1279    //!   from the beginning of the container. Returns end()
1280    //!   if n == size().
1281    //!
1282    //! <b>Throws</b>: Nothing.
1283    //!
1284    //! <b>Complexity</b>: Constant.
1285    //!
1286    //! <b>Note</b>: Non-standard extension
1287    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1288       iterator nth(size_type n) BOOST_NOEXCEPT_OR_NOTHROW
1289    {
1290       BOOST_ASSERT(n <= size());
1291       return iterator(m_.buffer + (m_.front_idx + n));
1292    }
1293 
1294    //! <b>Requires</b>: size() >= n.
1295    //!
1296    //! <b>Effects</b>: Returns a const_iterator to the nth element
1297    //!   from the beginning of the container. Returns end()
1298    //!   if n == size().
1299    //!
1300    //! <b>Throws</b>: Nothing.
1301    //!
1302    //! <b>Complexity</b>: Constant.
1303    //!
1304    //! <b>Note</b>: Non-standard extension
1305    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1306       const_iterator nth(size_type n) const BOOST_NOEXCEPT_OR_NOTHROW
1307    {
1308       BOOST_ASSERT(n <= size());
1309       return const_iterator(m_.buffer + (m_.front_idx + n));
1310    }
1311 
1312    //! <b>Requires</b>: begin() <= p <= end().
1313    //!
1314    //! <b>Effects</b>: Returns the index of the element pointed by p
1315    //!   and size() if p == end().
1316    //!
1317    //! <b>Throws</b>: Nothing.
1318    //!
1319    //! <b>Complexity</b>: Constant.
1320    //!
1321    //! <b>Note</b>: Non-standard extension
1322    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1323       size_type index_of(iterator p) BOOST_NOEXCEPT_OR_NOTHROW
1324    {
1325       BOOST_ASSERT(p >= begin());
1326       BOOST_ASSERT(p <= end());
1327       return static_cast<size_type>(p - this->begin());
1328    }
1329 
1330    //! <b>Requires</b>: begin() <= p <= end().
1331    //!
1332    //! <b>Effects</b>: Returns the index of the element pointed by p
1333    //!   and size() if p == end().
1334    //!
1335    //! <b>Throws</b>: Nothing.
1336    //!
1337    //! <b>Complexity</b>: Constant.
1338    //!
1339    //! <b>Note</b>: Non-standard extension
1340    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1341       size_type index_of(const_iterator p) const BOOST_NOEXCEPT_OR_NOTHROW
1342    {
1343       BOOST_ASSERT(p >= cbegin());
1344       BOOST_ASSERT(p <= cend());
1345       return static_cast<size_type>(p - this->cbegin());
1346    }
1347 
1348    /**
1349    * **Returns**: A reference to the `n`th element in the devector.
1350    *
1351    * **Throws**: `out_of_range`, if `n >= size()`.
1352    *
1353    * **Complexity**: Constant.
1354    */
1355    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1356       reference at(size_type n)
1357    {
1358       if (size() <= n)
1359             throw_out_of_range("devector::at out of range");
1360       return (*this)[n];
1361    }
1362 
1363    /**
1364    * **Returns**: A constant reference to the `n`th element in the devector.
1365    *
1366    * **Throws**: `out_of_range`, if `n >= size()`.
1367    *
1368    * **Complexity**: Constant.
1369    */
1370    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1371       const_reference at(size_type n) const
1372    {
1373       if (size() <= n)
1374             throw_out_of_range("devector::at out of range");
1375       return (*this)[n];
1376    }
1377 
1378    /**
1379    * **Returns**: A reference to the first element in the devector.
1380    *
1381    * **Precondition**: `!empty()`.
1382    *
1383    * **Complexity**: Constant.
1384    */
1385    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1386       reference front() BOOST_NOEXCEPT
1387    {
1388       BOOST_ASSERT(!empty());
1389 
1390       return m_.buffer[m_.front_idx];
1391    }
1392 
1393    /**
1394    * **Returns**: A constant reference to the first element in the devector.
1395    *
1396    * **Precondition**: `!empty()`.
1397    *
1398    * **Complexity**: Constant.
1399    */
1400    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1401       const_reference front() const BOOST_NOEXCEPT
1402    {
1403       BOOST_ASSERT(!empty());
1404 
1405       return m_.buffer[m_.front_idx];
1406    }
1407 
1408    /**
1409    * **Returns**: A reference to the last element in the devector.
1410    *
1411    * **Precondition**: `!empty()`.
1412    *
1413    * **Complexity**: Constant.
1414    */
1415    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1416       reference back() BOOST_NOEXCEPT
1417    {
1418       BOOST_ASSERT(!empty());
1419 
1420       return m_.buffer[m_.back_idx - 1u];
1421    }
1422 
1423    /**
1424    * **Returns**: A constant reference to the last element in the devector.
1425    *
1426    * **Precondition**: `!empty()`.
1427    *
1428    * **Complexity**: Constant.
1429    */
1430    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1431       const_reference back() const BOOST_NOEXCEPT
1432    {
1433       BOOST_ASSERT(!empty());
1434 
1435       return m_.buffer[m_.back_idx - 1u];
1436    }
1437 
1438    /**
1439    * **Returns**: A pointer to the underlying array serving as element storage.
1440    * The range `[data(); data() + size())` is always valid. For a non-empty devector,
1441    * `data() == &front()`.
1442    *
1443    * **Complexity**: Constant.
1444    */
1445    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1446       T* data() BOOST_NOEXCEPT
1447    {
1448       return boost::movelib::to_raw_pointer(m_.buffer) + m_.front_idx;
1449    }
1450 
1451    /**
1452    * **Returns**: A constant pointer to the underlying array serving as element storage.
1453    * The range `[data(); data() + size())` is always valid. For a non-empty devector,
1454    * `data() == &front()`.
1455    *
1456    * **Complexity**: Constant.
1457    */
1458    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1459       const T* data() const BOOST_NOEXCEPT
1460    {
1461       return boost::movelib::to_raw_pointer(m_.buffer) + m_.front_idx;
1462    }
1463 
1464    // modifiers:
1465 
1466    /**
1467    * **Effects**: Pushes a new element to the front of the devector.
1468    * The element is constructed in-place, using the perfect forwarded `args`
1469    * as constructor arguments. Invalidates iterators if reallocation is needed.
1470    * (`front_free_capacity() == 0`)
1471    *
1472    * **Requires**: `T` shall be [EmplaceConstructible] from `args` and [MoveInsertable] into `*this`.
1473    *
1474    * **Exceptions**: Strong exception guarantee.
1475    *
1476    * **Complexity**: Amortized constant in the size of `*this`.
1477    * (Constant, if `front_free_capacity() > 0`)
1478    *
1479    * [EmplaceConstructible]: http://en.cppreference.com/w/cpp/concept/EmplaceConstructible
1480    * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
1481    */
1482    #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1483    template <class... Args>
1484    reference emplace_front(Args&&... args)
1485    {
1486       if (BOOST_LIKELY(front_free_capacity() != 0)) // fast path
1487       {
1488          pointer const p = m_.buffer + (m_.front_idx - 1u);
1489          this->alloc_construct(p, boost::forward<Args>(args)...);
1490          --m_.front_idx;
1491          BOOST_ASSERT(invariants_ok());
1492          return *p;
1493       }
1494       else
1495       {
1496          typedef dtl::insert_emplace_proxy<allocator_type, Args...> proxy_t;
1497          return *this->insert_range_slow_path(this->begin(), 1, proxy_t(::boost::forward<Args>(args)...));
1498       }
1499    }
1500 
1501    #else //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1502 
1503    #define BOOST_CONTAINER_DEVECTOR_EMPLACE_FRONT(N) \
1504    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1505    inline reference emplace_front(BOOST_MOVE_UREF##N)\
1506    {\
1507       if (front_free_capacity())\
1508       {\
1509          pointer const p = m_.buffer + (m_.front_idx - 1u);\
1510          this->alloc_construct(p BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
1511          --m_.front_idx;\
1512          return *p;\
1513       }\
1514       else\
1515       {\
1516          typedef dtl::insert_emplace_proxy_arg##N<allocator_type BOOST_MOVE_I##N BOOST_MOVE_TARG##N> proxy_t;\
1517          return *this->insert_range_slow_path(this->begin(), 1, proxy_t(BOOST_MOVE_FWD##N));\
1518       }\
1519    }\
1520    //
1521    BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_DEVECTOR_EMPLACE_FRONT)
1522    #undef BOOST_CONTAINER_DEVECTOR_EMPLACE_FRONT
1523 
1524    #endif
1525 
1526    #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1527    /**
1528    * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
1529    *
1530    * **Effects**: Pushes the copy of `x` to the front of the devector.
1531    * Invalidates iterators if reallocation is needed.
1532    * (`front_free_capacity() == 0`)
1533    *
1534    * **Requires**: `T` shall be [CopyInsertable] into `*this`.
1535    *
1536    * **Exceptions**: Strong exception guarantee.
1537    *
1538    * **Complexity**: Amortized constant in the size of `*this`.
1539    * (Constant, if `front_free_capacity() > 0`)
1540    */
1541    void push_front(const T& x);
1542 
1543    /**
1544    * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
1545    *
1546    * **Effects**: Move constructs a new element at the front of the devector using `x`.
1547    * Invalidates iterators if reallocation is needed.
1548    * (`front_free_capacity() == 0`)
1549    *
1550    * **Requires**: `T` shall be [MoveInsertable] into `*this`.
1551    *
1552    * **Exceptions**: Strong exception guarantee, not regarding the state of `x`.
1553    *
1554    * **Complexity**: Amortized constant in the size of `*this`.
1555    * (Constant, if `front_free_capacity() > 0`)
1556    */
1557    void push_front(T&& x);
1558 
1559    #else
1560    BOOST_MOVE_CONVERSION_AWARE_CATCH(push_front, T, void, priv_push_front)
1561    #endif
1562 
1563    /**
1564    * **Effects**: Removes the first element of `*this`.
1565    *
1566    * **Precondition**: `!empty()`.
1567    *
1568    * **Postcondition**: `front_free_capacity()` is incremented by 1.
1569    *
1570    * **Complexity**: Constant.
1571    */
1572    void pop_front() BOOST_NOEXCEPT
1573    {
1574       BOOST_ASSERT(!empty());
1575       allocator_traits_type::destroy(get_allocator_ref(), boost::movelib::to_raw_pointer(m_.buffer + m_.front_idx));
1576       ++m_.front_idx;
1577       BOOST_ASSERT(invariants_ok());
1578    }
1579 
1580    /**
1581    * **Effects**: Pushes a new element to the back of the devector.
1582    * The element is constructed in-place, using the perfect forwarded `args`
1583    * as constructor arguments. Invalidates iterators if reallocation is needed.
1584    * (`back_free_capacity() == 0`)
1585    *
1586    * **Requires**: `T` shall be [EmplaceConstructible] from `args` and [MoveInsertable] into `*this`,
1587    * and [MoveAssignable].
1588    *
1589    * **Exceptions**: Strong exception guarantee.
1590    *
1591    * **Complexity**: Amortized constant in the size of `*this`.
1592    * (Constant, if `back_free_capacity() > 0`)
1593    *
1594    * [EmplaceConstructible]: http://en.cppreference.com/w/cpp/concept/EmplaceConstructible
1595    * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
1596    * [MoveAssignable]: http://en.cppreference.com/w/cpp/concept/MoveAssignable
1597    */
1598    #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1599    template <class... Args>
1600    inline reference emplace_back(Args&&... args)
1601    {
1602       if (BOOST_LIKELY(this->back_free_capacity() != 0)){
1603          pointer const p = m_.buffer + m_.back_idx;
1604          this->alloc_construct(p, boost::forward<Args>(args)...);
1605          ++m_.back_idx;
1606          BOOST_ASSERT(invariants_ok());
1607          return *p;
1608       }
1609       else {
1610          typedef dtl::insert_emplace_proxy<allocator_type, Args...> proxy_t;
1611          return *this->insert_range_slow_path(this->end(), 1, proxy_t(::boost::forward<Args>(args)...));
1612       }
1613    }
1614 
1615    #else //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1616 
1617    #define BOOST_CONTAINER_DEVECTOR_EMPLACE_BACK(N) \
1618    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1619    inline reference emplace_back(BOOST_MOVE_UREF##N)\
1620    {\
1621       if (this->back_free_capacity()){\
1622          pointer const p = m_.buffer + m_.back_idx;\
1623          this->alloc_construct(p BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
1624          ++m_.back_idx;\
1625          return *p;\
1626       }\
1627       else {\
1628          typedef dtl::insert_emplace_proxy_arg##N<allocator_type BOOST_MOVE_I##N BOOST_MOVE_TARG##N> proxy_t;\
1629          return *this->insert_range_slow_path(this->end(), 1, proxy_t(BOOST_MOVE_FWD##N));\
1630       }\
1631    }\
1632    //
1633    BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_DEVECTOR_EMPLACE_BACK)
1634    #undef BOOST_CONTAINER_DEVECTOR_EMPLACE_BACK
1635 
1636    #endif    //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1637 
1638 
1639    #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1640    /**
1641    * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
1642    *
1643    * **Effects**: Pushes the copy of `x` to the back of the devector.
1644    * Invalidates iterators if reallocation is needed.
1645    * (`back_free_capacity() == 0`)
1646    *
1647    * **Requires**: `T` shall be [CopyInsertable] into `*this`.
1648    *
1649    * **Exceptions**: Strong exception guarantee.
1650    *
1651    * **Complexity**: Amortized constant in the size of `*this`.
1652    * (Constant, if `back_free_capacity() > 0`)
1653    */
1654    void push_back(const T& x);
1655 
1656    /**
1657    * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
1658    *
1659    * **Effects**: Move constructs a new element at the back of the devector using `x`.
1660    * Invalidates iterators if reallocation is needed.
1661    * (`back_free_capacity() == 0`)
1662    *
1663    * **Requires**: `T` shall be [MoveInsertable] into `*this`.
1664    *
1665    * **Exceptions**: Strong exception guarantee, not regarding the state of `x`.
1666    *
1667    * **Complexity**: Amortized constant in the size of `*this`.
1668    * (Constant, if `back_free_capacity() > 0`)
1669    */
1670    void push_back(T&& x);
1671 
1672    #else
1673    BOOST_MOVE_CONVERSION_AWARE_CATCH(push_back, T, void, priv_push_back)
1674    #endif
1675 
1676    /**
1677    * **Effects**: Removes the last element of `*this`.
1678    *
1679    * **Precondition**: `!empty()`.
1680    *
1681    * **Postcondition**: `back_free_capacity()` is incremented by 1.
1682    *
1683    * **Complexity**: Constant.
1684    */
1685    void pop_back() BOOST_NOEXCEPT
1686    {
1687       BOOST_ASSERT(! empty());
1688       --m_.back_idx;
1689       allocator_traits_type::destroy(get_allocator_ref(), boost::movelib::to_raw_pointer(m_.buffer + m_.back_idx));
1690       BOOST_ASSERT(invariants_ok());
1691    }
1692 
1693    /**
1694    * **Effects**: Constructs a new element before the element pointed by `position`.
1695    * The element is constructed in-place, using the perfect forwarded `args`
1696    * as constructor arguments. Invalidates iterators if reallocation is needed.
1697    *
1698    * **Requires**: `T` shall be [EmplaceConstructible], and [MoveInsertable] into `*this`,
1699    * and [MoveAssignable].
1700    *
1701    * **Returns**: Iterator pointing to the newly constructed element.
1702    *
1703    * **Exceptions**: Strong exception guarantee if `T` is `NothrowConstructible`
1704    * and `NothrowAssignable`, Basic exception guarantee otherwise.
1705    *
1706    * **Complexity**: Linear in the size of `*this`.
1707    *
1708    * [EmplaceConstructible]: http://en.cppreference.com/w/cpp/concept/EmplaceConstructible
1709    * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
1710    * [MoveAssignable]: http://en.cppreference.com/w/cpp/concept/MoveAssignable
1711    */
1712    #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1713    template <class... Args>
1714    iterator emplace(const_iterator position, Args&&... args)
1715    {
1716       BOOST_ASSERT(position >= begin());
1717       BOOST_ASSERT(position <= end());
1718       typedef dtl::insert_emplace_proxy<allocator_type, Args...> proxy_t;
1719       bool prefer_move_back;
1720       if (position == end()){
1721          if(back_free_capacity()) // fast path
1722          {
1723             pointer const p = m_.buffer + m_.back_idx;
1724             this->alloc_construct(p, boost::forward<Args>(args)...);
1725             ++m_.back_idx;
1726             return iterator(p);
1727          }
1728          prefer_move_back = true;
1729       }
1730       else if (position == begin()){
1731          if(front_free_capacity()) // secondary fast path
1732          {
1733             pointer const p = m_.buffer + (m_.front_idx - 1);
1734             this->alloc_construct(p, boost::forward<Args>(args)...);
1735             --m_.front_idx;
1736             return iterator(p);
1737          }
1738          prefer_move_back = false;
1739       }
1740       else{
1741          iterator nonconst_pos = unconst_iterator(position);
1742          prefer_move_back = should_move_back(position);
1743 
1744          if(prefer_move_back){
1745             if(back_free_capacity()){
1746                boost::container::expand_forward_and_insert_nonempty_middle_alloc
1747                   ( get_allocator_ref()
1748                   , boost::movelib::to_raw_pointer(nonconst_pos)
1749                   , this->priv_raw_end()
1750                   , 1, proxy_t(::boost::forward<Args>(args)...));
1751                ++m_.back_idx;
1752                return nonconst_pos;
1753             }
1754          }
1755          else{
1756             if (front_free_capacity()){
1757                boost::container::expand_backward_and_insert_nonempty_middle_alloc
1758                (get_allocator_ref()
1759                   , this->priv_raw_begin()
1760                   , boost::movelib::to_raw_pointer(nonconst_pos)
1761                   , 1, proxy_t(::boost::forward<Args>(args)...));
1762                --m_.front_idx;
1763                return --nonconst_pos;
1764             }
1765          }
1766       }
1767       return this->insert_range_slow_path(position, 1, proxy_t(::boost::forward<Args>(args)...));
1768    }
1769 
1770    #else //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1771 
1772    #define BOOST_CONTAINER_DEVECTOR_EMPLACE(N) \
1773    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1774    iterator emplace(const_iterator position BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
1775    {\
1776       BOOST_ASSERT(position >= begin());\
1777       BOOST_ASSERT(position <= end());\
1778       typedef dtl::insert_emplace_proxy_arg##N<allocator_type  BOOST_MOVE_I##N BOOST_MOVE_TARG##N> proxy_t;\
1779       bool prefer_move_back;\
1780       if (position == end()){\
1781          if(back_free_capacity())\
1782          {\
1783             pointer const p = m_.buffer + m_.back_idx;\
1784             this->alloc_construct(p BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
1785             ++m_.back_idx;\
1786             return iterator(p);\
1787          }\
1788          prefer_move_back = true;\
1789       }\
1790       else if (position == begin()){\
1791          if(front_free_capacity())\
1792          {\
1793             pointer const p = m_.buffer + (m_.front_idx - 1);\
1794             this->alloc_construct(p BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
1795             --m_.front_idx;\
1796             return iterator(p);\
1797          }\
1798          prefer_move_back = false;\
1799       }\
1800       else{\
1801          iterator nonconst_pos = unconst_iterator(position);\
1802          prefer_move_back = should_move_back(position);\
1803          \
1804          if(prefer_move_back){\
1805             if(back_free_capacity()){\
1806                boost::container::expand_forward_and_insert_nonempty_middle_alloc\
1807                   ( get_allocator_ref()\
1808                   , boost::movelib::to_raw_pointer(nonconst_pos)\
1809                   , this->priv_raw_end()\
1810                   , 1, proxy_t(BOOST_MOVE_FWD##N));\
1811                ++m_.back_idx;\
1812                return nonconst_pos;\
1813             }\
1814          }\
1815          else{\
1816             if (front_free_capacity()){\
1817                boost::container::expand_backward_and_insert_nonempty_middle_alloc\
1818                (get_allocator_ref()\
1819                   , this->priv_raw_begin()\
1820                   , boost::movelib::to_raw_pointer(nonconst_pos)\
1821                   , 1, proxy_t(BOOST_MOVE_FWD##N));\
1822                --m_.front_idx;\
1823                return --nonconst_pos;\
1824             }\
1825          }\
1826       }\
1827       return this->insert_range_slow_path(position, 1, proxy_t(BOOST_MOVE_FWD##N));\
1828    }\
1829    //
1830    BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_DEVECTOR_EMPLACE)
1831    #undef BOOST_CONTAINER_DEVECTOR_EMPLACE
1832 
1833    #endif    //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1834 
1835 
1836    #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1837    /**
1838    * **Effects**: Copy constructs a new element before the element pointed by `position`,
1839    * using `x` as constructor argument. Invalidates iterators if reallocation is needed.
1840    *
1841    * **Requires**: `T` shall be [CopyInsertable] into `*this` and and [CopyAssignable].
1842    *
1843    * **Returns**: Iterator pointing to the newly constructed element.
1844    *
1845    * **Exceptions**: Strong exception guarantee if `T` is `NothrowConstructible`
1846    * and `NothrowAssignable`, Basic exception guarantee otherwise.
1847    *
1848    * **Complexity**: Linear in the size of `*this`.
1849    *
1850    * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
1851    * [CopyAssignable]: http://en.cppreference.com/w/cpp/concept/CopyAssignable
1852    */
1853    iterator insert(const_iterator position, const T &x);
1854 
1855    /**
1856    * **Effects**: Move constructs a new element before the element pointed by `position`,
1857    * using `x` as constructor argument. Invalidates iterators if reallocation is needed.
1858    *
1859    * **Requires**: `T` shall be [MoveInsertable] into `*this` and and [CopyAssignable].
1860    *
1861    * **Returns**: Iterator pointing to the newly constructed element.
1862    *
1863    * **Exceptions**: Strong exception guarantee if `T` is `NothrowConstructible`
1864    * and `NothrowAssignable` (not regarding the state of `x`),
1865    * Basic exception guarantee otherwise.
1866    *
1867    * **Complexity**: Linear in the size of `*this`.
1868    *
1869    * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
1870    * [CopyAssignable]: http://en.cppreference.com/w/cpp/concept/CopyAssignable
1871    */
1872    iterator insert(const_iterator position, T &&x);
1873    #else
1874    BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, T, iterator, priv_insert, const_iterator, const_iterator)
1875    #endif
1876 
1877    /**
1878    * **Effects**: Copy constructs `n` elements before the element pointed by `position`,
1879    * using `x` as constructor argument. Invalidates iterators if reallocation is needed.
1880    *
1881    * **Requires**: `T` shall be [CopyInsertable] into `*this` and and [CopyAssignable].
1882    *
1883    * **Returns**: Iterator pointing to the first inserted element, or `position`, if `n` is zero.
1884    *
1885    * **Exceptions**: Strong exception guarantee if `T` is `NothrowConstructible`
1886    * and `NothrowAssignable`, Basic exception guarantee otherwise.
1887    *
1888    * **Complexity**: Linear in the size of `*this` and `n`.
1889    *
1890    * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
1891    * [CopyAssignable]: http://en.cppreference.com/w/cpp/concept/CopyAssignable
1892    */
1893    inline iterator insert(const_iterator position, size_type n, const T& x)
1894    {
1895       cvalue_iterator first(x, n);
1896       cvalue_iterator last = first + n;
1897       return this->insert_range(position, first, last);
1898    }
1899 
1900    /**
1901    * **Effects**: Copy constructs elements before the element pointed by position
1902    * using each element in the range pointed by `first` and `last` as constructor arguments.
1903    * Invalidates iterators if reallocation is needed.
1904    *
1905    * **Requires**: `T` shall be [EmplaceConstructible] into `*this` from `*first`. If the specified iterator
1906    * does not meet the forward iterator requirements, `T` shall also be [MoveInsertable] into `*this`
1907    * and [MoveAssignable].
1908    *
1909    * **Precondition**: `first` and `last` are not iterators into `*this`.
1910    *
1911    * **Returns**: Iterator pointing to the first inserted element, or `position`, if `first == last`.
1912    *
1913    * **Complexity**: Linear in the size of `*this` and `N` (where `N` is the distance between `first` and `last`).
1914    * Makes only `N` calls to the constructor of `T` and no reallocations if iterators `first` and `last`
1915    * are of forward, bidirectional, or random access categories. It makes 2N calls to the copy constructor of `T`
1916    * and `O(log(N)) reallocations if they are just input iterators.
1917    *
1918    * **Exceptions**: Strong exception guarantee if `T` is `NothrowConstructible`
1919    * and `NothrowAssignable`, Basic exception guarantee otherwise.
1920    *
1921    * **Remarks**: Each iterator in the range `[first,last)` shall be dereferenced exactly once,
1922    * unless an exception is thrown.
1923    *
1924    * [EmplaceConstructible]: http://en.cppreference.com/w/cpp/concept/EmplaceConstructible
1925    * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
1926    * [MoveAssignable]: http://en.cppreference.com/w/cpp/concept/MoveAssignable
1927    */
1928    template <class InputIterator>
1929    iterator insert(const_iterator position, InputIterator first, InputIterator last
1930       //Input iterators
1931       BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_or
1932             < void
1933             BOOST_MOVE_I dtl::is_convertible<InputIterator BOOST_MOVE_I size_type>
1934             BOOST_MOVE_I dtl::is_not_input_iterator<InputIterator>
1935             >::type * = 0)
1936       )
1937    {
1938       if (position == end())
1939       {
1940          size_type insert_index = size();
1941 
1942          for (; first != last; ++first)
1943          {
1944             this->emplace_back(*first);
1945          }
1946 
1947          return begin() + insert_index;
1948       }
1949       else
1950       {
1951          const size_type insert_index = static_cast<size_type>(position - this->cbegin());
1952          const size_type old_size = static_cast<size_type>(this->size());
1953 
1954          for (; first != last; ++first) {
1955             this->emplace_back(*first);
1956          }
1957          iterator rit (this->begin() + insert_index);
1958          boost::movelib::rotate_gcd(rit, this->begin() + old_size, this->begin() + this->size());
1959          return rit;
1960       }
1961    }
1962 
1963    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1964 
1965    template <class ForwardIterator>
1966    inline iterator insert(const_iterator position, ForwardIterator first, ForwardIterator last
1967       //Other iterators
1968       BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_or
1969             < void
1970             BOOST_MOVE_I dtl::is_convertible<ForwardIterator BOOST_MOVE_I size_type>
1971             BOOST_MOVE_I dtl::is_input_iterator<ForwardIterator>
1972             >::type * = 0)
1973       )
1974    {
1975       return insert_range(position, first, last);
1976    }
1977 
1978    #endif // ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1979 
1980    #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1981    /** **Equivalent to**: `insert(position, il.begin(), il.end())` */
1982    inline iterator insert(const_iterator position, std::initializer_list<T> il)
1983    {
1984       return this->insert(position, il.begin(), il.end());
1985    }
1986    #endif
1987 
1988    /**
1989    * [MoveAssignable]: http://en.cppreference.com/w/cpp/concept/MoveAssignable
1990    *
1991    * **Effects**: Destroys the element pointed by `position` and removes it from the devector.
1992    * Invalidates iterators.
1993    *
1994    * **Requires**: `T` shall be [MoveAssignable].
1995    *
1996    * **Precondition**: `position` must be in the range of `[begin(), end())`.
1997    *
1998    * **Returns**: Iterator pointing to the element immediately following the erased element
1999    * prior to its erasure. If no such element exists, `end()` is returned.
2000    *
2001    * **Exceptions**: Strong exception guarantee if `T` is `NothrowAssignable`,
2002    * Basic exception guarantee otherwise.
2003    *
2004    * **Complexity**: Linear in half the size of `*this`.
2005    */
2006    iterator erase(const_iterator position)
2007    {
2008       return erase(position, position + 1);
2009    }
2010 
2011    /**
2012    * [MoveAssignable]: http://en.cppreference.com/w/cpp/concept/MoveAssignable
2013    *
2014    * **Effects**: Destroys the range `[first,last)` and removes it from the devector.
2015    * Invalidates iterators.
2016    *
2017    * **Requires**: `T` shall be [MoveAssignable].
2018    *
2019    * **Precondition**: `[first,last)` must be in the range of `[begin(), end())`.
2020    *
2021    * **Returns**: Iterator pointing to the element pointed to by `last` prior to any elements
2022    * being erased. If no such element exists, `end()` is returned.
2023    *
2024    * **Exceptions**: Strong exception guarantee if `T` is `NothrowAssignable`,
2025    * Basic exception guarantee otherwise.
2026    *
2027    * **Complexity**: Linear in half the size of `*this`
2028    * plus the distance between `first` and `last`.
2029    */
2030    iterator erase(const_iterator first, const_iterator last)
2031    {
2032       iterator nc_first = unconst_iterator(first);
2033       iterator nc_last  = unconst_iterator(last);
2034       return erase(nc_first, nc_last);
2035    }
2036 
2037    /**
2038    * [MoveAssignable]: http://en.cppreference.com/w/cpp/concept/MoveAssignable
2039    *
2040    * **Effects**: Destroys the range `[first,last)` and removes it from the devector.
2041    * Invalidates iterators.
2042    *
2043    * **Requires**: `T` shall be [MoveAssignable].
2044    *
2045    * **Precondition**: `[first,last)` must be in the range of `[begin(), end())`.
2046    *
2047    * **Returns**: Iterator pointing to the element pointed to by `last` prior to any elements
2048    * being erased. If no such element exists, `end()` is returned.
2049    *
2050    * **Exceptions**: Strong exception guarantee if `T` is `NothrowAssignable`,
2051    * Basic exception guarantee otherwise.
2052    *
2053    * **Complexity**: Linear in half the size of `*this`.
2054    */
2055    iterator erase(iterator first, iterator last)
2056    {
2057       size_type front_distance = pos_to_index(last);
2058       size_type back_distance  = size_type(end() - first);
2059       size_type n = boost::container::iterator_udistance(first, last);
2060 
2061       if (front_distance < back_distance)
2062       {
2063             // move n to the right
2064             boost::container::move_backward(begin(), first, last);
2065 
2066             for (iterator i = begin(); i != begin() + n; ++i)
2067             {
2068                allocator_traits_type::destroy(get_allocator_ref(), boost::movelib::to_raw_pointer(i));
2069             }
2070             //n is always less than max stored_size_type
2071             m_.set_front_idx(m_.front_idx + n);
2072 
2073             BOOST_ASSERT(invariants_ok());
2074             return last;
2075       }
2076       else {
2077             // move n to the left
2078             boost::container::move(last, end(), first);
2079 
2080             for (iterator i = end() - n; i != end(); ++i)
2081             {
2082                allocator_traits_type::destroy(get_allocator_ref(), boost::movelib::to_raw_pointer(i));
2083             }
2084             //n is always less than max stored_size_type
2085             m_.set_back_idx(m_.back_idx - n);
2086 
2087             BOOST_ASSERT(invariants_ok());
2088             return first;
2089       }
2090    }
2091 
2092    /**
2093    * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
2094    *
2095    * **Effects**: exchanges the contents of `*this` and `b`.
2096    *
2097    * **Requires**: instances of `T` must be swappable by unqualified call of `swap`
2098    * and `T` must be [MoveInsertable] into `*this`.
2099    *
2100    * **Precondition**: The allocators should allow propagation or should compare equal.
2101    *
2102    * **Exceptions**: Basic exceptions guarantee if not `noexcept`.
2103    *
2104    * **Complexity**: Constant.
2105    */
2106    void swap(devector& b)
2107       BOOST_NOEXCEPT_IF( allocator_traits_type::propagate_on_container_swap::value
2108                                  || allocator_traits_type::is_always_equal::value)
2109    {
2110       BOOST_CONSTEXPR_OR_CONST bool propagate_alloc = allocator_traits_type::propagate_on_container_swap::value;
2111       BOOST_ASSERT(propagate_alloc || get_allocator_ref() == b.get_allocator_ref()); // else it's undefined behavior
2112 
2113       swap_big_big(*this, b);
2114 
2115       // swap indices
2116       boost::adl_move_swap(m_.front_idx, b.m_.front_idx);
2117       boost::adl_move_swap(m_.back_idx, b.m_.back_idx);
2118 
2119       //And now swap the allocator
2120       dtl::swap_alloc(this->get_allocator_ref(), b.get_allocator_ref(), dtl::bool_<propagate_alloc>());
2121 
2122       BOOST_ASSERT(   invariants_ok());
2123       BOOST_ASSERT(b.invariants_ok());
2124    }
2125 
2126    /**
2127    * **Effects**: Destroys all elements in the devector.
2128    * Invalidates all references, pointers and iterators to the
2129    * elements of the devector.
2130    *
2131    * **Postcondition**: `empty() && front_free_capacity() == 0
2132    * && back_free_capacity() == old capacity`.
2133    *
2134    * **Complexity**: Linear in the size of `*this`.
2135    *
2136    * **Remarks**: Does not free memory.
2137    */
2138    void clear() BOOST_NOEXCEPT
2139    {
2140       destroy_elements(begin(), end());
2141       m_.front_idx = m_.back_idx = 0;
2142    }
2143 
2144    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
2145       friend bool operator==(const devector& x, const devector& y)
2146    {   return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin());   }
2147 
2148    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
2149       friend bool operator!=(const devector& x, const devector& y)
2150    {   return !(x == y); }
2151 
2152    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
2153       friend bool operator< (const devector& x, const devector& y)
2154    {   return boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());   }
2155 
2156    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
2157       friend bool operator>(const devector& x, const devector& y)
2158    {   return y < x;   }
2159 
2160    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
2161       friend bool operator<=(const devector& x, const devector& y)
2162    {   return !(y < x);   }
2163 
2164    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
2165       friend bool operator>=(const devector& x, const devector& y)
2166    {   return !(x < y);   }
2167 
2168    inline friend void swap(devector& x, devector& y)
2169       BOOST_NOEXCEPT_IF( allocator_traits_type::propagate_on_container_swap::value
2170                                  || allocator_traits_type::is_always_equal::value)
2171    {   x.swap(y);   }
2172 
2173    private:
2174 
2175    void priv_move_assign(BOOST_RV_REF(devector) x, dtl::bool_<true> /*steal_resources*/)
2176    {
2177       this->clear();
2178       this->deallocate_buffer();
2179 
2180       //Move allocator if needed
2181       dtl::bool_<allocator_traits_type::
2182          propagate_on_container_move_assignment::value> flag;
2183       dtl::move_alloc(this->get_allocator_ref(), x.get_allocator_ref(), flag);
2184 
2185       m_.capacity = x.m_.capacity;
2186       m_.buffer = x.m_.buffer;
2187       m_.front_idx = x.m_.front_idx;
2188       m_.back_idx = x.m_.back_idx;
2189 
2190       // leave x in valid state
2191       x.m_.capacity = 0u;
2192       x.m_.buffer = pointer();
2193       x.m_.back_idx = x.m_.front_idx = 0;
2194    }
2195 
2196    void priv_move_assign(BOOST_RV_REF(devector) x, dtl::bool_<false> /*steal_resources*/)
2197    {
2198       //We can't guarantee a compile-time equal allocator or propagation so fallback to runtime
2199       //Resources can be transferred if both allocators are equal
2200       if (get_allocator_ref() == x.get_allocator_ref()) {
2201          this->priv_move_assign(boost::move(x), dtl::true_());
2202       }
2203       else {
2204          // We can't steal memory.
2205          move_iterator<iterator> xbegin = boost::make_move_iterator(x.begin());
2206          move_iterator<iterator> xend = boost::make_move_iterator(x.end());
2207 
2208          //Move allocator if needed
2209          dtl::bool_<allocator_traits_type::
2210             propagate_on_container_move_assignment::value> flag;
2211          dtl::move_alloc(this->get_allocator_ref(), x.get_allocator_ref(), flag);
2212 
2213          if (m_.capacity >= x.size()) {
2214             overwrite_buffer(xbegin, xend);
2215          }
2216          else {
2217             allocate_and_copy_range(xbegin, xend);
2218          }
2219       }
2220    }
2221 
2222    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
2223    size_type pos_to_index(const_iterator i) const 
2224    {
2225       return static_cast<size_type>(i - cbegin());
2226    }
2227 
2228    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
2229    bool should_move_back(const_iterator i) const 
2230    {
2231       return static_cast<size_type>(this->pos_to_index(i)) >= this->size()/2u;
2232    }
2233 
2234    inline static iterator unconst_iterator(const_iterator i)
2235    {
2236       return boost::intrusive::pointer_traits<pointer>::const_cast_from(i);
2237    }
2238 
2239    inline size_type front_capacity() const
2240    {
2241       return m_.back_idx;
2242    }
2243 
2244    inline size_type back_capacity() const
2245    {
2246       return size_type(m_.capacity - m_.front_idx);
2247    }
2248 
2249    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
2250 
2251    inline T* priv_raw_begin() BOOST_NOEXCEPT
2252    {   return boost::movelib::to_raw_pointer(m_.buffer) + m_.front_idx;   }
2253 
2254    inline T* priv_raw_end() BOOST_NOEXCEPT
2255    {   return boost::movelib::to_raw_pointer(m_.buffer) + m_.back_idx;    }
2256 
2257 
2258    template <class U>
2259    inline void priv_push_front(BOOST_FWD_REF(U) u)
2260    {
2261       this->emplace_front(boost::forward<U>(u));
2262    }
2263 
2264    template <class U>
2265    inline void priv_push_back(BOOST_FWD_REF(U) u)
2266    {
2267       this->emplace_back(boost::forward<U>(u));
2268    }
2269 
2270    template <class U>
2271    inline iterator priv_insert(const_iterator pos, BOOST_FWD_REF(U) u)
2272    {
2273       return this->emplace(pos, boost::forward<U>(u));
2274    }
2275 
2276    // allocator_type wrappers
2277 
2278    inline allocator_type& get_allocator_ref() BOOST_NOEXCEPT
2279    {
2280       return static_cast<allocator_type&>(m_);
2281    }
2282 
2283    inline const allocator_type& get_allocator_ref() const BOOST_NOEXCEPT
2284    {
2285       return static_cast<const allocator_type&>(m_);
2286    }
2287 
2288    pointer allocate(size_type capacity)
2289    {
2290       pointer const p = impl::do_allocate(get_allocator_ref(), capacity);
2291       #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
2292       ++m_.capacity_alloc_count;
2293       #endif // BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
2294       return p;
2295    }
2296 
2297    void destroy_elements(pointer begin, pointer end)
2298    {
2299       for (; begin != end; ++begin)
2300       {
2301          allocator_traits_type::destroy(get_allocator_ref(), boost::movelib::to_raw_pointer(begin));
2302       }
2303    }
2304 
2305    void deallocate_buffer()
2306    {
2307       if (m_.buffer)
2308       {
2309          allocator_traits_type::deallocate(get_allocator_ref(), m_.buffer, m_.capacity);
2310       }
2311    }
2312 
2313    #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
2314    template <typename... Args>
2315    inline void alloc_construct(pointer dst, Args&&... args)
2316    {
2317       allocator_traits_type::construct(
2318             get_allocator_ref(),
2319             boost::movelib::to_raw_pointer(dst),
2320             boost::forward<Args>(args)...
2321       );
2322    }
2323 
2324    template <typename... Args>
2325    void construct_n(pointer buffer, size_type n, Args&&... args)
2326    {
2327       detail::construction_guard<allocator_type> ctr_guard(buffer, get_allocator_ref());
2328       guarded_construct_n(buffer, n, ctr_guard, boost::forward<Args>(args)...);
2329       ctr_guard.release();
2330    }
2331 
2332    template <typename... Args>
2333    void guarded_construct_n(pointer buffer, size_type n, detail::construction_guard<allocator_type>& ctr_guard, Args&&... args)
2334    {
2335       for (size_type i = 0; i < n; ++i) {
2336          this->alloc_construct(buffer + i, boost::forward<Args>(args)...);
2337          ctr_guard.extend();
2338       }
2339    }
2340 
2341    #else //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
2342 
2343    #define BOOST_CONTAINER_DEVECTOR_ALLOC_CONSTRUCT(N) \
2344    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
2345    inline void alloc_construct(pointer dst BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
2346    {\
2347       allocator_traits_type::construct(\
2348             get_allocator_ref(), boost::movelib::to_raw_pointer(dst) BOOST_MOVE_I##N BOOST_MOVE_FWD##N );\
2349    }\
2350    \
2351    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
2352    void construct_n(pointer buffer, size_type n BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
2353    {\
2354       detail::construction_guard<allocator_type> ctr_guard(buffer, get_allocator_ref());\
2355       guarded_construct_n(buffer, n, ctr_guard BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
2356       ctr_guard.release();\
2357    }\
2358    \
2359    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
2360    void guarded_construct_n(pointer buffer, size_type n, detail::construction_guard<allocator_type>& ctr_guard BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
2361    {\
2362       for (size_type i = 0; i < n; ++i) {\
2363             this->alloc_construct(buffer + i BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
2364             ctr_guard.extend();\
2365       }\
2366    }
2367    //
2368    BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_DEVECTOR_ALLOC_CONSTRUCT)
2369    #undef BOOST_CONTAINER_DEVECTOR_ALLOC_CONSTRUCT
2370 
2371    #endif    //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
2372 
2373    size_type calculate_new_capacity(size_type requested_capacity)
2374    {
2375       size_type max = allocator_traits_type::max_size(this->get_allocator_ref());
2376       (clamp_by_stored_size_type)(max, stored_size_type());
2377       const size_type remaining_additional_cap = max - size_type(m_.capacity);
2378       const size_type min_additional_cap = requested_capacity - size_type(m_.capacity);
2379       if ( remaining_additional_cap < min_additional_cap )
2380             boost::container::throw_length_error("devector: get_next_capacity, max size exceeded");
2381 
2382       return growth_factor_type()( size_type(m_.capacity), min_additional_cap, max);
2383    }
2384 
2385    void buffer_move_or_copy(pointer dst)
2386    {
2387       detail::construction_guard<allocator_type> guard(dst, get_allocator_ref());
2388 
2389       buffer_move_or_copy(dst, guard);
2390 
2391       guard.release();
2392    }
2393 
2394    void buffer_move_or_copy(pointer dst, detail::construction_guard<allocator_type>& guard)
2395    {
2396       opt_move_or_copy(begin(), end(), dst, guard);
2397 
2398       destroy_elements(data(), data() + size());
2399       deallocate_buffer();
2400    }
2401 
2402    template <typename Guard>
2403    void opt_move_or_copy(pointer begin, pointer end, pointer dst, Guard& guard)
2404    {
2405       // if trivial copy and default allocator, memcpy
2406       boost::container::uninitialized_move_alloc(get_allocator_ref(), begin, end, dst);
2407       guard.extend();
2408    }
2409 
2410    #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
2411 
2412    template <typename... Args>
2413    void resize_impl(size_type sz, Args&&... args)
2414    {
2415       const size_type old_sz = this->size();
2416       if (sz > old_sz)
2417       {
2418          const size_type n = sz - old_sz;
2419 
2420          if (sz <= m_.capacity)
2421          {
2422             //Construct at back
2423             const size_type bfc = this->back_free_capacity();
2424             const size_type b = n < bfc ? n : bfc;
2425             construct_n(m_.buffer + m_.back_idx, b, boost::forward<Args>(args)...);
2426             m_.set_back_idx(m_.back_idx + b);
2427 
2428             //Construct remaining at front
2429             const size_type f = n - b;
2430             construct_n(m_.buffer + m_.front_idx - f, f, boost::forward<Args>(args)...);
2431             m_.set_front_idx(m_.front_idx - f);
2432          }
2433          else
2434          {
2435             resize_back_slow_path(sz, n, boost::forward<Args>(args)...);
2436          }
2437       }
2438       else
2439       {
2440          const size_type n = old_sz - sz;
2441          const size_type new_bidx = m_.back_idx - n;
2442          destroy_elements(m_.buffer + new_bidx, m_.buffer + m_.back_idx);
2443          m_.set_back_idx(new_bidx);
2444       }
2445    }
2446 
2447    template <typename... Args>
2448    void resize_front_impl(size_type sz , Args&&... args)
2449    {
2450       const size_type old_sz = this->size();
2451       if (sz > old_sz)
2452       {
2453          const size_type n = sz - old_sz;
2454 
2455          if (sz <= this->front_capacity())
2456          {
2457             construct_n(m_.buffer + m_.front_idx - n, n, boost::forward<Args>(args)...);
2458             m_.set_front_idx(m_.front_idx - n);
2459          }
2460          else
2461          {
2462             resize_front_slow_path(sz, n, boost::forward<Args>(args)...);
2463          }
2464       }
2465       else {
2466          const size_type n = old_sz - sz;
2467          const size_type new_fidx = m_.front_idx + n;
2468          destroy_elements(m_.buffer + m_.front_idx, m_.buffer + new_fidx);
2469          m_.set_front_idx(new_fidx);
2470       }
2471    }
2472 
2473    template <typename... Args>
2474    void resize_front_slow_path(size_type sz, size_type n, Args&&... args)
2475    {
2476       const size_type new_capacity = calculate_new_capacity(sz + back_free_capacity());
2477       pointer new_buffer = allocate(new_capacity);
2478       allocation_guard new_buffer_guard(new_buffer, new_capacity, get_allocator_ref());
2479 
2480       const size_type old_sz = this->size();
2481       const size_type new_old_elem_index = new_capacity - old_sz;
2482       const size_type new_elem_index = new_old_elem_index - n;
2483 
2484       detail::construction_guard<allocator_type> guard(new_buffer + new_elem_index, get_allocator_ref());
2485       guarded_construct_n(new_buffer + new_elem_index, n, guard, boost::forward<Args>(args)...);
2486 
2487       buffer_move_or_copy(new_buffer + new_old_elem_index, guard);
2488 
2489       guard.release();
2490       new_buffer_guard.release();
2491 
2492       m_.buffer = new_buffer;
2493       m_.set_capacity(new_capacity);
2494       m_.set_front_idx(new_elem_index);
2495       m_.set_back_idx(new_elem_index + old_sz + n);
2496    }
2497 
2498    template <typename... Args>
2499    void resize_back_impl(size_type sz, Args&&... args)
2500    {
2501       const size_type old_sz = this->size();
2502       if (sz > old_sz)
2503       {
2504          const size_type n = sz - old_sz;
2505 
2506          if (sz <= this->back_capacity())
2507          {
2508             construct_n(m_.buffer + m_.back_idx, n, boost::forward<Args>(args)...);
2509             m_.set_back_idx(m_.back_idx + n);
2510          }
2511          else
2512          {
2513             resize_back_slow_path(sz, n, boost::forward<Args>(args)...);
2514          }
2515       }
2516       else
2517       {
2518          const size_type n = old_sz - sz;
2519          const size_type new_bidx = m_.back_idx - n;
2520          destroy_elements(m_.buffer + new_bidx, m_.buffer + m_.back_idx);
2521          m_.set_back_idx(new_bidx);
2522       }
2523    }
2524 
2525    template <typename... Args>
2526    void resize_back_slow_path(size_type sz, size_type n, Args&&... args)
2527    {
2528       const size_type new_capacity = calculate_new_capacity(sz + front_free_capacity());
2529       pointer new_buffer = allocate(new_capacity);
2530       allocation_guard new_buffer_guard(new_buffer, new_capacity, get_allocator_ref());
2531 
2532       detail::construction_guard<allocator_type> guard(new_buffer + m_.back_idx, get_allocator_ref());
2533       guarded_construct_n(new_buffer + m_.back_idx, n, guard, boost::forward<Args>(args)...);
2534 
2535       buffer_move_or_copy(new_buffer + m_.front_idx);
2536 
2537       guard.release();
2538       new_buffer_guard.release();
2539 
2540       m_.buffer = new_buffer;
2541       m_.set_capacity(new_capacity);
2542       m_.set_back_idx(m_.back_idx + n);
2543    }
2544 
2545    #else //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
2546 
2547    #define BOOST_CONTAINER_DEVECTOR_SLOW_PATH(N) \
2548    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
2549    void resize_front_impl(size_type sz BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
2550    {\
2551       if (sz > size())\
2552       {\
2553          const size_type n = sz - size();\
2554          if (sz <= front_capacity()){\
2555             construct_n(m_.buffer + m_.front_idx - n, n BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
2556             m_.set_front_idx(m_.front_idx - n);\
2557          }\
2558          else\
2559          {\
2560             resize_front_slow_path(sz, n BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
2561          }\
2562       }\
2563       else {\
2564          while (this->size() > sz)\
2565          {\
2566             this->pop_front();\
2567          }\
2568       }\
2569    }\
2570    \
2571    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
2572    void resize_front_slow_path(size_type sz, size_type n BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
2573    {\
2574       const size_type new_capacity = calculate_new_capacity(sz + back_free_capacity());\
2575       pointer new_buffer = allocate(new_capacity);\
2576       allocation_guard new_buffer_guard(new_buffer, new_capacity, get_allocator_ref());\
2577    \
2578       const size_type new_old_elem_index = new_capacity - size();\
2579       const size_type new_elem_index = new_old_elem_index - n;\
2580    \
2581       detail::construction_guard<allocator_type> guard(new_buffer + new_elem_index, get_allocator_ref());\
2582       guarded_construct_n(new_buffer + new_elem_index, n, guard BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
2583    \
2584       buffer_move_or_copy(new_buffer + new_old_elem_index, guard);\
2585    \
2586       guard.release();\
2587       new_buffer_guard.release();\
2588       m_.buffer = new_buffer;\
2589       m_.set_capacity(new_capacity);\
2590       m_.set_back_idx(new_old_elem_index + m_.back_idx - m_.front_idx);\
2591       m_.set_front_idx(new_elem_index);\
2592    }\
2593    \
2594    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
2595    void resize_back_impl(size_type sz BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
2596    {\
2597       if (sz > size())\
2598       {\
2599          const size_type n = sz - size();\
2600       \
2601          if (sz <= back_capacity())\
2602          {\
2603             construct_n(m_.buffer + m_.back_idx, n BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
2604             m_.set_back_idx(m_.back_idx + n);\
2605          }\
2606          else\
2607          {\
2608             resize_back_slow_path(sz, n BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
2609          }\
2610       }\
2611       else\
2612       {\
2613          while (size() > sz)\
2614          {\
2615             pop_back();\
2616          }\
2617       }\
2618    }\
2619    \
2620    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
2621    void resize_back_slow_path(size_type sz, size_type n BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
2622    {\
2623       const size_type new_capacity = calculate_new_capacity(sz + front_free_capacity());\
2624       pointer new_buffer = allocate(new_capacity);\
2625       allocation_guard new_buffer_guard(new_buffer, new_capacity, get_allocator_ref());\
2626    \
2627       detail::construction_guard<allocator_type> guard(new_buffer + m_.back_idx, get_allocator_ref());\
2628       guarded_construct_n(new_buffer + m_.back_idx, n, guard BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
2629    \
2630       buffer_move_or_copy(new_buffer + m_.front_idx);\
2631    \
2632       guard.release();\
2633       new_buffer_guard.release();\
2634    \
2635       m_.buffer = new_buffer;\
2636       m_.set_capacity(new_capacity);\
2637       m_.set_back_idx(m_.back_idx + n);\
2638    }\
2639    \
2640    //
2641    BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_DEVECTOR_SLOW_PATH)
2642    #undef BOOST_CONTAINER_DEVECTOR_SLOW_PATH
2643 
2644    #endif    //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
2645 
2646    void reallocate_at(size_type new_capacity, size_type buffer_offset)
2647    {
2648       pointer new_buffer = allocate(new_capacity);
2649       {
2650          allocation_guard new_buffer_guard(new_buffer, new_capacity, get_allocator_ref());
2651          boost::container::uninitialized_move_alloc(get_allocator_ref(), this->begin(), this->end(), new_buffer + buffer_offset);
2652          new_buffer_guard.release();
2653       }
2654       destroy_elements(m_.buffer + m_.front_idx, m_.buffer + m_.back_idx);
2655       deallocate_buffer();
2656 
2657       m_.buffer = new_buffer;
2658       //Safe cast, allocate() will handle stored_size_type overflow
2659       m_.set_capacity(new_capacity);
2660       m_.set_back_idx(size_type(m_.back_idx - m_.front_idx) + buffer_offset);
2661       m_.set_front_idx(buffer_offset);
2662 
2663       BOOST_ASSERT(invariants_ok());
2664    }
2665 
2666    template <typename ForwardIterator>
2667    iterator insert_range(const_iterator position, ForwardIterator first, ForwardIterator last)
2668    {
2669       BOOST_ASSERT(position >= begin());
2670       BOOST_ASSERT(position <= end());
2671       typedef dtl::insert_range_proxy<allocator_type, ForwardIterator> proxy_t;
2672 
2673       size_type const n = boost::container::iterator_udistance(first, last);
2674       bool prefer_move_back;
2675       if (BOOST_UNLIKELY(!n)) {
2676          return begin() + size_type(position - cbegin());
2677       }
2678       else if (position == end()) {
2679          if(back_free_capacity() >= n) // fast path
2680          {
2681             iterator r(this->end());
2682             boost::container::uninitialized_copy_alloc(get_allocator_ref(), first, last, this->priv_raw_end());
2683             m_.set_back_idx(m_.back_idx + n);
2684             return r;
2685          }
2686          prefer_move_back = true;
2687       }
2688       else if (position == begin()) {
2689          if(front_free_capacity() >= n) {// secondary fast path
2690             boost::container::uninitialized_copy_alloc(get_allocator_ref(), first, last, this->priv_raw_begin() - n);
2691             m_.set_front_idx(m_.front_idx - n);
2692             return begin();
2693          }
2694          prefer_move_back = false;
2695       }
2696       else{
2697          iterator nonconst_pos = unconst_iterator(position);
2698          prefer_move_back = should_move_back(position);
2699 
2700          if(prefer_move_back){
2701             if(back_free_capacity() >= n){
2702                boost::container::expand_forward_and_insert_nonempty_middle_alloc
2703                   ( get_allocator_ref()
2704                   , boost::movelib::to_raw_pointer(nonconst_pos)
2705                   , this->priv_raw_end()
2706                   , n, proxy_t(first));
2707                m_.set_back_idx(m_.back_idx + n);
2708                return nonconst_pos;
2709             }
2710          }
2711          else{
2712             if (front_free_capacity() >= n){
2713                boost::container::expand_backward_and_insert_nonempty_middle_alloc
2714                   ( get_allocator_ref()
2715                   , this->priv_raw_begin()
2716                   , boost::movelib::to_raw_pointer(nonconst_pos)
2717                   , n, proxy_t(first));
2718                m_.set_front_idx(m_.front_idx - n);
2719                return (nonconst_pos -= n);
2720             }
2721          }
2722       }
2723       return this->insert_range_slow_path(position, n, proxy_t(first));
2724    }
2725 
2726    template <class InsertionProxy>
2727    BOOST_CONTAINER_NOINLINE iterator insert_range_slow_path
2728       (const_iterator p, const size_type n, const InsertionProxy proxy)
2729    {
2730       size_type const back_free_cap = back_free_capacity();
2731       size_type const front_free_cap = front_free_capacity();
2732       size_type const free_cap = front_free_cap + back_free_cap;
2733       size_type const index = size_type(p - cbegin());
2734 
2735       size_type const cap = m_.capacity;
2736       //Test if enough free memory would be left
2737       if (free_cap >= n && (free_cap - n) >= cap/devector_min_free_fraction) {
2738          size_type const old_size = this->size();
2739          T* const raw_pos = const_cast<T*>(boost::movelib::to_raw_pointer(p));
2740          size_type const new_size = old_size + n;
2741          size_type const new_front_idx = (cap - new_size) / 2u;
2742 
2743          T* const raw_beg = this->priv_raw_begin();
2744          T* const new_raw_beg = raw_beg - std::ptrdiff_t(m_.front_idx - new_front_idx);
2745          m_.back_idx = 0u;
2746          m_.front_idx = 0u;
2747          boost::container::expand_backward_forward_and_insert_alloc
2748             (raw_beg, old_size, new_raw_beg, raw_pos, n, proxy, get_allocator_ref());
2749          m_.set_front_idx(new_front_idx);
2750          m_.set_back_idx(new_front_idx + new_size);
2751       }
2752       else {
2753          // reallocate
2754          const size_type new_capacity = calculate_new_capacity(m_.capacity + n);
2755          pointer new_buffer = allocate(new_capacity);
2756 
2757          // guard allocation
2758          allocation_guard new_buffer_guard(new_buffer, new_capacity, get_allocator_ref());
2759 
2760          size_type const old_size = this->size();
2761          const size_type new_front_index = (new_capacity - old_size - n) / 2u;
2762 
2763          T* const raw_pos = const_cast<T*>(boost::movelib::to_raw_pointer(p));
2764          T* const raw_new_start = const_cast<T*>(boost::movelib::to_raw_pointer(new_buffer)) + new_front_index;
2765 
2766          boost::container::uninitialized_move_and_insert_alloc
2767             (get_allocator_ref(), this->priv_raw_begin(), raw_pos, this->priv_raw_end(), raw_new_start, n, proxy);
2768          new_buffer_guard.release();
2769 
2770          // cleanup
2771          destroy_elements(begin(), end());
2772          deallocate_buffer();
2773 
2774          // rebind members
2775          m_.set_capacity(new_capacity);
2776          m_.buffer = new_buffer;
2777          m_.set_back_idx(new_front_index + old_size + n);
2778          m_.set_front_idx(new_front_index);
2779       }
2780       return begin() + index;
2781    }
2782 
2783 
2784    template <typename Iterator>
2785    void construct_from_range(Iterator begin, Iterator end)
2786    {
2787       allocation_guard buffer_guard(m_.buffer, m_.capacity, get_allocator_ref());
2788       boost::container::uninitialized_copy_alloc(get_allocator_ref(), begin, end, m_.buffer);
2789       buffer_guard.release();
2790    }
2791 
2792    template <typename ForwardIterator>
2793    void allocate_and_copy_range(ForwardIterator first, ForwardIterator last)
2794    {
2795       size_type n = boost::container::iterator_udistance(first, last);
2796 
2797       pointer new_buffer = n ? allocate(n) : pointer();
2798       allocation_guard new_buffer_guard(new_buffer, n, get_allocator_ref());
2799       boost::container::uninitialized_copy_alloc(get_allocator_ref(), first, last, new_buffer);
2800       destroy_elements(begin(), end());
2801       deallocate_buffer();
2802 
2803       m_.set_capacity(n);
2804       m_.buffer = new_buffer;
2805       m_.front_idx = 0;
2806       m_.set_back_idx(n);
2807 
2808       new_buffer_guard.release();
2809    }
2810 
2811    static void swap_big_big(devector& a, devector& b) BOOST_NOEXCEPT
2812    {
2813       boost::adl_move_swap(a.m_.capacity, b.m_.capacity);
2814       boost::adl_move_swap(a.m_.buffer, b.m_.buffer);
2815    }
2816 
2817    template <typename ForwardIterator>
2818    void overwrite_buffer_impl(ForwardIterator first, ForwardIterator last, dtl::true_)
2819    {
2820       const size_type n = boost::container::iterator_udistance(first, last);
2821 
2822       BOOST_ASSERT(m_.capacity >= n);
2823       boost::container::uninitialized_copy_alloc_n
2824             ( get_allocator_ref(), first
2825             , n, boost::movelib::to_raw_pointer(m_.buffer));
2826       m_.front_idx = 0;
2827       m_.set_back_idx(n);
2828    }
2829 
2830    template <typename InputIterator>
2831    InputIterator overwrite_buffer_impl(InputIterator first, InputIterator last, dtl::false_)
2832    {
2833       pointer pos = m_.buffer;
2834       detail::construction_guard<allocator_type> front_guard(pos, get_allocator_ref());
2835 
2836       while (first != last && pos != begin()) {
2837          this->alloc_construct(pos++, *first++);
2838          front_guard.extend();
2839       }
2840 
2841       while (first != last && pos != end()) {
2842          *pos++ = *first++;
2843       }
2844 
2845       detail::construction_guard<allocator_type> back_guard(pos, get_allocator_ref());
2846 
2847       iterator capacity_end = m_.buffer + m_.capacity;
2848       while (first != last && pos != capacity_end) {
2849          this->alloc_construct(pos++, *first++);
2850          back_guard.extend();
2851       }
2852 
2853       pointer destroy_after = dtl::min_value(dtl::max_value(begin(), pos), end());
2854       destroy_elements(destroy_after, end());
2855 
2856       front_guard.release();
2857       back_guard.release();
2858 
2859       m_.front_idx = 0;
2860       m_.set_back_idx(pos_to_index(pos));
2861       return first;
2862    }
2863 
2864    template <typename ForwardIterator>
2865    inline void overwrite_buffer(ForwardIterator first, ForwardIterator last)
2866    {
2867       this->overwrite_buffer_impl(first, last, 
2868             dtl::bool_<dtl::is_trivially_destructible<T>::value>());
2869    }
2870 
2871    bool invariants_ok()
2872    {
2873       return  (! m_.capacity || m_.buffer )
2874               && m_.front_idx <= m_.back_idx
2875               && m_.back_idx <= m_.capacity;
2876    }
2877 
2878    struct impl : allocator_type
2879    {
2880       BOOST_MOVABLE_BUT_NOT_COPYABLE(impl)
2881 
2882       public:
2883       allocator_type &get_al()
2884       {   return *this;   }
2885 
2886       static pointer do_allocate(allocator_type &a, size_type cap)
2887       {
2888          if (cap) {
2889             //First detect overflow on smaller stored_size_types
2890             if (cap > stored_size_type(-1)){
2891                   boost::container::throw_length_error("get_next_capacity, allocator's max size reached");
2892             }
2893             return allocator_traits_type::allocate(a, cap);
2894          }
2895          else {
2896             return pointer();
2897          }
2898       }
2899 
2900       impl()
2901          : allocator_type(), buffer(), front_idx(), back_idx(), capacity()
2902          #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
2903          , capacity_alloc_count(0)
2904          #endif
2905       {}
2906 
2907       explicit impl(const allocator_type &a)
2908          : allocator_type(a), buffer(), front_idx(), back_idx(), capacity()
2909          #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
2910          , capacity_alloc_count(0)
2911          #endif
2912       {}
2913 
2914       impl(reserve_uninitialized_t, const allocator_type& a, size_type c)
2915          : allocator_type(a), buffer(do_allocate(get_al(), c) )
2916          //static cast sizes, as the allocation function will take care of overflows
2917          , front_idx(static_cast<stored_size_type>(0u))
2918          , back_idx(static_cast<stored_size_type>(c))
2919          , capacity(static_cast<stored_size_type>(c))
2920          #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
2921          , capacity_alloc_count(size_type(buffer != pointer()))
2922          #endif
2923       {}
2924 
2925       impl(reserve_only_tag_t, const allocator_type &a, size_type const ffc, size_type const bfc)
2926          : allocator_type(a), buffer(do_allocate(get_al(), ffc+bfc) )
2927          //static cast sizes, as the allocation function will take care of overflows
2928          , front_idx(static_cast<stored_size_type>(ffc))
2929          , back_idx(static_cast<stored_size_type>(ffc))
2930          , capacity(static_cast<stored_size_type>(ffc + bfc))
2931          #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
2932          , capacity_alloc_count(size_type(buffer != pointer()))
2933          #endif
2934       {}
2935 
2936       impl(reserve_only_tag_t, const allocator_type &a, size_type const c)
2937          : allocator_type(a), buffer(do_allocate(get_al(), c) )
2938          //static cast sizes, as the allocation function will take care of overflows
2939          , front_idx(static_cast<stored_size_type>(c/2u))
2940          , back_idx(static_cast<stored_size_type>(c/2u))
2941          , capacity(static_cast<stored_size_type>(c))
2942          #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
2943          , capacity_alloc_count(size_type(buffer != pointer()))
2944          #endif
2945       {}
2946 
2947       impl(review_implementation_t, const allocator_type &a, pointer p, size_type fi, size_type bi, size_type c)
2948          : allocator_type(a), buffer(p)
2949          //static cast sizes, as the allocation function will take care of overflows
2950          , front_idx(static_cast<stored_size_type>(fi))
2951          , back_idx(static_cast<stored_size_type>(bi))
2952          , capacity(static_cast<stored_size_type>(c))
2953          #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
2954          , capacity_alloc_count(0)
2955          #endif
2956       {}
2957 
2958       impl(BOOST_RV_REF(impl) m)
2959          : allocator_type(BOOST_MOVE_BASE(allocator_type, m))
2960          , buffer(static_cast<impl&>(m).buffer)
2961          , front_idx(static_cast<impl&>(m).front_idx)
2962          , back_idx(static_cast<impl&>(m).back_idx)
2963          , capacity(static_cast<impl&>(m).capacity)
2964          #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
2965          , capacity_alloc_count(0)
2966          #endif
2967       {
2968          impl &i = static_cast<impl&>(m);
2969          // buffer is already acquired, reset rhs
2970          i.capacity = 0u;
2971          i.buffer = pointer();
2972          i.front_idx = 0;
2973          i.back_idx = 0;
2974       }
2975 
2976       inline void set_back_idx(size_type bi)
2977       {
2978          back_idx = static_cast<stored_size_type>(bi);
2979       }
2980 
2981       inline void set_front_idx(size_type fi)
2982       {
2983          front_idx = static_cast<stored_size_type>(fi);
2984       }
2985 
2986       inline void set_capacity(size_type c)
2987       {
2988          capacity = static_cast<stored_size_type>(c);
2989       }
2990 
2991       pointer           buffer;
2992       stored_size_type  front_idx;
2993       stored_size_type  back_idx;
2994       stored_size_type  capacity;
2995       #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
2996       size_type capacity_alloc_count;
2997       #endif
2998    } m_;
2999 
3000    #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
3001    public:
3002    void reset_alloc_stats()
3003    {
3004       m_.capacity_alloc_count = 0;
3005    }
3006 
3007    size_type get_alloc_count() const
3008    {
3009       return m_.capacity_alloc_count;
3010    }
3011 
3012    #endif // ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
3013 
3014    #endif // ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
3015 };
3016 
3017 }} // namespace boost::container
3018 
3019 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
3020 
3021 namespace boost {
3022 
3023 //!has_trivial_destructor_after_move<> == true_type
3024 //!specialization for optimizations
3025 template <class T, class Allocator, class Options>
3026 struct has_trivial_destructor_after_move<boost::container::devector<T, Allocator, Options> >
3027 {
3028     typedef typename boost::container::devector<T, Allocator, Options>::allocator_type allocator_type;
3029     typedef typename ::boost::container::allocator_traits<allocator_type>::pointer pointer;
3030     BOOST_STATIC_CONSTEXPR bool value =
3031       ::boost::has_trivial_destructor_after_move<allocator_type>::value &&
3032       ::boost::has_trivial_destructor_after_move<pointer>::value;
3033 };
3034 
3035 }
3036 
3037 #endif    //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
3038 
3039 #include <boost/container/detail/config_end.hpp>
3040 
3041 #endif // BOOST_CONTAINER_DEVECTOR_HPP