path: root/boost/container/stable_vector.hpp

//////////////////////////////////////////////////////////////////////////////
//
// (C) Copyright Ion Gaztanaga 2008-2012. 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

#if (defined _MSC_VER) && (_MSC_VER >= 1200)
#  pragma once
#endif

#include <boost/container/detail/config_begin.hpp>
#include <boost/container/detail/workaround.hpp>
#include <boost/container/container_fwd.hpp>
#include <boost/mpl/bool.hpp>
#include <boost/mpl/not.hpp>
#include <boost/type_traits/is_integral.hpp>
#include <boost/container/detail/version_type.hpp>
#include <boost/container/detail/multiallocation_chain.hpp>
#include <boost/container/detail/utilities.hpp>
#include <boost/container/detail/iterators.hpp>
#include <boost/container/detail/algorithms.hpp>
#include <boost/container/allocator_traits.hpp>
#include <boost/intrusive/pointer_traits.hpp>

#include <algorithm>
#include <stdexcept>
#include <memory>

///@cond

#include <boost/container/vector.hpp>

//#define STABLE_VECTOR_ENABLE_INVARIANT_CHECKING

#if defined(STABLE_VECTOR_ENABLE_INVARIANT_CHECKING)
#include <boost/assert.hpp>
#endif

///@endcond

namespace boost {
namespace container {

///@cond

namespace stable_vector_detail{

template<class SmartPtr>
struct smart_ptr_type
{
   typedef typename SmartPtr::value_type value_type;
   typedef value_type *pointer;
   static pointer get (const SmartPtr &smartptr)
   {  return smartptr.get();}
};

template<class T>
struct smart_ptr_type<T*>
{
   typedef T value_type;
   typedef value_type *pointer;
   static pointer get (pointer ptr)
   {  return ptr;}
};

template <class C>
class clear_on_destroy
{
   public:
   clear_on_destroy(C &c)
      :  c_(c), do_clear_(true)
   {}

   void release()
   {  do_clear_ = false; }

   ~clear_on_destroy()
   {
      if(do_clear_){
         c_.clear();
         c_.clear_pool(); 
      }
   }

   private:
   clear_on_destroy(const clear_on_destroy &);
   clear_on_destroy &operator=(const clear_on_destroy &);
   C &c_;
   bool do_clear_;
};

template<class VoidPtr>
struct node_type_base
{
   node_type_base()
   {}
   void set_pointer(const VoidPtr &p)
   {  up = p; }

