diff options
Diffstat (limited to 'boost/container/stable_vector.hpp')
| -rw-r--r-- | boost/container/stable_vector.hpp | 2143 |
1 files changed, 1131 insertions, 1012 deletions
diff --git a/boost/container/stable_vector.hpp b/boost/container/stable_vector.hpp index d91eccd16e..b8b415758e 100644 --- a/boost/container/stable_vector.hpp +++ b/boost/container/stable_vector.hpp @@ -1,6 +1,6 @@ ////////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2008-2012. Distributed under the Boost +// (C) Copyright Ion Gaztanaga 2008-2013. 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) // @@ -19,64 +19,51 @@ #ifndef BOOST_CONTAINER_STABLE_VECTOR_HPP #define BOOST_CONTAINER_STABLE_VECTOR_HPP -#if (defined _MSC_VER) && (_MSC_VER >= 1200) +#if defined(_MSC_VER) # 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/assert.hpp> +#include <boost/container/throw_exception.hpp> +#include <boost/container/detail/allocator_version_traits.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/container/throw_exception.hpp> #include <boost/intrusive/pointer_traits.hpp> - +#include <boost/core/no_exceptions_support.hpp> +#include <boost/aligned_storage.hpp> +#include <boost/move/utility_core.hpp> +#include <boost/move/iterator.hpp> +#include <boost/move/detail/move_helpers.hpp> +#include <boost/container/detail/placement_new.hpp> #include <algorithm> -#include <stdexcept> + + #include <memory> -///@cond +#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED #include <boost/container/vector.hpp> //#define STABLE_VECTOR_ENABLE_INVARIANT_CHECKING -#if defined(STABLE_VECTOR_ENABLE_INVARIANT_CHECKING) -#include <boost/assert.hpp> -#endif - -///@endcond +#endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED namespace boost { namespace container { -///@cond - -namespace stable_vector_detail{ +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) +#include <initializer_list> +#endif -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();} -}; +#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED -template<class T> -struct smart_ptr_type<T*> -{ - typedef T value_type; - typedef value_type *pointer; - static pointer get (pointer ptr) - { return ptr;} -}; +namespace stable_vector_detail{ template <class C> class clear_on_destroy @@ -93,7 +80,7 @@ class clear_on_destroy { if(do_clear_){ c_.clear(); - c_.clear_pool(); + c_.priv_clear_pool(); } } @@ -104,239 +91,304 @@ class clear_on_destroy bool do_clear_; }; +template<typename Pointer> +struct node; + template<class VoidPtr> -struct node_type_base +struct node_base { - node_type_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; + typedef typename void_ptr_traits:: + template rebind_pointer + <node_base_ptr>::type node_base_ptr_ptr; + + public: + node_base(const node_base_ptr_ptr &n) + : up(n) {} - void set_pointer(const VoidPtr &p) - { up = p; } - VoidPtr up; + node_base() + : up() + {} + + node_base_ptr_ptr up; }; -template<typename VoidPointer, typename T> -struct node_type - : public node_type_base<VoidPointer> +template<typename Pointer> +struct node + : public node_base + <typename ::boost::intrusive::pointer_traits<Pointer>::template + rebind_pointer<void>::type + > { private: - node_type(); + node(); public: - T value; + typename ::boost::intrusive::pointer_traits<Pointer>::element_type 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> +template<class VoidPtr, class VoidAllocator> +struct index_traits { - 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; + 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; - friend class iterator<T, const T, typename boost::intrusive::pointer_traits<Pointer>::template rebind_pointer<T>::type>; + static const 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(); - 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; + static node_base_ptr_ptr ptr_to_node_base_ptr(node_base_ptr &n) + { return node_base_ptr_ptr_traits::pointer_to(n); } - iterator() - {} + 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; + } + } - explicit iterator(node_type_ptr_t pn) - : pn(pn) - {} + static index_iterator get_fix_up_end(index_type &index) + { return index.end() - (ExtraPointers - 1); } - 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) + 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) { - return node_type_ptr_t(static_cast<node_type_t*>(container_detail::to_raw_pointer(p))); + 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 const_node_type_ptr_t node_ptr_cast(const const_void_ptr &p) + static void initialize_end_node(index_type &index, node_base_type &end_node, const size_type index_capacity_if_empty) { - return const_node_type_ptr_t(static_cast<const node_type_t*>(container_detail::to_raw_pointer(p))); + 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); + } } - static void_ptr_ptr void_ptr_ptr_cast(const void_ptr &p) + #ifdef STABLE_VECTOR_ENABLE_INVARIANT_CHECKING + static bool invariants(index_type &index) { - return void_ptr_ptr(static_cast<void_ptr*>(container_detail::to_raw_pointer(p))); + 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 - 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); } +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 ::boost::container::container_detail::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; + + private: + 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; + + node_base_ptr m_pn; 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; } + explicit stable_vector_iterator(node_base_ptr p) BOOST_CONTAINER_NOEXCEPT + : m_pn(p) + {} - iterator operator++(int) - { iterator tmp(*this); ++*this; return iterator(tmp); } + stable_vector_iterator() BOOST_CONTAINER_NOEXCEPT + : m_pn() //Value initialization to achieve "null iterators" (N3644) + {} - iterator& operator--() - { this->decrement(); return *this; } + stable_vector_iterator(stable_vector_iterator<Pointer, false> const& other) BOOST_CONTAINER_NOEXCEPT + : m_pn(other.node_pointer()) + {} - iterator operator--(int) - { iterator tmp(*this); --*this; return iterator(tmp); } + node_ptr node_pointer() const BOOST_CONTAINER_NOEXCEPT + { return node_ptr_traits::static_cast_from(m_pn); } - reference operator[](difference_type off) const + public: + //Pointer like operators + reference operator*() const BOOST_CONTAINER_NOEXCEPT + { return node_pointer()->value; } + + pointer operator->() const BOOST_CONTAINER_NOEXCEPT + { return ptr_traits::pointer_to(this->operator*()); } + + //Increment / Decrement + stable_vector_iterator& operator++() BOOST_CONTAINER_NOEXCEPT { - iterator tmp(*this); - tmp += off; - return *tmp; + node_base_ptr_ptr p(this->m_pn->up); + this->m_pn = *(++p); + return *this; } - iterator& operator+=(difference_type off) + stable_vector_iterator operator++(int) BOOST_CONTAINER_NOEXCEPT + { stable_vector_iterator tmp(*this); ++*this; return stable_vector_iterator(tmp); } + + stable_vector_iterator& operator--() BOOST_CONTAINER_NOEXCEPT { - pn = node_ptr_cast(*(void_ptr_ptr_cast(pn->up)+off)); + node_base_ptr_ptr p(this->m_pn->up); + this->m_pn = *(--p); return *this; } - friend iterator operator+(const iterator &left, difference_type off) + stable_vector_iterator operator--(int) BOOST_CONTAINER_NOEXCEPT + { stable_vector_iterator tmp(*this); --*this; return stable_vector_iterator(tmp); } + + reference operator[](difference_type off) const BOOST_CONTAINER_NOEXCEPT + { return node_ptr_traits::static_cast_from(this->m_pn->up[off])->value; } + + stable_vector_iterator& operator+=(difference_type off) BOOST_CONTAINER_NOEXCEPT { - iterator tmp(left); + if(off) this->m_pn = this->m_pn->up[off]; + return *this; + } + + friend stable_vector_iterator operator+(const stable_vector_iterator &left, difference_type off) BOOST_CONTAINER_NOEXCEPT + { + stable_vector_iterator tmp(left); tmp += off; return tmp; } - friend iterator operator+(difference_type off, const iterator& right) + friend stable_vector_iterator operator+(difference_type off, const stable_vector_iterator& right) BOOST_CONTAINER_NOEXCEPT { - iterator tmp(right); + stable_vector_iterator tmp(right); tmp += off; return tmp; } - iterator& operator-=(difference_type off) + stable_vector_iterator& operator-=(difference_type off) BOOST_CONTAINER_NOEXCEPT { *this += -off; return *this; } - friend iterator operator-(const iterator &left, difference_type off) + friend stable_vector_iterator operator-(const stable_vector_iterator &left, difference_type off) BOOST_CONTAINER_NOEXCEPT { - iterator tmp(left); + stable_vector_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); - } + friend difference_type operator-(const stable_vector_iterator& left, const stable_vector_iterator& right) BOOST_CONTAINER_NOEXCEPT + { return left.m_pn->up - right.m_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 stable_vector_iterator& l, const stable_vector_iterator& r) BOOST_CONTAINER_NOEXCEPT + { return l.m_pn == r.m_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 stable_vector_iterator& l, const stable_vector_iterator& r) BOOST_CONTAINER_NOEXCEPT + { return l.m_pn != r.m_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 stable_vector_iterator& l, const stable_vector_iterator& r) BOOST_CONTAINER_NOEXCEPT + { return l.m_pn->up < r.m_pn->up; } - node_type_ptr_t pn; -}; + friend bool operator<= (const stable_vector_iterator& l, const stable_vector_iterator& r) BOOST_CONTAINER_NOEXCEPT + { return l.m_pn->up <= r.m_pn->up; } -template<class A, unsigned int Version> -struct select_multiallocation_chain -{ - typedef typename A::multiallocation_chain type; -}; + friend bool operator> (const stable_vector_iterator& l, const stable_vector_iterator& r) BOOST_CONTAINER_NOEXCEPT + { return l.m_pn->up > r.m_pn->up; } -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; + friend bool operator>= (const stable_vector_iterator& l, const stable_vector_iterator& r) BOOST_CONTAINER_NOEXCEPT + { return l.m_pn->up >= r.m_pn->up; } }; -} //namespace stable_vector_detail - -#if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) + #if defined(STABLE_VECTOR_ENABLE_INVARIANT_CHECKING) -#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(); -#define STABLE_VECTOR_CHECK_INVARIANT \ -invariant_checker BOOST_JOIN(check_invariant_,__LINE__)(*this); \ -BOOST_JOIN(check_invariant_,__LINE__).touch(); -#else + #else //STABLE_VECTOR_ENABLE_INVARIANT_CHECKING -#define STABLE_VECTOR_CHECK_INVARIANT + #define STABLE_VECTOR_CHECK_INVARIANT -#endif //#if defined(STABLE_VECTOR_ENABLE_INVARIANT_CHECKING) + #endif //#if defined(STABLE_VECTOR_ENABLE_INVARIANT_CHECKING) -#endif //#if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) +#endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED -/// @endcond - -//! Originally developed by Joaquin M. Lopez Munoz, stable_vector is std::vector +//! 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. //! -//! More details taken the author's blog: +//! 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>) +//! 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. +//! 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 @@ -353,46 +405,53 @@ BOOST_JOIN(check_invariant_,__LINE__).touch(); //! 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: +//! 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 A = std::allocator<T> > +template <class T, class Allocator = std::allocator<T> > #else -template <class T, class A> +template <class T, class Allocator> #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>:: + #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED + typedef allocator_traits<Allocator> 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 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 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::container_detail:: integral_constant<unsigned, 1> allocator_v1; @@ -400,85 +459,74 @@ class stable_vector integral_constant<unsigned, 2> allocator_v2; typedef ::boost::container::container_detail::integral_constant <unsigned, boost::container::container_detail:: - version<A>::value> alloc_version; + version<Allocator>::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); } + <node_type>::type node_allocator_type; + + typedef ::boost::container::container_detail:: + allocator_version_traits<node_allocator_type> allocator_version_traits_t; + typedef typename allocator_version_traits_t::multiallocation_chain multiallocation_chain; + + node_ptr allocate_one() + { return allocator_version_traits_t::allocate_one(this->priv_node_alloc()); } + + void deallocate_one(const node_ptr &p) + { allocator_version_traits_t::deallocate_one(this->priv_node_alloc(), p); } + + 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); } + + 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>; - ///@endcond + typedef stable_vector_iterator + < typename allocator_traits<Allocator>::pointer + , false> iterator_impl; + typedef stable_vector_iterator + < typename allocator_traits<Allocator>::pointer + , false> const_iterator_impl; + #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 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 + ////////////////////////////////////////////// + // + // types + // + ////////////////////////////////////////////// + typedef T value_type; + typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer; + typedef typename ::boost::container::allocator_traits<Allocator>::const_pointer const_pointer; + typedef typename ::boost::container::allocator_traits<Allocator>::reference reference; + typedef typename ::boost::container::allocator_traits<Allocator>::const_reference const_reference; + typedef typename ::boost::container::allocator_traits<Allocator>::size_type size_type; + typedef typename ::boost::container::allocator_traits<Allocator>::difference_type difference_type; + typedef Allocator 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(container_detail::reverse_iterator<iterator>) reverse_iterator; + typedef BOOST_CONTAINER_IMPDEF(container_detail::reverse_iterator<const_iterator>) const_reverse_iterator; + + #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 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 + static const 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. //! @@ -486,31 +534,31 @@ class stable_vector //! //! <b>Complexity</b>: Constant. stable_vector() - : internal_data(), impl() + : internal_data(), index() { 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>Throws</b>: Nothing //! //! <b>Complexity</b>: Constant. - explicit stable_vector(const allocator_type& al) - : internal_data(al),impl(al) + explicit stable_vector(const allocator_type& al) BOOST_CONTAINER_NOEXCEPT + : internal_data(al), index(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. + //! and inserts n value initialized values. //! - //! <b>Throws</b>: If allocator_type's default constructor or copy constructor + //! <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(),impl() + : internal_data(), index() { stable_vector_detail::clear_on_destroy<stable_vector> cod(*this); this->resize(n); @@ -519,17 +567,35 @@ class stable_vector } //! <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) + : internal_data(), index() + { + stable_vector_detail::clear_on_destroy<stable_vector> cod(*this); + this->resize(n, default_init); + 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 + //! <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),impl(al) + : internal_data(al), index(al) { stable_vector_detail::clear_on_destroy<stable_vector> cod(*this); - this->insert(this->cbegin(), n, t); + this->insert(this->cend(), n, t); STABLE_VECTOR_CHECK_INVARIANT; cod.release(); } @@ -537,16 +603,16 @@ class stable_vector //! <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>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),impl(al) + : internal_data(al), index(al) { stable_vector_detail::clear_on_destroy<stable_vector> cod(*this); - this->insert(this->cbegin(), first, last); + this->insert(this->cend(), first, last); STABLE_VECTOR_CHECK_INVARIANT; cod.release(); } @@ -558,15 +624,33 @@ class stable_vector //! <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())) + 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()); + 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); - this->insert(this->cbegin(), x.begin(), x.end()); + insert(cend(), il.begin(), il.end()) STABLE_VECTOR_CHECK_INVARIANT; cod.release(); } +#endif //! <b>Effects</b>: Move constructor. Moves mx's resources to *this. //! @@ -574,7 +658,7 @@ class stable_vector //! //! <b>Complexity</b>: Constant. stable_vector(BOOST_RV_REF(stable_vector) x) - : internal_data(boost::move(x.node_alloc())), impl(boost::move(x.impl)) + : internal_data(boost::move(x.priv_node_alloc())), index(boost::move(x.index)) { this->priv_swap_members(x); } @@ -585,10 +669,10 @@ class stable_vector //! //! <b>Complexity</b>: Linear to the elements x contains. stable_vector(const stable_vector& x, const allocator_type &a) - : internal_data(a), impl(a) + : internal_data(a), index(a) { stable_vector_detail::clear_on_destroy<stable_vector> cod(*this); - this->insert(this->cbegin(), x.begin(), x.end()); + this->insert(this->cend(), x.begin(), x.end()); STABLE_VECTOR_CHECK_INVARIANT; cod.release(); } @@ -600,14 +684,14 @@ class stable_vector //! //! <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) + : internal_data(a), index(a) { - if(this->node_alloc() == x.node_alloc()){ + if(this->priv_node_alloc() == x.priv_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()); + this->insert(this->cend(), x.begin(), x.end()); STABLE_VECTOR_CHECK_INVARIANT; cod.release(); } @@ -622,7 +706,7 @@ class stable_vector ~stable_vector() { this->clear(); - clear_pool(); + this->priv_clear_pool(); } //! <b>Effects</b>: Makes *this contain the same elements as x. @@ -637,16 +721,16 @@ class stable_vector { STABLE_VECTOR_CHECK_INVARIANT; if (&x != this){ - node_allocator_type &this_alloc = this->node_alloc(); - const node_allocator_type &x_alloc = x.node_alloc(); + node_allocator_type &this_alloc = this->priv_node_alloc(); + const node_allocator_type &x_alloc = x.priv_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); + container_detail::assign_alloc(this->priv_node_alloc(), x.priv_node_alloc(), flag); + container_detail::assign_alloc(this->index.get_stored_allocator(), x.index.get_stored_allocator(), flag); this->assign(x.begin(), x.end()); } return *this; @@ -657,35 +741,65 @@ class stable_vector //! <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>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>: Linear. + //! <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) - { - 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())); - } + BOOST_CONTAINER_NOEXCEPT_IF(allocator_traits_type::propagate_on_container_move_assignment::value) + { + //for move constructor, no aliasing (&x != this) is assummed. + BOOST_ASSERT(this != &x); + node_allocator_type &this_alloc = this->priv_node_alloc(); + node_allocator_type &x_alloc = x.priv_node_alloc(); + const bool propagate_alloc = allocator_traits_type:: + propagate_on_container_move_assignment::value; + container_detail::bool_<propagate_alloc> flag; + const bool allocators_equal = this_alloc == x_alloc; (void)allocators_equal; + //Resources can be transferred if both allocators are + //going to be equal after this function (either propagated or already equal) + if(propagate_alloc || allocators_equal){ + //Destroy objects but retain memory in case x reuses it in the future + this->clear(); + //Move allocator if needed + container_detail::move_alloc(this_alloc, x_alloc, flag); + //Take resources + this->index = boost::move(x.index); + this->priv_swap_members(x); + } + //Else do a one by one move + else{ + this->assign( boost::make_move_iterator(x.begin()) + , boost::make_move_iterator(x.end())); } 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) + { + 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. + void assign(size_type n, const T& t) + { + typedef constant_iterator<value_type, difference_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 @@ -693,29 +807,47 @@ class stable_vector //! //! <b>Complexity</b>: Linear to n. template<typename InputIterator> - void assign(InputIterator first,InputIterator last) + void assign(InputIterator first,InputIterator last + #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) + , typename container_detail::enable_if_c + < !container_detail::is_convertible<InputIterator, size_type>::value + >::type * = 0 + #endif + ) { - assign_dispatch(first, last, boost::is_integral<InputIterator>()); + 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); + } } - - //! <b>Effects</b>: Assigns the n copies of val to *this. +#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 copy constructor throws. + //! <b>Throws</b>: If memory allocation throws or + //! T's constructor from dereferencing initializer_list iterator throws. //! - //! <b>Complexity</b>: Linear to n. - void assign(size_type n,const T& t) + void assign(std::initializer_list<value_type> il) { - typedef constant_iterator<value_type, difference_type> cvalue_iterator; - return assign_dispatch(cvalue_iterator(t, n), cvalue_iterator(), boost::mpl::false_()); + 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. - allocator_type get_allocator()const {return this->node_alloc();} + allocator_type get_allocator() const + { return this->priv_node_alloc(); } //! <b>Effects</b>: Returns a reference to the internal allocator. //! @@ -725,7 +857,7 @@ class stable_vector //! //! <b>Note</b>: Non-standard extension. const stored_allocator_type &get_stored_allocator() const BOOST_CONTAINER_NOEXCEPT - { return node_alloc(); } + { return this->priv_node_alloc(); } //! <b>Effects</b>: Returns a reference to the internal allocator. //! @@ -735,38 +867,45 @@ class stable_vector //! //! <b>Note</b>: Non-standard extension. stored_allocator_type &get_stored_allocator() BOOST_CONTAINER_NOEXCEPT - { return node_alloc(); } + { 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. - iterator begin() - { return (impl.empty()) ? end(): iterator(node_ptr_cast(impl.front())) ; } + iterator begin() BOOST_CONTAINER_NOEXCEPT + { 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. - const_iterator begin()const - { return (impl.empty()) ? cend() : const_iterator(node_ptr_cast(impl.front())) ; } + const_iterator begin() const BOOST_CONTAINER_NOEXCEPT + { 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. - iterator end() {return iterator(get_end_node());} + iterator end() BOOST_CONTAINER_NOEXCEPT + { 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. - const_iterator end()const {return const_iterator(get_end_node());} + const_iterator end() const BOOST_CONTAINER_NOEXCEPT + { return const_iterator(this->priv_get_end_node()); } //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning //! of the reversed stable_vector. @@ -774,7 +913,8 @@ class stable_vector //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Constant. - reverse_iterator rbegin() {return reverse_iterator(this->end());} + reverse_iterator rbegin() BOOST_CONTAINER_NOEXCEPT + { return reverse_iterator(this->end()); } //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning //! of the reversed stable_vector. @@ -782,7 +922,8 @@ class stable_vector //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Constant. - const_reverse_iterator rbegin()const {return const_reverse_iterator(this->end());} + const_reverse_iterator rbegin() const BOOST_CONTAINER_NOEXCEPT + { return const_reverse_iterator(this->end()); } //! <b>Effects</b>: Returns a reverse_iterator pointing to the end //! of the reversed stable_vector. @@ -790,7 +931,8 @@ class stable_vector //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Constant. - reverse_iterator rend() {return reverse_iterator(this->begin());} + reverse_iterator rend() BOOST_CONTAINER_NOEXCEPT + { return reverse_iterator(this->begin()); } //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end //! of the reversed stable_vector. @@ -798,21 +940,24 @@ class stable_vector //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Constant. - const_reverse_iterator rend()const {return const_reverse_iterator(this->begin());} + const_reverse_iterator rend() const BOOST_CONTAINER_NOEXCEPT + { 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();} + const_iterator cbegin() const BOOST_CONTAINER_NOEXCEPT + { 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();} + const_iterator cend() const BOOST_CONTAINER_NOEXCEPT + { return this->end(); } //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning //! of the reversed stable_vector. @@ -820,7 +965,8 @@ class stable_vector //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Constant. - const_reverse_iterator crbegin()const{return this->rbegin();} + const_reverse_iterator crbegin() const BOOST_CONTAINER_NOEXCEPT + { return this->rbegin(); } //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end //! of the reversed stable_vector. @@ -828,81 +974,110 @@ class stable_vector //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Constant. - const_reverse_iterator crend()const {return this->rend();} + const_reverse_iterator crend()const BOOST_CONTAINER_NOEXCEPT + { 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); } + ////////////////////////////////////////////// + // + // capacity + // + ////////////////////////////////////////////// - //! <b>Effects</b>: Returns the largest possible size of the stable_vector. + //! <b>Effects</b>: Returns true if the stable_vector contains no elements. //! //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Constant. - size_type max_size() const - { return impl.max_size() - ExtraPointers; } + bool empty() const BOOST_CONTAINER_NOEXCEPT + { return this->index.size() <= ExtraPointers; } - //! <b>Effects</b>: Number of elements for which memory has been allocated. - //! capacity() is always greater than or equal to size(). + //! <b>Effects</b>: Returns the number of the elements contained in the stable_vector. //! //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Constant. - size_type capacity() const + size_type size() const BOOST_CONTAINER_NOEXCEPT { - 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; - } + const size_type index_size = this->index.size(); + return (index_size - ExtraPointers) & (std::size_t(0u) -std::size_t(index_size != 0)); } - //! <b>Effects</b>: Returns true if the stable_vector contains no elements. + //! <b>Effects</b>: Returns the largest possible size of the stable_vector. //! //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Constant. - bool empty() const - { return impl.empty() || impl.size() == ExtraPointers; } + size_type max_size() const BOOST_CONTAINER_NOEXCEPT + { 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 copy constructed from x. + //! the size becomes n. New elements are value initialized. //! - //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws. + //! <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, const T& t) + void resize(size_type n) { + typedef value_init_construct_iterator<value_type, difference_type> value_init_iterator; STABLE_VECTOR_CHECK_INVARIANT; - if(n > size()) - this->insert(this->cend(), n - this->size(), t); + 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() + 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, difference_type> default_init_iterator; + 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() + n, this->cend()); } //! <b>Effects</b>: Inserts or erases elements at the end such that - //! the size becomes n. New elements are default constructed. + //! 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) + void resize(size_type n, const T& t) { - 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()); + if(n > this->size()) + this->insert(this->cend(), n - this->size(), t); else if(n < this->size()) this->erase(this->cbegin() + 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. + size_type capacity() const BOOST_CONTAINER_NOEXCEPT + { + const size_type index_size = this->index.size(); + BOOST_ASSERT(!index_size || index_size >= ExtraPointers); + const size_type bucket_extra_capacity = this->index.capacity()- index_size; + const size_type node_extra_capacity = this->internal_data.pool_size; + const size_type extra_capacity = (bucket_extra_capacity < node_extra_capacity) + ? bucket_extra_capacity : node_extra_capacity; + const size_type index_offset = + (ExtraPointers + extra_capacity) & (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 @@ -912,76 +1087,63 @@ class stable_vector void reserve(size_type n) { STABLE_VECTOR_CHECK_INVARIANT; - if(n > this->max_size()) - throw std::bad_alloc(); + if(n > this->max_size()){ + throw_length_error("stable_vector::reserve max_size() exceeded"); + } - size_type size = this->size(); + size_type sz = 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; + 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){ - this->align_nodes(impl.begin(), impl.begin()+size+1); + index_traits_type::fix_up_pointers_from(this->index, this->index.begin()); } //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); + if((n - sz) > this->internal_data.pool_size){ + this->priv_increase_pool((n - sz) - 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>Effects</b>: Tries to deallocate the excess of memory created + //! with previous allocations. The size of the stable_vector is unchanged //! - //! <b>Throws</b>: std::range_error if n >= size() + //! <b>Throws</b>: If memory allocation throws. //! - //! <b>Complexity</b>: Constant. - reference at(size_type n) + //! <b>Complexity</b>: Linear to size(). + void shrink_to_fit() { - if(n>=size()) - throw std::out_of_range("invalid subscript at stable_vector::at"); - return operator[](n); + 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()); + } + } + } } - //! <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); - } + ////////////////////////////////////////////// + // + // element access + // + ////////////////////////////////////////////// //! <b>Requires</b>: !empty() //! @@ -991,8 +1153,8 @@ class stable_vector //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Constant. - reference front() - { return value(impl.front()); } + reference front() BOOST_CONTAINER_NOEXCEPT + { return static_cast<node_reference>(*this->index.front()).value; } //! <b>Requires</b>: !empty() //! @@ -1002,8 +1164,8 @@ class stable_vector //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Constant. - const_reference front()const - { return value(impl.front()); } + const_reference front() const BOOST_CONTAINER_NOEXCEPT + { return static_cast<const_node_reference>(*this->index.front()).value; } //! <b>Requires</b>: !empty() //! @@ -1013,8 +1175,8 @@ class stable_vector //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Constant. - reference back() - { return value(*(&impl.back() - ExtraPointers)); } + reference back() BOOST_CONTAINER_NOEXCEPT + { return static_cast<node_reference>(*this->index[this->size()-1u]).value; } //! <b>Requires</b>: !empty() //! @@ -1024,113 +1186,75 @@ class stable_vector //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Constant. - const_reference back()const - { return value(*(&impl.back() - ExtraPointers)); } + const_reference back() const BOOST_CONTAINER_NOEXCEPT + { return static_cast<const_node_reference>(*this->index[this->size()-1u]).value; } - //! <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>Requires</b>: size() > n. //! - //! <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>Effects</b>: Returns a reference to the nth element + //! from the beginning of the container. //! //! <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>Complexity</b>: Constant. + reference operator[](size_type n) BOOST_CONTAINER_NOEXCEPT + { + BOOST_ASSERT(n < this->size()); + return static_cast<node_reference>(*this->index[n]).value; + } - //! <b>Requires</b>: position must be a valid iterator of *this. + //! <b>Requires</b>: size() > n. //! - //! <b>Effects</b>: Insert a new element before position with mx's resources. + //! <b>Effects</b>: Returns a const reference to the nth element + //! from the beginning of the container. //! - //! <b>Throws</b>: If memory allocation throws. + //! <b>Throws</b>: Nothing. //! - //! <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>Complexity</b>: Constant. + const_reference operator[](size_type n) const BOOST_CONTAINER_NOEXCEPT + { + BOOST_ASSERT(n < this->size()); + return static_cast<const_node_reference>(*this->index[n]).value; } - //! <b>Requires</b>: pos must be a valid iterator of *this. + //! <b>Requires</b>: size() > n. //! - //! <b>Effects</b>: Insert n copies of x before pos. + //! <b>Effects</b>: Returns a reference to the nth element + //! from the beginning of the container. //! - //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws. + //! <b>Throws</b>: std::range_error if n >= size() //! - //! <b>Complexity</b>: Linear to n. - void insert(const_iterator position, size_type n, const T& t) + //! <b>Complexity</b>: Constant. + reference at(size_type n) { - STABLE_VECTOR_CHECK_INVARIANT; - this->insert_not_iter(position, n, t); + if(n >= this->size()){ + throw_out_of_range("vector::at invalid subscript"); + } + return operator[](n); } - //! <b>Requires</b>: pos must be a valid iterator of *this. + //! <b>Requires</b>: size() > n. //! - //! <b>Effects</b>: Insert a copy of the [first, last) range before pos. + //! <b>Effects</b>: Returns a const reference to the nth element + //! from the beginning of the container. //! - //! <b>Throws</b>: If memory allocation throws, T's constructor from a - //! dereferenced InpIt throws or T's copy constructor throws. + //! <b>Throws</b>: std::range_error if n >= size() //! - //! <b>Complexity</b>: Linear to std::distance [first, last). - template <class InputIterator> - void insert(const_iterator position,InputIterator first, InputIterator last) + //! <b>Complexity</b>: Constant. + const_reference at(size_type n)const { - STABLE_VECTOR_CHECK_INVARIANT; - this->insert_iter(position,first,last, - boost::mpl::not_<boost::is_integral<InputIterator> >()); + if(n >= this->size()){ + throw_out_of_range("vector::at invalid subscript"); + } + return operator[](n); } + ////////////////////////////////////////////// + // + // modifiers + // + ////////////////////////////////////////////// + #if defined(BOOST_CONTAINER_PERFECT_FORWARDING) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) //! <b>Effects</b>: Inserts an object of type T constructed with @@ -1148,24 +1272,23 @@ class stable_vector this->insert(this->cend(), EmplaceIterator(ef), EmplaceIterator()); } - //! <b>Requires</b>: position must be a valid iterator of *this. + //! <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 position + //! std::forward<Args>(args)... before p //! //! <b>Throws</b>: If memory allocation throws or the in-place constructor throws. //! - //! <b>Complexity</b>: If position is end(), amortized constant time + //! <b>Complexity</b>: If p is end(), amortized constant time //! Linear time otherwise. template<class ...Args> - iterator emplace(const_iterator position, Args && ...args) + iterator emplace(const_iterator p, Args && ...args) { - //Just call more general insert(pos, size, value) and return iterator - size_type pos_n = position - cbegin(); + size_type pos_n = p - 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()); + this->insert(p, EmplaceIterator(ef), EmplaceIterator()); return iterator(this->begin() + pos_n); } @@ -1186,7 +1309,7 @@ class stable_vector } \ \ BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \ - iterator emplace(const_iterator pos \ + iterator emplace(const_iterator p \ BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \ { \ typedef BOOST_PP_CAT(BOOST_PP_CAT(emplace_functor, n), arg) \ @@ -1196,8 +1319,8 @@ class stable_vector 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()); \ + size_type pos_n = p - this->cbegin(); \ + this->insert(p, EmplaceIterator(ef), EmplaceIterator()); \ return iterator(this->begin() + pos_n); \ } \ //! @@ -1206,21 +1329,178 @@ class stable_vector #endif //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING - //! <b>Effects</b>: Erases the element at position pos. + #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 mx 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 mx'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) + { + STABLE_VECTOR_CHECK_INVARIANT; + typedef constant_iterator<value_type, difference_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 std::distance [il.begin(), il.end()). + iterator insert(const_iterator p, std::initializer_list<value_type> il) + { + 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 std::distance [first, last). + template <class InputIterator> + iterator insert(const_iterator p, InputIterator first, InputIterator last + #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) + , typename container_detail::enable_if_c + < !container_detail::is_convertible<InputIterator, size_type>::value + && container_detail::is_input_iterator<InputIterator>::value + >::type * = 0 + #endif + ) + { + STABLE_VECTOR_CHECK_INVARIANT; + const size_type pos_n = p - this->cbegin(); + for(; first != last; ++first){ + this->emplace(p, *first); + } + return this->begin() + pos_n; + } + + #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) + template <class FwdIt> + iterator insert(const_iterator p, FwdIt first, FwdIt last + , typename container_detail::enable_if_c + < !container_detail::is_convertible<FwdIt, size_type>::value + && !container_detail::is_input_iterator<FwdIt>::value + >::type * = 0 + ) + { + const size_type num_new = static_cast<size_type>(std::distance(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 + num_new); + { + //Prepare rollback + insert_rollback rollback(*this, it_past_newly_constructed, it_past_new); + while(first != last){ + const node_ptr p = this->priv_get_from_pool(); + BOOST_ASSERT(!!p); + //Put it in the index so rollback can return it in pool if construct_in_place throws + *it_past_newly_constructed = p; + //Constructs and fixes up pointers This can throw + this->priv_build_node_from_it(p, 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() + idx; + } + #endif + + //! <b>Effects</b>: Removes the last element from the stable_vector. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Constant time. + void pop_back() BOOST_CONTAINER_NOEXCEPT + { this->erase(--this->cend()); } + + //! <b>Effects</b>: Erases the element at p. //! //! <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) + //! <b>Complexity</b>: Linear to the elements between p and the + //! last element. Constant if p is the last element. + iterator erase(const_iterator p) BOOST_CONTAINER_NOEXCEPT { 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; + const size_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). @@ -1228,9 +1508,32 @@ class stable_vector //! <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()); } + //! plus linear to the elements between p and the last element. + iterator erase(const_iterator first, const_iterator last) BOOST_CONTAINER_NOEXCEPT + { + 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() + d1); + const index_iterator it2(it1 + d_dif); + index_iterator it(it1); + while(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. //! @@ -1241,9 +1544,9 @@ class stable_vector { 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); + container_detail::swap_alloc(this->priv_node_alloc(), x.priv_node_alloc(), flag); //vector's allocator is swapped here - this->impl.swap(x.impl); + this->index.swap(x.index); this->priv_swap_members(x); } @@ -1252,459 +1555,330 @@ class stable_vector //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Linear to the number of elements in the stable_vector. - void clear() + void clear() BOOST_CONTAINER_NOEXCEPT { 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>Effects</b>: Returns true if x and y are equal //! - //! <b>Throws</b>: If memory allocation throws. + //! <b>Complexity</b>: Linear to the number of elements in the container. + friend bool operator==(const stable_vector& x, const stable_vector& y) + { return x.size() == y.size() && std::equal(x.begin(), x.end(), y.begin()); } + + //! <b>Effects</b>: Returns true if x and y are unequal //! - //! <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); - } - } - } - } + //! <b>Complexity</b>: Linear to the number of elements in the container. + friend bool operator!=(const stable_vector& x, const stable_vector& y) + { return !(x == y); } - /// @cond + //! <b>Effects</b>: Returns true if x is less than y + //! + //! <b>Complexity</b>: Linear to the number of elements in the container. + friend bool operator<(const stable_vector& x, const stable_vector& y) + { return std::lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); } - 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()); - } + //! <b>Effects</b>: Returns true if x is greater than y + //! + //! <b>Complexity</b>: Linear to the number of elements in the container. + friend bool operator>(const stable_vector& x, const stable_vector& y) + { return y < x; } - void priv_push_back(const value_type &t) - { this->insert(end(), t); } + //! <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. + friend bool operator<=(const stable_vector& x, const stable_vector& y) + { return !(y < x); } - 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(); + //! <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. + friend bool operator>=(const stable_vector& x, const stable_vector& y) + { return !(x < y); } - 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; - } - } + //! <b>Effects</b>: x.swap(y) + //! + //! <b>Complexity</b>: Constant. + friend void swap(stable_vector& x, stable_vector& y) + { x.swap(y); } - 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; - } - } + #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED + private: - void clear_pool() + class insert_rollback { - this->clear_pool(alloc_version()); - } + public: - void add_to_pool(size_type n) - { - this->add_to_pool(n, alloc_version()); - } + 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) + {} - 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()); + ~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); + } } - } - 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; - } + private: + stable_vector &m_sv; + index_iterator &m_it_past_constructed; + const index_iterator &m_it_past_new; + }; - void put_in_pool(node_type_ptr_t p) + class push_back_rollback { - 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; - } + public: + push_back_rollback(stable_vector &sv, const node_ptr &p) + : m_sv(sv), m_p(p) + {} - 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; + ~push_back_rollback() + { + if(m_p){ + m_sv.priv_put_in_pool(m_p); } - 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); - } - } + void release() + { m_p = node_ptr(); } - template<typename InputIterator> - void assign_dispatch(InputIterator first, InputIterator last, boost::mpl::false_) + private: + stable_vector &m_sv; + node_ptr m_p; + }; + + index_iterator priv_insert_forward_non_templated(size_type idx, size_type num_new) { - 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); + 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); } - else{ - this->insert(last1, first, last); + + //Now try to make room in the vector + const node_base_ptr_ptr old_buffer = this->index.data(); + this->index.insert(this->index.begin() + 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 + idx); } + return index_beg + idx; } - template<typename Integer> - void assign_dispatch(Integer n, Integer t, boost::mpl::true_) + bool priv_capacity_bigger_than_size() const { - typedef constant_iterator<value_type, difference_type> cvalue_iterator; - this->assign_dispatch(cvalue_iterator(t, n), cvalue_iterator(), boost::mpl::false_()); + return this->index.capacity() > this->index.size() && + this->internal_data.pool_size > 0; } - iterator priv_erase(const_iterator first, const_iterator last, allocator_v1) + template <class U> + void priv_push_back(BOOST_MOVE_CATCH_FWD(U) x) { - 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()); + if(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)); } - return iterator(this->begin() + d1); } - impl_iterator get_last_align() + iterator priv_insert(const_iterator p, const value_type &t) { - return impl.end() - (ExtraPointers - 1); + typedef constant_iterator<value_type, difference_type> cvalue_iterator; + return this->insert(p, cvalue_iterator(t, 1), cvalue_iterator()); } - const_impl_iterator get_last_align() const + iterator priv_insert(const_iterator p, BOOST_RV_REF(T) x) { - return impl.cend() - (ExtraPointers - 1); + typedef repeat_iterator<T, difference_type> 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())); } - 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) + void priv_clear_pool() { - STABLE_VECTOR_CHECK_INVARIANT; - return priv_erase(first, last, allocator_v1()); - } + 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(); - 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))); + 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; + } } - static node_type_base_ptr_t node_base_ptr_cast(const void_ptr &p) + void priv_increase_pool(size_type n) { - return node_type_base_ptr_t(static_cast<node_type_base_t*>(container_detail::to_raw_pointer(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); + 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; + std::pair<node_ptr, node_ptr> data(holder.extract_data()); + pool_first_ref = data.first; + pool_last_ref = data.second; } - static value_type& value(const void_ptr &p) + void priv_put_in_pool(const node_ptr &p) { - return node_ptr_cast(p)->value; + 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; + std::pair<node_ptr, node_ptr> ret(holder.extract_data()); + pool_first_ref = ret.first; + pool_last_ref = ret.second; } - void initialize_end_node(size_type impl_capacity = 0) + void priv_put_in_pool(multiallocation_chain &ch) { - 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]; - } + 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 std::pair<node_ptr, node_ptr> ret(ch.extract_data()); + pool_first_ref = ret.first; + pool_last_ref = ret.second; } - void readjust_end_node() + node_ptr priv_get_from_pool() { - 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; + //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{ - this->internal_data.end_node.up = void_ptr(&this->internal_data.end_node.up); + const std::pair<node_ptr, node_ptr> data(holder.extract_data()); + pool_first_ref = data.first; + pool_last_ref = data.second; } + return ret; } - 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); - } + 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)); } - template<class Iter> - void_ptr new_node(const void_ptr &up, Iter it) + void priv_destroy_node(const node_type &n) { - 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); + destroy(this->priv_node_alloc(), container_detail::addressof(n.value)); + static_cast<const node_base_type*>(&n)->~node_base_type(); } - static void align_nodes(impl_iterator first, impl_iterator last) + void priv_delete_node(const node_ptr &n) { - while(first!=last){ - node_ptr_cast(*first)->up = void_ptr(&*first); - ++first; - } + this->priv_destroy_node(*n); + this->priv_put_in_pool(n); } - void insert_not_iter(const_iterator position, size_type n, const T& t) + template<class Iterator> + void priv_build_node_from_it(const node_ptr &p, const index_iterator &up_index, const Iterator &it) { - typedef constant_iterator<value_type, difference_type> cvalue_iterator; - this->insert_iter(position, cvalue_iterator(t, n), cvalue_iterator(), std::forward_iterator_tag()); + //This can throw + boost::container::construct_in_place + ( this->priv_node_alloc() + , container_detail::addressof(p->value) + , it); + //This does not throw + ::new(static_cast<node_base_type*>(container_detail::to_raw_pointer(p)), boost_container_new_t()) + node_base_type(index_traits_type::ptr_to_node_base_ptr(*up_index)); } - template <class InputIterator> - void insert_iter(const_iterator position,InputIterator first,InputIterator last, boost::mpl::true_) + template<class ValueConvertible> + void priv_build_node_from_convertible(const node_ptr &p, BOOST_FWD_REF(ValueConvertible) value_convertible) { - typedef typename std::iterator_traits<InputIterator>::iterator_category category; - this->insert_iter(position, first, last, category()); + //This can throw + boost::container::allocator_traits<node_allocator_type>::construct + ( this->priv_node_alloc() + , container_detail::addressof(p->value) + , ::boost::forward<ValueConvertible>(value_convertible)); + //This does not throw + ::new(static_cast<node_base_type*>(container_detail::to_raw_pointer(p)), boost_container_new_t()) node_base_type; } - template <class InputIterator> - void insert_iter(const_iterator position,InputIterator first,InputIterator last,std::input_iterator_tag) + void priv_swap_members(stable_vector &x) { - 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; + boost::container::swap_dispatch(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); } - template <class FwdIterator> - void insert_iter_fwd_alloc(const impl_iterator it, FwdIterator first, FwdIterator last, difference_type n, allocator_v1) + #if defined(STABLE_VECTOR_ENABLE_INVARIANT_CHECKING) + bool priv_invariant()const { - 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; - } - } + index_type & index_ref = const_cast<index_type&>(this->index); - 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; + if(index.empty()) + return !this->capacity() && !this->size(); + if(this->priv_get_end_node() != *(index.end() - ExtraPointers)){ + return false; } - } - 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)){ + if(!index_traits_type::invariants(index_ref)){ 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 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 beg(holder.begin()), end(holder.end()); size_type num_pool = 0; - node_type_ptr_t p = node_ptr_cast(pool_head); - while(p){ + while(beg != end){ ++num_pool; - p = node_ptr_cast(p->up); + ++beg; } - return n >= num_pool; + return n >= num_pool && num_pool == internal_data.pool_size; } class invariant_checker @@ -1715,7 +1889,7 @@ class stable_vector public: invariant_checker(const stable_vector& v):p(&v){} - ~invariant_checker(){BOOST_ASSERT(p->invariant());} + ~invariant_checker(){BOOST_ASSERT(p->priv_invariant());} void touch(){} }; #endif @@ -1725,103 +1899,48 @@ class stable_vector { 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; + node_base_type 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; } + node_allocator_type &priv_node_alloc() { return internal_data; } + const node_allocator_type &priv_node_alloc() const { return internal_data; } - impl_type impl; - /// @endcond + index_type index; + #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED }; -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; -} +#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED -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); -} +#undef STABLE_VECTOR_CHECK_INVARIANT -// specialized algorithms: +#endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED -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 +//!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> > + : public has_trivial_destructor_after_move<Allocator>::value +{}; -/// @endcond +*/ }} |