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