   VoidPtr up;
};

template<typename VoidPointer, typename T>
struct node_type
   : public node_type_base<VoidPointer>
{
   private:
   node_type();

   public:
   T value;
};

template<typename T, typename Reference, typename Pointer>
class iterator
   : public std::iterator< std::random_access_iterator_tag
                         , T
                         , typename boost::intrusive::
                              pointer_traits<Pointer>::difference_type
                         , Pointer
                         , Reference>
{
   typedef typename boost::intrusive::
      pointer_traits<Pointer>::template
         rebind_pointer<void>::type                void_ptr;
   typedef typename boost::intrusive::
      pointer_traits<Pointer>::template
         rebind_pointer<const void>::type          const_void_ptr;
   typedef node_type<void_ptr, T>                  node_type_t;
   typedef typename boost::intrusive::
      pointer_traits<Pointer>::template
         rebind_pointer<node_type_t>::type         node_type_ptr_t;
   typedef typename boost::intrusive::
      pointer_traits<Pointer>::template
         rebind_pointer<const node_type_t>::type   const_node_type_ptr_t;
   typedef typename boost::intrusive::
      pointer_traits<Pointer>::template
         rebind_pointer<void_ptr>::type            void_ptr_ptr;

   friend class iterator<T, const T, typename boost::intrusive::pointer_traits<Pointer>::template rebind_pointer<T>::type>;

   public:
   typedef std::random_access_iterator_tag      iterator_category;
   typedef T                                    value_type;
   typedef typename boost::intrusive::
      pointer_traits<Pointer>::difference_type  difference_type;
   typedef Pointer                              pointer;
   typedef Reference                            reference;

   iterator()
   {}

   explicit iterator(node_type_ptr_t pn)
      : pn(pn)
   {}

   iterator(const iterator<T, T&, typename boost::intrusive::pointer_traits<Pointer>::template rebind_pointer<T>::type>& x)
      : pn(x.pn)
   {}
  
   private:
   static node_type_ptr_t node_ptr_cast(const void_ptr &p)
   {
      return node_type_ptr_t(static_cast<node_type_t*>(container_detail::to_raw_pointer(p)));
   }

   static const_node_type_ptr_t node_ptr_cast(const const_void_ptr &p)
   {
      return const_node_type_ptr_t(static_cast<const node_type_t*>(container_detail::to_raw_pointer(p)));
   }

   static void_ptr_ptr void_ptr_ptr_cast(const void_ptr &p)
   {
      return void_ptr_ptr(static_cast<void_ptr*>(container_detail::to_raw_pointer(p)));
   }

   reference dereference() const
   {  return pn->value; }
   bool equal(const iterator& x) const
   {  return pn==x.pn;  }
   void increment()
   {  pn = node_ptr_cast(*(void_ptr_ptr_cast(pn->up)+1)); }
   void decrement()
   {  pn = node_ptr_cast(*(void_ptr_ptr_cast(pn->up)-1)); }
   void advance(difference_type n)
   {  pn = node_ptr_cast(*(void_ptr_ptr_cast(pn->up)+n)); }
   difference_type distance_to(const iterator& x)const
   {  return void_ptr_ptr_cast(x.pn->up) - void_ptr_ptr_cast(pn->up);   }

   public:
   //Pointer like operators
   reference operator*()  const {  return  this->dereference();  }
   pointer   operator->() const {  return  pointer(&this->dereference());  }

   //Increment / Decrement
   iterator& operator++() 
   {  this->increment(); return *this;  }

   iterator operator++(int)
   {  iterator tmp(*this);  ++*this; return iterator(tmp); }

   iterator& operator--()
   {  this->decrement(); return *this;  }

   iterator operator--(int)
   {  iterator tmp(*this);  --*this; return iterator(tmp);  }

   reference operator[](difference_type off) const
   {
      iterator tmp(*this);
      tmp += off;
      return *tmp;
   }

   iterator& operator+=(difference_type off)
   {
      pn = node_ptr_cast(*(void_ptr_ptr_cast(pn->up)+off));
      return *this;
   }

   friend iterator operator+(const iterator &left, difference_type off)
   {
      iterator tmp(left);
      tmp += off;
      return tmp;
   }

   friend iterator operator+(difference_type off, const iterator& right)
   {
      iterator tmp(right);
      tmp += off;
      return tmp;
   }

   iterator& operator-=(difference_type off)
   {  *this += -off; return *this;   }

   friend iterator operator-(const iterator &left, difference_type off)
   {
      iterator tmp(left);
      tmp -= off;
      return tmp;
   }

   friend difference_type operator-(const iterator& left, const iterator& right)
   {
      return void_ptr_ptr_cast(left.pn->up) - void_ptr_ptr_cast(right.pn->up);
   }

   //Comparison operators
   friend bool operator==   (const iterator& l, const iterator& r)
   {  return l.pn == r.pn;  }

   friend bool operator!=   (const iterator& l, const iterator& r)
   {  return l.pn != r.pn;  }

   friend bool operator<    (const iterator& l, const iterator& r)
   {  return void_ptr_ptr_cast(l.pn->up) < void_ptr_ptr_cast(r.pn->up);  }

   friend bool operator<=   (const iterator& l, const iterator& r)
   {  return void_ptr_ptr_cast(l.pn->up) <= void_ptr_ptr_cast(r.pn->up);  }

   friend bool operator>    (const iterator& l, const iterator& r)
   {  return void_ptr_ptr_cast(l.pn->up) > void_ptr_ptr_cast(r.pn->up);  }

   friend bool operator>=   (const iterator& l, const iterator& r)
   {  return void_ptr_ptr_cast(l.pn->up) >= void_ptr_ptr_cast(r.pn->up);  }

   node_type_ptr_t pn;
};

template<class A, unsigned int Version>
struct select_multiallocation_chain
{
   typedef typename A::multiallocation_chain type;
};

template<class A>
struct select_multiallocation_chain<A, 1>
{
   typedef typename boost::intrusive::pointer_traits
      <typename allocator_traits<A>::pointer>::
         template rebind_pointer<void>::type                void_ptr;
   typedef container_detail::basic_multiallocation_chain
      <void_ptr>                                            multialloc_cached_counted;
   typedef boost::container::container_detail::
      transform_multiallocation_chain
         < multialloc_cached_counted
         , typename allocator_traits<A>::value_type>        type;
};

} //namespace stable_vector_detail

#if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)

#if defined(STABLE_VECTOR_ENABLE_INVARIANT_CHECKING)

#define STABLE_VECTOR_CHECK_INVARIANT \
invariant_checker BOOST_JOIN(check_invariant_,__LINE__)(*this); \
BOOST_JOIN(check_invariant_,__LINE__).touch();
#else

#define STABLE_VECTOR_CHECK_INVARIANT

#endif   //#if defined(STABLE_VECTOR_ENABLE_INVARIANT_CHECKING)

#endif   //#if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)

/// @endcond

//! Originally developed by Joaquin M. Lopez Munoz, stable_vector is std::vector
//! drop-in replacement implemented as a node container, offering iterator and reference
//! stability.
//!
//! More details taken 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:
#ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
template <class T, class A = std::allocator<T> >
#else
template <class T, class A>
#endif
class stable_vector
{
   ///@cond
   typedef allocator_traits<A>                        allocator_traits_type;
   typedef typename container_detail::
      move_const_ref_type<T>::type                    insert_const_ref_type;
   typedef typename boost::intrusive::pointer_traits
      <typename allocator_traits_type::pointer>::
         template rebind_pointer<void>::type          void_ptr;
   typedef typename boost::intrusive::pointer_traits
      <void_ptr>::template
         rebind_pointer<const void>::type             const_void_ptr;
   typedef typename boost::intrusive::pointer_traits
      <void_ptr>::template
         rebind_pointer<void_ptr>::type               void_ptr_ptr;
   typedef typename boost::intrusive::pointer_traits
      <void_ptr>::template
         rebind_pointer<const void_ptr>::type         const_void_ptr_ptr;
   typedef stable_vector_detail::node_type
      <void_ptr, T>                                   node_type_t;
   typedef typename boost::intrusive::pointer_traits
      <void_ptr>::template
         rebind_pointer<node_type_t>::type            node_type_ptr_t;
   typedef stable_vector_detail::node_type_base
      <void_ptr>                                      node_type_base_t;
   typedef typename boost::intrusive::pointer_traits
      <void_ptr>::template
         rebind_pointer<node_type_base_t>::type       node_type_base_ptr_t;
   typedef ::boost::container::vector<void_ptr,
      typename allocator_traits_type::
         template portable_rebind_alloc
            <void_ptr>::type>                         impl_type;
   typedef typename impl_type::iterator               impl_iterator;
   typedef typename impl_type::const_iterator         const_impl_iterator;

   typedef ::boost::container::container_detail::
      integral_constant<unsigned, 1>                  allocator_v1;
   typedef ::boost::container::container_detail::
      integral_constant<unsigned, 2>                  allocator_v2;
   typedef ::boost::container::container_detail::integral_constant
      <unsigned, boost::container::container_detail::
      version<A>::value>                              alloc_version;
   typedef typename allocator_traits_type::
      template portable_rebind_alloc
         <node_type_t>::type                          node_allocator_type;

   node_type_ptr_t allocate_one()
   {  return this->allocate_one(alloc_version());   }

   template<class AllocatorVersion>
   node_type_ptr_t allocate_one(AllocatorVersion,
      typename boost::container::container_detail::enable_if_c
         <boost::container::container_detail::is_same<AllocatorVersion, allocator_v1>
            ::value>::type * = 0)
   {  return node_alloc().allocate(1);   }

   template<class AllocatorVersion>
   node_type_ptr_t allocate_one(AllocatorVersion,
      typename boost::container::container_detail::enable_if_c
         <!boost::container::container_detail::is_same<AllocatorVersion, allocator_v1>
            ::value>::type * = 0)
   {  return node_alloc().allocate_one();   }

   void deallocate_one(node_type_ptr_t p)
   {  return this->deallocate_one(p, alloc_version());   }

   template<class AllocatorVersion>
   void deallocate_one(node_type_ptr_t p, AllocatorVersion,
      typename boost::container::container_detail::enable_if_c
         <boost::container::container_detail::is_same<AllocatorVersion, allocator_v1>
            ::value>::type * = 0)
   {  node_alloc().deallocate(p, 1);   }

