diff options
Diffstat (limited to 'boost/container/detail/flat_tree.hpp')
-rw-r--r-- | boost/container/detail/flat_tree.hpp | 239 |
1 files changed, 128 insertions, 111 deletions
diff --git a/boost/container/detail/flat_tree.hpp b/boost/container/detail/flat_tree.hpp index a6f7568b43..a94043c6bd 100644 --- a/boost/container/detail/flat_tree.hpp +++ b/boost/container/detail/flat_tree.hpp @@ -11,7 +11,11 @@ #ifndef BOOST_CONTAINER_FLAT_TREE_HPP #define BOOST_CONTAINER_FLAT_TREE_HPP -#if defined(_MSC_VER) +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif @@ -20,29 +24,29 @@ #include <boost/container/container_fwd.hpp> -#include <algorithm> -#include <functional> -#include <utility> - -#include <boost/type_traits/has_trivial_destructor.hpp> #include <boost/move/utility_core.hpp> -#include <boost/container/detail/utilities.hpp> #include <boost/container/detail/pair.hpp> #include <boost/container/vector.hpp> #include <boost/container/detail/value_init.hpp> #include <boost/container/detail/destroyers.hpp> +#include <boost/container/detail/algorithm.hpp> //algo_equal(), algo_lexicographical_compare +#include <boost/container/detail/iterator.hpp> #include <boost/container/allocator_traits.hpp> #ifdef BOOST_CONTAINER_VECTOR_ITERATOR_IS_POINTER #include <boost/intrusive/pointer_traits.hpp> #endif -#include <boost/aligned_storage.hpp> +#include <boost/container/detail/type_traits.hpp> #include <boost/move/make_unique.hpp> +#include <boost/move/adl_move_swap.hpp> +#if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) +#include <boost/move/detail/fwd_macros.hpp> +#endif -namespace boost { +#include <boost/intrusive/detail/minimal_pair_header.hpp> //pair +namespace boost { namespace container { - namespace container_detail { template<class Compare, class Value, class KeyOfValue> @@ -78,30 +82,29 @@ template<class Pointer> struct get_flat_tree_iterators { #ifdef BOOST_CONTAINER_VECTOR_ITERATOR_IS_POINTER - typedef Pointer iterator; + typedef Pointer iterator; typedef typename boost::intrusive:: - pointer_traits<Pointer>::element_type iterator_element_type; + pointer_traits<Pointer>::element_type iterator_element_type; typedef typename boost::intrusive:: pointer_traits<Pointer>:: template - rebind_pointer<const iterator_element_type>::type const_iterator; + rebind_pointer<const iterator_element_type>::type const_iterator; #else //BOOST_CONTAINER_VECTOR_ITERATOR_IS_POINTER typedef typename boost::container::container_detail:: - vec_iterator<Pointer, false> iterator; + vec_iterator<Pointer, false> iterator; typedef typename boost::container::container_detail:: - vec_iterator<Pointer, true > const_iterator; + vec_iterator<Pointer, true > const_iterator; #endif //BOOST_CONTAINER_VECTOR_ITERATOR_IS_POINTER - typedef boost::container::container_detail:: - reverse_iterator<iterator> reverse_iterator; - typedef boost::container::container_detail:: - reverse_iterator<const_iterator> const_reverse_iterator; + typedef boost::container::reverse_iterator<iterator> reverse_iterator; + typedef boost::container::reverse_iterator<const_iterator> const_reverse_iterator; }; template <class Key, class Value, class KeyOfValue, - class Compare, class A> + class Compare, class Allocator> class flat_tree { - typedef boost::container::vector<Value, A> vector_t; - typedef A allocator_t; + typedef boost::container::vector<Value, Allocator> vector_t; + typedef Allocator allocator_t; + typedef allocator_traits<Allocator> allocator_traits_type; public: typedef flat_tree_value_compare<Compare, Value, KeyOfValue> value_compare; @@ -126,11 +129,11 @@ class flat_tree : value_compare(boost::move(static_cast<value_compare&>(d))), m_vect(boost::move(d.m_vect)) {} - Data(const Data &d, const A &a) + Data(const Data &d, const Allocator &a) : value_compare(static_cast<const value_compare&>(d)), m_vect(d.m_vect, a) {} - Data(BOOST_RV_REF(Data) d, const A &a) + Data(BOOST_RV_REF(Data) d, const Allocator &a) : value_compare(boost::move(static_cast<value_compare&>(d))), m_vect(boost::move(d.m_vect), a) {} @@ -163,7 +166,7 @@ class flat_tree void swap(Data &d) { value_compare& mycomp = *this, & othercomp = d; - boost::container::swap_dispatch(mycomp, othercomp); + boost::adl_move_swap(mycomp, othercomp); this->m_vect.swap(d.m_vect); } @@ -265,8 +268,10 @@ class flat_tree flat_tree& operator=(BOOST_COPY_ASSIGN_REF(flat_tree) x) { m_data = x.m_data; return *this; } - flat_tree& operator=(BOOST_RV_REF(flat_tree) mx) - { m_data = boost::move(mx.m_data); return *this; } + flat_tree& operator=(BOOST_RV_REF(flat_tree) x) + BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value + && boost::container::container_detail::is_nothrow_move_assignable<Compare>::value ) + { m_data = boost::move(x.m_data); return *this; } public: // accessors: @@ -331,6 +336,8 @@ class flat_tree { return this->m_data.m_vect.max_size(); } void swap(flat_tree& other) + BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value + && boost::container::container_detail::is_nothrow_swappable<Compare>::value ) { this->m_data.swap(other.m_data); } public: @@ -428,7 +435,7 @@ class flat_tree #endif ) { - const size_type len = static_cast<size_type>(std::distance(first, last)); + const size_type len = static_cast<size_type>(boost::container::iterator_distance(first, last)); this->reserve(this->size()+len); this->priv_insert_equal_loop(first, last); } @@ -455,7 +462,7 @@ class flat_tree #endif ) { - const size_type len = static_cast<size_type>(std::distance(first, last)); + const size_type len = static_cast<size_type>(boost::container::iterator_distance(first, last)); this->reserve(this->size()+len); this->priv_insert_equal_loop_ordered(first, last); } @@ -499,12 +506,12 @@ class flat_tree ) { this->priv_insert_ordered_range(true, first, last); } - #ifdef BOOST_CONTAINER_PERFECT_FORWARDING + #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) template <class... Args> - std::pair<iterator, bool> emplace_unique(Args&&... args) + std::pair<iterator, bool> emplace_unique(BOOST_FWD_REF(Args)... args) { - aligned_storage<sizeof(value_type), alignment_of<value_type>::value> v; + typename aligned_storage<sizeof(value_type), alignment_of<value_type>::value>::type v; value_type &val = *static_cast<value_type *>(static_cast<void *>(&v)); stored_allocator_type &a = this->get_stored_allocator(); stored_allocator_traits::construct(a, &val, ::boost::forward<Args>(args)... ); @@ -513,9 +520,9 @@ class flat_tree } template <class... Args> - iterator emplace_hint_unique(const_iterator hint, Args&&... args) + iterator emplace_hint_unique(const_iterator hint, BOOST_FWD_REF(Args)... args) { - aligned_storage<sizeof(value_type), alignment_of<value_type>::value> v; + typename aligned_storage<sizeof(value_type), alignment_of<value_type>::value>::type v; value_type &val = *static_cast<value_type *>(static_cast<void *>(&v)); stored_allocator_type &a = this->get_stored_allocator(); stored_allocator_traits::construct(a, &val, ::boost::forward<Args>(args)... ); @@ -524,9 +531,9 @@ class flat_tree } template <class... Args> - iterator emplace_equal(Args&&... args) + iterator emplace_equal(BOOST_FWD_REF(Args)... args) { - aligned_storage<sizeof(value_type), alignment_of<value_type>::value> v; + typename aligned_storage<sizeof(value_type), alignment_of<value_type>::value>::type v; value_type &val = *static_cast<value_type *>(static_cast<void *>(&v)); stored_allocator_type &a = this->get_stored_allocator(); stored_allocator_traits::construct(a, &val, ::boost::forward<Args>(args)... ); @@ -535,9 +542,9 @@ class flat_tree } template <class... Args> - iterator emplace_hint_equal(const_iterator hint, Args&&... args) + iterator emplace_hint_equal(const_iterator hint, BOOST_FWD_REF(Args)... args) { - aligned_storage<sizeof(value_type), alignment_of<value_type>::value> v; + typename aligned_storage<sizeof(value_type), alignment_of<value_type>::value>::type v; value_type &val = *static_cast<value_type *>(static_cast<void *>(&v)); stored_allocator_type &a = this->get_stored_allocator(); stored_allocator_traits::construct(a, &val, ::boost::forward<Args>(args)... ); @@ -545,64 +552,57 @@ class flat_tree return this->insert_equal(hint, ::boost::move(val)); } - #else //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING - - #define BOOST_PP_LOCAL_MACRO(n) \ - BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \ - std::pair<iterator, bool> \ - emplace_unique(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \ - { \ - aligned_storage<sizeof(value_type), alignment_of<value_type>::value> v; \ - value_type &val = *static_cast<value_type *>(static_cast<void *>(&v)); \ - stored_allocator_type &a = this->get_stored_allocator(); \ - stored_allocator_traits::construct(a, &val \ - BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _) ); \ - value_destructor<stored_allocator_type> d(a, val); \ - return this->insert_unique(::boost::move(val)); \ - } \ - \ - BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \ - iterator emplace_hint_unique(const_iterator hint \ - BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \ - { \ - aligned_storage<sizeof(value_type), alignment_of<value_type>::value> v; \ - value_type &val = *static_cast<value_type *>(static_cast<void *>(&v)); \ - stored_allocator_type &a = this->get_stored_allocator(); \ - stored_allocator_traits::construct(a, &val \ - BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _) ); \ - value_destructor<stored_allocator_type> d(a, val); \ - return this->insert_unique(hint, ::boost::move(val)); \ - } \ - \ - BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \ - iterator emplace_equal(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \ - { \ - aligned_storage<sizeof(value_type), alignment_of<value_type>::value> v; \ - value_type &val = *static_cast<value_type *>(static_cast<void *>(&v)); \ - stored_allocator_type &a = this->get_stored_allocator(); \ - stored_allocator_traits::construct(a, &val \ - BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _) ); \ - value_destructor<stored_allocator_type> d(a, val); \ - return this->insert_equal(::boost::move(val)); \ - } \ - \ - BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \ - iterator emplace_hint_equal(const_iterator hint \ - BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \ - { \ - aligned_storage<sizeof(value_type), alignment_of<value_type>::value> v; \ - value_type &val = *static_cast<value_type *>(static_cast<void *>(&v)); \ - stored_allocator_type &a = this->get_stored_allocator(); \ - stored_allocator_traits::construct(a, &val \ - BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _) ); \ - value_destructor<stored_allocator_type> d(a, val); \ - return this->insert_equal(hint, ::boost::move(val)); \ - } \ - //! - #define BOOST_PP_LOCAL_LIMITS (0, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS) - #include BOOST_PP_LOCAL_ITERATE() - - #endif //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING + #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) + + #define BOOST_CONTAINER_FLAT_TREE_EMPLACE_CODE(N) \ + BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ + std::pair<iterator, bool> emplace_unique(BOOST_MOVE_UREF##N)\ + {\ + typename aligned_storage<sizeof(value_type), alignment_of<value_type>::value>::type v;\ + value_type &val = *static_cast<value_type *>(static_cast<void *>(&v));\ + stored_allocator_type &a = this->get_stored_allocator();\ + stored_allocator_traits::construct(a, &val BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ + value_destructor<stored_allocator_type> d(a, val);\ + return this->insert_unique(::boost::move(val));\ + }\ + \ + BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ + iterator emplace_hint_unique(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ + {\ + typename aligned_storage<sizeof(value_type), alignment_of<value_type>::value>::type v;\ + value_type &val = *static_cast<value_type *>(static_cast<void *>(&v));\ + stored_allocator_type &a = this->get_stored_allocator();\ + stored_allocator_traits::construct(a, &val BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ + value_destructor<stored_allocator_type> d(a, val);\ + return this->insert_unique(hint, ::boost::move(val));\ + }\ + \ + BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ + iterator emplace_equal(BOOST_MOVE_UREF##N)\ + {\ + typename aligned_storage<sizeof(value_type), alignment_of<value_type>::value>::type v;\ + value_type &val = *static_cast<value_type *>(static_cast<void *>(&v));\ + stored_allocator_type &a = this->get_stored_allocator();\ + stored_allocator_traits::construct(a, &val BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ + value_destructor<stored_allocator_type> d(a, val);\ + return this->insert_equal(::boost::move(val));\ + }\ + \ + BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ + iterator emplace_hint_equal(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ + {\ + typename aligned_storage <sizeof(value_type), alignment_of<value_type>::value>::type v;\ + value_type &val = *static_cast<value_type *>(static_cast<void *>(&v));\ + stored_allocator_type &a = this->get_stored_allocator();\ + stored_allocator_traits::construct(a, &val BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ + value_destructor<stored_allocator_type> d(a, val);\ + return this->insert_equal(hint, ::boost::move(val));\ + }\ + // + BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_FLAT_TREE_EMPLACE_CODE) + #undef BOOST_CONTAINER_FLAT_TREE_EMPLACE_CODE + + #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) iterator erase(const_iterator position) { return this->m_data.m_vect.erase(position); } @@ -632,6 +632,18 @@ class flat_tree void shrink_to_fit() { this->m_data.m_vect.shrink_to_fit(); } + iterator nth(size_type n) BOOST_NOEXCEPT_OR_NOTHROW + { return this->m_data.m_vect.nth(n); } + + const_iterator nth(size_type n) const BOOST_NOEXCEPT_OR_NOTHROW + { return this->m_data.m_vect.nth(n); } + + size_type index_of(iterator p) BOOST_NOEXCEPT_OR_NOTHROW + { return this->m_data.m_vect.index_of(p); } + + size_type index_of(const_iterator p) const BOOST_NOEXCEPT_OR_NOTHROW + { return this->m_data.m_vect.index_of(p); } + // set operations: iterator find(const key_type& k) { @@ -694,13 +706,12 @@ class flat_tree friend bool operator==(const flat_tree& x, const flat_tree& y) { - return x.size() == y.size() && std::equal(x.begin(), x.end(), y.begin()); + return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin()); } friend bool operator<(const flat_tree& x, const flat_tree& y) { - return std::lexicographical_compare(x.begin(), x.end(), - y.begin(), y.end()); + return ::boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); } friend bool operator!=(const flat_tree& x, const flat_tree& y) @@ -936,7 +947,7 @@ class flat_tree template <class BidirIt> void priv_insert_ordered_range(const bool unique_values, BidirIt first, BidirIt last) { - size_type len = static_cast<size_type>(std::distance(first, 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. @@ -955,10 +966,10 @@ class flat_tree size_type unique_burst = 0u; size_type checked = 0; for(; checked != burst; ++checked){ - //Get the insertion position for each key, use std::iterator_traits<BidirIt>::value_type + //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<A, B> -> boost::container::pair<A, B> - const typename std::iterator_traits<BidirIt>::value_type & val = *first; + //(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){ @@ -984,7 +995,11 @@ class flat_tree while(len--){ BidirIt next(first); ++next; - if(next == last || val_cmp(*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); @@ -994,7 +1009,7 @@ class flat_tree BOOST_ASSERT(first == last); } else{ - BOOST_ASSERT(size_type(std::distance(first, last)) == len); + 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); } @@ -1004,16 +1019,18 @@ class flat_tree } //namespace container_detail { } //namespace container { -/* + //!has_trivial_destructor_after_move<> == true_type //!specialization for optimizations -template <class K, class V, class KOV, -class C, class A> -struct has_trivial_destructor_after_move<boost::container::container_detail::flat_tree<K, V, KOV, C, A> > +template <class Key, class T, class KeyOfValue, +class Compare, class Allocator> +struct has_trivial_destructor_after_move<boost::container::container_detail::flat_tree<Key, T, KeyOfValue, Compare, Allocator> > { - static const bool value = has_trivial_destructor_after_move<A>::value && has_trivial_destructor_after_move<C>::value; + typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer; + static const bool value = ::boost::has_trivial_destructor_after_move<Allocator>::value && + ::boost::has_trivial_destructor_after_move<pointer>::value; }; -*/ + } //namespace boost { #include <boost/container/detail/config_end.hpp> |