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

File indexing completed on 2025-09-15 08:31:03

 //////////////////////////////////////////////////////////////////////////////
 //
 // (C) Copyright Ion Gaztanaga 2008-2015. Distributed under the Boost
 // Software License, Version 1.0. (See accompanying file
 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
 //
 // See http://www.boost.org/libs/container for documentation.
 //
 //////////////////////////////////////////////////////////////////////////////
 // Stable vector.
 //
 // Copyright 2008 Joaquin M Lopez Munoz.
 // Distributed under the Boost Software License, Version 1.0.
 // (See accompanying file LICENSE_1_0.txt or copy at
 // http://www.boost.org/LICENSE_1_0.txt)
 //
 //////////////////////////////////////////////////////////////////////////////
 
 #ifndef BOOST_CONTAINER_STABLE_VECTOR_HPP
 #define BOOST_CONTAINER_STABLE_VECTOR_HPP
 
 #ifndef BOOST_CONFIG_HPP
 #  include <boost/config.hpp>
 #endif
 
 #if defined(BOOST_HAS_PRAGMA_ONCE)
 #  pragma once
 #endif
 
 #include <boost/container/detail/config_begin.hpp>
 #include <boost/container/detail/workaround.hpp>
 
 // container
 #include <boost/container/allocator_traits.hpp>
 #include <boost/container/container_fwd.hpp>
 #include <boost/container/new_allocator.hpp> //new_allocator
 #include <boost/container/throw_exception.hpp>
 // container/detail
 #include <boost/container/detail/addressof.hpp>
 #include <boost/container/detail/algorithm.hpp> //algo_equal(), algo_lexicographical_compare
 #include <boost/container/detail/alloc_helpers.hpp>
 #include <boost/container/detail/allocator_version_traits.hpp>
 #include <boost/container/detail/construct_in_place.hpp>
 #include <boost/container/detail/iterator.hpp>
 #include <boost/container/detail/iterators.hpp>
 #include <boost/container/detail/placement_new.hpp>
 #include <boost/move/detail/to_raw_pointer.hpp>
 #include <boost/container/detail/type_traits.hpp>
 // intrusive
 #include <boost/intrusive/pointer_traits.hpp>
 // intrusive/detail
 #include <boost/intrusive/detail/minimal_pair_header.hpp>   //pair
 // move
 #include <boost/move/utility_core.hpp>
 #include <boost/move/iterator.hpp>
 #include <boost/move/adl_move_swap.hpp>
 #include <boost/move/detail/launder.hpp>
 // move/detail
 #include <boost/move/detail/move_helpers.hpp>
 #include <boost/move/detail/iterator_to_raw_pointer.hpp>
 // other
 #include <boost/assert.hpp>
 // std
 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
 #include <initializer_list>
 #endif
 
 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
    #include <boost/container/vector.hpp>
    //#define STABLE_VECTOR_ENABLE_INVARIANT_CHECKING
 #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
 
 namespace boost {
 namespace container {
 
 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
 
 namespace stable_vector_detail{
 
 template <class C>
 class clear_on_destroy
 {
    public:
    inline clear_on_destroy(C &c)
       :  c_(c), do_clear_(true)
    {}
 
    inline void release()
    {  do_clear_ = false; }
 
    inline ~clear_on_destroy()
    {
       if(do_clear_){
          c_.clear();
          c_.priv_clear_pool();
       }
    }
 
    private:
    clear_on_destroy(const clear_on_destroy &);
    clear_on_destroy &operator=(const clear_on_destroy &);
    C &c_;
    bool do_clear_;
 };
 
 template<typename Pointer>
 struct node;
 
 template<class VoidPtr>
 struct node_base
 {
    private:
    typedef typename boost::intrusive::
       pointer_traits<VoidPtr>                   void_ptr_traits;
    typedef typename void_ptr_traits::
       template rebind_pointer
          <node_base>::type                      node_base_ptr;
 
    public:
    typedef typename void_ptr_traits::
       template rebind_pointer
          <node_base_ptr>::type                  node_base_ptr_ptr;
 
    public:
    inline explicit node_base(const node_base_ptr_ptr &n)
       : up(n)
    {}
 
    inline node_base()
       : up()
    {}
 
    node_base_ptr_ptr up;
 };
 
 
 template<typename Pointer>
 struct node
    : public node_base
       <typename ::boost::intrusive::pointer_traits<Pointer>::template
          rebind_pointer<void>::type
       >
 {
    public:
    typedef typename ::boost::intrusive::pointer_traits<Pointer>::element_type T;
    typedef node_base
       <typename ::boost::intrusive::pointer_traits<Pointer>::template
          rebind_pointer<void>::type
       > hook_type;
 
    typedef typename boost::container::dtl::aligned_storage
       <sizeof(T), boost::container::dtl::alignment_of<T>::value>::type storage_t;
    storage_t m_storage;
 
    inline explicit node(const typename hook_type::node_base_ptr_ptr &n)
       : hook_type(n)
    {}
 
    inline node()
    {}
 
    #if defined(BOOST_GCC) && (BOOST_GCC >= 40600) && (BOOST_GCC < 80000)
       #pragma GCC diagnostic push
       #pragma GCC diagnostic ignored "-Wstrict-aliasing"
       #define BOOST_CONTAINER_DISABLE_ALIASING_WARNING
    #  endif
 
    inline T &get_data()
    {  return *boost::move_detail::launder_cast<T*>(&this->m_storage);   }
 
    inline const T &get_data() const
    {  return *boost::move_detail::launder_cast<const T*>(&this->m_storage);  }
 
    inline T *get_data_ptr()
    {  return boost::move_detail::launder_cast<T*>(&this->m_storage);  }
 
    inline const T *get_data_ptr() const
    {  return boost::move_detail::launder_cast<const T*>(&this->m_storage);  }
 
    inline ~node()
    {  boost::move_detail::launder_cast<T*>(&this->m_storage)->~T();   }
 
    #if defined(BOOST_CONTAINER_DISABLE_ALIASING_WARNING)
       #pragma GCC diagnostic pop
       #undef BOOST_CONTAINER_DISABLE_ALIASING_WARNING
    #  endif
 
    inline void destroy_header()
    {  static_cast<hook_type*>(this)->~hook_type();  }
 };
 
 template<class VoidPtr, class VoidAllocator>
 struct index_traits
 {
    typedef boost::intrusive::
       pointer_traits
          <VoidPtr>                                    void_ptr_traits;
    typedef stable_vector_detail::
       node_base<VoidPtr>                              node_base_type;
    typedef typename void_ptr_traits::template
          rebind_pointer<node_base_type>::type         node_base_ptr;
    typedef typename void_ptr_traits::template
          rebind_pointer<node_base_ptr>::type          node_base_ptr_ptr;
    typedef boost::intrusive::
       pointer_traits<node_base_ptr>                   node_base_ptr_traits;
    typedef boost::intrusive::
       pointer_traits<node_base_ptr_ptr>               node_base_ptr_ptr_traits;
    typedef typename allocator_traits<VoidAllocator>::
          template portable_rebind_alloc
             <node_base_ptr>::type                     node_base_ptr_allocator;
    typedef ::boost::container::vector
       <node_base_ptr, node_base_ptr_allocator>        index_type;
    typedef typename index_type::iterator              index_iterator;
    typedef typename index_type::const_iterator        const_index_iterator;
    typedef typename index_type::size_type             size_type;
 
    BOOST_STATIC_CONSTEXPR size_type ExtraPointers = 3;
    //Stable vector stores metadata at the end of the index (node_base_ptr vector) with additional 3 pointers:
    //    back() is this->index.back() - ExtraPointers;
    //    end node index is    *(this->index.end() - 3)
    //    Node cache first is  *(this->index.end() - 2);
    //    Node cache last is   this->index.back();
 
    inline static node_base_ptr_ptr ptr_to_node_base_ptr(node_base_ptr &n)
    {  return node_base_ptr_ptr_traits::pointer_to(n);   }
 
    static void fix_up_pointers(index_iterator first, index_iterator last)
    {
       while(first != last){
          typedef typename index_type::reference node_base_ptr_ref;
          node_base_ptr_ref nbp = *first;
          nbp->up = index_traits::ptr_to_node_base_ptr(nbp);
          ++first;
       }
    }
 
    inline static index_iterator get_fix_up_end(index_type &index)
    {  return index.end() - (ExtraPointers - 1); }
 
    inline static void fix_up_pointers_from(index_type & index, index_iterator first)
    {  index_traits::fix_up_pointers(first, index_traits::get_fix_up_end(index));   }
 
    static void readjust_end_node(index_type &index, node_base_type &end_node)
    {
       if(!index.empty()){
          index_iterator end_node_it(index_traits::get_fix_up_end(index));
          node_base_ptr &end_node_idx_ref = *(--end_node_it);
          end_node_idx_ref = node_base_ptr_traits::pointer_to(end_node);
          end_node.up      = node_base_ptr_ptr_traits::pointer_to(end_node_idx_ref);
       }
       else{
          end_node.up = node_base_ptr_ptr();
       }
    }
 
    static void initialize_end_node(index_type &index, node_base_type &end_node, const size_type index_capacity_if_empty)
    {
       if(index.empty()){
          index.reserve(index_capacity_if_empty + ExtraPointers);
          index.resize(ExtraPointers);
          node_base_ptr &end_node_ref = *index.data();
          end_node_ref = node_base_ptr_traits::pointer_to(end_node);
          end_node.up = index_traits::ptr_to_node_base_ptr(end_node_ref);
       }
    }
 
    #ifdef STABLE_VECTOR_ENABLE_INVARIANT_CHECKING
    static bool invariants(index_type &index)
    {
       for( index_iterator it = index.begin()
          , it_end = index_traits::get_fix_up_end(index)
          ; it != it_end
          ; ++it){
          if((*it)->up != index_traits::ptr_to_node_base_ptr(*it)){
             return false;
          }
       }
       return true;
    }
    #endif   //STABLE_VECTOR_ENABLE_INVARIANT_CHECKING
 };
 
 } //namespace stable_vector_detail
 
 template<typename Pointer, bool IsConst>
 class stable_vector_iterator
 {
    typedef boost::intrusive::pointer_traits<Pointer>                                non_const_ptr_traits;
    public:
    typedef std::random_access_iterator_tag                                          iterator_category;
    typedef typename non_const_ptr_traits::element_type                              value_type;
    typedef typename non_const_ptr_traits::difference_type                           difference_type;
    typedef typename non_const_ptr_traits::size_type                                 size_type;
    typedef typename ::boost::container::dtl::if_c
       < IsConst
       , typename non_const_ptr_traits::template
          rebind_pointer<const value_type>::type
       , Pointer
       >::type                                                                       pointer;
    typedef boost::intrusive::pointer_traits<pointer>                                ptr_traits;
    typedef typename ptr_traits::reference                                           reference;
 
    typedef typename non_const_ptr_traits::template
          rebind_pointer<void>::type             void_ptr;
    typedef stable_vector_detail::node<Pointer>         node_type;
    typedef stable_vector_detail::node_base<void_ptr>   node_base_type;
    typedef typename non_const_ptr_traits::template
          rebind_pointer<node_type>::type        node_ptr;
    typedef boost::intrusive::
       pointer_traits<node_ptr>                  node_ptr_traits;
    typedef typename non_const_ptr_traits::template
          rebind_pointer<node_base_type>::type   node_base_ptr;
    typedef typename non_const_ptr_traits::template
          rebind_pointer<node_base_ptr>::type    node_base_ptr_ptr;
 
    class nat
    {
       public:
       node_base_ptr node_pointer() const
       { return node_base_ptr();  }
    };
    typedef typename dtl::if_c< IsConst
                              , stable_vector_iterator<Pointer, false>
                              , nat>::type                                           nonconst_iterator;
 
    node_base_ptr m_pn;
 
    public:
 
    inline explicit stable_vector_iterator(node_base_ptr p) BOOST_NOEXCEPT_OR_NOTHROW
       : m_pn(p)
    {}
 
    inline stable_vector_iterator() BOOST_NOEXCEPT_OR_NOTHROW
       : m_pn() //Value initialization to achieve "null iterators" (N3644)
    {}
 
    inline stable_vector_iterator(const stable_vector_iterator& other) BOOST_NOEXCEPT_OR_NOTHROW
       :  m_pn(other.node_pointer())
    {}
 
    inline stable_vector_iterator(const nonconst_iterator& other) BOOST_NOEXCEPT_OR_NOTHROW
       :  m_pn(other.node_pointer())
    {}
 
    inline stable_vector_iterator & operator=(const stable_vector_iterator& other) BOOST_NOEXCEPT_OR_NOTHROW
    {  m_pn = other.node_pointer(); return *this;   }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       node_ptr node_pointer() const BOOST_NOEXCEPT_OR_NOTHROW
    {  return node_ptr_traits::static_cast_from(m_pn);  }
 
    public:
    //Pointer like operators
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       reference operator*()  const BOOST_NOEXCEPT_OR_NOTHROW
    {  return  node_pointer()->get_data();  }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       pointer operator->() const BOOST_NOEXCEPT_OR_NOTHROW
    {  return ptr_traits::pointer_to(this->operator*());  }
 
    //Increment / Decrement
    inline stable_vector_iterator& operator++() BOOST_NOEXCEPT_OR_NOTHROW
    {
       node_base_ptr_ptr p(this->m_pn->up);
       this->m_pn = *(++p);
       return *this;
    }
 
    inline stable_vector_iterator operator++(int) BOOST_NOEXCEPT_OR_NOTHROW
    {  stable_vector_iterator tmp(*this);  ++*this; return stable_vector_iterator(tmp); }
 
    inline stable_vector_iterator& operator--() BOOST_NOEXCEPT_OR_NOTHROW
    {
       node_base_ptr_ptr p(this->m_pn->up);
       this->m_pn = *(--p);
       return *this;
    }
 
    inline stable_vector_iterator operator--(int) BOOST_NOEXCEPT_OR_NOTHROW
    {  stable_vector_iterator tmp(*this);  --*this; return stable_vector_iterator(tmp);  }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       reference operator[](difference_type off) const BOOST_NOEXCEPT_OR_NOTHROW
    {  return node_ptr_traits::static_cast_from(this->m_pn->up[off])->get_data();  }
 
    //Arithmetic
    inline stable_vector_iterator& operator+=(difference_type off) BOOST_NOEXCEPT_OR_NOTHROW
    {
       if(off) this->m_pn = this->m_pn->up[off];
       return *this;
    }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       friend stable_vector_iterator operator+(const stable_vector_iterator &left, difference_type off) BOOST_NOEXCEPT_OR_NOTHROW
    {
       stable_vector_iterator tmp(left);
       tmp += off;
       return tmp;
    }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       friend stable_vector_iterator operator+(difference_type off, const stable_vector_iterator& right) BOOST_NOEXCEPT_OR_NOTHROW
    {
       stable_vector_iterator tmp(right);
       tmp += off;
       return tmp;
    }
 
    inline stable_vector_iterator& operator-=(difference_type off) BOOST_NOEXCEPT_OR_NOTHROW
    {  *this += -off; return *this;   }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       friend stable_vector_iterator operator-(const stable_vector_iterator &left, difference_type off) BOOST_NOEXCEPT_OR_NOTHROW
    {
       stable_vector_iterator tmp(left);
       tmp -= off;
       return tmp;
    }
 
    //Difference
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       friend difference_type operator-(const stable_vector_iterator &left, const stable_vector_iterator &right) BOOST_NOEXCEPT_OR_NOTHROW
    {  return left.m_pn->up - right.m_pn->up;  }
 
    //Comparison operators
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       friend bool operator==   (const stable_vector_iterator& l, const stable_vector_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
    {  return l.m_pn == r.m_pn;  }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       friend bool operator!=   (const stable_vector_iterator& l, const stable_vector_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
    {  return l.m_pn != r.m_pn;  }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       friend bool operator<    (const stable_vector_iterator& l, const stable_vector_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
    {  return l.m_pn->up < r.m_pn->up;  }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       friend bool operator<=   (const stable_vector_iterator& l, const stable_vector_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
    {  return l.m_pn->up <= r.m_pn->up;  }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       friend bool operator>    (const stable_vector_iterator& l, const stable_vector_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
    {  return l.m_pn->up > r.m_pn->up;  }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       friend bool operator>=   (const stable_vector_iterator& l, const stable_vector_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
    {  return l.m_pn->up >= r.m_pn->up;  }
 };
 
    #if defined(STABLE_VECTOR_ENABLE_INVARIANT_CHECKING)
 
       #define BOOST_CONTAINER_STABLE_VECTOR_CHECK_INVARIANT \
                invariant_checker BOOST_JOIN(check_invariant_,__LINE__)(*this); \
                BOOST_JOIN(check_invariant_,__LINE__).touch();
 
    #else //STABLE_VECTOR_ENABLE_INVARIANT_CHECKING
 
       #define BOOST_CONTAINER_STABLE_VECTOR_CHECK_INVARIANT
 
    #endif   //#if defined(STABLE_VECTOR_ENABLE_INVARIANT_CHECKING)
 
 #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
 
 //! Originally developed by Joaquin M. Lopez Munoz, stable_vector is a std::vector
 //! drop-in replacement implemented as a node container, offering iterator and reference
 //! stability.
 //!
 //! Here are the details taken from the author's blog
 //! (<a href="http://bannalia.blogspot.com/2008/09/introducing-stablevector.html" >
 //! Introducing stable_vector</a>):
 //!
 //! We present stable_vector, a fully STL-compliant stable container that provides
 //! most of the features of std::vector except element contiguity.
 //!
 //! General properties: stable_vector satisfies all the requirements of a container,
 //! a reversible container and a sequence and provides all the optional operations
 //! present in std::vector. Like std::vector, iterators are random access.
 //! stable_vector does not provide element contiguity; in exchange for this absence,
 //! the container is stable, i.e. references and iterators to an element of a stable_vector
 //! remain valid as long as the element is not erased, and an iterator that has been
 //! assigned the return value of end() always remain valid until the destruction of
 //! the associated  stable_vector.
 //!
 //! Operation complexity: The big-O complexities of stable_vector operations match
 //! exactly those of std::vector. In general, insertion/deletion is constant time at
 //! the end of the sequence and linear elsewhere. Unlike std::vector, stable_vector
 //! does not internally perform any value_type destruction, copy or assignment
 //! operations other than those exactly corresponding to the insertion of new
 //! elements or deletion of stored elements, which can sometimes compensate in terms
 //! of performance for the extra burden of doing more pointer manipulation and an
 //! additional allocation per element.
 //!
 //! Exception safety: As stable_vector does not internally copy elements around, some
 //! operations provide stronger exception safety guarantees than in std::vector.
 //!
 //! \tparam T The type of object that is stored in the stable_vector
 //! \tparam Allocator The allocator used for all internal memory management
 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
 template <class T, class Allocator = void >
 #else
 template <class T, class Allocator>
 #endif
 class stable_vector
 {
    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
    typedef typename real_allocator<T, Allocator>::type     ValueAllocator;
    typedef allocator_traits<ValueAllocator>                allocator_traits_type;
    typedef boost::intrusive::
       pointer_traits
          <typename allocator_traits_type::pointer>    ptr_traits;
    typedef typename ptr_traits::
          template rebind_pointer<void>::type          void_ptr;
    typedef typename allocator_traits_type::
       template portable_rebind_alloc
          <void>::type                                 void_allocator_type;
    typedef stable_vector_detail::index_traits
       <void_ptr, void_allocator_type>                 index_traits_type;
    typedef typename index_traits_type::node_base_type node_base_type;
    typedef typename index_traits_type::node_base_ptr  node_base_ptr;
    typedef typename index_traits_type::
       node_base_ptr_ptr                               node_base_ptr_ptr;
    typedef typename index_traits_type::
       node_base_ptr_traits                            node_base_ptr_traits;
    typedef typename index_traits_type::
       node_base_ptr_ptr_traits                        node_base_ptr_ptr_traits;
    typedef typename index_traits_type::index_type     index_type;
    typedef typename index_traits_type::index_iterator index_iterator;
    typedef typename index_traits_type::
       const_index_iterator                            const_index_iterator;
    typedef stable_vector_detail::node
       <typename ptr_traits::pointer>                  node_type;
    typedef typename ptr_traits::template
       rebind_pointer<node_type>::type                 node_ptr;
    typedef boost::intrusive::
       pointer_traits<node_ptr>                        node_ptr_traits;
    typedef typename ptr_traits::template
       rebind_pointer<const node_type>::type           const_node_ptr;
    typedef boost::intrusive::
       pointer_traits<const_node_ptr>                  const_node_ptr_traits;
    typedef typename node_ptr_traits::reference        node_reference;
    typedef typename const_node_ptr_traits::reference  const_node_reference;
 
    typedef ::boost::container::dtl::integral_constant
       <unsigned, boost::container::dtl::
       version<ValueAllocator>::value>                              alloc_version;
    typedef typename allocator_traits_type::
       template portable_rebind_alloc
          <node_type>::type                            node_allocator_type;
 
    typedef ::boost::container::dtl::
       allocator_version_traits<node_allocator_type>                    allocator_version_traits_t;
    typedef typename allocator_version_traits_t::multiallocation_chain  multiallocation_chain;
 
    inline node_ptr allocate_one()
    {  return allocator_version_traits_t::allocate_one(this->priv_node_alloc());   }
 
    inline void deallocate_one(const node_ptr &p)
    {  allocator_version_traits_t::deallocate_one(this->priv_node_alloc(), p);   }
 
    inline void allocate_individual(typename allocator_traits_type::size_type n, multiallocation_chain &m)
    {  allocator_version_traits_t::allocate_individual(this->priv_node_alloc(), n, m);   }
 
    inline void deallocate_individual(multiallocation_chain &holder)
    {  allocator_version_traits_t::deallocate_individual(this->priv_node_alloc(), holder);   }
 
    friend class stable_vector_detail::clear_on_destroy<stable_vector>;
    typedef stable_vector_iterator
       < typename allocator_traits<ValueAllocator>::pointer
       , false>                                           iterator_impl;
    typedef stable_vector_iterator
       < typename allocator_traits<ValueAllocator>::pointer
       , true>                                            const_iterator_impl;
    #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
    public:
 
    //////////////////////////////////////////////
    //
    //                    types
    //
    //////////////////////////////////////////////
    typedef T                                                                           value_type;
    typedef typename ::boost::container::allocator_traits<ValueAllocator>::pointer           pointer;
    typedef typename ::boost::container::allocator_traits<ValueAllocator>::const_pointer     const_pointer;
    typedef typename ::boost::container::allocator_traits<ValueAllocator>::reference         reference;
    typedef typename ::boost::container::allocator_traits<ValueAllocator>::const_reference   const_reference;
    typedef typename ::boost::container::allocator_traits<ValueAllocator>::size_type         size_type;
    typedef typename ::boost::container::allocator_traits<ValueAllocator>::difference_type   difference_type;
    typedef ValueAllocator                                                                   allocator_type;
    typedef node_allocator_type                                                         stored_allocator_type;
    typedef BOOST_CONTAINER_IMPDEF(iterator_impl)                                       iterator;
    typedef BOOST_CONTAINER_IMPDEF(const_iterator_impl)                                 const_iterator;
    typedef BOOST_CONTAINER_IMPDEF(boost::container::reverse_iterator<iterator>)        reverse_iterator;
    typedef BOOST_CONTAINER_IMPDEF(boost::container::reverse_iterator<const_iterator>)  const_reverse_iterator;
 
    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
    private:
 
    //`allocator_type::value_type` must match container's `value type`. If this
    //assertion fails, please review your allocator definition. 
    BOOST_CONTAINER_STATIC_ASSERT((dtl::is_same<value_type, typename allocator_traits<allocator_type>::value_type>::value));
 
    BOOST_COPYABLE_AND_MOVABLE(stable_vector)
    BOOST_STATIC_CONSTEXPR size_type ExtraPointers = index_traits_type::ExtraPointers;
 
    class insert_rollback;
    friend class insert_rollback;
 
    class push_back_rollback;
    friend class push_back_rollback;
    #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
 
    public:
    //////////////////////////////////////////////
    //
    //          construct/copy/destroy
    //
    //////////////////////////////////////////////
 
    //! <b>Effects</b>: Default constructs a stable_vector.
    //!
    //! <b>Throws</b>: If allocator_type's default constructor throws.
    //!
    //! <b>Complexity</b>: Constant.
    inline stable_vector() BOOST_NOEXCEPT_IF(dtl::is_nothrow_default_constructible<ValueAllocator>::value)
       : internal_data(), index()
    {
       BOOST_CONTAINER_STABLE_VECTOR_CHECK_INVARIANT;
    }
 
    //! <b>Effects</b>: Constructs a stable_vector taking the allocator as parameter.
    //!
    //! <b>Throws</b>: Nothing
    //!
    //! <b>Complexity</b>: Constant.
    inline explicit stable_vector(const allocator_type& al) BOOST_NOEXCEPT_OR_NOTHROW
       : internal_data(al), index(al)
    {
       BOOST_CONTAINER_STABLE_VECTOR_CHECK_INVARIANT;
    }
 
    //! <b>Effects</b>: Constructs a stable_vector
    //!   and inserts n value initialized values.
    //!
    //! <b>Throws</b>: If allocator_type's default constructor
    //!   throws or T's default or copy constructor throws.
    //!
    //! <b>Complexity</b>: Linear to n.
    explicit stable_vector(size_type n)
       : internal_data(), index()
    {
       stable_vector_detail::clear_on_destroy<stable_vector> cod(*this);
       this->resize(n);
       BOOST_CONTAINER_STABLE_VECTOR_CHECK_INVARIANT;
       cod.release();
    }
 
    //! <b>Effects</b>: Constructs a stable_vector
    //!   and inserts n default initialized values.
    //!
    //! <b>Throws</b>: If allocator_type's default constructor
    //!   throws or T's default or copy constructor throws.
    //!
    //! <b>Complexity</b>: Linear to n.
    //!
    //! <b>Note</b>: Non-standard extension
    stable_vector(size_type n, default_init_t)
       : internal_data(), index()
    {
       stable_vector_detail::clear_on_destroy<stable_vector> cod(*this);
       this->resize(n, default_init);
       BOOST_CONTAINER_STABLE_VECTOR_CHECK_INVARIANT;
       cod.release();
    }
 
    //! <b>Effects</b>: Constructs a stable_vector that will use a copy of allocator a
    //!   and inserts n value initialized values.
    //!
    //! <b>Throws</b>: If allocator_type's default constructor
    //!   throws or T's default or copy constructor throws.
    //!
    //! <b>Complexity</b>: Linear to n.
    explicit stable_vector(size_type n, const allocator_type &a)
       : internal_data(), index(a)
    {
       stable_vector_detail::clear_on_destroy<stable_vector> cod(*this);
       this->resize(n);
       BOOST_CONTAINER_STABLE_VECTOR_CHECK_INVARIANT;
       cod.release();
    }
 
    //! <b>Effects</b>: Constructs a stable_vector that will use a copy of allocator a
    //!   and inserts n default initialized values.
    //!
    //! <b>Throws</b>: If allocator_type's default constructor
    //!   throws or T's default or copy constructor throws.
    //!
    //! <b>Complexity</b>: Linear to n.
    //!
    //! <b>Note</b>: Non-standard extension
    stable_vector(size_type n, default_init_t, const allocator_type &a)
       : internal_data(), index(a)
    {
       stable_vector_detail::clear_on_destroy<stable_vector> cod(*this);
       this->resize(n, default_init);
       BOOST_CONTAINER_STABLE_VECTOR_CHECK_INVARIANT;
       cod.release();
    }
 
    //! <b>Effects</b>: Constructs a stable_vector that will use a copy of allocator a
    //!   and inserts n copies of value.
    //!
    //! <b>Throws</b>: If allocator_type's default constructor
    //!   throws or T's default or copy constructor throws.
    //!
    //! <b>Complexity</b>: Linear to n.
    stable_vector(size_type n, const T& t, const allocator_type& al = allocator_type())
       : internal_data(al), index(al)
    {
       stable_vector_detail::clear_on_destroy<stable_vector> cod(*this);
       this->insert(this->cend(), n, t);
       BOOST_CONTAINER_STABLE_VECTOR_CHECK_INVARIANT;
       cod.release();
    }
 
    //! <b>Effects</b>: Constructs a stable_vector that will use a copy of allocator a
    //!   and inserts a copy of the range [first, last) in the stable_vector.
    //!
    //! <b>Throws</b>: If allocator_type's default constructor
    //!   throws or T's constructor taking a dereferenced InIt throws.
    //!
    //! <b>Complexity</b>: Linear to the range [first, last).
    template <class InputIterator>
    stable_vector(InputIterator first,InputIterator last, const allocator_type& al = allocator_type())
       : internal_data(al), index(al)
    {
       stable_vector_detail::clear_on_destroy<stable_vector> cod(*this);
       this->insert(this->cend(), first, last);
       BOOST_CONTAINER_STABLE_VECTOR_CHECK_INVARIANT;
       cod.release();
    }
 
    //! <b>Effects</b>: Copy constructs a stable_vector.
    //!
    //! <b>Postcondition</b>: x == *this.
    //!
    //! <b>Complexity</b>: Linear to the elements x contains.
    stable_vector(const stable_vector& x)
       : internal_data(allocator_traits<node_allocator_type>::
          select_on_container_copy_construction(x.priv_node_alloc()))
       , index(allocator_traits<allocator_type>::
          select_on_container_copy_construction(x.index.get_stored_allocator()))
    {
       stable_vector_detail::clear_on_destroy<stable_vector> cod(*this);
       this->insert(this->cend(), x.begin(), x.end());
       BOOST_CONTAINER_STABLE_VECTOR_CHECK_INVARIANT;
       cod.release();
    }
 
 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
    //! <b>Effects</b>: Constructs a stable_vector that will use a copy of allocator a
    //!  and inserts a copy of the range [il.begin(), il.last()) in the stable_vector
    //!
    //! <b>Throws</b>: If allocator_type's default constructor
    //!   throws or T's constructor taking a dereferenced initializer_list iterator throws.
    //!
    //! <b>Complexity</b>: Linear to the range [il.begin(), il.end()).
    stable_vector(std::initializer_list<value_type> il, const allocator_type& l = allocator_type())
       : internal_data(l), index(l)
    {
       stable_vector_detail::clear_on_destroy<stable_vector> cod(*this);
       insert(cend(), il.begin(), il.end());
       BOOST_CONTAINER_STABLE_VECTOR_CHECK_INVARIANT;
       cod.release();
    }
 #endif
 
    //! <b>Effects</b>: Move constructor. Moves x's resources to *this.
    //!
    //! <b>Throws</b>: If allocator_type's copy constructor throws.
    //!
    //! <b>Complexity</b>: Constant.
    inline stable_vector(BOOST_RV_REF(stable_vector) x) BOOST_NOEXCEPT_OR_NOTHROW
       : internal_data(boost::move(x.priv_node_alloc())), index(boost::move(x.index))
    {
       this->priv_swap_members(x);
    }
 
    //! <b>Effects</b>: Copy constructs a stable_vector using the specified allocator.
    //!
    //! <b>Postcondition</b>: x == *this.
    //!
    //! <b>Complexity</b>: Linear to the elements x contains.
    stable_vector(const stable_vector& x, const allocator_type &a)
       : internal_data(a), index(a)
    {
       stable_vector_detail::clear_on_destroy<stable_vector> cod(*this);
       this->insert(this->cend(), x.begin(), x.end());
       BOOST_CONTAINER_STABLE_VECTOR_CHECK_INVARIANT;
       cod.release();
    }
 
    //! <b>Effects</b>: Move constructor using the specified allocator.
    //!                 Moves x's resources to *this.
    //!
    //! <b>Throws</b>: If allocator_type's copy constructor throws.
    //!
    //! <b>Complexity</b>: Constant if a == x.get_allocator(), linear otherwise
    stable_vector(BOOST_RV_REF(stable_vector) x, const allocator_type &a)
       : internal_data(a), index(a)
    {
       if(this->priv_node_alloc() == x.priv_node_alloc()){
          this->index.swap(x.index);         
          this->priv_swap_members(x);
       }
       else{
          stable_vector_detail::clear_on_destroy<stable_vector> cod(*this);
          this->insert(this->cend(), boost::make_move_iterator(x.begin()), boost::make_move_iterator(x.end()));
          BOOST_CONTAINER_STABLE_VECTOR_CHECK_INVARIANT;
          cod.release();
       }
    }
 
    //! <b>Effects</b>: Destroys the stable_vector. All stored values are destroyed
    //!   and used memory is deallocated.
    //!
    //! <b>Throws</b>: Nothing.
    //!
    //! <b>Complexity</b>: Linear to the number of elements.
    ~stable_vector()
    {
       this->clear();
       this->priv_clear_pool();
    }
 
    //! <b>Effects</b>: Makes *this contain the same elements as x.
    //!
    //! <b>Postcondition</b>: this->size() == x.size(). *this contains a copy
    //! of each of x's elements.
    //!
    //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws.
    //!
    //! <b>Complexity</b>: Linear to the number of elements in x.
    stable_vector& operator=(BOOST_COPY_ASSIGN_REF(stable_vector) x)
    {
       BOOST_CONTAINER_STABLE_VECTOR_CHECK_INVARIANT;
       if (BOOST_LIKELY(this != &x)) {
          node_allocator_type &this_alloc     = this->priv_node_alloc();
          const node_allocator_type &x_alloc  = x.priv_node_alloc();
          dtl::bool_<allocator_traits_type::
             propagate_on_container_copy_assignment::value> flag;
          if(flag && this_alloc != x_alloc){
             this->clear();
             this->shrink_to_fit();
          }
          dtl::assign_alloc(this->priv_node_alloc(), x.priv_node_alloc(), flag);
          dtl::assign_alloc(this->index.get_stored_allocator(), x.index.get_stored_allocator(), flag);
          this->assign(x.begin(), x.end());
       }
       return *this;
    }
 
    //! <b>Effects</b>: Move assignment. All x's values are transferred to *this.
    //!
    //! <b>Postcondition</b>: x.empty(). *this contains a the elements x had
    //!   before the function.
    //!
    //! <b>Throws</b>: If allocator_traits_type::propagate_on_container_move_assignment
    //!   is false and (allocation throws or T's move constructor throws)
    //!
    //! <b>Complexity</b>: Constant if allocator_traits_type::
    //!   propagate_on_container_move_assignment is true or
    //!   this->get>allocator() == x.get_allocator(). Linear otherwise.
    stable_vector& operator=(BOOST_RV_REF(stable_vector) x)
       BOOST_NOEXCEPT_IF(allocator_traits_type::propagate_on_container_move_assignment::value
                                   || allocator_traits_type::is_always_equal::value)
    {
       if (BOOST_LIKELY(this != &x)) {
          //We know resources can be transferred at comiple time if both allocators are
          //always equal or the allocator is going to be propagated
          const bool can_steal_resources_alloc
             =  allocator_traits_type::propagate_on_container_move_assignment::value
             || allocator_traits_type::is_always_equal::value;
          dtl::bool_<can_steal_resources_alloc> flag;
          this->priv_move_assign(boost::move(x), flag);
       }
       return *this;
    }
 
 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
    //! <b>Effects</b>: Make *this container contains elements from il.
    //!
    //! <b>Complexity</b>: Linear to the range [il.begin(), il.end()).
    stable_vector& operator=(std::initializer_list<value_type> il)
    {
       BOOST_CONTAINER_STABLE_VECTOR_CHECK_INVARIANT;
       assign(il.begin(), il.end());
       return *this;
    }
 #endif
 
    //! <b>Effects</b>: Assigns the n copies of val to *this.
    //!
    //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws.
    //!
    //! <b>Complexity</b>: Linear to n.
    inline void assign(size_type n, const T& t)
    {
       typedef constant_iterator<value_type> cvalue_iterator;
       this->assign(cvalue_iterator(t, n), cvalue_iterator());
    }
 
    //! <b>Effects</b>: Assigns the the range [first, last) to *this.
    //!
    //! <b>Throws</b>: If memory allocation throws or
    //!   T's constructor from dereferencing InpIt throws.
    //!
    //! <b>Complexity</b>: Linear to n.
    template<typename InputIterator>
    #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
    typename dtl::disable_if_convertible<InputIterator, size_type>::type
    #else
    void
    #endif
       assign(InputIterator first,InputIterator last)
    {
       BOOST_CONTAINER_STABLE_VECTOR_CHECK_INVARIANT;
       iterator first1   = this->begin();
       iterator last1    = this->end();
       for ( ; first1 != last1 && first != last; ++first1, ++first)
          *first1 = *first;
       if (first == last){
          this->erase(first1, last1);
       }
       else{
          this->insert(last1, first, last);
       }
    }
 
 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
    //! <b>Effects</b>: Assigns the the range [il.begin(), il.end()) to *this.
    //!
    //! <b>Throws</b>: If memory allocation throws or
    //!   T's constructor from dereferencing initializer_list iterator throws.
    //!
    inline void assign(std::initializer_list<value_type> il)
    {
       BOOST_CONTAINER_STABLE_VECTOR_CHECK_INVARIANT;
       assign(il.begin(), il.end());
    }
 #endif
 
    //! <b>Effects</b>: Returns a copy of the internal allocator.
    //!
    //! <b>Throws</b>: If allocator's copy constructor throws.
    //!
    //! <b>Complexity</b>: Constant.
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       allocator_type get_allocator() const
    {  return this->priv_node_alloc();  }
 
    //! <b>Effects</b>: Returns a reference to the internal allocator.
    //!
    //! <b>Throws</b>: Nothing
    //!
    //! <b>Complexity</b>: Constant.
    //!
    //! <b>Note</b>: Non-standard extension.
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       const stored_allocator_type &get_stored_allocator() const BOOST_NOEXCEPT_OR_NOTHROW
    {  return this->priv_node_alloc(); }
 
    //! <b>Effects</b>: Returns a reference to the internal allocator.
    //!
    //! <b>Throws</b>: Nothing
    //!
    //! <b>Complexity</b>: Constant.
    //!
    //! <b>Note</b>: Non-standard extension.
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       stored_allocator_type &get_stored_allocator() BOOST_NOEXCEPT_OR_NOTHROW
    {  return this->priv_node_alloc(); }
 
    //////////////////////////////////////////////
    //
    //                iterators
    //
    //////////////////////////////////////////////
 
    //! <b>Effects</b>: Returns an iterator to the first element contained in the stable_vector.
    //!
    //! <b>Throws</b>: Nothing.
    //!
    //! <b>Complexity</b>: Constant.
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       iterator begin() BOOST_NOEXCEPT_OR_NOTHROW
    {   return (this->index.empty()) ? this->end(): iterator(node_ptr_traits::static_cast_from(this->index.front())); }
 
    //! <b>Effects</b>: Returns a const_iterator to the first element contained in the stable_vector.
    //!
    //! <b>Throws</b>: Nothing.
    //!
    //! <b>Complexity</b>: Constant.
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       const_iterator begin() const BOOST_NOEXCEPT_OR_NOTHROW
    {   return (this->index.empty()) ? this->cend() : const_iterator(node_ptr_traits::static_cast_from(this->index.front())) ;   }
 
    //! <b>Effects</b>: Returns an iterator to the end of the stable_vector.
    //!
    //! <b>Throws</b>: Nothing.
    //!
    //! <b>Complexity</b>: Constant.
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       iterator end() BOOST_NOEXCEPT_OR_NOTHROW
    {  return iterator(this->priv_get_end_node());  }
 
    //! <b>Effects</b>: Returns a const_iterator to the end of the stable_vector.
    //!
    //! <b>Throws</b>: Nothing.
    //!
    //! <b>Complexity</b>: Constant.
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW
    {  return const_iterator(this->priv_get_end_node());  }
 
    //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning
    //! of the reversed stable_vector.
    //!
    //! <b>Throws</b>: Nothing.
    //!
    //! <b>Complexity</b>: Constant.
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW
    {  return reverse_iterator(this->end());  }
 
    //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
    //! of the reversed stable_vector.
    //!
    //! <b>Throws</b>: Nothing.
    //!
    //! <b>Complexity</b>: Constant.
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW
    {  return const_reverse_iterator(this->end());  }
 
    //! <b>Effects</b>: Returns a reverse_iterator pointing to the end
    //! of the reversed stable_vector.
    //!
    //! <b>Throws</b>: Nothing.
    //!
    //! <b>Complexity</b>: Constant.
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW
    {  return reverse_iterator(this->begin());   }
 
    //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
    //! of the reversed stable_vector.
    //!
    //! <b>Throws</b>: Nothing.
    //!
    //! <b>Complexity</b>: Constant.
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW
    {  return const_reverse_iterator(this->begin());   }
 
    //! <b>Effects</b>: Returns a const_iterator to the first element contained in the stable_vector.
    //!
    //! <b>Throws</b>: Nothing.
    //!
    //! <b>Complexity</b>: Constant.
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       const_iterator cbegin() const BOOST_NOEXCEPT_OR_NOTHROW
    {  return this->begin();   }
 
    //! <b>Effects</b>: Returns a const_iterator to the end of the stable_vector.
    //!
    //! <b>Throws</b>: Nothing.
    //!
    //! <b>Complexity</b>: Constant.
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW
    {  return this->end();  }
 
    //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
    //! of the reversed stable_vector.
    //!
    //! <b>Throws</b>: Nothing.
    //!
    //! <b>Complexity</b>: Constant.
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW
    {  return this->rbegin();  }
 
    //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
    //! of the reversed stable_vector.
    //!
    //! <b>Throws</b>: Nothing.
    //!
    //! <b>Complexity</b>: Constant.
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       const_reverse_iterator crend()const BOOST_NOEXCEPT_OR_NOTHROW
    {  return this->rend(); }
 
    //////////////////////////////////////////////
    //
    //                capacity
    //
    //////////////////////////////////////////////
 
    //! <b>Effects</b>: Returns true if the stable_vector contains no elements.
    //!
    //! <b>Throws</b>: Nothing.
    //!
    //! <b>Complexity</b>: Constant.
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       bool empty() const BOOST_NOEXCEPT_OR_NOTHROW
    {  return this->index.size() <= ExtraPointers;  }
 
    //! <b>Effects</b>: Returns the number of the elements contained in the stable_vector.
    //!
    //! <b>Throws</b>: Nothing.
    //!
    //! <b>Complexity</b>: Constant.
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       size_type size() const BOOST_NOEXCEPT_OR_NOTHROW
    {
       const size_type index_size = this->index.size();
       return (index_size - ExtraPointers) & (size_type(0u) -size_type(index_size != 0));
    }
 
    //! <b>Effects</b>: Returns the largest possible size of the stable_vector.
    //!
    //! <b>Throws</b>: Nothing.
    //!
    //! <b>Complexity</b>: Constant.
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       size_type max_size() const BOOST_NOEXCEPT_OR_NOTHROW
    {  return this->index.max_size() - ExtraPointers;  }
 
    //! <b>Effects</b>: Inserts or erases elements at the end such that
    //!   the size becomes n. New elements are value initialized.
    //!
    //! <b>Throws</b>: If memory allocation throws, or T's value initialization throws.
    //!
    //! <b>Complexity</b>: Linear to the difference between size() and new_size.
    void resize(size_type n)
    {
       typedef value_init_construct_iterator<value_type> value_init_iterator;
       BOOST_CONTAINER_STABLE_VECTOR_CHECK_INVARIANT;
       if(n > this->size())
          this->insert( this->cend()
                      , value_init_iterator(n - this->size()), value_init_iterator());
       else if(n < this->size())
          this->erase(this->cbegin() + difference_type(n), this->cend());
    }
 
    //! <b>Effects</b>: Inserts or erases elements at the end such that
    //!   the size becomes n. New elements are default initialized.
    //!
    //! <b>Throws</b>: If memory allocation throws, or T's default initialization throws.
    //!
    //! <b>Complexity</b>: Linear to the difference between size() and new_size.
    //!
    //! <b>Note</b>: Non-standard extension
    void resize(size_type n, default_init_t)
    {
       typedef default_init_construct_iterator<value_type> default_init_iterator;
       BOOST_CONTAINER_STABLE_VECTOR_CHECK_INVARIANT;
       if(n > this->size())
          this->insert(this->cend(), default_init_iterator(n - this->size()), default_init_iterator());
       else if(n < this->size())
          this->erase(this->cbegin() + difference_type(n), this->cend());
    }
 
    //! <b>Effects</b>: Inserts or erases elements at the end such that
    //!   the size becomes n. New elements are copy constructed from x.
    //!
    //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws.
    //!
    //! <b>Complexity</b>: Linear to the difference between size() and new_size.
    void resize(size_type n, const T& t)
    {
       BOOST_CONTAINER_STABLE_VECTOR_CHECK_INVARIANT;
       if(n > this->size())
          this->insert(this->cend(), n - this->size(), t);
       else if(n < this->size())
          this->erase(this->cbegin() + difference_type(n), this->cend());
    }
 
    //! <b>Effects</b>: Number of elements for which memory has been allocated.
    //!   capacity() is always greater than or equal to size().
    //!
    //! <b>Throws</b>: Nothing.
    //!
    //! <b>Complexity</b>: Constant.
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       size_type capacity() const BOOST_NOEXCEPT_OR_NOTHROW
    {
       const size_type index_size             = this->index.size();
       BOOST_ASSERT(!index_size || index_size >= ExtraPointers);
       const size_type node_extra_capacity   = this->internal_data.pool_size;
       //Pool count must be less than index capacity, as index is a vector
       BOOST_ASSERT(node_extra_capacity <= (this->index.capacity()- index_size));
       const size_type index_offset =
          (node_extra_capacity - ExtraPointers) & (size_type(0u) - size_type(index_size != 0));
       return index_size + index_offset;
    }
 
    //! <b>Effects</b>: If n is less than or equal to capacity(), this call has no
    //!   effect. Otherwise, it is a request for allocation of additional memory.
    //!   If the request is successful, then capacity() is greater than or equal to
    //!   n; otherwise, capacity() is unchanged. In either case, size() is unchanged.
    //!
    //! <b>Throws</b>: If memory allocation allocation throws.
    void reserve(size_type n)
    {
       BOOST_CONTAINER_STABLE_VECTOR_CHECK_INVARIANT;
       if(n > this->max_size()){
          throw_length_error("stable_vector::reserve max_size() exceeded");
       }
 
       size_type sz         = this->size();
       size_type old_capacity = this->capacity();
       if(n > old_capacity){
          index_traits_type::initialize_end_node(this->index, this->internal_data.end_node, n);
          const void * old_ptr = &index[0];
          this->index.reserve(n + ExtraPointers);
          bool realloced = &index[0] != old_ptr;
          //Fix the pointers for the newly allocated buffer
          if(realloced){
             index_traits_type::fix_up_pointers_from(this->index, this->index.begin());
          }
          //Now fill pool if data is not enough
          if((n - sz) > this->internal_data.pool_size){
             this->priv_increase_pool((n - sz) - this->internal_data.pool_size);
          }
       }
    }
 
    //! <b>Effects</b>: Tries to deallocate the excess of memory created
    //!   with previous allocations. The size of the stable_vector is unchanged
    //!
    //! <b>Throws</b>: If memory allocation throws.
    //!
    //! <b>Complexity</b>: Linear to size().
    void shrink_to_fit()
    {
       if(this->capacity()){
          //First empty allocated node pool
          this->priv_clear_pool();
          //If empty completely destroy the index, let's recover default-constructed state
          if(this->empty()){
             this->index.clear();
             this->index.shrink_to_fit();
             this->internal_data.end_node.up = node_base_ptr_ptr();
          }
          //Otherwise, try to shrink-to-fit the index and readjust pointers if necessary
          else{
             const void* old_ptr = &index[0];
             this->index.shrink_to_fit();
             bool realloced = &index[0] != old_ptr;
             //Fix the pointers for the newly allocated buffer
             if(realloced){
                index_traits_type::fix_up_pointers_from(this->index, this->index.begin());
             }
          }
       }
    }
 
    //////////////////////////////////////////////
    //
    //               element access
    //
    //////////////////////////////////////////////
 
    //! <b>Requires</b>: !empty()
    //!
    //! <b>Effects</b>: Returns a reference to the first
    //!   element of the container.
    //!
    //! <b>Throws</b>: Nothing.
    //!
    //! <b>Complexity</b>: Constant.
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       reference front() BOOST_NOEXCEPT_OR_NOTHROW
    {
       BOOST_ASSERT(!this->empty());
       return static_cast<node_reference>(*this->index.front()).get_data();
    }
 
    //! <b>Requires</b>: !empty()
    //!
    //! <b>Effects</b>: Returns a const reference to the first
    //!   element of the container.
    //!
    //! <b>Throws</b>: Nothing.
    //!
    //! <b>Complexity</b>: Constant.
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       const_reference front() const BOOST_NOEXCEPT_OR_NOTHROW
    {
       BOOST_ASSERT(!this->empty());
       return static_cast<const_node_reference>(*this->index.front()).get_data();
    }
 
    //! <b>Requires</b>: !empty()
    //!
    //! <b>Effects</b>: Returns a reference to the last
    //!   element of the container.
    //!
    //! <b>Throws</b>: Nothing.
    //!
    //! <b>Complexity</b>: Constant.
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       reference back() BOOST_NOEXCEPT_OR_NOTHROW
    {
       BOOST_ASSERT(!this->empty());
       return static_cast<node_reference>(*this->index[this->size()-1u]).get_data();
    }
 
    //! <b>Requires</b>: !empty()
    //!
    //! <b>Effects</b>: Returns a const reference to the last
    //!   element of the container.
    //!
    //! <b>Throws</b>: Nothing.
    //!
    //! <b>Complexity</b>: Constant.
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       const_reference back() const BOOST_NOEXCEPT_OR_NOTHROW
    {
       BOOST_ASSERT(!this->empty());
       return static_cast<const_node_reference>(*this->index[this->size()-1u]).get_data();
    }
 
    //! <b>Requires</b>: size() > n.
    //!
    //! <b>Effects</b>: Returns a reference to the nth element
    //!   from the beginning of the container.
    //!
    //! <b>Throws</b>: Nothing.
    //!
    //! <b>Complexity</b>: Constant.
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       reference operator[](size_type n) BOOST_NOEXCEPT_OR_NOTHROW
    {
       BOOST_ASSERT(this->size() > n);
       return static_cast<node_reference>(*this->index[n]).get_data();
    }
 
    //! <b>Requires</b>: size() > n.
    //!
    //! <b>Effects</b>: Returns a const reference to the nth element
    //!   from the beginning of the container.
    //!
    //! <b>Throws</b>: Nothing.
    //!
    //! <b>Complexity</b>: Constant.
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       const_reference operator[](size_type n) const BOOST_NOEXCEPT_OR_NOTHROW
    {
       BOOST_ASSERT(this->size() > n);
       return static_cast<const_node_reference>(*this->index[n]).get_data();
    }
 
    //! <b>Requires</b>: size() >= n.
    //!
    //! <b>Effects</b>: Returns an iterator to the nth element
    //!   from the beginning of the container. Returns end()
    //!   if n == size().
    //!
    //! <b>Throws</b>: Nothing.
    //!
    //! <b>Complexity</b>: Constant.
    //!
    //! <b>Note</b>: Non-standard extension
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       iterator nth(size_type n) BOOST_NOEXCEPT_OR_NOTHROW
    {
       BOOST_ASSERT(this->size() >= n);
       return (this->index.empty()) ? this->end() : iterator(node_ptr_traits::static_cast_from(this->index[n]));
    }
 
    //! <b>Requires</b>: size() >= n.
    //!
    //! <b>Effects</b>: Returns a const_iterator to the nth element
    //!   from the beginning of the container. Returns end()
    //!   if n == size().
    //!
    //! <b>Throws</b>: Nothing.
    //!
    //! <b>Complexity</b>: Constant.
    //!
    //! <b>Note</b>: Non-standard extension
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       const_iterator nth(size_type n) const BOOST_NOEXCEPT_OR_NOTHROW
    {
       BOOST_ASSERT(this->size() >= n);
       return (this->index.empty()) ? this->cend() : iterator(node_ptr_traits::static_cast_from(this->index[n]));
    }
 
    //! <b>Requires</b>: begin() <= p <= end().
    //!
    //! <b>Effects</b>: Returns the index of the element pointed by p
    //!   and size() if p == end().
    //!
    //! <b>Throws</b>: Nothing.
    //!
    //! <b>Complexity</b>: Constant.
    //!
    //! <b>Note</b>: Non-standard extension
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       size_type index_of(iterator p) BOOST_NOEXCEPT_OR_NOTHROW
    {  return this->priv_index_of(p.node_pointer());  }
 
    //! <b>Requires</b>: begin() <= p <= end().
    //!
    //! <b>Effects</b>: Returns the index of the element pointed by p
    //!   and size() if p == end().
    //!
    //! <b>Throws</b>: Nothing.
    //!
    //! <b>Complexity</b>: Constant.
    //!
    //! <b>Note</b>: Non-standard extension
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       size_type index_of(const_iterator p) const BOOST_NOEXCEPT_OR_NOTHROW
    {  return this->priv_index_of(p.node_pointer());  }
 
    //! <b>Requires</b>: size() > n.
    //!
    //! <b>Effects</b>: Returns a reference to the nth element
    //!   from the beginning of the container.
    //!
    //! <b>Throws</b>: range_error if n >= size()
    //!
    //! <b>Complexity</b>: Constant.
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       reference at(size_type n)
    {
       if(n >= this->size()){
          throw_out_of_range("vector::at invalid subscript");
       }
       return operator[](n);
    }
 
    //! <b>Requires</b>: size() > n.
    //!
    //! <b>Effects</b>: Returns a const reference to the nth element
    //!   from the beginning of the container.
    //!
    //! <b>Throws</b>: range_error if n >= size()
    //!
    //! <b>Complexity</b>: Constant.
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       const_reference at(size_type n)const
    {
       if(n >= this->size()){
          throw_out_of_range("vector::at invalid subscript");
       }
       return operator[](n);
    }
 
    //////////////////////////////////////////////
    //
    //                modifiers
    //
    //////////////////////////////////////////////
 
    #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
 
    //! <b>Effects</b>: Inserts an object of type T constructed with
    //!   std::forward<Args>(args)... in the end of the stable_vector.
    //!
    //! <b>Returns</b>: A reference to the created object.
    //!
    //! <b>Throws</b>: If memory allocation throws or the in-place constructor throws.
    //!
    //! <b>Complexity</b>: Amortized constant time.
    template<class ...Args>
    reference emplace_back(Args &&...args)
    {
       typedef emplace_functor<Args...>         EmplaceFunctor;
       typedef emplace_iterator<value_type, EmplaceFunctor> EmplaceIterator;
       EmplaceFunctor &&ef = EmplaceFunctor(boost::forward<Args>(args)...);
       return *this->insert(this->cend(), EmplaceIterator(ef), EmplaceIterator());
    }
 
    //! <b>Requires</b>: p must be a valid iterator of *this.
    //!
    //! <b>Effects</b>: Inserts an object of type T constructed with
    //!   std::forward<Args>(args)... before p
    //!
    //! <b>Throws</b>: If memory allocation throws or the in-place constructor throws.
    //!
    //! <b>Complexity</b>: If p is end(), amortized constant time
    //!   Linear time otherwise.
    template<class ...Args>
    iterator emplace(const_iterator p, Args && ...args)
    {
       BOOST_ASSERT(this->priv_in_range_or_end(p));
       difference_type pos_n = p - cbegin();
       typedef emplace_functor<Args...>         EmplaceFunctor;
       typedef emplace_iterator<value_type, EmplaceFunctor> EmplaceIterator;
       EmplaceFunctor &&ef = EmplaceFunctor(boost::forward<Args>(args)...);
       this->insert(p, EmplaceIterator(ef), EmplaceIterator());
       return iterator(this->begin() + pos_n);
    }
 
    #else
 
    #define BOOST_CONTAINER_STABLE_VECTOR_EMPLACE_CODE(N) \
    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
    reference emplace_back(BOOST_MOVE_UREF##N)\
    {\
       typedef emplace_functor##N\
          BOOST_MOVE_LT##N BOOST_MOVE_TARG##N BOOST_MOVE_GT##N EmplaceFunctor;\
       typedef emplace_iterator<value_type, EmplaceFunctor>  EmplaceIterator;\
       EmplaceFunctor ef BOOST_MOVE_LP##N BOOST_MOVE_FWD##N BOOST_MOVE_RP##N;\
       return *this->insert(this->cend() , EmplaceIterator(ef), EmplaceIterator());\
    }\
    \
    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
    iterator emplace(const_iterator p BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
    {\
       BOOST_ASSERT(this->priv_in_range_or_end(p));\
       typedef emplace_functor##N\
          BOOST_MOVE_LT##N BOOST_MOVE_TARG##N BOOST_MOVE_GT##N EmplaceFunctor;\
       typedef emplace_iterator<value_type, EmplaceFunctor>  EmplaceIterator;\
       EmplaceFunctor ef BOOST_MOVE_LP##N BOOST_MOVE_FWD##N BOOST_MOVE_RP##N;\
       const size_type pos_n = size_type(p - this->cbegin());\
       this->insert(p, EmplaceIterator(ef), EmplaceIterator());\
       return this->begin() += difference_type(pos_n);\
    }\
    //
    BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_STABLE_VECTOR_EMPLACE_CODE)
    #undef BOOST_CONTAINER_STABLE_VECTOR_EMPLACE_CODE
 
    #endif   // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
 
    #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
    //! <b>Effects</b>: Inserts a copy of x at the end of the stable_vector.
    //!
    //! <b>Throws</b>: If memory allocation throws or
    //!   T's copy constructor throws.
    //!
    //! <b>Complexity</b>: Amortized constant time.
    void push_back(const T &x);
 
    //! <b>Effects</b>: Constructs a new element in the end of the stable_vector
    //!   and moves the resources of x to this new element.
    //!
    //! <b>Throws</b>: If memory allocation throws.
    //!
    //! <b>Complexity</b>: Amortized constant time.
    void push_back(T &&x);
    #else
    BOOST_MOVE_CONVERSION_AWARE_CATCH(push_back, T, void, priv_push_back)
    #endif
 
    #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
    //! <b>Requires</b>: p must be a valid iterator of *this.
    //!
    //! <b>Effects</b>: Insert a copy of x before p.
    //!
    //! <b>Returns</b>: An iterator to the inserted element.
    //!
    //! <b>Throws</b>: If memory allocation throws or x's copy constructor throws.
    //!
    //! <b>Complexity</b>: If p is end(), amortized constant time
    //!   Linear time otherwise.
    iterator insert(const_iterator p, const T &x);
 
    //! <b>Requires</b>: p must be a valid iterator of *this.
    //!
    //! <b>Effects</b>: Insert a new element before p with x's resources.
    //!
    //! <b>Returns</b>: an iterator to the inserted element.
    //!
    //! <b>Throws</b>: If memory allocation throws.
    //!
    //! <b>Complexity</b>: If p is end(), amortized constant time
    //!   Linear time otherwise.
    iterator insert(const_iterator p, T &&x);
    #else
    BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, T, iterator, priv_insert, const_iterator, const_iterator)
    #endif
 
    //! <b>Requires</b>: p must be a valid iterator of *this.
    //!
    //! <b>Effects</b>: Insert n copies of x before p.
    //!
    //! <b>Returns</b>: an iterator to the first inserted element or p if n is 0.
    //!
    //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws.
    //!
    //! <b>Complexity</b>: Linear to n.
    iterator insert(const_iterator p, size_type n, const T& t)
    {
       BOOST_ASSERT(this->priv_in_range_or_end(p));
       BOOST_CONTAINER_STABLE_VECTOR_CHECK_INVARIANT;
       typedef constant_iterator<value_type> cvalue_iterator;
       return this->insert(p, cvalue_iterator(t, n), cvalue_iterator());
    }
 
    //! <b>Requires</b>: p must be a valid iterator of *this.
 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
    //! <b>Requires</b>: p must be a valid iterator of *this.
    //!
    //! <b>Effects</b>: Insert a copy of the [il.begin(), il.end()) range before p.
    //!
    //! <b>Returns</b>: an iterator to the first inserted element or p if first == last.
    //!
    //! <b>Complexity</b>: Linear to distance [il.begin(), il.end()).
    inline iterator insert(const_iterator p, std::initializer_list<value_type> il)
    {
       //Position checks done by insert()
       BOOST_CONTAINER_STABLE_VECTOR_CHECK_INVARIANT;
       return insert(p, il.begin(), il.end());
    }
 #endif
 
    //! <b>Requires</b>: pos must be a valid iterator of *this.
    //!
    //! <b>Effects</b>: Insert a copy of the [first, last) range before p.
    //!
    //! <b>Returns</b>: an iterator to the first inserted element or p if first == last.
    //!
    //! <b>Throws</b>: If memory allocation throws, T's constructor from a
    //!   dereferenced InpIt throws or T's copy constructor throws.
    //!
    //! <b>Complexity</b>: Linear to distance [first, last).
    template <class InputIterator>
    iterator insert(const_iterator p, InputIterator first, InputIterator last
          #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
          //Put this as argument instead of the return type as old GCC's like 3.4
          //detect this and the next disable_if_or as overloads
          ,  typename dtl::disable_if_or
                < void
                , dtl::is_convertible<InputIterator, size_type>
                , dtl::is_not_input_iterator<InputIterator>
                >::type* = 0
          #endif
          )
    {
       BOOST_ASSERT(this->priv_in_range_or_end(p));
       BOOST_CONTAINER_STABLE_VECTOR_CHECK_INVARIANT;
       const difference_type pos_n = p - this->cbegin();
       for(; first != last; ++first){
          this->emplace(p, *first);
       }
       return this->begin() + difference_type(pos_n);
    }
 
    #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
    template <class FwdIt>
    typename dtl::disable_if_or
       < iterator
       , dtl::is_convertible<FwdIt, size_type>
       , dtl::is_input_iterator<FwdIt>
       >::type
       insert(const_iterator p, FwdIt first, FwdIt last)
    {
       BOOST_ASSERT(this->priv_in_range_or_end(p));
       const size_type num_new = boost::container::iterator_udistance(first, last);
       const size_type idx     = static_cast<size_type>(p - this->cbegin());
       if(num_new){
          //Fills the node pool and inserts num_new null pointers in idx.
          //If a new buffer was needed fixes up pointers up to idx so
          //past-new nodes are not aligned until the end of this function
          //or in a rollback in case of exception
          index_iterator it_past_newly_constructed(this->priv_insert_forward_non_templated(idx, num_new));
          const index_iterator it_past_new(it_past_newly_constructed + difference_type(num_new));
          {
             //Prepare rollback
             insert_rollback rollback(*this, it_past_newly_constructed, it_past_new);
             while(first != last){
                const node_ptr n = this->priv_get_from_pool();
                BOOST_ASSERT(!!n);
                //Put it in the index so rollback can return it in pool if construct_in_place throws
                *it_past_newly_constructed = n;
                //Constructs and fixes up pointers This can throw
                this->priv_build_node_from_it(n, it_past_newly_constructed, first);
                ++first;
                ++it_past_newly_constructed;
             }
             //rollback.~insert_rollback() called in case of exception
          }
          //Fix up pointers for past-new nodes (new nodes were fixed during construction) and
          //nodes before insertion p in priv_insert_forward_non_templated(...)
          index_traits_type::fix_up_pointers_from(this->index, it_past_newly_constructed);
       }
       return this->begin() + static_cast<difference_type>(idx);
    }
    #endif
 
    //! <b>Effects</b>: Removes the last element from the stable_vector.
    //!
    //! <b>Throws</b>: Nothing.
    //!
    //! <b>Complexity</b>: Constant time.
    inline void pop_back() BOOST_NOEXCEPT_OR_NOTHROW
    {
       BOOST_ASSERT(!this->empty());
       this->erase(--this->cend());
    }
 
    //! <b>Effects</b>: Erases the element at p.
    //!
    //! <b>Throws</b>: Nothing.
    //!
    //! <b>Complexity</b>: Linear to the elements between p and the
    //!   last element. Constant if p is the last element.
    inline iterator erase(const_iterator p) BOOST_NOEXCEPT_OR_NOTHROW
    {
       BOOST_ASSERT(this->priv_in_range(p));
       BOOST_CONTAINER_STABLE_VECTOR_CHECK_INVARIANT;
       const difference_type d = p - this->cbegin();
       index_iterator it = this->index.begin() + d;
       this->priv_delete_node(p.node_pointer());
       it = this->index.erase(it);
       index_traits_type::fix_up_pointers_from(this->index, it);
       return iterator(node_ptr_traits::static_cast_from(*it));
    }
 
    //! <b>Effects</b>: Erases the elements pointed by [first, last).
    //!
    //! <b>Throws</b>: Nothing.
    //!
    //! <b>Complexity</b>: Linear to the distance between first and last
    //!   plus linear to the elements between p and the last element.
    iterator erase(const_iterator first, const_iterator last) BOOST_NOEXCEPT_OR_NOTHROW
    {
       BOOST_ASSERT(first == last ||
          (first < last && this->priv_in_range(first) && this->priv_in_range_or_end(last)));
       BOOST_CONTAINER_STABLE_VECTOR_CHECK_INVARIANT;
       const const_iterator cbeg(this->cbegin());
       const size_type d1 = static_cast<size_type>(first - cbeg),
                       d2 = static_cast<size_type>(last  - cbeg);
       size_type d_dif = d2 - d1;
       if(d_dif){
          multiallocation_chain holder;
          const index_iterator it1(this->index.begin() + difference_type(d1));
          const index_iterator it2(it1 + difference_type(d_dif));
          index_iterator it(it1);
          while(d_dif){
             --d_dif;
             node_base_ptr &nb = *it;
             ++it;
             node_type &n = *node_ptr_traits::static_cast_from(nb);
             this->priv_destroy_node(n);
             holder.push_back(node_ptr_traits::pointer_to(n));
          }
          this->priv_put_in_pool(holder);
          const index_iterator e = this->index.erase(it1, it2);
          index_traits_type::fix_up_pointers_from(this->index, e);
       }
       return iterator(last.node_pointer());
    }
 
    //! <b>Effects</b>: Swaps the contents of *this and x.
    //!
    //! <b>Throws</b>: Nothing.
    //!
    //! <b>Complexity</b>: Constant.
    void swap(stable_vector & x)
       BOOST_NOEXCEPT_IF( allocator_traits_type::propagate_on_container_swap::value
                                 || allocator_traits_type::is_always_equal::value)
    {
       BOOST_ASSERT(allocator_traits_type::propagate_on_container_swap::value ||
                    allocator_traits_type::is_always_equal::value ||
                    this->get_stored_allocator() == x.get_stored_allocator());
       BOOST_CONTAINER_STABLE_VECTOR_CHECK_INVARIANT;
       dtl::bool_<allocator_traits_type::propagate_on_container_swap::value> flag;
       dtl::swap_alloc(this->priv_node_alloc(), x.priv_node_alloc(), flag);
       //vector's allocator is swapped here
       this->index.swap(x.index);
       this->priv_swap_members(x);
    }
 
    //! <b>Effects</b>: Erases all the elements of the stable_vector.
    //!
    //! <b>Throws</b>: Nothing.
    //!
    //! <b>Complexity</b>: Linear to the number of elements in the stable_vector.
    inline void clear() BOOST_NOEXCEPT_OR_NOTHROW
    {   this->erase(this->cbegin(),this->cend()); }
 
    //! <b>Effects</b>: Returns true if x and y are equal
    //!
    //! <b>Complexity</b>: Linear to the number of elements in the container.
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       friend bool operator==(const stable_vector& x, const stable_vector& y)
    {  return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin());  }
 
    //! <b>Effects</b>: Returns true if x and y are unequal
    //!
    //! <b>Complexity</b>: Linear to the number of elements in the container.
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       friend bool operator!=(const stable_vector& x, const stable_vector& y)
    {  return !(x == y); }
 
    //! <b>Effects</b>: Returns true if x is less than y
    //!
    //! <b>Complexity</b>: Linear to the number of elements in the container.
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       friend bool operator<(const stable_vector& x, const stable_vector& y)
    {  return ::boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());  }
 
    //! <b>Effects</b>: Returns true if x is greater than y
    //!
    //! <b>Complexity</b>: Linear to the number of elements in the container.
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       friend bool operator>(const stable_vector& x, const stable_vector& y)
    {  return y < x;  }
 
    //! <b>Effects</b>: Returns true if x is equal or less than y
    //!
    //! <b>Complexity</b>: Linear to the number of elements in the container.
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       friend bool operator<=(const stable_vector& x, const stable_vector& y)
    {  return !(y < x);  }
 
    //! <b>Effects</b>: Returns true if x is equal or greater than y
    //!
    //! <b>Complexity</b>: Linear to the number of elements in the container.
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       friend bool operator>=(const stable_vector& x, const stable_vector& y)
    {  return !(x < y);  }
 
    //! <b>Effects</b>: x.swap(y)
    //!
    //! <b>Complexity</b>: Constant.
    inline friend void swap(stable_vector& x, stable_vector& y)
        BOOST_NOEXCEPT_IF(BOOST_NOEXCEPT(x.swap(y)))
    {  x.swap(y);  }
 
    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
    private:
 
    void priv_move_assign(BOOST_RV_REF(stable_vector) x, dtl::bool_<true> /*steal_resources*/)
    {
       //Resources can be transferred if both allocators are
       //going to be equal after this function (either propagated or already equal)
       BOOST_CONTAINER_STABLE_VECTOR_CHECK_INVARIANT
       //Destroy objects but retain memory in case x reuses it in the future
       this->clear();
       //Move allocator if needed
       dtl::bool_<allocator_traits_type::
                  propagate_on_container_move_assignment::value> flag;
       dtl::move_alloc(this->priv_node_alloc(), x.priv_node_alloc(), flag);
 
       //Take resources
       this->index = boost::move(x.index); //this also moves the vector's allocator if needed
       this->priv_swap_members(x);
    }
 
    void priv_move_assign(BOOST_RV_REF(stable_vector) x, dtl::bool_<false> /*steal_resources*/)
    {
       //We can't guarantee a compile-time equal allocator or propagation so fallback to runtime
       //Resources can be transferred if both allocators are equal
       if (this->priv_node_alloc() == x.priv_node_alloc()) {
          this->priv_move_assign(boost::move(x), dtl::true_());
       }
       else {
          this->assign(boost::make_move_iterator(x.begin()), boost::make_move_iterator(x.end()));
       }
    }
 
    bool priv_in_range(const_iterator pos) const
    {
       return (this->begin() <= pos) && (pos < this->end());
    }
 
    inline bool priv_in_range_or_end(const_iterator pos) const
    {
       return (this->begin() <= pos) && (pos <= this->end());
    }
 
    inline size_type priv_index_of(node_ptr p) const
    {
       //Check range
       BOOST_ASSERT(this->index.empty() || (this->index.data() <= p->up));
       BOOST_ASSERT(this->index.empty() || p->up <= (this->index.data() + this->index.size()));
       return this->index.empty() ? 0u : size_type(p->up - this->index.data());
    }
 
    class insert_rollback
    {
       public:
 
       insert_rollback(stable_vector &sv, index_iterator &it_past_constructed, const index_iterator &it_past_new)
          : m_sv(sv), m_it_past_constructed(it_past_constructed), m_it_past_new(it_past_new)
       {}
 
       ~insert_rollback()
       {
          if(m_it_past_constructed != m_it_past_new){
             m_sv.priv_put_in_pool(node_ptr_traits::static_cast_from(*m_it_past_constructed));
             index_iterator e = m_sv.index.erase(m_it_past_constructed, m_it_past_new);
             index_traits_type::fix_up_pointers_from(m_sv.index, e);
          }
       }
 
       private:
       stable_vector &m_sv;
       index_iterator &m_it_past_constructed;
       const index_iterator &m_it_past_new;
    };
 
    class push_back_rollback
    {
       public:
       inline push_back_rollback(stable_vector &sv, const node_ptr &p)
          : m_sv(sv), m_p(p)
       {}
 
       inline ~push_back_rollback()
       {
          if(m_p){
             m_sv.priv_put_in_pool(m_p);
          }
       }
 
       inline void release()
       {  m_p = node_ptr();  }
 
       private:
       stable_vector &m_sv;
       node_ptr m_p;
    };
 
    index_iterator priv_insert_forward_non_templated(size_type idx, size_type num_new)
    {
       index_traits_type::initialize_end_node(this->index, this->internal_data.end_node, num_new);
 
       //Now try to fill the pool with new data
       if(this->internal_data.pool_size < num_new){
          this->priv_increase_pool(num_new - this->internal_data.pool_size);
       }
 
       //Now try to make room in the vector
       const node_base_ptr_ptr old_buffer = this->index.data();
       this->index.insert(this->index.begin() + (difference_type)idx, num_new, node_ptr());
       bool new_buffer = this->index.data() != old_buffer;
 
       //Fix the pointers for the newly allocated buffer
       const index_iterator index_beg = this->index.begin();
       if(new_buffer){
          index_traits_type::fix_up_pointers(index_beg, index_beg + (difference_type)idx);
       }
       return index_beg + (difference_type)idx;
    }
 
    inline bool priv_capacity_bigger_than_size() const
    {
       return this->index.capacity() > this->index.size() &&
              this->internal_data.pool_size > 0;
    }
 
    template <class U>
    void priv_push_back(BOOST_MOVE_CATCH_FWD(U) x)
    {
       if(BOOST_LIKELY(this->priv_capacity_bigger_than_size())){
          //Enough memory in the pool and in the index
          const node_ptr p = this->priv_get_from_pool();
          BOOST_ASSERT(!!p);
          {
             push_back_rollback rollback(*this, p);
             //This might throw
             this->priv_build_node_from_convertible(p, ::boost::forward<U>(x));
             rollback.release();
          }
          //This can't throw as there is room for a new elements in the index
          index_iterator new_index = this->index.insert(this->index.end() - ExtraPointers, p);
          index_traits_type::fix_up_pointers_from(this->index, new_index);
       }
       else{
          this->insert(this->cend(), ::boost::forward<U>(x));
       }
    }
 
    iterator priv_insert(const_iterator p, const value_type &t)
    {
       BOOST_ASSERT(this->priv_in_range_or_end(p));
       typedef constant_iterator<value_type> cvalue_iterator;
       return this->insert(p, cvalue_iterator(t, 1), cvalue_iterator());
    }
 
    iterator priv_insert(const_iterator p, BOOST_RV_REF(T) x)
    {
       BOOST_ASSERT(this->priv_in_range_or_end(p));
       typedef repeat_iterator<T>  repeat_it;
       typedef boost::move_iterator<repeat_it>      repeat_move_it;
       //Just call more general insert(p, size, value) and return iterator
       return this->insert(p, repeat_move_it(repeat_it(x, 1)), repeat_move_it(repeat_it()));
    }
 
    void priv_clear_pool()
    {
       if(!this->index.empty() && this->index.back()){
          node_base_ptr &pool_first_ref = *(this->index.end() - 2);
          node_base_ptr &pool_last_ref  = this->index.back();
 
          multiallocation_chain holder;
          holder.incorporate_after( holder.before_begin()
                                  , node_ptr_traits::static_cast_from(pool_first_ref)
                                  , node_ptr_traits::static_cast_from(pool_last_ref)
                                  , internal_data.pool_size);
          this->deallocate_individual(holder);
          pool_first_ref = pool_last_ref = 0;
          this->internal_data.pool_size = 0;
       }
    }
 
    void priv_increase_pool(size_type n)
    {
       node_base_ptr &pool_first_ref = *(this->index.end() - 2);
       node_base_ptr &pool_last_ref  = this->index.back();
       multiallocation_chain holder;
       holder.incorporate_after( holder.before_begin()
                               , node_ptr_traits::static_cast_from(pool_first_ref)
                               , node_ptr_traits::static_cast_from(pool_last_ref)
                               , internal_data.pool_size);
       multiallocation_chain m;
       this->allocate_individual(n, m);
       holder.splice_after(holder.before_begin(), m, m.before_begin(), m.last(), n);
       this->internal_data.pool_size += n;
       typename multiallocation_chain::pointer_pair data(holder.extract_data());
       pool_first_ref = data.first;
       pool_last_ref = data.second;
    }
 
    void priv_put_in_pool(const node_ptr &p)
    {
       node_base_ptr &pool_first_ref = *(this->index.end()-2);
       node_base_ptr &pool_last_ref  = this->index.back();
       multiallocation_chain holder;
       holder.incorporate_after( holder.before_begin()
                               , node_ptr_traits::static_cast_from(pool_first_ref)
                               , node_ptr_traits::static_cast_from(pool_last_ref)
                               , internal_data.pool_size);
       holder.push_front(p);
       ++this->internal_data.pool_size;
       typename multiallocation_chain::pointer_pair ret(holder.extract_data());
       pool_first_ref = ret.first;
       pool_last_ref  = ret.second;
    }
 
    void priv_put_in_pool(multiallocation_chain &ch)
    {
       node_base_ptr &pool_first_ref = *(this->index.end()-(ExtraPointers-1));
       node_base_ptr &pool_last_ref  = this->index.back();
       ch.incorporate_after( ch.before_begin()
                           , node_ptr_traits::static_cast_from(pool_first_ref)
                           , node_ptr_traits::static_cast_from(pool_last_ref)
                           , internal_data.pool_size);
       this->internal_data.pool_size = ch.size();
       const typename multiallocation_chain::pointer_pair ret(ch.extract_data());
       pool_first_ref = ret.first;
       pool_last_ref  = ret.second;
    }
 
    node_ptr priv_get_from_pool()
    {
       //Precondition: index is not empty
       BOOST_ASSERT(!this->index.empty());
       node_base_ptr &pool_first_ref = *(this->index.end() - (ExtraPointers-1));
       node_base_ptr &pool_last_ref  = this->index.back();
       multiallocation_chain holder;
       holder.incorporate_after( holder.before_begin()
                               , node_ptr_traits::static_cast_from(pool_first_ref)
                               , node_ptr_traits::static_cast_from(pool_last_ref)
                               , internal_data.pool_size);
       node_ptr ret = holder.pop_front();
       --this->internal_data.pool_size;
       if(!internal_data.pool_size){
          pool_first_ref = pool_last_ref = node_ptr();
       }
       else{
          const typename multiallocation_chain::pointer_pair data(holder.extract_data());
          pool_first_ref = data.first;
          pool_last_ref  = data.second;
       }
       return ret;
    }
 
    inline node_base_ptr priv_get_end_node() const
    {  return node_base_ptr_traits::pointer_to(const_cast<node_base_type&>(this->internal_data.end_node));  }
 
    inline void priv_destroy_node(const node_type &n)
    {
       allocator_traits<node_allocator_type>::
          destroy(this->priv_node_alloc(), &n);
    }
 
    inline void priv_delete_node(const node_ptr &n)
    {
       this->priv_destroy_node(*n);
       this->priv_put_in_pool(n);
    }
 
    template<class Iterator>
    void priv_build_node_from_it(const node_ptr &p, const index_iterator &up_index, const Iterator &it)
    {
       node_type *praw = ::new(boost::movelib::iterator_to_raw_pointer(p), boost_container_new_t())
          node_type(index_traits_type::ptr_to_node_base_ptr(*up_index));
       BOOST_CONTAINER_TRY{
          //This can throw
          boost::container::construct_in_place
             ( this->priv_node_alloc()
             , praw->get_data_ptr()
             , it);
       }
       BOOST_CONTAINER_CATCH(...) {
          praw->destroy_header();
          this->priv_node_alloc().deallocate(p, 1);
          BOOST_CONTAINER_RETHROW
       }
       BOOST_CONTAINER_CATCH_END
    }
 
    template<class ValueConvertible>
    void priv_build_node_from_convertible(const node_ptr &p, BOOST_FWD_REF(ValueConvertible) value_convertible)
    {
       node_type *praw = ::new(boost::movelib::iterator_to_raw_pointer(p), boost_container_new_t()) node_type;
       BOOST_CONTAINER_TRY{
          //This can throw
          boost::container::allocator_traits<node_allocator_type>::construct
             ( this->priv_node_alloc()
             , p->get_data_ptr()
             , ::boost::forward<ValueConvertible>(value_convertible));
       }
       BOOST_CONTAINER_CATCH(...) {
          praw->destroy_header();
          this->priv_node_alloc().deallocate(p, 1);
          BOOST_CONTAINER_RETHROW
       }
       BOOST_CONTAINER_CATCH_END
    }
 
    void priv_swap_members(stable_vector &x)
    {
       boost::adl_move_swap(this->internal_data.pool_size, x.internal_data.pool_size);
       index_traits_type::readjust_end_node(this->index, this->internal_data.end_node);
       index_traits_type::readjust_end_node(x.index, x.internal_data.end_node);
    }
 
    #if defined(STABLE_VECTOR_ENABLE_INVARIANT_CHECKING)
    bool priv_invariant()const
    {
       index_type & index_ref =  const_cast<index_type&>(this->index);
 
       const size_type index_size = this->index.size();
       if(!index_size)
          return !this->capacity() && !this->size();
 
       if(index_size < ExtraPointers)
          return false;
 
       const size_type bucket_extra_capacity = this->index.capacity()- index_size;
       const size_type node_extra_capacity   = this->internal_data.pool_size;
       if(bucket_extra_capacity < node_extra_capacity){
          return false;
       }
 
       if(this->priv_get_end_node() != *(index.end() - ExtraPointers)){
          return false;
       }
 
       if(!index_traits_type::invariants(index_ref)){
          return false;
       }
 
       size_type n = this->capacity() - this->size();
       node_base_ptr &pool_first_ref = *(index_ref.end() - (ExtraPointers-1));
       node_base_ptr &pool_last_ref  = index_ref.back();
       multiallocation_chain holder;
       holder.incorporate_after( holder.before_begin()
                               , node_ptr_traits::static_cast_from(pool_first_ref)
                               , node_ptr_traits::static_cast_from(pool_last_ref)
                               , internal_data.pool_size);
       typename multiallocation_chain::iterator b(holder.begin()), e(holder.end());
       size_type num_pool = 0;
       while(b != e){
          ++num_pool;
          ++b;
       }
       return n >= num_pool && num_pool == internal_data.pool_size;
    }
 
    class invariant_checker
    {
       invariant_checker(const invariant_checker &);
       invariant_checker & operator=(const invariant_checker &);
       const stable_vector* p;
 
       public:
       invariant_checker(const stable_vector& v):p(&v){}
       ~invariant_checker(){BOOST_ASSERT(p->priv_invariant());}
       void touch(){}
    };
    #endif
 
    class ebo_holder
       : public node_allocator_type
    {
       private:
       BOOST_MOVABLE_BUT_NOT_COPYABLE(ebo_holder)
 
       public:
       template<class AllocatorRLValue>
       explicit ebo_holder(BOOST_FWD_REF(AllocatorRLValue) a)
          : node_allocator_type(boost::forward<AllocatorRLValue>(a))
          , pool_size(0)
          , end_node()
       {}
 
       ebo_holder()
          : node_allocator_type()
          , pool_size(0)
          , end_node()
       {}
 
       size_type pool_size;
       node_base_type end_node;
    } internal_data;
 
    node_allocator_type &priv_node_alloc()              { return internal_data;  }
    const node_allocator_type &priv_node_alloc() const  { return internal_data;  }
 
    index_type                           index;
    #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
 };
 
 #ifndef BOOST_CONTAINER_NO_CXX17_CTAD
 
 template <typename InputIterator>
 stable_vector(InputIterator, InputIterator) ->
    stable_vector<typename iterator_traits<InputIterator>::value_type>;
 
 template <typename InputIterator, typename Allocator>
 stable_vector(InputIterator, InputIterator, Allocator const&) ->
    stable_vector<typename iterator_traits<InputIterator>::value_type, Allocator>;
 
 #endif
 
 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
 
 #undef BOOST_CONTAINER_STABLE_VECTOR_CHECK_INVARIANT
 
 }  //namespace container {
 
 //!has_trivial_destructor_after_move<> == true_type
 //!specialization for optimizations
 template <class T, class Allocator>
 struct has_trivial_destructor_after_move<boost::container::stable_vector<T, Allocator> >
 {
    typedef typename boost::container::stable_vector<T, Allocator>::allocator_type allocator_type;
    typedef typename ::boost::container::allocator_traits<allocator_type>::pointer pointer;
    BOOST_STATIC_CONSTEXPR bool value = ::boost::has_trivial_destructor_after_move<allocator_type>::value &&
                              ::boost::has_trivial_destructor_after_move<pointer>::value;
 };
 
 namespace container {
 
 #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
 
 }} //namespace boost{  namespace container {
 
 #include <boost/container/detail/config_end.hpp>
 
 #endif   //BOOST_CONTAINER_STABLE_VECTOR_HPP

This page was automatically generated by the 2.3.7 LXR engine. The LXR team