   template<class AllocatorVersion>
   void deallocate_one(node_type_ptr_t p, AllocatorVersion,
      typename boost::container::container_detail::enable_if_c
         <!boost::container::container_detail::is_same<AllocatorVersion, allocator_v1>
            ::value>::type * = 0)
   {  node_alloc().deallocate_one(p);   }

   friend class stable_vector_detail::clear_on_destroy<stable_vector>;
   ///@endcond
   public:


   // types:

   typedef typename allocator_traits_type::reference              reference;
   typedef typename allocator_traits_type::const_reference        const_reference;
   typedef typename allocator_traits_type::pointer                pointer;
   typedef typename allocator_traits_type::const_pointer          const_pointer;
   typedef stable_vector_detail::iterator
      <T,T&, pointer>                                 iterator;
   typedef stable_vector_detail::iterator
      <T,const T&, const_pointer>                     const_iterator;
   typedef typename impl_type::size_type              size_type;
   typedef typename iterator::difference_type         difference_type;
   typedef T                                          value_type;
   typedef A                                          allocator_type;
   typedef std::reverse_iterator<iterator>            reverse_iterator;
   typedef std::reverse_iterator<const_iterator>      const_reverse_iterator;
   typedef node_allocator_type                        stored_allocator_type;

   ///@cond
   private:
   BOOST_COPYABLE_AND_MOVABLE(stable_vector)
   static const size_type ExtraPointers = 3;
   //This container stores metadata at the end of the void_ptr vector with additional 3 pointers:
   //    back() is impl.back() - ExtraPointers;
   //    end node index is impl.end()[-3]
   //    Node cache first is impl.end()[-2];
   //    Node cache last is  *impl.back();

   typedef typename stable_vector_detail::
      select_multiallocation_chain
      < node_allocator_type
      , alloc_version::value
      >::type                                         multiallocation_chain;
   ///@endcond
   public:

   //! <b>Effects</b>: Default constructs a stable_vector.
   //!
   //! <b>Throws</b>: If allocator_type's default constructor throws.
   //!
   //! <b>Complexity</b>: Constant.
   stable_vector()
      : internal_data(), impl()
   {
      STABLE_VECTOR_CHECK_INVARIANT;
   }

   //! <b>Effects</b>: Constructs a stable_vector taking the allocator as parameter.
   //!
   //! <b>Throws</b>: If allocator_type's copy constructor throws.
   //!
   //! <b>Complexity</b>: Constant.
   explicit stable_vector(const allocator_type& al)
      : internal_data(al),impl(al)
   {
      STABLE_VECTOR_CHECK_INVARIANT;
   }

   //! <b>Effects</b>: Constructs a stable_vector that will use a copy of allocator a
   //!   and inserts n default contructed values.
   //!
   //! <b>Throws</b>: If allocator_type's default constructor or copy constructor
   //!   throws or T's default or copy constructor throws.
   //!
   //! <b>Complexity</b>: Linear to n.
   explicit stable_vector(size_type n)
      : internal_data(),impl()
   {
      stable_vector_detail::clear_on_destroy<stable_vector> cod(*this);
      this->resize(n);
      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 or copy 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),impl(al)
   {
      stable_vector_detail::clear_on_destroy<stable_vector> cod(*this);
      this->insert(this->cbegin(), n, t);
      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 or copy constructor
   //!   throws or T's constructor taking an 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),impl(al)
   {
      stable_vector_detail::clear_on_destroy<stable_vector> cod(*this);
      this->insert(this->cbegin(), first, last);
      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.node_alloc()))
      , impl(allocator_traits<allocator_type>::
         select_on_container_copy_construction(x.impl.get_stored_allocator()))
   {
      stable_vector_detail::clear_on_destroy<stable_vector> cod(*this);
      this->insert(this->cbegin(), x.begin(), x.end());
      STABLE_VECTOR_CHECK_INVARIANT;
      cod.release();
   }

   //! <b>Effects</b>: Move constructor. Moves mx's resources to *this.
   //!
   //! <b>Throws</b>: If allocator_type's copy constructor throws.
   //!
   //! <b>Complexity</b>: Constant.
   stable_vector(BOOST_RV_REF(stable_vector) x)
      : internal_data(boost::move(x.node_alloc())), impl(boost::move(x.impl))
   {
      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), impl(a)
   {
      stable_vector_detail::clear_on_destroy<stable_vector> cod(*this);
      this->insert(this->cbegin(), x.begin(), x.end());
      STABLE_VECTOR_CHECK_INVARIANT;
      cod.release();
   }

