boost/interprocess/containers/container/stable_vector.hpp
////////////////////////////////////////////////////////////////////////////// // // (C) Copyright Ion Gaztanaga 2008-2009. Distributed under the Boost // Software License, Version 1.0. (See accompanying file // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) // // See http://www.boost.org/libs/container for documentation. // ////////////////////////////////////////////////////////////////////////////// /* Stable vector. * * Copyright 2008 Joaquin M Lopez Munoz. * Distributed under the Boost Software License, Version 1.0. * (See accompanying file LICENSE_1_0.txt or copy at * http://www.boost.org/LICENSE_1_0.txt) */ #ifndef BOOST_CONTAINER_STABLE_VECTOR_HPP #define BOOST_CONTAINER_STABLE_VECTOR_HPP #if (defined _MSC_VER) && (_MSC_VER >= 1200) # pragma once #endif #include "detail/config_begin.hpp" #include INCLUDE_BOOST_CONTAINER_DETAIL_WORKAROUND_HPP #include INCLUDE_BOOST_CONTAINER_CONTAINER_FWD_HPP #include <boost/mpl/bool.hpp> #include <boost/mpl/not.hpp> #include <boost/noncopyable.hpp> #include <boost/type_traits/is_integral.hpp> #include INCLUDE_BOOST_CONTAINER_DETAIL_VERSION_TYPE_HPP #include INCLUDE_BOOST_CONTAINER_DETAIL_MULTIALLOCATION_CHAIN_HPP #include INCLUDE_BOOST_CONTAINER_DETAIL_UTILITIES_HPP #include INCLUDE_BOOST_CONTAINER_DETAIL_ITERATORS_HPP #include INCLUDE_BOOST_CONTAINER_DETAIL_ALGORITHMS_HPP #include <boost/pointer_to_other.hpp> #include <boost/get_pointer.hpp> #include <algorithm> #include <stdexcept> #include <memory> ///@cond #define STABLE_VECTOR_USE_CONTAINERS_VECTOR #if defined (STABLE_VECTOR_USE_CONTAINERS_VECTOR) #include INCLUDE_BOOST_CONTAINER_VECTOR_HPP #else #include <vector> #endif //STABLE_VECTOR_USE_CONTAINERS_VECTOR //#define STABLE_VECTOR_ENABLE_INVARIANT_CHECKING #if defined(STABLE_VECTOR_ENABLE_INVARIANT_CHECKING) #include <boost/assert.hpp> #endif ///@endcond namespace boost { namespace container { ///@cond namespace stable_vector_detail{ template<class SmartPtr> struct smart_ptr_type { typedef typename SmartPtr::value_type value_type; typedef value_type *pointer; static pointer get (const SmartPtr &smartptr) { return smartptr.get();} }; template<class T> struct smart_ptr_type<T*> { typedef T value_type; typedef value_type *pointer; static pointer get (pointer ptr) { return ptr;} }; template<class Ptr> inline typename smart_ptr_type<Ptr>::pointer get_pointer(const Ptr &ptr) { return smart_ptr_type<Ptr>::get(ptr); } template <class C> class clear_on_destroy { public: clear_on_destroy(C &c) : c_(c), do_clear_(true) {} void release() { do_clear_ = false; } ~clear_on_destroy() { if(do_clear_){ c_.clear(); c_.clear_pool(); } } private: clear_on_destroy(const clear_on_destroy &); clear_on_destroy &operator=(const clear_on_destroy &); C &c_; bool do_clear_; }; template<class VoidPtr> struct node_type_base {/* node_type_base(VoidPtr p) : up(p) {}*/ node_type_base() {} void set_pointer(VoidPtr p) { up = p; } VoidPtr up; }; template<typename VoidPointer, typename T> struct node_type : public node_type_base<VoidPointer> { #if defined(BOOST_CONTAINERS_PERFECT_FORWARDING) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) node_type() : value() {} template<class ...Args> node_type(Args &&...args) : value(BOOST_CONTAINER_MOVE_NAMESPACE::forward<Args>(args)...) {} #else //BOOST_CONTAINERS_PERFECT_FORWARDING node_type() : value() {} #define BOOST_PP_LOCAL_MACRO(n) \ template<BOOST_PP_ENUM_PARAMS(n, class P)> \ node_type(BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_LIST, _)) \ : value(BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_FORWARD, _)) \ {} \ //! #define BOOST_PP_LOCAL_LIMITS (1, BOOST_CONTAINERS_MAX_CONSTRUCTOR_PARAMETERS) #include BOOST_PP_LOCAL_ITERATE() #endif//BOOST_CONTAINERS_PERFECT_FORWARDING void set_pointer(VoidPointer p) { node_type_base<VoidPointer>::set_pointer(p); } T value; }; template<typename T, typename Reference, typename Pointer> class iterator : public std::iterator< std::random_access_iterator_tag , typename std::iterator_traits<Pointer>::value_type , typename std::iterator_traits<Pointer>::difference_type , Pointer , Reference> { typedef typename boost::pointer_to_other <Pointer, void>::type void_ptr; typedef node_type<void_ptr, T> node_type_t; typedef typename boost::pointer_to_other <void_ptr, node_type_t>::type node_type_ptr_t; typedef typename boost::pointer_to_other <void_ptr, void_ptr>::type void_ptr_ptr; friend class iterator<T, const T, typename boost::pointer_to_other<Pointer, T>::type>; public: typedef std::random_access_iterator_tag iterator_category; typedef T value_type; typedef typename std::iterator_traits <Pointer>::difference_type difference_type; typedef Pointer pointer; typedef Reference reference; iterator() {} explicit iterator(node_type_ptr_t pn) : pn(pn) {} iterator(const iterator<T, T&, typename boost::pointer_to_other<Pointer, T>::type >& x) : pn(x.pn) {} private: static node_type_ptr_t node_ptr_cast(void_ptr p) { using boost::get_pointer; return node_type_ptr_t(static_cast<node_type_t*>(stable_vector_detail::get_pointer(p))); } static void_ptr_ptr void_ptr_ptr_cast(void_ptr p) { using boost::get_pointer; return void_ptr_ptr(static_cast<void_ptr*>(stable_vector_detail::get_pointer(p))); } reference dereference() const { return pn->value; } bool equal(const iterator& x) const { return pn==x.pn; } void increment() { pn = node_ptr_cast(*(void_ptr_ptr_cast(pn->up)+1)); } void decrement() { pn = node_ptr_cast(*(void_ptr_ptr_cast(pn->up)-1)); } void advance(std::ptrdiff_t n) { pn = node_ptr_cast(*(void_ptr_ptr_cast(pn->up)+n)); } std::ptrdiff_t distance_to(const iterator& x)const { return void_ptr_ptr_cast(x.pn->up) - void_ptr_ptr_cast(pn->up); } public: //Pointer like operators reference operator*() const { return this->dereference(); } pointer operator->() const { return pointer(&this->dereference()); } //Increment / Decrement iterator& operator++() { this->increment(); return *this; } iterator operator++(int) { iterator tmp(*this); ++*this; return iterator(tmp); } iterator& operator--() { this->decrement(); return *this; } iterator operator--(int) { iterator tmp(*this); --*this; return iterator(tmp); } reference operator[](difference_type off) const { iterator tmp(*this); tmp += off; return *tmp; } iterator& operator+=(difference_type off) { pn = node_ptr_cast(*(void_ptr_ptr_cast(pn->up)+off)); return *this; } iterator operator+(difference_type off) const { iterator tmp(*this); tmp += off; return tmp; } friend iterator operator+(difference_type off, const iterator& right) { iterator tmp(right); tmp += off; return tmp; } iterator& operator-=(difference_type off) { *this += -off; return *this; } iterator operator-(difference_type off) const { iterator tmp(*this); tmp -= off; return tmp; } difference_type operator-(const iterator& right) const { void_ptr_ptr p1 = void_ptr_ptr_cast(this->pn->up); void_ptr_ptr p2 = void_ptr_ptr_cast(right.pn->up); return p1 - p2; } //Comparison operators bool operator== (const iterator& r) const { return pn == r.pn; } bool operator!= (const iterator& r) const { return pn != r.pn; } bool operator< (const iterator& r) const { return void_ptr_ptr_cast(pn->up) < void_ptr_ptr_cast(r.pn->up); } bool operator<= (const iterator& r) const { return void_ptr_ptr_cast(pn->up) <= void_ptr_ptr_cast(r.pn->up); } bool operator> (const iterator& r) const { return void_ptr_ptr_cast(pn->up) > void_ptr_ptr_cast(r.pn->up); } bool operator>= (const iterator& r) const { return void_ptr_ptr_cast(pn->up) >= void_ptr_ptr_cast(r.pn->up); } node_type_ptr_t pn; }; template<class Allocator, unsigned int Version> struct select_multiallocation_chain { typedef typename Allocator::multiallocation_chain type; }; template<class Allocator> struct select_multiallocation_chain<Allocator, 1> { typedef typename Allocator::template rebind<void>::other::pointer void_ptr; typedef containers_detail::basic_multiallocation_chain <void_ptr> multialloc_cached_counted; typedef boost::container::containers_detail::transform_multiallocation_chain <multialloc_cached_counted, typename Allocator::value_type> type; }; } //namespace stable_vector_detail #if defined(STABLE_VECTOR_ENABLE_INVARIANT_CHECKING) #define STABLE_VECTOR_CHECK_INVARIANT \ invariant_checker BOOST_JOIN(check_invariant_,__LINE__)(*this); \ BOOST_JOIN(check_invariant_,__LINE__).touch(); #else #define STABLE_VECTOR_CHECK_INVARIANT #endif //#if defined(STABLE_VECTOR_ENABLE_INVARIANT_CHECKING) /// @endcond //!Help taken from (<a href="http://bannalia.blogspot.com/2008/09/introducing-stablevector.html" > Introducing stable_vector</a>) //! //!We present stable_vector, a fully STL-compliant stable container that provides //!most of the features of std::vector except element contiguity. //! //!General properties: stable_vector satisfies all the requirements of a container, //!a reversible container and a sequence and provides all the optional operations //!present in std::vector. Like std::vector, iterators are random access. //!stable_vector does not provide element contiguity; in exchange for this absence, //!the container is stable, i.e. references and iterators to an element of a stable_vector //!remain valid as long as the element is not erased, and an iterator that has been //!assigned the return value of end() always remain valid until the destruction of //!the associated stable_vector. //! //!Operation complexity: The big-O complexities of stable_vector operations match //!exactly those of std::vector. In general, insertion/deletion is constant time at //!the end of the sequence and linear elsewhere. Unlike std::vector, stable_vector //!does not internally perform any value_type destruction, copy or assignment //!operations other than those exactly corresponding to the insertion of new //!elements or deletion of stored elements, which can sometimes compensate in terms //!of performance for the extra burden of doing more pointer manipulation and an //!additional allocation per element. //! //!Exception safety: As stable_vector does not internally copy elements around, some //!operations provide stronger exception safety guarantees than in std::vector: template<typename T, typename Allocator> class stable_vector { ///@cond typedef typename containers_detail:: move_const_ref_type<T>::type insert_const_ref_type; typedef typename Allocator::template rebind<void>::other::pointer void_ptr; typedef typename Allocator::template rebind<void_ptr>::other::pointer void_ptr_ptr; typedef stable_vector_detail::node_type <void_ptr, T> node_type_t; typedef typename Allocator::template rebind<node_type_t>::other::pointer node_type_ptr_t; typedef stable_vector_detail::node_type_base <void_ptr> node_type_base_t; typedef typename Allocator::template rebind<node_type_base_t>::other::pointer node_type_base_ptr_t; typedef #if defined (STABLE_VECTOR_USE_CONTAINERS_VECTOR) ::boost::container:: #else ::std:: #endif //STABLE_VECTOR_USE_CONTAINERS_VECTOR vector<void_ptr, typename Allocator:: template rebind<void_ptr>::other > impl_type; typedef typename impl_type::iterator impl_iterator; typedef typename impl_type::const_iterator const_impl_iterator; typedef ::boost::container::containers_detail:: integral_constant<unsigned, 1> allocator_v1; typedef ::boost::container::containers_detail:: integral_constant<unsigned, 2> allocator_v2; typedef ::boost::container::containers_detail::integral_constant <unsigned, boost::container::containers_detail:: version<Allocator>::value> alloc_version; typedef typename Allocator:: template rebind<node_type_t>::other node_allocator_type; node_type_ptr_t allocate_one() { return this->allocate_one(alloc_version()); } node_type_ptr_t allocate_one(allocator_v1) { return get_al().allocate(1); } node_type_ptr_t allocate_one(allocator_v2) { return get_al().allocate_one(); } void deallocate_one(node_type_ptr_t p) { return this->deallocate_one(p, alloc_version()); } void deallocate_one(node_type_ptr_t p, allocator_v1) { get_al().deallocate(p, 1); } void deallocate_one(node_type_ptr_t p, allocator_v2) { get_al().deallocate_one(p); } friend class stable_vector_detail::clear_on_destroy<stable_vector>; ///@endcond public: // types: typedef typename Allocator::reference reference; typedef typename Allocator::const_reference const_reference; typedef typename Allocator::pointer pointer; typedef typename Allocator::const_pointer const_pointer; typedef stable_vector_detail::iterator <T,T&, pointer> iterator; typedef stable_vector_detail::iterator <T,const T&, const_pointer> const_iterator; typedef typename impl_type::size_type size_type; typedef typename iterator::difference_type difference_type; typedef T value_type; typedef Allocator allocator_type; typedef std::reverse_iterator<iterator> reverse_iterator; typedef std::reverse_iterator<const_iterator> const_reverse_iterator; ///@cond private: BOOST_MOVE_MACRO_COPYABLE_AND_MOVABLE(stable_vector) static const size_type ExtraPointers = 3; typedef typename stable_vector_detail:: select_multiallocation_chain < node_allocator_type , alloc_version::value >::type multiallocation_chain; ///@endcond public: // construct/copy/destroy: explicit stable_vector(const Allocator& al=Allocator()) : internal_data(al),impl(al) { STABLE_VECTOR_CHECK_INVARIANT; } explicit stable_vector(size_type n) : internal_data(Allocator()),impl(Allocator()) { stable_vector_detail::clear_on_destroy<stable_vector> cod(*this); this->resize(n); STABLE_VECTOR_CHECK_INVARIANT; cod.release(); } stable_vector(size_type n, const T& t, const Allocator& al=Allocator()) : internal_data(al),impl(al) { stable_vector_detail::clear_on_destroy<stable_vector> cod(*this); this->insert(this->cbegin(), n, t); STABLE_VECTOR_CHECK_INVARIANT; cod.release(); } template <class InputIterator> stable_vector(InputIterator first,InputIterator last,const Allocator& al=Allocator()) : internal_data(al),impl(al) { stable_vector_detail::clear_on_destroy<stable_vector> cod(*this); this->insert(this->cbegin(), first, last); STABLE_VECTOR_CHECK_INVARIANT; cod.release(); } stable_vector(const stable_vector& x) : internal_data(x.get_al()),impl(x.get_al()) { stable_vector_detail::clear_on_destroy<stable_vector> cod(*this); this->insert(this->cbegin(), x.begin(), x.end()); STABLE_VECTOR_CHECK_INVARIANT; cod.release(); } stable_vector(BOOST_MOVE_MACRO_RV_REF(stable_vector) x) : internal_data(x.get_al()),impl(x.get_al()) { this->swap(x); } ~stable_vector() { this->clear(); clear_pool(); } stable_vector& operator=(BOOST_MOVE_MACRO_COPY_ASSIGN_REF(stable_vector) x) { STABLE_VECTOR_CHECK_INVARIANT; if (this != &x) { this->assign(x.begin(), x.end()); } return *this; } stable_vector& operator=(BOOST_MOVE_MACRO_RV_REF(stable_vector) x) { if (&x != this){ this->swap(x); x.clear(); } return *this; } template<typename InputIterator> void assign(InputIterator first,InputIterator last) { assign_dispatch(first, last, boost::is_integral<InputIterator>()); } void assign(size_type n,const T& t) { typedef constant_iterator<value_type, difference_type> cvalue_iterator; return assign_dispatch(cvalue_iterator(t, n), cvalue_iterator(), boost::mpl::false_()); } allocator_type get_allocator()const {return get_al();} // iterators: iterator begin() { return (impl.empty()) ? end(): iterator(node_ptr_cast(impl.front())) ; } const_iterator begin()const { return (impl.empty()) ? cend() : const_iterator(node_ptr_cast(impl.front())) ; } iterator end() {return iterator(get_end_node());} const_iterator end()const {return const_iterator(get_end_node());} reverse_iterator rbegin() {return reverse_iterator(this->end());} const_reverse_iterator rbegin()const {return const_reverse_iterator(this->end());} reverse_iterator rend() {return reverse_iterator(this->begin());} const_reverse_iterator rend()const {return const_reverse_iterator(this->begin());} const_iterator cbegin()const {return this->begin();} const_iterator cend()const {return this->end();} const_reverse_iterator crbegin()const{return this->rbegin();} const_reverse_iterator crend()const {return this->rend();} // capacity: size_type size() const { return impl.empty() ? 0 : (impl.size() - ExtraPointers); } size_type max_size() const { return impl.max_size() - ExtraPointers; } size_type capacity() const { if(!impl.capacity()){ return 0; } else{ const size_type num_nodes = this->impl.size() + this->internal_data.pool_size; const size_type num_buck = this->impl.capacity(); return (num_nodes < num_buck) ? num_nodes : num_buck; } } bool empty() const { return impl.empty() || impl.size() == ExtraPointers; } void resize(size_type n, const T& t) { STABLE_VECTOR_CHECK_INVARIANT; if(n > size()) this->insert(this->cend(), n - this->size(), t); else if(n < this->size()) this->erase(this->cbegin() + n, this->cend()); } void resize(size_type n) { typedef default_construct_iterator<value_type, difference_type> default_iterator; STABLE_VECTOR_CHECK_INVARIANT; if(n > size()) this->insert(this->cend(), default_iterator(n - this->size()), default_iterator()); else if(n < this->size()) this->erase(this->cbegin() + n, this->cend()); } void reserve(size_type n) { STABLE_VECTOR_CHECK_INVARIANT; if(n > this->max_size()) throw std::bad_alloc(); size_type size = this->size(); size_type old_capacity = this->capacity(); if(n > old_capacity){ this->initialize_end_node(n); const void * old_ptr = &impl[0]; impl.reserve(n + ExtraPointers); bool realloced = &impl[0] != old_ptr; //Fix the pointers for the newly allocated buffer if(realloced){ this->align_nodes(impl.begin(), impl.begin()+size+1); } //Now fill pool if data is not enough if((n - size) > this->internal_data.pool_size){ this->add_to_pool((n - size) - this->internal_data.pool_size); } } } // element access: reference operator[](size_type n){return value(impl[n]);} const_reference operator[](size_type n)const{return value(impl[n]);} const_reference at(size_type n)const { if(n>=size()) throw std::out_of_range("invalid subscript at stable_vector::at"); return operator[](n); } reference at(size_type n) { if(n>=size()) throw std::out_of_range("invalid subscript at stable_vector::at"); return operator[](n); } reference front() { return value(impl.front()); } const_reference front()const { return value(impl.front()); } reference back() { return value(*(&impl.back() - ExtraPointers)); } const_reference back()const { return value(*(&impl.back() - ExtraPointers)); } // modifiers: void push_back(insert_const_ref_type x) { return priv_push_back(x); } #if defined(BOOST_NO_RVALUE_REFERENCES) && !defined(BOOST_MOVE_DOXYGEN_INVOKED) void push_back(T &x) { push_back(const_cast<const T &>(x)); } template<class U> void push_back(const U &u, typename containers_detail::enable_if_c<containers_detail::is_same<T, U>::value && !::BOOST_CONTAINER_MOVE_NAMESPACE::is_movable<U>::value >::type* =0) { return priv_push_back(u); } #endif void push_back(BOOST_MOVE_MACRO_RV_REF(T) t) { this->insert(end(), BOOST_CONTAINER_MOVE_NAMESPACE::move(t)); } void pop_back() { this->erase(this->end()-1); } iterator insert(const_iterator position, insert_const_ref_type x) { return this->priv_insert(position, x); } #if defined(BOOST_NO_RVALUE_REFERENCES) && !defined(BOOST_MOVE_DOXYGEN_INVOKED) iterator insert(const_iterator position, T &x) { return this->insert(position, const_cast<const T &>(x)); } template<class U> iterator insert(const_iterator position, const U &u, typename containers_detail::enable_if_c<containers_detail::is_same<T, U>::value && !::BOOST_CONTAINER_MOVE_NAMESPACE::is_movable<U>::value >::type* =0) { return this->priv_insert(position, u); } #endif iterator insert(const_iterator position, BOOST_MOVE_MACRO_RV_REF(T) x) { typedef repeat_iterator<T, difference_type> repeat_it; typedef BOOST_CONTAINER_MOVE_NAMESPACE::move_iterator<repeat_it> repeat_move_it; //Just call more general insert(pos, size, value) and return iterator size_type pos_n = position - cbegin(); this->insert(position ,repeat_move_it(repeat_it(x, 1)) ,repeat_move_it(repeat_it())); return iterator(this->begin() + pos_n); } void insert(const_iterator position, size_type n, const T& t) { STABLE_VECTOR_CHECK_INVARIANT; this->insert_not_iter(position, n, t); } template <class InputIterator> void insert(const_iterator position,InputIterator first, InputIterator last) { STABLE_VECTOR_CHECK_INVARIANT; this->insert_iter(position,first,last, boost::mpl::not_<boost::is_integral<InputIterator> >()); } #if defined(BOOST_CONTAINERS_PERFECT_FORWARDING) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) //! <b>Effects</b>: Inserts an object of type T constructed with //! std::forward<Args>(args)... in the end of the vector. //! //! <b>Throws</b>: If memory allocation throws or the in-place constructor throws. //! //! <b>Complexity</b>: Amortized constant time. template<class ...Args> void emplace_back(Args &&...args) { typedef emplace_functor<node_type_t, Args...> EmplaceFunctor; typedef emplace_iterator<node_type_t, EmplaceFunctor> EmplaceIterator; EmplaceFunctor &&ef = EmplaceFunctor(BOOST_CONTAINER_MOVE_NAMESPACE::forward<Args>(args)...); this->insert(this->cend(), EmplaceIterator(ef), EmplaceIterator()); } //! <b>Requires</b>: position must be a valid iterator of *this. //! //! <b>Effects</b>: Inserts an object of type T constructed with //! std::forward<Args>(args)... before position //! //! <b>Throws</b>: If memory allocation throws or the in-place constructor throws. //! //! <b>Complexity</b>: If position is end(), amortized constant time //! Linear time otherwise. template<class ...Args> iterator emplace(const_iterator position, Args && ...args) { //Just call more general insert(pos, size, value) and return iterator size_type pos_n = position - cbegin(); typedef emplace_functor<node_type_t, Args...> EmplaceFunctor; typedef emplace_iterator<node_type_t, EmplaceFunctor> EmplaceIterator; EmplaceFunctor &&ef = EmplaceFunctor(BOOST_CONTAINER_MOVE_NAMESPACE::forward<Args>(args)...); this->insert(position, EmplaceIterator(ef), EmplaceIterator()); return iterator(this->begin() + pos_n); } #else void emplace_back() { typedef emplace_functor<node_type_t> EmplaceFunctor; typedef emplace_iterator<node_type_t, EmplaceFunctor> EmplaceIterator; EmplaceFunctor ef; this->insert(this->cend(), EmplaceIterator(ef), EmplaceIterator()); } iterator emplace(const_iterator position) { typedef emplace_functor<node_type_t> EmplaceFunctor; typedef emplace_iterator<node_type_t, EmplaceFunctor> EmplaceIterator; EmplaceFunctor ef; size_type pos_n = position - this->cbegin(); this->insert(position, EmplaceIterator(ef), EmplaceIterator()); return iterator(this->begin() + pos_n); } #define BOOST_PP_LOCAL_MACRO(n) \ template<BOOST_PP_ENUM_PARAMS(n, class P)> \ void emplace_back(BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_LIST, _)) \ { \ typedef BOOST_PP_CAT(BOOST_PP_CAT(emplace_functor, n), arg) \ <node_type_t, BOOST_PP_ENUM_PARAMS(n, P)> EmplaceFunctor; \ typedef emplace_iterator<node_type_t, EmplaceFunctor> EmplaceIterator; \ EmplaceFunctor ef(BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_FORWARD, _)); \ this->insert(this->cend(), EmplaceIterator(ef), EmplaceIterator()); \ } \ \ template<BOOST_PP_ENUM_PARAMS(n, class P)> \ iterator emplace(const_iterator pos, BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_LIST, _)) \ { \ typedef BOOST_PP_CAT(BOOST_PP_CAT(emplace_functor, n), arg) \ <node_type_t, BOOST_PP_ENUM_PARAMS(n, P)> EmplaceFunctor; \ typedef emplace_iterator<node_type_t, EmplaceFunctor> EmplaceIterator; \ EmplaceFunctor ef(BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_FORWARD, _)); \ size_type pos_n = pos - this->cbegin(); \ this->insert(pos, EmplaceIterator(ef), EmplaceIterator()); \ return iterator(this->begin() + pos_n); \ } \ //! #define BOOST_PP_LOCAL_LIMITS (1, BOOST_CONTAINERS_MAX_CONSTRUCTOR_PARAMETERS) #include BOOST_PP_LOCAL_ITERATE() #endif //#ifdef BOOST_CONTAINERS_PERFECT_FORWARDING iterator erase(const_iterator position) { STABLE_VECTOR_CHECK_INVARIANT; difference_type d=position-this->cbegin(); impl_iterator it=impl.begin()+d; this->delete_node(*it); impl.erase(it); this->align_nodes(impl.begin()+d,get_last_align()); return this->begin()+d; } iterator erase(const_iterator first, const_iterator last) { return priv_erase(first, last, alloc_version()); } void swap(stable_vector & x) { STABLE_VECTOR_CHECK_INVARIANT; this->swap_impl(*this,x); } void clear() { this->erase(this->cbegin(),this->cend()); } /// @cond private: iterator priv_insert(const_iterator position, const value_type &t) { typedef constant_iterator<value_type, difference_type> cvalue_iterator; return this->insert_iter(position, cvalue_iterator(t, 1), cvalue_iterator(), std::forward_iterator_tag()); } void priv_push_back(const value_type &t) { this->insert(end(), t); } void clear_pool(allocator_v1) { if(!impl.empty() && impl.back()){ void_ptr &p1 = *(impl.end()-2); void_ptr &p2 = impl.back(); multiallocation_chain holder; holder.incorporate_after(holder.before_begin(), p1, p2, this->internal_data.pool_size); while(!holder.empty()){ node_type_ptr_t n = holder.front(); holder.pop_front(); this->deallocate_one(n); } p1 = p2 = 0; this->internal_data.pool_size = 0; } } void clear_pool(allocator_v2) { if(!impl.empty() && impl.back()){ void_ptr &p1 = *(impl.end()-2); void_ptr &p2 = impl.back(); multiallocation_chain holder; holder.incorporate_after(holder.before_begin(), p1, p2, internal_data.pool_size); get_al().deallocate_individual(BOOST_CONTAINER_MOVE_NAMESPACE::move(holder)); p1 = p2 = 0; this->internal_data.pool_size = 0; } } void clear_pool() { this->clear_pool(alloc_version()); } void add_to_pool(size_type n) { this->add_to_pool(n, alloc_version()); } void add_to_pool(size_type n, allocator_v1) { size_type remaining = n; while(remaining--){ this->put_in_pool(this->allocate_one()); } } void add_to_pool(size_type n, allocator_v2) { void_ptr &p1 = *(impl.end()-2); void_ptr &p2 = impl.back(); multiallocation_chain holder; holder.incorporate_after(holder.before_begin(), p1, p2, internal_data.pool_size); BOOST_STATIC_ASSERT((::BOOST_CONTAINER_MOVE_NAMESPACE::is_movable<multiallocation_chain>::value == true)); multiallocation_chain m (get_al().allocate_individual(n)); holder.splice_after(holder.before_begin(), m, m.before_begin(), m.last(), n); this->internal_data.pool_size += n; std::pair<void_ptr, void_ptr> data(holder.extract_data()); p1 = data.first; p2 = data.second; } void put_in_pool(node_type_ptr_t p) { void_ptr &p1 = *(impl.end()-2); void_ptr &p2 = impl.back(); multiallocation_chain holder; holder.incorporate_after(holder.before_begin(), p1, p2, internal_data.pool_size); holder.push_front(p); ++this->internal_data.pool_size; std::pair<void_ptr, void_ptr> ret(holder.extract_data()); p1 = ret.first; p2 = ret.second; } node_type_ptr_t get_from_pool() { if(!impl.back()){ return node_type_ptr_t(0); } else{ void_ptr &p1 = *(impl.end()-2); void_ptr &p2 = impl.back(); multiallocation_chain holder; holder.incorporate_after(holder.before_begin(), p1, p2, internal_data.pool_size); node_type_ptr_t ret = holder.front(); holder.pop_front(); --this->internal_data.pool_size; if(!internal_data.pool_size){ p1 = p2 = 0; } else{ std::pair<void_ptr, void_ptr> data(holder.extract_data()); p1 = data.first; p2 = data.second; } return ret; } } void insert_iter_prolog(size_type n, difference_type d) { initialize_end_node(n); const void* old_ptr = &impl[0]; //size_type old_capacity = capacity(); //size_type old_size = size(); impl.insert(impl.begin()+d, n, 0); bool realloced = &impl[0] != old_ptr; //Fix the pointers for the newly allocated buffer if(realloced){ align_nodes(impl.begin(), impl.begin()+d); } } template<typename InputIterator> void assign_dispatch(InputIterator first, InputIterator last, boost::mpl::false_) { STABLE_VECTOR_CHECK_INVARIANT; iterator first1 = this->begin(); iterator last1 = this->end(); for ( ; first1 != last1 && first != last; ++first1, ++first) *first1 = *first; if (first == last){ this->erase(first1, last1); } else{ this->insert(last1, first, last); } } template<typename Integer> void assign_dispatch(Integer n, Integer t, boost::mpl::true_) { typedef constant_iterator<value_type, difference_type> cvalue_iterator; this->assign_dispatch(cvalue_iterator(t, n), cvalue_iterator(), boost::mpl::false_()); } iterator priv_erase(const_iterator first, const_iterator last, allocator_v1) { STABLE_VECTOR_CHECK_INVARIANT; difference_type d1 = first - this->cbegin(), d2 = last - this->cbegin(); if(d1 != d2){ impl_iterator it1(impl.begin() + d1), it2(impl.begin() + d2); for(impl_iterator it = it1; it != it2; ++it) this->delete_node(*it); impl.erase(it1, it2); this->align_nodes(impl.begin() + d1, get_last_align()); } return iterator(this->begin() + d1); } impl_iterator get_last_align() { return impl.end() - (ExtraPointers - 1); } const_impl_iterator get_last_align() const { return impl.cend() - (ExtraPointers - 1); } template<class AllocatorVersion> iterator priv_erase(const_iterator first, const_iterator last, AllocatorVersion, typename boost::container::containers_detail::enable_if_c <boost::container::containers_detail::is_same<AllocatorVersion, allocator_v2> ::value>::type * = 0) { STABLE_VECTOR_CHECK_INVARIANT; return priv_erase(first, last, allocator_v1()); } static node_type_ptr_t node_ptr_cast(void_ptr p) { using boost::get_pointer; return node_type_ptr_t(static_cast<node_type_t*>(stable_vector_detail::get_pointer(p))); } static node_type_base_ptr_t node_base_ptr_cast(void_ptr p) { using boost::get_pointer; return node_type_base_ptr_t(static_cast<node_type_base_t*>(stable_vector_detail::get_pointer(p))); } static value_type& value(void_ptr p) { return node_ptr_cast(p)->value; } void initialize_end_node(size_type impl_capacity = 0) { if(impl.empty()){ impl.reserve(impl_capacity + ExtraPointers); impl.resize (ExtraPointers, void_ptr(0)); impl[0] = &this->internal_data.end_node; this->internal_data.end_node.up = &impl[0]; } } void readjust_end_node() { if(!this->impl.empty()){ void_ptr &end_node_ref = *(this->get_last_align()-1); end_node_ref = this->get_end_node(); this->internal_data.end_node.up = &end_node_ref; } else{ this->internal_data.end_node.up = void_ptr(&this->internal_data.end_node.up); } } node_type_ptr_t get_end_node() const { const node_type_base_t* cp = &this->internal_data.end_node; node_type_base_t* p = const_cast<node_type_base_t*>(cp); return node_ptr_cast(p); } template<class Iter> void_ptr new_node(void_ptr up, Iter it) { node_type_ptr_t p = this->allocate_one(); try{ boost::container::construct_in_place(&*p, it); p->set_pointer(up); } catch(...){ this->deallocate_one(p); throw; } return p; } void delete_node(void_ptr p) { node_type_ptr_t n(node_ptr_cast(p)); n->~node_type_t(); this->put_in_pool(n); } static void align_nodes(impl_iterator first,impl_iterator last) { while(first!=last){ node_ptr_cast(*first)->up = void_ptr(&*first); ++first; } } void insert_not_iter(const_iterator position, size_type n, const T& t) { typedef constant_iterator<value_type, difference_type> cvalue_iterator; this->insert_iter(position, cvalue_iterator(t, n), cvalue_iterator(), std::forward_iterator_tag()); } template <class InputIterator> void insert_iter(const_iterator position,InputIterator first,InputIterator last, boost::mpl::true_) { typedef typename std::iterator_traits<InputIterator>::iterator_category category; this->insert_iter(position, first, last, category()); } template <class InputIterator> void insert_iter(const_iterator position,InputIterator first,InputIterator last,std::input_iterator_tag) { for(; first!=last; ++first){ this->insert(position, *first); } } template <class InputIterator> iterator insert_iter(const_iterator position, InputIterator first, InputIterator last, std::forward_iterator_tag) { size_type n = (size_type)std::distance(first,last); difference_type d = position-this->cbegin(); if(n){ this->insert_iter_prolog(n, d); const impl_iterator it(impl.begin() + d); this->insert_iter_fwd(it, first, last, n); //Fix the pointers for the newly allocated buffer this->align_nodes(it + n, get_last_align()); } return this->begin() + d; } template <class FwdIterator> void insert_iter_fwd_alloc(const impl_iterator it, FwdIterator first, FwdIterator last, difference_type n, allocator_v1) { size_type i=0; try{ while(first!=last){ *(it + i) = this->new_node(void_ptr((void*)(&*(it + i))), first); ++first; ++i; } } catch(...){ impl.erase(it + i, it + n); this->align_nodes(it + i, get_last_align()); throw; } } template <class FwdIterator> void insert_iter_fwd_alloc(const impl_iterator it, FwdIterator first, FwdIterator last, difference_type n, allocator_v2) { multiallocation_chain mem(get_al().allocate_individual(n)); size_type i = 0; node_type_ptr_t p = 0; try{ while(first != last){ p = mem.front(); mem.pop_front(); //This can throw boost::container::construct_in_place(&*p, first); p->set_pointer(void_ptr((void*)(&*(it + i)))); ++first; *(it + i) = p; ++i; } } catch(...){ get_al().deallocate_one(p); get_al().deallocate_many(BOOST_CONTAINER_MOVE_NAMESPACE::move(mem)); impl.erase(it+i, it+n); this->align_nodes(it+i,get_last_align()); throw; } } template <class FwdIterator> void insert_iter_fwd(const impl_iterator it, FwdIterator first, FwdIterator last, difference_type n) { size_type i = 0; node_type_ptr_t p = 0; try{ while(first != last){ p = get_from_pool(); if(!p){ insert_iter_fwd_alloc(it+i, first, last, n-i, alloc_version()); break; } //This can throw boost::container::construct_in_place(&*p, first); p->set_pointer(void_ptr(&*(it+i))); ++first; *(it+i)=p; ++i; } } catch(...){ put_in_pool(p); impl.erase(it+i,it+n); this->align_nodes(it+i,get_last_align()); throw; } } template <class InputIterator> void insert_iter(const_iterator position, InputIterator first, InputIterator last, boost::mpl::false_) { this->insert_not_iter(position, first, last); } static void swap_impl(stable_vector& x,stable_vector& y) { using std::swap; swap(x.get_al(),y.get_al()); swap(x.impl,y.impl); swap(x.internal_data.pool_size, y.internal_data.pool_size); x.readjust_end_node(); y.readjust_end_node(); } #if defined(STABLE_VECTOR_ENABLE_INVARIANT_CHECKING) bool invariant()const { if(impl.empty()) return !capacity() && !size(); if(get_end_node() != *(impl.end() - ExtraPointers)){ return false; } for(const_impl_iterator it=impl.begin(),it_end=get_last_align();it!=it_end;++it){ if(node_ptr_cast(*it)->up != &*it) return false; } size_type n = capacity()-size(); const void_ptr &pool_head = impl.back(); size_type num_pool = 0; node_type_ptr_t p = node_ptr_cast(pool_head); while(p){ ++num_pool; p = p->up; } return n >= num_pool; } class invariant_checker:private boost::noncopyable { const stable_vector* p; public: invariant_checker(const stable_vector& v):p(&v){} ~invariant_checker(){BOOST_ASSERT(p->invariant());} void touch(){} }; #endif struct ebo_holder : node_allocator_type { ebo_holder(const allocator_type &a) : node_allocator_type(a), pool_size(0), end_node() { end_node.set_pointer(void_ptr(&end_node.up)); } size_type pool_size; node_type_base_t end_node; } internal_data; node_allocator_type &get_al() { return internal_data; } const node_allocator_type &get_al() const { return internal_data; } impl_type impl; /// @endcond }; template <typename T,typename Allocator> bool operator==(const stable_vector<T,Allocator>& x,const stable_vector<T,Allocator>& y) { return x.size()==y.size()&&std::equal(x.begin(),x.end(),y.begin()); } template <typename T,typename Allocator> bool operator< (const stable_vector<T,Allocator>& x,const stable_vector<T,Allocator>& y) { return std::lexicographical_compare(x.begin(),x.end(),y.begin(),y.end()); } template <typename T,typename Allocator> bool operator!=(const stable_vector<T,Allocator>& x,const stable_vector<T,Allocator>& y) { return !(x==y); } template <typename T,typename Allocator> bool operator> (const stable_vector<T,Allocator>& x,const stable_vector<T,Allocator>& y) { return y<x; } template <typename T,typename Allocator> bool operator>=(const stable_vector<T,Allocator>& x,const stable_vector<T,Allocator>& y) { return !(x<y); } template <typename T,typename Allocator> bool operator<=(const stable_vector<T,Allocator>& x,const stable_vector<T,Allocator>& y) { return !(x>y); } // specialized algorithms: template <typename T, typename Allocator> void swap(stable_vector<T,Allocator>& x,stable_vector<T,Allocator>& y) { x.swap(y); } /// @cond #undef STABLE_VECTOR_CHECK_INVARIANT /// @endcond }} #include INCLUDE_BOOST_CONTAINER_DETAIL_CONFIG_END_HPP #endif //BOOST_CONTAINER_STABLE_VECTOR_HPP