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