diff options
Diffstat (limited to 'boost/container/vector.hpp')
-rw-r--r-- | boost/container/vector.hpp | 630 |
1 files changed, 356 insertions, 274 deletions
diff --git a/boost/container/vector.hpp b/boost/container/vector.hpp index 8e1e7a53a3..89ed12e99f 100644 --- a/boost/container/vector.hpp +++ b/boost/container/vector.hpp @@ -27,6 +27,7 @@ #include <boost/container/allocator_traits.hpp> #include <boost/container/new_allocator.hpp> //new_allocator #include <boost/container/throw_exception.hpp> +#include <boost/container/options.hpp> // container detail #include <boost/container/detail/advanced_insert_int.hpp> #include <boost/container/detail/algorithm.hpp> //equal() @@ -39,6 +40,7 @@ #include <boost/move/detail/iterator_to_raw_pointer.hpp> #include <boost/container/detail/mpl.hpp> #include <boost/container/detail/next_capacity.hpp> +#include <boost/container/detail/value_functors.hpp> #include <boost/move/detail/to_raw_pointer.hpp> #include <boost/container/detail/type_traits.hpp> #include <boost/container/detail/version_type.hpp> @@ -58,6 +60,7 @@ #include <boost/move/algo/adaptive_merge.hpp> #include <boost/move/algo/unique.hpp> #include <boost/move/algo/predicate.hpp> +#include <boost/move/algo/detail/set_difference.hpp> // other #include <boost/core/no_exceptions_support.hpp> #include <boost/assert.hpp> @@ -73,7 +76,6 @@ namespace container { #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED -namespace container_detail { template <class Pointer, bool IsConst> class vec_iterator @@ -82,7 +84,7 @@ class vec_iterator typedef std::random_access_iterator_tag iterator_category; typedef typename boost::intrusive::pointer_traits<Pointer>::element_type value_type; typedef typename boost::intrusive::pointer_traits<Pointer>::difference_type difference_type; - typedef typename if_c + typedef typename dtl::if_c < IsConst , typename boost::intrusive::pointer_traits<Pointer>::template rebind_pointer<const value_type>::type @@ -210,64 +212,28 @@ struct vector_insert_ordered_cursor BiDirValueIt last_value_it; }; -template<class T, class SizeType, class BiDirValueIt, class Comp> -struct vector_merge_cursor -{ - typedef SizeType size_type; - typedef typename iterator_traits<BiDirValueIt>::reference reference; - - BOOST_CONTAINER_FORCEINLINE vector_merge_cursor(T *pbeg, T *plast, BiDirValueIt valueit, Comp &cmp) - : m_pbeg(pbeg), m_pcur(--plast), m_valueit(valueit), m_cmp(cmp) - {} - - void operator --() - { - --m_valueit; - const T &t = *m_valueit; - while((m_pcur + 1) != m_pbeg){ - if(!m_cmp(t, *m_pcur)){ - break; - } - --m_pcur; - } - } - - BOOST_CONTAINER_FORCEINLINE size_type get_pos() const - { return static_cast<size_type>((m_pcur + 1) - m_pbeg); } - - BOOST_CONTAINER_FORCEINLINE reference get_val() - { return *m_valueit; } - - T *const m_pbeg; - T *m_pcur; - BiDirValueIt m_valueit; - Comp &m_cmp; -}; - -} //namespace container_detail { +struct initial_capacity_t{}; template<class Pointer, bool IsConst> -BOOST_CONTAINER_FORCEINLINE const Pointer &vector_iterator_get_ptr(const container_detail::vec_iterator<Pointer, IsConst> &it) BOOST_NOEXCEPT_OR_NOTHROW +BOOST_CONTAINER_FORCEINLINE const Pointer &vector_iterator_get_ptr(const vec_iterator<Pointer, IsConst> &it) BOOST_NOEXCEPT_OR_NOTHROW { return it.get_ptr(); } template<class Pointer, bool IsConst> -BOOST_CONTAINER_FORCEINLINE Pointer &get_ptr(container_detail::vec_iterator<Pointer, IsConst> &it) BOOST_NOEXCEPT_OR_NOTHROW +BOOST_CONTAINER_FORCEINLINE Pointer &get_ptr(vec_iterator<Pointer, IsConst> &it) BOOST_NOEXCEPT_OR_NOTHROW { return it.get_ptr(); } -namespace container_detail { - -struct uninitialized_size_t {}; -static const uninitialized_size_t uninitialized_size = uninitialized_size_t(); +struct vector_uninitialized_size_t {}; +static const vector_uninitialized_size_t vector_uninitialized_size = vector_uninitialized_size_t(); template <class T> struct vector_value_traits_base { - static const bool trivial_dctr = is_trivially_destructible<T>::value; + static const bool trivial_dctr = dtl::is_trivially_destructible<T>::value; static const bool trivial_dctr_after_move = has_trivial_destructor_after_move<T>::value; - static const bool trivial_copy = is_trivially_copy_constructible<T>::value; - static const bool nothrow_copy = is_nothrow_copy_constructible<T>::value || trivial_copy; - static const bool trivial_assign = is_trivially_copy_assignable<T>::value; - static const bool nothrow_assign = is_nothrow_copy_assignable<T>::value || trivial_assign; + static const bool trivial_copy = dtl::is_trivially_copy_constructible<T>::value; + static const bool nothrow_copy = dtl::is_nothrow_copy_constructible<T>::value || trivial_copy; + static const bool trivial_assign = dtl::is_trivially_copy_assignable<T>::value; + static const bool nothrow_assign = dtl::is_nothrow_copy_assignable<T>::value || trivial_assign; }; @@ -278,18 +244,19 @@ struct vector_value_traits typedef vector_value_traits_base<typename Allocator::value_type> base_t; //This is the anti-exception array destructor //to deallocate values already constructed - typedef typename container_detail::if_c + typedef typename dtl::if_c <base_t::trivial_dctr - ,container_detail::null_scoped_destructor_n<Allocator> - ,container_detail::scoped_destructor_n<Allocator> + ,dtl::null_scoped_destructor_n<Allocator> + ,dtl::scoped_destructor_n<Allocator> >::type ArrayDestructor; //This is the anti-exception array deallocator - typedef container_detail::scoped_array_deallocator<Allocator> ArrayDeallocator; + typedef dtl::scoped_array_deallocator<Allocator> ArrayDeallocator; }; //!This struct deallocates and allocated memory template < class Allocator - , class AllocatorVersion = typename container_detail::version<Allocator>::type + , class StoredSizeType + , class AllocatorVersion = typename dtl::version<Allocator>::type > struct vector_alloc_holder : public Allocator @@ -298,7 +265,8 @@ struct vector_alloc_holder BOOST_MOVABLE_BUT_NOT_COPYABLE(vector_alloc_holder) public: - typedef Allocator allocator_type; + typedef Allocator allocator_type; + typedef StoredSizeType stored_size_type; typedef boost::container::allocator_traits<Allocator> allocator_traits_type; typedef typename allocator_traits_type::pointer pointer; typedef typename allocator_traits_type::size_type size_type; @@ -322,7 +290,7 @@ struct vector_alloc_holder //Constructor, does not throw vector_alloc_holder() - BOOST_NOEXCEPT_IF(container_detail::is_nothrow_default_constructible<Allocator>::value) + BOOST_NOEXCEPT_IF(dtl::is_nothrow_default_constructible<Allocator>::value) : Allocator(), m_start(), m_size(), m_capacity() {} @@ -334,28 +302,34 @@ struct vector_alloc_holder //Constructor, does not throw template<class AllocConvertible> - vector_alloc_holder(uninitialized_size_t, BOOST_FWD_REF(AllocConvertible) a, size_type initial_size) + vector_alloc_holder(vector_uninitialized_size_t, BOOST_FWD_REF(AllocConvertible) a, size_type initial_size) : Allocator(boost::forward<AllocConvertible>(a)) , m_start() - , m_size(initial_size) //Size is initialized here so vector should only call uninitialized_xxx after this + //Size is initialized here so vector should only call uninitialized_xxx after this + , m_size(static_cast<stored_size_type>(initial_size)) , m_capacity() { if(initial_size){ pointer reuse = pointer(); - m_start = this->allocation_command(allocate_new, initial_size, m_capacity = initial_size, reuse); + size_type final_cap = initial_size; + m_start = this->allocation_command(allocate_new, initial_size, final_cap, reuse); + m_capacity = static_cast<stored_size_type>(final_cap); } } //Constructor, does not throw - vector_alloc_holder(uninitialized_size_t, size_type initial_size) + vector_alloc_holder(vector_uninitialized_size_t, size_type initial_size) : Allocator() , m_start() - , m_size(initial_size) //Size is initialized here so vector should only call uninitialized_xxx after this + //Size is initialized here so vector should only call uninitialized_xxx after this + , m_size(static_cast<stored_size_type>(initial_size)) , m_capacity() { if(initial_size){ pointer reuse = pointer(); - m_start = this->allocation_command(allocate_new, initial_size, m_capacity = initial_size, reuse); + size_type final_cap = initial_size; + m_start = this->allocation_command(allocate_new, initial_size, final_cap, reuse); + m_capacity = static_cast<stored_size_type>(final_cap); } } @@ -369,17 +343,17 @@ struct vector_alloc_holder holder.m_size = holder.m_capacity = 0; } - vector_alloc_holder(pointer p, size_type capacity, BOOST_RV_REF(vector_alloc_holder) holder) + vector_alloc_holder(initial_capacity_t, pointer p, size_type capacity, BOOST_RV_REF(vector_alloc_holder) holder) : Allocator(BOOST_MOVE_BASE(Allocator, holder)) , m_start(p) , m_size(holder.m_size) - , m_capacity(capacity) + , m_capacity(static_cast<stored_size_type>(capacity)) { allocator_type &this_alloc = this->alloc(); allocator_type &x_alloc = holder.alloc(); if(this->is_propagable_from(x_alloc, holder.start(), this_alloc, true)){ if(this->m_capacity){ - allocator_traits_type::deallocate(this->alloc(), this->m_start, this->m_capacity); + this->deallocate(this->m_start, this->m_capacity); } m_start = holder.m_start; m_capacity = holder.m_capacity; @@ -389,23 +363,26 @@ struct vector_alloc_holder else if(this->m_capacity < holder.m_size){ size_type const n = holder.m_size; pointer reuse = pointer(); - m_start = this->allocation_command(allocate_new, n, m_capacity = n, reuse); + size_type final_cap = n; + m_start = this->allocation_command(allocate_new, n, final_cap, reuse); + m_capacity = static_cast<stored_size_type>(final_cap); #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS this->num_alloc += n != 0; #endif } } - vector_alloc_holder(pointer p, size_type n) - BOOST_NOEXCEPT_IF(container_detail::is_nothrow_default_constructible<Allocator>::value) + vector_alloc_holder(initial_capacity_t, pointer p, size_type n) + BOOST_NOEXCEPT_IF(dtl::is_nothrow_default_constructible<Allocator>::value) : Allocator() , m_start(p) , m_size() - , m_capacity(n) + //n is guaranteed to fit into stored_size_type + , m_capacity(static_cast<stored_size_type>(n)) {} template<class AllocFwd> - vector_alloc_holder(pointer p, size_type n, BOOST_FWD_REF(AllocFwd) a) + vector_alloc_holder(initial_capacity_t, pointer p, size_type n, BOOST_FWD_REF(AllocFwd) a) : Allocator(::boost::forward<AllocFwd>(a)) , m_start(p) , m_size() @@ -415,17 +392,32 @@ struct vector_alloc_holder BOOST_CONTAINER_FORCEINLINE ~vector_alloc_holder() BOOST_NOEXCEPT_OR_NOTHROW { if(this->m_capacity){ - allocator_traits_type::deallocate(this->alloc(), this->m_start, this->m_capacity); + this->deallocate(this->m_start, this->m_capacity); } } BOOST_CONTAINER_FORCEINLINE pointer allocation_command(boost::container::allocation_type command, size_type limit_size, size_type &prefer_in_recvd_out_size, pointer &reuse) { - typedef typename container_detail::version<Allocator>::type alloc_version; + typedef typename dtl::version<Allocator>::type alloc_version; return this->priv_allocation_command(alloc_version(), command, limit_size, prefer_in_recvd_out_size, reuse); } + BOOST_CONTAINER_FORCEINLINE pointer allocate(size_type n) + { + const size_type max_alloc = allocator_traits_type::max_size(this->alloc()); + const size_type max = max_alloc <= stored_size_type(-1) ? max_alloc : stored_size_type(-1); + if ( max < n ) + boost::container::throw_length_error("get_next_capacity, allocator's max size reached"); + + return allocator_traits_type::allocate(this->alloc(), n); + } + + BOOST_CONTAINER_FORCEINLINE void deallocate(const pointer &p, size_type n) + { + allocator_traits_type::deallocate(this->alloc(), p, n); + } + bool try_expand_fwd(size_type at_least) { //There is not enough memory, try to expand the old one @@ -443,17 +435,24 @@ struct vector_alloc_holder return success; } - BOOST_CONTAINER_FORCEINLINE size_type next_capacity(size_type additional_objects) const + template<class GrowthFactorType> + size_type next_capacity(size_type additional_objects) const { - return next_capacity_calculator - <size_type, NextCapacityDouble //NextCapacity60Percent - >::get( allocator_traits_type::max_size(this->alloc()) - , this->m_capacity, additional_objects ); + BOOST_ASSERT(additional_objects > size_type(this->m_capacity - this->m_size)); + size_type max = allocator_traits_type::max_size(this->alloc()); + (clamp_by_stored_size_type)(max, stored_size_type()); + const size_type remaining_cap = max - size_type(this->m_capacity); + const size_type min_additional_cap = additional_objects - size_type(this->m_capacity - this->m_size); + + if ( remaining_cap < min_additional_cap ) + boost::container::throw_length_error("get_next_capacity, allocator's max size reached"); + + return GrowthFactorType()( size_type(this->m_capacity), min_additional_cap, max); } - pointer m_start; - size_type m_size; - size_type m_capacity; + pointer m_start; + stored_size_type m_size; + stored_size_type m_capacity; void swap_resources(vector_alloc_holder &x) BOOST_NOEXCEPT_OR_NOTHROW { @@ -477,10 +476,14 @@ struct vector_alloc_holder BOOST_CONTAINER_FORCEINLINE const Allocator &alloc() const BOOST_NOEXCEPT_OR_NOTHROW { return *this; } - const pointer &start() const BOOST_NOEXCEPT_OR_NOTHROW { return m_start; } - const size_type &capacity() const BOOST_NOEXCEPT_OR_NOTHROW { return m_capacity; } - void start(const pointer &p) BOOST_NOEXCEPT_OR_NOTHROW { m_start = p; } - void capacity(const size_type &c) BOOST_NOEXCEPT_OR_NOTHROW { m_capacity = c; } + BOOST_CONTAINER_FORCEINLINE const pointer &start() const BOOST_NOEXCEPT_OR_NOTHROW + { return m_start; } + BOOST_CONTAINER_FORCEINLINE size_type capacity() const BOOST_NOEXCEPT_OR_NOTHROW + { return m_capacity; } + BOOST_CONTAINER_FORCEINLINE void start(const pointer &p) BOOST_NOEXCEPT_OR_NOTHROW + { m_start = p; } + BOOST_CONTAINER_FORCEINLINE void capacity(const size_type &c) BOOST_NOEXCEPT_OR_NOTHROW + { BOOST_ASSERT( c <= stored_size_type(-1)); m_capacity = c; } private: void priv_first_allocation(size_type cap) @@ -495,15 +498,30 @@ struct vector_alloc_holder } } + BOOST_CONTAINER_FORCEINLINE static void clamp_by_stored_size_type(size_type &, size_type) + {} + + template<class SomeStoredSizeType> + BOOST_CONTAINER_FORCEINLINE static void clamp_by_stored_size_type(size_type &s, SomeStoredSizeType) + { + if (s >= SomeStoredSizeType(-1) ) + s = SomeStoredSizeType(-1); + } + BOOST_CONTAINER_FORCEINLINE pointer priv_allocation_command(version_1, boost::container::allocation_type command, - size_type , + size_type limit_size, size_type &prefer_in_recvd_out_size, pointer &reuse) { (void)command; BOOST_ASSERT( (command & allocate_new)); BOOST_ASSERT(!(command & nothrow_allocation)); - pointer const p = allocator_traits_type::allocate(this->alloc(), prefer_in_recvd_out_size, reuse); + //First detect overflow on smaller stored_size_types + if (limit_size > stored_size_type(-1)){ + boost::container::throw_length_error("get_next_capacity, allocator's max size reached"); + } + (clamp_by_stored_size_type)(prefer_in_recvd_out_size, stored_size_type()); + pointer const p = this->allocate(prefer_in_recvd_out_size); reuse = pointer(); return p; } @@ -513,13 +531,22 @@ struct vector_alloc_holder size_type &prefer_in_recvd_out_size, pointer &reuse) { - return this->alloc().allocation_command(command, limit_size, prefer_in_recvd_out_size, reuse); + //First detect overflow on smaller stored_size_types + if (limit_size > stored_size_type(-1)){ + boost::container::throw_length_error("get_next_capacity, allocator's max size reached"); + } + (clamp_by_stored_size_type)(prefer_in_recvd_out_size, stored_size_type()); + //Allocate memory + pointer p = this->alloc().allocation_command(command, limit_size, prefer_in_recvd_out_size, reuse); + //If after allocation prefer_in_recvd_out_size is not representable by stored_size_type, truncate it. + (clamp_by_stored_size_type)(prefer_in_recvd_out_size, stored_size_type()); + return p; } }; //!This struct deallocates and allocated memory -template <class Allocator> -struct vector_alloc_holder<Allocator, version_0> +template <class Allocator, class StoredSizeType> +struct vector_alloc_holder<Allocator, StoredSizeType, version_0> : public Allocator { private: @@ -530,13 +557,14 @@ struct vector_alloc_holder<Allocator, version_0> typedef typename allocator_traits_type::pointer pointer; typedef typename allocator_traits_type::size_type size_type; typedef typename allocator_traits_type::value_type value_type; + typedef StoredSizeType stored_size_type; - template <class OtherAllocator, class OtherAllocatorVersion> + template <class OtherAllocator, class OtherStoredSizeType, class OtherAllocatorVersion> friend struct vector_alloc_holder; //Constructor, does not throw vector_alloc_holder() - BOOST_NOEXCEPT_IF(container_detail::is_nothrow_default_constructible<Allocator>::value) + BOOST_NOEXCEPT_IF(dtl::is_nothrow_default_constructible<Allocator>::value) : Allocator(), m_size() {} @@ -548,7 +576,7 @@ struct vector_alloc_holder<Allocator, version_0> //Constructor, does not throw template<class AllocConvertible> - vector_alloc_holder(uninitialized_size_t, BOOST_FWD_REF(AllocConvertible) a, size_type initial_size) + vector_alloc_holder(vector_uninitialized_size_t, BOOST_FWD_REF(AllocConvertible) a, size_type initial_size) : Allocator(boost::forward<AllocConvertible>(a)) , m_size(initial_size) //Size is initialized here... { @@ -557,7 +585,7 @@ struct vector_alloc_holder<Allocator, version_0> } //Constructor, does not throw - vector_alloc_holder(uninitialized_size_t, size_type initial_size) + vector_alloc_holder(vector_uninitialized_size_t, size_type initial_size) : Allocator() , m_size(initial_size) //Size is initialized here... { @@ -573,8 +601,8 @@ struct vector_alloc_holder<Allocator, version_0> (this->alloc(), boost::movelib::to_raw_pointer(holder.start()), m_size, boost::movelib::to_raw_pointer(this->start())); } - template<class OtherAllocator, class OtherAllocatorVersion> - vector_alloc_holder(BOOST_RV_REF_BEG vector_alloc_holder<OtherAllocator, OtherAllocatorVersion> BOOST_RV_REF_END holder) + template<class OtherAllocator, class OtherStoredSizeType, class OtherAllocatorVersion> + vector_alloc_holder(BOOST_RV_REF_BEG vector_alloc_holder<OtherAllocator, OtherStoredSizeType, OtherAllocatorVersion> BOOST_RV_REF_END holder) : Allocator() , m_size(holder.m_size) //Initialize it to m_size as first_allocation can only succeed or abort { @@ -597,8 +625,8 @@ struct vector_alloc_holder<Allocator, version_0> this->priv_deep_swap(x); } - template<class OtherAllocator, class OtherAllocatorVersion> - void deep_swap(vector_alloc_holder<OtherAllocator, OtherAllocatorVersion> &x) + template<class OtherAllocator, class OtherStoredSizeType, class OtherAllocatorVersion> + void deep_swap(vector_alloc_holder<OtherAllocator, OtherStoredSizeType, OtherAllocatorVersion> &x) { if(this->m_size > OtherAllocator::internal_capacity || x.m_size > Allocator::internal_capacity){ throw_bad_alloc(); @@ -628,12 +656,12 @@ struct vector_alloc_holder<Allocator, version_0> BOOST_CONTAINER_FORCEINLINE pointer start() const BOOST_NOEXCEPT_OR_NOTHROW { return Allocator::internal_storage(); } BOOST_CONTAINER_FORCEINLINE size_type capacity() const BOOST_NOEXCEPT_OR_NOTHROW { return Allocator::internal_capacity; } - size_type m_size; + stored_size_type m_size; private: - template<class OtherAllocator, class OtherAllocatorVersion> - void priv_deep_swap(vector_alloc_holder<OtherAllocator, OtherAllocatorVersion> &x) + template<class OtherAllocator, class OtherStoredSizeType, class OtherAllocatorVersion> + void priv_deep_swap(vector_alloc_holder<OtherAllocator, OtherStoredSizeType, OtherAllocatorVersion> &x) { const size_type MaxTmpStorage = sizeof(value_type)*Allocator::internal_capacity; value_type *const first_this = boost::movelib::to_raw_pointer(this->start()); @@ -649,7 +677,34 @@ struct vector_alloc_holder<Allocator, version_0> } }; -} //namespace container_detail { +struct growth_factor_60; + +template<class T, class Default> +struct default_if_void +{ + typedef T type; +}; + +template<class Default> +struct default_if_void<void, Default> +{ + typedef Default type; +}; + +template<class Options, class AllocatorSizeType> +struct get_vector_opt +{ + typedef vector_opt< typename default_if_void<typename Options::growth_factor_type, growth_factor_60>::type + , typename default_if_void<typename Options::stored_size_type, AllocatorSizeType>::type + > type; +}; + +template<class AllocatorSizeType> +struct get_vector_opt<void, AllocatorSizeType> +{ + typedef vector_opt<growth_factor_60, AllocatorSizeType> type; +}; + #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED @@ -660,28 +715,32 @@ struct vector_alloc_holder<Allocator, version_0> //! //! \tparam T The type of object that is stored in the vector //! \tparam Allocator The allocator used for all internal memory management -template <class T, class Allocator BOOST_CONTAINER_DOCONLY(= new_allocator<T>) > +//! \tparam Options A type produced from \c boost::container::vector_options. +template <class T, class Allocator BOOST_CONTAINER_DOCONLY(= new_allocator<T>), class Options BOOST_CONTAINER_DOCONLY(= void) > class vector { #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED - struct value_less - { - typedef typename boost::container::allocator_traits<Allocator>::value_type value_type; - bool operator()(const value_type &a, const value_type &b) const - { return a < b; } - }; + typedef typename boost::container::allocator_traits<Allocator>::size_type alloc_size_type; + typedef typename get_vector_opt<Options, alloc_size_type>::type options_type; + typedef typename options_type::growth_factor_type growth_factor_type; + typedef typename options_type::stored_size_type stored_size_type; + typedef value_less<T> value_less_t; + + //If provided the stored_size option must specify a type that is equal or a type that is smaller. + BOOST_STATIC_ASSERT( (sizeof(stored_size_type) < sizeof(alloc_size_type) || + dtl::is_same<stored_size_type, alloc_size_type>::value) ); - typedef typename container_detail::version<Allocator>::type alloc_version; - typedef boost::container::container_detail::vector_alloc_holder<Allocator> alloc_holder_t; + typedef typename dtl::version<Allocator>::type alloc_version; + typedef boost::container::vector_alloc_holder<Allocator, stored_size_type> alloc_holder_t; alloc_holder_t m_holder; typedef allocator_traits<Allocator> allocator_traits_type; - template <class U, class UAllocator> + template <class U, class UAllocator, class UOptions> friend class vector; typedef typename allocator_traits_type::pointer pointer_impl; - typedef container_detail::vec_iterator<pointer_impl, false> iterator_impl; - typedef container_detail::vec_iterator<pointer_impl, true > const_iterator_impl; + typedef vec_iterator<pointer_impl, false> iterator_impl; + typedef vec_iterator<pointer_impl, true > const_iterator_impl; protected: static bool is_propagable_from(const Allocator &from_alloc, pointer_impl p, const Allocator &to_alloc, bool const propagate_allocator) @@ -716,7 +775,7 @@ class vector #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED private: BOOST_COPYABLE_AND_MOVABLE(vector) - typedef container_detail::vector_value_traits<Allocator> value_traits; + typedef vector_value_traits<Allocator> value_traits; typedef constant_iterator<T, difference_type> cvalue_iterator; protected: @@ -724,14 +783,13 @@ class vector BOOST_CONTAINER_FORCEINLINE void steal_resources(vector &x) { return this->m_holder.steal_resources(x.m_holder); } - struct initial_capacity_t{}; template<class AllocFwd> BOOST_CONTAINER_FORCEINLINE vector(initial_capacity_t, pointer initial_memory, size_type capacity, BOOST_FWD_REF(AllocFwd) a) - : m_holder(initial_memory, capacity, ::boost::forward<AllocFwd>(a)) + : m_holder(initial_capacity_t(), initial_memory, capacity, ::boost::forward<AllocFwd>(a)) {} BOOST_CONTAINER_FORCEINLINE vector(initial_capacity_t, pointer initial_memory, size_type capacity) - : m_holder(initial_memory, capacity) + : m_holder(initial_capacity_t(), initial_memory, capacity) {} #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED @@ -748,7 +806,7 @@ class vector //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Constant. - vector() BOOST_NOEXCEPT_IF(container_detail::is_nothrow_default_constructible<Allocator>::value) + vector() BOOST_NOEXCEPT_IF(dtl::is_nothrow_default_constructible<Allocator>::value) : m_holder() {} @@ -768,7 +826,7 @@ class vector //! //! <b>Complexity</b>: Linear to n. explicit vector(size_type n) - : m_holder(container_detail::uninitialized_size, n) + : m_holder(vector_uninitialized_size, n) { #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS this->num_alloc += n != 0; @@ -785,7 +843,7 @@ class vector //! //! <b>Complexity</b>: Linear to n. explicit vector(size_type n, const allocator_type &a) - : m_holder(container_detail::uninitialized_size, a, n) + : m_holder(vector_uninitialized_size, a, n) { #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS this->num_alloc += n != 0; @@ -804,7 +862,7 @@ class vector //! //! <b>Note</b>: Non-standard extension vector(size_type n, default_init_t) - : m_holder(container_detail::uninitialized_size, n) + : m_holder(vector_uninitialized_size, n) { #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS this->num_alloc += n != 0; @@ -823,7 +881,7 @@ class vector //! //! <b>Note</b>: Non-standard extension vector(size_type n, default_init_t, const allocator_type &a) - : m_holder(container_detail::uninitialized_size, a, n) + : m_holder(vector_uninitialized_size, a, n) { #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS this->num_alloc += n != 0; @@ -840,7 +898,7 @@ class vector //! //! <b>Complexity</b>: Linear to n. vector(size_type n, const T& value) - : m_holder(container_detail::uninitialized_size, n) + : m_holder(vector_uninitialized_size, n) { #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS this->num_alloc += n != 0; @@ -857,7 +915,7 @@ class vector //! //! <b>Complexity</b>: Linear to n. vector(size_type n, const T& value, const allocator_type& a) - : m_holder(container_detail::uninitialized_size, a, n) + : m_holder(vector_uninitialized_size, a, n) { #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS this->num_alloc += n != 0; @@ -875,9 +933,9 @@ class vector //! <b>Complexity</b>: Linear to the range [first, last). template <class InIt> vector(InIt first, InIt last - BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename container_detail::disable_if_c - < container_detail::is_convertible<InIt BOOST_MOVE_I size_type>::value - BOOST_MOVE_I container_detail::nat >::type * = 0) + BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_c + < dtl::is_convertible<InIt BOOST_MOVE_I size_type>::value + BOOST_MOVE_I dtl::nat >::type * = 0) ) : m_holder() { this->assign(first, last); } @@ -891,9 +949,9 @@ class vector //! <b>Complexity</b>: Linear to the range [first, last). template <class InIt> vector(InIt first, InIt last, const allocator_type& a - BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename container_detail::disable_if_c - < container_detail::is_convertible<InIt BOOST_MOVE_I size_type>::value - BOOST_MOVE_I container_detail::nat >::type * = 0) + BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_c + < dtl::is_convertible<InIt BOOST_MOVE_I size_type>::value + BOOST_MOVE_I dtl::nat >::type * = 0) ) : m_holder(a) { this->assign(first, last); } @@ -907,7 +965,7 @@ class vector //! //! <b>Complexity</b>: Linear to the elements x contains. vector(const vector &x) - : m_holder( container_detail::uninitialized_size + : m_holder( vector_uninitialized_size , allocator_traits_type::select_on_container_copy_construction(x.m_holder.alloc()) , x.size()) { @@ -953,8 +1011,8 @@ class vector //! <b>Note</b>: Non-standard extension to support static_vector template<class OtherAllocator> vector(BOOST_RV_REF_BEG vector<T, OtherAllocator> BOOST_RV_REF_END x - , typename container_detail::enable_if_c - < container_detail::is_version<OtherAllocator, 0>::value>::type * = 0 + , typename dtl::enable_if_c + < dtl::is_version<OtherAllocator, 0>::value>::type * = 0 ) : m_holder(boost::move(x.m_holder)) {} @@ -970,7 +1028,7 @@ class vector //! //! <b>Complexity</b>: Linear to the elements x contains. vector(const vector &x, const allocator_type &a) - : m_holder(container_detail::uninitialized_size, a, x.size()) + : m_holder(vector_uninitialized_size, a, x.size()) { #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS this->num_alloc += x.size() != 0; @@ -988,7 +1046,7 @@ class vector //! //! <b>Complexity</b>: Constant if a == x.get_allocator(), linear otherwise. vector(BOOST_RV_REF(vector) x, const allocator_type &a) - : m_holder( container_detail::uninitialized_size, a + : m_holder( vector_uninitialized_size, a , is_propagable_from(x.get_stored_allocator(), x.m_holder.start(), a, true) ? 0 : x.size() ) { @@ -1079,10 +1137,10 @@ class vector //! //! <b>Note</b>: Non-standard extension to support static_vector template<class OtherAllocator> - BOOST_CONTAINER_FORCEINLINE typename container_detail::enable_if_and + BOOST_CONTAINER_FORCEINLINE typename dtl::enable_if_and < vector& - , container_detail::is_version<OtherAllocator, 0> - , container_detail::is_different<OtherAllocator, allocator_type> + , dtl::is_version<OtherAllocator, 0> + , dtl::is_different<OtherAllocator, allocator_type> >::type operator=(BOOST_RV_REF_BEG vector<value_type, OtherAllocator> BOOST_RV_REF_END x) { @@ -1101,10 +1159,10 @@ class vector //! //! <b>Note</b>: Non-standard extension to support static_vector template<class OtherAllocator> - BOOST_CONTAINER_FORCEINLINE typename container_detail::enable_if_and + BOOST_CONTAINER_FORCEINLINE typename dtl::enable_if_and < vector& - , container_detail::is_version<OtherAllocator, 0> - , container_detail::is_different<OtherAllocator, allocator_type> + , dtl::is_version<OtherAllocator, 0> + , dtl::is_different<OtherAllocator, allocator_type> >::type operator=(const vector<value_type, OtherAllocator> &x) { @@ -1122,12 +1180,12 @@ class vector //! <b>Complexity</b>: Linear to n. template <class InIt> void assign(InIt first, InIt last - BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename container_detail::disable_if_or + BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_or < void - BOOST_MOVE_I container_detail::is_convertible<InIt BOOST_MOVE_I size_type> - BOOST_MOVE_I container_detail::and_ - < container_detail::is_different<alloc_version BOOST_MOVE_I version_0> - BOOST_MOVE_I container_detail::is_not_input_iterator<InIt> + BOOST_MOVE_I dtl::is_convertible<InIt BOOST_MOVE_I size_type> + BOOST_MOVE_I dtl::and_ + < dtl::is_different<alloc_version BOOST_MOVE_I version_0> + BOOST_MOVE_I dtl::is_not_input_iterator<InIt> > >::type * = 0) ) @@ -1171,11 +1229,11 @@ class vector //! <b>Complexity</b>: Linear to n. template <class FwdIt> void assign(FwdIt first, FwdIt last - BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename container_detail::disable_if_or + BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_or < void - BOOST_MOVE_I container_detail::is_same<alloc_version BOOST_MOVE_I version_0> - BOOST_MOVE_I container_detail::is_convertible<FwdIt BOOST_MOVE_I size_type> - BOOST_MOVE_I container_detail::is_input_iterator<FwdIt> + BOOST_MOVE_I dtl::is_same<alloc_version BOOST_MOVE_I version_0> + BOOST_MOVE_I dtl::is_convertible<FwdIt BOOST_MOVE_I size_type> + BOOST_MOVE_I dtl::is_input_iterator<FwdIt> >::type * = 0) ) { @@ -1194,7 +1252,7 @@ class vector pointer const old_p = this->m_holder.start(); if(old_p){ this->priv_destroy_all(); - allocator_traits_type::deallocate(this->m_holder.alloc(), old_p, old_capacity); + this->m_holder.deallocate(old_p, old_capacity); } this->m_holder.start(ret); this->m_holder.capacity(real_cap); @@ -1697,7 +1755,7 @@ class vector return *p; } else{ - typedef container_detail::insert_emplace_proxy<Allocator, T*, Args...> type; + typedef dtl::insert_emplace_proxy<Allocator, T*, Args...> type; return *this->priv_forward_range_insert_no_capacity (this->back_ptr(), 1, type(::boost::forward<Args>(args)...), alloc_version()); } @@ -1738,7 +1796,7 @@ class vector { BOOST_ASSERT(this->priv_in_range_or_end(position)); //Just call more general insert(pos, size, value) and return iterator - typedef container_detail::insert_emplace_proxy<Allocator, T*, Args...> type; + typedef dtl::insert_emplace_proxy<Allocator, T*, Args...> type; return this->priv_forward_range_insert( vector_iterator_get_ptr(position), 1 , type(::boost::forward<Args>(args)...)); } @@ -1757,7 +1815,7 @@ class vector return *p;\ }\ else{\ - typedef container_detail::insert_emplace_proxy_arg##N<Allocator, T* BOOST_MOVE_I##N BOOST_MOVE_TARG##N> type;\ + typedef dtl::insert_emplace_proxy_arg##N<Allocator, T* BOOST_MOVE_I##N BOOST_MOVE_TARG##N> type;\ return *this->priv_forward_range_insert_no_capacity\ ( this->back_ptr(), 1, type(BOOST_MOVE_FWD##N), alloc_version());\ }\ @@ -1779,7 +1837,7 @@ class vector iterator emplace(const_iterator pos BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ {\ BOOST_ASSERT(this->priv_in_range_or_end(pos));\ - typedef container_detail::insert_emplace_proxy_arg##N<Allocator, T* BOOST_MOVE_I##N BOOST_MOVE_TARG##N> type;\ + typedef dtl::insert_emplace_proxy_arg##N<Allocator, T* BOOST_MOVE_I##N BOOST_MOVE_TARG##N> type;\ return this->priv_forward_range_insert(vector_iterator_get_ptr(pos), 1, type(BOOST_MOVE_FWD##N));\ }\ // @@ -1845,7 +1903,7 @@ class vector iterator insert(const_iterator p, size_type n, const T& x) { BOOST_ASSERT(this->priv_in_range_or_end(p)); - container_detail::insert_n_copies_proxy<Allocator, T*> proxy(x); + dtl::insert_n_copies_proxy<Allocator, T*> proxy(x); return this->priv_forward_range_insert(vector_iterator_get_ptr(p), n, proxy); } @@ -1862,10 +1920,10 @@ class vector template <class InIt> iterator insert(const_iterator pos, InIt first, InIt last #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) - , typename container_detail::disable_if_or + , typename dtl::disable_if_or < void - , container_detail::is_convertible<InIt, size_type> - , container_detail::is_not_input_iterator<InIt> + , dtl::is_convertible<InIt, size_type> + , dtl::is_not_input_iterator<InIt> >::type * = 0 #endif ) @@ -1883,15 +1941,15 @@ class vector #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) template <class FwdIt> iterator insert(const_iterator pos, FwdIt first, FwdIt last - , typename container_detail::disable_if_or + , typename dtl::disable_if_or < void - , container_detail::is_convertible<FwdIt, size_type> - , container_detail::is_input_iterator<FwdIt> + , dtl::is_convertible<FwdIt, size_type> + , dtl::is_input_iterator<FwdIt> >::type * = 0 ) { BOOST_ASSERT(this->priv_in_range_or_end(pos)); - container_detail::insert_range_proxy<Allocator, FwdIt, T*> proxy(first); + dtl::insert_range_proxy<Allocator, FwdIt, T*> proxy(first); return this->priv_forward_range_insert(vector_iterator_get_ptr(pos), boost::container::iterator_distance(first, last), proxy); } #endif @@ -1916,10 +1974,10 @@ class vector iterator insert(const_iterator pos, size_type num, InIt first, InIt last) { BOOST_ASSERT(this->priv_in_range_or_end(pos)); - BOOST_ASSERT(container_detail::is_input_iterator<InIt>::value || + BOOST_ASSERT(dtl::is_input_iterator<InIt>::value || num == static_cast<size_type>(boost::container::iterator_distance(first, last))); (void)last; - container_detail::insert_range_proxy<Allocator, InIt, T*> proxy(first); + dtl::insert_range_proxy<Allocator, InIt, T*> proxy(first); return this->priv_forward_range_insert(vector_iterator_get_ptr(pos), num, proxy); } #endif @@ -1965,7 +2023,7 @@ class vector T *const beg_ptr = this->priv_raw_begin(); T *const new_end_ptr = ::boost::container::move(pos_ptr + 1, beg_ptr + this->m_holder.m_size, pos_ptr); //Move elements forward and destroy last - this->priv_destroy_last(pos_ptr == new_end_ptr); + this->priv_destroy_last(pos_ptr != new_end_ptr); return iterator(p); } @@ -1994,12 +2052,12 @@ class vector //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Constant. - void swap(vector& x) + BOOST_CONTAINER_FORCEINLINE void swap(vector& x) BOOST_NOEXCEPT_IF( ((allocator_traits_type::propagate_on_container_swap::value || allocator_traits_type::is_always_equal::value) && - !container_detail::is_version<Allocator, 0>::value)) + !dtl::is_version<Allocator, 0>::value)) { - this->priv_swap(x, container_detail::bool_<container_detail::is_version<Allocator, 0>::value>()); + this->priv_swap(x, dtl::bool_<dtl::is_version<Allocator, 0>::value>()); } #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED @@ -2012,11 +2070,11 @@ class vector //! //! <b>Note</b>: Non-standard extension to support static_vector template<class OtherAllocator> - void swap(vector<T, OtherAllocator> & x - , typename container_detail::enable_if_and + BOOST_CONTAINER_FORCEINLINE void swap(vector<T, OtherAllocator> & x + , typename dtl::enable_if_and < void - , container_detail::is_version<OtherAllocator, 0> - , container_detail::is_different<OtherAllocator, allocator_type> + , dtl::is_version<OtherAllocator, 0> + , dtl::is_different<OtherAllocator, allocator_type> >::type * = 0 ) { this->m_holder.deep_swap(x.m_holder); } @@ -2028,19 +2086,19 @@ class vector //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Linear to the number of elements in the container. - void clear() BOOST_NOEXCEPT_OR_NOTHROW + BOOST_CONTAINER_FORCEINLINE void clear() BOOST_NOEXCEPT_OR_NOTHROW { this->priv_destroy_all(); } //! <b>Effects</b>: Returns true if x and y are equal //! //! <b>Complexity</b>: Linear to the number of elements in the container. - friend bool operator==(const vector& x, const vector& y) + BOOST_CONTAINER_FORCEINLINE friend bool operator==(const vector& x, const vector& y) { return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin()); } //! <b>Effects</b>: Returns true if x and y are unequal //! //! <b>Complexity</b>: Linear to the number of elements in the container. - friend bool operator!=(const vector& x, const vector& y) + BOOST_CONTAINER_FORCEINLINE friend bool operator!=(const vector& x, const vector& y) { return !(x == y); } //! <b>Effects</b>: Returns true if x is less than y @@ -2060,25 +2118,25 @@ class vector //! <b>Effects</b>: Returns true if x is greater than y //! //! <b>Complexity</b>: Linear to the number of elements in the container. - friend bool operator>(const vector& x, const vector& y) + BOOST_CONTAINER_FORCEINLINE friend bool operator>(const vector& x, const vector& y) { return y < x; } //! <b>Effects</b>: Returns true if x is equal or less than y //! //! <b>Complexity</b>: Linear to the number of elements in the container. - friend bool operator<=(const vector& x, const vector& y) + BOOST_CONTAINER_FORCEINLINE friend bool operator<=(const vector& x, const vector& y) { return !(y < x); } //! <b>Effects</b>: Returns true if x is equal or greater than y //! //! <b>Complexity</b>: Linear to the number of elements in the container. - friend bool operator>=(const vector& x, const vector& y) + BOOST_CONTAINER_FORCEINLINE friend bool operator>=(const vector& x, const vector& y) { return !(x < y); } //! <b>Effects</b>: x.swap(y) //! //! <b>Complexity</b>: Constant. - friend void swap(vector& x, vector& y) + BOOST_CONTAINER_FORCEINLINE friend void swap(vector& x, vector& y) { x.swap(y); } #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED @@ -2099,27 +2157,51 @@ class vector //Absolutely experimental. This function might change, disappear or simply crash! template<class BiDirPosConstIt, class BiDirValueIt> - void insert_ordered_at(const size_type element_count, BiDirPosConstIt last_position_it, BiDirValueIt last_value_it) + BOOST_CONTAINER_FORCEINLINE void insert_ordered_at(const size_type element_count, BiDirPosConstIt last_position_it, BiDirValueIt last_value_it) { - typedef container_detail::vector_insert_ordered_cursor<BiDirPosConstIt, BiDirValueIt> inserter_t; + typedef vector_insert_ordered_cursor<BiDirPosConstIt, BiDirValueIt> inserter_t; return this->priv_insert_ordered_at(element_count, inserter_t(last_position_it, last_value_it)); } - template<class BidirIt> - void merge(BidirIt first, BidirIt last) - { this->merge(first, last, value_less()); } + template<class InputIt> + BOOST_CONTAINER_FORCEINLINE void merge(InputIt first, InputIt last) + { this->merge(first, last, value_less_t()); } - template<class BidirIt, class Compare> - void merge(BidirIt first, BidirIt last, Compare comp) - { this->priv_merge(container_detail::false_type(), first, last, comp); } + template<class InputIt, class Compare> + BOOST_CONTAINER_FORCEINLINE void merge(InputIt first, InputIt last, Compare comp) + { + size_type const s = this->size(); + size_type const c = this->capacity(); + size_type n = 0; + size_type const free_cap = c - s; + //If not input iterator and new elements don't fit in the remaining capacity, merge in new buffer + if(!dtl::is_input_iterator<InputIt>::value && + free_cap < (n = static_cast<size_type>(boost::container::iterator_distance(first, last)))){ + this->priv_merge_in_new_buffer(first, n, comp, alloc_version()); + } + else{ + iterator pos(this->insert(this->cend(), first, last)); + T *const raw_beg = this->priv_raw_begin(); + T *const raw_end = this->priv_raw_end(); + T *const raw_pos = raw_beg + s; + boost::movelib::adaptive_merge(raw_beg, raw_pos, raw_end, comp, raw_end, free_cap - n); + } + } - template<class BidirIt> - void merge_unique(BidirIt first, BidirIt last) - { this->priv_merge(container_detail::true_type(), first, last, value_less()); } + template<class InputIt> + BOOST_CONTAINER_FORCEINLINE void merge_unique(InputIt first, InputIt last) + { this->merge_unique(first, last, value_less_t()); } - template<class BidirIt, class Compare> - void merge_unique(BidirIt first, BidirIt last, Compare comp) - { this->priv_merge(container_detail::true_type(), first, last, comp); } + template<class InputIt, class Compare> + BOOST_CONTAINER_FORCEINLINE void merge_unique(InputIt first, InputIt last, Compare comp) + { + size_type const s = this->size(); + this->priv_set_difference_back(first, last, comp); + T *const raw_beg = this->priv_raw_begin(); + T *const raw_end = this->priv_raw_end(); + T *raw_pos = raw_beg + s; + boost::movelib::adaptive_merge(raw_beg, raw_pos, raw_end, comp, raw_end, this->capacity() - this->size()); + } private: template<class PositionValue> @@ -2179,43 +2261,48 @@ class vector } } - template<class UniqueBool, class BidirIt, class Compare> - void priv_merge(UniqueBool, BidirIt first, BidirIt last, Compare comp) + template<class InputIt, class Compare> + void priv_set_difference_back(InputIt first1, InputIt last1, Compare comp) { - size_type const n = static_cast<size_type>(boost::container::iterator_distance(first, last)); - size_type const s = this->size(); - if(BOOST_LIKELY(s)){ - size_type const c = this->capacity(); - size_type const free_c = (c - s); - //Use a new buffer if current one is too small for new elements - if(free_c < n){ - this->priv_merge_in_new_buffer(UniqueBool(), first, n, comp, alloc_version()); + T * old_first2 = this->priv_raw_begin(); + T * first2 = old_first2; + T * last2 = this->priv_raw_end(); + + while (first1 != last1) { + if (first2 == last2){ + this->insert(this->cend(), first1, last1); + return; } - else{ - T *raw_pos = boost::movelib::iterator_to_raw_pointer(this->insert(this->cend(), first, last)); - T *raw_beg = this->priv_raw_begin(); - T *raw_end = this->priv_raw_end(); - boost::movelib::adaptive_merge(raw_beg, raw_pos, raw_end, comp, raw_end, free_c - n); - if(UniqueBool::value){ - size_type const count = - static_cast<size_type>(raw_end - boost::movelib::unique(raw_beg, raw_end, boost::movelib::negate<Compare>(comp))); - this->priv_destroy_last_n(count); + + if (comp(*first1, *first2)) { + this->emplace_back(*first1); + //Reallocation happened, update range + T * const raw_begin = this->priv_raw_begin(); + if(old_first2 != raw_begin){ + first2 = raw_begin + (first2 - old_first2); + last2 = first2 + (last2 - old_first2); + old_first2 = raw_begin; } + + ++first1; + } + else { + if (!comp(*first2, *first1)) { + ++first1; + } + ++first2; } - } - else{ - this->insert(this->cend(), n, first, last); } } - template<class UniqueBool, class FwdIt, class Compare> - void priv_merge_in_new_buffer(UniqueBool, FwdIt, size_type, Compare, version_0) + template<class FwdIt, class Compare> + BOOST_CONTAINER_FORCEINLINE void priv_merge_in_new_buffer(FwdIt, size_type, Compare, version_0) { throw_bad_alloc(); } - template<class UniqueBool, class FwdIt, class Compare, class Version> - void priv_merge_in_new_buffer(UniqueBool, FwdIt first, size_type n, Compare comp, Version) + template<class FwdIt, class Compare, class Version> + void priv_merge_in_new_buffer(FwdIt first, size_type n, Compare comp, Version) { size_type const new_size = this->size() + n; size_type new_cap = new_size; @@ -2249,11 +2336,6 @@ class vector --n; ++d_first; } - else if(UniqueBool::value && !comp(*pbeg, *first)){ - ++first; - --n; - --added; - } else{ allocator_traits_type::construct( this->m_holder.alloc(), d_first, boost::move(*pbeg) ); new_values_destroyer.increment_size(1u); @@ -2266,7 +2348,7 @@ class vector pointer const old_p = this->m_holder.start(); size_type const old_cap = this->m_holder.capacity(); boost::container::destroy_alloc_n(a, boost::movelib::to_raw_pointer(old_p), old_size); - allocator_traits_type::deallocate(a, old_p, old_cap); + this->m_holder.deallocate(old_p, old_cap); this->m_holder.m_size = old_size + added; this->m_holder.start(new_storage); this->m_holder.capacity(new_cap); @@ -2274,10 +2356,10 @@ class vector new_values_destroyer.release(); } - bool room_enough() const + BOOST_CONTAINER_FORCEINLINE bool room_enough() const { return this->m_holder.m_size < this->m_holder.capacity(); } - pointer back_ptr() const + BOOST_CONTAINER_FORCEINLINE pointer back_ptr() const { return this->m_holder.start() + this->m_holder.m_size; } size_type priv_index_of(pointer p) const @@ -2289,10 +2371,10 @@ class vector template<class OtherAllocator> void priv_move_assign(BOOST_RV_REF_BEG vector<T, OtherAllocator> BOOST_RV_REF_END x - , typename container_detail::enable_if_c - < container_detail::is_version<OtherAllocator, 0>::value >::type * = 0) + , typename dtl::enable_if_c + < dtl::is_version<OtherAllocator, 0>::value >::type * = 0) { - if(!container_detail::is_same<OtherAllocator, allocator_type>::value && + if(!dtl::is_same<OtherAllocator, allocator_type>::value && this->capacity() < x.size()){ throw_bad_alloc(); } @@ -2306,10 +2388,10 @@ class vector template<class OtherAllocator> void priv_move_assign(BOOST_RV_REF_BEG vector<T, OtherAllocator> BOOST_RV_REF_END x - , typename container_detail::disable_if_or + , typename dtl::disable_if_or < void - , container_detail::is_version<OtherAllocator, 0> - , container_detail::is_different<OtherAllocator, allocator_type> + , dtl::is_version<OtherAllocator, 0> + , dtl::is_different<OtherAllocator, allocator_type> >::type * = 0) { //for move assignment, no aliasing (&x != this) is assummed. @@ -2331,7 +2413,7 @@ class vector } else if(is_propagable_from_x){ this->clear(); - allocator_traits_type::deallocate(this->m_holder.alloc(), this->m_holder.m_start, this->m_holder.m_capacity); + this->m_holder.deallocate(this->m_holder.m_start, this->m_holder.m_capacity); this->m_holder.steal_resources(x.m_holder); } //Else do a one by one move @@ -2341,15 +2423,15 @@ class vector ); } //Move allocator if needed - container_detail::move_alloc(this_alloc, x_alloc, container_detail::bool_<propagate_alloc>()); + dtl::move_alloc(this_alloc, x_alloc, dtl::bool_<propagate_alloc>()); } template<class OtherAllocator> void priv_copy_assign(const vector<T, OtherAllocator> &x - , typename container_detail::enable_if_c - < container_detail::is_version<OtherAllocator, 0>::value >::type * = 0) + , typename dtl::enable_if_c + < dtl::is_version<OtherAllocator, 0>::value >::type * = 0) { - if(!container_detail::is_same<OtherAllocator, allocator_type>::value && + if(!dtl::is_same<OtherAllocator, allocator_type>::value && this->capacity() < x.size()){ throw_bad_alloc(); } @@ -2362,31 +2444,31 @@ class vector } template<class OtherAllocator> - typename container_detail::disable_if_or + typename dtl::disable_if_or < void - , container_detail::is_version<OtherAllocator, 0> - , container_detail::is_different<OtherAllocator, allocator_type> + , dtl::is_version<OtherAllocator, 0> + , dtl::is_different<OtherAllocator, allocator_type> >::type priv_copy_assign(const vector<T, OtherAllocator> &x) { allocator_type &this_alloc = this->m_holder.alloc(); const allocator_type &x_alloc = x.m_holder.alloc(); - container_detail::bool_<allocator_traits_type:: + dtl::bool_<allocator_traits_type:: propagate_on_container_copy_assignment::value> flag; if(flag && this_alloc != x_alloc){ this->clear(); this->shrink_to_fit(); } - container_detail::assign_alloc(this_alloc, x_alloc, flag); + dtl::assign_alloc(this_alloc, x_alloc, flag); this->assign( x.priv_raw_begin(), x.priv_raw_end() ); } template<class Vector> //Template it to avoid it in explicit instantiations - void priv_swap(Vector &x, container_detail::true_type) //version_0 + void priv_swap(Vector &x, dtl::true_type) //version_0 { this->m_holder.deep_swap(x.m_holder); } template<class Vector> //Template it to avoid it in explicit instantiations - void priv_swap(Vector &x, container_detail::false_type) //version_N + void priv_swap(Vector &x, dtl::false_type) //version_N { const bool propagate_alloc = allocator_traits_type::propagate_on_container_swap::value; if(are_swap_propagable( this->get_stored_allocator(), this->m_holder.start() @@ -2413,15 +2495,15 @@ class vector big.erase(big.nth(common_elements), big.cend()); } //And now swap the allocator - container_detail::swap_alloc(this->m_holder.alloc(), x.m_holder.alloc(), container_detail::bool_<propagate_alloc>()); + dtl::swap_alloc(this->m_holder.alloc(), x.m_holder.alloc(), dtl::bool_<propagate_alloc>()); } void priv_reserve_no_capacity(size_type, version_0) { throw_bad_alloc(); } - container_detail::insert_range_proxy<Allocator, boost::move_iterator<T*>, T*> priv_dummy_empty_proxy() + dtl::insert_range_proxy<Allocator, boost::move_iterator<T*>, T*> priv_dummy_empty_proxy() { - return container_detail::insert_range_proxy<Allocator, boost::move_iterator<T*>, T*> + return dtl::insert_range_proxy<Allocator, boost::move_iterator<T*>, T*> (::boost::make_move_iterator((T *)0)); } @@ -2429,7 +2511,7 @@ class vector { //There is not enough memory, allocate a new buffer //Pass the hint so that allocators can take advantage of this. - pointer const p = allocator_traits_type::allocate(this->m_holder.alloc(), new_cap, this->m_holder.m_start); + pointer const p = this->m_holder.allocate(new_cap); //We will reuse insert code, so create a dummy input iterator this->priv_forward_range_insert_new_allocation ( boost::movelib::to_raw_pointer(p), new_cap, this->priv_raw_end(), 0, this->priv_dummy_empty_proxy()); @@ -2475,7 +2557,8 @@ class vector void priv_destroy_last(const bool moved = false) BOOST_NOEXCEPT_OR_NOTHROW { (void)moved; - if(!(value_traits::trivial_dctr || (value_traits::trivial_dctr_after_move && moved))){ + const bool skip_destructor = value_traits::trivial_dctr || (value_traits::trivial_dctr_after_move && moved); + if(!skip_destructor){ value_type* const p = this->priv_raw_end() - 1; allocator_traits_type::destroy(this->get_stored_allocator(), p); } @@ -2512,14 +2595,14 @@ class vector { BOOST_ASSERT(this->priv_in_range_or_end(p)); return this->priv_forward_range_insert - ( vector_iterator_get_ptr(p), 1, container_detail::get_insert_value_proxy<T*, Allocator>(::boost::forward<U>(x))); + ( vector_iterator_get_ptr(p), 1, dtl::get_insert_value_proxy<T*, Allocator>(::boost::forward<U>(x))); } - container_detail::insert_copy_proxy<Allocator, T*> priv_single_insert_proxy(const T &x) - { return container_detail::insert_copy_proxy<Allocator, T*> (x); } + dtl::insert_copy_proxy<Allocator, T*> priv_single_insert_proxy(const T &x) + { return dtl::insert_copy_proxy<Allocator, T*> (x); } - container_detail::insert_move_proxy<Allocator, T*> priv_single_insert_proxy(BOOST_RV_REF(T) x) - { return container_detail::insert_move_proxy<Allocator, T*> (x); } + dtl::insert_move_proxy<Allocator, T*> priv_single_insert_proxy(BOOST_RV_REF(T) x) + { return dtl::insert_move_proxy<Allocator, T*> (x); } template <class U> void priv_push_back(BOOST_FWD_REF(U) u) @@ -2537,14 +2620,14 @@ class vector } } - container_detail::insert_n_copies_proxy<Allocator, T*> priv_resize_proxy(const T &x) - { return container_detail::insert_n_copies_proxy<Allocator, T*>(x); } + BOOST_CONTAINER_FORCEINLINE dtl::insert_n_copies_proxy<Allocator, T*> priv_resize_proxy(const T &x) + { return dtl::insert_n_copies_proxy<Allocator, T*>(x); } - container_detail::insert_default_initialized_n_proxy<Allocator, T*> priv_resize_proxy(default_init_t) - { return container_detail::insert_default_initialized_n_proxy<Allocator, T*>(); } + BOOST_CONTAINER_FORCEINLINE dtl::insert_default_initialized_n_proxy<Allocator, T*> priv_resize_proxy(default_init_t) + { return dtl::insert_default_initialized_n_proxy<Allocator, T*>(); } - container_detail::insert_value_initialized_n_proxy<Allocator, T*> priv_resize_proxy(value_init_t) - { return container_detail::insert_value_initialized_n_proxy<Allocator, T*>(); } + BOOST_CONTAINER_FORCEINLINE dtl::insert_value_initialized_n_proxy<Allocator, T*> priv_resize_proxy(value_init_t) + { return dtl::insert_value_initialized_n_proxy<Allocator, T*>(); } template <class U> void priv_resize(size_type new_size, const U& u) @@ -2560,7 +2643,7 @@ class vector } } - void priv_shrink_to_fit(version_0) BOOST_NOEXCEPT_OR_NOTHROW + BOOST_CONTAINER_FORCEINLINE void priv_shrink_to_fit(version_0) BOOST_NOEXCEPT_OR_NOTHROW {} void priv_shrink_to_fit(version_1) @@ -2569,14 +2652,14 @@ class vector if(cp){ const size_type sz = this->size(); if(!sz){ - allocator_traits_type::deallocate(this->m_holder.alloc(), this->m_holder.m_start, cp); + this->m_holder.deallocate(this->m_holder.m_start, cp); this->m_holder.m_start = pointer(); this->m_holder.m_capacity = 0; } else if(sz < cp){ //Allocate a new buffer. //Pass the hint so that allocators can take advantage of this. - pointer const p = allocator_traits_type::allocate(this->m_holder.alloc(), sz, this->m_holder.m_start); + pointer const p = this->m_holder.allocate(sz); //We will reuse insert code, so create a dummy input iterator #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS @@ -2595,7 +2678,7 @@ class vector if(cp){ const size_type sz = this->size(); if(!sz){ - allocator_traits_type::deallocate(this->m_holder.alloc(), this->m_holder.m_start, cp); + this->m_holder.deallocate(this->m_holder.m_start, cp); this->m_holder.m_start = pointer(); this->m_holder.m_capacity = 0; } @@ -2629,10 +2712,9 @@ class vector const size_type n_pos = pos - this->m_holder.start(); T *const raw_pos = boost::movelib::to_raw_pointer(pos); - const size_type new_cap = this->m_holder.next_capacity(n); + const size_type new_cap = this->m_holder.template next_capacity<growth_factor_type>(n); //Pass the hint so that allocators can take advantage of this. - T * const new_buf = boost::movelib::to_raw_pointer - (allocator_traits_type::allocate(this->m_holder.alloc(), new_cap, this->m_holder.m_start)); + T * const new_buf = boost::movelib::to_raw_pointer(this->m_holder.allocate(new_cap)); #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS ++this->num_alloc; #endif @@ -2651,7 +2733,7 @@ class vector //There is not enough memory, allocate a new //buffer or expand the old one. - size_type real_cap = this->m_holder.next_capacity(n); + size_type real_cap = this->m_holder.template next_capacity<growth_factor_type>(n); pointer reuse(this->m_holder.start()); pointer const ret (this->m_holder.allocation_command (allocate_new | expand_fwd | expand_bwd, this->m_holder.m_size + n, real_cap, reuse)); @@ -2725,7 +2807,7 @@ class vector } template <class InsertionProxy, class AllocVersion> - iterator priv_forward_range_insert_at_end + BOOST_CONTAINER_FORCEINLINE iterator priv_forward_range_insert_at_end (const size_type n, const InsertionProxy insert_range_proxy, AllocVersion) { return this->priv_forward_range_insert(this->back_ptr(), n, insert_range_proxy); @@ -2909,10 +2991,10 @@ class vector //If there is allocated memory, destroy and deallocate if(!value_traits::trivial_dctr_after_move) boost::container::destroy_alloc_n(this->get_stored_allocator(), old_buffer, this->m_holder.m_size); - allocator_traits_type::deallocate(this->m_holder.alloc(), this->m_holder.start(), this->m_holder.capacity()); + this->m_holder.deallocate(this->m_holder.start(), this->m_holder.capacity()); } this->m_holder.start(new_start); - this->m_holder.m_size = new_finish - new_start; + this->m_holder.m_size = size_type(new_finish - new_start); this->m_holder.capacity(new_cap); //All construction successful, disable rollbacks new_values_destroyer.release(); @@ -3248,12 +3330,12 @@ class vector } } - bool priv_in_range(const_iterator pos) const + BOOST_CONTAINER_FORCEINLINE 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 + BOOST_CONTAINER_FORCEINLINE bool priv_in_range_or_end(const_iterator pos) const { return (this->begin() <= pos) && (pos <= this->end()); } |