EIC code displayed by LXR master/​include/​boost/​container/​devector.hpp	Source navigation Diff markup Identifier search General search
	Version: master test Revert   Change

File indexing completed on 2025-01-18 09:30:16

 //////////////////////////////////////////////////////////////////////////////
 //
 // (C) Copyright Benedek Thaler 2015-2016
 // (C) Copyright Ion Gaztanaga 2019-2020. Distributed under the Boost
 // Software License, Version 1.0. (See accompanying file
 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
 //
 // See http://www.boost.org/libs/container for documentation.
 //
 //////////////////////////////////////////////////////////////////////////////
 
 #ifndef BOOST_CONTAINER_DEVECTOR_HPP
 #define BOOST_CONTAINER_DEVECTOR_HPP
 
 #include <boost/container/detail/config_begin.hpp>
 #include <boost/container/detail/workaround.hpp>
 
 #include <cstring> // memcpy
 
 #include <boost/assert.hpp>
 
 #include <boost/container/detail/copy_move_algo.hpp>
 #include <boost/container/new_allocator.hpp> //new_allocator
 #include <boost/container/allocator_traits.hpp> //allocator_traits
 #include <boost/container/detail/algorithm.hpp> //equal()
 #include <boost/container/throw_exception.hpp>
 #include <boost/container/options.hpp>
 
 #include <boost/container/detail/guards_dended.hpp>
 #include <boost/container/detail/iterator.hpp>
 #include <boost/container/detail/iterators.hpp>
 #include <boost/container/detail/destroyers.hpp>
 #include <boost/container/detail/min_max.hpp>
 #include <boost/container/detail/next_capacity.hpp>
 #include <boost/container/detail/alloc_helpers.hpp>
 #include <boost/container/detail/advanced_insert_int.hpp>
 
 // move
 #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
 #include <boost/move/detail/fwd_macros.hpp>
 #endif
 #include <boost/move/detail/move_helpers.hpp>
 #include <boost/move/adl_move_swap.hpp>
 #include <boost/move/iterator.hpp>
 #include <boost/move/traits.hpp>
 #include <boost/move/utility_core.hpp>
 #include <boost/move/detail/to_raw_pointer.hpp>
 #include <boost/move/algo/detail/merge.hpp>
 #include <boost/move/detail/force_ptr.hpp>
 
 //std
 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
 #include <initializer_list>    //for std::initializer_list
 #endif
 
 namespace boost {
 namespace container {
 
 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
 
 struct growth_factor_60;
 
 template<class Options, class AllocatorSizeType>
 struct get_devector_opt
 {
     typedef devector_opt< typename default_if_void<typename Options::growth_factor_type, growth_factor_60>::type
                         , typename default_if_void<typename Options::stored_size_type, AllocatorSizeType>::type
                         , default_if_zero<Options::free_fraction, relocate_on_90::value>::value
                         > type;
 };
 
 template<class AllocatorSizeType>
 struct get_devector_opt<void, AllocatorSizeType>
 {
     typedef devector_opt< growth_factor_60, AllocatorSizeType, relocate_on_90::value> type;
 };
 
 #endif    //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
 
 struct reserve_only_tag_t {};
 struct reserve_uninitialized_t {};
 struct review_implementation_t {};
 
 //struct unsafe_uninitialized_tag_t {};
 
 /**
  * A vector-like sequence container providing front and back operations
  * (e.g: `push_front`/`pop_front`/`push_back`/`pop_back`) with amortized constant complexity.
  *
  * Models the [SequenceContainer], [ReversibleContainer], and [AllocatorAwareContainer] concepts.
  *
  * **Requires**:
  *   - `T` shall be [MoveInsertable] into the devector.
  *   - `T` shall be [Erasable] from any `devector<T, allocator_type, GP>`.
  *   - `GrowthFactor`, and `Allocator` must model the concepts with the same names or be void.
  *
  * **Definition**: `T` is `NothrowConstructible` if it's either nothrow move constructible or
  * nothrow copy constructible.
  *
  * **Definition**: `T` is `NothrowAssignable` if it's either nothrow move assignable or
  * nothrow copy assignable.
  *
  * **Exceptions**: The exception specifications assume `T` is nothrow [Destructible].
  *
  * Most methods providing the strong exception guarantee assume `T` either has a move
  * constructor marked noexcept or is [CopyInsertable] into the devector. If it isn't true,
  * and the move constructor throws, the guarantee is waived and the effects are unspecified.
  *
  * In addition to the exceptions specified in the **Throws** clause, the following operations
  * of `T` can throw when any of the specified concept is required:
  *   - [DefaultInsertable][]: Default constructor
  *   - [MoveInsertable][]: Move constructor
  *   - [CopyInsertable][]: Copy constructor
  *   - [DefaultConstructible][]: Default constructor
  *   - [EmplaceConstructible][]: Constructor selected by the given arguments
  *   - [MoveAssignable][]: Move assignment operator
  *   - [CopyAssignable][]: Copy assignment operator
  *
  * Furthermore, not `noexcept` methods throws whatever the allocator throws
  * if memory allocation fails. Such methods also throw `length_error` if the capacity
  * exceeds `max_size()`.
  *
  * **Remark**: If a method invalidates some iterators, it also invalidates references
  * and pointers to the elements pointed by the invalidated iterators.
  *
  *! \tparam Options A type produced from \c boost::container::devector_options.
  *
  * [SequenceContainer]: http://en.cppreference.com/w/cpp/concept/SequenceContainer
  * [ReversibleContainer]: http://en.cppreference.com/w/cpp/concept/ReversibleContainer
  * [AllocatorAwareContainer]: http://en.cppreference.com/w/cpp/concept/AllocatorAwareContainer
  * [DefaultInsertable]: http://en.cppreference.com/w/cpp/concept/DefaultInsertable
  * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
  * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
  * [Erasable]: http://en.cppreference.com/w/cpp/concept/Erasable
  * [DefaultConstructible]: http://en.cppreference.com/w/cpp/concept/DefaultConstructible
  * [Destructible]: http://en.cppreference.com/w/cpp/concept/Destructible
  * [EmplaceConstructible]: http://en.cppreference.com/w/cpp/concept/EmplaceConstructible
  * [MoveAssignable]: http://en.cppreference.com/w/cpp/concept/MoveAssignable
  * [CopyAssignable]: http://en.cppreference.com/w/cpp/concept/CopyAssignable
  */
 template < typename T, class A BOOST_CONTAINER_DOCONLY(= void), class Options BOOST_CONTAINER_DOCONLY(= void)>
 class devector
 {
    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
    typedef boost::container::allocator_traits
       <typename real_allocator<T, A>::type>                                      allocator_traits_type;
    typedef typename allocator_traits_type::size_type                             alloc_size_type;
    typedef typename get_devector_opt<Options, alloc_size_type>::type             options_type;
    typedef typename options_type::growth_factor_type                             growth_factor_type;
    typedef typename options_type::stored_size_type                               stored_size_type;
    static const std::size_t devector_min_free_fraction =
       options_type::free_fraction;
 
    #endif // ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
 
    public:
    // Standard Interface Types:
    typedef T                                                                     value_type;
    typedef BOOST_CONTAINER_IMPDEF
       (typename real_allocator<T BOOST_MOVE_I A>::type)                          allocator_type;
    typedef allocator_type                                                        stored_allocator_type;
    typedef typename    allocator_traits<allocator_type>::pointer                 pointer;
    typedef typename    allocator_traits<allocator_type>::const_pointer           const_pointer;
    typedef typename    allocator_traits<allocator_type>::reference               reference;
    typedef typename    allocator_traits<allocator_type>::const_reference         const_reference;
    typedef typename    allocator_traits<allocator_type>::size_type               size_type;
    typedef typename    allocator_traits<allocator_type>::difference_type         difference_type;
    typedef pointer                                                               iterator;
    typedef const_pointer                                                         const_iterator;
    typedef BOOST_CONTAINER_IMPDEF
       (boost::container::reverse_iterator<iterator>)                             reverse_iterator;
    typedef BOOST_CONTAINER_IMPDEF
       (boost::container::reverse_iterator<const_iterator>)                       const_reverse_iterator;
 
    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
    private:
    BOOST_COPYABLE_AND_MOVABLE(devector)
 
    // Guard to deallocate buffer on exception
    typedef typename detail::allocation_guard<allocator_type> allocation_guard;
 
    // Random access pseudo iterator always yielding to the same result
    typedef constant_iterator<T> cvalue_iterator;
 
    static size_type to_internal_capacity(size_type desired_capacity)
    {
       const size_type rounder = devector_min_free_fraction - 2u;
       const size_type divisor = devector_min_free_fraction - 1u;
       size_type const nc = ((desired_capacity + rounder) / divisor) * devector_min_free_fraction;
       BOOST_ASSERT(desired_capacity <= (nc - nc / devector_min_free_fraction));
       return nc;
    }
 
    #endif // ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
 
    // Standard Interface
    public:
    // construct/copy/destroy
 
    /**
    * **Effects**: Constructs an empty devector.
    *
    * **Postcondition**: `empty() && front_free_capacity() == 0
    * && back_free_capacity() == 0`.
    *
    * **Complexity**: Constant.
    */
    devector() BOOST_NOEXCEPT
       : m_()
    {}
 
    /**
    * **Effects**: Constructs an empty devector, using the specified allocator.
    *
    * **Postcondition**: `empty() && front_free_capacity() == 0
    * && back_free_capacity() == 0`.
    *
    * **Complexity**: Constant.
    */
    explicit devector(const allocator_type& allocator) BOOST_NOEXCEPT
       : m_(allocator)
    {}
 
    /**
    * **Effects**: Constructs an empty devector, using the specified allocator
    * and reserves `n` slots as if `reserve(n)` was called.
    *
    * **Postcondition**: `empty() && capacity() >= n`.
    *
    * **Exceptions**: Strong exception guarantee.
    *
    * **Complexity**: Constant.
    */
    devector(size_type n, reserve_only_tag_t, const allocator_type& allocator = allocator_type())
       : m_(reserve_only_tag_t(), allocator, to_internal_capacity(n))
    {}
 
    /**
    * **Effects**: Constructs an empty devector, using the specified allocator
    * and reserves at least `front_free_cap + back_free_cap` slots as if `reserve_front(front_cap)` and
    * `reserve_back(back_cap)` was called.
    *
    * **Postcondition**: `empty() && front_free_capacity() >= front_free_cap
    * && back_free_capacity() >= back_free_cap`.
    *
    * **Exceptions**: Strong exception guarantee.
    *
    * **Complexity**: Constant.
    */
    devector(size_type front_free_cap, size_type back_free_cap, reserve_only_tag_t, const allocator_type& allocator = allocator_type())
       : m_(reserve_only_tag_t(), allocator, front_free_cap, back_free_cap)
    {}
 
    /**
    * [DefaultInsertable]: http://en.cppreference.com/w/cpp/concept/DefaultInsertable
    *
    * **Effects**: Constructs a devector with `n` value_initialized elements using the specified allocator.
    *
    * **Requires**: `T` shall be [DefaultInsertable] into `*this`.
    *
    * **Postcondition**: `size() == n`.
    *
    * **Exceptions**: Strong exception guarantee.
    *
    * **Complexity**: Linear in `n`.
    */
    explicit devector(size_type n, const allocator_type& allocator = allocator_type())
       : m_(reserve_uninitialized_t(), allocator, n)
    {
       allocation_guard buffer_guard(m_.buffer, m_.capacity, get_allocator_ref());
       boost::container::uninitialized_value_init_alloc_n(get_allocator_ref(), n, this->priv_raw_begin());
       buffer_guard.release();
       BOOST_ASSERT(invariants_ok());
    }
 
    /**
    * **Effects**: Constructs a devector with `n` default-initialized elements using the specified allocator.
    *
    * **Requires**: `T` shall be [DefaultInsertable] into `*this`.
    *
    * **Postcondition**: `size() == n`.
    *
    * **Exceptions**: Strong exception guarantee.
    *
    * **Complexity**: Linear in `n`.
    */
    explicit devector(size_type n, default_init_t, const allocator_type& allocator = allocator_type())
       : m_(reserve_uninitialized_t(), allocator, n)
    {
       allocation_guard buffer_guard(m_.buffer, m_.capacity, get_allocator_ref());
       boost::container::uninitialized_default_init_alloc_n(get_allocator_ref(), n, this->priv_raw_begin());
       buffer_guard.release();
       BOOST_ASSERT(invariants_ok());
    }
 
    /**
    * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
    *
    * **Effects**: Constructs a devector with `n` copies of `value`, using the specified allocator.
    *
    * **Requires**: `T` shall be [CopyInsertable] into `*this`.
    *
    * **Postcondition**: `size() == n`.
    *
    * **Exceptions**: Strong exception guarantee.
    *
    * **Complexity**: Linear in `n`.
    */
    devector(size_type n, const T& value, const allocator_type& allocator = allocator_type())
       : m_(reserve_uninitialized_t(), allocator, n)
    {
       construct_from_range(cvalue_iterator(value, n), cvalue_iterator());
       BOOST_ASSERT(invariants_ok());
    }
 
    /**
    * **Effects**: Constructs a devector equal to the range `[first,last)`, using the specified allocator.
    *
    * **Requires**: `T` shall be [EmplaceConstructible] into `*this` from `*first`. If the specified
    * iterator does not meet the forward iterator requirements, `T` shall also be [MoveInsertable]
    * into `*this`.
    *
    * **Postcondition**: `size() == boost::container::iterator_distance(first, last)
    *
    * **Exceptions**: Strong exception guarantee.
    *
    * **Complexity**: Makes only `N` calls to the copy constructor of `T` (where `N` is the distance between `first`
    * and `last`), at most one allocation and no reallocations if iterators first and last are of forward,
    * bidirectional, or random access categories. It makes `O(N)` calls to the copy constructor of `T`
    * and `O(log(N)) reallocations if they are just input iterators.
    *
    * **Remarks**: Each iterator in the range `[first,last)` shall be dereferenced exactly once,
    * unless an exception is thrown.
    *
    * [EmplaceConstructible]: http://en.cppreference.com/w/cpp/concept/EmplaceConstructible
    * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
    */
    template <class InputIterator>
    devector(InputIterator first, InputIterator last, const allocator_type& allocator = allocator_type()
       //Input iterators
       BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_or
             < void
             BOOST_MOVE_I dtl::is_convertible<InputIterator BOOST_MOVE_I size_type>
             BOOST_MOVE_I dtl::is_not_input_iterator<InputIterator>
             >::type * = 0)
       )
       : m_(allocator)
    {
       BOOST_CONTAINER_TRY{
          while (first != last) {
             this->emplace_back(*first++);
          }
          BOOST_ASSERT(invariants_ok());
       }
       BOOST_CONTAINER_CATCH(...){
          this->destroy_elements(m_.buffer + m_.front_idx, m_.buffer + m_.back_idx);
          this->deallocate_buffer();
       }
       BOOST_CONTAINER_CATCH_END
    }
 
    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
 
    template <class ForwardIterator>
    devector(ForwardIterator first, ForwardIterator last, const allocator_type& allocator = allocator_type()
       //Other iterators
       BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_or
             < void
             BOOST_MOVE_I dtl::is_convertible<ForwardIterator BOOST_MOVE_I size_type>
             BOOST_MOVE_I dtl::is_input_iterator<ForwardIterator>
             >::type * = 0)
       )
       : m_(reserve_uninitialized_t(), allocator, boost::container::iterator_udistance(first, last))
    {
       this->construct_from_range(first, last);
       BOOST_ASSERT(invariants_ok());
    }
 
    #endif // ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
 
    /**
    * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
    *
    * **Effects**: Copy constructs a devector.
    *
    * **Requires**: `T` shall be [CopyInsertable] into `*this`.
    *
    * **Postcondition**: `this->size() == x.size()`.
    *
    * **Exceptions**: Strong exception guarantee.
    *
    * **Complexity**: Linear in the size of `x`.
    */
    devector(const devector& x)
       : m_(reserve_uninitialized_t(), allocator_traits_type::select_on_container_copy_construction(x.get_allocator_ref()), x.size())
    {
       this->construct_from_range(x.begin(), x.end());
       BOOST_ASSERT(invariants_ok());
    }
 
    /**
    * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
    *
    * **Effects**: Copy constructs a devector, using the specified allocator.
    *
    * **Requires**: `T` shall be [CopyInsertable] into `*this`.
    *
    * **Postcondition**: `*this == x`.
    *
    * **Exceptions**: Strong exception guarantee.
    *
    * **Complexity**: Linear in the size of `x`.
    */
    devector(const devector& x, const allocator_type& allocator)
       : m_(reserve_uninitialized_t(), allocator, x.size())
    {
       this->construct_from_range(x.begin(), x.end());
       BOOST_ASSERT(invariants_ok());
    }
 
    /**
    * **Effects**: Moves `rhs`'s resources to `*this`.
    *
    * **Throws**: Nothing.
    *
    * **Postcondition**: *this has the same value `rhs` had before the operation.
    *                    `rhs` is left in an unspecified but valid state.
    *
    * **Exceptions**: Strong exception guarantee if not `noexcept`.
    *
    * **Complexity**: Constant.
    */
    devector(BOOST_RV_REF(devector) rhs) BOOST_NOEXCEPT_OR_NOTHROW
       : m_(::boost::move(rhs.m_))
    {
       BOOST_ASSERT(      invariants_ok());
       BOOST_ASSERT(rhs.invariants_ok());
    }
 
    /**
    * **Effects**: Moves `rhs`'s resources to `*this`, using the specified allocator.
    *
    * **Throws**: If allocation or T's move constructor throws.
    *
    * **Postcondition**: *this has the same value `rhs` had before the operation.
    *                    `rhs` is left in an unspecified but valid state.
    *
    * **Exceptions**: Strong exception guarantee if not `noexcept`.
    *
    * **Complexity**: Linear if allocator != rhs.get_allocator(), otherwise constant.
    */
    devector(BOOST_RV_REF(devector) rhs, const allocator_type& allocator)
       : m_(review_implementation_t(), allocator, rhs.m_.buffer, rhs.m_.front_idx, rhs.m_.back_idx, rhs.m_.capacity)
    {
       // TODO should move elems-by-elems if the two allocators differ
       // buffer is already acquired, reset rhs
       rhs.m_.capacity = 0u;
       rhs.m_.buffer = pointer();
       rhs.m_.front_idx = 0;
       rhs.m_.back_idx = 0;
       BOOST_ASSERT(      invariants_ok());
       BOOST_ASSERT(rhs.invariants_ok());
    }
 
    #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
    /**
    * **Equivalent to**: `devector(il.begin(), il.end(), allocator)`.
    */
    devector(const std::initializer_list<T>& il, const allocator_type& allocator = allocator_type())
       : m_(reserve_uninitialized_t(), allocator, il.size())
    {
       this->construct_from_range(il.begin(), il.end());
       BOOST_ASSERT(invariants_ok());
    }
    #endif
 
 /**
    * **Effects**: Destroys the devector. All stored values are destroyed and
    * used memory, if any, deallocated.
    *
    * **Complexity**: Linear in the size of `*this`.
    */
 ~devector() BOOST_NOEXCEPT
 {
    destroy_elements(m_.buffer + m_.front_idx, m_.buffer + m_.back_idx);
    deallocate_buffer();
 }
 
 /**
    * **Effects**: Copies elements of `x` to `*this`. Previously
    * held elements get copy assigned to or destroyed.
    *
    * **Requires**: `T` shall be [CopyInsertable] into `*this`.
    *
    * **Postcondition**: `this->size() == x.size()`, the elements of
    * `*this` are copies of elements in `x` in the same order.
    *
    * **Returns**: `*this`.
    *
    * **Exceptions**: Strong exception guarantee if `T` is `NothrowConstructible`
    * and the allocator is allowed to be propagated
    * ([propagate_on_container_copy_assignment] is true),
    * Basic exception guarantee otherwise.
    *
    * **Complexity**: Linear in the size of `x` and `*this`.
    *
    * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
    * [propagate_on_container_copy_assignment]: http://en.cppreference.com/w/cpp/memory/allocator_traits
    */
 
    BOOST_CONTAINER_FORCEINLINE devector& operator=(BOOST_COPY_ASSIGN_REF(devector) rhs)
    {
       const devector &x = rhs;
       if (this == &x) { return *this; } // skip self
 
       BOOST_IF_CONSTEXPR(allocator_traits_type::propagate_on_container_copy_assignment::value)
       {
             allocator_type &this_alloc = this->get_allocator_ref();
             const allocator_type &other_alloc = x.get_allocator_ref();
             if (this_alloc != other_alloc)
             {
                // new allocator cannot free existing storage
                this->clear();
                this->deallocate_buffer();
                m_.capacity = 0u;
                m_.buffer = pointer();
             }
 
             this_alloc = other_alloc;
       }
 
       size_type n = x.size();
       if (m_.capacity >= n)
       {
             this->overwrite_buffer(x.begin(), x.end());
       }
       else
       {
             this->allocate_and_copy_range(x.begin(), x.end());
       }
 
       BOOST_ASSERT(invariants_ok());
 
       return *this;
    }
 
    /**
    * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
    *
    * **Effects**: Moves elements of `x` to `*this`. Previously
    * held elements get move/copy assigned to or destroyed.
    *
    * **Requires**: `T` shall be [MoveInsertable] into `*this`.
    *
    * **Postcondition**: `x` is left in an unspecified but valid state.
    *
    * **Returns**: `*this`.
    *
    * **Exceptions**: Basic exception guarantee if not `noexcept`.
    *
    * **Complexity**: Constant if allocator_traits_type::
    *   propagate_on_container_move_assignment is true or
    *   this->get>allocator() == x.get_allocator(). Linear otherwise.
    */
    devector& operator=(BOOST_RV_REF(devector) x)
       BOOST_NOEXCEPT_IF(allocator_traits_type::propagate_on_container_move_assignment::value
                                  || allocator_traits_type::is_always_equal::value)
    {
       BOOST_CONSTEXPR_OR_CONST bool copy_alloc = allocator_traits_type::propagate_on_container_move_assignment::value;
 
       BOOST_IF_CONSTEXPR (copy_alloc || get_allocator_ref() == x.get_allocator_ref())
       {
          this->clear();
          this->deallocate_buffer();
 
          if (copy_alloc)
          {
             this->get_allocator_ref() = boost::move(x.get_allocator_ref());
          }
 
          m_.capacity = x.m_.capacity;
          m_.buffer = x.m_.buffer;
          m_.front_idx = x.m_.front_idx;
          m_.back_idx = x.m_.back_idx;
 
          // leave x in valid state
          x.m_.capacity = 0u;
          x.m_.buffer = pointer();
          x.m_.back_idx = x.m_.front_idx = 0;
       }
       else
       {
          // if the allocator shouldn't be copied and they do not compare equal
          // we can't steal memory.
 
          move_iterator<iterator> xbegin = boost::make_move_iterator(x.begin());
          move_iterator<iterator> xend = boost::make_move_iterator(x.end());
 
          if (copy_alloc)
          {
             get_allocator_ref() = boost::move(x.get_allocator_ref());
          }
 
          if (m_.capacity >= x.size())
          {
             overwrite_buffer(xbegin, xend);
          }
          else
          {
             allocate_and_copy_range(xbegin, xend);
          }
       }
 
       BOOST_ASSERT(invariants_ok());
 
       return *this;
    }
 
    #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
    /**
    * **Effects**: Copies elements of `il` to `*this`. Previously
    * held elements get copy assigned to or destroyed.
    *
    * **Requires**: `T` shall be [CopyInsertable] into `*this` and [CopyAssignable].
    *
    * **Postcondition**: `this->size() == il.size()`, the elements of
    * `*this` are copies of elements in `il` in the same order.
    *
    * **Exceptions**: Strong exception guarantee if `T` is nothrow copy assignable
    * from `T` and `NothrowConstructible`, Basic exception guarantee otherwise.
    *
    * **Returns**: `*this`.
    *
    * **Complexity**: Linear in the size of `il` and `*this`.
    *
    * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
    * [CopyAssignable]: http://en.cppreference.com/w/cpp/concept/CopyAssignable
    */
    BOOST_CONTAINER_FORCEINLINE devector& operator=(std::initializer_list<T> il)
    {
       this->assign(il.begin(), il.end());
       return *this;
    }
    #endif
 
    /**
    * **Effects**: Replaces elements of `*this` with a copy of `[first,last)`.
    * Previously held elements get copy assigned to or destroyed.
    *
    * **Requires**: `T` shall be [EmplaceConstructible] from `*first`. If the specified iterator
    * does not meet the forward iterator requirements, `T` shall be also [MoveInsertable] into `*this`.
    *
    * **Precondition**: `first` and `last` are not iterators into `*this`.
    *
    * **Postcondition**: `size() == N`, where `N` is the distance between `first` and `last`.
    *
    * **Exceptions**: Strong exception guarantee if `T` is nothrow copy assignable
    * from `*first` and `NothrowConstructible`, Basic exception guarantee otherwise.
    *
    * **Complexity**: Linear in the distance between `first` and `last`.
    * Makes a single reallocation at most if the iterators `first` and `last`
    * are of forward, bidirectional, or random access categories. It makes
    * `O(log(N))` reallocations if they are just input iterators.
    *
    * **Remarks**: Each iterator in the range `[first,last)` shall be dereferenced exactly once,
    * unless an exception is thrown.
    *
    * [EmplaceConstructible]: http://en.cppreference.com/w/cpp/concept/EmplaceConstructible
    * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
    */
    template <class InputIterator>
    void assign(InputIterator first, InputIterator last
       //Input iterators
       BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_or
             < void
             BOOST_MOVE_I dtl::is_convertible<InputIterator BOOST_MOVE_I size_type>
             BOOST_MOVE_I dtl::is_not_input_iterator<InputIterator>
             >::type * = 0)
       )
    {
       first = overwrite_buffer_impl(first, last, dtl::false_());
       while (first != last)
       {
          this->emplace_back(*first++);
       }
    }
 
    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
 
    template <class ForwardIterator>
    void assign(ForwardIterator first, ForwardIterator last
       //Other iterators
       BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_or
             < void
             BOOST_MOVE_I dtl::is_convertible<ForwardIterator BOOST_MOVE_I size_type>
             BOOST_MOVE_I dtl::is_input_iterator<ForwardIterator>
             >::type * = 0)
       )
    {
       const size_type n = boost::container::iterator_udistance(first, last);
 
       if (m_.capacity >= n)
       {
          overwrite_buffer(first, last);
       }
       else
       {
          allocate_and_copy_range(first, last);
       }
 
       BOOST_ASSERT(invariants_ok());
    }
 
    #endif // ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
 
    /**
     * **Effects**: Replaces elements of `*this` with `n` copies of `u`.
     * Previously held elements get copy assigned to or destroyed.
     *
     * **Requires**: `T` shall be [CopyInsertable] into `*this` and
     * [CopyAssignable].
     *
     * **Precondition**: `u` is not a reference into `*this`.
     *
     * **Postcondition**: `size() == n` and the elements of
     * `*this` are copies of `u`.
     *
     * **Exceptions**: Strong exception guarantee if `T` is nothrow copy assignable
     * from `u` and `NothrowConstructible`, Basic exception guarantee otherwise.
     *
     * **Complexity**: Linear in `n` and the size of `*this`.
     *
     * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
     * [CopyAssignable]: http://en.cppreference.com/w/cpp/concept/CopyAssignable
     */
    BOOST_CONTAINER_FORCEINLINE void assign(size_type n, const T& u)
    {
       cvalue_iterator first(u, n);
       cvalue_iterator last;
       this->assign(first, last);
    }
 
     #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
     /** **Equivalent to**: `assign(il.begin(), il.end())`. */
    BOOST_CONTAINER_FORCEINLINE void assign(std::initializer_list<T> il)
     {
          this->assign(il.begin(), il.end());
     }
     #endif
 
    /**
     * **Returns**: A copy of the allocator associated with the container.
     *
     * **Complexity**: Constant.
     */
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
     allocator_type get_allocator() const BOOST_NOEXCEPT
    {
       return static_cast<const allocator_type&>(m_);
    }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
     const allocator_type &get_stored_allocator() const BOOST_NOEXCEPT
    {
       return static_cast<const allocator_type&>(m_);
    }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
          allocator_type &get_stored_allocator() BOOST_NOEXCEPT
    {
       return static_cast<allocator_type&>(m_);
    }
 
    // iterators
 
    /**
     * **Returns**: A iterator pointing to the first element in the devector,
     * or the past the end iterator if the devector is empty.
     *
     * **Complexity**: Constant.
     */
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
          iterator begin() BOOST_NOEXCEPT
    {
       return m_.buffer + m_.front_idx;
    }
 
    /**
     * **Returns**: A constant iterator pointing to the first element in the devector,
     * or the past the end iterator if the devector is empty.
     *
     * **Complexity**: Constant.
     */
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
     const_iterator begin() const BOOST_NOEXCEPT
    {
       return m_.buffer + m_.front_idx;
    }
 
    /**
     * **Returns**: An iterator pointing past the last element of the container.
     *
     * **Complexity**: Constant.
     */
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
          iterator end() BOOST_NOEXCEPT
    {
       return m_.buffer + m_.back_idx;
    }
 
    /**
     * **Returns**: A constant iterator pointing past the last element of the container.
     *
     * **Complexity**: Constant.
     */
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
     const_iterator end() const BOOST_NOEXCEPT
    {
       return m_.buffer + m_.back_idx;
    }
 
    /**
     * **Returns**: A reverse iterator pointing to the first element in the reversed devector,
     * or the reverse past the end iterator if the devector is empty.
     *
     * **Complexity**: Constant.
     */
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
     reverse_iterator rbegin() BOOST_NOEXCEPT
    {
       return reverse_iterator(m_.buffer + m_.back_idx);
    }
 
    /**
     * **Returns**: A constant reverse iterator
     * pointing to the first element in the reversed devector,
     * or the reverse past the end iterator if the devector is empty.
     *
     * **Complexity**: Constant.
     */
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
     const_reverse_iterator rbegin() const BOOST_NOEXCEPT
    {
       return const_reverse_iterator(m_.buffer + m_.back_idx);
    }
 
    /**
     * **Returns**: A reverse iterator pointing past the last element in the
     * reversed container, or to the beginning of the reversed container if it's empty.
     *
     * **Complexity**: Constant.
     */
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
     reverse_iterator rend() BOOST_NOEXCEPT
    {
       return reverse_iterator(m_.buffer + m_.front_idx);
    }
 
    /**
     * **Returns**: A constant reverse iterator pointing past the last element in the
     * reversed container, or to the beginning of the reversed container if it's empty.
     *
     * **Complexity**: Constant.
     */
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
     const_reverse_iterator rend() const BOOST_NOEXCEPT
    {
       return const_reverse_iterator(m_.buffer + m_.front_idx);
    }
 
    /**
     * **Returns**: A constant iterator pointing to the first element in the devector,
     * or the past the end iterator if the devector is empty.
     *
     * **Complexity**: Constant.
     */
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
     const_iterator cbegin() const BOOST_NOEXCEPT
    {
       return m_.buffer + m_.front_idx;
    }
 
    /**
     * **Returns**: A constant iterator pointing past the last element of the container.
     *
     * **Complexity**: Constant.
     */
    const_iterator cend() const BOOST_NOEXCEPT
    {
       return m_.buffer + m_.back_idx;
    }
 
    /**
     * **Returns**: A constant reverse iterator
     * pointing to the first element in the reversed devector,
     * or the reverse past the end iterator if the devector is empty.
     *
     * **Complexity**: Constant.
     */
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
     const_reverse_iterator crbegin() const BOOST_NOEXCEPT
    {
       return const_reverse_iterator(m_.buffer + m_.back_idx);
    }
 
    /**
     * **Returns**: A constant reverse iterator pointing past the last element in the
     * reversed container, or to the beginning of the reversed container if it's empty.
     *
     * **Complexity**: Constant.
     */
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
     const_reverse_iterator crend() const BOOST_NOEXCEPT
    {
       return const_reverse_iterator(m_.buffer + m_.front_idx);
    }
 
    // capacity
 
    /**
     * **Returns**: True, if `size() == 0`, false otherwise.
     *
     * **Complexity**: Constant.
     */
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
     bool empty() const BOOST_NOEXCEPT
    {
       return m_.front_idx == m_.back_idx;
    }
 
    /**
     * **Returns**: The number of elements the devector contains.
     *
     * **Complexity**: Constant.
     */
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
     size_type size() const BOOST_NOEXCEPT
    {
       return size_type(m_.back_idx - m_.front_idx);
    }
 
    /**
     * **Returns**: The maximum number of elements the devector could possibly hold.
     *
     * **Complexity**: Constant.
     */
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
     size_type max_size() const BOOST_NOEXCEPT
    {
       size_type alloc_max = allocator_traits_type::max_size(get_allocator_ref());
       size_type size_type_max = (size_type)-1;
       return (alloc_max <= size_type_max) ? size_type(alloc_max) : size_type_max;
    }
 
    /**
    * **Returns**: The *minimum* number of elements that can be inserted into devector using
    *   position-based insertions without requiring a reallocation. Note that, unlike in 
    *   typical sequence containers like `vector`, `capacity()`, `capacity()` can be smaller than `size()`.
    *   This can happen if a user inserts elements in a particular way (usually inserting at
    *   front up to front_free_capacity() and at back up to back_free_capacity()).
    * 
    * **Complexity**: Constant.
    */
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
    size_type capacity() const BOOST_NOEXCEPT
    {
       size_type const cap_reserve = m_.capacity/devector_min_free_fraction;
       return m_.capacity > cap_reserve ? (m_.capacity - cap_reserve) : 0u;
    }
 
    /**
     * **Returns**: The total number of elements that can be pushed to the front of the
     * devector without requiring reallocation.
     *
     * **Complexity**: Constant.
     */
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
    size_type front_free_capacity() const BOOST_NOEXCEPT
    {
       return m_.front_idx;
    }
 
    /**
     * **Returns**: The total number of elements that can be pushed to the back of the
     * devector without requiring reallocation.
     *
     * **Complexity**: Constant.
     */
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
     size_type back_free_capacity() const BOOST_NOEXCEPT
    {
       return size_type(m_.capacity - m_.back_idx);
    }
 
    /**
    * **Effects**: If `sz` is greater than the size of `*this`,
    * additional value-initialized elements are inserted. Invalidates iterators
    * if reallocation is needed. If `sz` is smaller than than the size of `*this`,
    * elements are erased from the extremes.
    *
    * **Requires**: T shall be [MoveInsertable] into *this and [DefaultConstructible].
    *
    * **Postcondition**: `sz == size()`.
    *
    * **Exceptions**: Strong exception guarantee.
    *
    * **Complexity**: Linear in the size of `*this` and `sz`.
    *
    * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
    * [DefaultConstructible]: http://en.cppreference.com/w/cpp/concept/DefaultConstructible
    */
    BOOST_CONTAINER_FORCEINLINE void resize(size_type sz)
    {
       this->resize_back(sz);
    }
 
    /**
     * **Effects**: Same as resize(sz) but creates default-initialized
     * value-initialized.
     */
    BOOST_CONTAINER_FORCEINLINE void resize(size_type sz, default_init_t)
    {
       this->resize_back(sz, default_init);
    }
 
    /**
    * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
    *
    * **Effects**: If `sz` is greater than the size of `*this`,
    * copies of `c` are inserted at extremes.
    * If `sz` is smaller than than the size of `*this`,
    * elements are popped from the extremes.
    *
    * **Postcondition**: `sz == size()`.
    *
    * **Requires**: `T` shall be [CopyInsertable] into `*this`.
    *
    * **Exceptions**: Strong exception guarantee.
    *
    * **Complexity**: Linear in the size of `*this` and `sz`.
    */
    BOOST_CONTAINER_FORCEINLINE void resize(size_type sz, const T& c)
    {
       this->resize_back(sz, c);
    }
 
    /**
     * **Effects**: If `sz` is greater than the size of `*this`,
     * additional value-initialized elements are inserted
     * to the front. Invalidates iterators if reallocation is needed.
     * If `sz` is smaller than than the size of `*this`,
     * elements are popped from the front.
     *
     * **Requires**: T shall be [MoveInsertable] into *this and [DefaultConstructible].
     *
     * **Postcondition**: `sz == size()`.
     *
     * **Exceptions**: Strong exception guarantee.
     *
     * **Complexity**: Linear in the size of `*this` and `sz`.
     *
     * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
     * [DefaultConstructible]: http://en.cppreference.com/w/cpp/concept/DefaultConstructible
     */
    BOOST_CONTAINER_FORCEINLINE void resize_front(size_type sz)
    {
       resize_front_impl(sz);
       BOOST_ASSERT(invariants_ok());
    }
 
    /**
     * **Effects**: If `sz` is greater than the size of `*this`,
     * additional value-initialized elements are inserted
     * to the front. Invalidates iterators if reallocation is needed.
     * If `sz` is smaller than than the size of `*this`,
     * elements are popped from the front.
     *
     * **Requires**: T shall be [MoveInsertable] into *this and default_initializable.
     *
     * **Postcondition**: `sz == size()`.
     *
     * **Exceptions**: Strong exception guarantee.
     *
     * **Complexity**: Linear in the size of `*this` and `sz`.
     *
     * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
     */
    BOOST_CONTAINER_FORCEINLINE void resize_front(size_type sz, default_init_t)
    {
       resize_front_impl(sz, default_init);
       BOOST_ASSERT(invariants_ok());
    }
 
    /**
     * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
     *
     * **Effects**: If `sz` is greater than the size of `*this`,
     * copies of `c` are inserted to the front.
     * Invalidates iterators if reallocation is needed.
     * If `sz` is smaller than than the size of `*this`,
     * elements are popped from the front.
     *
     * **Postcondition**: `sz == size()`.
     *
     * **Requires**: `T` shall be [CopyInsertable] into `*this`.
     *
     * **Exceptions**: Strong exception guarantee.
     *
     * **Complexity**: Linear in the size of `*this` and `sz`.
     */
    BOOST_CONTAINER_FORCEINLINE void resize_front(size_type sz, const T& c)
    {
       resize_front_impl(sz, c);
       BOOST_ASSERT(invariants_ok());
    }
 
    /**
     * **Effects**: If `sz` is greater than the size of `*this`,
     * additional value-initialized elements are inserted
     * to the back. Invalidates iterators if reallocation is needed.
     * If `sz` is smaller than than the size of `*this`,
     * elements are popped from the back.
     *
     * **Requires**: T shall be [MoveInsertable] into *this and [DefaultConstructible].
     *
     * **Postcondition**: `sz == size()`.
     *
     * **Exceptions**: Strong exception guarantee.
     *
     * **Complexity**: Linear in the size of `*this` and `sz`.
     *
     * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
     * [DefaultConstructible]: http://en.cppreference.com/w/cpp/concept/DefaultConstructible
     */
    BOOST_CONTAINER_FORCEINLINE void resize_back(size_type sz)
    {
       resize_back_impl(sz);
       BOOST_ASSERT(invariants_ok());
    }
 
    /**
     * **Effects**: If `sz` is greater than the size of `*this`,
     * additional value-initialized elements are inserted
     * to the back. Invalidates iterators if reallocation is needed.
     * If `sz` is smaller than than the size of `*this`,
     * elements are popped from the back.
     *
     * **Requires**: T shall be [MoveInsertable] into *this and default initializable.
     *
     * **Postcondition**: `sz == size()`.
     *
     * **Exceptions**: Strong exception guarantee.
     *
     * **Complexity**: Linear in the size of `*this` and `sz`.
     *
     * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
     */
    BOOST_CONTAINER_FORCEINLINE void resize_back(size_type sz, default_init_t)
    {
       resize_back_impl(sz, default_init);
       BOOST_ASSERT(invariants_ok());
    }
 
    /**
     * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
     *
     * **Effects**: If `sz` is greater than the size of `*this`,
     * copies of `c` are inserted to the back.
     * If `sz` is smaller than than the size of `*this`,
     * elements are popped from the back.
     *
     * **Postcondition**: `sz == size()`.
     *
     * **Requires**: `T` shall be [CopyInsertable] into `*this`.
     *
     * **Exceptions**: Strong exception guarantee.
     *
     * **Complexity**: Linear in the size of `*this` and `sz`.
     */
    BOOST_CONTAINER_FORCEINLINE void resize_back(size_type sz, const T& c)
    {
       resize_back_impl(sz, c);
       BOOST_ASSERT(invariants_ok());
    }
 
    /**
     * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
     *
     * **Effects**: Ensures that at least `n` elements can be inserted
     * without requiring reallocation, where `n` is `new_capacity - size()`,
     * if `n` is positive. Otherwise, there are no effects.
     * Invalidates iterators if reallocation is needed.
     *
     * **Requires**: `T` shall be [MoveInsertable] into `*this`.
     *
     * **Complexity**: Linear in the size of *this.
     *
     * **Exceptions**: Strong exception guarantee.
     *
     * **Throws**: length_error if `new_capacity > max_size()`.
     */
    BOOST_CONTAINER_FORCEINLINE void reserve(size_type new_capacity)
    {
       if (this->capacity() < new_capacity) {
          const size_type rounder = devector_min_free_fraction - 2u;
          const size_type divisor = devector_min_free_fraction - 1u;
          size_type const nc = ((new_capacity + rounder)/divisor)*devector_min_free_fraction;
          BOOST_ASSERT(new_capacity <= (nc - nc / devector_min_free_fraction));
          size_type const sz = this->size();
          reallocate_at(nc, (nc-sz)/2u);
       }
       BOOST_ASSERT(invariants_ok());
    }
 
    /**
     * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
     *
     * **Effects**: Ensures that `n` elements can be pushed to the front
     * without requiring reallocation, where `n` is `new_capacity - size()`,
     * if `n` is positive. Otherwise, there are no effects.
     * Invalidates iterators if reallocation is needed.
     *
     * **Requires**: `T` shall be [MoveInsertable] into `*this`.
     *
     * **Complexity**: Linear in the size of *this.
     *
     * **Exceptions**: Strong exception guarantee.
     *
     * **Throws**: `length_error` if `new_capacity > max_size()`.
     */
    BOOST_CONTAINER_FORCEINLINE void reserve_front(size_type new_capacity)
    {
       if (front_capacity() >= new_capacity) { return; }
 
       reallocate_at(new_capacity + back_free_capacity(), new_capacity - size());
 
       BOOST_ASSERT(invariants_ok());
    }
 
    /**
     * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
     *
     * **Effects**: Ensures that `n` elements can be pushed to the back
     * without requiring reallocation, where `n` is `new_capacity - size()`,
     * if `n` is positive. Otherwise, there are no effects.
     * Invalidates iterators if reallocation is needed.
     *
     * **Requires**: `T` shall be [MoveInsertable] into `*this`.
     *
     * **Complexity**: Linear in the size of *this.
     *
     * **Exceptions**: Strong exception guarantee.
     *
     * **Throws**: length_error if `new_capacity > max_size()`.
     */
    BOOST_CONTAINER_FORCEINLINE void reserve_back(size_type new_capacity)
    {
       if (back_capacity() >= new_capacity) { return; }
 
       reallocate_at(new_capacity + front_free_capacity(), m_.front_idx);
 
       BOOST_ASSERT(invariants_ok());
    }
 
 
    /**
     * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
     *
     * **Effects**: Reduces `capacity()` to `size()`. Invalidates iterators.
     *
     * **Requires**: `T` shall be [MoveInsertable] into `*this`.
     *
     * **Exceptions**: Strong exception guarantee.
     *
     * **Complexity**: Linear in the size of *this.
     */
    BOOST_CONTAINER_FORCEINLINE void shrink_to_fit()
    {
       if(this->front_capacity() || this->back_capacity())
             this->reallocate_at(size(), 0);
    }
 
    // element access:
 
    /**
     * **Returns**: A reference to the `n`th element in the devector.
     *
     * **Precondition**: `n < size()`.
     *
     * **Complexity**: Constant.
     */
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
    reference operator[](size_type n) BOOST_NOEXCEPT
    {
       BOOST_ASSERT(n < size());
       return m_.buffer[m_.front_idx + n];
    }
 
    /**
     * **Returns**: A constant reference to the `n`th element in the devector.
     *
     * **Precondition**: `n < size()`.
     *
     * **Complexity**: Constant.
     */
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
    const_reference operator[](size_type n) const BOOST_NOEXCEPT
    {
       BOOST_ASSERT(n < size());
       return m_.buffer[m_.front_idx + n];
    }
 
    /**
    * **Returns**: A reference to the `n`th element in the devector.
    *
    * **Throws**: `out_of_range`, if `n >= size()`.
    *
    * **Complexity**: Constant.
    */
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
       reference at(size_type n)
    {
       if (size() <= n)
             throw_out_of_range("devector::at out of range");
       return (*this)[n];
    }
 
    /**
    * **Returns**: A constant reference to the `n`th element in the devector.
    *
    * **Throws**: `out_of_range`, if `n >= size()`.
    *
    * **Complexity**: Constant.
    */
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
       const_reference at(size_type n) const
    {
       if (size() <= n)
             throw_out_of_range("devector::at out of range");
       return (*this)[n];
    }
 
    /**
    * **Returns**: A reference to the first element in the devector.
    *
    * **Precondition**: `!empty()`.
    *
    * **Complexity**: Constant.
    */
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
       reference front() BOOST_NOEXCEPT
    {
       BOOST_ASSERT(!empty());
 
       return m_.buffer[m_.front_idx];
    }
 
    /**
    * **Returns**: A constant reference to the first element in the devector.
    *
    * **Precondition**: `!empty()`.
    *
    * **Complexity**: Constant.
    */
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
       const_reference front() const BOOST_NOEXCEPT
    {
       BOOST_ASSERT(!empty());
 
       return m_.buffer[m_.front_idx];
    }
 
    /**
    * **Returns**: A reference to the last element in the devector.
    *
    * **Precondition**: `!empty()`.
    *
    * **Complexity**: Constant.
    */
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
       reference back() BOOST_NOEXCEPT
    {
       BOOST_ASSERT(!empty());
 
       return m_.buffer[m_.back_idx - 1u];
    }
 
    /**
    * **Returns**: A constant reference to the last element in the devector.
    *
    * **Precondition**: `!empty()`.
    *
    * **Complexity**: Constant.
    */
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
       const_reference back() const BOOST_NOEXCEPT
    {
       BOOST_ASSERT(!empty());
 
       return m_.buffer[m_.back_idx - 1u];
    }
 
    /**
    * **Returns**: A pointer to the underlying array serving as element storage.
    * The range `[data(); data() + size())` is always valid. For a non-empty devector,
    * `data() == &front()`.
    *
    * **Complexity**: Constant.
    */
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
       T* data() BOOST_NOEXCEPT
    {
       return boost::movelib::to_raw_pointer(m_.buffer) + m_.front_idx;
    }
 
    /**
    * **Returns**: A constant pointer to the underlying array serving as element storage.
    * The range `[data(); data() + size())` is always valid. For a non-empty devector,
    * `data() == &front()`.
    *
    * **Complexity**: Constant.
    */
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
       const T* data() const BOOST_NOEXCEPT
    {
       return boost::movelib::to_raw_pointer(m_.buffer) + m_.front_idx;
    }
 
    // modifiers:
 
    /**
    * **Effects**: Pushes a new element to the front of the devector.
    * The element is constructed in-place, using the perfect forwarded `args`
    * as constructor arguments. Invalidates iterators if reallocation is needed.
    * (`front_free_capacity() == 0`)
    *
    * **Requires**: `T` shall be [EmplaceConstructible] from `args` and [MoveInsertable] into `*this`.
    *
    * **Exceptions**: Strong exception guarantee.
    *
    * **Complexity**: Amortized constant in the size of `*this`.
    * (Constant, if `front_free_capacity() > 0`)
    *
    * [EmplaceConstructible]: http://en.cppreference.com/w/cpp/concept/EmplaceConstructible
    * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
    */
    #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
    template <class... Args>
    reference emplace_front(Args&&... args)
    {
       if (BOOST_LIKELY(front_free_capacity() != 0)) // fast path
       {
          pointer const p = m_.buffer + (m_.front_idx - 1u);
          this->alloc_construct(p, boost::forward<Args>(args)...);
          --m_.front_idx;
          BOOST_ASSERT(invariants_ok());
          return *p;
       }
       else
       {
          typedef dtl::insert_emplace_proxy<allocator_type, Args...> proxy_t;
          return *this->insert_range_slow_path(this->begin(), 1, proxy_t(::boost::forward<Args>(args)...));
       }
    }
 
    #else //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
 
    #define BOOST_CONTAINER_DEVECTOR_EMPLACE_FRONT(N) \
    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
    BOOST_CONTAINER_FORCEINLINE reference emplace_front(BOOST_MOVE_UREF##N)\
    {\
       if (front_free_capacity())\
       {\
          pointer const p = m_.buffer + (m_.front_idx - 1u);\
          this->alloc_construct(p BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
          --m_.front_idx;\
          return *p;\
       }\
       else\
       {\
          typedef dtl::insert_emplace_proxy_arg##N<allocator_type BOOST_MOVE_I##N BOOST_MOVE_TARG##N> proxy_t;\
          return *this->insert_range_slow_path(this->begin(), 1, proxy_t(BOOST_MOVE_FWD##N));\
       }\
    }\
    //
    BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_DEVECTOR_EMPLACE_FRONT)
    #undef BOOST_CONTAINER_DEVECTOR_EMPLACE_FRONT
 
    #endif
 
    #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
    /**
    * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
    *
    * **Effects**: Pushes the copy of `x` to the front of the devector.
    * Invalidates iterators if reallocation is needed.
    * (`front_free_capacity() == 0`)
    *
    * **Requires**: `T` shall be [CopyInsertable] into `*this`.
    *
    * **Exceptions**: Strong exception guarantee.
    *
    * **Complexity**: Amortized constant in the size of `*this`.
    * (Constant, if `front_free_capacity() > 0`)
    */
    void push_front(const T& x);
 
    /**
    * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
    *
    * **Effects**: Move constructs a new element at the front of the devector using `x`.
    * Invalidates iterators if reallocation is needed.
    * (`front_free_capacity() == 0`)
    *
    * **Requires**: `T` shall be [MoveInsertable] into `*this`.
    *
    * **Exceptions**: Strong exception guarantee, not regarding the state of `x`.
    *
    * **Complexity**: Amortized constant in the size of `*this`.
    * (Constant, if `front_free_capacity() > 0`)
    */
    void push_front(T&& x);
 
    #else
    BOOST_MOVE_CONVERSION_AWARE_CATCH(push_front, T, void, priv_push_front)
    #endif
 
    /**
    * **Effects**: Removes the first element of `*this`.
    *
    * **Precondition**: `!empty()`.
    *
    * **Postcondition**: `front_free_capacity()` is incremented by 1.
    *
    * **Complexity**: Constant.
    */
    void pop_front() BOOST_NOEXCEPT
    {
       BOOST_ASSERT(!empty());
       allocator_traits_type::destroy(get_allocator_ref(), boost::movelib::to_raw_pointer(m_.buffer + m_.front_idx));
       ++m_.front_idx;
       BOOST_ASSERT(invariants_ok());
    }
 
    /**
    * **Effects**: Pushes a new element to the back of the devector.
    * The element is constructed in-place, using the perfect forwarded `args`
    * as constructor arguments. Invalidates iterators if reallocation is needed.
    * (`back_free_capacity() == 0`)
    *
    * **Requires**: `T` shall be [EmplaceConstructible] from `args` and [MoveInsertable] into `*this`,
    * and [MoveAssignable].
    *
    * **Exceptions**: Strong exception guarantee.
    *
    * **Complexity**: Amortized constant in the size of `*this`.
    * (Constant, if `back_free_capacity() > 0`)
    *
    * [EmplaceConstructible]: http://en.cppreference.com/w/cpp/concept/EmplaceConstructible
    * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
    * [MoveAssignable]: http://en.cppreference.com/w/cpp/concept/MoveAssignable
    */
    #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
    template <class... Args>
    BOOST_CONTAINER_FORCEINLINE reference emplace_back(Args&&... args)
    {
       if (BOOST_LIKELY(this->back_free_capacity() != 0)){
          pointer const p = m_.buffer + m_.back_idx;
          this->alloc_construct(p, boost::forward<Args>(args)...);
          ++m_.back_idx;
          BOOST_ASSERT(invariants_ok());
          return *p;
       }
       else {
          typedef dtl::insert_emplace_proxy<allocator_type, Args...> proxy_t;
          return *this->insert_range_slow_path(this->end(), 1, proxy_t(::boost::forward<Args>(args)...));
       }
    }
 
    #else //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
 
    #define BOOST_CONTAINER_DEVECTOR_EMPLACE_BACK(N) \
    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
    BOOST_CONTAINER_FORCEINLINE reference emplace_back(BOOST_MOVE_UREF##N)\
    {\
       if (this->back_free_capacity()){\
          pointer const p = m_.buffer + m_.back_idx;\
          this->alloc_construct(p BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
          ++m_.back_idx;\
          return *p;\
       }\
       else {\
          typedef dtl::insert_emplace_proxy_arg##N<allocator_type BOOST_MOVE_I##N BOOST_MOVE_TARG##N> proxy_t;\
          return *this->insert_range_slow_path(this->end(), 1, proxy_t(BOOST_MOVE_FWD##N));\
       }\
    }\
    //
    BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_DEVECTOR_EMPLACE_BACK)
    #undef BOOST_CONTAINER_DEVECTOR_EMPLACE_BACK
 
    #endif    //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
 
 
    #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
    /**
    * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
    *
    * **Effects**: Pushes the copy of `x` to the back of the devector.
    * Invalidates iterators if reallocation is needed.
    * (`back_free_capacity() == 0`)
    *
    * **Requires**: `T` shall be [CopyInsertable] into `*this`.
    *
    * **Exceptions**: Strong exception guarantee.
    *
    * **Complexity**: Amortized constant in the size of `*this`.
    * (Constant, if `back_free_capacity() > 0`)
    */
    void push_back(const T& x);
 
    /**
    * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
    *
    * **Effects**: Move constructs a new element at the back of the devector using `x`.
    * Invalidates iterators if reallocation is needed.
    * (`back_free_capacity() == 0`)
    *
    * **Requires**: `T` shall be [MoveInsertable] into `*this`.
    *
    * **Exceptions**: Strong exception guarantee, not regarding the state of `x`.
    *
    * **Complexity**: Amortized constant in the size of `*this`.
    * (Constant, if `back_free_capacity() > 0`)
    */
    void push_back(T&& x);
 
    #else
    BOOST_MOVE_CONVERSION_AWARE_CATCH(push_back, T, void, priv_push_back)
    #endif
 
    /**
    * **Effects**: Removes the last element of `*this`.
    *
    * **Precondition**: `!empty()`.
    *
    * **Postcondition**: `back_free_capacity()` is incremented by 1.
    *
    * **Complexity**: Constant.
    */
    void pop_back() BOOST_NOEXCEPT
    {
       BOOST_ASSERT(! empty());
       --m_.back_idx;
       allocator_traits_type::destroy(get_allocator_ref(), boost::movelib::to_raw_pointer(m_.buffer + m_.back_idx));
       BOOST_ASSERT(invariants_ok());
    }
 
    /**
    * **Effects**: Constructs a new element before the element pointed by `position`.
    * The element is constructed in-place, using the perfect forwarded `args`
    * as constructor arguments. Invalidates iterators if reallocation is needed.
    *
    * **Requires**: `T` shall be [EmplaceConstructible], and [MoveInsertable] into `*this`,
    * and [MoveAssignable].
    *
    * **Returns**: Iterator pointing to the newly constructed element.
    *
    * **Exceptions**: Strong exception guarantee if `T` is `NothrowConstructible`
    * and `NothrowAssignable`, Basic exception guarantee otherwise.
    *
    * **Complexity**: Linear in the size of `*this`.
    *
    * [EmplaceConstructible]: http://en.cppreference.com/w/cpp/concept/EmplaceConstructible
    * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
    * [MoveAssignable]: http://en.cppreference.com/w/cpp/concept/MoveAssignable
    */
    #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
    template <class... Args>
    iterator emplace(const_iterator position, Args&&... args)
    {
       BOOST_ASSERT(position >= begin());
       BOOST_ASSERT(position <= end());
       typedef dtl::insert_emplace_proxy<allocator_type, Args...> proxy_t;
       bool prefer_move_back;
       if (position == end()){
          if(back_free_capacity()) // fast path
          {
             pointer const p = m_.buffer + m_.back_idx;
             this->alloc_construct(p, boost::forward<Args>(args)...);
             ++m_.back_idx;
             return iterator(p);
          }
          prefer_move_back = true;
       }
       else if (position == begin()){
          if(front_free_capacity()) // secondary fast path
          {
             pointer const p = m_.buffer + (m_.front_idx - 1);
             this->alloc_construct(p, boost::forward<Args>(args)...);
             --m_.front_idx;
             return iterator(p);
          }
          prefer_move_back = false;
       }
       else{
          iterator nonconst_pos = unconst_iterator(position);
          prefer_move_back = should_move_back(position);
 
          if(prefer_move_back){
             if(back_free_capacity()){
                boost::container::expand_forward_and_insert_nonempty_middle_alloc
                   ( get_allocator_ref()
                   , boost::movelib::to_raw_pointer(nonconst_pos)
                   , this->priv_raw_end()
                   , 1, proxy_t(::boost::forward<Args>(args)...));
                ++m_.back_idx;
                return nonconst_pos;
             }
          }
          else{
             if (front_free_capacity()){
                boost::container::expand_backward_and_insert_nonempty_middle_alloc
                (get_allocator_ref()
                   , this->priv_raw_begin()
                   , boost::movelib::to_raw_pointer(nonconst_pos)
                   , 1, proxy_t(::boost::forward<Args>(args)...));
                --m_.front_idx;
                return --nonconst_pos;
             }
          }
       }
       return this->insert_range_slow_path(position, 1, proxy_t(::boost::forward<Args>(args)...));
    }
 
    #else //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
 
    #define BOOST_CONTAINER_DEVECTOR_EMPLACE(N) \
    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
    iterator emplace(const_iterator position BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
    {\
       BOOST_ASSERT(position >= begin());\
       BOOST_ASSERT(position <= end());\
       typedef dtl::insert_emplace_proxy_arg##N<allocator_type  BOOST_MOVE_I##N BOOST_MOVE_TARG##N> proxy_t;\
       bool prefer_move_back;\
       if (position == end()){\
          if(back_free_capacity())\
          {\
             pointer const p = m_.buffer + m_.back_idx;\
             this->alloc_construct(p BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
             ++m_.back_idx;\
             return iterator(p);\
          }\
          prefer_move_back = true;\
       }\
       else if (position == begin()){\
          if(front_free_capacity())\
          {\
             pointer const p = m_.buffer + (m_.front_idx - 1);\
             this->alloc_construct(p BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
             --m_.front_idx;\
             return iterator(p);\
          }\
          prefer_move_back = false;\
       }\
       else{\
          iterator nonconst_pos = unconst_iterator(position);\
          prefer_move_back = should_move_back(position);\
          \
          if(prefer_move_back){\
             if(back_free_capacity()){\
                boost::container::expand_forward_and_insert_nonempty_middle_alloc\
                   ( get_allocator_ref()\
                   , boost::movelib::to_raw_pointer(nonconst_pos)\
                   , this->priv_raw_end()\
                   , 1, proxy_t(BOOST_MOVE_FWD##N));\
                ++m_.back_idx;\
                return nonconst_pos;\
             }\
          }\
          else{\
             if (front_free_capacity()){\
                boost::container::expand_backward_and_insert_nonempty_middle_alloc\
                (get_allocator_ref()\
                   , this->priv_raw_begin()\
                   , boost::movelib::to_raw_pointer(nonconst_pos)\
                   , 1, proxy_t(BOOST_MOVE_FWD##N));\
                --m_.front_idx;\
                return --nonconst_pos;\
             }\
          }\
       }\
       return this->insert_range_slow_path(position, 1, proxy_t(BOOST_MOVE_FWD##N));\
    }\
    //
    BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_DEVECTOR_EMPLACE)
    #undef BOOST_CONTAINER_DEVECTOR_EMPLACE
 
    #endif    //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
 
 
    #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
    /**
    * **Effects**: Copy constructs a new element before the element pointed by `position`,
    * using `x` as constructor argument. Invalidates iterators if reallocation is needed.
    *
    * **Requires**: `T` shall be [CopyInsertable] into `*this` and and [CopyAssignable].
    *
    * **Returns**: Iterator pointing to the newly constructed element.
    *
    * **Exceptions**: Strong exception guarantee if `T` is `NothrowConstructible`
    * and `NothrowAssignable`, Basic exception guarantee otherwise.
    *
    * **Complexity**: Linear in the size of `*this`.
    *
    * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
    * [CopyAssignable]: http://en.cppreference.com/w/cpp/concept/CopyAssignable
    */
    iterator insert(const_iterator position, const T &x);
 
    /**
    * **Effects**: Move constructs a new element before the element pointed by `position`,
    * using `x` as constructor argument. Invalidates iterators if reallocation is needed.
    *
    * **Requires**: `T` shall be [MoveInsertable] into `*this` and and [CopyAssignable].
    *
    * **Returns**: Iterator pointing to the newly constructed element.
    *
    * **Exceptions**: Strong exception guarantee if `T` is `NothrowConstructible`
    * and `NothrowAssignable` (not regarding the state of `x`),
    * Basic exception guarantee otherwise.
    *
    * **Complexity**: Linear in the size of `*this`.
    *
    * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
    * [CopyAssignable]: http://en.cppreference.com/w/cpp/concept/CopyAssignable
    */
    iterator insert(const_iterator position, T &&x);
    #else
    BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, T, iterator, priv_insert, const_iterator, const_iterator)
    #endif
 
    /**
    * **Effects**: Copy constructs `n` elements before the element pointed by `position`,
    * using `x` as constructor argument. Invalidates iterators if reallocation is needed.
    *
    * **Requires**: `T` shall be [CopyInsertable] into `*this` and and [CopyAssignable].
    *
    * **Returns**: Iterator pointing to the first inserted element, or `position`, if `n` is zero.
    *
    * **Exceptions**: Strong exception guarantee if `T` is `NothrowConstructible`
    * and `NothrowAssignable`, Basic exception guarantee otherwise.
    *
    * **Complexity**: Linear in the size of `*this` and `n`.
    *
    * [CopyInsertable]: http://en.cppreference.com/w/cpp/concept/CopyInsertable
    * [CopyAssignable]: http://en.cppreference.com/w/cpp/concept/CopyAssignable
    */
    BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator position, size_type n, const T& x)
    {
       cvalue_iterator first(x, n);
       cvalue_iterator last = first + n;
       return this->insert_range(position, first, last);
    }
 
    /**
    * **Effects**: Copy constructs elements before the element pointed by position
    * using each element in the range pointed by `first` and `last` as constructor arguments.
    * Invalidates iterators if reallocation is needed.
    *
    * **Requires**: `T` shall be [EmplaceConstructible] into `*this` from `*first`. If the specified iterator
    * does not meet the forward iterator requirements, `T` shall also be [MoveInsertable] into `*this`
    * and [MoveAssignable].
    *
    * **Precondition**: `first` and `last` are not iterators into `*this`.
    *
    * **Returns**: Iterator pointing to the first inserted element, or `position`, if `first == last`.
    *
    * **Complexity**: Linear in the size of `*this` and `N` (where `N` is the distance between `first` and `last`).
    * Makes only `N` calls to the constructor of `T` and no reallocations if iterators `first` and `last`
    * are of forward, bidirectional, or random access categories. It makes 2N calls to the copy constructor of `T`
    * and `O(log(N)) reallocations if they are just input iterators.
    *
    * **Exceptions**: Strong exception guarantee if `T` is `NothrowConstructible`
    * and `NothrowAssignable`, Basic exception guarantee otherwise.
    *
    * **Remarks**: Each iterator in the range `[first,last)` shall be dereferenced exactly once,
    * unless an exception is thrown.
    *
    * [EmplaceConstructible]: http://en.cppreference.com/w/cpp/concept/EmplaceConstructible
    * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
    * [MoveAssignable]: http://en.cppreference.com/w/cpp/concept/MoveAssignable
    */
    template <class InputIterator>
    iterator insert(const_iterator position, InputIterator first, InputIterator last
       //Input iterators
       BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_or
             < void
             BOOST_MOVE_I dtl::is_convertible<InputIterator BOOST_MOVE_I size_type>
             BOOST_MOVE_I dtl::is_not_input_iterator<InputIterator>
             >::type * = 0)
       )
    {
       if (position == end())
       {
          size_type insert_index = size();
 
          for (; first != last; ++first)
          {
             this->emplace_back(*first);
          }
 
          return begin() + insert_index;
       }
       else
       {
          const size_type insert_index = static_cast<size_type>(position - this->cbegin());
          const size_type old_size = static_cast<size_type>(this->size());
 
          for (; first != last; ++first) {
             this->emplace_back(*first);
          }
          iterator rit (this->begin() + insert_index);
          boost::movelib::rotate_gcd(rit, this->begin() + old_size, this->begin() + this->size());
          return rit;
       }
    }
 
    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
 
    template <class ForwardIterator>
    BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator position, ForwardIterator first, ForwardIterator last
       //Other iterators
       BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_or
             < void
             BOOST_MOVE_I dtl::is_convertible<ForwardIterator BOOST_MOVE_I size_type>
             BOOST_MOVE_I dtl::is_input_iterator<ForwardIterator>
             >::type * = 0)
       )
    {
       return insert_range(position, first, last);
    }
 
    #endif // ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
 
    #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
    /** **Equivalent to**: `insert(position, il.begin(), il.end())` */
    BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator position, std::initializer_list<T> il)
    {
       return this->insert(position, il.begin(), il.end());
    }
    #endif
 
    /**
    * [MoveAssignable]: http://en.cppreference.com/w/cpp/concept/MoveAssignable
    *
    * **Effects**: Destroys the element pointed by `position` and removes it from the devector.
    * Invalidates iterators.
    *
    * **Requires**: `T` shall be [MoveAssignable].
    *
    * **Precondition**: `position` must be in the range of `[begin(), end())`.
    *
    * **Returns**: Iterator pointing to the element immediately following the erased element
    * prior to its erasure. If no such element exists, `end()` is returned.
    *
    * **Exceptions**: Strong exception guarantee if `T` is `NothrowAssignable`,
    * Basic exception guarantee otherwise.
    *
    * **Complexity**: Linear in half the size of `*this`.
    */
    iterator erase(const_iterator position)
    {
       return erase(position, position + 1);
    }
 
    /**
    * [MoveAssignable]: http://en.cppreference.com/w/cpp/concept/MoveAssignable
    *
    * **Effects**: Destroys the range `[first,last)` and removes it from the devector.
    * Invalidates iterators.
    *
    * **Requires**: `T` shall be [MoveAssignable].
    *
    * **Precondition**: `[first,last)` must be in the range of `[begin(), end())`.
    *
    * **Returns**: Iterator pointing to the element pointed to by `last` prior to any elements
    * being erased. If no such element exists, `end()` is returned.
    *
    * **Exceptions**: Strong exception guarantee if `T` is `NothrowAssignable`,
    * Basic exception guarantee otherwise.
    *
    * **Complexity**: Linear in half the size of `*this`
    * plus the distance between `first` and `last`.
    */
    iterator erase(const_iterator first, const_iterator last)
    {
       iterator nc_first = unconst_iterator(first);
       iterator nc_last  = unconst_iterator(last);
       return erase(nc_first, nc_last);
    }
 
    /**
    * [MoveAssignable]: http://en.cppreference.com/w/cpp/concept/MoveAssignable
    *
    * **Effects**: Destroys the range `[first,last)` and removes it from the devector.
    * Invalidates iterators.
    *
    * **Requires**: `T` shall be [MoveAssignable].
    *
    * **Precondition**: `[first,last)` must be in the range of `[begin(), end())`.
    *
    * **Returns**: Iterator pointing to the element pointed to by `last` prior to any elements
    * being erased. If no such element exists, `end()` is returned.
    *
    * **Exceptions**: Strong exception guarantee if `T` is `NothrowAssignable`,
    * Basic exception guarantee otherwise.
    *
    * **Complexity**: Linear in half the size of `*this`.
    */
    iterator erase(iterator first, iterator last)
    {
       size_type front_distance = pos_to_index(last);
       size_type back_distance  = size_type(end() - first);
       size_type n = boost::container::iterator_udistance(first, last);
 
       if (front_distance < back_distance)
       {
             // move n to the right
             boost::container::move_backward(begin(), first, last);
 
             for (iterator i = begin(); i != begin() + n; ++i)
             {
                allocator_traits_type::destroy(get_allocator_ref(), boost::movelib::to_raw_pointer(i));
             }
             //n is always less than max stored_size_type
             m_.set_front_idx(m_.front_idx + n);
 
             BOOST_ASSERT(invariants_ok());
             return last;
       }
       else {
             // move n to the left
             boost::container::move(last, end(), first);
 
             for (iterator i = end() - n; i != end(); ++i)
             {
                allocator_traits_type::destroy(get_allocator_ref(), boost::movelib::to_raw_pointer(i));
             }
             //n is always less than max stored_size_type
             m_.set_back_idx(m_.back_idx - n);
 
             BOOST_ASSERT(invariants_ok());
             return first;
       }
    }
 
    /**
    * [MoveInsertable]: http://en.cppreference.com/w/cpp/concept/MoveInsertable
    *
    * **Effects**: exchanges the contents of `*this` and `b`.
    *
    * **Requires**: instances of `T` must be swappable by unqualified call of `swap`
    * and `T` must be [MoveInsertable] into `*this`.
    *
    * **Precondition**: The allocators should allow propagation or should compare equal.
    *
    * **Exceptions**: Basic exceptions guarantee if not `noexcept`.
    *
    * **Complexity**: Constant.
    */
    void swap(devector& b)
       BOOST_NOEXCEPT_IF( allocator_traits_type::propagate_on_container_swap::value
                                  || allocator_traits_type::is_always_equal::value)
    {
       BOOST_CONSTEXPR_OR_CONST bool propagate_alloc = allocator_traits_type::propagate_on_container_swap::value;
       BOOST_ASSERT(propagate_alloc || get_allocator_ref() == b.get_allocator_ref()); // else it's undefined behavior
 
       swap_big_big(*this, b);
 
       // swap indices
       boost::adl_move_swap(m_.front_idx, b.m_.front_idx);
       boost::adl_move_swap(m_.back_idx, b.m_.back_idx);
 
       //And now swap the allocator
       dtl::swap_alloc(this->get_allocator_ref(), b.get_allocator_ref(), dtl::bool_<propagate_alloc>());
 
       BOOST_ASSERT(   invariants_ok());
       BOOST_ASSERT(b.invariants_ok());
    }
 
    /**
    * **Effects**: Destroys all elements in the devector.
    * Invalidates all references, pointers and iterators to the
    * elements of the devector.
    *
    * **Postcondition**: `empty() && front_free_capacity() == 0
    * && back_free_capacity() == old capacity`.
    *
    * **Complexity**: Linear in the size of `*this`.
    *
    * **Remarks**: Does not free memory.
    */
    void clear() BOOST_NOEXCEPT
    {
       destroy_elements(begin(), end());
       m_.front_idx = m_.back_idx = 0;
    }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
       friend bool operator==(const devector& x, const devector& y)
    {   return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin());   }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
       friend bool operator!=(const devector& x, const devector& y)
    {   return !(x == y); }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
       friend bool operator< (const devector& x, const devector& y)
    {   return boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());   }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
       friend bool operator>(const devector& x, const devector& y)
    {   return y < x;   }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
       friend bool operator<=(const devector& x, const devector& y)
    {   return !(y < x);   }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
       friend bool operator>=(const devector& x, const devector& y)
    {   return !(x < y);   }
 
    BOOST_CONTAINER_FORCEINLINE friend void swap(devector& x, devector& y)
       BOOST_NOEXCEPT_IF( allocator_traits_type::propagate_on_container_swap::value
                                  || allocator_traits_type::is_always_equal::value)
    {   x.swap(y);   }
 
    private:
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
    size_type pos_to_index(const_iterator i) const 
    {
       return static_cast<size_type>(i - cbegin());
    }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
    bool should_move_back(const_iterator i) const 
    {
       return static_cast<size_type>(this->pos_to_index(i)) >= this->size()/2u;
    }
 
    BOOST_CONTAINER_FORCEINLINE static iterator unconst_iterator(const_iterator i)
    {
       return boost::intrusive::pointer_traits<pointer>::const_cast_from(i);
    }
 
    BOOST_CONTAINER_FORCEINLINE size_type front_capacity() const
    {
       return m_.back_idx;
    }
 
    BOOST_CONTAINER_FORCEINLINE size_type back_capacity() const
    {
       return size_type(m_.capacity - m_.front_idx);
    }
 
    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
 
    BOOST_CONTAINER_FORCEINLINE T* priv_raw_begin() BOOST_NOEXCEPT
    {   return boost::movelib::to_raw_pointer(m_.buffer) + m_.front_idx;   }
 
    BOOST_CONTAINER_FORCEINLINE T* priv_raw_end() BOOST_NOEXCEPT
    {   return boost::movelib::to_raw_pointer(m_.buffer) + m_.back_idx;    }
 
 
    template <class U>
    BOOST_CONTAINER_FORCEINLINE void priv_push_front(BOOST_FWD_REF(U) u)
    {
       this->emplace_front(boost::forward<U>(u));
    }
 
    template <class U>
    BOOST_CONTAINER_FORCEINLINE void priv_push_back(BOOST_FWD_REF(U) u)
    {
       this->emplace_back(boost::forward<U>(u));
    }
 
    template <class U>
    BOOST_CONTAINER_FORCEINLINE iterator priv_insert(const_iterator pos, BOOST_FWD_REF(U) u)
    {
       return this->emplace(pos, boost::forward<U>(u));
    }
 
    // allocator_type wrappers
 
    BOOST_CONTAINER_FORCEINLINE allocator_type& get_allocator_ref() BOOST_NOEXCEPT
    {
       return static_cast<allocator_type&>(m_);
    }
 
    BOOST_CONTAINER_FORCEINLINE const allocator_type& get_allocator_ref() const BOOST_NOEXCEPT
    {
       return static_cast<const allocator_type&>(m_);
    }
 
    pointer allocate(size_type capacity)
    {
       pointer const p = impl::do_allocate(get_allocator_ref(), capacity);
       #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
       ++m_.capacity_alloc_count;
       #endif // BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
       return p;
    }
 
    void destroy_elements(pointer begin, pointer end)
    {
       for (; begin != end; ++begin)
       {
          allocator_traits_type::destroy(get_allocator_ref(), boost::movelib::to_raw_pointer(begin));
       }
    }
 
    void deallocate_buffer()
    {
       if (m_.buffer)
       {
          allocator_traits_type::deallocate(get_allocator_ref(), m_.buffer, m_.capacity);
       }
    }
 
    #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
    template <typename... Args>
    BOOST_CONTAINER_FORCEINLINE void alloc_construct(pointer dst, Args&&... args)
    {
       allocator_traits_type::construct(
             get_allocator_ref(),
             boost::movelib::to_raw_pointer(dst),
             boost::forward<Args>(args)...
       );
    }
 
    template <typename... Args>
    void construct_n(pointer buffer, size_type n, Args&&... args)
    {
       detail::construction_guard<allocator_type> ctr_guard(buffer, get_allocator_ref());
       guarded_construct_n(buffer, n, ctr_guard, boost::forward<Args>(args)...);
       ctr_guard.release();
    }
 
    template <typename... Args>
    void guarded_construct_n(pointer buffer, size_type n, detail::construction_guard<allocator_type>& ctr_guard, Args&&... args)
    {
       for (size_type i = 0; i < n; ++i) {
          this->alloc_construct(buffer + i, boost::forward<Args>(args)...);
          ctr_guard.extend();
       }
    }
 
    #else //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
 
    #define BOOST_CONTAINER_DEVECTOR_ALLOC_CONSTRUCT(N) \
    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
    BOOST_CONTAINER_FORCEINLINE void alloc_construct(pointer dst BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
    {\
       allocator_traits_type::construct(\
             get_allocator_ref(), boost::movelib::to_raw_pointer(dst) BOOST_MOVE_I##N BOOST_MOVE_FWD##N );\
    }\
    \
    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
    void construct_n(pointer buffer, size_type n BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
    {\
       detail::construction_guard<allocator_type> ctr_guard(buffer, get_allocator_ref());\
       guarded_construct_n(buffer, n, ctr_guard BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
       ctr_guard.release();\
    }\
    \
    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
    void guarded_construct_n(pointer buffer, size_type n, detail::construction_guard<allocator_type>& ctr_guard BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
    {\
       for (size_type i = 0; i < n; ++i) {\
             this->alloc_construct(buffer + i BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
             ctr_guard.extend();\
       }\
    }
    //
    BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_DEVECTOR_ALLOC_CONSTRUCT)
    #undef BOOST_CONTAINER_DEVECTOR_ALLOC_CONSTRUCT
 
    #endif    //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
 
    size_type calculate_new_capacity(size_type requested_capacity)
    {
       size_type max = allocator_traits_type::max_size(this->get_allocator_ref());
       (clamp_by_stored_size_type)(max, stored_size_type());
       const size_type remaining_additional_cap = max - size_type(m_.capacity);
       const size_type min_additional_cap = requested_capacity - size_type(m_.capacity);
       if ( remaining_additional_cap < min_additional_cap )
             boost::container::throw_length_error("devector: get_next_capacity, max size exceeded");
 
       return growth_factor_type()( size_type(m_.capacity), min_additional_cap, max);
    }
 
    void buffer_move_or_copy(pointer dst)
    {
       detail::construction_guard<allocator_type> guard(dst, get_allocator_ref());
 
       buffer_move_or_copy(dst, guard);
 
       guard.release();
    }
 
    void buffer_move_or_copy(pointer dst, detail::construction_guard<allocator_type>& guard)
    {
       opt_move_or_copy(begin(), end(), dst, guard);
 
       destroy_elements(data(), data() + size());
       deallocate_buffer();
    }
 
    template <typename Guard>
    void opt_move_or_copy(pointer begin, pointer end, pointer dst, Guard& guard)
    {
       // if trivial copy and default allocator, memcpy
       boost::container::uninitialized_move_alloc(get_allocator_ref(), begin, end, dst);
       guard.extend();
    }
 
    #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
 
    template <typename... Args>
    void resize_impl(size_type sz, Args&&... args)
    {
       const size_type old_sz = this->size();
       if (sz > old_sz)
       {
          const size_type n = sz - old_sz;
 
          if (sz <= m_.capacity)
          {
             //Construct at back
             const size_type bfc = this->back_free_capacity();
             const size_type b = n < bfc ? n : bfc;
             construct_n(m_.buffer + m_.back_idx, b, boost::forward<Args>(args)...);
             m_.set_back_idx(m_.back_idx + b);
 
             //Construct remaining at front
             const size_type f = n - b;
             construct_n(m_.buffer + m_.front_idx - f, f, boost::forward<Args>(args)...);
             m_.set_front_idx(m_.front_idx - f);
          }
          else
          {
             resize_back_slow_path(sz, n, boost::forward<Args>(args)...);
          }
       }
       else
       {
          const size_type n = old_sz - sz;
          const size_type new_bidx = m_.back_idx - n;
          destroy_elements(m_.buffer + new_bidx, m_.buffer + m_.back_idx);
          m_.set_back_idx(new_bidx);
       }
    }
 
    template <typename... Args>
    void resize_front_impl(size_type sz , Args&&... args)
    {
       const size_type old_sz = this->size();
       if (sz > old_sz)
       {
          const size_type n = sz - old_sz;
 
          if (sz <= this->front_capacity())
          {
             construct_n(m_.buffer + m_.front_idx - n, n, boost::forward<Args>(args)...);
             m_.set_front_idx(m_.front_idx - n);
          }
          else
          {
             resize_front_slow_path(sz, n, boost::forward<Args>(args)...);
          }
       }
       else {
          const size_type n = old_sz - sz;
          const size_type new_fidx = m_.front_idx + n;
          destroy_elements(m_.buffer + m_.front_idx, m_.buffer + new_fidx);
          m_.set_front_idx(new_fidx);
       }
    }
 
    template <typename... Args>
    void resize_front_slow_path(size_type sz, size_type n, Args&&... args)
    {
       const size_type new_capacity = calculate_new_capacity(sz + back_free_capacity());
       pointer new_buffer = allocate(new_capacity);
       allocation_guard new_buffer_guard(new_buffer, new_capacity, get_allocator_ref());
 
       const size_type old_sz = this->size();
       const size_type new_old_elem_index = new_capacity - old_sz;
       const size_type new_elem_index = new_old_elem_index - n;
 
       detail::construction_guard<allocator_type> guard(new_buffer + new_elem_index, get_allocator_ref());
       guarded_construct_n(new_buffer + new_elem_index, n, guard, boost::forward<Args>(args)...);
 
       buffer_move_or_copy(new_buffer + new_old_elem_index, guard);
 
       guard.release();
       new_buffer_guard.release();
 
       m_.buffer = new_buffer;
       m_.set_capacity(new_capacity);
       m_.set_front_idx(new_elem_index);
       m_.set_back_idx(new_elem_index + old_sz + n);
    }
 
    template <typename... Args>
    void resize_back_impl(size_type sz, Args&&... args)
    {
       const size_type old_sz = this->size();
       if (sz > old_sz)
       {
          const size_type n = sz - old_sz;
 
          if (sz <= this->back_capacity())
          {
             construct_n(m_.buffer + m_.back_idx, n, boost::forward<Args>(args)...);
             m_.set_back_idx(m_.back_idx + n);
          }
          else
          {
             resize_back_slow_path(sz, n, boost::forward<Args>(args)...);
          }
       }
       else
       {
          const size_type n = old_sz - sz;
          const size_type new_bidx = m_.back_idx - n;
          destroy_elements(m_.buffer + new_bidx, m_.buffer + m_.back_idx);
          m_.set_back_idx(new_bidx);
       }
    }
 
    template <typename... Args>
    void resize_back_slow_path(size_type sz, size_type n, Args&&... args)
    {
       const size_type new_capacity = calculate_new_capacity(sz + front_free_capacity());
       pointer new_buffer = allocate(new_capacity);
       allocation_guard new_buffer_guard(new_buffer, new_capacity, get_allocator_ref());
 
       detail::construction_guard<allocator_type> guard(new_buffer + m_.back_idx, get_allocator_ref());
       guarded_construct_n(new_buffer + m_.back_idx, n, guard, boost::forward<Args>(args)...);
 
       buffer_move_or_copy(new_buffer + m_.front_idx);
 
       guard.release();
       new_buffer_guard.release();
 
       m_.buffer = new_buffer;
       m_.set_capacity(new_capacity);
       m_.set_back_idx(m_.back_idx + n);
    }
 
    #else //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
 
    #define BOOST_CONTAINER_DEVECTOR_SLOW_PATH(N) \
    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
    void resize_front_impl(size_type sz BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
    {\
       if (sz > size())\
       {\
          const size_type n = sz - size();\
          if (sz <= front_capacity()){\
             construct_n(m_.buffer + m_.front_idx - n, n BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
             m_.set_front_idx(m_.front_idx - n);\
          }\
          else\
          {\
             resize_front_slow_path(sz, n BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
          }\
       }\
       else {\
          while (this->size() > sz)\
          {\
             this->pop_front();\
          }\
       }\
    }\
    \
    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
    void resize_front_slow_path(size_type sz, size_type n BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
    {\
       const size_type new_capacity = calculate_new_capacity(sz + back_free_capacity());\
       pointer new_buffer = allocate(new_capacity);\
       allocation_guard new_buffer_guard(new_buffer, new_capacity, get_allocator_ref());\
    \
       const size_type new_old_elem_index = new_capacity - size();\
       const size_type new_elem_index = new_old_elem_index - n;\
    \
       detail::construction_guard<allocator_type> guard(new_buffer + new_elem_index, get_allocator_ref());\
       guarded_construct_n(new_buffer + new_elem_index, n, guard BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
    \
       buffer_move_or_copy(new_buffer + new_old_elem_index, guard);\
    \
       guard.release();\
       new_buffer_guard.release();\
       m_.buffer = new_buffer;\
       m_.set_capacity(new_capacity);\
       m_.set_back_idx(new_old_elem_index + m_.back_idx - m_.front_idx);\
       m_.set_front_idx(new_elem_index);\
    }\
    \
    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
    void resize_back_impl(size_type sz BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
    {\
       if (sz > size())\
       {\
          const size_type n = sz - size();\
       \
          if (sz <= back_capacity())\
          {\
             construct_n(m_.buffer + m_.back_idx, n BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
             m_.set_back_idx(m_.back_idx + n);\
          }\
          else\
          {\
             resize_back_slow_path(sz, n BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
          }\
       }\
       else\
       {\
          while (size() > sz)\
          {\
             pop_back();\
          }\
       }\
    }\
    \
    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
    void resize_back_slow_path(size_type sz, size_type n BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
    {\
       const size_type new_capacity = calculate_new_capacity(sz + front_free_capacity());\
       pointer new_buffer = allocate(new_capacity);\
       allocation_guard new_buffer_guard(new_buffer, new_capacity, get_allocator_ref());\
    \
       detail::construction_guard<allocator_type> guard(new_buffer + m_.back_idx, get_allocator_ref());\
       guarded_construct_n(new_buffer + m_.back_idx, n, guard BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
    \
       buffer_move_or_copy(new_buffer + m_.front_idx);\
    \
       guard.release();\
       new_buffer_guard.release();\
    \
       m_.buffer = new_buffer;\
       m_.set_capacity(new_capacity);\
       m_.set_back_idx(m_.back_idx + n);\
    }\
    \
    //
    BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_DEVECTOR_SLOW_PATH)
    #undef BOOST_CONTAINER_DEVECTOR_SLOW_PATH
 
    #endif    //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
 
    void reallocate_at(size_type new_capacity, size_type buffer_offset)
    {
       pointer new_buffer = allocate(new_capacity);
       {
          allocation_guard new_buffer_guard(new_buffer, new_capacity, get_allocator_ref());
          boost::container::uninitialized_move_alloc(get_allocator_ref(), this->begin(), this->end(), new_buffer + buffer_offset);
          new_buffer_guard.release();
       }
       destroy_elements(m_.buffer + m_.front_idx, m_.buffer + m_.back_idx);
       deallocate_buffer();
 
       m_.buffer = new_buffer;
       //Safe cast, allocate() will handle stored_size_type overflow
       m_.set_capacity(new_capacity);
       m_.set_back_idx(size_type(m_.back_idx - m_.front_idx) + buffer_offset);
       m_.set_front_idx(buffer_offset);
 
       BOOST_ASSERT(invariants_ok());
    }
 
    template <typename ForwardIterator>
    iterator insert_range(const_iterator position, ForwardIterator first, ForwardIterator last)
    {
       BOOST_ASSERT(position >= begin());
       BOOST_ASSERT(position <= end());
       typedef dtl::insert_range_proxy<allocator_type, ForwardIterator> proxy_t;
 
       size_type const n = boost::container::iterator_udistance(first, last);
       bool prefer_move_back;
       if (BOOST_UNLIKELY(!n)) {
          return begin() + size_type(position - cbegin());
       }
       else if (position == end()) {
          if(back_free_capacity() >= n) // fast path
          {
             iterator r(this->end());
             boost::container::uninitialized_copy_alloc(get_allocator_ref(), first, last, this->priv_raw_end());
             m_.set_back_idx(m_.back_idx + n);
             return r;
          }
          prefer_move_back = true;
       }
       else if (position == begin()) {
          if(front_free_capacity() >= n) {// secondary fast path
             boost::container::uninitialized_copy_alloc(get_allocator_ref(), first, last, this->priv_raw_begin() - n);
             m_.set_front_idx(m_.front_idx - n);
             return begin();
          }
          prefer_move_back = false;
       }
       else{
          iterator nonconst_pos = unconst_iterator(position);
          prefer_move_back = should_move_back(position);
 
          if(prefer_move_back){
             if(back_free_capacity() >= n){
                boost::container::expand_forward_and_insert_nonempty_middle_alloc
                   ( get_allocator_ref()
                   , boost::movelib::to_raw_pointer(nonconst_pos)
                   , this->priv_raw_end()
                   , n, proxy_t(first));
                m_.set_back_idx(m_.back_idx + n);
                return nonconst_pos;
             }
          }
          else{
             if (front_free_capacity() >= n){
                boost::container::expand_backward_and_insert_nonempty_middle_alloc
                   ( get_allocator_ref()
                   , this->priv_raw_begin()
                   , boost::movelib::to_raw_pointer(nonconst_pos)
                   , n, proxy_t(first));
                m_.set_front_idx(m_.front_idx - n);
                return (nonconst_pos -= n);
             }
          }
       }
       return this->insert_range_slow_path(position, n, proxy_t(first));
    }
 
    template <class InsertionProxy>
    BOOST_CONTAINER_NOINLINE iterator insert_range_slow_path
       (const_iterator p, const size_type n, const InsertionProxy proxy)
    {
       size_type const back_free_cap = back_free_capacity();
       size_type const front_free_cap = front_free_capacity();
       size_type const free_cap = front_free_cap + back_free_cap;
       size_type const index = size_type(p - cbegin());
 
       size_type const cap = m_.capacity;
       //Test if enough free memory would be left
       if (free_cap >= n && (free_cap - n) >= cap/devector_min_free_fraction) {
          //Make sure relocation is happening because there was no enough space
          size_type const old_size = this->size();
          BOOST_ASSERT(should_move_back(p) ? (back_free_cap < n) : (front_free_cap < n));
 
          T* const raw_pos = const_cast<T*>(boost::movelib::to_raw_pointer(p));
          size_type const new_size = old_size + n;
          size_type const new_front_idx = (cap - new_size) / 2u;
 
          T* const raw_beg = this->priv_raw_begin();
          T* const new_raw_beg = raw_beg - std::ptrdiff_t(m_.front_idx - new_front_idx);
          m_.back_idx = 0u;
          m_.front_idx = 0u;
          boost::container::expand_backward_forward_and_insert_alloc
             (raw_beg, old_size, new_raw_beg, raw_pos, n, proxy, get_allocator_ref());
          m_.set_front_idx(new_front_idx);
          m_.set_back_idx(new_front_idx + new_size);
       }
       else {
          // reallocate
          const size_type new_capacity = calculate_new_capacity(m_.capacity + n);
          pointer new_buffer = allocate(new_capacity);
 
          // guard allocation
          allocation_guard new_buffer_guard(new_buffer, new_capacity, get_allocator_ref());
 
          size_type const old_size = this->size();
          const size_type new_front_index = (new_capacity - old_size - n) / 2u;
 
          T* const raw_pos = const_cast<T*>(boost::movelib::to_raw_pointer(p));
          T* const raw_new_start = const_cast<T*>(boost::movelib::to_raw_pointer(new_buffer)) + new_front_index;
 
          boost::container::uninitialized_move_and_insert_alloc
             (get_allocator_ref(), this->priv_raw_begin(), raw_pos, this->priv_raw_end(), raw_new_start, n, proxy);
          new_buffer_guard.release();
 
          // cleanup
          destroy_elements(begin(), end());
          deallocate_buffer();
 
          // rebind members
          m_.set_capacity(new_capacity);
          m_.buffer = new_buffer;
          m_.set_back_idx(new_front_index + old_size + n);
          m_.set_front_idx(new_front_index);
       }
       return begin() + index;
    }
 
 
    template <typename Iterator>
    void construct_from_range(Iterator begin, Iterator end)
    {
       allocation_guard buffer_guard(m_.buffer, m_.capacity, get_allocator_ref());
       boost::container::uninitialized_copy_alloc(get_allocator_ref(), begin, end, m_.buffer);
       buffer_guard.release();
    }
 
    template <typename ForwardIterator>
    void allocate_and_copy_range(ForwardIterator first, ForwardIterator last)
    {
       size_type n = boost::container::iterator_udistance(first, last);
 
       pointer new_buffer = n ? allocate(n) : pointer();
       allocation_guard new_buffer_guard(new_buffer, n, get_allocator_ref());
       boost::container::uninitialized_copy_alloc(get_allocator_ref(), first, last, new_buffer);
       destroy_elements(begin(), end());
       deallocate_buffer();
 
       m_.set_capacity(n);
       m_.buffer = new_buffer;
       m_.front_idx = 0;
       m_.set_back_idx(n);
 
       new_buffer_guard.release();
    }
 
    static void swap_big_big(devector& a, devector& b) BOOST_NOEXCEPT
    {
       boost::adl_move_swap(a.m_.capacity, b.m_.capacity);
       boost::adl_move_swap(a.m_.buffer, b.m_.buffer);
    }
 
    template <typename ForwardIterator>
    void overwrite_buffer_impl(ForwardIterator first, ForwardIterator last, dtl::true_)
    {
       const size_type n = boost::container::iterator_udistance(first, last);
 
       BOOST_ASSERT(m_.capacity >= n);
       boost::container::uninitialized_copy_alloc_n
             ( get_allocator_ref(), first
             , n, boost::movelib::to_raw_pointer(m_.buffer));
       m_.front_idx = 0;
       m_.set_back_idx(n);
    }
 
    template <typename InputIterator>
    InputIterator overwrite_buffer_impl(InputIterator first, InputIterator last, dtl::false_)
    {
       pointer pos = m_.buffer;
       detail::construction_guard<allocator_type> front_guard(pos, get_allocator_ref());
 
       while (first != last && pos != begin()) {
          this->alloc_construct(pos++, *first++);
          front_guard.extend();
       }
 
       while (first != last && pos != end()) {
          *pos++ = *first++;
       }
 
       detail::construction_guard<allocator_type> back_guard(pos, get_allocator_ref());
 
       iterator capacity_end = m_.buffer + m_.capacity;
       while (first != last && pos != capacity_end) {
          this->alloc_construct(pos++, *first++);
          back_guard.extend();
       }
 
       pointer destroy_after = dtl::min_value(dtl::max_value(begin(), pos), end());
       destroy_elements(destroy_after, end());
 
       front_guard.release();
       back_guard.release();
 
       m_.front_idx = 0;
       m_.set_back_idx(pos_to_index(pos));
       return first;
    }
 
    template <typename ForwardIterator>
    BOOST_CONTAINER_FORCEINLINE void overwrite_buffer(ForwardIterator first, ForwardIterator last)
    {
       this->overwrite_buffer_impl(first, last, 
             dtl::bool_<dtl::is_trivially_destructible<T>::value>());
    }
 
    bool invariants_ok()
    {
       return  (! m_.capacity || m_.buffer )
               && m_.front_idx <= m_.back_idx
               && m_.back_idx <= m_.capacity;
    }
 
    struct impl : allocator_type
    {
       BOOST_MOVABLE_BUT_NOT_COPYABLE(impl)
 
       public:
       allocator_type &get_al()
       {   return *this;   }
 
       static pointer do_allocate(allocator_type &a, size_type cap)
       {
          if (cap) {
             //First detect overflow on smaller stored_size_types
             if (cap > stored_size_type(-1)){
                   boost::container::throw_length_error("get_next_capacity, allocator's max size reached");
             }
             return allocator_traits_type::allocate(a, cap);
          }
          else {
             return pointer();
          }
       }
 
       impl()
          : allocator_type(), buffer(), front_idx(), back_idx(), capacity()
          #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
          , capacity_alloc_count(0)
          #endif
       {}
 
       explicit impl(const allocator_type &a)
          : allocator_type(a), buffer(), front_idx(), back_idx(), capacity()
          #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
          , capacity_alloc_count(0)
          #endif
       {}
 
       impl(reserve_uninitialized_t, const allocator_type& a, size_type c)
          : allocator_type(a), buffer(do_allocate(get_al(), c) )
          //static cast sizes, as the allocation function will take care of overflows
          , front_idx(static_cast<stored_size_type>(0u))
          , back_idx(static_cast<stored_size_type>(c))
          , capacity(static_cast<stored_size_type>(c))
          #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
          , capacity_alloc_count(size_type(buffer != pointer()))
          #endif
       {}
 
       impl(reserve_only_tag_t, const allocator_type &a, size_type const ffc, size_type const bfc)
          : allocator_type(a), buffer(do_allocate(get_al(), ffc+bfc) )
          //static cast sizes, as the allocation function will take care of overflows
          , front_idx(static_cast<stored_size_type>(ffc))
          , back_idx(static_cast<stored_size_type>(ffc))
          , capacity(static_cast<stored_size_type>(ffc + bfc))
          #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
          , capacity_alloc_count(size_type(buffer != pointer()))
          #endif
       {}
 
       impl(reserve_only_tag_t, const allocator_type &a, size_type const c)
          : allocator_type(a), buffer(do_allocate(get_al(), c) )
          //static cast sizes, as the allocation function will take care of overflows
          , front_idx(static_cast<stored_size_type>(c/2u))
          , back_idx(static_cast<stored_size_type>(c/2u))
          , capacity(static_cast<stored_size_type>(c))
          #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
          , capacity_alloc_count(size_type(buffer != pointer()))
          #endif
       {}
 
       impl(review_implementation_t, const allocator_type &a, pointer p, size_type fi, size_type bi, size_type c)
          : allocator_type(a), buffer(p)
          //static cast sizes, as the allocation function will take care of overflows
          , front_idx(static_cast<stored_size_type>(fi))
          , back_idx(static_cast<stored_size_type>(bi))
          , capacity(static_cast<stored_size_type>(c))
          #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
          , capacity_alloc_count(0)
          #endif
       {}
 
       impl(BOOST_RV_REF(impl) m)
          : allocator_type(BOOST_MOVE_BASE(allocator_type, m))
          , buffer(static_cast<impl&>(m).buffer)
          , front_idx(static_cast<impl&>(m).front_idx)
          , back_idx(static_cast<impl&>(m).back_idx)
          , capacity(static_cast<impl&>(m).capacity)
          #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
          , capacity_alloc_count(0)
          #endif
       {
          impl &i = static_cast<impl&>(m);
          // buffer is already acquired, reset rhs
          i.capacity = 0u;
          i.buffer = pointer();
          i.front_idx = 0;
          i.back_idx = 0;
       }
 
       BOOST_CONTAINER_FORCEINLINE void set_back_idx(size_type bi)
       {
          back_idx = static_cast<stored_size_type>(bi);
       }
 
       BOOST_CONTAINER_FORCEINLINE void set_front_idx(size_type fi)
       {
          front_idx = static_cast<stored_size_type>(fi);
       }
 
       BOOST_CONTAINER_FORCEINLINE void set_capacity(size_type c)
       {
          capacity = static_cast<stored_size_type>(c);
       }
 
       pointer           buffer;
       stored_size_type  front_idx;
       stored_size_type  back_idx;
       stored_size_type  capacity;
       #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
       size_type capacity_alloc_count;
       #endif
    } m_;
 
    #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
    public:
    void reset_alloc_stats()
    {
       m_.capacity_alloc_count = 0;
    }
 
    size_type get_alloc_count() const
    {
       return m_.capacity_alloc_count;
    }
 
    #endif // ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
 
    #endif // ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
 };
 
 }} // namespace boost::container
 
 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
 
 namespace boost {
 
 //!has_trivial_destructor_after_move<> == true_type
 //!specialization for optimizations
 template <class T, class Allocator, class Options>
 struct has_trivial_destructor_after_move<boost::container::devector<T, Allocator, Options> >
 {
     typedef typename boost::container::devector<T, Allocator, Options>::allocator_type allocator_type;
     typedef typename ::boost::container::allocator_traits<allocator_type>::pointer pointer;
     static const bool value = ::boost::has_trivial_destructor_after_move<allocator_type>::value &&
                                            ::boost::has_trivial_destructor_after_move<pointer>::value;
 };
 
 }
 
 #endif    //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
 
 #include <boost/container/detail/config_end.hpp>
 
 #endif // BOOST_CONTAINER_DEVECTOR_HPP