   //! <b>Effects</b>: Move constructor using the specified allocator.
   //!                 Moves mx'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), impl(a)
   {
      if(this->node_alloc() == x.node_alloc()){
         this->priv_swap_members(x);
      }
      else{
         stable_vector_detail::clear_on_destroy<stable_vector> cod(*this);
         this->insert(this->cbegin(), x.begin(), x.end());
         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();
      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)
   {
      STABLE_VECTOR_CHECK_INVARIANT;
      if (&x != this){
         node_allocator_type &this_alloc     = this->node_alloc();
         const node_allocator_type &x_alloc  = x.node_alloc();
         container_detail::bool_<allocator_traits_type::
            propagate_on_container_copy_assignment::value> flag;
         if(flag && this_alloc != x_alloc){
            this->clear();
            this->shrink_to_fit();
         }
         container_detail::assign_alloc(this->node_alloc(), x.node_alloc(), flag);
         container_detail::assign_alloc(this->impl.get_stored_allocator(), x.impl.get_stored_allocator(), flag);
         this->assign(x.begin(), x.end());
      }
      return *this;
   }

   //! <b>Effects</b>: Move assignment. All mx'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_type's copy constructor throws.
   //!
   //! <b>Complexity</b>: Linear.
   stable_vector& operator=(BOOST_RV_REF(stable_vector) x)
   {
      if (&x != this){
         node_allocator_type &this_alloc = this->node_alloc();
         node_allocator_type &x_alloc    = x.node_alloc();
         //If allocators are equal we can just swap pointers
         if(this_alloc == x_alloc){
            //Destroy objects but retain memory
            this->clear();
            this->impl = boost::move(x.impl);
            this->priv_swap_members(x);
            //Move allocator if needed
            container_detail::bool_<allocator_traits_type::
               propagate_on_container_move_assignment::value> flag;
            container_detail::move_alloc(this->node_alloc(), x.node_alloc(), flag);
         }
         //If unequal allocators, then do a one by one move
         else{
            typedef typename std::iterator_traits<iterator>::iterator_category ItCat;
            this->assign( boost::make_move_iterator(x.begin())
                        , boost::make_move_iterator(x.end()));
         }
      }
      return *this;
   }

   //! <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>
   void assign(InputIterator first,InputIterator last)
   {
      assign_dispatch(first, last, boost::is_integral<InputIterator>());
   }


   //! <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.
   void assign(size_type n,const T& t)
   {
      typedef constant_iterator<value_type, difference_type> cvalue_iterator;
      return assign_dispatch(cvalue_iterator(t, n), cvalue_iterator(), boost::mpl::false_());
   }

   //! <b>Effects</b>: Returns a copy of the internal allocator.
   //!
   //! <b>Throws</b>: If allocator's copy constructor throws.
   //!
   //! <b>Complexity</b>: Constant.
   allocator_type get_allocator()const  {return this->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.
   const stored_allocator_type &get_stored_allocator() const BOOST_CONTAINER_NOEXCEPT
   {  return 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.
   stored_allocator_type &get_stored_allocator() BOOST_CONTAINER_NOEXCEPT
   {  return node_alloc(); }


   //! <b>Effects</b>: Returns an iterator to the first element contained in the stable_vector.
   //!
   //! <b>Throws</b>: Nothing.
   //!
   //! <b>Complexity</b>: Constant.
   iterator  begin()
   {   return (impl.empty()) ? end(): iterator(node_ptr_cast(impl.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.
   const_iterator  begin()const
   {   return (impl.empty()) ? cend() : const_iterator(node_ptr_cast(impl.front())) ;   }

   //! <b>Effects</b>: Returns an iterator to the end of the stable_vector.
   //!
   //! <b>Throws</b>: Nothing.
   //!
   //! <b>Complexity</b>: Constant.
   iterator        end()                {return iterator(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.
   const_iterator  end()const           {return const_iterator(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.
   reverse_iterator       rbegin()      {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.
   const_reverse_iterator rbegin()const {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.
   reverse_iterator       rend()        {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.
   const_reverse_iterator rend()const   {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.
   const_iterator         cbegin()const {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.
   const_iterator         cend()const   {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.
   const_reverse_iterator crbegin()const{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.
   const_reverse_iterator crend()const  {return this->rend();}

   //! <b>Effects</b>: Returns the number of the elements contained in the stable_vector.
   //!
   //! <b>Throws</b>: Nothing.
   //!
   //! <b>Complexity</b>: Constant.
   size_type size() const
   {  return impl.empty() ? 0 : (impl.size() - ExtraPointers);   }

   //! <b>Effects</b>: Returns the largest possible size of the stable_vector.
   //!
   //! <b>Throws</b>: Nothing.
   //!
   //! <b>Complexity</b>: Constant.
   size_type max_size() const
   {  return impl.max_size() - ExtraPointers;  }

   //! <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.
   size_type capacity() const
   {
      if(!impl.capacity()){
         return 0;
      }
      else{
         const size_type num_nodes = this->impl.size() + this->internal_data.pool_size;
         const size_type num_buck  = this->impl.capacity();
         return (num_nodes < num_buck) ? num_nodes : num_buck;
      }
   }

   //! <b>Effects</b>: Returns true if the stable_vector contains no elements.
   //!
   //! <b>Throws</b>: Nothing.
   //!
   //! <b>Complexity</b>: Constant.
   bool empty() const
   {  return impl.empty() || impl.size() == ExtraPointers;  }

   //! <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)
   {
      STABLE_VECTOR_CHECK_INVARIANT;
      if(n > size())
         this->insert(this->cend(), n - this->size(), t);
      else if(n < this->size())
         this->erase(this->cbegin() + n, this->cend());
   }

   //! <b>Effects</b>: Inserts or erases elements at the end such that
   //!   the size becomes n. New elements are default constructed.
   //!
   //! <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)
   {
      typedef default_construct_iterator<value_type, difference_type> default_iterator;
      STABLE_VECTOR_CHECK_INVARIANT;
      if(n > size())
         this->insert(this->cend(), default_iterator(n - this->size()), default_iterator());
      else if(n < this->size())
         this->erase(this->cbegin() + n, this->cend());
   }

   //! <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)
   {
      STABLE_VECTOR_CHECK_INVARIANT;
      if(n > this->max_size())
         throw std::bad_alloc();

      size_type size = this->size();  
      size_type old_capacity = this->capacity();
      if(n > old_capacity){
         this->initialize_end_node(n);
         const void * old_ptr = &impl[0];
         impl.reserve(n + ExtraPointers);
         bool realloced = &impl[0] != old_ptr;
         //Fix the pointers for the newly allocated buffer
         if(realloced){
            this->align_nodes(impl.begin(), impl.begin()+size+1);
         }
         //Now fill pool if data is not enough
         if((n - size) > this->internal_data.pool_size){
            this->add_to_pool((n - size) - this->internal_data.pool_size);
         }
      }
   }

   //! <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.
   reference operator[](size_type n){return value(impl[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>: Nothing.
   //!
   //! <b>Complexity</b>: Constant.
   const_reference operator[](size_type n)const{return value(impl[n]);}

   //! <b>Requires</b>: size() > n.
   //!
   //! <b>Effects</b>: Returns a reference to the nth element
   //!   from the beginning of the container.
   //!
   //! <b>Throws</b>: std::range_error if n >= size()
   //!
   //! <b>Complexity</b>: Constant.
   reference at(size_type n)
   {
      if(n>=size())
         throw std::out_of_range("invalid subscript at stable_vector::at");
      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>: std::range_error if n >= size()
   //!
   //! <b>Complexity</b>: Constant.
   const_reference at(size_type n)const
   {
      if(n>=size())
         throw std::out_of_range("invalid subscript at stable_vector::at");
      return operator[](n);
   }

   //! <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.
   reference front()
   {  return value(impl.front());   }

   //! <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.
   const_reference front()const
   {  return value(impl.front());   }

   //! <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.
   reference back()
   {  return value(*(&impl.back() - ExtraPointers)); }

   //! <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.
   const_reference back()const
   {  return value(*(&impl.back() - ExtraPointers)); }

   //! <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(insert_const_ref_type x)
   {  return priv_push_back(x);  }

   #if defined(BOOST_NO_RVALUE_REFERENCES) && !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
   void push_back(T &x) { push_back(const_cast<const T &>(x)); }

   template<class U>
   void push_back(const U &u, typename container_detail::enable_if_c
                  <container_detail::is_same<T, U>::value && !::boost::has_move_emulation_enabled<U>::value >::type* =0)
   { return priv_push_back(u); }
   #endif

   //! <b>Effects</b>: Constructs a new element in the end of the stable_vector
   //!   and moves the resources of mx to this new element.
   //!
   //! <b>Throws</b>: If memory allocation throws.
   //!
   //! <b>Complexity</b>: Amortized constant time.
   void push_back(BOOST_RV_REF(T) t)
   {  this->insert(end(), boost::move(t));  }

   //! <b>Effects</b>: Removes the last element from the stable_vector.
   //!
   //! <b>Throws</b>: Nothing.
   //!
   //! <b>Complexity</b>: Constant time.
   void pop_back()
   {  this->erase(this->end()-1);   }

   //! <b>Requires</b>: position must be a valid iterator of *this.
   //!
   //! <b>Effects</b>: Insert a copy of x before position.
   //!
   //! <b>Throws</b>: If memory allocation throws or x's copy constructor throws.
   //!
   //! <b>Complexity</b>: If position is end(), amortized constant time
   //!   Linear time otherwise.
   iterator insert(const_iterator position, insert_const_ref_type x)
   {  return this->priv_insert(position, x); }

   #if defined(BOOST_NO_RVALUE_REFERENCES) && !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
   iterator insert(const_iterator position, T &x) { return this->insert(position, const_cast<const T &>(x)); }

   template<class U>
   iterator insert(const_iterator position, const U &u, typename container_detail::enable_if_c
                  <container_detail::is_same<T, U>::value && !::boost::has_move_emulation_enabled<U>::value >::type* =0)
   {  return this->priv_insert(position, u); }
   #endif

   //! <b>Requires</b>: position must be a valid iterator of *this.
   //!
   //! <b>Effects</b>: Insert a new element before position with mx's resources.
   //!
   //! <b>Throws</b>: If memory allocation throws.
   //!
   //! <b>Complexity</b>: If position is end(), amortized constant time
   //!   Linear time otherwise.
   iterator insert(const_iterator position, BOOST_RV_REF(T) x)
   {
      typedef repeat_iterator<T, difference_type>           repeat_it;
      typedef boost::move_iterator<repeat_it> repeat_move_it;
      //Just call more general insert(pos, size, value) and return iterator
      size_type pos_n = position - cbegin();
      this->insert(position
         ,repeat_move_it(repeat_it(x, 1))
         ,repeat_move_it(repeat_it()));
      return iterator(this->begin() + pos_n);
   }

   //! <b>Requires</b>: pos must be a valid iterator of *this.
   //!
   //! <b>Effects</b>: Insert n copies of x before pos.
   //!
   //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws.
   //!
   //! <b>Complexity</b>: Linear to n.
   void insert(const_iterator position, size_type n, const T& t)
   {
      STABLE_VECTOR_CHECK_INVARIANT;
      this->insert_not_iter(position, n, t);
   }

   //! <b>Requires</b>: pos must be a valid iterator of *this.
   //!
   //! <b>Effects</b>: Insert a copy of the [first, last) range before pos.
   //!
   //! <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 std::distance [first, last).
   template <class InputIterator>
   void insert(const_iterator position,InputIterator first, InputIterator last)
   {
      STABLE_VECTOR_CHECK_INVARIANT;
      this->insert_iter(position,first,last,
                        boost::mpl::not_<boost::is_integral<InputIterator> >());
   }

   #if defined(BOOST_CONTAINER_PERFECT_FORWARDING) || 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>Throws</b>: If memory allocation throws or the in-place constructor throws.
   //!
   //! <b>Complexity</b>: Amortized constant time.
   template<class ...Args>
   void emplace_back(Args &&...args)
   {
      typedef emplace_functor<Args...>         EmplaceFunctor;
      typedef emplace_iterator<value_type, EmplaceFunctor, difference_type> EmplaceIterator;
      EmplaceFunctor &&ef = EmplaceFunctor(boost::forward<Args>(args)...);
      this->insert(this->cend(), EmplaceIterator(ef), EmplaceIterator());
   }

   //! <b>Requires</b>: position must be a valid iterator of *this.
   //!
   //! <b>Effects</b>: Inserts an object of type T constructed with
   //!   std::forward<Args>(args)... before position
   //!
   //! <b>Throws</b>: If memory allocation throws or the in-place constructor throws.
   //!
   //! <b>Complexity</b>: If position is end(), amortized constant time
   //!   Linear time otherwise.
   template<class ...Args>
   iterator emplace(const_iterator position, Args && ...args)
   {
      //Just call more general insert(pos, size, value) and return iterator
      size_type pos_n = position - cbegin();
      typedef emplace_functor<Args...>         EmplaceFunctor;
      typedef emplace_iterator<value_type, EmplaceFunctor, difference_type> EmplaceIterator;
      EmplaceFunctor &&ef = EmplaceFunctor(boost::forward<Args>(args)...);
      this->insert(position, EmplaceIterator(ef), EmplaceIterator());
      return iterator(this->begin() + pos_n);
   }

   #else

   #define BOOST_PP_LOCAL_MACRO(n)                                                              \
   BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >)       \
   void emplace_back(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _))                        \
   {                                                                                            \
      typedef BOOST_PP_CAT(BOOST_PP_CAT(emplace_functor, n), arg)                               \
         BOOST_PP_EXPR_IF(n, <) BOOST_PP_ENUM_PARAMS(n, P) BOOST_PP_EXPR_IF(n, >)               \
            EmplaceFunctor;                                                                     \
      typedef emplace_iterator<value_type, EmplaceFunctor, difference_type>  EmplaceIterator;   \
      EmplaceFunctor ef BOOST_PP_LPAREN_IF(n)                                                   \
                        BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _)                   \
                        BOOST_PP_RPAREN_IF(n);                                                  \
      this->insert(this->cend() , EmplaceIterator(ef), EmplaceIterator());                      \
   }                                                                                            \
                                                                                                \
   BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >)       \
   iterator emplace(const_iterator pos                                                          \
           BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _))                         \
   {                                                                                            \
      typedef BOOST_PP_CAT(BOOST_PP_CAT(emplace_functor, n), arg)                               \
         BOOST_PP_EXPR_IF(n, <) BOOST_PP_ENUM_PARAMS(n, P) BOOST_PP_EXPR_IF(n, >)               \
            EmplaceFunctor;                                                                     \
      typedef emplace_iterator<value_type, EmplaceFunctor, difference_type>  EmplaceIterator;   \
      EmplaceFunctor ef BOOST_PP_LPAREN_IF(n)                                                   \
                        BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _)                   \
                        BOOST_PP_RPAREN_IF(n);                                                  \
      size_type pos_n = pos - this->cbegin();                                                   \
      this->insert(pos, EmplaceIterator(ef), EmplaceIterator());                                \
      return iterator(this->begin() + pos_n);                                                   \
   }                                                                                            \
   //!
   #define BOOST_PP_LOCAL_LIMITS (0, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS)
   #include BOOST_PP_LOCAL_ITERATE()

   #endif   //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING

   //! <b>Effects</b>: Erases the element at position pos.
   //!
   //! <b>Throws</b>: Nothing.
   //!
   //! <b>Complexity</b>: Linear to the elements between pos and the
   //!   last element. Constant if pos is the last element.
   iterator erase(const_iterator position)
   {
      STABLE_VECTOR_CHECK_INVARIANT;
      difference_type d = position - this->cbegin();
      impl_iterator   it = impl.begin() + d;
      this->delete_node(*it);
      it = impl.erase(it);
      this->align_nodes(it, get_last_align());
      return this->begin()+d;
   }

   //! <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 pos and the last element.
   iterator erase(const_iterator first, const_iterator last)
   {   return priv_erase(first, last, alloc_version());  }

   //! <b>Effects</b>: Swaps the contents of *this and x.
   //!
   //! <b>Throws</b>: Nothing.
   //!
   //! <b>Complexity</b>: Constant.
   void swap(stable_vector & x)
   {
      STABLE_VECTOR_CHECK_INVARIANT;
      container_detail::bool_<allocator_traits_type::propagate_on_container_swap::value> flag;
      container_detail::swap_alloc(this->node_alloc(), x.node_alloc(), flag);
      //vector's allocator is swapped here
      this->impl.swap(x.impl);
      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.
   void clear()
   {   this->erase(this->cbegin(),this->cend()); }

   //! <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->clear_pool();
         //If empty completely destroy the index, let's recover default-constructed state
         if(this->empty()){
            this->impl.clear();
            this->impl.shrink_to_fit();
            this->internal_data.set_end_pointer_to_default_constructed();
         }
         //Otherwise, try to shrink-to-fit the index and readjust pointers if necessary
         else{
            const size_type size = this->size();
            const void* old_ptr = &impl[0];
            this->impl.shrink_to_fit();
            bool realloced = &impl[0] != old_ptr;
            //Fix the pointers for the newly allocated buffer
            if(realloced){
               this->align_nodes(impl.begin(), impl.begin()+size+1);
            }
         }
      }
   }

   /// @cond

   iterator priv_insert(const_iterator position, const value_type &t)
   {
      typedef constant_iterator<value_type, difference_type> cvalue_iterator;
      return this->insert_iter(position, cvalue_iterator(t, 1), cvalue_iterator(), std::forward_iterator_tag());
   }

   void priv_push_back(const value_type &t)
   {  this->insert(end(), t);  }

   template<class AllocatorVersion>
   void clear_pool(AllocatorVersion,
      typename boost::container::container_detail::enable_if_c
         <boost::container::container_detail::is_same<AllocatorVersion, allocator_v1>
            ::value>::type * = 0)
   {
      if(!impl.empty() && impl.back()){
         void_ptr &pool_first_ref = impl.end()[-2];
         void_ptr &pool_last_ref = impl.back();

         multiallocation_chain holder;
         holder.incorporate_after(holder.before_begin(), pool_first_ref, pool_last_ref, this->internal_data.pool_size);
         while(!holder.empty()){
            node_type_ptr_t n = holder.front();
            holder.pop_front();
            this->deallocate_one(n);
         }
         pool_first_ref = pool_last_ref = 0;
         this->internal_data.pool_size = 0;
      }
   }

   template<class AllocatorVersion>
   void clear_pool(AllocatorVersion,
      typename boost::container::container_detail::enable_if_c
         <!boost::container::container_detail::is_same<AllocatorVersion, allocator_v1>
            ::value>::type * = 0)
   {
      if(!impl.empty() && impl.back()){
         void_ptr &pool_first_ref = impl.end()[-2];
         void_ptr &pool_last_ref = impl.back();
         multiallocation_chain holder;
         holder.incorporate_after(holder.before_begin(), pool_first_ref, pool_last_ref, internal_data.pool_size);
         node_alloc().deallocate_individual(boost::move(holder));
         pool_first_ref = pool_last_ref = 0;
         this->internal_data.pool_size = 0;
      }
   }

   void clear_pool()
   {
      this->clear_pool(alloc_version());
   }

   void add_to_pool(size_type n)
   {
      this->add_to_pool(n, alloc_version());
   }

   template<class AllocatorVersion>
   void add_to_pool(size_type n, AllocatorVersion,
      typename boost::container::container_detail::enable_if_c
         <boost::container::container_detail::is_same<AllocatorVersion, allocator_v1>
            ::value>::type * = 0)
   {
      size_type remaining = n;
      while(remaining--){
         this->put_in_pool(this->allocate_one());
      }
   }

   template<class AllocatorVersion>
   void add_to_pool(size_type n, AllocatorVersion,
      typename boost::container::container_detail::enable_if_c
         <!boost::container::container_detail::is_same<AllocatorVersion, allocator_v1>
            ::value>::type * = 0)
   {
      void_ptr &pool_first_ref = impl.end()[-2];
      void_ptr &pool_last_ref = impl.back();
      multiallocation_chain holder;
      holder.incorporate_after(holder.before_begin(), pool_first_ref, pool_last_ref, internal_data.pool_size);
      //BOOST_STATIC_ASSERT((::boost::has_move_emulation_enabled<multiallocation_chain>::value == true));
      multiallocation_chain m (node_alloc().allocate_individual(n));
      holder.splice_after(holder.before_begin(), m, m.before_begin(), m.last(), n);
      this->internal_data.pool_size += n;
      std::pair<void_ptr, void_ptr> data(holder.extract_data());
      pool_first_ref = data.first;
      pool_last_ref = data.second;
   }

   void put_in_pool(node_type_ptr_t p)
   {
      void_ptr &pool_first_ref = impl.end()[-2];
      void_ptr &pool_last_ref = impl.back();
      multiallocation_chain holder;
      holder.incorporate_after(holder.before_begin(), pool_first_ref, pool_last_ref, internal_data.pool_size);
      holder.push_front(p);
      ++this->internal_data.pool_size;
      std::pair<void_ptr, void_ptr> ret(holder.extract_data());
      pool_first_ref = ret.first;
      pool_last_ref = ret.second;
   }

   node_type_ptr_t get_from_pool()
   {
      if(!impl.back()){
         return node_type_ptr_t(0);
      }
      else{
         void_ptr &pool_first_ref = impl.end()[-2];
         void_ptr &pool_last_ref = impl.back();
         multiallocation_chain holder;
         holder.incorporate_after(holder.before_begin(), pool_first_ref, pool_last_ref, internal_data.pool_size);
         node_type_ptr_t ret = holder.front();
         holder.pop_front();
         --this->internal_data.pool_size;
         if(!internal_data.pool_size){
            pool_first_ref = pool_last_ref = void_ptr(0);
         }
         else{
            std::pair<void_ptr, void_ptr> data(holder.extract_data());
            pool_first_ref = data.first;
            pool_last_ref = data.second;
         }
         return ret;
      }
   }

   void insert_iter_prolog(size_type n, difference_type d)
   {
      initialize_end_node(n);
      const void* old_ptr = &impl[0];
      //size_type old_capacity = capacity();
      //size_type old_size = size();
      impl.insert(impl.begin()+d, n, 0);
      bool realloced = &impl[0] != old_ptr;
      //Fix the pointers for the newly allocated buffer
      if(realloced){
         align_nodes(impl.begin(), impl.begin()+d);
      }
   }

   template<typename InputIterator>
   void assign_dispatch(InputIterator first, InputIterator last, boost::mpl::false_)
   {
      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);
      }
   }

   template<typename Integer>
   void assign_dispatch(Integer n, Integer t, boost::mpl::true_)
   {
      typedef constant_iterator<value_type, difference_type> cvalue_iterator;
      this->assign_dispatch(cvalue_iterator(t, n), cvalue_iterator(), boost::mpl::false_());
   }

   iterator priv_erase(const_iterator first, const_iterator last, allocator_v1)
   {
      STABLE_VECTOR_CHECK_INVARIANT;
      difference_type d1 = first - this->cbegin(), d2 = last - this->cbegin();
      if(d1 != d2){
         impl_iterator it1(impl.begin() + d1), it2(impl.begin() + d2);
         for(impl_iterator it = it1; it != it2; ++it)
            this->delete_node(*it);
         impl_iterator e = impl.erase(it1, it2);
         this->align_nodes(e, get_last_align());
      }
      return iterator(this->begin() + d1);
   }

   impl_iterator get_last_align()
   {
      return impl.end() - (ExtraPointers - 1);
   }

   const_impl_iterator get_last_align() const
   {
      return impl.cend() - (ExtraPointers - 1);
   }

   template<class AllocatorVersion>
   iterator priv_erase(const_iterator first, const_iterator last, AllocatorVersion,
      typename boost::container::container_detail::enable_if_c
         <!boost::container::container_detail::is_same<AllocatorVersion, allocator_v1>
            ::value>::type * = 0)
   {
      STABLE_VECTOR_CHECK_INVARIANT;
      return priv_erase(first, last, allocator_v1());
   }

   static node_type_ptr_t node_ptr_cast(const void_ptr &p)
   {
      return node_type_ptr_t(static_cast<node_type_t*>(container_detail::to_raw_pointer(p)));
   }

   static node_type_base_ptr_t node_base_ptr_cast(const void_ptr &p)
   {
      return node_type_base_ptr_t(static_cast<node_type_base_t*>(container_detail::to_raw_pointer(p)));
   }

   static value_type& value(const void_ptr &p)
   {
      return node_ptr_cast(p)->value;
   }

   void initialize_end_node(size_type impl_capacity = 0)
   {
      if(impl.empty()){
         impl.reserve(impl_capacity + ExtraPointers);
         impl.resize (ExtraPointers, void_ptr(0));
         impl[0] = &this->internal_data.end_node;
         this->internal_data.end_node.up = &impl[0];
      }
   }

   void readjust_end_node()
   {
      if(!this->impl.empty()){
         void_ptr &end_node_ref = *(this->get_last_align()-1);
         end_node_ref = this->get_end_node();
         this->internal_data.end_node.up = &end_node_ref;
      }
      else{
         this->internal_data.end_node.up = void_ptr(&this->internal_data.end_node.up);
      }
   }

   node_type_ptr_t get_end_node() const
   {
      const node_type_base_t* cp = &this->internal_data.end_node;
      node_type_base_t* p = const_cast<node_type_base_t*>(cp);
      return node_ptr_cast(p);
   }

   template<class Iter>
   void_ptr new_node(const void_ptr &up, Iter it)
   {
      node_type_ptr_t p = this->allocate_one();
      try{
         boost::container::construct_in_place(this->node_alloc(), container_detail::addressof(p->value), it);
         //This does not throw
         ::new(static_cast<node_type_base_t*>(container_detail::to_raw_pointer(p))) node_type_base_t;
         p->set_pointer(up);
      }
      catch(...){
         this->deallocate_one(p);
         throw;
      }
      return p;
   }

   void delete_node(const void_ptr &p)
   {
      node_type_ptr_t n(node_ptr_cast(p));
      allocator_traits<node_allocator_type>::
         destroy(this->node_alloc(), container_detail::to_raw_pointer(n));
      this->put_in_pool(n);
   }

   static void align_nodes(impl_iterator first, impl_iterator last)
   {
      while(first!=last){
         node_ptr_cast(*first)->up = void_ptr(&*first);
         ++first;
      }
   }

   void insert_not_iter(const_iterator position, size_type n, const T& t)
   {
      typedef constant_iterator<value_type, difference_type> cvalue_iterator;
      this->insert_iter(position, cvalue_iterator(t, n), cvalue_iterator(), std::forward_iterator_tag());
   }

   template <class InputIterator>
   void insert_iter(const_iterator position,InputIterator first,InputIterator last, boost::mpl::true_)
   {
      typedef typename std::iterator_traits<InputIterator>::iterator_category category;
      this->insert_iter(position, first, last, category());
   }

   template <class InputIterator>
   void insert_iter(const_iterator position,InputIterator first,InputIterator last,std::input_iterator_tag)
   {
      for(; first!=last; ++first){
         this->insert(position, *first);
      }   
   }

   template <class InputIterator>
   iterator insert_iter(const_iterator position, InputIterator first, InputIterator last, std::forward_iterator_tag)
   {
      size_type       n = (size_type)std::distance(first,last);
      difference_type d = position-this->cbegin();
      if(n){
         this->insert_iter_prolog(n, d);
         const impl_iterator it(impl.begin() + d);
         this->insert_iter_fwd(it, first, last, n);
         //Fix the pointers for the newly allocated buffer
         this->align_nodes(it + n, get_last_align());
      }
      return this->begin() + d;
   }

   template <class FwdIterator>
   void insert_iter_fwd_alloc(const impl_iterator it, FwdIterator first, FwdIterator last, difference_type n, allocator_v1)
   {
      size_type i=0;
      try{
         while(first!=last){
            it[i] = this->new_node(void_ptr_ptr(&it[i]), first);
            ++first;
            ++i;
         }
      }
      catch(...){
         impl_iterator e = impl.erase(it + i, it + n);
         this->align_nodes(e, get_last_align());
         throw;
      }
   }

   template <class FwdIterator>
   void insert_iter_fwd_alloc(const impl_iterator it, FwdIterator first, FwdIterator last, difference_type n, allocator_v2)
   {
      multiallocation_chain mem(node_alloc().allocate_individual(n));

      size_type i = 0;
      node_type_ptr_t p = 0;
      try{
         while(first != last){
            p = mem.front();
            mem.pop_front();
            //This can throw
            boost::container::construct_in_place(this->node_alloc(), container_detail::addressof(p->value), first);
            //This does not throw
            ::new(static_cast<node_type_base_t*>(container_detail::to_raw_pointer(p))) node_type_base_t;
            p->set_pointer(void_ptr_ptr(&it[i]));
            ++first;
            it[i] = p;
            ++i;
         }
      }
      catch(...){
         node_alloc().deallocate_one(p);
         node_alloc().deallocate_many(boost::move(mem));
         impl_iterator e = impl.erase(it+i, it+n);
         this->align_nodes(e, get_last_align());
         throw;
      }
   }

   template <class FwdIterator>
   void insert_iter_fwd(const impl_iterator it, FwdIterator first, FwdIterator last, difference_type n)
   {
      size_type i = 0;
      node_type_ptr_t p = 0;
      try{
         while(first != last){
            p = this->get_from_pool();
            if(!p){
               insert_iter_fwd_alloc(it+i, first, last, n-i, alloc_version());
               break;
            }
            //This can throw
            boost::container::construct_in_place(this->node_alloc(), container_detail::addressof(p->value), first);
            //This does not throw
            ::new(static_cast<node_type_base_t*>(container_detail::to_raw_pointer(p))) node_type_base_t;
            p->set_pointer(void_ptr_ptr(&it[i]));
            ++first;
            it[i]=p;
            ++i;
         }
      }
      catch(...){
         put_in_pool(p);
         impl_iterator e = impl.erase(it+i, it+n);
         this->align_nodes(e, get_last_align());
         throw;
      }
   }

   template <class InputIterator>
   void insert_iter(const_iterator position, InputIterator first, InputIterator last, boost::mpl::false_)
   {
      this->insert_not_iter(position, first, last);
   }

   #if defined(STABLE_VECTOR_ENABLE_INVARIANT_CHECKING)
   bool invariant()const
   {
      if(impl.empty())
         return !capacity() && !size();
      if(get_end_node() != *(impl.end() - ExtraPointers)){
         return false;
      }
      for(const_impl_iterator it = impl.begin(), it_end = get_last_align(); it != it_end; ++it){
         if(const_void_ptr(node_ptr_cast(*it)->up) !=
               const_void_ptr(const_void_ptr_ptr(&*it)))
            return false;
      }
      size_type n = capacity()-size();
      const void_ptr &pool_head = impl.back();
      size_type num_pool = 0;
      node_type_ptr_t p = node_ptr_cast(pool_head);
      while(p){
         ++num_pool;
         p = node_ptr_cast(p->up);
      }
      return n >= num_pool;
   }

   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->invariant());}
      void touch(){}
   };
   #endif

   class ebo_holder
      : public node_allocator_type
   {
      private:
      BOOST_MOVABLE_BUT_NOT_COPYABLE(ebo_holder)
      public:
/*
      explicit ebo_holder(BOOST_RV_REF(ebo_holder) x)
         : node_allocator_type(boost::move(static_cast<node_allocator_type&>(x)))
         , pool_size(0)
         , end_node()
      {}
*/
      template<class AllocatorRLValue>
      explicit ebo_holder(BOOST_FWD_REF(AllocatorRLValue) a)
         : node_allocator_type(boost::forward<AllocatorRLValue>(a))
         , pool_size(0)
         , end_node()
      {
         this->set_end_pointer_to_default_constructed();
      }

      ebo_holder()
         : node_allocator_type()
         , pool_size(0)
         , end_node()
      {
         this->set_end_pointer_to_default_constructed();
      }

      void set_end_pointer_to_default_constructed()
      {
         end_node.set_pointer(void_ptr(&end_node.up));
      }

      size_type pool_size;
      node_type_base_t end_node;
   } internal_data;

   void priv_swap_members(stable_vector &x)
   {
      container_detail::do_swap(this->internal_data.pool_size, x.internal_data.pool_size);
      this->readjust_end_node();
      x.readjust_end_node();
   }

   node_allocator_type &node_alloc()              { return internal_data;  }
   const node_allocator_type &node_alloc() const  { return internal_data;  }

   impl_type                           impl;
   /// @endcond
};

template <typename T,typename A>
bool operator==(const stable_vector<T,A>& x,const stable_vector<T,A>& y)
{
   return x.size()==y.size()&&std::equal(x.begin(),x.end(),y.begin());
}

template <typename T,typename A>
bool operator< (const stable_vector<T,A>& x,const stable_vector<T,A>& y)
{
   return std::lexicographical_compare(x.begin(),x.end(),y.begin(),y.end());
}

template <typename T,typename A>
bool operator!=(const stable_vector<T,A>& x,const stable_vector<T,A>& y)
{
   return !(x==y);
}

template <typename T,typename A>
bool operator> (const stable_vector<T,A>& x,const stable_vector<T,A>& y)
{
   return y<x;
}

template <typename T,typename A>
bool operator>=(const stable_vector<T,A>& x,const stable_vector<T,A>& y)
{
   return !(x<y);
}

template <typename T,typename A>
bool operator<=(const stable_vector<T,A>& x,const stable_vector<T,A>& y)
{
   return !(x>y);
}

// specialized algorithms:

template <typename T, typename A>
void swap(stable_vector<T,A>& x,stable_vector<T,A>& y)
{
   x.swap(y);
}

/// @cond

#undef STABLE_VECTOR_CHECK_INVARIANT

/// @endcond

}}

#include <boost/container/detail/config_end.hpp>

#endif   //BOOST_CONTAINER_STABLE_VECTOR_HPP