BVB Source Codes

mars Show vector.hpp Source code

Return Download mars: download vector.hpp Source code - Download mars Source code - Type:.hpp
  1. //////////////////////////////////////////////////////////////////////////////
  2. //
  3. // (C) Copyright Ion Gaztanaga 2005-2015. Distributed under the Boost
  4. // Software License, Version 1.0. (See accompanying file
  5. // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
  6. //
  7. // See http://www.boost.org/libs/container for documentation.
  8. //
  9. //////////////////////////////////////////////////////////////////////////////
  10.  
  11. #ifndef BOOST_CONTAINER_CONTAINER_VECTOR_HPP
  12. #define BOOST_CONTAINER_CONTAINER_VECTOR_HPP
  13.  
  14. #ifndef BOOST_CONFIG_HPP
  15. #  include <boost/config.hpp>
  16. #endif
  17.  
  18. #if defined(BOOST_HAS_PRAGMA_ONCE)
  19. #  pragma once
  20. #endif
  21.  
  22. #include <boost/container/detail/config_begin.hpp>
  23. #include <boost/container/detail/workaround.hpp>
  24.  
  25. // container
  26. #include <boost/container/container_fwd.hpp>
  27. #include <boost/container/allocator_traits.hpp>
  28. #include <boost/container/new_allocator.hpp> //new_allocator
  29. #include <boost/container/throw_exception.hpp>
  30. // container detail
  31. #include <boost/container/detail/advanced_insert_int.hpp>
  32. #include <boost/container/detail/algorithm.hpp> //equal()
  33. #include <boost/container/detail/alloc_helpers.hpp>
  34. #include <boost/container/detail/allocation_type.hpp>
  35. #include <boost/container/detail/copy_move_algo.hpp>
  36. #include <boost/container/detail/destroyers.hpp>
  37. #include <boost/container/detail/iterator.hpp>
  38. #include <boost/container/detail/iterators.hpp>
  39. #include <boost/container/detail/iterator_to_raw_pointer.hpp>
  40. #include <boost/container/detail/mpl.hpp>
  41. #include <boost/container/detail/next_capacity.hpp>
  42. #include <boost/container/detail/to_raw_pointer.hpp>
  43. #include <boost/container/detail/type_traits.hpp>
  44. #include <boost/container/detail/version_type.hpp>
  45. // intrusive
  46. #include <boost/intrusive/pointer_traits.hpp>
  47. // move
  48. #include <boost/move/adl_move_swap.hpp>
  49. #include <boost/move/iterator.hpp>
  50. #include <boost/move/traits.hpp>
  51. #include <boost/move/utility_core.hpp>
  52. // move/detail
  53. #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
  54. #include <boost/move/detail/fwd_macros.hpp>
  55. #endif
  56. #include <boost/move/detail/move_helpers.hpp>
  57. // other
  58. #include <boost/core/no_exceptions_support.hpp>
  59. #include <boost/assert.hpp>
  60. #include <boost/cstdint.hpp>
  61.  
  62. //std
  63. #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
  64. #include <initializer_list>   //for std::initializer_list
  65. #endif
  66.  
  67. namespace mars_boost {} namespace boost = mars_boost; namespace mars_boost {
  68. namespace container {
  69.  
  70. #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
  71.  
  72. //#define BOOST_CONTAINER_VECTOR_ITERATOR_IS_POINTER
  73.  
  74. namespace container_detail {
  75.  
  76. #ifndef BOOST_CONTAINER_VECTOR_ITERATOR_IS_POINTER
  77.  
  78. template <class Pointer, bool IsConst>
  79. class vec_iterator
  80. {
  81.    public:
  82.    typedef std::random_access_iterator_tag                                          iterator_category;
  83.    typedef typename mars_boost::intrusive::pointer_traits<Pointer>::element_type         value_type;
  84.    typedef typename mars_boost::intrusive::pointer_traits<Pointer>::difference_type      difference_type;
  85.    typedef typename if_c
  86.       < IsConst
  87.       , typename mars_boost::intrusive::pointer_traits<Pointer>::template
  88.                                  rebind_pointer<const value_type>::type
  89.       , Pointer
  90.       >::type                                                                       pointer;
  91.    typedef typename mars_boost::intrusive::pointer_traits<pointer>                       ptr_traits;
  92.    typedef typename ptr_traits::reference                                           reference;
  93.  
  94.    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
  95.    private:
  96.    Pointer m_ptr;
  97.  
  98.    public:
  99.    const Pointer &get_ptr() const BOOST_NOEXCEPT_OR_NOTHROW
  100.    {  return   m_ptr;  }
  101.  
  102.    Pointer &get_ptr() BOOST_NOEXCEPT_OR_NOTHROW
  103.    {  return   m_ptr;  }
  104.  
  105.    explicit vec_iterator(Pointer ptr) BOOST_NOEXCEPT_OR_NOTHROW
  106.       : m_ptr(ptr)
  107.    {}
  108.    #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
  109.  
  110.    public:
  111.  
  112.    //Constructors
  113.    vec_iterator() BOOST_NOEXCEPT_OR_NOTHROW
  114.       : m_ptr()   //Value initialization to achieve "null iterators" (N3644)
  115.    {}
  116.  
  117.    vec_iterator(vec_iterator<Pointer, false> const& other) BOOST_NOEXCEPT_OR_NOTHROW
  118.       :  m_ptr(other.get_ptr())
  119.    {}
  120.  
  121.    //Pointer like operators
  122.    reference operator*()   const BOOST_NOEXCEPT_OR_NOTHROW
  123.    {  return *m_ptr;  }
  124.  
  125.    pointer operator->()  const BOOST_NOEXCEPT_OR_NOTHROW
  126.    {  return ::mars_boost::intrusive::pointer_traits<pointer>::pointer_to(this->operator*());  }
  127.  
  128.    reference operator[](difference_type off) const BOOST_NOEXCEPT_OR_NOTHROW
  129.    {  return m_ptr[off];   }
  130.  
  131.    //Increment / Decrement
  132.    vec_iterator& operator++() BOOST_NOEXCEPT_OR_NOTHROW
  133.    { ++m_ptr;  return *this; }
  134.  
  135.    vec_iterator operator++(int) BOOST_NOEXCEPT_OR_NOTHROW
  136.    {  return vec_iterator(m_ptr++); }
  137.  
  138.    vec_iterator& operator--() BOOST_NOEXCEPT_OR_NOTHROW
  139.    {  --m_ptr; return *this;  }
  140.  
  141.    vec_iterator operator--(int) BOOST_NOEXCEPT_OR_NOTHROW
  142.    {  return vec_iterator(m_ptr--); }
  143.  
  144.    //Arithmetic
  145.    vec_iterator& operator+=(difference_type off) BOOST_NOEXCEPT_OR_NOTHROW
  146.    {  m_ptr += off; return *this;   }
  147.  
  148.    vec_iterator& operator-=(difference_type off) BOOST_NOEXCEPT_OR_NOTHROW
  149.    {  m_ptr -= off; return *this;   }
  150.  
  151.    friend vec_iterator operator+(const vec_iterator &x, difference_type off) BOOST_NOEXCEPT_OR_NOTHROW
  152.    {  return vec_iterator(x.m_ptr+off);  }
  153.  
  154.    friend vec_iterator operator+(difference_type off, vec_iterator right) BOOST_NOEXCEPT_OR_NOTHROW
  155.    {  right.m_ptr += off;  return right; }
  156.  
  157.    friend vec_iterator operator-(vec_iterator left, difference_type off) BOOST_NOEXCEPT_OR_NOTHROW
  158.    {  left.m_ptr -= off;  return left; }
  159.  
  160.    friend difference_type operator-(const vec_iterator &left, const vec_iterator& right) BOOST_NOEXCEPT_OR_NOTHROW
  161.    {  return left.m_ptr - right.m_ptr;   }
  162.  
  163.    //Comparison operators
  164.    friend bool operator==   (const vec_iterator& l, const vec_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
  165.    {  return l.m_ptr == r.m_ptr;  }
  166.  
  167.    friend bool operator!=   (const vec_iterator& l, const vec_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
  168.    {  return l.m_ptr != r.m_ptr;  }
  169.  
  170.    friend bool operator<    (const vec_iterator& l, const vec_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
  171.    {  return l.m_ptr < r.m_ptr;  }
  172.  
  173.    friend bool operator<=   (const vec_iterator& l, const vec_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
  174.    {  return l.m_ptr <= r.m_ptr;  }
  175.  
  176.    friend bool operator>    (const vec_iterator& l, const vec_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
  177.    {  return l.m_ptr > r.m_ptr;  }
  178.  
  179.    friend bool operator>=   (const vec_iterator& l, const vec_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
  180.    {  return l.m_ptr >= r.m_ptr;  }
  181. };
  182.  
  183. template<class BiDirPosConstIt, class BiDirValueIt>
  184. struct vector_insert_ordered_cursor
  185. {
  186.    typedef typename iterator_traits<BiDirPosConstIt>::value_type  size_type;
  187.    typedef typename iterator_traits<BiDirValueIt>::reference      reference;
  188.  
  189.    vector_insert_ordered_cursor(BiDirPosConstIt posit, BiDirValueIt valueit)
  190.       : last_position_it(posit), last_value_it(valueit)
  191.    {}
  192.  
  193.    void operator --()
  194.    {
  195.       --last_value_it;
  196.       --last_position_it;
  197.       while(this->get_pos() == size_type(-1)){
  198.          --last_value_it;
  199.          --last_position_it;
  200.       }
  201.    }
  202.  
  203.    size_type get_pos() const
  204.    {  return *last_position_it;  }
  205.  
  206.    reference get_val()
  207.    {  return *last_value_it;  }
  208.  
  209.    BiDirPosConstIt last_position_it;
  210.    BiDirValueIt last_value_it;
  211. };
  212.  
  213. template<class T, class SizeType, class BiDirValueIt, class Comp>
  214. struct vector_merge_cursor
  215. {
  216.    typedef SizeType  size_type;
  217.    typedef typename iterator_traits<BiDirValueIt>::reference      reference;
  218.  
  219.    vector_merge_cursor(T *pbeg, T *plast, BiDirValueIt valueit, Comp &cmp)
  220.       : m_pbeg(pbeg), m_pcur(--plast), m_valueit(valueit), m_cmp(cmp)
  221.    {}
  222.  
  223.    void operator --()
  224.    {
  225.       --m_valueit;
  226.       const T &t = *m_valueit;
  227.       while((m_pcur + 1) != m_pbeg){
  228.          if(!m_cmp(t, *m_pcur)){
  229.             break;
  230.          }
  231.          --m_pcur;
  232.       }
  233.    }
  234.  
  235.    size_type get_pos() const
  236.    {  return static_cast<size_type>((m_pcur + 1) - m_pbeg);  }
  237.  
  238.    reference get_val()
  239.    {  return *m_valueit;  }
  240.  
  241.    T *const m_pbeg;
  242.    T *m_pcur;
  243.    BiDirValueIt m_valueit;
  244.    Comp &m_cmp;
  245. };
  246.  
  247. }  //namespace container_detail {
  248.  
  249. template<class Pointer, bool IsConst>
  250. const Pointer &vector_iterator_get_ptr(const container_detail::vec_iterator<Pointer, IsConst> &it) BOOST_NOEXCEPT_OR_NOTHROW
  251. {  return   it.get_ptr();  }
  252.  
  253. template<class Pointer, bool IsConst>
  254. Pointer &get_ptr(container_detail::vec_iterator<Pointer, IsConst> &it) BOOST_NOEXCEPT_OR_NOTHROW
  255. {  return  it.get_ptr();  }
  256.  
  257. namespace container_detail {
  258.  
  259. #else //ifndef BOOST_CONTAINER_VECTOR_ITERATOR_IS_POINTER
  260.  
  261. template< class MaybeConstPointer
  262.         , bool ElementTypeIsConst
  263.             = is_const< typename mars_boost::intrusive::pointer_traits<MaybeConstPointer>::element_type>::value >
  264. struct vector_get_ptr_pointer_to_non_const
  265. {
  266.    typedef MaybeConstPointer                                         const_pointer;
  267.    typedef mars_boost::intrusive::pointer_traits<const_pointer>           pointer_traits_t;
  268.    typedef typename pointer_traits_t::element_type                   element_type;
  269.    typedef typename remove_const<element_type>::type                 non_const_element_type;
  270.    typedef typename pointer_traits_t
  271.       ::template rebind_pointer<non_const_element_type>::type        return_type;
  272.  
  273.    static return_type get_ptr(const const_pointer &ptr) BOOST_NOEXCEPT_OR_NOTHROW
  274.    {  return mars_boost::intrusive::pointer_traits<return_type>::const_cast_from(ptr);  }
  275. };
  276.  
  277. template<class Pointer>
  278. struct vector_get_ptr_pointer_to_non_const<Pointer, false>
  279. {
  280.    typedef const Pointer & return_type;
  281.    static return_type get_ptr(const Pointer &ptr) BOOST_NOEXCEPT_OR_NOTHROW
  282.    {  return ptr;  }
  283. };
  284.  
  285. }  //namespace container_detail {
  286.  
  287. template<class MaybeConstPointer>
  288. typename container_detail::vector_get_ptr_pointer_to_non_const<MaybeConstPointer>::return_type
  289.    vector_iterator_get_ptr(const MaybeConstPointer &ptr) BOOST_NOEXCEPT_OR_NOTHROW
  290. {
  291.    return container_detail::vector_get_ptr_pointer_to_non_const<MaybeConstPointer>::get_ptr(ptr);
  292. }
  293.  
  294. namespace container_detail {
  295.  
  296. #endif   //#ifndef BOOST_CONTAINER_VECTOR_ITERATOR_IS_POINTER
  297.  
  298. struct uninitialized_size_t {};
  299. static const uninitialized_size_t uninitialized_size = uninitialized_size_t();
  300.  
  301. template <class T>
  302. struct vector_value_traits_base
  303. {
  304.    static const bool trivial_dctr = is_trivially_destructible<T>::value;
  305.    static const bool trivial_dctr_after_move = has_trivial_destructor_after_move<T>::value;
  306.    static const bool trivial_copy = is_trivially_copy_constructible<T>::value;
  307.    static const bool nothrow_copy = is_nothrow_copy_constructible<T>::value || trivial_copy;
  308.    static const bool trivial_assign = is_trivially_copy_assignable<T>::value;
  309.    static const bool nothrow_assign = is_nothrow_copy_assignable<T>::value || trivial_assign;
  310. };
  311.  
  312.  
  313. template <class Allocator>
  314. struct vector_value_traits
  315.    : public vector_value_traits_base<typename Allocator::value_type>
  316. {
  317.    typedef vector_value_traits_base<typename Allocator::value_type> base_t;
  318.    //This is the anti-exception array destructor
  319.    //to deallocate values already constructed
  320.    typedef typename container_detail::if_c
  321.       <base_t::trivial_dctr
  322.       ,container_detail::null_scoped_destructor_n<Allocator>
  323.       ,container_detail::scoped_destructor_n<Allocator>
  324.       >::type   ArrayDestructor;
  325.    //This is the anti-exception array deallocator
  326.    typedef container_detail::scoped_array_deallocator<Allocator> ArrayDeallocator;
  327. };
  328.  
  329. //!This struct deallocates and allocated memory
  330. template < class Allocator
  331.          , class AllocatorVersion = typename container_detail::version<Allocator>::type
  332.          >
  333. struct vector_alloc_holder
  334.    : public Allocator
  335. {
  336.    private:
  337.    BOOST_MOVABLE_BUT_NOT_COPYABLE(vector_alloc_holder)
  338.  
  339.    public:
  340.    typedef Allocator allocator_type;
  341.    typedef mars_boost::container::allocator_traits<Allocator> allocator_traits_type;
  342.    typedef typename allocator_traits_type::pointer       pointer;
  343.    typedef typename allocator_traits_type::size_type     size_type;
  344.    typedef typename allocator_traits_type::value_type    value_type;
  345.  
  346.    static bool is_propagable_from(const allocator_type &from_alloc, pointer p, const allocator_type &to_alloc, bool const propagate_allocator)
  347.    {
  348.       (void)propagate_allocator; (void)p; (void)to_alloc; (void)from_alloc;
  349.       const bool all_storage_propagable = !allocator_traits_type::is_partially_propagable::value ||
  350.                                           !allocator_traits_type::storage_is_unpropagable(from_alloc, p);
  351.       return all_storage_propagable && (propagate_allocator || allocator_traits_type::equal(from_alloc, to_alloc));
  352.    }
  353.  
  354.    static bool are_swap_propagable(const allocator_type &l_a, pointer l_p, const allocator_type &r_a, pointer r_p, bool const propagate_allocator)
  355.    {
  356.       (void)propagate_allocator; (void)l_p; (void)r_p; (void)l_a; (void)r_a;
  357.       const bool all_storage_propagable = !allocator_traits_type::is_partially_propagable::value ||
  358.               !(allocator_traits_type::storage_is_unpropagable(l_a, l_p) || allocator_traits_type::storage_is_unpropagable(r_a, r_p));
  359.       return all_storage_propagable && (propagate_allocator || allocator_traits_type::equal(l_a, r_a));
  360.    }
  361.  
  362.    //Constructor, does not throw
  363.    vector_alloc_holder()
  364.       BOOST_NOEXCEPT_IF(container_detail::is_nothrow_default_constructible<Allocator>::value)
  365.       : Allocator(), m_start(), m_size(), m_capacity()
  366.    {}
  367.  
  368.    //Constructor, does not throw
  369.    template<class AllocConvertible>
  370.    explicit vector_alloc_holder(BOOST_FWD_REF(AllocConvertible) a) BOOST_NOEXCEPT_OR_NOTHROW
  371.       : Allocator(mars_boost::forward<AllocConvertible>(a)), m_start(), m_size(), m_capacity()
  372.    {}
  373.  
  374.    //Constructor, does not throw
  375.    template<class AllocConvertible>
  376.    vector_alloc_holder(uninitialized_size_t, BOOST_FWD_REF(AllocConvertible) a, size_type initial_size)
  377.       : Allocator(mars_boost::forward<AllocConvertible>(a))
  378.       , m_start()
  379.       , m_size(initial_size)  //Size is initialized here so vector should only call uninitialized_xxx after this
  380.       , m_capacity()
  381.    {
  382.       if(initial_size){
  383.          pointer reuse = 0;
  384.          m_start = this->allocation_command(allocate_new, initial_size, m_capacity = initial_size, reuse);
  385.       }
  386.    }
  387.  
  388.    //Constructor, does not throw
  389.    vector_alloc_holder(uninitialized_size_t, size_type initial_size)
  390.       : Allocator()
  391.       , m_start()
  392.       , m_size(initial_size)  //Size is initialized here so vector should only call uninitialized_xxx after this
  393.       , m_capacity()
  394.    {
  395.       if(initial_size){
  396.          pointer reuse = 0;
  397.          m_start = this->allocation_command(allocate_new, initial_size, m_capacity = initial_size, reuse);
  398.       }
  399.    }
  400.  
  401.    vector_alloc_holder(BOOST_RV_REF(vector_alloc_holder) holder) BOOST_NOEXCEPT_OR_NOTHROW
  402.       : Allocator(BOOST_MOVE_BASE(Allocator, holder))
  403.       , m_start(holder.m_start)
  404.       , m_size(holder.m_size)
  405.       , m_capacity(holder.m_capacity)
  406.    {
  407.       holder.m_start = pointer();
  408.       holder.m_size = holder.m_capacity = 0;
  409.    }
  410.  
  411.    vector_alloc_holder(pointer p, size_type capacity, BOOST_RV_REF(vector_alloc_holder) holder)
  412.       : Allocator(BOOST_MOVE_BASE(Allocator, holder))
  413.       , m_start(p)
  414.       , m_size(holder.m_size)
  415.       , m_capacity(capacity)
  416.    {
  417.       allocator_type &this_alloc = this->alloc();
  418.       allocator_type &x_alloc = holder.alloc();
  419.       if(this->is_propagable_from(x_alloc, holder.start(), this_alloc, true)){
  420.          if(this->m_capacity){
  421.             this->alloc().deallocate(this->m_start, this->m_capacity);
  422.          }
  423.          m_start = holder.m_start;
  424.          m_capacity = holder.m_capacity;
  425.          holder.m_start = pointer();
  426.          holder.m_capacity = holder.m_size = 0;
  427.       }
  428.       else if(this->m_capacity < holder.m_size){
  429.          size_type const n = holder.m_size;
  430.          pointer reuse = pointer();
  431.          m_start = this->allocation_command(allocate_new, n, m_capacity = n, reuse);
  432.          #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
  433.          this->num_alloc += n != 0;
  434.          #endif
  435.       }
  436.    }
  437.  
  438.    vector_alloc_holder(pointer p, size_type n)
  439.       BOOST_NOEXCEPT_IF(container_detail::is_nothrow_default_constructible<Allocator>::value)
  440.       : Allocator()
  441.       , m_start(p)
  442.       , m_size()
  443.       , m_capacity(n)
  444.    {}
  445.  
  446.    template<class AllocFwd>
  447.    vector_alloc_holder(pointer p, size_type n, BOOST_FWD_REF(AllocFwd) a)
  448.       : Allocator(::mars_boost::forward<AllocFwd>(a))
  449.       , m_start(p)
  450.       , m_size()
  451.       , m_capacity(n)
  452.    {}
  453.  
  454.    ~vector_alloc_holder() BOOST_NOEXCEPT_OR_NOTHROW
  455.    {
  456.       if(this->m_capacity){
  457.          this->alloc().deallocate(this->m_start, this->m_capacity);
  458.       }
  459.    }
  460.  
  461.    pointer allocation_command(mars_boost::container::allocation_type command,
  462.                               size_type limit_size, size_type &prefer_in_recvd_out_size, pointer &reuse)
  463.    {
  464.       typedef typename container_detail::version<Allocator>::type alloc_version;
  465.       return this->priv_allocation_command(alloc_version(), command, limit_size, prefer_in_recvd_out_size, reuse);
  466.    }
  467.  
  468.    bool try_expand_fwd(size_type at_least)
  469.    {
  470.       //There is not enough memory, try to expand the old one
  471.       const size_type new_cap = this->capacity() + at_least;
  472.       size_type real_cap = new_cap;
  473.       pointer reuse = this->start();
  474.       bool const success = !!this->allocation_command(expand_fwd, new_cap, real_cap, reuse);
  475.       //Check for forward expansion
  476.       if(success){
  477.          #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
  478.          ++this->num_expand_fwd;
  479.          #endif
  480.          this->capacity(real_cap);
  481.       }
  482.       return success;
  483.    }
  484.  
  485.    size_type next_capacity(size_type additional_objects) const
  486.    {
  487.       return next_capacity_calculator
  488.          <size_type, NextCapacityDouble //NextCapacity60Percent
  489.          >::get( allocator_traits_type::max_size(this->alloc())
  490.                , this->m_capacity, additional_objects );
  491.    }
  492.  
  493.    pointer     m_start;
  494.    size_type   m_size;
  495.    size_type   m_capacity;
  496.  
  497.    void swap_resources(vector_alloc_holder &x) BOOST_NOEXCEPT_OR_NOTHROW
  498.    {
  499.       mars_boost::adl_move_swap(this->m_start, x.m_start);
  500.       mars_boost::adl_move_swap(this->m_size, x.m_size);
  501.       mars_boost::adl_move_swap(this->m_capacity, x.m_capacity);
  502.    }
  503.  
  504.    void steal_resources(vector_alloc_holder &x) BOOST_NOEXCEPT_OR_NOTHROW
  505.    {
  506.       this->m_start     = x.m_start;
  507.       this->m_size      = x.m_size;
  508.       this->m_capacity  = x.m_capacity;
  509.       x.m_start = pointer();
  510.       x.m_size = x.m_capacity = 0;
  511.    }
  512.  
  513.    Allocator &alloc() BOOST_NOEXCEPT_OR_NOTHROW
  514.    {  return *this;  }
  515.  
  516.    const Allocator &alloc() const BOOST_NOEXCEPT_OR_NOTHROW
  517.    {  return *this;  }
  518.  
  519.    const pointer   &start() const     BOOST_NOEXCEPT_OR_NOTHROW {  return m_start;  }
  520.    const size_type &capacity() const  BOOST_NOEXCEPT_OR_NOTHROW {  return m_capacity;  }
  521.    void start(const pointer &p)       BOOST_NOEXCEPT_OR_NOTHROW {  m_start = p;  }
  522.    void capacity(const size_type &c)  BOOST_NOEXCEPT_OR_NOTHROW {  m_capacity = c;  }
  523.  
  524.    private:
  525.    void priv_first_allocation(size_type cap)
  526.    {
  527.       if(cap){
  528.          pointer reuse = 0;
  529.          m_start = this->allocation_command(allocate_new, cap, cap, reuse);
  530.          m_capacity = cap;
  531.          #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
  532.          ++this->num_alloc;
  533.          #endif
  534.       }
  535.    }
  536.  
  537.    pointer priv_allocation_command(version_1, mars_boost::container::allocation_type command,
  538.                          size_type ,
  539.                          size_type &prefer_in_recvd_out_size,
  540.                          pointer &reuse)
  541.    {
  542.       (void)command;
  543.       BOOST_ASSERT( (command & allocate_new));
  544.       BOOST_ASSERT(!(command & nothrow_allocation));
  545.       pointer const p = allocator_traits_type::allocate(this->alloc(), prefer_in_recvd_out_size, reuse);
  546.       reuse = pointer();
  547.       return p;
  548.    }
  549.  
  550.    pointer priv_allocation_command(version_2, mars_boost::container::allocation_type command,
  551.                          size_type limit_size,
  552.                          size_type &prefer_in_recvd_out_size,
  553.                          pointer &reuse)
  554.    {
  555.       return this->alloc().allocation_command(command, limit_size, prefer_in_recvd_out_size, reuse);
  556.    }
  557. };
  558.  
  559. //!This struct deallocates and allocated memory
  560. template <class Allocator>
  561. struct vector_alloc_holder<Allocator, version_0>
  562.    : public Allocator
  563. {
  564.    private:
  565.    BOOST_MOVABLE_BUT_NOT_COPYABLE(vector_alloc_holder)
  566.  
  567.    public:
  568.    typedef mars_boost::container::allocator_traits<Allocator> allocator_traits_type;
  569.    typedef typename allocator_traits_type::pointer       pointer;
  570.    typedef typename allocator_traits_type::size_type     size_type;
  571.    typedef typename allocator_traits_type::value_type    value_type;
  572.  
  573.    template <class OtherAllocator, class OtherAllocatorVersion>
  574.    friend struct vector_alloc_holder;
  575.  
  576.    //Constructor, does not throw
  577.    vector_alloc_holder()
  578.       BOOST_NOEXCEPT_IF(container_detail::is_nothrow_default_constructible<Allocator>::value)
  579.       : Allocator(), m_size()
  580.    {}
  581.  
  582.    //Constructor, does not throw
  583.    template<class AllocConvertible>
  584.    explicit vector_alloc_holder(BOOST_FWD_REF(AllocConvertible) a) BOOST_NOEXCEPT_OR_NOTHROW
  585.       : Allocator(mars_boost::forward<AllocConvertible>(a)), m_size()
  586.    {}
  587.  
  588.    //Constructor, does not throw
  589.    template<class AllocConvertible>
  590.    vector_alloc_holder(uninitialized_size_t, BOOST_FWD_REF(AllocConvertible) a, size_type initial_size)
  591.       : Allocator(mars_boost::forward<AllocConvertible>(a))
  592.       , m_size(initial_size)  //Size is initialized here...
  593.    {
  594.       //... and capacity here, so vector, must call uninitialized_xxx in the derived constructor
  595.       this->priv_first_allocation(initial_size);
  596.    }
  597.  
  598.    //Constructor, does not throw
  599.    vector_alloc_holder(uninitialized_size_t, size_type initial_size)
  600.       : Allocator()
  601.       , m_size(initial_size)  //Size is initialized here...
  602.    {
  603.       //... and capacity here, so vector, must call uninitialized_xxx in the derived constructor
  604.       this->priv_first_allocation(initial_size);
  605.    }
  606.  
  607.    vector_alloc_holder(BOOST_RV_REF(vector_alloc_holder) holder)
  608.       : Allocator(BOOST_MOVE_BASE(Allocator, holder))
  609.       , m_size(holder.m_size) //Size is initialized here so vector should only call uninitialized_xxx after this
  610.    {
  611.       ::mars_boost::container::uninitialized_move_alloc_n
  612.          (this->alloc(), container_detail::to_raw_pointer(holder.start()), m_size, container_detail::to_raw_pointer(this->start()));
  613.    }
  614.  
  615.    template<class OtherAllocator, class OtherAllocatorVersion>
  616.    vector_alloc_holder(BOOST_RV_REF_BEG vector_alloc_holder<OtherAllocator, OtherAllocatorVersion> BOOST_RV_REF_END holder)
  617.       : Allocator()
  618.       , m_size(holder.m_size) //Initialize it to m_size as first_allocation can only succeed or abort
  619.    {
  620.       //Different allocator type so we must check we have enough storage
  621.       const size_type n = holder.m_size;
  622.       this->priv_first_allocation(n);
  623.       ::mars_boost::container::uninitialized_move_alloc_n
  624.          (this->alloc(), container_detail::to_raw_pointer(holder.start()), n, container_detail::to_raw_pointer(this->start()));
  625.    }
  626.  
  627.    void priv_first_allocation(size_type cap)
  628.    {
  629.       if(cap > Allocator::internal_capacity){
  630.          throw_bad_alloc();
  631.       }
  632.    }
  633.  
  634.    void deep_swap(vector_alloc_holder &x)
  635.    {
  636.       this->priv_deep_swap(x);
  637.    }
  638.  
  639.    template<class OtherAllocator, class OtherAllocatorVersion>
  640.    void deep_swap(vector_alloc_holder<OtherAllocator, OtherAllocatorVersion> &x)
  641.    {
  642.       if(this->m_size > OtherAllocator::internal_capacity || x.m_size > Allocator::internal_capacity){
  643.          throw_bad_alloc();
  644.       }
  645.       this->priv_deep_swap(x);
  646.    }
  647.  
  648.    void swap_resources(vector_alloc_holder &) BOOST_NOEXCEPT_OR_NOTHROW
  649.    {  //Containers with version 0 allocators can't be moved without moving elements one by one
  650.       throw_bad_alloc();
  651.    }
  652.  
  653.  
  654.    void steal_resources(vector_alloc_holder &)
  655.    {  //Containers with version 0 allocators can't be moved without moving elements one by one
  656.       throw_bad_alloc();
  657.    }
  658.  
  659.    Allocator &alloc() BOOST_NOEXCEPT_OR_NOTHROW
  660.    {  return *this;  }
  661.  
  662.    const Allocator &alloc() const BOOST_NOEXCEPT_OR_NOTHROW
  663.    {  return *this;  }
  664.  
  665.    bool try_expand_fwd(size_type at_least)
  666.    {  return !at_least;  }
  667.  
  668.    pointer start() const       BOOST_NOEXCEPT_OR_NOTHROW {  return Allocator::internal_storage();  }
  669.    size_type  capacity() const BOOST_NOEXCEPT_OR_NOTHROW {  return Allocator::internal_capacity;  }
  670.    size_type   m_size;
  671.  
  672.    private:
  673.  
  674.    template<class OtherAllocator, class OtherAllocatorVersion>
  675.    void priv_deep_swap(vector_alloc_holder<OtherAllocator, OtherAllocatorVersion> &x)
  676.    {
  677.       const size_type MaxTmpStorage = sizeof(value_type)*Allocator::internal_capacity;
  678.       value_type *const first_this = container_detail::to_raw_pointer(this->start());
  679.       value_type *const first_x = container_detail::to_raw_pointer(x.start());
  680.  
  681.       if(this->m_size < x.m_size){
  682.          mars_boost::container::deep_swap_alloc_n<MaxTmpStorage>(this->alloc(), first_this, this->m_size, first_x, x.m_size);
  683.       }
  684.       else{
  685.          mars_boost::container::deep_swap_alloc_n<MaxTmpStorage>(this->alloc(), first_x, x.m_size, first_this, this->m_size);
  686.       }
  687.       mars_boost::adl_move_swap(this->m_size, x.m_size);
  688.    }
  689. };
  690.  
  691. }  //namespace container_detail {
  692.  
  693. #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
  694.  
  695. //! A vector is a sequence that supports random access to elements, constant
  696. //! time insertion and removal of elements at the end, and linear time insertion
  697. //! and removal of elements at the beginning or in the middle. The number of
  698. //! elements in a vector may vary dynamically; memory management is automatic.
  699. //!
  700. //! \tparam T The type of object that is stored in the vector
  701. //! \tparam Allocator The allocator used for all internal memory management
  702. template <class T, class Allocator BOOST_CONTAINER_DOCONLY(= new_allocator<T>) >
  703. class vector
  704. {
  705.    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
  706.  
  707.    struct value_less
  708.    {
  709.       typedef typename mars_boost::container::allocator_traits<Allocator>::value_type value_type;
  710.       bool operator()(const value_type &a, const value_type &b) const
  711.          {  return a < b;  }
  712.    };
  713.  
  714.    typedef typename container_detail::version<Allocator>::type alloc_version;
  715.    typedef mars_boost::container::container_detail::vector_alloc_holder<Allocator> alloc_holder_t;
  716.    alloc_holder_t m_holder;
  717.    typedef allocator_traits<Allocator>                      allocator_traits_type;
  718.    template <class U, class UAllocator>
  719.    friend class vector;
  720.  
  721.    typedef typename allocator_traits_type::pointer  pointer_impl;
  722.    typedef container_detail::vec_iterator<pointer_impl, false> iterator_impl;
  723.    typedef container_detail::vec_iterator<pointer_impl, true > const_iterator_impl;
  724.  
  725.    protected:
  726.    static bool is_propagable_from(const Allocator &from_alloc, pointer_impl p, const Allocator &to_alloc, bool const propagate_allocator)
  727.    {  return alloc_holder_t::is_propagable_from(from_alloc, p, to_alloc, propagate_allocator);  }
  728.  
  729.    static bool are_swap_propagable( const Allocator &l_a, pointer_impl l_p
  730.                                   , const Allocator &r_a, pointer_impl r_p, bool const propagate_allocator)
  731.    {  return alloc_holder_t::are_swap_propagable(l_a, l_p, r_a, r_p, propagate_allocator);  }
  732.  
  733.    #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
  734.    public:
  735.    //////////////////////////////////////////////
  736.    //
  737.    //                    types
  738.    //
  739.    //////////////////////////////////////////////
  740.  
  741.    typedef T                                                                           value_type;
  742.    typedef typename ::mars_boost::container::allocator_traits<Allocator>::pointer           pointer;
  743.    typedef typename ::mars_boost::container::allocator_traits<Allocator>::const_pointer     const_pointer;
  744.    typedef typename ::mars_boost::container::allocator_traits<Allocator>::reference         reference;
  745.    typedef typename ::mars_boost::container::allocator_traits<Allocator>::const_reference   const_reference;
  746.    typedef typename ::mars_boost::container::allocator_traits<Allocator>::size_type         size_type;
  747.    typedef typename ::mars_boost::container::allocator_traits<Allocator>::difference_type   difference_type;
  748.    typedef Allocator                                                                   allocator_type;
  749.    typedef Allocator                                                                   stored_allocator_type;
  750.    #if defined BOOST_CONTAINER_VECTOR_ITERATOR_IS_POINTER
  751.    typedef BOOST_CONTAINER_IMPDEF(pointer)                                             iterator;
  752.    typedef BOOST_CONTAINER_IMPDEF(const_pointer)                                       const_iterator;
  753.    #else
  754.    typedef BOOST_CONTAINER_IMPDEF(iterator_impl)                                       iterator;
  755.    typedef BOOST_CONTAINER_IMPDEF(const_iterator_impl)                                 const_iterator;
  756.    #endif
  757.    typedef BOOST_CONTAINER_IMPDEF(mars_boost::container::reverse_iterator<iterator>)        reverse_iterator;
  758.    typedef BOOST_CONTAINER_IMPDEF(mars_boost::container::reverse_iterator<const_iterator>)  const_reverse_iterator;
  759.  
  760.    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
  761.    private:
  762.    BOOST_COPYABLE_AND_MOVABLE(vector)
  763.    typedef container_detail::vector_value_traits<Allocator> value_traits;
  764.    typedef constant_iterator<T, difference_type>            cvalue_iterator;
  765.  
  766.    protected:
  767.  
  768.    void steal_resources(vector &x)
  769.    {  return this->m_holder.steal_resources(x.m_holder);   }
  770.  
  771.    struct initial_capacity_t{};
  772.    template<class AllocFwd>
  773.    vector(initial_capacity_t, pointer initial_memory, size_type capacity, BOOST_FWD_REF(AllocFwd) a)
  774.       : m_holder(initial_memory, capacity, ::mars_boost::forward<AllocFwd>(a))
  775.    {}
  776.  
  777.    vector(initial_capacity_t, pointer initial_memory, size_type capacity)
  778.       : m_holder(initial_memory, capacity)
  779.    {}
  780.  
  781.    #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
  782.  
  783.    public:
  784.    //////////////////////////////////////////////
  785.    //
  786.    //          construct/copy/destroy
  787.    //
  788.    //////////////////////////////////////////////
  789.  
  790.    //! <b>Effects</b>: Constructs a vector taking the allocator as parameter.
  791.    //!
  792.    //! <b>Throws</b>: Nothing.
  793.    //!
  794.    //! <b>Complexity</b>: Constant.
  795.    vector() BOOST_NOEXCEPT_OR_NOTHROW
  796.       : m_holder()
  797.    {}
  798.  
  799.    //! <b>Effects</b>: Constructs a vector taking the allocator as parameter.
  800.    //!
  801.    //! <b>Throws</b>: Nothing
  802.    //!
  803.    //! <b>Complexity</b>: Constant.
  804.    explicit vector(const allocator_type& a) BOOST_NOEXCEPT_OR_NOTHROW
  805.       : m_holder(a)
  806.    {}
  807.  
  808.    //! <b>Effects</b>: Constructs a vector and inserts n value initialized values.
  809.    //!
  810.    //! <b>Throws</b>: If allocator_type's allocation
  811.    //!   throws or T's value initialization throws.
  812.    //!
  813.    //! <b>Complexity</b>: Linear to n.
  814.    explicit vector(size_type n)
  815.       :  m_holder(container_detail::uninitialized_size, n)
  816.    {
  817.       #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
  818.       this->num_alloc += n != 0;
  819.       #endif
  820.       mars_boost::container::uninitialized_value_init_alloc_n
  821.          (this->m_holder.alloc(), n, this->priv_raw_begin());
  822.    }
  823.  
  824.    //! <b>Effects</b>: Constructs a vector that will use a copy of allocator a
  825.    //!   and inserts n default initialized values.
  826.    //!
  827.    //! <b>Throws</b>: If allocator_type's allocation
  828.    //!   throws or T's default initialization throws.
  829.    //!
  830.    //! <b>Complexity</b>: Linear to n.
  831.    //!
  832.    //! <b>Note</b>: Non-standard extension
  833.    vector(size_type n, default_init_t)
  834.       :  m_holder(container_detail::uninitialized_size, n)
  835.    {
  836.       #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
  837.       this->num_alloc += n != 0;
  838.       #endif
  839.       mars_boost::container::uninitialized_default_init_alloc_n
  840.          (this->m_holder.alloc(), n, this->priv_raw_begin());
  841.    }
  842.  
  843.    //! <b>Effects</b>: Constructs a vector that will use a copy of allocator a
  844.    //!   and inserts n value initialized values.
  845.    //!
  846.    //! <b>Throws</b>: If allocator_type's allocation
  847.    //!   throws or T's value initialization throws.
  848.    //!
  849.    //! <b>Complexity</b>: Linear to n.
  850.    explicit vector(size_type n, const allocator_type &a)
  851.       :  m_holder(container_detail::uninitialized_size, a, n)
  852.    {
  853.       #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
  854.       this->num_alloc += n != 0;
  855.       #endif
  856.       mars_boost::container::uninitialized_value_init_alloc_n
  857.          (this->m_holder.alloc(), n, this->priv_raw_begin());
  858.    }
  859.  
  860.    //! <b>Effects</b>: Constructs a vector that will use a copy of allocator a
  861.    //!   and inserts n default initialized values.
  862.    //!
  863.    //! <b>Throws</b>: If allocator_type's allocation
  864.    //!   throws or T's default initialization throws.
  865.    //!
  866.    //! <b>Complexity</b>: Linear to n.
  867.    //!
  868.    //! <b>Note</b>: Non-standard extension
  869.    vector(size_type n, default_init_t, const allocator_type &a)
  870.       :  m_holder(container_detail::uninitialized_size, a, n)
  871.    {
  872.       #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
  873.       this->num_alloc += n != 0;
  874.       #endif
  875.       mars_boost::container::uninitialized_default_init_alloc_n
  876.          (this->m_holder.alloc(), n, this->priv_raw_begin());
  877.    }
  878.  
  879.    //! <b>Effects</b>: Constructs a vector
  880.    //!   and inserts n copies of value.
  881.    //!
  882.    //! <b>Throws</b>: If allocator_type's allocation
  883.    //!   throws or T's copy constructor throws.
  884.    //!
  885.    //! <b>Complexity</b>: Linear to n.
  886.    vector(size_type n, const T& value)
  887.       :  m_holder(container_detail::uninitialized_size, n)
  888.    {
  889.       #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
  890.       this->num_alloc += n != 0;
  891.       #endif
  892.       mars_boost::container::uninitialized_fill_alloc_n
  893.          (this->m_holder.alloc(), value, n, this->priv_raw_begin());
  894.    }
  895.  
  896.    //! <b>Effects</b>: Constructs a vector that will use a copy of allocator a
  897.    //!   and inserts n copies of value.
  898.    //!
  899.    //! <b>Throws</b>: If allocation
  900.    //!   throws or T's copy constructor throws.
  901.    //!
  902.    //! <b>Complexity</b>: Linear to n.
  903.    vector(size_type n, const T& value, const allocator_type& a)
  904.       :  m_holder(container_detail::uninitialized_size, a, n)
  905.    {
  906.       #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
  907.       this->num_alloc += n != 0;
  908.       #endif
  909.       mars_boost::container::uninitialized_fill_alloc_n
  910.          (this->m_holder.alloc(), value, n, this->priv_raw_begin());
  911.    }
  912.  
  913.    //! <b>Effects</b>: Constructs a vector
  914.    //!   and inserts a copy of the range [first, last) in the vector.
  915.    //!
  916.    //! <b>Throws</b>: If allocator_type's allocation
  917.    //!   throws or T's constructor taking a dereferenced InIt throws.
  918.    //!
  919.    //! <b>Complexity</b>: Linear to the range [first, last).
  920.    template <class InIt>
  921.    vector(InIt first, InIt last)
  922.       :  m_holder()
  923.    {  this->assign(first, last); }
  924.  
  925.    //! <b>Effects</b>: Constructs a vector that will use a copy of allocator a
  926.    //!   and inserts a copy of the range [first, last) in the vector.
  927.    //!
  928.    //! <b>Throws</b>: If allocator_type's allocation
  929.    //!   throws or T's constructor taking a dereferenced InIt throws.
  930.    //!
  931.    //! <b>Complexity</b>: Linear to the range [first, last).
  932.    template <class InIt>
  933.    vector(InIt first, InIt last, const allocator_type& a)
  934.       :  m_holder(a)
  935.    {  this->assign(first, last); }
  936.  
  937.    //! <b>Effects</b>: Copy constructs a vector.
  938.    //!
  939.    //! <b>Postcondition</b>: x == *this.
  940.    //!
  941.    //! <b>Throws</b>: If allocator_type's allocation
  942.    //!   throws or T's copy constructor throws.
  943.    //!
  944.    //! <b>Complexity</b>: Linear to the elements x contains.
  945.    vector(const vector &x)
  946.       :  m_holder( container_detail::uninitialized_size
  947.                  , allocator_traits_type::select_on_container_copy_construction(x.m_holder.alloc())
  948.                  , x.size())
  949.    {
  950.       #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
  951.       this->num_alloc += x.size() != 0;
  952.       #endif
  953.       ::mars_boost::container::uninitialized_copy_alloc_n
  954.          ( this->m_holder.alloc(), x.priv_raw_begin()
  955.          , x.size(), this->priv_raw_begin());
  956.    }
  957.  
  958.    //! <b>Effects</b>: Move constructor. Moves x's resources to *this.
  959.    //!
  960.    //! <b>Throws</b>: Nothing
  961.    //!
  962.    //! <b>Complexity</b>: Constant.
  963.    vector(BOOST_RV_REF(vector) x) BOOST_NOEXCEPT_OR_NOTHROW
  964.       :  m_holder(mars_boost::move(x.m_holder))
  965.    {  BOOST_STATIC_ASSERT((!allocator_traits_type::is_partially_propagable::value));  }
  966.  
  967.    #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
  968.    //! <b>Effects</b>: Constructs a vector that will use a copy of allocator a
  969.    //!  and inserts a copy of the range [il.begin(), il.last()) in the vector
  970.    //!
  971.    //! <b>Throws</b>: If T's constructor taking a dereferenced initializer_list iterator throws.
  972.    //!
  973.    //! <b>Complexity</b>: Linear to the range [il.begin(), il.end()).
  974.    vector(std::initializer_list<value_type> il, const allocator_type& a = allocator_type())
  975.       : m_holder(a)
  976.    {
  977.       this->assign(il.begin(), il.end());
  978.    }
  979.    #endif
  980.  
  981.    #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
  982.  
  983.    //! <b>Effects</b>: Move constructor. Moves x's resources to *this.
  984.    //!
  985.    //! <b>Throws</b>: If T's move constructor or allocation throws
  986.    //!
  987.    //! <b>Complexity</b>: Linear.
  988.    //!
  989.    //! <b>Note</b>: Non-standard extension to support static_vector
  990.    template<class OtherAllocator>
  991.    vector(BOOST_RV_REF_BEG vector<T, OtherAllocator> BOOST_RV_REF_END x
  992.          , typename container_detail::enable_if_c
  993.             < container_detail::is_version<OtherAllocator, 0>::value>::type * = 0
  994.          )
  995.       :  m_holder(mars_boost::move(x.m_holder))
  996.    {}
  997.  
  998.    #endif   //!defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
  999.  
  1000.    //! <b>Effects</b>: Copy constructs a vector using the specified allocator.
  1001.    //!
  1002.    //! <b>Postcondition</b>: x == *this.
  1003.    //!
  1004.    //! <b>Throws</b>: If allocation
  1005.    //!   throws or T's copy constructor throws.
  1006.    //!
  1007.    //! <b>Complexity</b>: Linear to the elements x contains.
  1008.    vector(const vector &x, const allocator_type &a)
  1009.       :  m_holder(container_detail::uninitialized_size, a, x.size())
  1010.    {
  1011.       #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
  1012.       this->num_alloc += x.size() != 0;
  1013.       #endif
  1014.       ::mars_boost::container::uninitialized_copy_alloc_n_source
  1015.          ( this->m_holder.alloc(), x.priv_raw_begin()
  1016.          , x.size(), this->priv_raw_begin());
  1017.    }
  1018.  
  1019.    //! <b>Effects</b>: Move constructor using the specified allocator.
  1020.    //!                 Moves x's resources to *this if a == allocator_type().
  1021.    //!                 Otherwise copies values from x to *this.
  1022.    //!
  1023.    //! <b>Throws</b>: If allocation or T's copy constructor throws.
  1024.    //!
  1025.    //! <b>Complexity</b>: Constant if a == x.get_allocator(), linear otherwise.
  1026.    vector(BOOST_RV_REF(vector) x, const allocator_type &a)
  1027.       :  m_holder( container_detail::uninitialized_size, a
  1028.                  , is_propagable_from(x.get_stored_allocator(), x.m_holder.start(), a, true) ? 0 : x.size()
  1029.                  )
  1030.    {
  1031.       if(is_propagable_from(x.get_stored_allocator(), x.m_holder.start(), a, true)){
  1032.          this->m_holder.steal_resources(x.m_holder);
  1033.       }
  1034.       else{
  1035.          const size_type n = x.size();
  1036.          #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
  1037.          this->num_alloc += n != 0;
  1038.          #endif
  1039.          ::mars_boost::container::uninitialized_move_alloc_n_source
  1040.             ( this->m_holder.alloc(), x.priv_raw_begin()
  1041.             , n, this->priv_raw_begin());
  1042.       }
  1043.    }
  1044.  
  1045.    //! <b>Effects</b>: Destroys the vector. All stored values are destroyed
  1046.    //!   and used memory is deallocated.
  1047.    //!
  1048.    //! <b>Throws</b>: Nothing.
  1049.    //!
  1050.    //! <b>Complexity</b>: Linear to the number of elements.
  1051.    ~vector() BOOST_NOEXCEPT_OR_NOTHROW
  1052.    {
  1053.       mars_boost::container::destroy_alloc_n
  1054.          (this->get_stored_allocator(), this->priv_raw_begin(), this->m_holder.m_size);
  1055.       //vector_alloc_holder deallocates the data
  1056.    }
  1057.  
  1058.    //! <b>Effects</b>: Makes *this contain the same elements as x.
  1059.    //!
  1060.    //! <b>Postcondition</b>: this->size() == x.size(). *this contains a copy
  1061.    //! of each of x's elements.
  1062.    //!
  1063.    //! <b>Throws</b>: If memory allocation throws or T's copy/move constructor/assignment throws.
  1064.    //!
  1065.    //! <b>Complexity</b>: Linear to the number of elements in x.
  1066.    vector& operator=(BOOST_COPY_ASSIGN_REF(vector) x)
  1067.    {
  1068.       if (&x != this){
  1069.          this->priv_copy_assign(x);
  1070.       }
  1071.       return *this;
  1072.    }
  1073.  
  1074.    #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
  1075.    //! <b>Effects</b>: Make *this container contains elements from il.
  1076.    //!
  1077.    //! <b>Complexity</b>: Linear to the range [il.begin(), il.end()).
  1078.    vector& operator=(std::initializer_list<value_type> il)
  1079.    {
  1080.       this->assign(il.begin(), il.end());
  1081.       return *this;
  1082.    }
  1083.    #endif
  1084.  
  1085.    //! <b>Effects</b>: Move assignment. All x's values are transferred to *this.
  1086.    //!
  1087.    //! <b>Postcondition</b>: x.empty(). *this contains a the elements x had
  1088.    //!   before the function.
  1089.    //!
  1090.    //! <b>Throws</b>: If allocator_traits_type::propagate_on_container_move_assignment
  1091.    //!   is false and (allocation throws or value_type's move constructor throws)
  1092.    //!
  1093.    //! <b>Complexity</b>: Constant if allocator_traits_type::
  1094.    //!   propagate_on_container_move_assignment is true or
  1095.    //!   this->get>allocator() == x.get_allocator(). Linear otherwise.
  1096.    vector& operator=(BOOST_RV_REF(vector) x)
  1097.       BOOST_NOEXCEPT_IF(allocator_traits_type::propagate_on_container_move_assignment::value
  1098.                                   || allocator_traits_type::is_always_equal::value)
  1099.    {
  1100.       BOOST_ASSERT(&x != this);
  1101.       this->priv_move_assign(mars_boost::move(x));
  1102.       return *this;
  1103.    }
  1104.  
  1105.    #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
  1106.  
  1107.    //! <b>Effects</b>: Move assignment. All x's values are transferred to *this.
  1108.    //!
  1109.    //! <b>Postcondition</b>: x.empty(). *this contains a the elements x had
  1110.    //!   before the function.
  1111.    //!
  1112.    //! <b>Throws</b>: If move constructor/assignment of T throws or allocation throws
  1113.    //!
  1114.    //! <b>Complexity</b>: Linear.
  1115.    //!
  1116.    //! <b>Note</b>: Non-standard extension to support static_vector
  1117.    template<class OtherAllocator>
  1118.    typename container_detail::enable_if_and
  1119.                            < vector&
  1120.                            , container_detail::is_version<OtherAllocator, 0>
  1121.                            , container_detail::is_different<OtherAllocator, allocator_type>
  1122.                            >::type
  1123.       operator=(BOOST_RV_REF_BEG vector<value_type, OtherAllocator> BOOST_RV_REF_END x)
  1124.    {
  1125.       this->priv_move_assign(mars_boost::move(x));
  1126.       return *this;
  1127.    }
  1128.  
  1129.    //! <b>Effects</b>: Copy assignment. All x's values are copied to *this.
  1130.    //!
  1131.    //! <b>Postcondition</b>: x.empty(). *this contains a the elements x had
  1132.    //!   before the function.
  1133.    //!
  1134.    //! <b>Throws</b>: If move constructor/assignment of T throws or allocation throws
  1135.    //!
  1136.    //! <b>Complexity</b>: Linear.
  1137.    //!
  1138.    //! <b>Note</b>: Non-standard extension to support static_vector
  1139.    template<class OtherAllocator>
  1140.    typename container_detail::enable_if_and
  1141.                            < vector&
  1142.                            , container_detail::is_version<OtherAllocator, 0>
  1143.                            , container_detail::is_different<OtherAllocator, allocator_type>
  1144.                            >::type
  1145.       operator=(const vector<value_type, OtherAllocator> &x)
  1146.    {
  1147.       this->priv_copy_assign(x);
  1148.       return *this;
  1149.    }
  1150.  
  1151.    #endif
  1152.  
  1153.    //! <b>Effects</b>: Assigns the the range [first, last) to *this.
  1154.    //!
  1155.    //! <b>Throws</b>: If memory allocation throws or T's copy/move constructor/assignment or
  1156.    //!   T's constructor/assignment from dereferencing InpIt throws.
  1157.    //!
  1158.    //! <b>Complexity</b>: Linear to n.
  1159.    template <class InIt>
  1160.    void assign(InIt first, InIt last
  1161.       BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename container_detail::disable_if_or
  1162.          < void
  1163.          BOOST_MOVE_I container_detail::is_convertible<InIt BOOST_MOVE_I size_type>
  1164.          BOOST_MOVE_I container_detail::and_
  1165.             < container_detail::is_different<alloc_version BOOST_MOVE_I version_0>
  1166.             BOOST_MOVE_I container_detail::is_not_input_iterator<InIt>
  1167.             >
  1168.          >::type * = 0)
  1169.       )
  1170.    {
  1171.       //Overwrite all elements we can from [first, last)
  1172.       iterator cur = this->begin();
  1173.       const iterator end_it = this->end();
  1174.       for ( ; first != last && cur != end_it; ++cur, ++first){
  1175.          *cur = *first;
  1176.       }
  1177.  
  1178.       if (first == last){
  1179.          //There are no more elements in the sequence, erase remaining
  1180.          T* const end_pos = this->priv_raw_end();
  1181.          const size_type n = static_cast<size_type>(end_pos - container_detail::iterator_to_raw_pointer(cur));
  1182.          this->priv_destroy_last_n(n);
  1183.       }
  1184.       else{
  1185.          //There are more elements in the range, insert the remaining ones
  1186.          this->insert(this->cend(), first, last);
  1187.       }
  1188.    }
  1189.  
  1190.    #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
  1191.    //! <b>Effects</b>: Assigns the the range [il.begin(), il.end()) to *this.
  1192.    //!
  1193.    //! <b>Throws</b>: If memory allocation throws or
  1194.    //!   T's constructor from dereferencing iniializer_list iterator throws.
  1195.    //!
  1196.    void assign(std::initializer_list<T> il)
  1197.    {
  1198.       this->assign(il.begin(), il.end());
  1199.    }
  1200.    #endif
  1201.  
  1202.    //! <b>Effects</b>: Assigns the the range [first, last) to *this.
  1203.    //!
  1204.    //! <b>Throws</b>: If memory allocation throws or T's copy/move constructor/assignment or
  1205.    //!   T's constructor/assignment from dereferencing InpIt throws.
  1206.    //!
  1207.    //! <b>Complexity</b>: Linear to n.
  1208.    template <class FwdIt>
  1209.    void assign(FwdIt first, FwdIt last
  1210.       BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename container_detail::disable_if_or
  1211.          < void
  1212.          BOOST_MOVE_I container_detail::is_same<alloc_version BOOST_MOVE_I version_0>
  1213.          BOOST_MOVE_I container_detail::is_convertible<FwdIt BOOST_MOVE_I size_type>
  1214.          BOOST_MOVE_I container_detail::is_input_iterator<FwdIt>
  1215.          >::type * = 0)
  1216.       )
  1217.    {
  1218.       //For Fwd iterators the standard only requires EmplaceConstructible and assignable from *first
  1219.       //so we can't do any backwards allocation
  1220.       const size_type input_sz = static_cast<size_type>(mars_boost::container::iterator_distance(first, last));
  1221.       const size_type old_capacity = this->capacity();
  1222.       if(input_sz > old_capacity){  //If input range is too big, we need to reallocate
  1223.          size_type real_cap = 0;
  1224.          pointer reuse(this->m_holder.start());
  1225.          pointer const ret(this->m_holder.allocation_command(allocate_new|expand_fwd, input_sz, real_cap = input_sz, reuse));
  1226.          if(!reuse){  //New allocation, just emplace new values
  1227.             #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
  1228.             ++this->num_alloc;
  1229.             #endif
  1230.             pointer const old_p = this->m_holder.start();
  1231.             if(old_p){
  1232.                this->priv_destroy_all();
  1233.                this->m_holder.alloc().deallocate(old_p, old_capacity);
  1234.             }
  1235.             this->m_holder.start(ret);
  1236.             this->m_holder.capacity(real_cap);
  1237.             this->m_holder.m_size = 0;
  1238.             this->priv_uninitialized_construct_at_end(first, last);
  1239.             return;
  1240.          }
  1241.          else{
  1242.             #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
  1243.             ++this->num_expand_fwd;
  1244.             #endif
  1245.             this->m_holder.capacity(real_cap);
  1246.             //Forward expansion, use assignment + back deletion/construction that comes later
  1247.          }
  1248.       }
  1249.       //Overwrite all elements we can from [first, last)
  1250.       iterator cur = this->begin();
  1251.       const iterator end_it = this->end();
  1252.       for ( ; first != last && cur != end_it; ++cur, ++first){
  1253.          *cur = *first;
  1254.       }
  1255.  
  1256.       if (first == last){
  1257.          //There are no more elements in the sequence, erase remaining
  1258.          this->priv_destroy_last_n(this->size() - input_sz);
  1259.       }
  1260.       else{
  1261.          //Uninitialized construct at end the remaining range
  1262.          this->priv_uninitialized_construct_at_end(first, last);
  1263.       }
  1264.    }
  1265.  
  1266.    //! <b>Effects</b>: Assigns the n copies of val to *this.
  1267.    //!
  1268.    //! <b>Throws</b>: If memory allocation throws or
  1269.    //!   T's copy/move constructor/assignment throws.
  1270.    //!
  1271.    //! <b>Complexity</b>: Linear to n.
  1272.    void assign(size_type n, const value_type& val)
  1273.    {  this->assign(cvalue_iterator(val, n), cvalue_iterator());   }
  1274.  
  1275.    //! <b>Effects</b>: Returns a copy of the internal allocator.
  1276.    //!
  1277.    //! <b>Throws</b>: If allocator's copy constructor throws.
  1278.    //!
  1279.    //! <b>Complexity</b>: Constant.
  1280.    allocator_type get_allocator() const BOOST_NOEXCEPT_OR_NOTHROW
  1281.    { return this->m_holder.alloc();  }
  1282.  
  1283.    //! <b>Effects</b>: Returns a reference to the internal allocator.
  1284.    //!
  1285.    //! <b>Throws</b>: Nothing
  1286.    //!
  1287.    //! <b>Complexity</b>: Constant.
  1288.    //!
  1289.    //! <b>Note</b>: Non-standard extension.
  1290.    stored_allocator_type &get_stored_allocator() BOOST_NOEXCEPT_OR_NOTHROW
  1291.    {  return this->m_holder.alloc(); }
  1292.  
  1293.    //! <b>Effects</b>: Returns a reference to the internal allocator.
  1294.    //!
  1295.    //! <b>Throws</b>: Nothing
  1296.    //!
  1297.    //! <b>Complexity</b>: Constant.
  1298.    //!
  1299.    //! <b>Note</b>: Non-standard extension.
  1300.    const stored_allocator_type &get_stored_allocator() const BOOST_NOEXCEPT_OR_NOTHROW
  1301.    {  return this->m_holder.alloc(); }
  1302.  
  1303.    //////////////////////////////////////////////
  1304.    //
  1305.    //                iterators
  1306.    //
  1307.    //////////////////////////////////////////////
  1308.  
  1309.    //! <b>Effects</b>: Returns an iterator to the first element contained in the vector.
  1310.    //!
  1311.    //! <b>Throws</b>: Nothing.
  1312.    //!
  1313.    //! <b>Complexity</b>: Constant.
  1314.    iterator begin() BOOST_NOEXCEPT_OR_NOTHROW
  1315.    { return iterator(this->m_holder.start()); }
  1316.  
  1317.    //! <b>Effects</b>: Returns a const_iterator to the first element contained in the vector.
  1318.    //!
  1319.    //! <b>Throws</b>: Nothing.
  1320.    //!
  1321.    //! <b>Complexity</b>: Constant.
  1322.    const_iterator begin() const BOOST_NOEXCEPT_OR_NOTHROW
  1323.    { return const_iterator(this->m_holder.start()); }
  1324.  
  1325.    //! <b>Effects</b>: Returns an iterator to the end of the vector.
  1326.    //!
  1327.    //! <b>Throws</b>: Nothing.
  1328.    //!
  1329.    //! <b>Complexity</b>: Constant.
  1330.    iterator end() BOOST_NOEXCEPT_OR_NOTHROW
  1331.    { return iterator(this->m_holder.start() + this->m_holder.m_size); }
  1332.  
  1333.    //! <b>Effects</b>: Returns a const_iterator to the end of the vector.
  1334.    //!
  1335.    //! <b>Throws</b>: Nothing.
  1336.    //!
  1337.    //! <b>Complexity</b>: Constant.
  1338.    const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW
  1339.    { return this->cend(); }
  1340.  
  1341.    //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning
  1342.    //! of the reversed vector.
  1343.    //!
  1344.    //! <b>Throws</b>: Nothing.
  1345.    //!
  1346.    //! <b>Complexity</b>: Constant.
  1347.    reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW
  1348.    { return reverse_iterator(this->end());      }
  1349.  
  1350.    //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
  1351.    //! of the reversed vector.
  1352.    //!
  1353.    //! <b>Throws</b>: Nothing.
  1354.    //!
  1355.    //! <b>Complexity</b>: Constant.
  1356.    const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW
  1357.    { return this->crbegin(); }
  1358.  
  1359.    //! <b>Effects</b>: Returns a reverse_iterator pointing to the end
  1360.    //! of the reversed vector.
  1361.    //!
  1362.    //! <b>Throws</b>: Nothing.
  1363.    //!
  1364.    //! <b>Complexity</b>: Constant.
  1365.    reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW
  1366.    { return reverse_iterator(this->begin());       }
  1367.  
  1368.    //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
  1369.    //! of the reversed vector.
  1370.    //!
  1371.    //! <b>Throws</b>: Nothing.
  1372.    //!
  1373.    //! <b>Complexity</b>: Constant.
  1374.    const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW
  1375.    { return this->crend(); }
  1376.  
  1377.    //! <b>Effects</b>: Returns a const_iterator to the first element contained in the vector.
  1378.    //!
  1379.    //! <b>Throws</b>: Nothing.
  1380.    //!
  1381.    //! <b>Complexity</b>: Constant.
  1382.    const_iterator cbegin() const BOOST_NOEXCEPT_OR_NOTHROW
  1383.    { return const_iterator(this->m_holder.start()); }
  1384.  
  1385.    //! <b>Effects</b>: Returns a const_iterator to the end of the vector.
  1386.    //!
  1387.    //! <b>Throws</b>: Nothing.
  1388.    //!
  1389.    //! <b>Complexity</b>: Constant.
  1390.    const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW
  1391.    { return const_iterator(this->m_holder.start() + this->m_holder.m_size); }
  1392.  
  1393.    //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
  1394.    //! of the reversed vector.
  1395.    //!
  1396.    //! <b>Throws</b>: Nothing.
  1397.    //!
  1398.    //! <b>Complexity</b>: Constant.
  1399.    const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW
  1400.    { return const_reverse_iterator(this->end());}
  1401.  
  1402.    //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
  1403.    //! of the reversed vector.
  1404.    //!
  1405.    //! <b>Throws</b>: Nothing.
  1406.    //!
  1407.    //! <b>Complexity</b>: Constant.
  1408.    const_reverse_iterator crend() const BOOST_NOEXCEPT_OR_NOTHROW
  1409.    { return const_reverse_iterator(this->begin()); }
  1410.  
  1411.    //////////////////////////////////////////////
  1412.    //
  1413.    //                capacity
  1414.    //
  1415.    //////////////////////////////////////////////
  1416.  
  1417.    //! <b>Effects</b>: Returns true if the vector contains no elements.
  1418.    //!
  1419.    //! <b>Throws</b>: Nothing.
  1420.    //!
  1421.    //! <b>Complexity</b>: Constant.
  1422.    bool empty() const BOOST_NOEXCEPT_OR_NOTHROW
  1423.    { return !this->m_holder.m_size; }
  1424.  
  1425.    //! <b>Effects</b>: Returns the number of the elements contained in the vector.
  1426.    //!
  1427.    //! <b>Throws</b>: Nothing.
  1428.    //!
  1429.    //! <b>Complexity</b>: Constant.
  1430.    size_type size() const BOOST_NOEXCEPT_OR_NOTHROW
  1431.    { return this->m_holder.m_size; }
  1432.  
  1433.    //! <b>Effects</b>: Returns the largest possible size of the vector.
  1434.    //!
  1435.    //! <b>Throws</b>: Nothing.
  1436.    //!
  1437.    //! <b>Complexity</b>: Constant.
  1438.    size_type max_size() const BOOST_NOEXCEPT_OR_NOTHROW
  1439.    { return allocator_traits_type::max_size(this->m_holder.alloc()); }
  1440.  
  1441.    //! <b>Effects</b>: Inserts or erases elements at the end such that
  1442.    //!   the size becomes n. New elements are value initialized.
  1443.    //!
  1444.    //! <b>Throws</b>: If memory allocation throws, or T's copy/move or value initialization throws.
  1445.    //!
  1446.    //! <b>Complexity</b>: Linear to the difference between size() and new_size.
  1447.    void resize(size_type new_size)
  1448.    {  this->priv_resize(new_size, value_init);  }
  1449.  
  1450.    //! <b>Effects</b>: Inserts or erases elements at the end such that
  1451.    //!   the size becomes n. New elements are default initialized.
  1452.    //!
  1453.    //! <b>Throws</b>: If memory allocation throws, or T's copy/move or default initialization throws.
  1454.    //!
  1455.    //! <b>Complexity</b>: Linear to the difference between size() and new_size.
  1456.    //!
  1457.    //! <b>Note</b>: Non-standard extension
  1458.    void resize(size_type new_size, default_init_t)
  1459.    {  this->priv_resize(new_size, default_init);  }
  1460.  
  1461.    //! <b>Effects</b>: Inserts or erases elements at the end such that
  1462.    //!   the size becomes n. New elements are copy constructed from x.
  1463.    //!
  1464.    //! <b>Throws</b>: If memory allocation throws, or T's copy/move constructor throws.
  1465.    //!
  1466.    //! <b>Complexity</b>: Linear to the difference between size() and new_size.
  1467.    void resize(size_type new_size, const T& x)
  1468.    {  this->priv_resize(new_size, x);  }
  1469.  
  1470.    //! <b>Effects</b>: Number of elements for which memory has been allocated.
  1471.    //!   capacity() is always greater than or equal to size().
  1472.    //!
  1473.    //! <b>Throws</b>: Nothing.
  1474.    //!
  1475.    //! <b>Complexity</b>: Constant.
  1476.    size_type capacity() const BOOST_NOEXCEPT_OR_NOTHROW
  1477.    { return this->m_holder.capacity(); }
  1478.  
  1479.    //! <b>Effects</b>: If n is less than or equal to capacity(), this call has no
  1480.    //!   effect. Otherwise, it is a request for allocation of additional memory.
  1481.    //!   If the request is successful, then capacity() is greater than or equal to
  1482.    //!   n; otherwise, capacity() is unchanged. In either case, size() is unchanged.
  1483.    //!
  1484.    //! <b>Throws</b>: If memory allocation allocation throws or T's copy/move constructor throws.
  1485.    void reserve(size_type new_cap)
  1486.    {
  1487.       if (this->capacity() < new_cap){
  1488.          this->priv_reserve_no_capacity(new_cap, alloc_version());
  1489.       }
  1490.    }
  1491.  
  1492.    //! <b>Effects</b>: Tries to deallocate the excess of memory created
  1493.    //!   with previous allocations. The size of the vector is unchanged
  1494.    //!
  1495.    //! <b>Throws</b>: If memory allocation throws, or T's copy/move constructor throws.
  1496.    //!
  1497.    //! <b>Complexity</b>: Linear to size().
  1498.    void shrink_to_fit()
  1499.    {  this->priv_shrink_to_fit(alloc_version());   }
  1500.  
  1501.    //////////////////////////////////////////////
  1502.    //
  1503.    //               element access
  1504.    //
  1505.    //////////////////////////////////////////////
  1506.  
  1507.    //! <b>Requires</b>: !empty()
  1508.    //!
  1509.    //! <b>Effects</b>: Returns a reference to the first
  1510.    //!   element of the container.
  1511.    //!
  1512.    //! <b>Throws</b>: Nothing.
  1513.    //!
  1514.    //! <b>Complexity</b>: Constant.
  1515.    reference         front() BOOST_NOEXCEPT_OR_NOTHROW
  1516.    {
  1517.       BOOST_ASSERT(!this->empty());
  1518.       return *this->m_holder.start();
  1519.    }
  1520.  
  1521.    //! <b>Requires</b>: !empty()
  1522.    //!
  1523.    //! <b>Effects</b>: Returns a const reference to the first
  1524.    //!   element of the container.
  1525.    //!
  1526.    //! <b>Throws</b>: Nothing.
  1527.    //!
  1528.    //! <b>Complexity</b>: Constant.
  1529.    const_reference   front() const BOOST_NOEXCEPT_OR_NOTHROW
  1530.    {
  1531.       BOOST_ASSERT(!this->empty());
  1532.       return *this->m_holder.start();
  1533.    }
  1534.  
  1535.    //! <b>Requires</b>: !empty()
  1536.    //!
  1537.    //! <b>Effects</b>: Returns a reference to the last
  1538.    //!   element of the container.
  1539.    //!
  1540.    //! <b>Throws</b>: Nothing.
  1541.    //!
  1542.    //! <b>Complexity</b>: Constant.
  1543.    reference         back() BOOST_NOEXCEPT_OR_NOTHROW
  1544.    {
  1545.       BOOST_ASSERT(!this->empty());
  1546.       return this->m_holder.start()[this->m_holder.m_size - 1];
  1547.    }
  1548.  
  1549.    //! <b>Requires</b>: !empty()
  1550.    //!
  1551.    //! <b>Effects</b>: Returns a const reference to the last
  1552.    //!   element of the container.
  1553.    //!
  1554.    //! <b>Throws</b>: Nothing.
  1555.    //!
  1556.    //! <b>Complexity</b>: Constant.
  1557.    const_reference   back()  const BOOST_NOEXCEPT_OR_NOTHROW
  1558.    {
  1559.       BOOST_ASSERT(!this->empty());
  1560.       return this->m_holder.start()[this->m_holder.m_size - 1];
  1561.    }
  1562.  
  1563.    //! <b>Requires</b>: size() > n.
  1564.    //!
  1565.    //! <b>Effects</b>: Returns a reference to the nth element
  1566.    //!   from the beginning of the container.
  1567.    //!
  1568.    //! <b>Throws</b>: Nothing.
  1569.    //!
  1570.    //! <b>Complexity</b>: Constant.
  1571.    reference operator[](size_type n) BOOST_NOEXCEPT_OR_NOTHROW
  1572.    {
  1573.       BOOST_ASSERT(this->m_holder.m_size > n);
  1574.       return this->m_holder.start()[n];
  1575.    }
  1576.  
  1577.    //! <b>Requires</b>: size() > n.
  1578.    //!
  1579.    //! <b>Effects</b>: Returns a const reference to the nth element
  1580.    //!   from the beginning of the container.
  1581.    //!
  1582.    //! <b>Throws</b>: Nothing.
  1583.    //!
  1584.    //! <b>Complexity</b>: Constant.
  1585.    const_reference operator[](size_type n) const BOOST_NOEXCEPT_OR_NOTHROW
  1586.    {
  1587.       BOOST_ASSERT(this->m_holder.m_size > n);
  1588.       return this->m_holder.start()[n];
  1589.    }
  1590.  
  1591.    //! <b>Requires</b>: size() >= n.
  1592.    //!
  1593.    //! <b>Effects</b>: Returns an iterator to the nth element
  1594.    //!   from the beginning of the container. Returns end()
  1595.    //!   if n == size().
  1596.    //!
  1597.    //! <b>Throws</b>: Nothing.
  1598.    //!
  1599.    //! <b>Complexity</b>: Constant.
  1600.    //!
  1601.    //! <b>Note</b>: Non-standard extension
  1602.    iterator nth(size_type n) BOOST_NOEXCEPT_OR_NOTHROW
  1603.    {
  1604.       BOOST_ASSERT(this->m_holder.m_size >= n);
  1605.       return iterator(this->m_holder.start()+n);
  1606.    }
  1607.  
  1608.    //! <b>Requires</b>: size() >= n.
  1609.    //!
  1610.    //! <b>Effects</b>: Returns a const_iterator to the nth element
  1611.    //!   from the beginning of the container. Returns end()
  1612.    //!   if n == size().
  1613.    //!
  1614.    //! <b>Throws</b>: Nothing.
  1615.    //!
  1616.    //! <b>Complexity</b>: Constant.
  1617.    //!
  1618.    //! <b>Note</b>: Non-standard extension
  1619.    const_iterator nth(size_type n) const BOOST_NOEXCEPT_OR_NOTHROW
  1620.    {
  1621.       BOOST_ASSERT(this->m_holder.m_size >= n);
  1622.       return const_iterator(this->m_holder.start()+n);
  1623.    }
  1624.  
  1625.    //! <b>Requires</b>: size() >= n.
  1626.    //!
  1627.    //! <b>Effects</b>: Returns an iterator to the nth element
  1628.    //!   from the beginning of the container. Returns end()
  1629.    //!   if n == size().
  1630.    //!
  1631.    //! <b>Throws</b>: Nothing.
  1632.    //!
  1633.    //! <b>Complexity</b>: Constant.
  1634.    //!
  1635.    //! <b>Note</b>: Non-standard extension
  1636.    size_type index_of(iterator p) BOOST_NOEXCEPT_OR_NOTHROW
  1637.    {
  1638.       //Range check assert done in priv_index_of
  1639.       return this->priv_index_of(vector_iterator_get_ptr(p));
  1640.    }
  1641.  
  1642.    //! <b>Requires</b>: begin() <= p <= end().
  1643.    //!
  1644.    //! <b>Effects</b>: Returns the index of the element pointed by p
  1645.    //!   and size() if p == end().
  1646.    //!
  1647.    //! <b>Throws</b>: Nothing.
  1648.    //!
  1649.    //! <b>Complexity</b>: Constant.
  1650.    //!
  1651.    //! <b>Note</b>: Non-standard extension
  1652.    size_type index_of(const_iterator p) const BOOST_NOEXCEPT_OR_NOTHROW
  1653.    {
  1654.       //Range check assert done in priv_index_of
  1655.       return this->priv_index_of(vector_iterator_get_ptr(p));
  1656.    }
  1657.  
  1658.    //! <b>Requires</b>: size() > n.
  1659.    //!
  1660.    //! <b>Effects</b>: Returns a reference to the nth element
  1661.    //!   from the beginning of the container.
  1662.    //!
  1663.    //! <b>Throws</b>: std::range_error if n >= size()
  1664.    //!
  1665.    //! <b>Complexity</b>: Constant.
  1666.    reference at(size_type n)
  1667.    {
  1668.       this->priv_throw_if_out_of_range(n);
  1669.       return this->m_holder.start()[n];
  1670.    }
  1671.  
  1672.    //! <b>Requires</b>: size() > n.
  1673.    //!
  1674.    //! <b>Effects</b>: Returns a const reference to the nth element
  1675.    //!   from the beginning of the container.
  1676.    //!
  1677.    //! <b>Throws</b>: std::range_error if n >= size()
  1678.    //!
  1679.    //! <b>Complexity</b>: Constant.
  1680.    const_reference at(size_type n) const
  1681.    {
  1682.       this->priv_throw_if_out_of_range(n);
  1683.       return this->m_holder.start()[n];
  1684.    }
  1685.  
  1686.    //////////////////////////////////////////////
  1687.    //
  1688.    //                 data access
  1689.    //
  1690.    //////////////////////////////////////////////
  1691.  
  1692.    //! <b>Returns</b>: A pointer such that [data(),data() + size()) is a valid range.
  1693.    //!   For a non-empty vector, data() == &front().
  1694.    //!
  1695.    //! <b>Throws</b>: Nothing.
  1696.    //!
  1697.    //! <b>Complexity</b>: Constant.
  1698.    T* data() BOOST_NOEXCEPT_OR_NOTHROW
  1699.    { return this->priv_raw_begin(); }
  1700.  
  1701.    //! <b>Returns</b>: A pointer such that [data(),data() + size()) is a valid range.
  1702.    //!   For a non-empty vector, data() == &front().
  1703.    //!
  1704.    //! <b>Throws</b>: Nothing.
  1705.    //!
  1706.    //! <b>Complexity</b>: Constant.
  1707.    const T * data()  const BOOST_NOEXCEPT_OR_NOTHROW
  1708.    { return this->priv_raw_begin(); }
  1709.  
  1710.    //////////////////////////////////////////////
  1711.    //
  1712.    //                modifiers
  1713.    //
  1714.    //////////////////////////////////////////////
  1715.  
  1716.    #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
  1717.    //! <b>Effects</b>: Inserts an object of type T constructed with
  1718.    //!   std::forward<Args>(args)... in the end of the vector.
  1719.    //!
  1720.    //! <b>Throws</b>: If memory allocation throws or the in-place constructor throws or
  1721.    //!   T's copy/move constructor throws.
  1722.    //!
  1723.    //! <b>Complexity</b>: Amortized constant time.
  1724.    template<class ...Args>
  1725.    void emplace_back(BOOST_FWD_REF(Args)...args)
  1726.    {
  1727.       if (BOOST_LIKELY(this->room_enough())){
  1728.          //There is more memory, just construct a new object at the end
  1729.          allocator_traits_type::construct(this->m_holder.alloc(), this->priv_raw_end(), ::mars_boost::forward<Args>(args)...);
  1730.          ++this->m_holder.m_size;
  1731.       }
  1732.       else{
  1733.          typedef container_detail::insert_emplace_proxy<Allocator, T*, Args...> type;
  1734.          this->priv_forward_range_insert_no_capacity
  1735.             (this->back_ptr(), 1, type(::mars_boost::forward<Args>(args)...), alloc_version());
  1736.       }
  1737.    }
  1738.  
  1739.    //! <b>Effects</b>: Inserts an object of type T constructed with
  1740.    //!   std::forward<Args>(args)... in the end of the vector.
  1741.    //!
  1742.    //! <b>Throws</b>: If the in-place constructor throws.
  1743.    //!
  1744.    //! <b>Complexity</b>: Constant time.
  1745.    //!
  1746.    //! <b>Note</b>: Non-standard extension.
  1747.    template<class ...Args>
  1748.    bool stable_emplace_back(BOOST_FWD_REF(Args)...args)
  1749.    {
  1750.       const bool is_room_enough = this->room_enough() || (alloc_version::value == 2 && this->m_holder.try_expand_fwd(1u));
  1751.       if (BOOST_LIKELY(is_room_enough)){
  1752.          //There is more memory, just construct a new object at the end
  1753.          allocator_traits_type::construct(this->m_holder.alloc(), this->priv_raw_end(), ::mars_boost::forward<Args>(args)...);
  1754.          ++this->m_holder.m_size;
  1755.       }
  1756.       return is_room_enough;
  1757.    }
  1758.  
  1759.    //! <b>Requires</b>: position must be a valid iterator of *this.
  1760.    //!
  1761.    //! <b>Effects</b>: Inserts an object of type T constructed with
  1762.    //!   std::forward<Args>(args)... before position
  1763.    //!
  1764.    //! <b>Throws</b>: If memory allocation throws or the in-place constructor throws or
  1765.    //!   T's copy/move constructor/assignment throws.
  1766.    //!
  1767.    //! <b>Complexity</b>: If position is end(), amortized constant time
  1768.    //!   Linear time otherwise.
  1769.    template<class ...Args>
  1770.    iterator emplace(const_iterator position, BOOST_FWD_REF(Args) ...args)
  1771.    {
  1772.       BOOST_ASSERT(this->priv_in_range_or_end(position));
  1773.       //Just call more general insert(pos, size, value) and return iterator
  1774.       typedef container_detail::insert_emplace_proxy<Allocator, T*, Args...> type;
  1775.       return this->priv_forward_range_insert( vector_iterator_get_ptr(position), 1
  1776.                                             , type(::mars_boost::forward<Args>(args)...));
  1777.    }
  1778.  
  1779.    #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
  1780.  
  1781.    #define BOOST_CONTAINER_VECTOR_EMPLACE_CODE(N) \
  1782.    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
  1783.    void emplace_back(BOOST_MOVE_UREF##N)\
  1784.    {\
  1785.       if (BOOST_LIKELY(this->room_enough())){\
  1786.          allocator_traits_type::construct (this->m_holder.alloc()\
  1787.             , this->priv_raw_end() BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
  1788.          ++this->m_holder.m_size;\
  1789.       }\
  1790.       else{\
  1791.          typedef container_detail::insert_emplace_proxy_arg##N<Allocator, T* BOOST_MOVE_I##N BOOST_MOVE_TARG##N> type;\
  1792.          this->priv_forward_range_insert_no_capacity\
  1793.             ( this->back_ptr(), 1, type(BOOST_MOVE_FWD##N), alloc_version());\
  1794.       }\
  1795.    }\
  1796.    \
  1797.    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
  1798.    bool stable_emplace_back(BOOST_MOVE_UREF##N)\
  1799.    {\
  1800.       const bool is_room_enough = this->room_enough() || (alloc_version::value == 2 && this->m_holder.try_expand_fwd(1u));\
  1801.       if (BOOST_LIKELY(is_room_enough)){\
  1802.          allocator_traits_type::construct (this->m_holder.alloc()\
  1803.             , this->priv_raw_end() BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
  1804.          ++this->m_holder.m_size;\
  1805.       }\
  1806.       return is_room_enough;\
  1807.    }\
  1808.    \
  1809.    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
  1810.    iterator emplace(const_iterator pos BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
  1811.    {\
  1812.       BOOST_ASSERT(this->priv_in_range_or_end(pos));\
  1813.       typedef container_detail::insert_emplace_proxy_arg##N<Allocator, T* BOOST_MOVE_I##N BOOST_MOVE_TARG##N> type;\
  1814.       return this->priv_forward_range_insert(vector_iterator_get_ptr(pos), 1, type(BOOST_MOVE_FWD##N));\
  1815.    }\
  1816.    //
  1817.    BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_VECTOR_EMPLACE_CODE)
  1818.    #undef BOOST_CONTAINER_VECTOR_EMPLACE_CODE
  1819.  
  1820.    #endif
  1821.  
  1822.    #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
  1823.    //! <b>Effects</b>: Inserts a copy of x at the end of the vector.
  1824.    //!
  1825.    //! <b>Throws</b>: If memory allocation throws or
  1826.    //!   T's copy/move constructor throws.
  1827.    //!
  1828.    //! <b>Complexity</b>: Amortized constant time.
  1829.    void push_back(const T &x);
  1830.  
  1831.    //! <b>Effects</b>: Constructs a new element in the end of the vector
  1832.    //!   and moves the resources of x to this new element.
  1833.    //!
  1834.    //! <b>Throws</b>: If memory allocation throws or
  1835.    //!   T's copy/move constructor throws.
  1836.    //!
  1837.    //! <b>Complexity</b>: Amortized constant time.
  1838.    void push_back(T &&x);
  1839.    #else
  1840.    BOOST_MOVE_CONVERSION_AWARE_CATCH(push_back, T, void, priv_push_back)
  1841.    #endif
  1842.  
  1843.    #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
  1844.    //! <b>Requires</b>: position must be a valid iterator of *this.
  1845.    //!
  1846.    //! <b>Effects</b>: Insert a copy of x before position.
  1847.    //!
  1848.    //! <b>Throws</b>: If memory allocation throws or T's copy/move constructor/assignment throws.
  1849.    //!
  1850.    //! <b>Complexity</b>: If position is end(), amortized constant time
  1851.    //!   Linear time otherwise.
  1852.    iterator insert(const_iterator position, const T &x);
  1853.  
  1854.    //! <b>Requires</b>: position must be a valid iterator of *this.
  1855.    //!
  1856.    //! <b>Effects</b>: Insert a new element before position with x's resources.
  1857.    //!
  1858.    //! <b>Throws</b>: If memory allocation throws.
  1859.    //!
  1860.    //! <b>Complexity</b>: If position is end(), amortized constant time
  1861.    //!   Linear time otherwise.
  1862.    iterator insert(const_iterator position, T &&x);
  1863.    #else
  1864.    BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, T, iterator, priv_insert, const_iterator, const_iterator)
  1865.    #endif
  1866.  
  1867.    //! <b>Requires</b>: p must be a valid iterator of *this.
  1868.    //!
  1869.    //! <b>Effects</b>: Insert n copies of x before pos.
  1870.    //!
  1871.    //! <b>Returns</b>: an iterator to the first inserted element or p if n is 0.
  1872.    //!
  1873.    //! <b>Throws</b>: If memory allocation throws or T's copy/move constructor throws.
  1874.    //!
  1875.    //! <b>Complexity</b>: Linear to n.
  1876.    iterator insert(const_iterator p, size_type n, const T& x)
  1877.    {
  1878.       BOOST_ASSERT(this->priv_in_range_or_end(p));
  1879.       container_detail::insert_n_copies_proxy<Allocator, T*> proxy(x);
  1880.       return this->priv_forward_range_insert(vector_iterator_get_ptr(p), n, proxy);
  1881.    }
  1882.  
  1883.    //! <b>Requires</b>: p must be a valid iterator of *this.
  1884.    //!
  1885.    //! <b>Effects</b>: Insert a copy of the [first, last) range before pos.
  1886.    //!
  1887.    //! <b>Returns</b>: an iterator to the first inserted element or pos if first == last.
  1888.    //!
  1889.    //! <b>Throws</b>: If memory allocation throws, T's constructor from a
  1890.    //!   dereferenced InpIt throws or T's copy/move constructor/assignment throws.
  1891.    //!
  1892.    //! <b>Complexity</b>: Linear to mars_boost::container::iterator_distance [first, last).
  1893.    template <class InIt>
  1894.    iterator insert(const_iterator pos, InIt first, InIt last
  1895.       #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
  1896.       , typename container_detail::disable_if_or
  1897.          < void
  1898.          , container_detail::is_convertible<InIt, size_type>
  1899.          , container_detail::is_not_input_iterator<InIt>
  1900.          >::type * = 0
  1901.       #endif
  1902.       )
  1903.    {
  1904.       BOOST_ASSERT(this->priv_in_range_or_end(pos));
  1905.       const size_type n_pos = pos - this->cbegin();
  1906.       iterator it(vector_iterator_get_ptr(pos));
  1907.       for(;first != last; ++first){
  1908.          it = this->emplace(it, *first);
  1909.          ++it;
  1910.       }
  1911.       return iterator(this->m_holder.start() + n_pos);
  1912.    }
  1913.  
  1914.    #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
  1915.    template <class FwdIt>
  1916.    iterator insert(const_iterator pos, FwdIt first, FwdIt last
  1917.       , typename container_detail::disable_if_or
  1918.          < void
  1919.          , container_detail::is_convertible<FwdIt, size_type>
  1920.          , container_detail::is_input_iterator<FwdIt>
  1921.          >::type * = 0
  1922.       )
  1923.    {
  1924.       BOOST_ASSERT(this->priv_in_range_or_end(pos));
  1925.       container_detail::insert_range_proxy<Allocator, FwdIt, T*> proxy(first);
  1926.       return this->priv_forward_range_insert(vector_iterator_get_ptr(pos), mars_boost::container::iterator_distance(first, last), proxy);
  1927.    }
  1928.    #endif
  1929.  
  1930.    //! <b>Requires</b>: p must be a valid iterator of *this. num, must
  1931.    //!   be equal to mars_boost::container::iterator_distance(first, last)
  1932.    //!
  1933.    //! <b>Effects</b>: Insert a copy of the [first, last) range before pos.
  1934.    //!
  1935.    //! <b>Returns</b>: an iterator to the first inserted element or pos if first == last.
  1936.    //!
  1937.    //! <b>Throws</b>: If memory allocation throws, T's constructor from a
  1938.    //!   dereferenced InpIt throws or T's copy/move constructor/assignment throws.
  1939.    //!
  1940.    //! <b>Complexity</b>: Linear to mars_boost::container::iterator_distance [first, last).
  1941.    //!
  1942.    //! <b>Note</b>: This function avoids a linear operation to calculate mars_boost::container::iterator_distance[first, last)
  1943.    //!   for forward and bidirectional iterators, and a one by one insertion for input iterators. This is a
  1944.    //!   a non-standard extension.
  1945.    #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
  1946.    template <class InIt>
  1947.    iterator insert(const_iterator pos, size_type num, InIt first, InIt last)
  1948.    {
  1949.       BOOST_ASSERT(this->priv_in_range_or_end(pos));
  1950.       BOOST_ASSERT(container_detail::is_input_iterator<InIt>::value ||
  1951.                    num == static_cast<size_type>(mars_boost::container::iterator_distance(first, last)));
  1952.       (void)last;
  1953.       container_detail::insert_range_proxy<Allocator, InIt, T*> proxy(first);
  1954.       return this->priv_forward_range_insert(vector_iterator_get_ptr(pos), num, proxy);
  1955.    }
  1956.    #endif
  1957.  
  1958.    #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
  1959.    //! <b>Requires</b>: position must be a valid iterator of *this.
  1960.    //!
  1961.    //! <b>Effects</b>: Insert a copy of the [il.begin(), il.end()) range before position.
  1962.    //!
  1963.    //! <b>Returns</b>: an iterator to the first inserted element or position if first == last.
  1964.    //!
  1965.    //! <b>Complexity</b>: Linear to the range [il.begin(), il.end()).
  1966.    iterator insert(const_iterator position, std::initializer_list<value_type> il)
  1967.    {
  1968.       //Assertion done in insert()
  1969.       return this->insert(position, il.begin(), il.end());
  1970.    }
  1971.    #endif
  1972.  
  1973.    //! <b>Effects</b>: Removes the last element from the container.
  1974.    //!
  1975.    //! <b>Throws</b>: Nothing.
  1976.    //!
  1977.    //! <b>Complexity</b>: Constant time.
  1978.    void pop_back() BOOST_NOEXCEPT_OR_NOTHROW
  1979.    {
  1980.       BOOST_ASSERT(!this->empty());
  1981.       //Destroy last element
  1982.       this->priv_destroy_last();
  1983.    }
  1984.  
  1985.    //! <b>Effects</b>: Erases the element at position pos.
  1986.    //!
  1987.    //! <b>Throws</b>: Nothing.
  1988.    //!
  1989.    //! <b>Complexity</b>: Linear to the elements between pos and the
  1990.    //!   last element. Constant if pos is the last element.
  1991.    iterator erase(const_iterator position)
  1992.    {
  1993.       BOOST_ASSERT(this->priv_in_range(position));
  1994.       const pointer p = vector_iterator_get_ptr(position);
  1995.       T *const pos_ptr = container_detail::to_raw_pointer(p);
  1996.       T *const beg_ptr = this->priv_raw_begin();
  1997.       T *const new_end_ptr = ::mars_boost::container::move(pos_ptr + 1, beg_ptr + this->m_holder.m_size, pos_ptr);
  1998.       //Move elements forward and destroy last
  1999.       this->priv_destroy_last(pos_ptr == new_end_ptr);
  2000.       return iterator(p);
  2001.    }
  2002.  
  2003.    //! <b>Effects</b>: Erases the elements pointed by [first, last).
  2004.    //!
  2005.    //! <b>Throws</b>: Nothing.
  2006.    //!
  2007.    //! <b>Complexity</b>: Linear to the distance between first and last
  2008.    //!   plus linear to the elements between pos and the last element.
  2009.    iterator erase(const_iterator first, const_iterator last)
  2010.    {
  2011.       BOOST_ASSERT(first == last ||
  2012.          (first < last && this->priv_in_range(first) && this->priv_in_range_or_end(last)));
  2013.       if (first != last){
  2014.          T* const old_end_ptr = this->priv_raw_end();
  2015.          T* const first_ptr = container_detail::to_raw_pointer(vector_iterator_get_ptr(first));
  2016.          T* const last_ptr  = container_detail::to_raw_pointer(vector_iterator_get_ptr(last));
  2017.          T* const ptr = container_detail::to_raw_pointer(mars_boost::container::move(last_ptr, old_end_ptr, first_ptr));
  2018.          this->priv_destroy_last_n(old_end_ptr - ptr);
  2019.       }
  2020.       return iterator(vector_iterator_get_ptr(first));
  2021.    }
  2022.  
  2023.    //! <b>Effects</b>: Swaps the contents of *this and x.
  2024.    //!
  2025.    //! <b>Throws</b>: Nothing.
  2026.    //!
  2027.    //! <b>Complexity</b>: Constant.
  2028.    void swap(vector& x)
  2029.       BOOST_NOEXCEPT_IF( ((allocator_traits_type::propagate_on_container_swap::value
  2030.                                     || allocator_traits_type::is_always_equal::value) &&
  2031.                                     !container_detail::is_version<Allocator, 0>::value))
  2032.    {
  2033.       this->priv_swap(x, container_detail::bool_<container_detail::is_version<Allocator, 0>::value>());
  2034.    }
  2035.  
  2036.    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
  2037.  
  2038.    //! <b>Effects</b>: Swaps the contents of *this and x.
  2039.    //!
  2040.    //! <b>Throws</b>: Nothing.
  2041.    //!
  2042.    //! <b>Complexity</b>: Linear
  2043.    //!
  2044.    //! <b>Note</b>: Non-standard extension to support static_vector
  2045.    template<class OtherAllocator>
  2046.    void swap(vector<T, OtherAllocator> & x
  2047.             , typename container_detail::enable_if_and
  2048.                      < void
  2049.                      , container_detail::is_version<OtherAllocator, 0>
  2050.                      , container_detail::is_different<OtherAllocator, allocator_type>
  2051.                      >::type * = 0
  2052.             )
  2053.    {  this->m_holder.deep_swap(x.m_holder); }
  2054.  
  2055.    #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
  2056.  
  2057.    //! <b>Effects</b>: Erases all the elements of the vector.
  2058.    //!
  2059.    //! <b>Throws</b>: Nothing.
  2060.    //!
  2061.    //! <b>Complexity</b>: Linear to the number of elements in the container.
  2062.    void clear() BOOST_NOEXCEPT_OR_NOTHROW
  2063.    {  this->priv_destroy_all();  }
  2064.  
  2065.    //! <b>Effects</b>: Returns true if x and y are equal
  2066.    //!
  2067.    //! <b>Complexity</b>: Linear to the number of elements in the container.
  2068.    friend bool operator==(const vector& x, const vector& y)
  2069.    {  return x.size() == y.size() && ::mars_boost::container::algo_equal(x.begin(), x.end(), y.begin());  }
  2070.  
  2071.    //! <b>Effects</b>: Returns true if x and y are unequal
  2072.    //!
  2073.    //! <b>Complexity</b>: Linear to the number of elements in the container.
  2074.    friend bool operator!=(const vector& x, const vector& y)
  2075.    {  return !(x == y); }
  2076.  
  2077.    //! <b>Effects</b>: Returns true if x is less than y
  2078.    //!
  2079.    //! <b>Complexity</b>: Linear to the number of elements in the container.
  2080.    friend bool operator<(const vector& x, const vector& y)
  2081.    {
  2082.       const_iterator first1(x.cbegin()), first2(y.cbegin());
  2083.       const const_iterator last1(x.cend()), last2(y.cend());
  2084.       for ( ; (first1 != last1) && (first2 != last2); ++first1, ++first2 ) {
  2085.          if (*first1 < *first2) return true;
  2086.          if (*first2 < *first1) return false;
  2087.       }
  2088.       return (first1 == last1) && (first2 != last2);
  2089.    }
  2090.  
  2091.    //! <b>Effects</b>: Returns true if x is greater than y
  2092.    //!
  2093.    //! <b>Complexity</b>: Linear to the number of elements in the container.
  2094.    friend bool operator>(const vector& x, const vector& y)
  2095.    {  return y < x;  }
  2096.  
  2097.    //! <b>Effects</b>: Returns true if x is equal or less than y
  2098.    //!
  2099.    //! <b>Complexity</b>: Linear to the number of elements in the container.
  2100.    friend bool operator<=(const vector& x, const vector& y)
  2101.    {  return !(y < x);  }
  2102.  
  2103.    //! <b>Effects</b>: Returns true if x is equal or greater than y
  2104.    //!
  2105.    //! <b>Complexity</b>: Linear to the number of elements in the container.
  2106.    friend bool operator>=(const vector& x, const vector& y)
  2107.    {  return !(x < y);  }
  2108.  
  2109.    //! <b>Effects</b>: x.swap(y)
  2110.    //!
  2111.    //! <b>Complexity</b>: Constant.
  2112.    friend void swap(vector& x, vector& y)
  2113.    {  x.swap(y);  }
  2114.  
  2115.    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
  2116.    //! <b>Effects</b>: If n is less than or equal to capacity(), this call has no
  2117.    //!   effect. Otherwise, it is a request for allocation of additional memory
  2118.    //!   (memory expansion) that will not invalidate iterators.
  2119.    //!   If the request is successful, then capacity() is greater than or equal to
  2120.    //!   n; otherwise, capacity() is unchanged. In either case, size() is unchanged.
  2121.    //!
  2122.    //! <b>Throws</b>: If memory allocation allocation throws or T's copy/move constructor throws.
  2123.    //!
  2124.    //! <b>Note</b>: Non-standard extension.
  2125.    bool stable_reserve(size_type new_cap)
  2126.    {
  2127.       const size_type cp = this->capacity();
  2128.       return cp >= new_cap || (alloc_version::value == 2 && this->m_holder.try_expand_fwd(new_cap - cp));
  2129.    }
  2130.  
  2131.    //Absolutely experimental. This function might change, disappear or simply crash!
  2132.    template<class BiDirPosConstIt, class BiDirValueIt>
  2133.    void insert_ordered_at(const size_type element_count, BiDirPosConstIt last_position_it, BiDirValueIt last_value_it)
  2134.    {
  2135.       typedef container_detail::vector_insert_ordered_cursor<BiDirPosConstIt, BiDirValueIt> inserter_t;
  2136.       return this->priv_insert_ordered_at(element_count, inserter_t(last_position_it, last_value_it));
  2137.    }
  2138.  
  2139.    template<class BidirIt>
  2140.    void merge(BidirIt first, BidirIt last)
  2141.    {  this->merge(first, last, value_less());  }
  2142.  
  2143.    template<class BidirIt, class Compare>
  2144.    void merge(BidirIt first, BidirIt last, Compare comp)
  2145.    {  this->priv_merge(container_detail::false_type(), first, last, comp);  }
  2146.  
  2147.    template<class BidirIt>
  2148.    void merge_unique(BidirIt first, BidirIt last)
  2149.    {  this->priv_merge(container_detail::true_type(),  first, last, value_less());  }
  2150.  
  2151.    template<class BidirIt, class Compare>
  2152.    void merge_unique(BidirIt first, BidirIt last, Compare comp)
  2153.    {  this->priv_merge(container_detail::true_type(),  first, last, comp);  }
  2154.  
  2155.    private:
  2156.    template<class PositionValue>
  2157.    void priv_insert_ordered_at(const size_type element_count, PositionValue position_value)
  2158.    {
  2159.       const size_type old_size_pos = this->size();
  2160.       this->reserve(old_size_pos + element_count);
  2161.       T* const begin_ptr = this->priv_raw_begin();
  2162.       size_type insertions_left = element_count;
  2163.       size_type prev_pos = old_size_pos;
  2164.       size_type old_hole_size = element_count;
  2165.  
  2166.       //Exception rollback. If any copy throws before the hole is filled, values
  2167.       //already inserted/copied at the end of the buffer will be destroyed.
  2168.       typename value_traits::ArrayDestructor past_hole_values_destroyer
  2169.          (begin_ptr + old_size_pos + element_count, this->m_holder.alloc(), size_type(0u));
  2170.       //Loop for each insertion backwards, first moving the elements after the insertion point,
  2171.       //then inserting the element.
  2172.       while(insertions_left){
  2173.          --position_value;
  2174.          size_type const pos = position_value.get_pos();
  2175.          BOOST_ASSERT(pos != size_type(-1) && pos <= old_size_pos && pos <= prev_pos);
  2176.          //If needed shift the range after the insertion point and the previous insertion point.
  2177.          //Function will take care if the shift crosses the size() boundary, using copy/move
  2178.          //or uninitialized copy/move if necessary.
  2179.          size_type new_hole_size = (pos != prev_pos)
  2180.             ? priv_insert_ordered_at_shift_range(pos, prev_pos, this->size(), insertions_left)
  2181.             : old_hole_size
  2182.             ;
  2183.          if(new_hole_size){
  2184.             //The hole was reduced by priv_insert_ordered_at_shift_range so expand exception rollback range backwards
  2185.             past_hole_values_destroyer.increment_size_backwards(prev_pos - pos);
  2186.             //Insert the new value in the hole
  2187.             allocator_traits_type::construct(this->m_holder.alloc(), begin_ptr + pos + insertions_left - 1, position_value.get_val());
  2188.             if(--new_hole_size){
  2189.                //The hole was reduced by the new insertion by one
  2190.                past_hole_values_destroyer.increment_size_backwards(size_type(1u));
  2191.             }
  2192.             else{
  2193.                //Hole was just filled, disable exception rollback and change vector size
  2194.                past_hole_values_destroyer.release();
  2195.                this->m_holder.m_size += element_count;
  2196.             }
  2197.          }
  2198.          else{
  2199.             if(old_hole_size){
  2200.                //Hole was just filled by priv_insert_ordered_at_shift_range, disable exception rollback and change vector size
  2201.                past_hole_values_destroyer.release();
  2202.                this->m_holder.m_size += element_count;
  2203.             }
  2204.             //Insert the new value in the already constructed range
  2205.             begin_ptr[pos + insertions_left - 1] = position_value.get_val();
  2206.          }
  2207.          --insertions_left;
  2208.          old_hole_size = new_hole_size;
  2209.          prev_pos = pos;
  2210.       }
  2211.    }
  2212.  
  2213.    template<class UniqueBool, class BidirIt, class Compare>
  2214.    void priv_merge(UniqueBool, BidirIt first, BidirIt last, Compare comp)
  2215.    {
  2216.       size_type const n = static_cast<size_type>(mars_boost::container::iterator_distance(first, last));
  2217.       size_type const s = this->size();
  2218.       if(BOOST_LIKELY(s)){
  2219.          size_type const c = this->capacity();
  2220.          size_type const free_c = (c - s);
  2221.          //Use a new buffer if current one is too small for new elements,
  2222.          //or there is no room for position indexes
  2223.          if(free_c < n){
  2224.             size_type const new_size = s + n;
  2225.             size_type new_cap = new_size;
  2226.             pointer p = pointer();
  2227.             p = this->m_holder.allocation_command(allocate_new, new_size, new_cap, p);
  2228.             this->priv_merge_in_new_buffer(UniqueBool(), first, n, comp, p, new_cap);
  2229.          }
  2230.          else if(!UniqueBool::value && free_c >= n){
  2231.             typedef container_detail::vector_merge_cursor<T, size_type, BidirIt, Compare> inserter_t;
  2232.             T* const pbeg = this->priv_raw_begin();
  2233.             return this->priv_insert_ordered_at(n, inserter_t(pbeg, pbeg + s, last, comp));
  2234.          }
  2235.          else{ //UniqueBool::value == true and free_c >= n
  2236.             std::size_t remaining = n;
  2237.             static const std::size_t PosCount = 64u;
  2238.             size_type positions[PosCount];
  2239.             size_type *indexes = 0;
  2240.             while(remaining){
  2241.                //Query for room to store indexes in the remaining buffer
  2242.                uintptr_t const szt_align_mask = container_detail::alignment_of<size_type>::value - 1;
  2243.                mars_boost::uintptr_t const addr = mars_boost::uintptr_t(this->priv_raw_begin() + s + n);
  2244.                mars_boost::uintptr_t const capaddr = mars_boost::uintptr_t(this->priv_raw_begin() + c);
  2245.                mars_boost::uintptr_t const aligned_addr = (addr + szt_align_mask) & ~szt_align_mask;
  2246.                indexes =  reinterpret_cast<size_type *>(aligned_addr);
  2247.                std::size_t index_capacity = (aligned_addr >= capaddr) ? 0u : (capaddr - addr)/sizeof(size_type);
  2248.  
  2249.                //Capacity is constant, we're not going to change it
  2250.                if(index_capacity < PosCount){
  2251.                   indexes =  positions;
  2252.                   index_capacity = PosCount;
  2253.                }
  2254.                if(index_capacity > remaining)
  2255.                   index_capacity = remaining;
  2256.                BidirIt limit = first;
  2257.                mars_boost::container::iterator_advance(limit, index_capacity);
  2258.                this->priv_insert_ordered_range(UniqueBool(), index_capacity, first, limit, indexes, comp);
  2259.                first = limit;
  2260.                remaining -= index_capacity;
  2261.             }
  2262.          }
  2263.       }
  2264.       else{
  2265.          this->insert(this->cend(), n, first, last);
  2266.       }
  2267.    }
  2268.  
  2269.    template <class UniqueBool, class BidirIt, class Compare>
  2270.    void priv_insert_ordered_range
  2271.       (UniqueBool, size_type const n, BidirIt first, BidirIt const last, size_type positions[], Compare comp)
  2272.    {
  2273.       //Linear: at most N + M -1 comparisons
  2274.       //Log: MlogN
  2275.       //Average
  2276.       //Linear: N + M - 2
  2277.       //Log: MlogN
  2278.       //N+M - 2
  2279.       //N
  2280.       //(N+M)/2 < MlogN
  2281.       //(N/M+1)/2 <= logN
  2282.       //bool const linear = !s || !n || (s <= n) || ((s+n)/n/2 < logN);
  2283.       size_type const s = this->size();
  2284.       size_type remaining = n;
  2285.       T* const pbeg = this->priv_raw_begin();
  2286.       T* const pend = pbeg + s;
  2287.       T* pcur = pbeg;
  2288.       size_type *position = positions;
  2289.       size_type added_in_middle = 0;
  2290.       if(first != last && pcur != pend){
  2291.          while(1){
  2292.             //maintain stability moving external values only if they are strictly less
  2293.             if(comp(*first, *pcur)) {
  2294.                *position = static_cast<size_type>(pcur - pbeg);
  2295.                BOOST_ASSERT((position == positions) || (*(position-1) == size_type(-1)) || (*(position-1) <= *position));
  2296.                ++position;
  2297.                ++added_in_middle;
  2298.                --remaining;
  2299.                if(++first == last)  break;
  2300.             }
  2301.             else if(UniqueBool::value && !comp(*pcur, *first)){
  2302.                *position = size_type(-1);
  2303.                ++position;
  2304.                --remaining;
  2305.                if(++first == last)  break;
  2306.             }
  2307.             else{
  2308.                if(++pcur == pend)   break;
  2309.             }
  2310.          }
  2311.       }
  2312.       this->insert_ordered_at(added_in_middle, position, first);
  2313.       this->insert(this->cend(), remaining, first, last);
  2314.    }
  2315.  
  2316.    template<class UniqueBool, class FwdIt, class Compare>
  2317.    void priv_merge_in_new_buffer
  2318.       (UniqueBool, FwdIt first, size_type n, Compare comp, pointer new_storage, size_type const new_cap)
  2319.    {
  2320.       BOOST_ASSERT((new_cap >= this->size() ) && (new_cap - this->size()) >= n);
  2321.       allocator_type &a = this->m_holder.alloc();
  2322.       typename value_traits::ArrayDeallocator new_buffer_deallocator(new_storage, a, new_cap);
  2323.       typename value_traits::ArrayDestructor  new_values_destroyer(new_storage, a, 0u);
  2324.       T* pbeg  = this->priv_raw_begin();
  2325.       size_type const old_size = this->size();
  2326.       T* const pend = pbeg + old_size;
  2327.       T* d_first = container_detail::to_raw_pointer(new_storage);
  2328.       size_type added = n;
  2329.       //Merge in new buffer loop
  2330.       while(1){
  2331.          if(!n) {
  2332.             ::mars_boost::container::uninitialized_move_alloc(this->m_holder.alloc(), pbeg, pend, d_first);
  2333.             break;
  2334.          }
  2335.          else if(pbeg == pend) {
  2336.             ::mars_boost::container::uninitialized_move_alloc_n(this->m_holder.alloc(), first, n, d_first);
  2337.             break;
  2338.          }
  2339.          //maintain stability moving external values only if they are strictly less
  2340.          else if(comp(*first, *pbeg)) {
  2341.             allocator_traits_type::construct( this->m_holder.alloc(), d_first, ::mars_boost::move(*first) );
  2342.             new_values_destroyer.increment_size(1u);
  2343.             ++first;
  2344.             --n;
  2345.             ++d_first;
  2346.          }
  2347.          else if(UniqueBool::value && !comp(*pbeg, *first)){
  2348.             ++first;
  2349.             --n;
  2350.             --added;
  2351.          }
  2352.          else{
  2353.             allocator_traits_type::construct( this->m_holder.alloc(), d_first, ::mars_boost::move(*pbeg) );
  2354.             new_values_destroyer.increment_size(1u);
  2355.             ++pbeg;
  2356.             ++d_first;
  2357.          }
  2358.       }
  2359.  
  2360.       //Nothrow operations
  2361.       pointer const old_p     = this->m_holder.start();
  2362.       size_type const old_cap = this->m_holder.capacity();
  2363.       mars_boost::container::destroy_alloc_n(a, container_detail::to_raw_pointer(old_p), old_size);
  2364.       a.deallocate(old_p, old_cap);
  2365.       this->m_holder.m_size = old_size + added;
  2366.       this->m_holder.start(new_storage);
  2367.       this->m_holder.capacity(new_cap);
  2368.       new_buffer_deallocator.release();
  2369.       new_values_destroyer.release();
  2370.    }
  2371.  
  2372.    bool room_enough() const
  2373.    {  return this->m_holder.m_size < this->m_holder.capacity();   }
  2374.  
  2375.    pointer back_ptr() const
  2376.    {  return this->m_holder.start() + this->m_holder.m_size;  }
  2377.  
  2378.    size_type priv_index_of(pointer p) const
  2379.    {
  2380.       BOOST_ASSERT(this->m_holder.start() <= p);
  2381.       BOOST_ASSERT(p <= (this->m_holder.start()+this->size()));
  2382.       return static_cast<size_type>(p - this->m_holder.start());
  2383.    }
  2384.  
  2385.    template<class OtherAllocator>
  2386.    void priv_move_assign(BOOST_RV_REF_BEG vector<T, OtherAllocator> BOOST_RV_REF_END x
  2387.       , typename container_detail::enable_if_c
  2388.          < container_detail::is_version<OtherAllocator, 0>::value >::type * = 0)
  2389.    {
  2390.       if(!container_detail::is_same<OtherAllocator, allocator_type>::value &&
  2391.           this->capacity() < x.size()){
  2392.          throw_bad_alloc();
  2393.       }
  2394.       T* const this_start  = this->priv_raw_begin();
  2395.       T* const other_start = x.priv_raw_begin();
  2396.       const size_type this_sz  = m_holder.m_size;
  2397.       const size_type other_sz = static_cast<size_type>(x.m_holder.m_size);
  2398.       mars_boost::container::move_assign_range_alloc_n(this->m_holder.alloc(), other_start, other_sz, this_start, this_sz);
  2399.       this->m_holder.m_size = other_sz;
  2400.    }
  2401.  
  2402.    template<class OtherAllocator>
  2403.    void priv_move_assign(BOOST_RV_REF_BEG vector<T, OtherAllocator> BOOST_RV_REF_END x
  2404.       , typename container_detail::disable_if_or
  2405.          < void
  2406.          , container_detail::is_version<OtherAllocator, 0>
  2407.          , container_detail::is_different<OtherAllocator, allocator_type>
  2408.          >::type * = 0)
  2409.    {
  2410.       //for move assignment, no aliasing (&x != this) is assummed.
  2411.       BOOST_ASSERT(this != &x);
  2412.       allocator_type &this_alloc = this->m_holder.alloc();
  2413.       allocator_type &x_alloc    = x.m_holder.alloc();
  2414.       const bool propagate_alloc = allocator_traits_type::propagate_on_container_move_assignment::value;
  2415.  
  2416.       const bool is_propagable_from_x = is_propagable_from(x_alloc, x.m_holder.start(), this_alloc, propagate_alloc);
  2417.       const bool is_propagable_from_t = is_propagable_from(this_alloc, m_holder.start(), x_alloc,   propagate_alloc);
  2418.       const bool are_both_propagable  = is_propagable_from_x && is_propagable_from_t;
  2419.  
  2420.       //Resources can be transferred if both allocators are
  2421.       //going to be equal after this function (either propagated or already equal)
  2422.       if(are_both_propagable){
  2423.          //Destroy objects but retain memory in case x reuses it in the future
  2424.          this->clear();
  2425.          this->m_holder.swap_resources(x.m_holder);
  2426.       }
  2427.       else if(is_propagable_from_x){
  2428.          this->clear();
  2429.          this->m_holder.alloc().deallocate(this->m_holder.m_start, this->m_holder.m_capacity);
  2430.          this->m_holder.steal_resources(x.m_holder);
  2431.       }
  2432.       //Else do a one by one move
  2433.       else{
  2434.          this->assign( mars_boost::make_move_iterator(container_detail::iterator_to_raw_pointer(x.begin()))
  2435.                      , mars_boost::make_move_iterator(container_detail::iterator_to_raw_pointer(x.end()  ))
  2436.                      );
  2437.       }
  2438.       //Move allocator if needed
  2439.       container_detail::move_alloc(this_alloc, x_alloc, container_detail::bool_<propagate_alloc>());
  2440.    }
  2441.  
  2442.    template<class OtherAllocator>
  2443.    void priv_copy_assign(const vector<T, OtherAllocator> &x
  2444.       , typename container_detail::enable_if_c
  2445.          < container_detail::is_version<OtherAllocator, 0>::value >::type * = 0)
  2446.    {
  2447.       if(!container_detail::is_same<OtherAllocator, allocator_type>::value &&
  2448.          this->capacity() < x.size()){
  2449.          throw_bad_alloc();
  2450.       }
  2451.       T* const this_start  = this->priv_raw_begin();
  2452.       T* const other_start = x.priv_raw_begin();
  2453.       const size_type this_sz  = m_holder.m_size;
  2454.       const size_type other_sz = static_cast<size_type>(x.m_holder.m_size);
  2455.       mars_boost::container::copy_assign_range_alloc_n(this->m_holder.alloc(), other_start, other_sz, this_start, this_sz);
  2456.       this->m_holder.m_size = other_sz;
  2457.    }
  2458.  
  2459.    template<class OtherAllocator>
  2460.    typename container_detail::disable_if_or
  2461.       < void
  2462.       , container_detail::is_version<OtherAllocator, 0>
  2463.       , container_detail::is_different<OtherAllocator, allocator_type>
  2464.       >::type
  2465.       priv_copy_assign(const vector<T, OtherAllocator> &x)
  2466.    {
  2467.       allocator_type &this_alloc     = this->m_holder.alloc();
  2468.       const allocator_type &x_alloc  = x.m_holder.alloc();
  2469.       container_detail::bool_<allocator_traits_type::
  2470.          propagate_on_container_copy_assignment::value> flag;
  2471.       if(flag && this_alloc != x_alloc){
  2472.          this->clear();
  2473.          this->shrink_to_fit();
  2474.       }
  2475.       container_detail::assign_alloc(this_alloc, x_alloc, flag);
  2476.       this->assign( x.priv_raw_begin(), x.priv_raw_end() );
  2477.    }
  2478.  
  2479.    template<class Vector>  //Template it to avoid it in explicit instantiations
  2480.    void priv_swap(Vector &x, container_detail::true_type)   //version_0
  2481.    {  this->m_holder.deep_swap(x.m_holder);  }
  2482.  
  2483.    template<class Vector>  //Template it to avoid it in explicit instantiations
  2484.    void priv_swap(Vector &x, container_detail::false_type)  //version_N
  2485.    {
  2486.       const bool propagate_alloc = allocator_traits_type::propagate_on_container_swap::value;
  2487.       if(are_swap_propagable( this->get_stored_allocator(), this->m_holder.start()
  2488.                             , x.get_stored_allocator(), x.m_holder.start(), propagate_alloc)){
  2489.          //Just swap internals
  2490.          this->m_holder.swap_resources(x.m_holder);
  2491.       }
  2492.       else{
  2493.          //Else swap element by element...
  2494.          bool const t_smaller = this->size() < x.size();
  2495.          vector &sml = t_smaller ? *this : x;
  2496.          vector &big = t_smaller ? x : *this;
  2497.  
  2498.          size_type const common_elements = sml.size();
  2499.          for(size_type i = 0; i != common_elements; ++i){
  2500.             mars_boost::adl_move_swap(sml[i], big[i]);
  2501.          }
  2502.          //... and move-insert the remaining range
  2503.          sml.insert( sml.cend()
  2504.                    , mars_boost::make_move_iterator(container_detail::iterator_to_raw_pointer(big.nth(common_elements)))
  2505.                    , mars_boost::make_move_iterator(container_detail::iterator_to_raw_pointer(big.end()))
  2506.                    );
  2507.          //Destroy remaining elements
  2508.          big.erase(big.nth(common_elements), big.cend());
  2509.       }
  2510.       //And now swap the allocator
  2511.       container_detail::swap_alloc(this->m_holder.alloc(), x.m_holder.alloc(), container_detail::bool_<propagate_alloc>());
  2512.    }
  2513.  
  2514.    void priv_reserve_no_capacity(size_type, version_0)
  2515.    {  throw_bad_alloc();  }
  2516.  
  2517.    container_detail::insert_range_proxy<Allocator, mars_boost::move_iterator<T*>, T*> priv_dummy_empty_proxy()
  2518.    {
  2519.       return container_detail::insert_range_proxy<Allocator, mars_boost::move_iterator<T*>, T*>
  2520.          (::mars_boost::make_move_iterator((T *)0));
  2521.    }
  2522.  
  2523.    void priv_reserve_no_capacity(size_type new_cap, version_1)
  2524.    {
  2525.       //There is not enough memory, allocate a new buffer
  2526.       //Pass the hint so that allocators can take advantage of this.
  2527.       pointer const p = allocator_traits_type::allocate(this->m_holder.alloc(), new_cap, this->m_holder.m_start);
  2528.       //We will reuse insert code, so create a dummy input iterator
  2529.       this->priv_forward_range_insert_new_allocation
  2530.          ( container_detail::to_raw_pointer(p), new_cap, this->priv_raw_end(), 0, this->priv_dummy_empty_proxy());
  2531.    }
  2532.  
  2533.    void priv_reserve_no_capacity(size_type new_cap, version_2)
  2534.    {
  2535.       //There is not enough memory, allocate a new
  2536.       //buffer or expand the old one.
  2537.       bool same_buffer_start;
  2538.       size_type real_cap = 0;
  2539.       pointer reuse = 0;
  2540.       pointer const ret(this->m_holder.allocation_command(allocate_new | expand_fwd | expand_bwd, new_cap, real_cap = new_cap, reuse));
  2541.  
  2542.       //Check for forward expansion
  2543.       same_buffer_start = reuse && this->m_holder.start() == ret;
  2544.       if(same_buffer_start){
  2545.          #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
  2546.          ++this->num_expand_fwd;
  2547.          #endif
  2548.          this->m_holder.capacity(real_cap);
  2549.       }
  2550.       else{ //If there is no forward expansion, move objects, we will reuse insertion code
  2551.          T * const new_mem = container_detail::to_raw_pointer(ret);
  2552.          T * const ins_pos = this->priv_raw_end();
  2553.          if(reuse){   //Backwards (and possibly forward) expansion
  2554.             #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
  2555.             ++this->num_expand_bwd;
  2556.             #endif
  2557.             this->priv_forward_range_insert_expand_backwards
  2558.                ( new_mem , real_cap, ins_pos, 0, this->priv_dummy_empty_proxy());
  2559.          }
  2560.          else{ //New buffer
  2561.             #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
  2562.             ++this->num_alloc;
  2563.             #endif
  2564.             this->priv_forward_range_insert_new_allocation
  2565.                ( new_mem, real_cap, ins_pos, 0, this->priv_dummy_empty_proxy());
  2566.          }
  2567.       }
  2568.    }
  2569.  
  2570.    void priv_destroy_last(const bool moved = false) BOOST_NOEXCEPT_OR_NOTHROW
  2571.    {
  2572.       (void)moved;
  2573.       if(!(value_traits::trivial_dctr || (value_traits::trivial_dctr_after_move && moved))){
  2574.          value_type* const p = this->priv_raw_end() - 1;
  2575.          allocator_traits_type::destroy(this->get_stored_allocator(), p);
  2576.       }
  2577.       --this->m_holder.m_size;
  2578.    }
  2579.  
  2580.    void priv_destroy_last_n(const size_type n) BOOST_NOEXCEPT_OR_NOTHROW
  2581.    {
  2582.       BOOST_ASSERT(n <= this->m_holder.m_size);
  2583.       if(!value_traits::trivial_dctr){
  2584.          T* const destroy_pos = this->priv_raw_begin() + (this->m_holder.m_size-n);
  2585.          mars_boost::container::destroy_alloc_n(this->get_stored_allocator(), destroy_pos, n);
  2586.       }
  2587.       this->m_holder.m_size -= n;
  2588.    }
  2589.  
  2590.    template<class InpIt>
  2591.    void priv_uninitialized_construct_at_end(InpIt first, InpIt last)
  2592.    {
  2593.       T* const old_end_pos = this->priv_raw_end();
  2594.       T* const new_end_pos = mars_boost::container::uninitialized_copy_alloc(this->m_holder.alloc(), first, last, old_end_pos);
  2595.       this->m_holder.m_size += new_end_pos - old_end_pos;
  2596.    }
  2597.  
  2598.    void priv_destroy_all() BOOST_NOEXCEPT_OR_NOTHROW
  2599.    {
  2600.       mars_boost::container::destroy_alloc_n
  2601.          (this->get_stored_allocator(), this->priv_raw_begin(), this->m_holder.m_size);
  2602.       this->m_holder.m_size = 0;
  2603.    }
  2604.  
  2605.    template<class U>
  2606.    iterator priv_insert(const const_iterator &p, BOOST_FWD_REF(U) x)
  2607.    {
  2608.       BOOST_ASSERT(this->priv_in_range_or_end(p));
  2609.       return this->priv_forward_range_insert
  2610.          ( vector_iterator_get_ptr(p), 1, container_detail::get_insert_value_proxy<T*, Allocator>(::mars_boost::forward<U>(x)));
  2611.    }
  2612.  
  2613.    container_detail::insert_copy_proxy<Allocator, T*> priv_single_insert_proxy(const T &x)
  2614.    {  return container_detail::insert_copy_proxy<Allocator, T*> (x);  }
  2615.  
  2616.    container_detail::insert_move_proxy<Allocator, T*> priv_single_insert_proxy(BOOST_RV_REF(T) x)
  2617.    {  return container_detail::insert_move_proxy<Allocator, T*> (x);  }
  2618.  
  2619.    template <class U>
  2620.    void priv_push_back(BOOST_FWD_REF(U) u)
  2621.    {
  2622.       if (BOOST_LIKELY(this->room_enough())){
  2623.          //There is more memory, just construct a new object at the end
  2624.          allocator_traits_type::construct
  2625.             ( this->m_holder.alloc(), this->priv_raw_end(), ::mars_boost::forward<U>(u) );
  2626.          ++this->m_holder.m_size;
  2627.       }
  2628.       else{
  2629.          this->priv_forward_range_insert_no_capacity
  2630.             ( this->back_ptr(), 1
  2631.             , this->priv_single_insert_proxy(::mars_boost::forward<U>(u)), alloc_version());
  2632.       }
  2633.    }
  2634.  
  2635.    container_detail::insert_n_copies_proxy<Allocator, T*> priv_resize_proxy(const T &x)
  2636.    {  return container_detail::insert_n_copies_proxy<Allocator, T*>(x);   }
  2637.  
  2638.    container_detail::insert_default_initialized_n_proxy<Allocator, T*> priv_resize_proxy(default_init_t)
  2639.    {  return container_detail::insert_default_initialized_n_proxy<Allocator, T*>();  }
  2640.  
  2641.    container_detail::insert_value_initialized_n_proxy<Allocator, T*> priv_resize_proxy(value_init_t)
  2642.    {  return container_detail::insert_value_initialized_n_proxy<Allocator, T*>(); }
  2643.  
  2644.    template <class U>
  2645.    void priv_resize(size_type new_size, const U& u)
  2646.    {
  2647.       const size_type sz = this->size();
  2648.       if (new_size < sz){
  2649.          //Destroy last elements
  2650.          this->priv_destroy_last_n(sz - new_size);
  2651.       }
  2652.       else{
  2653.          const size_type n = new_size - this->size();
  2654.          this->priv_forward_range_insert_at_end(n, this->priv_resize_proxy(u), alloc_version());
  2655.       }
  2656.    }
  2657.  
  2658.    void priv_shrink_to_fit(version_0) BOOST_NOEXCEPT_OR_NOTHROW
  2659.    {}
  2660.  
  2661.    void priv_shrink_to_fit(version_1)
  2662.    {
  2663.       const size_type cp = this->m_holder.capacity();
  2664.       if(cp){
  2665.          const size_type sz = this->size();
  2666.          if(!sz){
  2667.             this->m_holder.alloc().deallocate(this->m_holder.m_start, cp);
  2668.             this->m_holder.m_start     = pointer();
  2669.             this->m_holder.m_capacity  = 0;
  2670.          }
  2671.          else if(sz < cp){
  2672.             //Allocate a new buffer.
  2673.             //Pass the hint so that allocators can take advantage of this.
  2674.             pointer const p = allocator_traits_type::allocate(this->m_holder.alloc(), sz, this->m_holder.m_start);
  2675.  
  2676.             //We will reuse insert code, so create a dummy input iterator
  2677.             #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
  2678.             ++this->num_alloc;
  2679.             #endif
  2680.             this->priv_forward_range_insert_new_allocation
  2681.                ( container_detail::to_raw_pointer(p), sz
  2682.                , this->priv_raw_begin(), 0, this->priv_dummy_empty_proxy());
  2683.          }
  2684.       }
  2685.    }
  2686.  
  2687.    void priv_shrink_to_fit(version_2) BOOST_NOEXCEPT_OR_NOTHROW
  2688.    {
  2689.       const size_type cp = this->m_holder.capacity();
  2690.       if(cp){
  2691.          const size_type sz = this->size();
  2692.          if(!sz){
  2693.             this->m_holder.alloc().deallocate(this->m_holder.m_start, cp);
  2694.             this->m_holder.m_start     = pointer();
  2695.             this->m_holder.m_capacity  = 0;
  2696.          }
  2697.          else{
  2698.             size_type received_size = sz;
  2699.             pointer reuse(this->m_holder.start());
  2700.             if(this->m_holder.allocation_command
  2701.                (shrink_in_place | nothrow_allocation, cp, received_size, reuse)){
  2702.                this->m_holder.capacity(received_size);
  2703.                #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
  2704.                ++this->num_shrink;
  2705.                #endif
  2706.             }
  2707.          }
  2708.       }
  2709.    }
  2710.  
  2711.    template <class InsertionProxy>
  2712.    iterator priv_forward_range_insert_no_capacity
  2713.       (const pointer &pos, const size_type, const InsertionProxy , version_0)
  2714.    {
  2715.       throw_bad_alloc();
  2716.       return iterator(pos);
  2717.    }
  2718.  
  2719.    template <class InsertionProxy>
  2720.    iterator priv_forward_range_insert_no_capacity
  2721.       (const pointer &pos, const size_type n, const InsertionProxy insert_range_proxy, version_1)
  2722.    {
  2723.       //Check if we have enough memory or try to expand current memory
  2724.       const size_type n_pos = pos - this->m_holder.start();
  2725.       T *const raw_pos = container_detail::to_raw_pointer(pos);
  2726.  
  2727.       const size_type new_cap = this->m_holder.next_capacity(n);
  2728.       //Pass the hint so that allocators can take advantage of this.
  2729.       T * const new_buf = container_detail::to_raw_pointer
  2730.          (allocator_traits_type::allocate(this->m_holder.alloc(), new_cap, this->m_holder.m_start));
  2731.       #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
  2732.       ++this->num_alloc;
  2733.       #endif
  2734.       this->priv_forward_range_insert_new_allocation
  2735.          ( new_buf, new_cap, raw_pos, n, insert_range_proxy);
  2736.       return iterator(this->m_holder.start() + n_pos);
  2737.    }
  2738.  
  2739.    template <class InsertionProxy>
  2740.    iterator priv_forward_range_insert_no_capacity
  2741.       (const pointer &pos, const size_type n, const InsertionProxy insert_range_proxy, version_2)
  2742.    {
  2743.       //Check if we have enough memory or try to expand current memory
  2744.       T *const raw_pos = container_detail::to_raw_pointer(pos);
  2745.       const size_type n_pos = raw_pos - this->priv_raw_begin();
  2746.  
  2747.       //There is not enough memory, allocate a new
  2748.       //buffer or expand the old one.
  2749.       size_type real_cap = this->m_holder.next_capacity(n);
  2750.       pointer reuse(this->m_holder.start());
  2751.       pointer const ret (this->m_holder.allocation_command
  2752.          (allocate_new | expand_fwd | expand_bwd, this->m_holder.m_size + n, real_cap, reuse));
  2753.  
  2754.       //Buffer reallocated
  2755.       if(reuse){
  2756.          //Forward expansion, delay insertion
  2757.          if(this->m_holder.start() == ret){
  2758.             #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
  2759.             ++this->num_expand_fwd;
  2760.             #endif
  2761.             this->m_holder.capacity(real_cap);
  2762.             //Expand forward
  2763.             this->priv_forward_range_insert_expand_forward(raw_pos, n, insert_range_proxy);
  2764.          }
  2765.          //Backwards (and possibly forward) expansion
  2766.          else{
  2767.             #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
  2768.             ++this->num_expand_bwd;
  2769.             #endif
  2770.             this->priv_forward_range_insert_expand_backwards
  2771.                (container_detail::to_raw_pointer(ret), real_cap, raw_pos, n, insert_range_proxy);
  2772.          }
  2773.       }
  2774.       //New buffer
  2775.       else{
  2776.          #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
  2777.          ++this->num_alloc;
  2778.          #endif
  2779.          this->priv_forward_range_insert_new_allocation
  2780.             ( container_detail::to_raw_pointer(ret), real_cap, raw_pos, n, insert_range_proxy);
  2781.       }
  2782.  
  2783.       return iterator(this->m_holder.start() + n_pos);
  2784.    }
  2785.  
  2786.    template <class InsertionProxy>
  2787.    iterator priv_forward_range_insert
  2788.       (const pointer &pos, const size_type n, const InsertionProxy insert_range_proxy)
  2789.    {
  2790.       BOOST_ASSERT(this->m_holder.capacity() >= this->m_holder.m_size);
  2791.       //Check if we have enough memory or try to expand current memory
  2792.       const size_type remaining = this->m_holder.capacity() - this->m_holder.m_size;
  2793.  
  2794.       bool same_buffer_start = n <= remaining;
  2795.       if (!same_buffer_start){
  2796.          return priv_forward_range_insert_no_capacity(pos, n, insert_range_proxy, alloc_version());
  2797.       }
  2798.       else{
  2799.          //Expand forward
  2800.          T *const raw_pos = container_detail::to_raw_pointer(pos);
  2801.          const size_type n_pos = raw_pos - this->priv_raw_begin();
  2802.          this->priv_forward_range_insert_expand_forward(raw_pos, n, insert_range_proxy);
  2803.          return iterator(this->m_holder.start() + n_pos);
  2804.       }
  2805.    }
  2806.  
  2807.    template <class InsertionProxy>
  2808.    iterator priv_forward_range_insert_at_end
  2809.       (const size_type n, const InsertionProxy insert_range_proxy, version_0)
  2810.    {
  2811.       //Check if we have enough memory or try to expand current memory
  2812.       const size_type remaining = this->m_holder.capacity() - this->m_holder.m_size;
  2813.  
  2814.       if (n > remaining){
  2815.          //This will trigger an error
  2816.          throw_bad_alloc();
  2817.       }
  2818.       this->priv_forward_range_insert_at_end_expand_forward(n, insert_range_proxy);
  2819.       return this->end();
  2820.    }
  2821.  
  2822.    template <class InsertionProxy, class AllocVersion>
  2823.    iterator priv_forward_range_insert_at_end
  2824.       (const size_type n, const InsertionProxy insert_range_proxy, AllocVersion)
  2825.    {
  2826.       return this->priv_forward_range_insert(this->back_ptr(), n, insert_range_proxy);
  2827.    }
  2828.  
  2829.    //Takes the range pointed by [first_pos, last_pos) and shifts it to the right
  2830.    //by 'shift_count'. 'limit_pos' marks the end of constructed elements.
  2831.    //
  2832.    //Precondition: first_pos <= last_pos <= limit_pos
  2833.    //
  2834.    //The shift operation might cross limit_pos so elements to moved beyond limit_pos
  2835.    //are uninitialized_moved with an allocator. Other elements are moved.
  2836.    //
  2837.    //The shift operation might left uninitialized elements after limit_pos
  2838.    //and the number of uninitialized elements is returned by the function.
  2839.    //
  2840.    //Old situation:
  2841.    //       first_pos   last_pos         old_limit
  2842.    //             |       |                  |
  2843.    // ____________V_______V__________________V_____________
  2844.    //|   prefix   | range |     suffix       |raw_mem      ~
  2845.    //|____________|_______|__________________|_____________~
  2846.    //
  2847.    //New situation in Case A (hole_size == 0):
  2848.    // range is moved through move assignments
  2849.    //
  2850.    //       first_pos   last_pos         limit_pos
  2851.    //             |       |                  |
  2852.    // ____________V_______V__________________V_____________
  2853.    //|   prefix'  |       |  | range |suffix'|raw_mem      ~
  2854.    //|________________+______|___^___|_______|_____________~
  2855.    //                 |          |
  2856.    //                 |_>_>_>_>_>^
  2857.    //
  2858.    //
  2859.    //New situation in Case B (hole_size >= 0):
  2860.    // range is moved through uninitialized moves
  2861.    //
  2862.    //       first_pos   last_pos         limit_pos
  2863.    //             |       |                  |
  2864.    // ____________V_______V__________________V________________
  2865.    //|    prefix' |       |                  | [hole] | range |
  2866.    //|_______________________________________|________|___^___|
  2867.    //                 |                                   |
  2868.    //                 |_>_>_>_>_>_>_>_>_>_>_>_>_>_>_>_>_>_^
  2869.    //
  2870.    //New situation in Case C (hole_size == 0):
  2871.    // range is moved through move assignments and uninitialized moves
  2872.    //
  2873.    //       first_pos   last_pos         limit_pos
  2874.    //             |       |                  |
  2875.    // ____________V_______V__________________V___
  2876.    //|   prefix'  |       |              | range |
  2877.    //|___________________________________|___^___|
  2878.    //                 |                      |
  2879.    //                 |_>_>_>_>_>_>_>_>_>_>_>^
  2880.    size_type priv_insert_ordered_at_shift_range
  2881.       (size_type first_pos, size_type last_pos, size_type limit_pos, size_type shift_count)
  2882.    {
  2883.       BOOST_ASSERT(first_pos <= last_pos);
  2884.       BOOST_ASSERT(last_pos <= limit_pos);
  2885.       //
  2886.       T* const begin_ptr = this->priv_raw_begin();
  2887.       T* const first_ptr = begin_ptr + first_pos;
  2888.       T* const last_ptr  = begin_ptr + last_pos;
  2889.  
  2890.       size_type hole_size = 0;
  2891.       //Case A:
  2892.       if((last_pos + shift_count) <= limit_pos){
  2893.          //All move assigned
  2894.          mars_boost::container::move_backward(first_ptr, last_ptr, last_ptr + shift_count);
  2895.       }
  2896.       //Case B:
  2897.       else if((first_pos + shift_count) >= limit_pos){
  2898.          //All uninitialized_moved
  2899.          ::mars_boost::container::uninitialized_move_alloc
  2900.             (this->m_holder.alloc(), first_ptr, last_ptr, first_ptr + shift_count);
  2901.          hole_size = first_pos + shift_count - limit_pos;
  2902.       }
  2903.       //Case C:
  2904.       else{
  2905.          //Some uninitialized_moved
  2906.          T* const limit_ptr    = begin_ptr + limit_pos;
  2907.          T* const boundary_ptr = limit_ptr - shift_count;
  2908.          ::mars_boost::container::uninitialized_move_alloc(this->m_holder.alloc(), boundary_ptr, last_ptr, limit_ptr);
  2909.          //The rest is move assigned
  2910.          mars_boost::container::move_backward(first_ptr, boundary_ptr, limit_ptr);
  2911.       }
  2912.       return hole_size;
  2913.    }
  2914.  
  2915.    private:
  2916.    T *priv_raw_begin() const
  2917.    {  return container_detail::to_raw_pointer(m_holder.start());  }
  2918.  
  2919.    T* priv_raw_end() const
  2920.    {  return this->priv_raw_begin() + this->m_holder.m_size;  }
  2921.  
  2922.    template <class InsertionProxy>
  2923.    void priv_forward_range_insert_at_end_expand_forward(const size_type n, InsertionProxy insert_range_proxy)
  2924.    {
  2925.       T* const old_finish = this->priv_raw_end();
  2926.       insert_range_proxy.uninitialized_copy_n_and_update(this->m_holder.alloc(), old_finish, n);
  2927.       this->m_holder.m_size += n;
  2928.    }
  2929.  
  2930.    template <class InsertionProxy>
  2931.    void priv_forward_range_insert_expand_forward(T* const pos, const size_type n, InsertionProxy insert_range_proxy)
  2932.    {
  2933.       //n can't be 0, because there is nothing to do in that case
  2934.       if(BOOST_UNLIKELY(!n)) return;
  2935.       //There is enough memory
  2936.       T* const old_finish = this->priv_raw_end();
  2937.       const size_type elems_after = old_finish - pos;
  2938.  
  2939.       if (!elems_after){
  2940.          insert_range_proxy.uninitialized_copy_n_and_update(this->m_holder.alloc(), old_finish, n);
  2941.          this->m_holder.m_size += n;
  2942.       }
  2943.       else if (elems_after >= n){
  2944.          //New elements can be just copied.
  2945.          //Move to uninitialized memory last objects
  2946.          ::mars_boost::container::uninitialized_move_alloc
  2947.             (this->m_holder.alloc(), old_finish - n, old_finish, old_finish);
  2948.          this->m_holder.m_size += n;
  2949.          //Copy previous to last objects to the initialized end
  2950.          mars_boost::container::move_backward(pos, old_finish - n, old_finish);
  2951.          //Insert new objects in the pos
  2952.          insert_range_proxy.copy_n_and_update(this->m_holder.alloc(), pos, n);
  2953.       }
  2954.       else {
  2955.          //The new elements don't fit in the [pos, end()) range.
  2956.  
  2957.          //Copy old [pos, end()) elements to the uninitialized memory (a gap is created)
  2958.          ::mars_boost::container::uninitialized_move_alloc(this-