diff options
Diffstat (limited to 'boost/container')
| -rw-r--r-- | boost/container/adaptive_pool.hpp | 6 | ||||
| -rw-r--r-- | boost/container/allocator_traits.hpp | 73 | ||||
| -rw-r--r-- | boost/container/deque.hpp | 28 | ||||
| -rw-r--r-- | boost/container/detail/copy_move_algo.hpp | 71 | ||||
| -rw-r--r-- | boost/container/detail/flat_tree.hpp | 98 | ||||
| -rw-r--r-- | boost/container/detail/iterator.hpp | 1 | ||||
| -rw-r--r-- | boost/container/detail/iterators.hpp | 12 | ||||
| -rw-r--r-- | boost/container/detail/mpl.hpp | 175 | ||||
| -rw-r--r-- | boost/container/detail/node_alloc_holder.hpp | 108 | ||||
| -rw-r--r-- | boost/container/detail/pair.hpp | 79 | ||||
| -rw-r--r-- | boost/container/detail/std_fwd.hpp | 6 | ||||
| -rw-r--r-- | boost/container/detail/tree.hpp | 91 | ||||
| -rw-r--r-- | boost/container/detail/type_traits.hpp | 1 | ||||
| -rw-r--r-- | boost/container/list.hpp | 4 | ||||
| -rw-r--r-- | boost/container/node_allocator.hpp | 6 | ||||
| -rw-r--r-- | boost/container/scoped_allocator.hpp | 52 | ||||
| -rw-r--r-- | boost/container/slist.hpp | 4 | ||||
| -rw-r--r-- | boost/container/small_vector.hpp | 12 | ||||
| -rw-r--r-- | boost/container/stable_vector.hpp | 81 | ||||
| -rw-r--r-- | boost/container/string.hpp | 57 | ||||
| -rw-r--r-- | boost/container/vector.hpp | 471 |
21 files changed, 716 insertions, 720 deletions
diff --git a/boost/container/adaptive_pool.hpp b/boost/container/adaptive_pool.hpp index 1f6b6667e9..59ba37bc93 100644 --- a/boost/container/adaptive_pool.hpp +++ b/boost/container/adaptive_pool.hpp @@ -83,9 +83,9 @@ class adaptive_pool typedef T * pointer; typedef const T * const_pointer; typedef typename ::boost::container:: - container_detail::unvoid<T>::type & reference; - typedef const typename ::boost::container:: - container_detail::unvoid<T>::type & const_reference; + container_detail::unvoid_ref<T>::type reference; + typedef typename ::boost::container:: + container_detail::unvoid_ref<const T>::type const_reference; typedef std::size_t size_type; typedef std::ptrdiff_t difference_type; diff --git a/boost/container/allocator_traits.hpp b/boost/container/allocator_traits.hpp index cdaf2eacf0..2c7900ea72 100644 --- a/boost/container/allocator_traits.hpp +++ b/boost/container/allocator_traits.hpp @@ -96,6 +96,10 @@ template<class T> struct is_std_allocator< std::allocator<T> > { static const bool value = true; }; +template<class Allocator> +struct is_not_std_allocator +{ static const bool value = !is_std_allocator<Allocator>::value; }; + BOOST_INTRUSIVE_INSTANTIATE_DEFAULT_TYPE_TMPLT(pointer) BOOST_INTRUSIVE_INSTANTIATE_EVAL_DEFAULT_TYPE_TMPLT(const_pointer) BOOST_INTRUSIVE_INSTANTIATE_DEFAULT_TYPE_TMPLT(reference) @@ -195,11 +199,11 @@ struct allocator_traits const_pointer; //reference typedef BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_DEFAULT(boost::container::container_detail::, Allocator, - reference, typename container_detail::unvoid<value_type>::type&) + reference, typename container_detail::unvoid_ref<value_type>::type) reference; //const_reference typedef BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_DEFAULT(boost::container::container_detail::, Allocator, - const_reference, const typename container_detail::unvoid<value_type>::type&) + const_reference, typename container_detail::unvoid_ref<const value_type>::type) const_reference; //void_pointer typedef BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_EVAL_DEFAULT(boost::container::container_detail::, Allocator, @@ -340,7 +344,12 @@ struct allocator_traits template <class T, class ...Args> static void construct(Allocator & a, T* p, BOOST_FWD_REF(Args)... args) { - container_detail::bool_<container_detail::is_std_allocator<Allocator>::value> flag; + static const bool value = ::boost::move_detail::and_ + < container_detail::is_not_std_allocator<Allocator> + , boost::container::container_detail::has_member_function_callable_with_construct + < Allocator, T*, Args... > + >::value; + container_detail::bool_<value> flag; allocator_traits::priv_construct(flag, a, p, ::boost::forward<Args>(args)...); } #endif @@ -391,25 +400,11 @@ struct allocator_traits #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) template<class T, class ...Args> - static void priv_construct(container_detail::false_type, Allocator &a, T *p, BOOST_FWD_REF(Args) ...args) - { - const bool value = boost::container::container_detail:: - has_member_function_callable_with_construct - < Allocator, T*, Args... >::value; - container_detail::bool_<value> flag; - (priv_construct_dispatch_next)(flag, a, p, ::boost::forward<Args>(args)...); - } - - template<class T, class ...Args> static void priv_construct(container_detail::true_type, Allocator &a, T *p, BOOST_FWD_REF(Args) ...args) - { (priv_construct_dispatch_next)(container_detail::false_type(), a, p, ::boost::forward<Args>(args)...); } - - template<class T, class ...Args> - static void priv_construct_dispatch_next(container_detail::true_type, Allocator &a, T *p, BOOST_FWD_REF(Args) ...args) { a.construct( p, ::boost::forward<Args>(args)...); } template<class T, class ...Args> - static void priv_construct_dispatch_next(container_detail::false_type, Allocator &, T *p, BOOST_FWD_REF(Args) ...args) + static void priv_construct(container_detail::false_type, Allocator &, T *p, BOOST_FWD_REF(Args) ...args) { ::new((void*)p, boost_container_new_t()) T(::boost::forward<Args>(args)...); } #else // #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) public: @@ -418,54 +413,38 @@ struct allocator_traits template<class T BOOST_MOVE_I##N BOOST_MOVE_CLASS##N >\ static void construct(Allocator &a, T *p BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ {\ - container_detail::bool_<container_detail::is_std_allocator<Allocator>::value> flag;\ + static const bool value = ::boost::move_detail::and_ \ + < container_detail::is_not_std_allocator<Allocator> \ + , boost::container::container_detail::has_member_function_callable_with_construct \ + < Allocator, T* BOOST_MOVE_I##N BOOST_MOVE_FWD_T##N > \ + >::value; \ + container_detail::bool_<value> flag;\ (priv_construct)(flag, a, p BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ }\ // - BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_ALLOCATOR_TRAITS_CONSTRUCT_IMPL) + BOOST_MOVE_ITERATE_0TO8(BOOST_CONTAINER_ALLOCATOR_TRAITS_CONSTRUCT_IMPL) #undef BOOST_CONTAINER_ALLOCATOR_TRAITS_CONSTRUCT_IMPL private: - - ////////////////// + ///////////////////////////////// // priv_construct - ////////////////// + ///////////////////////////////// #define BOOST_CONTAINER_ALLOCATOR_TRAITS_PRIV_CONSTRUCT_IMPL(N) \ template<class T BOOST_MOVE_I##N BOOST_MOVE_CLASS##N >\ - static void priv_construct(container_detail::false_type, Allocator &a, T *p BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ - {\ - const bool value = boost::container::container_detail::has_member_function_callable_with_construct\ - < Allocator, T* BOOST_MOVE_I##N BOOST_MOVE_FWD_T##N>::value;\ - container_detail::bool_<value> flag;\ - (priv_construct_dispatch_next)(flag, a, p BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ - }\ - \ - template<class T BOOST_MOVE_I##N BOOST_MOVE_CLASS##N >\ static void priv_construct(container_detail::true_type, Allocator &a, T *p BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ - { (priv_construct_dispatch_next)(container_detail::false_type(), a, p BOOST_MOVE_I##N BOOST_MOVE_FWD##N); }\ - // - BOOST_MOVE_ITERATE_0TO8(BOOST_CONTAINER_ALLOCATOR_TRAITS_PRIV_CONSTRUCT_IMPL) - #undef BOOST_CONTAINER_ALLOCATOR_TRAITS_PRIV_CONSTRUCT_IMPL - - ///////////////////////////////// - // priv_construct_dispatch_next - ///////////////////////////////// - #define BOOST_CONTAINER_ALLOCATOR_TRAITS_PRIV_CONSTRUCT_DISPATCH_NEXT_IMPL(N) \ - template<class T BOOST_MOVE_I##N BOOST_MOVE_CLASS##N >\ - static void priv_construct_dispatch_next(container_detail::true_type, Allocator &a, T *p BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ { a.construct( p BOOST_MOVE_I##N BOOST_MOVE_FWD##N ); }\ \ template<class T BOOST_MOVE_I##N BOOST_MOVE_CLASS##N >\ - static void priv_construct_dispatch_next(container_detail::false_type, Allocator &, T *p BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ + static void priv_construct(container_detail::false_type, Allocator &, T *p BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ { ::new((void*)p, boost_container_new_t()) T(BOOST_MOVE_FWD##N); }\ // - BOOST_MOVE_ITERATE_0TO8(BOOST_CONTAINER_ALLOCATOR_TRAITS_PRIV_CONSTRUCT_DISPATCH_NEXT_IMPL) - #undef BOOST_CONTAINER_ALLOCATOR_TRAITS_PRIV_CONSTRUCT_DISPATCH_NEXT_IMPL + BOOST_MOVE_ITERATE_0TO8(BOOST_CONTAINER_ALLOCATOR_TRAITS_PRIV_CONSTRUCT_IMPL) + #undef BOOST_CONTAINER_ALLOCATOR_TRAITS_PRIV_CONSTRUCT_IMPL #endif // #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) template<class T> - static void priv_construct_dispatch_next(container_detail::false_type, Allocator &, T *p, const ::boost::container::default_init_t&) + static void priv_construct(container_detail::false_type, Allocator &, T *p, const ::boost::container::default_init_t&) { ::new((void*)p) T; } static bool priv_storage_is_unpropagable(container_detail::true_type, const Allocator &a, pointer p) diff --git a/boost/container/deque.hpp b/boost/container/deque.hpp index eb372a430a..bdfecc1212 100644 --- a/boost/container/deque.hpp +++ b/boost/container/deque.hpp @@ -835,9 +835,10 @@ class deque : protected deque_base<Allocator> template <class InIt> void assign(InIt first, InIt last #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) - , typename container_detail::enable_if_c - < !container_detail::is_convertible<InIt, size_type>::value - && container_detail::is_input_iterator<InIt>::value + , typename container_detail::disable_if_or + < void + , container_detail::is_convertible<InIt, size_type> + , container_detail::is_not_input_iterator<InIt> >::type * = 0 #endif ) @@ -857,9 +858,10 @@ class deque : protected deque_base<Allocator> #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) template <class FwdIt> void assign(FwdIt first, FwdIt last - , typename container_detail::enable_if_c - < !container_detail::is_convertible<FwdIt, size_type>::value - && !container_detail::is_input_iterator<FwdIt>::value + , typename container_detail::disable_if_or + < void + , container_detail::is_convertible<FwdIt, size_type> + , container_detail::is_input_iterator<FwdIt> >::type * = 0 ) { @@ -1509,9 +1511,10 @@ class deque : protected deque_base<Allocator> template <class InIt> iterator insert(const_iterator pos, InIt first, InIt last #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) - , typename container_detail::enable_if_c - < !container_detail::is_convertible<InIt, size_type>::value - && container_detail::is_input_iterator<InIt>::value + , typename container_detail::disable_if_or + < void + , container_detail::is_convertible<InIt, size_type> + , container_detail::is_not_input_iterator<InIt> >::type * = 0 #endif ) @@ -1545,9 +1548,10 @@ class deque : protected deque_base<Allocator> template <class FwdIt> iterator insert(const_iterator p, FwdIt first, FwdIt last #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) - , typename container_detail::enable_if_c - < !container_detail::is_convertible<FwdIt, size_type>::value - && !container_detail::is_input_iterator<FwdIt>::value + , typename container_detail::disable_if_or + < void + , container_detail::is_convertible<FwdIt, size_type> + , container_detail::is_input_iterator<FwdIt> >::type * = 0 #endif ) diff --git a/boost/container/detail/copy_move_algo.hpp b/boost/container/detail/copy_move_algo.hpp index 79cbde80a9..23fa730838 100644 --- a/boost/container/detail/copy_move_algo.hpp +++ b/boost/container/detail/copy_move_algo.hpp @@ -123,48 +123,49 @@ struct are_elements_contiguous< ::boost::interprocess::offset_ptr<PointedType, D template <typename I, typename O> struct are_contiguous_and_same -{ - static const bool is_same_io = - is_same< typename remove_const< typename ::boost::container::iterator_traits<I>::value_type >::type - , typename ::boost::container::iterator_traits<O>::value_type - >::value; - static const bool value = is_same_io && - are_elements_contiguous<I>::value && - are_elements_contiguous<O>::value; -}; + : boost::move_detail::and_ + < are_elements_contiguous<I> + , are_elements_contiguous<O> + , is_same< typename remove_const< typename ::boost::container::iterator_traits<I>::value_type >::type + , typename ::boost::container::iterator_traits<O>::value_type + > + > +{}; template <typename I, typename O> struct is_memtransfer_copy_assignable -{ - static const bool value = are_contiguous_and_same<I, O>::value && - container_detail::is_trivially_copy_assignable< typename ::boost::container::iterator_traits<I>::value_type >::value; -}; + : boost::move_detail::and_ + < are_contiguous_and_same<I, O> + , container_detail::is_trivially_copy_assignable< typename ::boost::container::iterator_traits<I>::value_type > + > +{}; template <typename I, typename O> struct is_memtransfer_copy_constructible -{ - static const bool value = are_contiguous_and_same<I, O>::value && - container_detail::is_trivially_copy_constructible< typename ::boost::container::iterator_traits<I>::value_type >::value; -}; + : boost::move_detail::and_ + < are_contiguous_and_same<I, O> + , container_detail::is_trivially_copy_constructible< typename ::boost::container::iterator_traits<I>::value_type > + > +{}; template <typename I, typename O, typename R> struct enable_if_memtransfer_copy_constructible - : enable_if_c<container_detail::is_memtransfer_copy_constructible<I, O>::value, R> + : enable_if<container_detail::is_memtransfer_copy_constructible<I, O>, R> {}; template <typename I, typename O, typename R> struct disable_if_memtransfer_copy_constructible - : enable_if_c<!container_detail::is_memtransfer_copy_constructible<I, O>::value, R> + : disable_if<container_detail::is_memtransfer_copy_constructible<I, O>, R> {}; template <typename I, typename O, typename R> struct enable_if_memtransfer_copy_assignable - : enable_if_c<container_detail::is_memtransfer_copy_assignable<I, O>::value, R> + : enable_if<container_detail::is_memtransfer_copy_assignable<I, O>, R> {}; template <typename I, typename O, typename R> struct disable_if_memtransfer_copy_assignable - : enable_if_c<!container_detail::is_memtransfer_copy_assignable<I, O>::value, R> + : disable_if<container_detail::is_memtransfer_copy_assignable<I, O>, R> {}; template @@ -174,8 +175,10 @@ inline F memmove(I f, I l, F r) BOOST_NOEXCEPT_OR_NOTHROW { typedef typename boost::container::iterator_traits<I>::value_type value_type; typename boost::container::iterator_traits<I>::difference_type n = boost::container::iterator_distance(f, l); - std::memmove((iterator_to_raw_pointer)(r), (iterator_to_raw_pointer)(f), sizeof(value_type)*n); - boost::container::iterator_advance(r, n); + if(n){ + std::memmove((iterator_to_raw_pointer)(r), (iterator_to_raw_pointer)(f), sizeof(value_type)*n); + boost::container::iterator_advance(r, n); + } return r; } @@ -185,8 +188,10 @@ template F memmove_n(I f, typename boost::container::iterator_traits<I>::difference_type n, F r) BOOST_NOEXCEPT_OR_NOTHROW { typedef typename boost::container::iterator_traits<I>::value_type value_type; - std::memmove((iterator_to_raw_pointer)(r), (iterator_to_raw_pointer)(f), sizeof(value_type)*n); - boost::container::iterator_advance(r, n); + if(n){ + std::memmove((iterator_to_raw_pointer)(r), (iterator_to_raw_pointer)(f), sizeof(value_type)*n); + boost::container::iterator_advance(r, n); + } return r; } @@ -195,9 +200,11 @@ template typename F> // F models ForwardIterator I memmove_n_source(I f, typename boost::container::iterator_traits<I>::difference_type n, F r) BOOST_NOEXCEPT_OR_NOTHROW { - typedef typename boost::container::iterator_traits<I>::value_type value_type; - std::memmove((iterator_to_raw_pointer)(r), (iterator_to_raw_pointer)(f), sizeof(value_type)*n); - boost::container::iterator_advance(f, n); + if(n){ + typedef typename boost::container::iterator_traits<I>::value_type value_type; + std::memmove((iterator_to_raw_pointer)(r), (iterator_to_raw_pointer)(f), sizeof(value_type)*n); + boost::container::iterator_advance(f, n); + } return f; } @@ -207,9 +214,11 @@ template I memmove_n_source_dest(I f, typename boost::container::iterator_traits<I>::difference_type n, F &r) BOOST_NOEXCEPT_OR_NOTHROW { typedef typename boost::container::iterator_traits<I>::value_type value_type; - std::memmove((iterator_to_raw_pointer)(r), (iterator_to_raw_pointer)(f), sizeof(value_type)*n); - boost::container::iterator_advance(f, n); - boost::container::iterator_advance(r, n); + if(n){ + std::memmove((iterator_to_raw_pointer)(r), (iterator_to_raw_pointer)(f), sizeof(value_type)*n); + boost::container::iterator_advance(f, n); + boost::container::iterator_advance(r, n); + } return f; } diff --git a/boost/container/detail/flat_tree.hpp b/boost/container/detail/flat_tree.hpp index a94043c6bd..f27421125f 100644 --- a/boost/container/detail/flat_tree.hpp +++ b/boost/container/detail/flat_tree.hpp @@ -470,20 +470,22 @@ class flat_tree template <class BidirIt> void insert_equal(ordered_range_t, BidirIt first, BidirIt last #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) - , typename container_detail::enable_if_c - < !container_detail::is_input_iterator<BidirIt>::value && - !container_detail::is_forward_iterator<BidirIt>::value + , typename container_detail::disable_if_or + < void + , container_detail::is_input_iterator<BidirIt> + , container_detail::is_forward_iterator<BidirIt> >::type * = 0 #endif ) - { this->priv_insert_ordered_range(false, first, last); } + { this->m_data.m_vect.merge(first, last); } template <class InIt> void insert_unique(ordered_unique_range_t, InIt first, InIt last #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) - , typename container_detail::enable_if_c - < container_detail::is_input_iterator<InIt>::value || - container_detail::is_forward_iterator<InIt>::value + , typename container_detail::enable_if_or + < void + , container_detail::is_input_iterator<InIt> + , container_detail::is_forward_iterator<InIt> >::type * = 0 #endif ) @@ -504,7 +506,7 @@ class flat_tree >::type * = 0 #endif ) - { this->priv_insert_ordered_range(true, first, last); } + { this->m_data.m_vect.merge_unique(first, last, value_compare()); } #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) @@ -855,8 +857,8 @@ class flat_tree } template <class RanIt> - RanIt priv_upper_bound(RanIt first, const RanIt last, - const key_type & key) const + RanIt priv_upper_bound + (RanIt first, const RanIt last,const key_type & key) const { const Compare &key_cmp = this->m_data.get_comp(); KeyOfValue key_extract; @@ -904,9 +906,9 @@ class flat_tree //Middle is equal to key last = first; last += len; + RanIt const first_ret = this->priv_lower_bound(first, middle, key); return std::pair<RanIt, RanIt> - ( this->priv_lower_bound(first, middle, key) - , this->priv_upper_bound(++middle, last, key)); + ( first_ret, this->priv_upper_bound(++middle, last, key)); } } return std::pair<RanIt, RanIt>(first, first); @@ -939,81 +941,11 @@ class flat_tree for ( ; first != last; ++first){ //If ordered, then try hint version //to achieve constant-time complexity per insertion + //in some cases pos = this->insert_equal(pos, *first); ++pos; } } - - template <class BidirIt> - void priv_insert_ordered_range(const bool unique_values, BidirIt first, BidirIt last) - { - size_type len = static_cast<size_type>(boost::container::iterator_distance(first, last)); - //Prereserve all memory so that iterators are not invalidated - this->reserve(this->size()+len); - //Auxiliary data for insertion positions. - const size_type BurstSize = len; - const ::boost::movelib::unique_ptr<size_type[]> positions = - ::boost::movelib::make_unique_definit<size_type[]>(BurstSize); - - const const_iterator b(this->cbegin()); - const const_iterator ce(this->cend()); - const_iterator pos(b); - const value_compare &val_cmp = this->m_data; - //Loop in burst sizes - bool back_insert = false; - while(len && !back_insert){ - const size_type burst = len < BurstSize ? len : BurstSize; - size_type unique_burst = 0u; - size_type checked = 0; - for(; checked != burst; ++checked){ - //Get the insertion position for each key, use iterator_traits<BidirIt>::value_type - //because it can be different from container::value_type - //(e.g. conversion between std::pair<T1, T2> -> boost::container::pair<T1, T2> - const typename boost::container::iterator_traits<BidirIt>::value_type & val = *first; - pos = const_cast<const flat_tree&>(*this).priv_lower_bound(pos, ce, KeyOfValue()(val)); - //Check if already present - if (pos != ce){ - ++first; - --len; - positions[checked] = (unique_values && !val_cmp(val, *pos)) ? - size_type(-1) : (++unique_burst, static_cast<size_type>(pos - b)); - } - else{ //this element and the remaining should be back inserted - back_insert = true; - break; - } - } - if(unique_burst){ - //Insert all in a single step in the precalculated positions - this->m_data.m_vect.insert_ordered_at(unique_burst, positions.get() + checked, first); - //Next search position updated, iterator still valid because we've preserved the vector - pos += unique_burst; - } - } - //The remaining range should be back inserted - if(unique_values){ - while(len--){ - BidirIt next(first); - ++next; - //Use iterator_traits<BidirIt>::value_type - //because it can be different from container::value_type - //(e.g. conversion between std::pair<T1, T2> -> boost::container::pair<T1, T2> - const typename boost::container::iterator_traits<BidirIt>::value_type & val = *first; - if (next == last || val_cmp(val, *next)){ - const bool room = this->m_data.m_vect.stable_emplace_back(*first); - (void)room; - BOOST_ASSERT(room); - } - first = next; - } - BOOST_ASSERT(first == last); - } - else{ - BOOST_ASSERT(size_type(boost::container::iterator_distance(first, last)) == len); - if(len) - this->m_data.m_vect.insert(this->m_data.m_vect.cend(), len, first, last); - } - } }; } //namespace container_detail { diff --git a/boost/container/detail/iterator.hpp b/boost/container/detail/iterator.hpp index ceb224f3ad..8538acc161 100644 --- a/boost/container/detail/iterator.hpp +++ b/boost/container/detail/iterator.hpp @@ -32,6 +32,7 @@ using ::boost::intrusive::iterator_advance; using ::boost::intrusive::iterator; using ::boost::intrusive::iterator_enable_if_tag; using ::boost::intrusive::iterator_disable_if_tag; +using ::boost::intrusive::iterator_arrow_result; } //namespace container { } //namespace boost { diff --git a/boost/container/detail/iterators.hpp b/boost/container/detail/iterators.hpp index 1f80d3e122..e8cfcf97a4 100644 --- a/boost/container/detail/iterators.hpp +++ b/boost/container/detail/iterators.hpp @@ -651,11 +651,13 @@ namespace container_detail { template<class T> struct has_iterator_category { + struct two { char _[2]; }; + template <typename X> static char test(int, typename X::iterator_category*); template <typename X> - static int test(int, ...); + static two test(int, ...); static const bool value = (1 == sizeof(test<T>(0, 0))); }; @@ -673,6 +675,12 @@ struct is_input_iterator<T, false> static const bool value = false; }; +template<class T> +struct is_not_input_iterator +{ + static const bool value = !is_input_iterator<T>::value; +}; + template<class T, bool = has_iterator_category<T>::value > struct is_forward_iterator { @@ -796,7 +804,7 @@ class iterator_from_iiterator { return !(l == r); } reference operator*() const BOOST_NOEXCEPT_OR_NOTHROW - { return (*this->m_iit).get_data(); } + { return this->m_iit->get_data(); } pointer operator->() const BOOST_NOEXCEPT_OR_NOTHROW { return ::boost::intrusive::pointer_traits<pointer>::pointer_to(this->operator*()); } diff --git a/boost/container/detail/mpl.hpp b/boost/container/detail/mpl.hpp index 74b618f8c6..e1684ea0b1 100644 --- a/boost/container/detail/mpl.hpp +++ b/boost/container/detail/mpl.hpp @@ -23,6 +23,8 @@ #include <boost/container/detail/config_begin.hpp> #include <boost/container/detail/workaround.hpp> +#include <boost/move/detail/type_traits.hpp> +#include <boost/intrusive/detail/mpl.hpp> #include <cstddef> @@ -30,110 +32,35 @@ namespace boost { namespace container { namespace container_detail { -template <class T, T val> -struct integral_constant -{ - static const T value = val; - typedef integral_constant<T,val> type; -}; - -template< bool C_ > -struct bool_ : integral_constant<bool, C_> -{ - static const bool value = C_; - operator bool() const { return bool_::value; } -}; - -template< unsigned V_ > -struct unsigned_ : integral_constant<unsigned, V_> -{ - static const unsigned value = V_; - operator unsigned() const { return unsigned_::value; } -}; - -typedef bool_<true> true_; -typedef bool_<false> false_; - -typedef true_ true_type; -typedef false_ false_type; - -typedef char yes_type; -struct no_type -{ - char padding[8]; -}; - -template <bool B, class T = void> -struct enable_if_c { - typedef T type; -}; - -template <class T> -struct enable_if_c<false, T> {}; - -template <class Cond, class T = void> -struct enable_if : public enable_if_c<Cond::value, T> {}; - -template <class Cond, class T = void> -struct disable_if : public enable_if_c<!Cond::value, T> {}; - -template <bool B, class T = void> -struct disable_if_c : public enable_if_c<!B, T> {}; - -#if defined(_MSC_VER) && (_MSC_VER >= 1400) - -template <class T, class U> -struct is_convertible -{ - static const bool value = __is_convertible_to(T, U); -}; - -#else - -template <class T, class U> -class is_convertible -{ - typedef char true_t; - class false_t { char dummy[2]; }; - //use any_conversion as first parameter since in MSVC - //overaligned types can't go through ellipsis - static false_t dispatch(...); - static true_t dispatch(U); - static T &trigger(); - public: - static const bool value = sizeof(dispatch(trigger())) == sizeof(true_t); -}; - -#endif - -template< - bool C - , typename T1 - , typename T2 - > -struct if_c -{ - typedef T1 type; -}; - -template< - typename T1 - , typename T2 - > -struct if_c<false,T1,T2> -{ - typedef T2 type; -}; - -template< - typename T1 - , typename T2 - , typename T3 - > -struct if_ -{ - typedef typename if_c<0 != T1::value, T2, T3>::type type; -}; +using boost::move_detail::integral_constant; +using boost::move_detail::true_type; +using boost::move_detail::false_type; +using boost::move_detail::enable_if_c; +using boost::move_detail::enable_if; +using boost::move_detail::enable_if_convertible; +using boost::move_detail::disable_if_c; +using boost::move_detail::disable_if; +using boost::move_detail::disable_if_convertible; +using boost::move_detail::is_convertible; +using boost::move_detail::if_c; +using boost::move_detail::if_; +using boost::move_detail::identity; +using boost::move_detail::bool_; +using boost::move_detail::true_; +using boost::move_detail::false_; +using boost::move_detail::yes_type; +using boost::move_detail::no_type; +using boost::move_detail::bool_; +using boost::move_detail::true_; +using boost::move_detail::false_; +using boost::move_detail::unvoid_ref; +using boost::move_detail::and_; +using boost::move_detail::or_; +using boost::move_detail::not_; +using boost::move_detail::enable_if_and; +using boost::move_detail::disable_if_and; +using boost::move_detail::enable_if_or; +using boost::move_detail::disable_if_or; template <class Pair> @@ -150,46 +77,6 @@ struct select1st { return x; } }; -// identity is an extension: it is not part of the standard. -template <class T> -struct identity -{ - typedef T argument_type; - typedef T result_type; - - typedef T type; - const T& operator()(const T& x) const - { return x; } -}; - -template<std::size_t S> -struct ls_zeros -{ - static const std::size_t value = (S & std::size_t(1)) ? 0 : (1u + ls_zeros<(S >> 1u)>::value); -}; - -template<> -struct ls_zeros<0> -{ - static const std::size_t value = 0; -}; - -template<> -struct ls_zeros<1> -{ - static const std::size_t value = 0; -}; - -template <std::size_t OrigSize, std::size_t RoundTo> -struct ct_rounded_size -{ - static const std::size_t value = ((OrigSize-1)/RoundTo+1)*RoundTo; -}; - -template <typename T> struct unvoid { typedef T type; }; -template <> struct unvoid<void> { struct type { }; }; -template <> struct unvoid<const void> { struct type { }; }; - } //namespace container_detail { } //namespace container { } //namespace boost { diff --git a/boost/container/detail/node_alloc_holder.hpp b/boost/container/detail/node_alloc_holder.hpp index 98c8e62baa..3b632a677d 100644 --- a/boost/container/detail/node_alloc_holder.hpp +++ b/boost/container/detail/node_alloc_holder.hpp @@ -173,87 +173,25 @@ struct node_alloc_holder } #else //defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) - NodePtr create_node() - { - NodePtr p = this->allocate_one(); - Deallocator node_deallocator(p, this->node_alloc()); - allocator_traits<NodeAlloc>::construct - (this->node_alloc(), container_detail::addressof(p->m_data)); - node_deallocator.release(); - typedef typename Node::hook_type hook_type; - ::new(static_cast<hook_type*>(container_detail::to_raw_pointer(p)), boost_container_new_t()) hook_type; - return (p); - } - - template<BOOST_MOVE_CLASS1> - NodePtr create_node(BOOST_MOVE_UREF1) - { - NodePtr p = this->allocate_one(); - Deallocator node_deallocator(p, this->node_alloc()); - allocator_traits<NodeAlloc>::construct - (this->node_alloc(), container_detail::addressof(p->m_data) - , BOOST_MOVE_FWD1); - node_deallocator.release(); - typedef typename Node::hook_type hook_type; - ::new(static_cast<hook_type*>(container_detail::to_raw_pointer(p)), boost_container_new_t()) hook_type; - return (p); - } - template<BOOST_MOVE_CLASS2> - NodePtr create_node(BOOST_MOVE_UREF2) - { - NodePtr p = this->allocate_one(); - Deallocator node_deallocator(p, this->node_alloc()); - allocator_traits<NodeAlloc>::construct - (this->node_alloc(), container_detail::addressof(p->m_data) - , BOOST_MOVE_FWD2); - node_deallocator.release(); - typedef typename Node::hook_type hook_type; - ::new(static_cast<hook_type*>(container_detail::to_raw_pointer(p)), boost_container_new_t()) hook_type; - return (p); - } - - template<BOOST_MOVE_CLASS3> - NodePtr create_node(BOOST_MOVE_UREF3) - { - NodePtr p = this->allocate_one(); - Deallocator node_deallocator(p, this->node_alloc()); - allocator_traits<NodeAlloc>::construct - (this->node_alloc(), container_detail::addressof(p->m_data) - , BOOST_MOVE_FWD3); - node_deallocator.release(); - typedef typename Node::hook_type hook_type; - ::new(static_cast<hook_type*>(container_detail::to_raw_pointer(p)), boost_container_new_t()) hook_type; - return (p); - } - - template<BOOST_MOVE_CLASS4> - NodePtr create_node(BOOST_MOVE_UREF4) - { - NodePtr p = this->allocate_one(); - Deallocator node_deallocator(p, this->node_alloc()); - allocator_traits<NodeAlloc>::construct - (this->node_alloc(), container_detail::addressof(p->m_data) - , BOOST_MOVE_FWD4); - node_deallocator.release(); - typedef typename Node::hook_type hook_type; - ::new(static_cast<hook_type*>(container_detail::to_raw_pointer(p)), boost_container_new_t()) hook_type; - return (p); - } - - template<BOOST_MOVE_CLASS5> - NodePtr create_node(BOOST_MOVE_UREF5) - { - NodePtr p = this->allocate_one(); - Deallocator node_deallocator(p, this->node_alloc()); - allocator_traits<NodeAlloc>::construct - (this->node_alloc(), container_detail::addressof(p->m_data) - , BOOST_MOVE_FWD5); - node_deallocator.release(); - typedef typename Node::hook_type hook_type; - ::new(static_cast<hook_type*>(container_detail::to_raw_pointer(p)), boost_container_new_t()) hook_type; - return (p); - } + #define BOOST_CONTAINER_NODE_ALLOC_HOLDER_CONSTRUCT_IMPL(N) \ + BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ + NodePtr create_node(BOOST_MOVE_UREF##N)\ + {\ + NodePtr p = this->allocate_one();\ + Deallocator node_deallocator(p, this->node_alloc());\ + allocator_traits<NodeAlloc>::construct\ + ( this->node_alloc()\ + , container_detail::addressof(p->m_data)\ + BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ + node_deallocator.release();\ + typedef typename Node::hook_type hook_type;\ + ::new(static_cast<hook_type*>(container_detail::to_raw_pointer(p)), boost_container_new_t()) hook_type;\ + return (p);\ + }\ + // + BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_NODE_ALLOC_HOLDER_CONSTRUCT_IMPL) + #undef BOOST_CONTAINER_NODE_ALLOC_HOLDER_CONSTRUCT_IMPL #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) @@ -375,7 +313,7 @@ struct node_alloc_holder {} NodePtr operator()(const Node &other) const - { return m_holder.create_node(other.get_data()); } + { return m_holder.create_node(other.m_data); } node_alloc_holder &m_holder; }; @@ -387,7 +325,9 @@ struct node_alloc_holder {} NodePtr operator()(Node &other) - { return m_holder.create_node(::boost::move(other.get_data())); } + { //Use m_data instead of get_data to allow moving const key in [multi]map + return m_holder.create_node(::boost::move(other.m_data)); + } node_alloc_holder &m_holder; }; @@ -413,12 +353,12 @@ struct node_alloc_holder template<class ConvertibleToAlloc> members_holder(BOOST_FWD_REF(ConvertibleToAlloc) c2alloc, const value_compare &c) : NodeAlloc(boost::forward<ConvertibleToAlloc>(c2alloc)) - , m_icont(typename ICont::value_compare(c)) + , m_icont(typename ICont::key_compare(c)) {} explicit members_holder(const value_compare &c) : NodeAlloc() - , m_icont(typename ICont::value_compare(c)) + , m_icont(typename ICont::key_compare(c)) {} //The intrusive container diff --git a/boost/container/detail/pair.hpp b/boost/container/detail/pair.hpp index 6d31d3b796..35e8846caa 100644 --- a/boost/container/detail/pair.hpp +++ b/boost/container/detail/pair.hpp @@ -33,6 +33,46 @@ #include <boost/intrusive/detail/minimal_pair_header.hpp> //pair #include <boost/move/utility_core.hpp> +/* +namespace boost{ + +template<class T1, class T2> +inline rv< std::pair<T1, T2> > &move(std::pair<T1, T2> &r) +{ + return reinterpret_cast< rv< std::pair<T1, T2> > &>(r); +} + +template<class T1, class T2> +inline rv< std::pair<T1, T2> > &move(rv< std::pair<T1, T2> > &r) +{ + return r; +} + +template <class T> +inline typename ::boost::move_detail::enable_if_and + < T & + , boost::container::container_detail::is_std_pair<T> + , ::boost::move_detail::is_rv<T> + >::type + forward(const typename ::boost::move_detail::identity<T>::type &x) BOOST_NOEXCEPT +{ + return const_cast<T&>(x); +} + +template <class T> +inline typename ::boost::move_detail::enable_if_and + < const T & + , boost::container::container_detail::is_std_pair<T> + , ::boost::move_detail::is_not_rv<T> + >::type + forward(const typename ::boost::move_detail::identity<T>::type &x) BOOST_NOEXCEPT +{ + return x; +} + +} //namespace boost { +*/ + namespace boost { namespace container { namespace container_detail { @@ -58,6 +98,24 @@ struct is_pair< std::pair<T1, T2> > static const bool value = true; }; +template <class T> +struct is_not_pair +{ + static const bool value = !is_pair<T>::value; +}; + +template <class T> +struct is_std_pair +{ + static const bool value = false; +}; + +template <class T1, class T2> +struct is_std_pair< std::pair<T1, T2> > +{ + static const bool value = true; +}; + struct pair_nat; struct piecewise_construct_t { }; @@ -182,10 +240,11 @@ struct pair } template <class D, class S> - typename ::boost::container::container_detail::enable_if_c - < !(::boost::container::container_detail::is_same<T1, D>::value && - ::boost::container::container_detail::is_same<T2, S>::value) - , pair &>::type + typename ::boost::container::container_detail::disable_if_or + < pair & + , ::boost::container::container_detail::is_same<T1, D> + , ::boost::container::container_detail::is_same<T2, S> + >::type operator=(const pair<D, S>&p) { first = p.first; @@ -194,18 +253,18 @@ struct pair } template <class D, class S> - typename ::boost::container::container_detail::enable_if_c - < !(::boost::container::container_detail::is_same<T1, D>::value && - ::boost::container::container_detail::is_same<T2, S>::value) - , pair &>::type + typename ::boost::container::container_detail::disable_if_or + < pair & + , ::boost::container::container_detail::is_same<T1, D> + , ::boost::container::container_detail::is_same<T2, S> + >::type operator=(BOOST_RV_REF_BEG pair<D, S> BOOST_RV_REF_END p) { first = ::boost::move(p.first); second = ::boost::move(p.second); return *this; } - - //std::pair copy assignment +//std::pair copy assignment pair& operator=(const std::pair<T1, T2> &p) { first = p.first; diff --git a/boost/container/detail/std_fwd.hpp b/boost/container/detail/std_fwd.hpp index a2931c134b..1277df071f 100644 --- a/boost/container/detail/std_fwd.hpp +++ b/boost/container/detail/std_fwd.hpp @@ -23,10 +23,12 @@ // Standard predeclarations ////////////////////////////////////////////////////////////////////////////// -#if defined(__clang__) && defined(_LIBCPP_VERSION) +#if defined(_LIBCPP_VERSION) #define BOOST_CONTAINER_CLANG_INLINE_STD_NS #pragma GCC diagnostic push - #pragma GCC diagnostic ignored "-Wc++11-extensions" + #if defined(__clang__) + #pragma GCC diagnostic ignored "-Wc++11-extensions" + #endif #define BOOST_CONTAINER_STD_NS_BEG _LIBCPP_BEGIN_NAMESPACE_STD #define BOOST_CONTAINER_STD_NS_END _LIBCPP_END_NAMESPACE_STD #elif defined(BOOST_GNU_STDLIB) && defined(_GLIBCXX_BEGIN_NAMESPACE_VERSION) //GCC >= 4.6 diff --git a/boost/container/detail/tree.hpp b/boost/container/detail/tree.hpp index 0f90b5a4e2..c90202973a 100644 --- a/boost/container/detail/tree.hpp +++ b/boost/container/detail/tree.hpp @@ -43,6 +43,7 @@ #include <boost/intrusive/sgtree.hpp> // intrusive/detail #include <boost/intrusive/detail/minimal_pair_header.hpp> //pair +#include <boost/intrusive/detail/tree_value_compare.hpp> //tree_value_compare // move #include <boost/move/utility_core.hpp> // move/detail @@ -52,57 +53,15 @@ // other #include <boost/core/no_exceptions_support.hpp> -namespace boost { -namespace container { -namespace container_detail { -template<class Key, class T, class Compare, class KeyOfValue> -struct tree_value_compare - : public Compare -{ - typedef T value_type; - typedef Compare key_compare; - typedef KeyOfValue key_of_value; - typedef Key key_type; - explicit tree_value_compare(const key_compare &kcomp) - : Compare(kcomp) - {} - - tree_value_compare() - : Compare() - {} +#include <boost/container/detail/std_fwd.hpp> - const key_compare &key_comp() const - { return static_cast<const key_compare &>(*this); } - - key_compare &key_comp() - { return static_cast<key_compare &>(*this); } - - template<class U> - struct is_key - { - static const bool value = is_same<const U, const key_type>::value; - }; - - template<class U> - typename enable_if_c<is_key<U>::value, const key_type &>::type - key_forward(const U &key) const - { return key; } - - template<class U> - typename enable_if_c<!is_key<U>::value, const key_type &>::type - key_forward(const U &key) const - { return KeyOfValue()(key); } - - template<class KeyType, class KeyType2> - bool operator()(const KeyType &key1, const KeyType2 &key2) const - { return key_compare::operator()(this->key_forward(key1), this->key_forward(key2)); } +namespace boost { +namespace container { +namespace container_detail { - template<class KeyType, class KeyType2> - bool operator()(const KeyType &key1, const KeyType2 &key2) - { return key_compare::operator()(this->key_forward(key1), this->key_forward(key2)); } -}; +using boost::intrusive::tree_value_compare; template<class VoidPointer, boost::container::tree_type_enum tree_type_value, bool OptimizeSize> struct intrusive_tree_hook; @@ -156,7 +115,7 @@ struct tree_internal_data_type template<class T1, class T2> struct tree_internal_data_type< std::pair<T1, T2> > { - typedef pair<T1, T2> type; + typedef pair<typename boost::move_detail::remove_const<T1>::type, T2> type; }; //The node to be store in the tree @@ -549,9 +508,10 @@ class tree tree(bool unique_insertion, InputIterator first, InputIterator last, const key_compare& comp, const allocator_type& a #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) - , typename container_detail::enable_if_c - < container_detail::is_input_iterator<InputIterator>::value - || container_detail::is_same<alloc_version, version_1>::value + , typename container_detail::enable_if_or + < void + , container_detail::is_same<alloc_version, version_1> + , container_detail::is_input_iterator<InputIterator> >::type * = 0 #endif ) @@ -577,9 +537,10 @@ class tree tree(bool unique_insertion, InputIterator first, InputIterator last, const key_compare& comp, const allocator_type& a #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) - , typename container_detail::enable_if_c - < !(container_detail::is_input_iterator<InputIterator>::value - || container_detail::is_same<alloc_version, version_1>::value) + , typename container_detail::disable_if_or + < void + , container_detail::is_same<alloc_version, version_1> + , container_detail::is_input_iterator<InputIterator> >::type * = 0 #endif ) @@ -606,10 +567,11 @@ class tree tree( ordered_range_t, InputIterator first, InputIterator last , const key_compare& comp = key_compare(), const allocator_type& a = allocator_type() #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) - , typename container_detail::enable_if_c - < container_detail::is_input_iterator<InputIterator>::value - || container_detail::is_same<alloc_version, version_1>::value - >::type * = 0 + , typename container_detail::enable_if_or + < void + , container_detail::is_same<alloc_version, version_1> + , container_detail::is_input_iterator<InputIterator> + >::type * = 0 #endif ) : AllocHolder(value_compare(comp), a) @@ -623,10 +585,11 @@ class tree tree( ordered_range_t, InputIterator first, InputIterator last , const key_compare& comp = key_compare(), const allocator_type& a = allocator_type() #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) - , typename container_detail::enable_if_c - < !(container_detail::is_input_iterator<InputIterator>::value - || container_detail::is_same<alloc_version, version_1>::value) - >::type * = 0 + , typename container_detail::disable_if_or + < void + , container_detail::is_same<alloc_version, version_1> + , container_detail::is_input_iterator<InputIterator> + >::type * = 0 #endif ) : AllocHolder(value_compare(comp), a) @@ -663,7 +626,7 @@ class tree } else{ this->icont().clone_from - (x.icont(), typename AllocHolder::move_cloner(*this), Destroyer(this->node_alloc())); + (boost::move(x.icont()), typename AllocHolder::move_cloner(*this), Destroyer(this->node_alloc())); } } @@ -730,7 +693,7 @@ class tree //Now recreate the source tree reusing nodes stored by other_tree this->icont().clone_from - (x.icont() + (::boost::move(x.icont()) , RecyclingCloner<AllocHolder, true>(*this, other_tree) , Destroyer(this->node_alloc())); diff --git a/boost/container/detail/type_traits.hpp b/boost/container/detail/type_traits.hpp index 1ae2426863..e02709ac6e 100644 --- a/boost/container/detail/type_traits.hpp +++ b/boost/container/detail/type_traits.hpp @@ -31,6 +31,7 @@ namespace container { namespace container_detail { using ::boost::move_detail::is_same; +using ::boost::move_detail::is_different; using ::boost::move_detail::is_pointer; using ::boost::move_detail::add_reference; using ::boost::move_detail::add_const; diff --git a/boost/container/list.hpp b/boost/container/list.hpp index 54da6df518..5135eaecee 100644 --- a/boost/container/list.hpp +++ b/boost/container/list.hpp @@ -417,9 +417,7 @@ class list template <class InpIt> void assign(InpIt first, InpIt last #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) - , typename container_detail::enable_if_c - < !container_detail::is_convertible<InpIt, size_type>::value - >::type * = 0 + , typename container_detail::disable_if_convertible<InpIt, size_type>::type * = 0 #endif ) { diff --git a/boost/container/node_allocator.hpp b/boost/container/node_allocator.hpp index afd6f98a8d..c3d809078f 100644 --- a/boost/container/node_allocator.hpp +++ b/boost/container/node_allocator.hpp @@ -74,9 +74,9 @@ class node_allocator typedef T * pointer; typedef const T * const_pointer; typedef typename ::boost::container:: - container_detail::unvoid<T>::type & reference; - typedef const typename ::boost::container:: - container_detail::unvoid<T>::type & const_reference; + container_detail::unvoid_ref<T>::type reference; + typedef typename ::boost::container:: + container_detail::unvoid_ref<const T>::type const_reference; typedef std::size_t size_type; typedef std::ptrdiff_t difference_type; diff --git a/boost/container/scoped_allocator.hpp b/boost/container/scoped_allocator.hpp index 55514aae21..0724f948fb 100644 --- a/boost/container/scoped_allocator.hpp +++ b/boost/container/scoped_allocator.hpp @@ -1129,7 +1129,7 @@ class scoped_allocator_adaptor #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) void #else - typename container_detail::enable_if_c<!container_detail::is_pair<T>::value, void>::type + typename container_detail::enable_if<container_detail::is_not_pair<T> >::type #endif construct(T* p, BOOST_FWD_REF(Args)...args) { @@ -1146,7 +1146,7 @@ class scoped_allocator_adaptor //overload selection problems when the first parameter is a pair. #define BOOST_CONTAINER_SCOPED_ALLOCATOR_CONSTRUCT_CODE(N) \ template < typename T BOOST_MOVE_I##N BOOST_MOVE_CLASSQ##N >\ - typename container_detail::enable_if_c<!container_detail::is_pair<T>::value, void>::type\ + typename container_detail::enable_if< container_detail::is_not_pair<T> >::type\ construct(T* p BOOST_MOVE_I##N BOOST_MOVE_UREFQ##N)\ {\ container_detail::dispatch_uses_allocator\ @@ -1188,12 +1188,12 @@ class scoped_allocator_adaptor template <class T1, class T2, class U, class V> void construct( std::pair<T1, T2>* p , BOOST_RV_REF_BEG std::pair<U, V> BOOST_RV_REF_END x) - { this->construct_pair(p, x); } + { this->construct_pair(p, ::boost::move(x)); } template <class T1, class T2, class U, class V> void construct( container_detail::pair<T1, T2>* p , BOOST_RV_REF_BEG container_detail::pair<U, V> BOOST_RV_REF_END x) - { this->construct_pair(p, x); } + { this->construct_pair(p, ::boost::move(x)); } #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED private: @@ -1246,6 +1246,39 @@ class scoped_allocator_adaptor #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED }; +template<bool ZeroInner> +struct scoped_allocator_operator_equal +{ + //Optimize equal outer allocator types with + //allocator_traits::equal which uses is_always_equal + template<class IA> + static bool equal_outer(const IA &l, const IA &r) + { return allocator_traits<IA>::equal(l, r); } + + //Otherwise compare it normally + template<class IA1, class IA2> + static bool equal_outer(const IA1 &l, const IA2 &r) + { return l == r; } + + //Otherwise compare it normally + template<class IA> + static bool equal_inner(const IA &l, const IA &r) + { return allocator_traits<IA>::equal(l, r); } +}; + +template<> +struct scoped_allocator_operator_equal<true> + : scoped_allocator_operator_equal<false> +{ + //when inner allocator count is zero, + //inner_allocator_type is the same as outer_allocator_type + //so both types can be different in operator== + template<class IA1, class IA2> + static bool equal_inner(const IA1 &, const IA2 &) + { return true; } +}; + + template <typename OuterA1, typename OuterA2, BOOST_CONTAINER_SCOPEDALLOC_ALLINNERCLASS> inline bool operator==(const scoped_allocator_adaptor<OuterA1, BOOST_CONTAINER_SCOPEDALLOC_ALLINNER>& a ,const scoped_allocator_adaptor<OuterA2, BOOST_CONTAINER_SCOPEDALLOC_ALLINNER>& b) @@ -1255,14 +1288,9 @@ inline bool operator==(const scoped_allocator_adaptor<OuterA1, BOOST_CONTAINER_S #else const bool has_zero_inner = boost::container::container_detail::is_same<P0, void>::value; #endif - typedef typename scoped_allocator_adaptor<OuterA1, BOOST_CONTAINER_SCOPEDALLOC_ALLINNER> - ::outer_allocator_type outer_allocator_type; - typedef typename scoped_allocator_adaptor<OuterA1, BOOST_CONTAINER_SCOPEDALLOC_ALLINNER> - ::inner_allocator_type inner_allocator_type; - - return allocator_traits<outer_allocator_type>::equal(a.outer_allocator(), b.outer_allocator()) - && (has_zero_inner || - allocator_traits<inner_allocator_type>::equal(a.inner_allocator(), b.inner_allocator())); + typedef scoped_allocator_operator_equal<has_zero_inner> equal_t; + return equal_t::equal_outer(a.outer_allocator(), b.outer_allocator()) && + equal_t::equal_inner(a.inner_allocator(), b.inner_allocator()); } template <typename OuterA1, typename OuterA2, BOOST_CONTAINER_SCOPEDALLOC_ALLINNERCLASS> diff --git a/boost/container/slist.hpp b/boost/container/slist.hpp index b0901ef086..2b53df132f 100644 --- a/boost/container/slist.hpp +++ b/boost/container/slist.hpp @@ -442,9 +442,7 @@ class slist template <class InpIt> void assign(InpIt first, InpIt last #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) - , typename container_detail::enable_if_c - < !container_detail::is_convertible<InpIt, size_type>::value - >::type * = 0 + , typename container_detail::disable_if_convertible<InpIt, size_type>::type * = 0 #endif ) { diff --git a/boost/container/small_vector.hpp b/boost/container/small_vector.hpp index 7ef0c238a3..a9f7522205 100644 --- a/boost/container/small_vector.hpp +++ b/boost/container/small_vector.hpp @@ -60,7 +60,7 @@ class small_vector_base; //! for documentation purposes. //! //! This allocator inherits from a standard-conforming allocator -//! and forwards member functiond to the standard allocator except +//! and forwards member functions to the standard allocator except //! when internal storage is being used as memory source. //! //! This allocator is a "partially_propagable" allocator and @@ -68,7 +68,7 @@ class small_vector_base; //! //! A partially propagable allocator means that not all storage //! allocatod by an instance of `small_vector_allocator` can be -//! deallocated by another instance of this type, even is both +//! deallocated by another instance of this type, even if both //! instances compare equal or an instance is propagated to another //! one using the copy/move constructor or assignment. The storage that //! can never be propagated is identified by `storage_is_unpropagable(p)`. @@ -311,8 +311,12 @@ class small_vector_base : public vector<T, small_vector_allocator<SecondaryAllocator> > { #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED + public: + //Make it public as it will be inherited by small_vector and container + //must have this public member typedef typename allocator_traits<SecondaryAllocator>::pointer pointer; + private: BOOST_COPYABLE_AND_MOVABLE(small_vector_base) friend class small_vector_allocator<SecondaryAllocator>; @@ -428,8 +432,8 @@ struct small_vector_storage_definer #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED -//! small_vector a vector-like container optimized for the case when it contains few elements. -//! It contains some preallocated elements in-place, which allows it to avoid the use of dynamic storage allocation +//! small_vector is a vector-like container optimized for the case when it contains few elements. +//! It contains some preallocated elements in-place, which can avoid the use of dynamic storage allocation //! when the actual number of elements is below that preallocated threshold. //! //! `small_vector<T, N, Allocator>` is convertible to `small_vector_base<T, Allocator>` that is independent diff --git a/boost/container/stable_vector.hpp b/boost/container/stable_vector.hpp index 76c9e9f07b..6aca69bde6 100644 --- a/boost/container/stable_vector.hpp +++ b/boost/container/stable_vector.hpp @@ -349,7 +349,7 @@ class stable_vector_iterator return tmp; } - friend difference_type operator-(const stable_vector_iterator& left, const stable_vector_iterator& right) BOOST_NOEXCEPT_OR_NOTHROW + friend difference_type operator-(const stable_vector_iterator &left, const stable_vector_iterator &right) BOOST_NOEXCEPT_OR_NOTHROW { return left.m_pn->up - right.m_pn->up; } //Comparison operators @@ -493,7 +493,7 @@ class stable_vector , false> iterator_impl; typedef stable_vector_iterator < typename allocator_traits<Allocator>::pointer - , false> const_iterator_impl; + , true> const_iterator_impl; #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED public: @@ -687,7 +687,7 @@ class stable_vector : internal_data(l), index(l) { stable_vector_detail::clear_on_destroy<stable_vector> cod(*this); - insert(cend(), il.begin(), il.end()) + insert(cend(), il.begin(), il.end()); STABLE_VECTOR_CHECK_INVARIANT; cod.release(); } @@ -804,6 +804,7 @@ class stable_vector //Resources can be transferred if both allocators are //going to be equal after this function (either propagated or already equal) if(propagate_alloc || allocators_equal){ + STABLE_VECTOR_CHECK_INVARIANT //Destroy objects but retain memory in case x reuses it in the future this->clear(); //Move allocator if needed @@ -850,13 +851,12 @@ class stable_vector //! //! <b>Complexity</b>: Linear to n. template<typename InputIterator> - void assign(InputIterator first,InputIterator last - #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) - , typename container_detail::enable_if_c - < !container_detail::is_convertible<InputIterator, size_type>::value - >::type * = 0 - #endif - ) + #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) + typename container_detail::disable_if_convertible<InputIterator, size_type>::type + #else + void + #endif + assign(InputIterator first,InputIterator last) { STABLE_VECTOR_CHECK_INVARIANT; iterator first1 = this->begin(); @@ -1112,13 +1112,12 @@ class stable_vector { const size_type index_size = this->index.size(); BOOST_ASSERT(!index_size || index_size >= ExtraPointers); - const size_type bucket_extra_capacity = this->index.capacity()- index_size; const size_type node_extra_capacity = this->internal_data.pool_size; - const size_type extra_capacity = (bucket_extra_capacity < node_extra_capacity) - ? bucket_extra_capacity : node_extra_capacity; + //Pool count must be less than index capacity, as index is a vector + BOOST_ASSERT(node_extra_capacity <= (this->index.capacity()- index_size)); const size_type index_offset = - (ExtraPointers + extra_capacity) & (size_type(0u) - size_type(index_size != 0)); - return index_size - index_offset; + (node_extra_capacity - ExtraPointers) & (size_type(0u) - size_type(index_size != 0)); + return index_size + index_offset; } //! <b>Effects</b>: If n is less than or equal to capacity(), this call has no @@ -1294,11 +1293,10 @@ class stable_vector return (this->index.empty()) ? this->cend() : iterator(node_ptr_traits::static_cast_from(this->index[n])); } - //! <b>Requires</b>: size() >= n. + //! <b>Requires</b>: begin() <= p <= end(). //! - //! <b>Effects</b>: Returns an iterator to the nth element - //! from the beginning of the container. Returns end() - //! if n == size(). + //! <b>Effects</b>: Returns the index of the element pointed by p + //! and size() if p == end(). //! //! <b>Throws</b>: Nothing. //! @@ -1517,14 +1515,16 @@ class stable_vector //! //! <b>Complexity</b>: Linear to distance [first, last). template <class InputIterator> - iterator insert(const_iterator p, InputIterator first, InputIterator last - #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) - , typename container_detail::enable_if_c - < !container_detail::is_convertible<InputIterator, size_type>::value - && container_detail::is_input_iterator<InputIterator>::value - >::type * = 0 - #endif - ) + #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) + typename container_detail::disable_if_or + < iterator + , container_detail::is_convertible<InputIterator, size_type> + , container_detail::is_not_input_iterator<InputIterator> + >::type + #else + iterator + #endif + insert(const_iterator p, InputIterator first, InputIterator last) { STABLE_VECTOR_CHECK_INVARIANT; const size_type pos_n = p - this->cbegin(); @@ -1536,12 +1536,12 @@ class stable_vector #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) template <class FwdIt> - iterator insert(const_iterator p, FwdIt first, FwdIt last - , typename container_detail::enable_if_c - < !container_detail::is_convertible<FwdIt, size_type>::value - && !container_detail::is_input_iterator<FwdIt>::value - >::type * = 0 - ) + typename container_detail::disable_if_or + < iterator + , container_detail::is_convertible<FwdIt, size_type> + , container_detail::is_input_iterator<FwdIt> + >::type + insert(const_iterator p, FwdIt first, FwdIt last) { const size_type num_new = static_cast<size_type>(boost::container::iterator_distance(first, last)); const size_type idx = static_cast<size_type>(p - this->cbegin()); @@ -1786,7 +1786,7 @@ class stable_vector template <class U> void priv_push_back(BOOST_MOVE_CATCH_FWD(U) x) { - if(this->priv_capacity_bigger_than_size()){ + if(BOOST_LIKELY(this->priv_capacity_bigger_than_size())){ //Enough memory in the pool and in the index const node_ptr p = this->priv_get_from_pool(); BOOST_ASSERT(!!p); @@ -1961,8 +1961,19 @@ class stable_vector { index_type & index_ref = const_cast<index_type&>(this->index); - if(index.empty()) + const size_type index_size = this->index.size(); + if(!index_size) return !this->capacity() && !this->size(); + + if(index_size < ExtraPointers) + return false; + + const size_type bucket_extra_capacity = this->index.capacity()- index_size; + const size_type node_extra_capacity = this->internal_data.pool_size; + if(bucket_extra_capacity < node_extra_capacity){ + return false; + } + if(this->priv_get_end_node() != *(index.end() - ExtraPointers)){ return false; } diff --git a/boost/container/string.hpp b/boost/container/string.hpp index e5ec287cf8..7399223904 100644 --- a/boost/container/string.hpp +++ b/boost/container/string.hpp @@ -111,8 +111,7 @@ class basic_string_base ~basic_string_base() { if(!this->is_short()){ - this->deallocate_block(); - this->is_short(true); + this->deallocate(this->priv_long_addr(), this->priv_long_storage()); } } @@ -131,15 +130,14 @@ class basic_string_base long_t(const long_t &other) { - this->is_short = other.is_short; + this->is_short = false; length = other.length; storage = other.storage; start = other.start; } - long_t &operator =(const long_t &other) + long_t &operator= (const long_t &other) { - this->is_short = other.is_short; length = other.length; storage = other.storage; start = other.start; @@ -165,8 +163,7 @@ class basic_string_base static const size_type MinInternalBufferChars = 8; static const size_type AlignmentOfValueType = alignment_of<value_type>::value; - static const size_type ShortDataOffset = - container_detail::ct_rounded_size<sizeof(short_header), AlignmentOfValueType>::value; + static const size_type ShortDataOffset = ((sizeof(short_header)-1)/AlignmentOfValueType+1)*AlignmentOfValueType; static const size_type ZeroCostInternalBufferChars = (sizeof(long_t) - ShortDataOffset)/sizeof(value_type); static const size_type UnalignedFinalInternalBufferChars = @@ -421,21 +418,19 @@ class basic_string_base } else{ short_t short_backup(this->members_.m_repr.short_repr()); - long_t long_backup (other.members_.m_repr.long_repr()); + this->members_.m_repr.short_repr().~short_t(); + ::new(&this->members_.m_repr.long_repr()) long_t(other.members_.m_repr.long_repr()); other.members_.m_repr.long_repr().~long_t(); - ::new(&this->members_.m_repr.long_repr()) long_t; - this->members_.m_repr.long_repr() = long_backup; - other.members_.m_repr.short_repr() = short_backup; + ::new(&other.members_.m_repr.short_repr()) short_t(short_backup); } } else{ if(other.is_short()){ short_t short_backup(other.members_.m_repr.short_repr()); - long_t long_backup (this->members_.m_repr.long_repr()); + other.members_.m_repr.short_repr().~short_t(); + ::new(&other.members_.m_repr.long_repr()) long_t(this->members_.m_repr.long_repr()); this->members_.m_repr.long_repr().~long_t(); - ::new(&other.members_.m_repr.long_repr()) long_t; - other.members_.m_repr.long_repr() = long_backup; - this->members_.m_repr.short_repr() = short_backup; + ::new(&this->members_.m_repr.short_repr()) short_t(short_backup); } else{ boost::adl_move_swap(this->members_.m_repr.long_repr(), other.members_.m_repr.long_repr()); @@ -1289,9 +1284,7 @@ class basic_string template <class InputIter> basic_string& assign(InputIter first, InputIter last #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) - , typename container_detail::enable_if_c - < !container_detail::is_convertible<InputIter, size_type>::value - >::type * = 0 + , typename container_detail::disable_if_convertible<InputIter, size_type>::type * = 0 #endif ) { @@ -1438,9 +1431,10 @@ class basic_string template <class InputIter> iterator insert(const_iterator p, InputIter first, InputIter last #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) - , typename container_detail::enable_if_c - < !container_detail::is_convertible<InputIter, size_type>::value - && container_detail::is_input_iterator<InputIter>::value + , typename container_detail::disable_if_or + < void + , container_detail::is_convertible<InputIter, size_type> + , container_detail::is_not_input_iterator<InputIter> >::type * = 0 #endif ) @@ -1455,9 +1449,10 @@ class basic_string #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) template <class ForwardIter> iterator insert(const_iterator p, ForwardIter first, ForwardIter last - , typename container_detail::enable_if_c - < !container_detail::is_convertible<ForwardIter, size_type>::value - && !container_detail::is_input_iterator<ForwardIter>::value + , typename container_detail::disable_if_or + < void + , container_detail::is_convertible<ForwardIter, size_type> + , container_detail::is_input_iterator<ForwardIter> >::type * = 0 ) { @@ -1829,9 +1824,10 @@ class basic_string template <class InputIter> basic_string& replace(const_iterator i1, const_iterator i2, InputIter j1, InputIter j2 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) - , typename container_detail::enable_if_c - < !container_detail::is_convertible<InputIter, size_type>::value - && container_detail::is_input_iterator<InputIter>::value + , typename container_detail::disable_if_or + < void + , container_detail::is_convertible<InputIter, size_type> + , container_detail::is_input_iterator<InputIter> >::type * = 0 #endif ) @@ -1850,9 +1846,10 @@ class basic_string #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) template <class ForwardIter> basic_string& replace(const_iterator i1, const_iterator i2, ForwardIter j1, ForwardIter j2 - , typename container_detail::enable_if_c - < !container_detail::is_convertible<ForwardIter, size_type>::value - && !container_detail::is_input_iterator<ForwardIter>::value + , typename container_detail::disable_if_or + < void + , container_detail::is_convertible<ForwardIter, size_type> + , container_detail::is_not_input_iterator<ForwardIter> >::type * = 0 ) { diff --git a/boost/container/vector.hpp b/boost/container/vector.hpp index 1b6d963934..1cf44c8e27 100644 --- a/boost/container/vector.hpp +++ b/boost/container/vector.hpp @@ -57,6 +57,7 @@ // other #include <boost/core/no_exceptions_support.hpp> #include <boost/assert.hpp> +#include <boost/cstdint.hpp> //std #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) @@ -179,6 +180,70 @@ class vec_iterator { return l.m_ptr >= r.m_ptr; } }; +template<class BiDirPosConstIt, class BiDirValueIt> +struct vector_insert_ordered_cursor +{ + typedef typename iterator_traits<BiDirPosConstIt>::value_type size_type; + typedef typename iterator_traits<BiDirValueIt>::reference reference; + + vector_insert_ordered_cursor(BiDirPosConstIt posit, BiDirValueIt valueit) + : last_position_it(posit), last_value_it(valueit) + {} + + void operator --() + { + --last_value_it; + --last_position_it; + while(this->get_pos() == size_type(-1)){ + --last_value_it; + --last_position_it; + } + } + + size_type get_pos() const + { return *last_position_it; } + + reference get_val() + { return *last_value_it; } + + BiDirPosConstIt last_position_it; + 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; + + 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; + } + } + + size_type get_pos() const + { return static_cast<size_type>((m_pcur + 1) - m_pbeg); } + + reference get_val() + { return *m_valueit; } + + T *const m_pbeg; + T *m_pcur; + BiDirValueIt m_valueit; + Comp m_cmp; +}; + } //namespace container_detail { template<class Pointer, bool IsConst> @@ -640,6 +705,13 @@ 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 container_detail::version<Allocator>::type alloc_version; typedef boost::container::container_detail::vector_alloc_holder<Allocator> alloc_holder_t; alloc_holder_t m_holder; @@ -1043,10 +1115,11 @@ class vector //! //! <b>Note</b>: Non-standard extension to support static_vector template<class OtherAllocator> - typename container_detail::enable_if_c - < container_detail::is_version<OtherAllocator, 0>::value && - !container_detail::is_same<OtherAllocator, allocator_type>::value - , vector& >::type + typename container_detail::enable_if_and + < vector& + , container_detail::is_version<OtherAllocator, 0> + , container_detail::is_different<OtherAllocator, allocator_type> + >::type operator=(BOOST_RV_REF_BEG vector<value_type, OtherAllocator> BOOST_RV_REF_END x) { this->priv_move_assign(boost::move(x)); @@ -1064,10 +1137,11 @@ class vector //! //! <b>Note</b>: Non-standard extension to support static_vector template<class OtherAllocator> - typename container_detail::enable_if_c - < container_detail::is_version<OtherAllocator, 0>::value && - !container_detail::is_same<OtherAllocator, allocator_type>::value - , vector& >::type + typename container_detail::enable_if_and + < vector& + , container_detail::is_version<OtherAllocator, 0> + , container_detail::is_different<OtherAllocator, allocator_type> + >::type operator=(const vector<value_type, OtherAllocator> &x) { this->priv_copy_assign(x); @@ -1084,11 +1158,15 @@ 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::enable_if_c - < !container_detail::is_convertible<InIt BOOST_MOVE_I size_type>::value && - ( container_detail::is_input_iterator<InIt>::value || - container_detail::is_same<alloc_version BOOST_MOVE_I version_0>::value ) - >::type * = 0) ) + BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename container_detail::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> + > + >::type * = 0) + ) { //Overwrite all elements we can from [first, last) iterator cur = this->begin(); @@ -1129,10 +1207,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::enable_if_c - < !container_detail::is_convertible<FwdIt BOOST_MOVE_I size_type>::value && - ( !container_detail::is_input_iterator<FwdIt>::value && - !container_detail::is_same<alloc_version BOOST_MOVE_I version_0>::value ) + BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename container_detail::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> >::type * = 0) ) { @@ -1791,10 +1870,13 @@ class vector //! <b>Complexity</b>: Linear to boost::container::iterator_distance [first, last). template <class InIt> iterator insert(const_iterator pos, InIt first, InIt last - BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename container_detail::enable_if_c - < !container_detail::is_convertible<InIt BOOST_MOVE_I size_type>::value - && container_detail::is_input_iterator<InIt>::value - >::type * = 0) + #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) + , typename container_detail::disable_if_or + < void + , container_detail::is_convertible<InIt, size_type> + , container_detail::is_not_input_iterator<InIt> + >::type * = 0 + #endif ) { const size_type n_pos = pos - this->cbegin(); @@ -1809,9 +1891,10 @@ class vector #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) template <class FwdIt> iterator insert(const_iterator pos, FwdIt first, FwdIt last - , typename container_detail::enable_if_c - < !container_detail::is_convertible<FwdIt, size_type>::value - && !container_detail::is_input_iterator<FwdIt>::value + , typename container_detail::disable_if_or + < void + , container_detail::is_convertible<FwdIt, size_type> + , container_detail::is_input_iterator<FwdIt> >::type * = 0 ) { @@ -1902,7 +1985,7 @@ class vector T* const first_ptr = container_detail::to_raw_pointer(vector_iterator_get_ptr(first)); T* const last_ptr = container_detail::to_raw_pointer(vector_iterator_get_ptr(last)); T* const ptr = container_detail::to_raw_pointer(boost::container::move(last_ptr, old_end_ptr, first_ptr)); - this->priv_destroy_last_n(old_end_ptr - ptr, last_ptr == old_end_ptr); + this->priv_destroy_last_n(old_end_ptr - ptr); } return iterator(vector_iterator_get_ptr(first)); } @@ -1931,9 +2014,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_c - < container_detail::is_version<OtherAllocator, 0>::value && - !container_detail::is_same<OtherAllocator, allocator_type>::value >::type * = 0 + , typename container_detail::enable_if_and + < void + , container_detail::is_version<OtherAllocator, 0> + , container_detail::is_different<OtherAllocator, allocator_type> + >::type * = 0 ) { this->m_holder.deep_swap(x.m_holder); } @@ -2017,12 +2102,36 @@ class vector template<class BiDirPosConstIt, class BiDirValueIt> 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; + 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 BidirIt, class Compare> + void merge(BidirIt first, BidirIt last, Compare comp) + { this->priv_merge(container_detail::false_type(), first, last, comp); } + + template<class BidirIt> + void merge_unique(BidirIt first, BidirIt last) + { this->priv_merge(container_detail::true_type(), first, last, value_less()); } + + template<class BidirIt, class Compare> + void merge_unique(BidirIt first, BidirIt last, Compare comp) + { this->priv_merge(container_detail::true_type(), first, last, comp); } + + private: + template<class PositionValue> + void priv_insert_ordered_at(const size_type element_count, PositionValue position_value) + { const size_type old_size_pos = this->size(); this->reserve(old_size_pos + element_count); T* const begin_ptr = container_detail::to_raw_pointer(this->m_holder.start()); size_type insertions_left = element_count; - size_type next_pos = old_size_pos; - size_type hole_size = element_count; + size_type prev_pos = old_size_pos; + size_type old_hole_size = element_count; //Exception rollback. If any copy throws before the hole is filled, values //already inserted/copied at the end of the buffer will be destroyed. @@ -2031,52 +2140,197 @@ class vector //Loop for each insertion backwards, first moving the elements after the insertion point, //then inserting the element. while(insertions_left){ - size_type pos = static_cast<size_type>(*(--last_position_it)); - while(pos == size_type(-1)){ - --last_value_it; - pos = static_cast<size_type>(*(--last_position_it)); - } - - BOOST_ASSERT(pos != size_type(-1) && pos <= old_size_pos); + --position_value; + size_type const pos = position_value.get_pos(); + BOOST_ASSERT(pos != size_type(-1) && pos <= old_size_pos && pos <= prev_pos); //If needed shift the range after the insertion point and the previous insertion point. //Function will take care if the shift crosses the size() boundary, using copy/move //or uninitialized copy/move if necessary. - size_type new_hole_size = (pos != next_pos) - ? priv_insert_ordered_at_shift_range(pos, next_pos, this->size(), insertions_left) - : hole_size + size_type new_hole_size = (pos != prev_pos) + ? priv_insert_ordered_at_shift_range(pos, prev_pos, this->size(), insertions_left) + : old_hole_size ; - if(new_hole_size > 0){ + if(new_hole_size){ //The hole was reduced by priv_insert_ordered_at_shift_range so expand exception rollback range backwards - past_hole_values_destroyer.increment_size_backwards(next_pos - pos); + past_hole_values_destroyer.increment_size_backwards(prev_pos - pos); //Insert the new value in the hole - allocator_traits_type::construct(this->m_holder.alloc(), begin_ptr + pos + insertions_left - 1, *(--last_value_it)); - --new_hole_size; - if(new_hole_size == 0){ + allocator_traits_type::construct(this->m_holder.alloc(), begin_ptr + pos + insertions_left - 1, position_value.get_val()); + if(--new_hole_size){ + //The hole was reduced by the new insertion by one + past_hole_values_destroyer.increment_size_backwards(size_type(1u)); + } + else{ //Hole was just filled, disable exception rollback and change vector size past_hole_values_destroyer.release(); this->m_holder.m_size += element_count; } - else{ - //The hole was reduced by the new insertion by one - past_hole_values_destroyer.increment_size_backwards(size_type(1u)); - } } else{ - if(hole_size){ + if(old_hole_size){ //Hole was just filled by priv_insert_ordered_at_shift_range, disable exception rollback and change vector size past_hole_values_destroyer.release(); this->m_holder.m_size += element_count; } //Insert the new value in the already constructed range - begin_ptr[pos + insertions_left - 1] = *(--last_value_it); + begin_ptr[pos + insertions_left - 1] = position_value.get_val(); } --insertions_left; - hole_size = new_hole_size; - next_pos = pos; + old_hole_size = new_hole_size; + prev_pos = pos; } } - private: + template<class UniqueBool, class BidirIt, class Compare> + void priv_merge(UniqueBool, BidirIt first, BidirIt last, Compare comp) + { + size_type const n = static_cast<size_type>(boost::container::iterator_distance(first, last)); + if(BOOST_LIKELY(n)){ + 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, + //or there is no room for position indexes + bool new_buffer = false; + if(free_c < n){ + new_buffer = true; + } + else if(!UniqueBool::value && free_c >= n){ + typedef container_detail::vector_merge_cursor<T, size_type, BidirIt, Compare> inserter_t; + T* const pbeg = container_detail::to_raw_pointer(m_holder.start()); + return this->priv_insert_ordered_at(n, inserter_t(pbeg, pbeg + s, last, comp)); + } + else if(UniqueBool::value){ //Query for room to store n + 1 indexes (+1 to guarantee potential alignment overhead). + //No need to destroy them as they are integral types, which simplifies things a lot. + std::size_t const sz_vlt = sizeof(value_type); + std::size_t const sz_szt = sizeof(size_type); + new_buffer = (c-s-n)*sz_vlt/sz_szt < (n+1); + } + + if(new_buffer){ + size_type const new_size = s + n; + size_type new_cap = new_size; + pointer p = pointer(); + p = this->m_holder.allocation_command(allocate_new, new_size, new_cap, p); + this->priv_merge_in_new_buffer(UniqueBool(), first, n, comp, p, new_cap); + } + else{ + //Use trailing memory to store position offsets + uintptr_t const szt_align_mask = container_detail::alignment_of<size_type>::value - 1; + boost::uintptr_t const addr = boost::uintptr_t(container_detail::to_raw_pointer(m_holder.start()) + s + n); + //Align memory before casting to address + size_type *const paddr = reinterpret_cast<size_type *>((addr + szt_align_mask) & ~szt_align_mask); + this->priv_insert_ordered_range(UniqueBool(), n, first, last, paddr, comp); + } + } + else{ + this->insert(this->cend(), n, first, last); + } + } + } + + template <class UniqueBool, class BidirIt, class Compare> + void priv_insert_ordered_range + (UniqueBool, size_type const n, BidirIt first, BidirIt const last, size_type positions[], Compare comp) + { + //Linear: at most N + M -1 comparisons + //Log: MlogN + //Average + //Linear: N + M - 2 + //Log: MlogN + //N+M - 2 + //N + //(N+M)/2 < MlogN + //(N/M+1)/2 <= logN + //bool const linear = !s || !n || (s <= n) || ((s+n)/n/2 < logN); + size_type const s = this->size(); + size_type remaining = n; + T* const pbeg = container_detail::to_raw_pointer(m_holder.start()); + T* const pend = pbeg + s; + T* pcur = pbeg; + size_type *position = positions; + size_type added_in_middle = 0; + if(first != last && pcur != pend){ + while(1){ + //maintain stability moving external values only if they are strictly less + if(comp(*first, *pcur)) { + *position = static_cast<size_type>(pcur - pbeg); + BOOST_ASSERT((position == positions) || (*(position-1) == size_type(-1)) || (*(position-1) <= *position)); + ++position; + ++added_in_middle; + --remaining; + if(++first == last) break; + } + else if(UniqueBool::value && !comp(*pcur, *first)){ + *position = size_type(-1); + ++position; + --remaining; + if(++first == last) break; + } + else{ + if(++pcur == pend) break; + } + } + } + this->insert_ordered_at(added_in_middle, position, first); + this->insert(this->cend(), remaining, first, last); + } + + template<class UniqueBool, class FwdIt, class Compare> + void priv_merge_in_new_buffer + (UniqueBool, FwdIt first, size_type n, Compare comp, pointer new_storage, size_type const new_cap) + { + BOOST_ASSERT((new_cap >= this->size() ) && (new_cap - this->size()) >= n); + allocator_type &a = this->m_holder.alloc(); + typename value_traits::ArrayDeallocator new_buffer_deallocator(new_storage, a, new_cap); + typename value_traits::ArrayDestructor new_values_destroyer(new_storage, a, 0u); + T* pbeg = container_detail::to_raw_pointer(m_holder.start()); + size_type const old_size = this->size(); + T* const pend = pbeg + old_size; + T* d_first = container_detail::to_raw_pointer(new_storage); + size_type added = n; + //Merge in new buffer loop + while(1){ + if(!n) { + ::boost::container::uninitialized_move_alloc(this->m_holder.alloc(), pbeg, pend, d_first); + break; + } + else if(pbeg == pend) { + ::boost::container::uninitialized_move_alloc_n(this->m_holder.alloc(), first, n, d_first); + break; + } + //maintain stability moving external values only if they are strictly less + else if(comp(*first, *pbeg)) { + allocator_traits_type::construct( this->m_holder.alloc(), d_first, ::boost::move(*first) ); + new_values_destroyer.increment_size(1u); + ++first; + --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); + ++pbeg; + ++d_first; + } + } + + //Nothrow operations + pointer const old_p = this->m_holder.start(); + size_type const old_cap = this->m_holder.capacity(); + boost::container::destroy_alloc_n(a, container_detail::to_raw_pointer(old_p), old_size); + a.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); + new_buffer_deallocator.release(); + new_values_destroyer.release(); + } bool room_enough() const { return this->m_holder.m_size < this->m_holder.capacity(); } @@ -2113,9 +2367,11 @@ 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 && - container_detail::is_same<OtherAllocator, allocator_type>::value>::type * = 0) + , typename container_detail::disable_if_or + < void + , container_detail::is_version<OtherAllocator, 0> + , container_detail::is_different<OtherAllocator, allocator_type> + >::type * = 0) { //for move constructor, no aliasing (&x != this) is assummed. BOOST_ASSERT(this != &x); @@ -2167,10 +2423,12 @@ class vector } 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 && - container_detail::is_same<OtherAllocator, allocator_type>::value >::type * = 0) + typename container_detail::disable_if_or + < void + , container_detail::is_version<OtherAllocator, 0> + , container_detail::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(); @@ -2274,16 +2532,7 @@ class vector } } - void priv_destroy_last() BOOST_NOEXCEPT_OR_NOTHROW - { - if(!value_traits::trivial_dctr){ - value_type* const p = this->back_raw() - 1; - allocator_traits_type::destroy(this->get_stored_allocator(), p); - } - --this->m_holder.m_size; - } - - void priv_destroy_last(const bool moved) BOOST_NOEXCEPT_OR_NOTHROW + 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))){ @@ -2303,17 +2552,6 @@ class vector this->m_holder.m_size -= n; } - void priv_destroy_last_n(const size_type n, const bool moved) BOOST_NOEXCEPT_OR_NOTHROW - { - BOOST_ASSERT(n <= this->m_holder.m_size); - (void)moved; - if(!(value_traits::trivial_dctr || (value_traits::trivial_dctr_after_move && moved))){ - T* const destroy_pos = container_detail::to_raw_pointer(this->m_holder.start()) + (this->m_holder.m_size-n); - boost::container::destroy_alloc_n(this->get_stored_allocator(), destroy_pos, n); - } - this->m_holder.m_size -= n; - } - template<class InpIt> void priv_uninitialized_construct_at_end(InpIt first, InpIt last) { @@ -2554,69 +2792,6 @@ class vector return this->priv_forward_range_insert(this->back_ptr(), n, insert_range_proxy); } - //Absolutely experimental. This function might change, disappear or simply crash! - template<class BiDirPosConstIt, class BiDirSkipConstIt, class BiDirValueIt> - void priv_insert_ordered_at( size_type element_count, BiDirPosConstIt last_position_it - , bool do_skip, BiDirSkipConstIt last_skip_it, BiDirValueIt last_value_it) - { - const size_type old_size_pos = this->size(); - this->reserve(old_size_pos + element_count); - T* const begin_ptr = container_detail::to_raw_pointer(this->m_holder.start()); - size_type insertions_left = element_count; - size_type next_pos = old_size_pos; - size_type hole_size = element_count; - - //Exception rollback. If any copy throws before the hole is filled, values - //already inserted/copied at the end of the buffer will be destroyed. - typename value_traits::ArrayDestructor past_hole_values_destroyer - (begin_ptr + old_size_pos + element_count, this->m_holder.alloc(), size_type(0u)); - //Loop for each insertion backwards, first moving the elements after the insertion point, - //then inserting the element. - while(insertions_left){ - if(do_skip){ - size_type n = *(--last_skip_it); - boost::container::iterator_advance(last_value_it, -difference_type(n)); - } - const size_type pos = static_cast<size_type>(*(--last_position_it)); - BOOST_ASSERT(pos <= old_size_pos); - //If needed shift the range after the insertion point and the previous insertion point. - //Function will take care if the shift crosses the size() boundary, using copy/move - //or uninitialized copy/move if necessary. - size_type new_hole_size = (pos != next_pos) - ? priv_insert_ordered_at_shift_range(pos, next_pos, this->size(), insertions_left) - : hole_size - ; - if(new_hole_size > 0){ - //The hole was reduced by priv_insert_ordered_at_shift_range so expand exception rollback range backwards - past_hole_values_destroyer.increment_size_backwards(next_pos - pos); - //Insert the new value in the hole - allocator_traits_type::construct(this->m_holder.alloc(), begin_ptr + pos + insertions_left - 1, *(--last_value_it)); - --new_hole_size; - if(new_hole_size == 0){ - //Hole was just filled, disable exception rollback and change vector size - past_hole_values_destroyer.release(); - this->m_holder.m_size += element_count; - } - else{ - //The hole was reduced by the new insertion by one - past_hole_values_destroyer.increment_size_backwards(size_type(1u)); - } - } - else{ - if(hole_size){ - //Hole was just filled by priv_insert_ordered_at_shift_range, disable exception rollback and change vector size - past_hole_values_destroyer.release(); - this->m_holder.m_size += element_count; - } - //Insert the new value in the already constructed range - begin_ptr[pos + insertions_left - 1] = *(--last_value_it); - } - --insertions_left; - hole_size = new_hole_size; - next_pos = pos; - } - } - //Takes the range pointed by [first_pos, last_pos) and shifts it to the right //by 'shift_count'. 'limit_pos' marks the end of constructed elements. // @@ -2647,7 +2822,7 @@ class vector // |_>_>_>_>_>^ // // - //New situation in Case B (hole_size > 0): + //New situation in Case B (hole_size >= 0): // range is moved through uninitialized moves // // first_pos last_pos limit_pos @@ -2689,7 +2864,7 @@ class vector //All uninitialized_moved ::boost::container::uninitialized_move_alloc (this->m_holder.alloc(), first_ptr, last_ptr, first_ptr + shift_count); - hole_size = last_pos + shift_count - limit_pos; + hole_size = first_pos + shift_count - limit_pos; } //Case C: else{ @@ -2716,7 +2891,7 @@ class vector void priv_forward_range_insert_expand_forward(T* const pos, const size_type n, InsertionProxy insert_range_proxy) { //n can't be 0, because there is nothing to do in that case - if(!n) return; + if(BOOST_UNLIKELY(!n)) return; //There is enough memory T* const old_finish = this->back_raw(); const size_type elems_after = old_finish - pos; |