diff options
Diffstat (limited to 'boost/container/detail')
| -rw-r--r-- | boost/container/detail/addressof.hpp | 4 | ||||
| -rw-r--r-- | boost/container/detail/advanced_insert_int.hpp | 4 | ||||
| -rw-r--r-- | boost/container/detail/compare_functors.hpp | 8 | ||||
| -rw-r--r-- | boost/container/detail/construct_in_place.hpp | 44 | ||||
| -rw-r--r-- | boost/container/detail/copy_move_algo.hpp | 12 | ||||
| -rw-r--r-- | boost/container/detail/dispatch_uses_allocator.hpp | 136 | ||||
| -rw-r--r-- | boost/container/detail/flat_tree.hpp | 319 | ||||
| -rw-r--r-- | boost/container/detail/is_sorted.hpp | 57 | ||||
| -rw-r--r-- | boost/container/detail/iterators.hpp | 56 | ||||
| -rw-r--r-- | boost/container/detail/mpl.hpp | 15 | ||||
| -rw-r--r-- | boost/container/detail/node_alloc_holder.hpp | 13 | ||||
| -rw-r--r-- | boost/container/detail/pair.hpp | 197 | ||||
| -rw-r--r-- | boost/container/detail/tree.hpp | 430 | ||||
| -rw-r--r-- | boost/container/detail/value_init.hpp | 2 | ||||
| -rw-r--r-- | boost/container/detail/variadic_templates_tools.hpp | 23 | ||||
| -rw-r--r-- | boost/container/detail/workaround.hpp | 18 |
16 files changed, 1018 insertions, 320 deletions
diff --git a/boost/container/detail/addressof.hpp b/boost/container/detail/addressof.hpp index cc582c439d..fedbdb91d1 100644 --- a/boost/container/detail/addressof.hpp +++ b/boost/container/detail/addressof.hpp @@ -25,12 +25,12 @@ namespace container { namespace container_detail { template <typename T> -inline T* addressof(T& obj) +BOOST_CONTAINER_FORCEINLINE T* addressof(T& obj) { return static_cast<T*>( static_cast<void*>( const_cast<char*>( - &reinterpret_cast<const char&>(obj) + &reinterpret_cast<const volatile char&>(obj) ))); } diff --git a/boost/container/detail/advanced_insert_int.hpp b/boost/container/detail/advanced_insert_int.hpp index 56df588706..278cd1b3f1 100644 --- a/boost/container/detail/advanced_insert_int.hpp +++ b/boost/container/detail/advanced_insert_int.hpp @@ -236,7 +236,7 @@ struct insert_nonmovable_emplace_proxy { this->priv_uninitialized_copy_some_and_update(a, index_tuple_t(), p, n); } private: - template<int ...IdxPack> + template<std::size_t ...IdxPack> void priv_uninitialized_copy_some_and_update(Allocator &a, const index_tuple<IdxPack...>&, Iterator p, size_type n) { BOOST_ASSERT(n == 1); (void)n; @@ -266,7 +266,7 @@ struct insert_emplace_proxy private: - template<int ...IdxPack> + template<std::size_t ...IdxPack> void priv_copy_some_and_update(Allocator &a, const index_tuple<IdxPack...>&, Iterator p, size_type n) { BOOST_ASSERT(n ==1); (void)n; diff --git a/boost/container/detail/compare_functors.hpp b/boost/container/detail/compare_functors.hpp index 4220d50996..28f9093b9a 100644 --- a/boost/container/detail/compare_functors.hpp +++ b/boost/container/detail/compare_functors.hpp @@ -53,16 +53,16 @@ struct value_to_node_compare {} bool operator()(const Node &a, const Node &b) const - { return static_cast<const Pred&>(*this)(a.m_data, b.m_data); } + { return static_cast<const Pred&>(*this)(a.get_data(), b.get_data()); } bool operator()(const Node &a) const - { return static_cast<const Pred&>(*this)(a.m_data); } + { return static_cast<const Pred&>(*this)(a.get_data()); } bool operator()(const Node &a, const Node &b) - { return static_cast<Pred&>(*this)(a.m_data, b.m_data); } + { return static_cast<Pred&>(*this)(a.get_data(), b.get_data()); } bool operator()(const Node &a) - { return static_cast<Pred&>(*this)(a.m_data); } + { return static_cast<Pred&>(*this)(a.get_data()); } predicate_type & predicate() { return static_cast<predicate_type&>(*this); } const predicate_type & predicate() const { return static_cast<predicate_type&>(*this); } diff --git a/boost/container/detail/construct_in_place.hpp b/boost/container/detail/construct_in_place.hpp index 6cb339519c..9fecd24a8f 100644 --- a/boost/container/detail/construct_in_place.hpp +++ b/boost/container/detail/construct_in_place.hpp @@ -23,16 +23,19 @@ #include <boost/container/allocator_traits.hpp> #include <boost/container/detail/iterators.hpp> +#include <boost/container/detail/value_init.hpp> namespace boost { namespace container { +//In place construction + template<class Allocator, class T, class InpIt> -inline void construct_in_place(Allocator &a, T* dest, InpIt source) +BOOST_CONTAINER_FORCEINLINE void construct_in_place(Allocator &a, T* dest, InpIt source) { boost::container::allocator_traits<Allocator>::construct(a, dest, *source); } template<class Allocator, class T, class U, class D> -inline void construct_in_place(Allocator &a, T *dest, value_init_construct_iterator<U, D>) +BOOST_CONTAINER_FORCEINLINE void construct_in_place(Allocator &a, T *dest, value_init_construct_iterator<U, D>) { boost::container::allocator_traits<Allocator>::construct(a, dest); } @@ -41,7 +44,7 @@ template <class T, class Difference> class default_init_construct_iterator; template<class Allocator, class T, class U, class D> -inline void construct_in_place(Allocator &a, T *dest, default_init_construct_iterator<U, D>) +BOOST_CONTAINER_FORCEINLINE void construct_in_place(Allocator &a, T *dest, default_init_construct_iterator<U, D>) { boost::container::allocator_traits<Allocator>::construct(a, dest, default_init); } @@ -50,13 +53,44 @@ template <class T, class EmplaceFunctor, class Difference> class emplace_iterator; template<class Allocator, class T, class U, class EF, class D> -inline void construct_in_place(Allocator &a, T *dest, emplace_iterator<U, EF, D> ei) +BOOST_CONTAINER_FORCEINLINE void construct_in_place(Allocator &a, T *dest, emplace_iterator<U, EF, D> ei) { ei.construct_in_place(a, dest); } +//Assignment + +template<class DstIt, class InpIt> +BOOST_CONTAINER_FORCEINLINE void assign_in_place(DstIt dest, InpIt source) +{ *dest = *source; } + +template<class DstIt, class U, class D> +BOOST_CONTAINER_FORCEINLINE void assign_in_place(DstIt dest, value_init_construct_iterator<U, D>) +{ + container_detail::value_init<U> val; + *dest = boost::move(val.get()); +} + +template <class DstIt, class Difference> +class default_init_construct_iterator; + +template<class DstIt, class U, class D> +BOOST_CONTAINER_FORCEINLINE void assign_in_place(DstIt dest, default_init_construct_iterator<U, D>) +{ + U u; + *dest = boost::move(u); +} + +template <class T, class EmplaceFunctor, class Difference> +class emplace_iterator; + +template<class DstIt, class U, class EF, class D> +BOOST_CONTAINER_FORCEINLINE void assign_in_place(DstIt dest, emplace_iterator<U, EF, D> ei) +{ + ei.assign_in_place(dest); +} + } //namespace container { } //namespace boost { #endif //#ifndef BOOST_CONTAINER_DETAIL_CONSTRUCT_IN_PLACE_HPP - diff --git a/boost/container/detail/copy_move_algo.hpp b/boost/container/detail/copy_move_algo.hpp index f590a8aaf3..ead93c6035 100644 --- a/boost/container/detail/copy_move_algo.hpp +++ b/boost/container/detail/copy_move_algo.hpp @@ -7,8 +7,8 @@ // See http://www.boost.org/libs/container for documentation. // ////////////////////////////////////////////////////////////////////////////// -#ifndef BOOST_CONTAINER_DETAIL_UTILITIES_HPP -#define BOOST_CONTAINER_DETAIL_UTILITIES_HPP +#ifndef BOOST_CONTAINER_DETAIL_COPY_MOVE_ALGO_HPP +#define BOOST_CONTAINER_DETAIL_COPY_MOVE_ALGO_HPP #ifndef BOOST_CONFIG_HPP # include <boost/config.hpp> @@ -25,6 +25,8 @@ #include <boost/container/detail/iterator_to_raw_pointer.hpp> #include <boost/container/detail/mpl.hpp> #include <boost/container/detail/type_traits.hpp> +#include <boost/container/detail/construct_in_place.hpp> + // move #include <boost/move/adl_move_swap.hpp> #include <boost/move/iterator.hpp> @@ -515,7 +517,7 @@ inline typename container_detail::disable_if_memtransfer_copy_constructible<I, F F back = r; BOOST_TRY{ while (n--) { - allocator_traits<Allocator>::construct(a, container_detail::iterator_to_raw_pointer(r), *f); + boost::container::construct_in_place(a, container_detail::iterator_to_raw_pointer(r), f); ++f; ++r; } } @@ -757,7 +759,7 @@ inline typename container_detail::disable_if_memtransfer_copy_assignable<I, F, I copy_n_source(I f, typename boost::container::iterator_traits<I>::difference_type n, F r) { while (n--) { - *r = *f; + boost::container::assign_in_place(r, f); ++f; ++r; } return f; @@ -1139,4 +1141,4 @@ void move_assign_range_alloc_n( Allocator &a, I inp_start, typename allocator_tr } //namespace container { } //namespace boost { -#endif //#ifndef BOOST_CONTAINER_DETAIL_UTILITIES_HPP +#endif //#ifndef BOOST_CONTAINER_DETAIL_COPY_MOVE_ALGO_HPP diff --git a/boost/container/detail/dispatch_uses_allocator.hpp b/boost/container/detail/dispatch_uses_allocator.hpp index 3000f7cb27..fdf203cef8 100644 --- a/boost/container/detail/dispatch_uses_allocator.hpp +++ b/boost/container/detail/dispatch_uses_allocator.hpp @@ -222,7 +222,7 @@ template < typename ConstructAlloc BOOST_CONTAINER_DOC1ST(void, typename container_detail::enable_if<container_detail::is_pair<Pair> >::type) dispatch_uses_allocator ( ConstructAlloc & construct_alloc - , ArgAlloc & arg_alloc + , BOOST_FWD_REF(ArgAlloc) arg_alloc , Pair* p) { (dispatch_uses_allocator)(construct_alloc, arg_alloc, container_detail::addressof(p->first)); @@ -243,7 +243,7 @@ template < typename ConstructAlloc BOOST_CONTAINER_DOC1ST(void, typename container_detail::enable_if<container_detail::is_pair<Pair> >::type) dispatch_uses_allocator ( ConstructAlloc & construct_alloc - , ArgAlloc & arg_alloc + , BOOST_FWD_REF(ArgAlloc) arg_alloc , Pair* p, BOOST_FWD_REF(U) x, BOOST_FWD_REF(V) y) { (dispatch_uses_allocator)(construct_alloc, arg_alloc, container_detail::addressof(p->first), ::boost::forward<U>(x)); @@ -263,7 +263,7 @@ template < typename ConstructAlloc BOOST_CONTAINER_DOC1ST(void, typename container_detail::enable_if< container_detail::is_pair<Pair> >::type) dispatch_uses_allocator (ConstructAlloc & construct_alloc - , ArgAlloc & arg_alloc + , BOOST_FWD_REF(ArgAlloc) arg_alloc , Pair* p, Pair2& x) { (dispatch_uses_allocator)(construct_alloc, arg_alloc, p, x.first, x.second); } @@ -276,13 +276,135 @@ typename container_detail::enable_if_and , container_detail::not_<boost::move_detail::is_reference<Pair2> > >::type //This is needed for MSVC10 and ambiguous overloads dispatch_uses_allocator (ConstructAlloc & construct_alloc - , ArgAlloc & arg_alloc + , BOOST_FWD_REF(ArgAlloc) arg_alloc , Pair* p, BOOST_RV_REF_BEG Pair2 BOOST_RV_REF_END x) { (dispatch_uses_allocator)(construct_alloc, arg_alloc, p, ::boost::move(x.first), ::boost::move(x.second)); } -//template <typename ConstructAlloc, typename ArgAlloc, class Pair, class Pair2> -//void dispatch_uses_allocator( ConstructAlloc & construct_alloc, ArgAlloc & arg_alloc -// , pair<T1, T2>* p, piecewise_construct_t, tuple<Args1...> x, tuple<Args2...> y); + +//piecewise construction from boost::tuple +#define BOOST_DISPATCH_USES_ALLOCATOR_PIECEWISE_CONSTRUCT_BOOST_TUPLE_CODE(N,M)\ +template< typename ConstructAlloc, typename ArgAlloc, class Pair \ + , template<class, class, class, class, class, class, class, class, class, class> class BoostTuple \ + BOOST_MOVE_I_IF(BOOST_MOVE_OR(N,M)) BOOST_MOVE_CLASS##N BOOST_MOVE_I_IF(BOOST_MOVE_AND(N,M)) BOOST_MOVE_CLASSQ##M > \ +typename container_detail::enable_if< container_detail::is_pair<Pair> >::type\ + dispatch_uses_allocator( ConstructAlloc & construct_alloc, ArgAlloc & arg_alloc, Pair* pair, piecewise_construct_t\ + , BoostTuple<BOOST_MOVE_TARG##N BOOST_MOVE_I##N BOOST_MOVE_REPEAT(BOOST_MOVE_SUB(10,N),::boost::tuples::null_type)> p\ + , BoostTuple<BOOST_MOVE_TARGQ##M BOOST_MOVE_I##M BOOST_MOVE_REPEAT(BOOST_MOVE_SUB(10,M),::boost::tuples::null_type)> q)\ +{\ + (void)p; (void)q;\ + (dispatch_uses_allocator)\ + (construct_alloc, arg_alloc, container_detail::addressof(pair->first) BOOST_MOVE_I_IF(N) BOOST_MOVE_TMPL_GET##N);\ + BOOST_TRY{\ + (dispatch_uses_allocator)\ + (construct_alloc, arg_alloc, container_detail::addressof(pair->second) BOOST_MOVE_I_IF(M) BOOST_MOVE_TMPL_GETQ##M);\ + }\ + BOOST_CATCH(...) {\ + allocator_traits<ConstructAlloc>::destroy(construct_alloc, container_detail::addressof(pair->first));\ + BOOST_RETHROW\ + }\ + BOOST_CATCH_END\ +}\ +// +BOOST_MOVE_ITER2D_0TOMAX(9, BOOST_DISPATCH_USES_ALLOCATOR_PIECEWISE_CONSTRUCT_BOOST_TUPLE_CODE) +#undef BOOST_DISPATCH_USES_ALLOCATOR_PIECEWISE_CONSTRUCT_BOOST_TUPLE_CODE + +//piecewise construction from Std Tuple +#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) + + template< typename ConstructAlloc, typename ArgAlloc, class Pair + , template<class ...> class Tuple, class... Args1, class... Args2, size_t... Indexes1, size_t... Indexes2> + void dispatch_uses_allocator_index( ConstructAlloc & construct_alloc, ArgAlloc & arg_alloc, Pair* pair + , Tuple<Args1...>& t1, Tuple<Args2...>& t2, index_tuple<Indexes1...>, index_tuple<Indexes2...>) + { + (void)t1; (void)t2; + (dispatch_uses_allocator)(construct_alloc, arg_alloc, container_detail::addressof(pair->first), ::boost::forward<Args1>(get<Indexes1>(t1))...); + BOOST_TRY{ + (dispatch_uses_allocator)(construct_alloc, arg_alloc, container_detail::addressof(pair->second), ::boost::forward<Args2>(get<Indexes2>(t2))...); + } + BOOST_CATCH(...){ + allocator_traits<ConstructAlloc>::destroy(construct_alloc, container_detail::addressof(pair->first)); + BOOST_RETHROW + } + BOOST_CATCH_END + } + + template< typename ConstructAlloc, typename ArgAlloc, class Pair + , template<class ...> class Tuple, class... Args1, class... Args2> + typename container_detail::enable_if< container_detail::is_pair<Pair> >::type + dispatch_uses_allocator( ConstructAlloc & construct_alloc, ArgAlloc & arg_alloc, Pair* pair, piecewise_construct_t + , Tuple<Args1...> t1, Tuple<Args2...> t2) + { + (dispatch_uses_allocator_index)( construct_alloc, arg_alloc, pair, t1, t2 + , typename build_number_seq<sizeof...(Args1)>::type() + , typename build_number_seq<sizeof...(Args2)>::type()); + } + +#elif defined(BOOST_MSVC) && (_CPPLIB_VER == 520) + + //MSVC 2010 tuple implementation + #define BOOST_DISPATCH_USES_ALLOCATOR_PIECEWISE_CONSTRUCT_MSVC2010_TUPLE_CODE(N,M)\ + template< typename ConstructAlloc, typename ArgAlloc, class Pair\ + , template<class, class, class, class, class, class, class, class, class, class> class StdTuple\ + BOOST_MOVE_I_IF(BOOST_MOVE_OR(N,M)) BOOST_MOVE_CLASS##N BOOST_MOVE_I_IF(BOOST_MOVE_AND(N,M)) BOOST_MOVE_CLASSQ##M > \ + typename container_detail::enable_if< container_detail::is_pair<Pair> >::type\ + dispatch_uses_allocator(ConstructAlloc & construct_alloc, ArgAlloc & arg_alloc, Pair* pair, piecewise_construct_t\ + , StdTuple<BOOST_MOVE_TARG##N BOOST_MOVE_I##N BOOST_MOVE_REPEAT(BOOST_MOVE_SUB(10,N),::std::tr1::_Nil)> p\ + , StdTuple<BOOST_MOVE_TARGQ##M BOOST_MOVE_I##M BOOST_MOVE_REPEAT(BOOST_MOVE_SUB(10,M),::std::tr1::_Nil)> q)\ + {\ + (void)p; (void)q;\ + (dispatch_uses_allocator)\ + (construct_alloc, arg_alloc, container_detail::addressof(pair->first) BOOST_MOVE_I_IF(N) BOOST_MOVE_GET_IDX##N);\ + BOOST_TRY{\ + (dispatch_uses_allocator)\ + (construct_alloc, arg_alloc, container_detail::addressof(pair->second) BOOST_MOVE_I_IF(M) BOOST_MOVE_GET_IDXQ##M);\ + }\ + BOOST_CATCH(...) {\ + allocator_traits<ConstructAlloc>::destroy(construct_alloc, container_detail::addressof(pair->first));\ + BOOST_RETHROW\ + }\ + BOOST_CATCH_END\ + }\ + // + BOOST_MOVE_ITER2D_0TOMAX(9, BOOST_DISPATCH_USES_ALLOCATOR_PIECEWISE_CONSTRUCT_MSVC2010_TUPLE_CODE) + #undef BOOST_DISPATCH_USES_ALLOCATOR_PIECEWISE_CONSTRUCT_MSVC2010_TUPLE_CODE + +#elif defined(BOOST_MSVC) && (_CPPLIB_VER == 540) + #if _VARIADIC_MAX >= 9 + #define BOOST_DISPATCH_USES_ALLOCATOR_PIECEWISE_CONSTRUCT_MSVC2012_TUPLE_MAX_IT 9 + #else + #define BOOST_DISPATCH_USES_ALLOCATOR_PIECEWISE_CONSTRUCT_MSVC2012_TUPLE_MAX_IT BOOST_MOVE_ADD(_VARIADIC_MAX, 1) + #endif + + //MSVC 2012 tuple implementation + #define BOOST_DISPATCH_USES_ALLOCATOR_PIECEWISE_CONSTRUCT_MSVC2012_TUPLE_CODE(N,M)\ + template< typename ConstructAlloc, typename ArgAlloc, class Pair\ + , template<BOOST_MOVE_REPEAT(_VARIADIC_MAX, class), class, class, class> class StdTuple \ + BOOST_MOVE_I_IF(BOOST_MOVE_OR(N,M)) BOOST_MOVE_CLASS##N BOOST_MOVE_I_IF(BOOST_MOVE_AND(N,M)) BOOST_MOVE_CLASSQ##M > \ + typename container_detail::enable_if< container_detail::is_pair<Pair> >::type\ + dispatch_uses_allocator\ + ( ConstructAlloc & construct_alloc, ArgAlloc & arg_alloc, Pair* pair, piecewise_construct_t\ + , StdTuple<BOOST_MOVE_TARG##N BOOST_MOVE_I##N BOOST_MOVE_REPEAT(BOOST_MOVE_SUB(BOOST_MOVE_ADD(_VARIADIC_MAX, 3),N),::std::_Nil) > p\ + , StdTuple<BOOST_MOVE_TARGQ##M BOOST_MOVE_I##M BOOST_MOVE_REPEAT(BOOST_MOVE_SUB(BOOST_MOVE_ADD(_VARIADIC_MAX, 3),M),::std::_Nil) > q)\ + {\ + (void)p; (void)q;\ + (dispatch_uses_allocator)\ + (construct_alloc, arg_alloc, container_detail::addressof(pair->first) BOOST_MOVE_I_IF(N) BOOST_MOVE_GET_IDX##N);\ + BOOST_TRY{\ + (dispatch_uses_allocator)\ + (construct_alloc, arg_alloc, container_detail::addressof(pair->second) BOOST_MOVE_I_IF(M) BOOST_MOVE_GET_IDXQ##M);\ + }\ + BOOST_CATCH(...) {\ + allocator_traits<ConstructAlloc>::destroy(construct_alloc, container_detail::addressof(pair->first));\ + BOOST_RETHROW\ + }\ + BOOST_CATCH_END\ + }\ + // + BOOST_MOVE_ITER2D_0TOMAX(BOOST_DISPATCH_USES_ALLOCATOR_PIECEWISE_CONSTRUCT_MSVC2012_TUPLE_MAX_IT, BOOST_DISPATCH_USES_ALLOCATOR_PIECEWISE_CONSTRUCT_MSVC2012_TUPLE_CODE) + #undef BOOST_DISPATCH_USES_ALLOCATOR_PIECEWISE_CONSTRUCT_MSVC2010_TUPLE_CODE + #undef BOOST_DISPATCH_USES_ALLOCATOR_PIECEWISE_CONSTRUCT_MSVC2012_TUPLE_MAX_IT + +#endif //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) } //namespace container_detail diff --git a/boost/container/detail/flat_tree.hpp b/boost/container/detail/flat_tree.hpp index 4c48c8b7d3..db73c410a9 100644 --- a/boost/container/detail/flat_tree.hpp +++ b/boost/container/detail/flat_tree.hpp @@ -32,11 +32,13 @@ #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/detail/is_sorted.hpp> #include <boost/container/allocator_traits.hpp> #ifdef BOOST_CONTAINER_VECTOR_ITERATOR_IS_POINTER #include <boost/intrusive/pointer_traits.hpp> #endif #include <boost/container/detail/type_traits.hpp> +#include <boost/container/detail/iterators.hpp> #include <boost/move/make_unique.hpp> #include <boost/move/adl_move_swap.hpp> #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) @@ -44,6 +46,7 @@ #endif #include <boost/intrusive/detail/minimal_pair_header.hpp> //pair +#include <boost/move/iterator.hpp> namespace boost { namespace container { @@ -98,7 +101,7 @@ struct get_flat_tree_iterators typedef boost::container::reverse_iterator<const_iterator> const_reverse_iterator; }; -template <class Key, class Value, class KeyOfValue, +template <class Value, class KeyOfValue, class Compare, class Allocator> class flat_tree { @@ -183,7 +186,7 @@ class flat_tree typedef typename vector_t::const_pointer const_pointer; typedef typename vector_t::reference reference; typedef typename vector_t::const_reference const_reference; - typedef Key key_type; + typedef typename KeyOfValue::type key_type; typedef Compare key_compare; typedef typename vector_t::allocator_type allocator_type; typedef typename vector_t::size_type size_type; @@ -200,35 +203,36 @@ class flat_tree typedef allocator_traits<stored_allocator_type> stored_allocator_traits; public: - flat_tree() + BOOST_CONTAINER_FORCEINLINE flat_tree() : m_data() { } - explicit flat_tree(const Compare& comp) + BOOST_CONTAINER_FORCEINLINE explicit flat_tree(const Compare& comp) : m_data(comp) { } - flat_tree(const Compare& comp, const allocator_type& a) + BOOST_CONTAINER_FORCEINLINE flat_tree(const Compare& comp, const allocator_type& a) : m_data(comp, a) { } - explicit flat_tree(const allocator_type& a) + BOOST_CONTAINER_FORCEINLINE explicit flat_tree(const allocator_type& a) : m_data(a) { } - flat_tree(const flat_tree& x) + BOOST_CONTAINER_FORCEINLINE flat_tree(const flat_tree& x) : m_data(x.m_data) { } - flat_tree(BOOST_RV_REF(flat_tree) x) + BOOST_CONTAINER_FORCEINLINE flat_tree(BOOST_RV_REF(flat_tree) x) + BOOST_NOEXCEPT_IF(boost::container::container_detail::is_nothrow_move_constructible<Compare>::value) : m_data(boost::move(x.m_data)) { } - flat_tree(const flat_tree& x, const allocator_type &a) + BOOST_CONTAINER_FORCEINLINE flat_tree(const flat_tree& x, const allocator_type &a) : m_data(x.m_data, a) { } - flat_tree(BOOST_RV_REF(flat_tree) x, const allocator_type &a) + BOOST_CONTAINER_FORCEINLINE flat_tree(BOOST_RV_REF(flat_tree) x, const allocator_type &a) : m_data(boost::move(x.m_data), a) { } @@ -237,7 +241,20 @@ class flat_tree , const Compare& comp = Compare() , const allocator_type& a = allocator_type()) : m_data(comp, a) - { this->m_data.m_vect.insert(this->m_data.m_vect.end(), first, last); } + { + this->m_data.m_vect.insert(this->m_data.m_vect.end(), first, last); + BOOST_ASSERT((is_sorted)(this->m_data.m_vect.cbegin(), this->m_data.m_vect.cend(), this->priv_value_comp())); + } + + template <class InputIterator> + flat_tree( ordered_unique_range_t, InputIterator first, InputIterator last + , const Compare& comp = Compare() + , const allocator_type& a = allocator_type()) + : m_data(comp, a) + { + this->m_data.m_vect.insert(this->m_data.m_vect.end(), first, last); + BOOST_ASSERT((is_sorted_and_unique)(this->m_data.m_vect.cbegin(), this->m_data.m_vect.cend(), this->priv_value_comp())); + } template <class InputIterator> flat_tree( bool unique_insertion @@ -262,80 +279,93 @@ class flat_tree } } - ~flat_tree() + BOOST_CONTAINER_FORCEINLINE ~flat_tree() {} - flat_tree& operator=(BOOST_COPY_ASSIGN_REF(flat_tree) x) + BOOST_CONTAINER_FORCEINLINE 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) x) - BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value - && boost::container::container_detail::is_nothrow_move_assignable<Compare>::value ) + BOOST_CONTAINER_FORCEINLINE flat_tree& operator=(BOOST_RV_REF(flat_tree) x) + BOOST_NOEXCEPT_IF( (allocator_traits_type::propagate_on_container_move_assignment::value || + 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; } + BOOST_CONTAINER_FORCEINLINE const value_compare &priv_value_comp() const + { return static_cast<const value_compare &>(this->m_data); } + + BOOST_CONTAINER_FORCEINLINE value_compare &priv_value_comp() + { return static_cast<value_compare &>(this->m_data); } + + BOOST_CONTAINER_FORCEINLINE const key_compare &priv_key_comp() const + { return this->priv_value_comp().get_comp(); } + + BOOST_CONTAINER_FORCEINLINE key_compare &priv_key_comp() + { return this->priv_value_comp().get_comp(); } + public: // accessors: - Compare key_comp() const + BOOST_CONTAINER_FORCEINLINE Compare key_comp() const { return this->m_data.get_comp(); } - value_compare value_comp() const + BOOST_CONTAINER_FORCEINLINE value_compare value_comp() const { return this->m_data; } - allocator_type get_allocator() const + BOOST_CONTAINER_FORCEINLINE allocator_type get_allocator() const { return this->m_data.m_vect.get_allocator(); } - const stored_allocator_type &get_stored_allocator() const + BOOST_CONTAINER_FORCEINLINE const stored_allocator_type &get_stored_allocator() const { return this->m_data.m_vect.get_stored_allocator(); } - stored_allocator_type &get_stored_allocator() + BOOST_CONTAINER_FORCEINLINE stored_allocator_type &get_stored_allocator() { return this->m_data.m_vect.get_stored_allocator(); } - iterator begin() + BOOST_CONTAINER_FORCEINLINE iterator begin() { return this->m_data.m_vect.begin(); } - const_iterator begin() const + BOOST_CONTAINER_FORCEINLINE const_iterator begin() const { return this->cbegin(); } - const_iterator cbegin() const + BOOST_CONTAINER_FORCEINLINE const_iterator cbegin() const { return this->m_data.m_vect.begin(); } - iterator end() + BOOST_CONTAINER_FORCEINLINE iterator end() { return this->m_data.m_vect.end(); } - const_iterator end() const + BOOST_CONTAINER_FORCEINLINE const_iterator end() const { return this->cend(); } - const_iterator cend() const + BOOST_CONTAINER_FORCEINLINE const_iterator cend() const { return this->m_data.m_vect.end(); } - reverse_iterator rbegin() + BOOST_CONTAINER_FORCEINLINE reverse_iterator rbegin() { return reverse_iterator(this->end()); } - const_reverse_iterator rbegin() const + BOOST_CONTAINER_FORCEINLINE const_reverse_iterator rbegin() const { return this->crbegin(); } - const_reverse_iterator crbegin() const + BOOST_CONTAINER_FORCEINLINE const_reverse_iterator crbegin() const { return const_reverse_iterator(this->cend()); } - reverse_iterator rend() + BOOST_CONTAINER_FORCEINLINE reverse_iterator rend() { return reverse_iterator(this->begin()); } - const_reverse_iterator rend() const + BOOST_CONTAINER_FORCEINLINE const_reverse_iterator rend() const { return this->crend(); } - const_reverse_iterator crend() const + BOOST_CONTAINER_FORCEINLINE const_reverse_iterator crend() const { return const_reverse_iterator(this->cbegin()); } - bool empty() const + BOOST_CONTAINER_FORCEINLINE bool empty() const { return this->m_data.m_vect.empty(); } - size_type size() const + BOOST_CONTAINER_FORCEINLINE size_type size() const { return this->m_data.m_vect.size(); } - size_type max_size() const + BOOST_CONTAINER_FORCEINLINE size_type max_size() const { return this->m_data.m_vect.max_size(); } - void swap(flat_tree& other) + BOOST_CONTAINER_FORCEINLINE 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); } @@ -346,7 +376,7 @@ class flat_tree { std::pair<iterator,bool> ret; insert_commit_data data; - ret.second = this->priv_insert_unique_prepare(val, data); + ret.second = this->priv_insert_unique_prepare(KeyOfValue()(val), data); ret.first = ret.second ? this->priv_insert_commit(data, val) : iterator(vector_iterator_get_ptr(data.position)); return ret; @@ -356,7 +386,7 @@ class flat_tree { std::pair<iterator,bool> ret; insert_commit_data data; - ret.second = this->priv_insert_unique_prepare(val, data); + ret.second = this->priv_insert_unique_prepare(KeyOfValue()(val), data); ret.first = ret.second ? this->priv_insert_commit(data, boost::move(val)) : iterator(vector_iterator_get_ptr(data.position)); return ret; @@ -381,7 +411,7 @@ class flat_tree BOOST_ASSERT(this->priv_in_range_or_end(hint)); std::pair<iterator,bool> ret; insert_commit_data data; - return this->priv_insert_unique_prepare(hint, val, data) + return this->priv_insert_unique_prepare(hint, KeyOfValue()(val), data) ? this->priv_insert_commit(data, val) : iterator(vector_iterator_get_ptr(data.position)); } @@ -391,7 +421,7 @@ class flat_tree BOOST_ASSERT(this->priv_in_range_or_end(hint)); std::pair<iterator,bool> ret; insert_commit_data data; - return this->priv_insert_unique_prepare(hint, val, data) + return this->priv_insert_unique_prepare(hint, KeyOfValue()(val), data) ? this->priv_insert_commit(data, boost::move(val)) : iterator(vector_iterator_get_ptr(data.position)); } @@ -481,7 +511,7 @@ class flat_tree >::type * = 0 #endif ) - { this->m_data.m_vect.merge(first, last); } + { this->m_data.m_vect.merge(first, last, static_cast<const value_compare &>(this->m_data)); } template <class InIt> void insert_unique(ordered_unique_range_t, InIt first, InIt last @@ -510,7 +540,7 @@ class flat_tree >::type * = 0 #endif ) - { this->m_data.m_vect.merge_unique(first, last, value_compare()); } + { this->m_data.m_vect.merge_unique(first, last, static_cast<const value_compare &>(this->m_data)); } #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) @@ -560,6 +590,29 @@ class flat_tree return this->insert_equal(hint, ::boost::move(val)); } + template <class KeyType, class... Args> + BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> try_emplace + (const_iterator hint, BOOST_FWD_REF(KeyType) key, BOOST_FWD_REF(Args)... args) + { + std::pair<iterator,bool> ret; + insert_commit_data data; + const key_type & k = key; + ret.second = hint == const_iterator() + ? this->priv_insert_unique_prepare(k, data) + : this->priv_insert_unique_prepare(hint, k, data); + + if(!ret.second){ + ret.first = this->nth(data.position - this->cbegin()); + } + else{ + typedef typename emplace_functor_type<try_emplace_t, KeyType, Args...>::type func_t; + typedef emplace_iterator<value_type, func_t, difference_type> it_t; + func_t func(try_emplace_t(), ::boost::forward<KeyType>(key), ::boost::forward<Args>(args)...); + ret.first = this->m_data.m_vect.insert(data.position, it_t(func), it_t()); + } + return ret; + } + #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) #define BOOST_CONTAINER_FLAT_TREE_EMPLACE_CODE(N) \ @@ -606,13 +659,57 @@ class flat_tree value_destructor<stored_allocator_type> d(a, val);\ return this->insert_equal(hint, ::boost::move(val));\ }\ + template <class KeyType BOOST_MOVE_I##N BOOST_MOVE_CLASS##N>\ + BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool>\ + try_emplace(const_iterator hint, BOOST_FWD_REF(KeyType) key BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ + {\ + std::pair<iterator,bool> ret;\ + insert_commit_data data;\ + const key_type & k = key;\ + ret.second = hint == const_iterator()\ + ? this->priv_insert_unique_prepare(k, data)\ + : this->priv_insert_unique_prepare(hint, k, data);\ + \ + if(!ret.second){\ + ret.first = this->nth(data.position - this->cbegin());\ + }\ + else{\ + typedef typename emplace_functor_type<try_emplace_t, KeyType BOOST_MOVE_I##N BOOST_MOVE_TARG##N>::type func_t;\ + typedef emplace_iterator<value_type, func_t, difference_type> it_t;\ + func_t func(try_emplace_t(), ::boost::forward<KeyType>(key) BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ + ret.first = this->m_data.m_vect.insert(data.position, it_t(func), it_t());\ + }\ + return ret;\ + }\ // - BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_FLAT_TREE_EMPLACE_CODE) + BOOST_MOVE_ITERATE_0TO7(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) + template<class KeyType, class M> + std::pair<iterator, bool> insert_or_assign(const_iterator hint, BOOST_FWD_REF(KeyType) key, BOOST_FWD_REF(M) obj) + { + const key_type& k = key; + std::pair<iterator,bool> ret; + insert_commit_data data; + ret.second = hint == const_iterator() + ? this->priv_insert_unique_prepare(k, data) + : this->priv_insert_unique_prepare(hint, k, data); + if(!ret.second){ + ret.first = this->nth(data.position - this->cbegin()); + ret.first->second = boost::forward<M>(obj); + } + else{ + typedef typename emplace_functor_type<KeyType, M>::type func_t; + typedef emplace_iterator<value_type, func_t, difference_type> it_t; + func_t func(boost::forward<KeyType>(key), boost::forward<M>(obj)); + ret.first = this->m_data.m_vect.insert(data.position, it_t(func), it_t()); + } + return ret; + } + + BOOST_CONTAINER_FORCEINLINE iterator erase(const_iterator position) { return this->m_data.m_vect.erase(position); } size_type erase(const key_type& k) @@ -625,10 +722,10 @@ class flat_tree return ret; } - iterator erase(const_iterator first, const_iterator last) + BOOST_CONTAINER_FORCEINLINE iterator erase(const_iterator first, const_iterator last) { return this->m_data.m_vect.erase(first, last); } - void clear() + BOOST_CONTAINER_FORCEINLINE void clear() { this->m_data.m_vect.clear(); } //! <b>Effects</b>: Tries to deallocate the excess of memory created @@ -637,19 +734,19 @@ class flat_tree //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws. //! //! <b>Complexity</b>: Linear to size(). - void shrink_to_fit() + BOOST_CONTAINER_FORCEINLINE void shrink_to_fit() { this->m_data.m_vect.shrink_to_fit(); } - iterator nth(size_type n) BOOST_NOEXCEPT_OR_NOTHROW + BOOST_CONTAINER_FORCEINLINE 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 + BOOST_CONTAINER_FORCEINLINE 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 + BOOST_CONTAINER_FORCEINLINE 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 + BOOST_CONTAINER_FORCEINLINE size_type index_of(const_iterator p) const BOOST_NOEXCEPT_OR_NOTHROW { return this->m_data.m_vect.index_of(p); } // set operations: @@ -682,64 +779,94 @@ class flat_tree return n; } - iterator lower_bound(const key_type& k) + template<class C2> + void merge_unique(flat_tree<Value, KeyOfValue, C2, Allocator>& source) + { + this->insert( boost::make_move_iterator(source.begin()) + , boost::make_move_iterator(source.end())); + } + + template<class C2> + void merge_equal(flat_tree<Value, KeyOfValue, C2, Allocator>& source) + { + this->insert( boost::make_move_iterator(source.begin()) + , boost::make_move_iterator(source.end())); + } + + void merge_unique(flat_tree& source) + { + this->m_data.m_vect.merge_unique + ( boost::make_move_iterator(source.begin()) + , boost::make_move_iterator(source.end()) + , static_cast<const value_compare &>(this->m_data)); + } + + void merge_equal(flat_tree& source) + { + this->m_data.m_vect.merge + ( boost::make_move_iterator(source.begin()) + , boost::make_move_iterator(source.end()) + , static_cast<const value_compare &>(this->m_data)); + } + + BOOST_CONTAINER_FORCEINLINE iterator lower_bound(const key_type& k) { return this->priv_lower_bound(this->begin(), this->end(), k); } - const_iterator lower_bound(const key_type& k) const + BOOST_CONTAINER_FORCEINLINE const_iterator lower_bound(const key_type& k) const { return this->priv_lower_bound(this->cbegin(), this->cend(), k); } - iterator upper_bound(const key_type& k) + BOOST_CONTAINER_FORCEINLINE iterator upper_bound(const key_type& k) { return this->priv_upper_bound(this->begin(), this->end(), k); } - const_iterator upper_bound(const key_type& k) const + BOOST_CONTAINER_FORCEINLINE const_iterator upper_bound(const key_type& k) const { return this->priv_upper_bound(this->cbegin(), this->cend(), k); } - std::pair<iterator,iterator> equal_range(const key_type& k) + BOOST_CONTAINER_FORCEINLINE std::pair<iterator,iterator> equal_range(const key_type& k) { return this->priv_equal_range(this->begin(), this->end(), k); } - std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const + BOOST_CONTAINER_FORCEINLINE std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const { return this->priv_equal_range(this->cbegin(), this->cend(), k); } - std::pair<iterator, iterator> lower_bound_range(const key_type& k) + BOOST_CONTAINER_FORCEINLINE std::pair<iterator, iterator> lower_bound_range(const key_type& k) { return this->priv_lower_bound_range(this->begin(), this->end(), k); } - std::pair<const_iterator, const_iterator> lower_bound_range(const key_type& k) const + BOOST_CONTAINER_FORCEINLINE std::pair<const_iterator, const_iterator> lower_bound_range(const key_type& k) const { return this->priv_lower_bound_range(this->cbegin(), this->cend(), k); } - size_type capacity() const + BOOST_CONTAINER_FORCEINLINE size_type capacity() const { return this->m_data.m_vect.capacity(); } - void reserve(size_type cnt) + BOOST_CONTAINER_FORCEINLINE void reserve(size_type cnt) { this->m_data.m_vect.reserve(cnt); } - friend bool operator==(const flat_tree& x, const flat_tree& y) + BOOST_CONTAINER_FORCEINLINE friend bool operator==(const flat_tree& x, const flat_tree& y) { 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) + BOOST_CONTAINER_FORCEINLINE friend bool operator<(const flat_tree& x, const flat_tree& y) { 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) + BOOST_CONTAINER_FORCEINLINE friend bool operator!=(const flat_tree& x, const flat_tree& y) { return !(x == y); } - friend bool operator>(const flat_tree& x, const flat_tree& y) + BOOST_CONTAINER_FORCEINLINE friend bool operator>(const flat_tree& x, const flat_tree& y) { return y < x; } - friend bool operator<=(const flat_tree& x, const flat_tree& y) + BOOST_CONTAINER_FORCEINLINE friend bool operator<=(const flat_tree& x, const flat_tree& y) { return !(y < x); } - friend bool operator>=(const flat_tree& x, const flat_tree& y) + BOOST_CONTAINER_FORCEINLINE friend bool operator>=(const flat_tree& x, const flat_tree& y) { return !(x < y); } - friend void swap(flat_tree& x, flat_tree& y) + BOOST_CONTAINER_FORCEINLINE friend void swap(flat_tree& x, flat_tree& y) { x.swap(y); } private: - bool priv_in_range_or_end(const_iterator pos) const + BOOST_CONTAINER_FORCEINLINE bool priv_in_range_or_end(const_iterator pos) const { return (this->begin() <= pos) && (pos <= this->end()); } @@ -780,34 +907,34 @@ class flat_tree } bool priv_insert_unique_prepare - (const_iterator b, const_iterator e, const value_type& val, insert_commit_data &commit_data) + (const_iterator b, const_iterator e, const key_type& k, insert_commit_data &commit_data) { - const value_compare &val_cmp = this->m_data; - commit_data.position = this->priv_lower_bound(b, e, KeyOfValue()(val)); - return commit_data.position == e || val_cmp(val, *commit_data.position); + const key_compare &key_cmp = this->priv_key_comp(); + commit_data.position = this->priv_lower_bound(b, e, k); + return commit_data.position == e || key_cmp(k, KeyOfValue()(*commit_data.position)); } - bool priv_insert_unique_prepare - (const value_type& val, insert_commit_data &commit_data) - { return this->priv_insert_unique_prepare(this->cbegin(), this->cend(), val, commit_data); } + BOOST_CONTAINER_FORCEINLINE bool priv_insert_unique_prepare + (const key_type& k, insert_commit_data &commit_data) + { return this->priv_insert_unique_prepare(this->cbegin(), this->cend(), k, commit_data); } bool priv_insert_unique_prepare - (const_iterator pos, const value_type& val, insert_commit_data &commit_data) + (const_iterator pos, const key_type& k, insert_commit_data &commit_data) { //N1780. Props to Howard Hinnant! - //To insert val at pos: - //if pos == end || val <= *pos - // if pos == begin || val >= *(pos-1) - // insert val before pos + //To insert k at pos: + //if pos == end || k <= *pos + // if pos == begin || k >= *(pos-1) + // insert k before pos // else - // insert val before upper_bound(val) - //else if pos+1 == end || val <= *(pos+1) - // insert val after pos + // insert k before upper_bound(k) + //else if pos+1 == end || k <= *(pos+1) + // insert k after pos //else - // insert val before lower_bound(val) - const value_compare &val_cmp = this->m_data; + // insert k before lower_bound(k) + const key_compare &key_cmp = this->priv_key_comp(); const const_iterator cend_it = this->cend(); - if(pos == cend_it || val_cmp(val, *pos)){ //Check if val should go before end + if(pos == cend_it || key_cmp(k, KeyOfValue()(*pos))){ //Check if k should go before end const const_iterator cbeg = this->cbegin(); commit_data.position = pos; if(pos == cbeg){ //If container is empty then insert it in the beginning @@ -815,27 +942,27 @@ class flat_tree } const_iterator prev(pos); --prev; - if(val_cmp(*prev, val)){ //If previous element was less, then it should go between prev and pos + if(key_cmp(KeyOfValue()(*prev), k)){ //If previous element was less, then it should go between prev and pos return true; } - else if(!val_cmp(val, *prev)){ //If previous was equal then insertion should fail + else if(!key_cmp(k, KeyOfValue()(*prev))){ //If previous was equal then insertion should fail commit_data.position = prev; return false; } else{ //Previous was bigger so insertion hint was pointless, dispatch to hintless insertion - //but reduce the search between beg and prev as prev is bigger than val - return this->priv_insert_unique_prepare(cbeg, prev, val, commit_data); + //but reduce the search between beg and prev as prev is bigger than k + return this->priv_insert_unique_prepare(cbeg, prev, k, commit_data); } } else{ //The hint is before the insertion position, so insert it //in the remaining range [pos, end) - return this->priv_insert_unique_prepare(pos, cend_it, val, commit_data); + return this->priv_insert_unique_prepare(pos, cend_it, k, commit_data); } } template<class Convertible> - iterator priv_insert_commit + BOOST_CONTAINER_FORCEINLINE iterator priv_insert_commit (insert_commit_data &commit_data, BOOST_FWD_REF(Convertible) convertible) { return this->m_data.m_vect.insert @@ -966,9 +1093,9 @@ class flat_tree //!has_trivial_destructor_after_move<> == true_type //!specialization for optimizations -template <class Key, class T, class KeyOfValue, +template <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> > +struct has_trivial_destructor_after_move<boost::container::container_detail::flat_tree<T, KeyOfValue, Compare, Allocator> > { typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer; static const bool value = ::boost::has_trivial_destructor_after_move<Allocator>::value && diff --git a/boost/container/detail/is_sorted.hpp b/boost/container/detail/is_sorted.hpp new file mode 100644 index 0000000000..b8c223bb7b --- /dev/null +++ b/boost/container/detail/is_sorted.hpp @@ -0,0 +1,57 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2016-2016. Distributed under the Boost +// Software License, Version 1.0. (See accompanying file +// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) +// +// See http://www.boost.org/libs/container for documentation. +// +////////////////////////////////////////////////////////////////////////////// +#ifndef BOOST_CONTAINER_DETAIL_IS_SORTED_HPP +#define BOOST_CONTAINER_DETAIL_IS_SORTED_HPP + +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + +namespace boost { +namespace container { +namespace container_detail { + +template <class ForwardIterator, class Pred> +bool is_sorted (ForwardIterator first, ForwardIterator last, Pred pred) +{ + if(first != last){ + ForwardIterator next = first; + while (++next != last){ + if(pred(*next, *first)) + return false; + ++first; + } + } + return true; +} + +template <class ForwardIterator, class Pred> +bool is_sorted_and_unique (ForwardIterator first, ForwardIterator last, Pred pred) +{ + if(first != last){ + ForwardIterator next = first; + while (++next != last){ + if(!pred(*first, *next)) + return false; + ++first; + } + } + return true; +} + +} //namespace container_detail { +} //namespace container { +} //namespace boost { + +#endif //#ifndef BOOST_CONTAINER_DETAIL_IS_SORTED_HPP diff --git a/boost/container/detail/iterators.hpp b/boost/container/detail/iterators.hpp index 32ff32f362..d3b353a461 100644 --- a/boost/container/detail/iterators.hpp +++ b/boost/container/detail/iterators.hpp @@ -26,6 +26,7 @@ #include <boost/container/detail/workaround.hpp> #include <boost/container/allocator_traits.hpp> #include <boost/container/detail/type_traits.hpp> +#include <boost/container/detail/value_init.hpp> #include <boost/static_assert.hpp> #include <boost/move/utility_core.hpp> #include <boost/intrusive/detail/reverse_iterator.hpp> @@ -560,17 +561,23 @@ class emplace_iterator BOOST_CONTAINER_FORCEINLINE this_type operator-(difference_type off) const { return *this + (-off); } + private: //This pseudo-iterator's dereference operations have no sense since value is not //constructed until ::boost::container::construct_in_place is called. //So comment them to catch bad uses - //const T& operator*() const; - //const T& operator[](difference_type) const; - //const T* operator->() const; + const T& operator*() const; + const T& operator[](difference_type) const; + const T* operator->() const; + public: template<class Allocator> void construct_in_place(Allocator &a, T* ptr) { (*m_pe)(a, ptr); } + template<class DestIt> + void assign_in_place(DestIt dest) + { (*m_pe)(dest); } + private: difference_type m_num; EmplaceFunctor * m_pe; @@ -612,21 +619,44 @@ struct emplace_functor {} template<class Allocator, class T> - void operator()(Allocator &a, T *ptr) + BOOST_CONTAINER_FORCEINLINE void operator()(Allocator &a, T *ptr) { emplace_functor::inplace_impl(a, ptr, index_tuple_t()); } - template<class Allocator, class T, int ...IdxPack> + template<class DestIt> + BOOST_CONTAINER_FORCEINLINE void operator()(DestIt dest) + { emplace_functor::inplace_impl(dest, index_tuple_t()); } + + private: + template<class Allocator, class T, std::size_t ...IdxPack> BOOST_CONTAINER_FORCEINLINE void inplace_impl(Allocator &a, T* ptr, const container_detail::index_tuple<IdxPack...>&) { allocator_traits<Allocator>::construct (a, ptr, ::boost::forward<Args>(container_detail::get<IdxPack>(args_))...); } + template<class DestIt, std::size_t ...IdxPack> + BOOST_CONTAINER_FORCEINLINE void inplace_impl(DestIt dest, const container_detail::index_tuple<IdxPack...>&) + { + typedef typename boost::container::iterator_traits<DestIt>::value_type value_type; + value_type && tmp= value_type(::boost::forward<Args>(container_detail::get<IdxPack>(args_))...); + *dest = ::boost::move(tmp); + } + container_detail::tuple<Args&...> args_; }; +template<class ...Args> +struct emplace_functor_type +{ + typedef emplace_functor<Args...> type; +}; + #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) +//Partial specializations cannot match argument list for primary template, so add an extra argument +template <BOOST_MOVE_CLASSDFLT9, class Dummy = void> +struct emplace_functor_type; + #define BOOST_MOVE_ITERATOR_EMPLACE_FUNCTOR_CODE(N) \ BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ struct emplace_functor##N\ @@ -638,10 +668,26 @@ struct emplace_functor##N\ void operator()(Allocator &a, T *ptr)\ { allocator_traits<Allocator>::construct(a, ptr BOOST_MOVE_I##N BOOST_MOVE_MFWD##N); }\ \ + template<class DestIt>\ + void operator()(DestIt dest)\ + {\ + typedef typename boost::container::iterator_traits<DestIt>::value_type value_type;\ + BOOST_MOVE_IF(N, value_type tmp(BOOST_MOVE_MFWD##N), container_detail::value_init<value_type> tmp) ;\ + *dest = ::boost::move(const_cast<value_type &>(BOOST_MOVE_IF(N, tmp, tmp.get())));\ + }\ + \ BOOST_MOVE_MREF##N\ };\ +\ +template <BOOST_MOVE_CLASS##N>\ +struct emplace_functor_type<BOOST_MOVE_TARG##N>\ +{\ + typedef emplace_functor##N BOOST_MOVE_LT##N BOOST_MOVE_TARG##N BOOST_MOVE_GT##N type;\ +};\ // + BOOST_MOVE_ITERATE_0TO9(BOOST_MOVE_ITERATOR_EMPLACE_FUNCTOR_CODE) + #undef BOOST_MOVE_ITERATOR_EMPLACE_FUNCTOR_CODE #endif diff --git a/boost/container/detail/mpl.hpp b/boost/container/detail/mpl.hpp index e1684ea0b1..82fcc7036d 100644 --- a/boost/container/detail/mpl.hpp +++ b/boost/container/detail/mpl.hpp @@ -62,19 +62,18 @@ using boost::move_detail::disable_if_and; using boost::move_detail::enable_if_or; using boost::move_detail::disable_if_or; - -template <class Pair> +template <class FirstType> struct select1st { - typedef Pair argument_type; - typedef typename Pair::first_type result_type; + typedef FirstType type; - template<class OtherPair> - const typename Pair::first_type& operator()(const OtherPair& x) const + template<class T> + const type& operator()(const T& x) const { return x.first; } - const typename Pair::first_type& operator()(const typename Pair::first_type& x) const - { return x; } + template<class T> + type& operator()(T& x) + { return const_cast<type&>(x.first); } }; } //namespace container_detail { diff --git a/boost/container/detail/node_alloc_holder.hpp b/boost/container/detail/node_alloc_holder.hpp index 1b7c4d76dc..7ef5d2883e 100644 --- a/boost/container/detail/node_alloc_holder.hpp +++ b/boost/container/detail/node_alloc_holder.hpp @@ -394,12 +394,6 @@ struct node_alloc_holder ICont &non_const_icont() const { return const_cast<ICont&>(this->members_.m_icont); } - ICont &icont() - { return this->members_.m_icont; } - - const ICont &icont() const - { return this->members_.m_icont; } - NodeAlloc &node_alloc() { return static_cast<NodeAlloc &>(this->members_); } @@ -407,6 +401,13 @@ struct node_alloc_holder { return static_cast<const NodeAlloc &>(this->members_); } members_holder members_; + + public: + ICont &icont() + { return this->members_.m_icont; } + + const ICont &icont() const + { return this->members_.m_icont; } }; } //namespace container_detail { diff --git a/boost/container/detail/pair.hpp b/boost/container/detail/pair.hpp index 134760e1e6..096f79561e 100644 --- a/boost/container/detail/pair.hpp +++ b/boost/container/detail/pair.hpp @@ -28,13 +28,62 @@ #include <boost/container/detail/type_traits.hpp> #include <boost/container/detail/mpl.hpp> #include <boost/container/detail/std_fwd.hpp> +#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) +# include <boost/container/detail/variadic_templates_tools.hpp> +#endif #include <boost/move/adl_move_swap.hpp> //swap #include <boost/intrusive/detail/minimal_pair_header.hpp> //pair #include <boost/move/utility_core.hpp> +#include<boost/move/detail/fwd_macros.hpp> + +namespace boost { +namespace tuples { + +struct null_type; + +} //namespace tuples { +} //namespace boost { + +#if defined(BOOST_MSVC) && (_CPPLIB_VER == 520) +//MSVC 2010 tuple marker +namespace std { namespace tr1 { struct _Nil; }} +#elif defined(BOOST_MSVC) && (_CPPLIB_VER == 540) +//MSVC 2012 tuple marker +namespace std { struct _Nil; } +#endif + namespace boost { namespace container { + +#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED + + template <int Dummy = 0> + struct std_piecewise_construct_holder + { + static ::std::piecewise_construct_t *dummy; + }; + + template <int Dummy> + ::std::piecewise_construct_t *std_piecewise_construct_holder<Dummy>::dummy; + +typedef const std::piecewise_construct_t & piecewise_construct_t; + +struct try_emplace_t{}; + +#else + +//! The piecewise_construct_t struct is an empty structure type used as a unique type to +//! disambiguate used to disambiguate between different functions that take two tuple arguments. +typedef unspecified piecewise_construct_t; + +#endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED + +//! A instance of type +//! piecewise_construct_t +static piecewise_construct_t piecewise_construct = BOOST_CONTAINER_DOC1ST(unspecified, *std_piecewise_construct_holder<>::dummy); + namespace container_detail { template <class T1, class T2> @@ -78,6 +127,9 @@ struct is_std_pair< std::pair<T1, T2> > struct pair_nat; +template<typename T, typename U, typename V> +void get(T); //to enable ADL + template <class T1, class T2> struct pair { @@ -147,11 +199,105 @@ struct pair : first(::boost::move(p.first)), second(::boost::move(p.second)) {} - //piecewise_construct missing - //template <class U, class V> pair(pair<U, V>&& p); - //template <class... Args1, class... Args2> - // pair(piecewise_construct_t, tuple<Args1...> first_args, - // tuple<Args2...> second_args); + #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) + template< class KeyType, class ...Args> + pair(try_emplace_t, BOOST_FWD_REF(KeyType) k, Args && ...args) + : first(boost::forward<KeyType>(k)), second(::boost::forward<Args>(args)...)\ + {} + #else + + //piecewise construction from boost::tuple + #define BOOST_PAIR_TRY_EMPLACE_CONSTRUCT_CODE(N)\ + template< class KeyType BOOST_MOVE_I##N BOOST_MOVE_CLASS##N > \ + pair( try_emplace_t, BOOST_FWD_REF(KeyType) k BOOST_MOVE_I##N BOOST_MOVE_UREF##N )\ + : first(boost::forward<KeyType>(k)), second(BOOST_MOVE_FWD##N)\ + {}\ + // + BOOST_MOVE_ITERATE_0TO9(BOOST_PAIR_TRY_EMPLACE_CONSTRUCT_CODE) + #undef BOOST_PAIR_TRY_EMPLACE_CONSTRUCT_CODE + + #endif //BOOST_NO_CXX11_VARIADIC_TEMPLATES + + //piecewise construction from boost::tuple + #define BOOST_PAIR_PIECEWISE_CONSTRUCT_BOOST_TUPLE_CODE(N,M)\ + template< template<class, class, class, class, class, class, class, class, class, class> class BoostTuple \ + BOOST_MOVE_I_IF(BOOST_MOVE_OR(N,M)) BOOST_MOVE_CLASS##N BOOST_MOVE_I_IF(BOOST_MOVE_AND(N,M)) BOOST_MOVE_CLASSQ##M > \ + pair( piecewise_construct_t\ + , BoostTuple<BOOST_MOVE_TARG##N BOOST_MOVE_I##N BOOST_MOVE_REPEAT(BOOST_MOVE_SUB(10,N),::boost::tuples::null_type)> p\ + , BoostTuple<BOOST_MOVE_TARGQ##M BOOST_MOVE_I##M BOOST_MOVE_REPEAT(BOOST_MOVE_SUB(10,M),::boost::tuples::null_type)> q)\ + : first(BOOST_MOVE_TMPL_GET##N), second(BOOST_MOVE_TMPL_GETQ##M)\ + { (void)p; (void)q; }\ + // + BOOST_MOVE_ITER2D_0TOMAX(9, BOOST_PAIR_PIECEWISE_CONSTRUCT_BOOST_TUPLE_CODE) + #undef BOOST_PAIR_PIECEWISE_CONSTRUCT_BOOST_TUPLE_CODE + + //piecewise construction from variadic tuple (with delegating constructors) + #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) + # if !defined(BOOST_CONTAINER_NO_CXX11_DELEGATING_CONSTRUCTORS) + private: + template<template<class ...> class Tuple, class... Args1, class... Args2, size_t... Indexes1, size_t... Indexes2> + pair(Tuple<Args1...>& t1, Tuple<Args2...>& t2, index_tuple<Indexes1...>, index_tuple<Indexes2...>) + : first (::boost::forward<Args1>(get<Indexes1>(t1))...) + , second(::boost::forward<Args2>(get<Indexes2>(t2))...) + { (void) t1; (void)t2; } + + public: + template<template<class ...> class Tuple, class... Args1, class... Args2> + pair(piecewise_construct_t, Tuple<Args1...> t1, Tuple<Args2...> t2) + : pair(t1, t2, typename build_number_seq<sizeof...(Args1)>::type(), typename build_number_seq<sizeof...(Args2)>::type()) + {} + # else + //piecewise construction from variadic tuple (suboptimal, without delegating constructors) + private: + template<typename T, template<class ...> class Tuple, typename... Args> + static T build_from_args(Tuple<Args...>&& t) + { return do_build_from_args<T>(::boost::move(t), typename build_number_seq<sizeof...(Args)>::type()); } + + template<typename T, template<class ...> class Tuple, typename... Args, std::size_t... Indexes> + static T do_build_from_args(Tuple<Args...> && t, const index_tuple<Indexes...>&) + { (void)t; return T(::boost::forward<Args>(get<Indexes>(t))...); } + + public: + template<template<class ...> class Tuple, class... Args1, class... Args2> + pair(piecewise_construct_t, Tuple<Args1...> t1, Tuple<Args2...> t2) + : first (build_from_args<first_type> (::boost::move(t1))) + , second (build_from_args<second_type>(::boost::move(t2))) + {} + # endif //BOOST_NO_CXX11_VARIADIC_TEMPLATES + #elif defined(BOOST_MSVC) && (_CPPLIB_VER == 520) + //MSVC 2010 tuple implementation + #define BOOST_PAIR_PIECEWISE_CONSTRUCT_MSVC2010_TUPLE_CODE(N,M)\ + template< template<class, class, class, class, class, class, class, class, class, class> class StdTuple \ + BOOST_MOVE_I_IF(BOOST_MOVE_OR(N,M)) BOOST_MOVE_CLASS##N BOOST_MOVE_I_IF(BOOST_MOVE_AND(N,M)) BOOST_MOVE_CLASSQ##M > \ + pair( piecewise_construct_t\ + , StdTuple<BOOST_MOVE_TARG##N BOOST_MOVE_I##N BOOST_MOVE_REPEAT(BOOST_MOVE_SUB(10,N),::std::tr1::_Nil)> p\ + , StdTuple<BOOST_MOVE_TARGQ##M BOOST_MOVE_I##M BOOST_MOVE_REPEAT(BOOST_MOVE_SUB(10,M),::std::tr1::_Nil)> q)\ + : first(BOOST_MOVE_GET_IDX##N), second(BOOST_MOVE_GET_IDXQ##M)\ + { (void)p; (void)q; }\ + // + BOOST_MOVE_ITER2D_0TOMAX(9, BOOST_PAIR_PIECEWISE_CONSTRUCT_MSVC2010_TUPLE_CODE) + #undef BOOST_PAIR_PIECEWISE_CONSTRUCT_MSVC2010_TUPLE_CODE + #elif defined(BOOST_MSVC) && (_CPPLIB_VER == 540) + #if _VARIADIC_MAX >= 9 + #define BOOST_PAIR_PIECEWISE_CONSTRUCT_MSVC2012_TUPLE_MAX_IT 9 + #else + #define BOOST_PAIR_PIECEWISE_CONSTRUCT_MSVC2012_TUPLE_MAX_IT BOOST_MOVE_ADD(_VARIADIC_MAX, 1) + #endif + + //MSVC 2012 tuple implementation + #define BOOST_PAIR_PIECEWISE_CONSTRUCT_MSVC2012_TUPLE_CODE(N,M)\ + template< template<BOOST_MOVE_REPEAT(_VARIADIC_MAX, class), class, class, class> class StdTuple \ + BOOST_MOVE_I_IF(BOOST_MOVE_OR(N,M)) BOOST_MOVE_CLASS##N BOOST_MOVE_I_IF(BOOST_MOVE_AND(N,M)) BOOST_MOVE_CLASSQ##M > \ + pair( piecewise_construct_t\ + , StdTuple<BOOST_MOVE_TARG##N BOOST_MOVE_I##N BOOST_MOVE_REPEAT(BOOST_MOVE_SUB(BOOST_MOVE_ADD(_VARIADIC_MAX, 3),N),::std::_Nil) > p\ + , StdTuple<BOOST_MOVE_TARGQ##M BOOST_MOVE_I##M BOOST_MOVE_REPEAT(BOOST_MOVE_SUB(BOOST_MOVE_ADD(_VARIADIC_MAX, 3),M),::std::_Nil) > q)\ + : first(BOOST_MOVE_GET_IDX##N), second(BOOST_MOVE_GET_IDXQ##M)\ + { (void)p; (void)q; }\ + // + BOOST_MOVE_ITER2D_0TOMAX(BOOST_PAIR_PIECEWISE_CONSTRUCT_MSVC2012_TUPLE_MAX_IT, BOOST_PAIR_PIECEWISE_CONSTRUCT_MSVC2012_TUPLE_CODE) + #undef BOOST_PAIR_PIECEWISE_CONSTRUCT_MSVC2010_TUPLE_CODE + #undef BOOST_PAIR_PIECEWISE_CONSTRUCT_MSVC2012_TUPLE_MAX_IT + #endif //pair copy assignment pair& operator=(BOOST_COPY_ASSIGN_REF(pair) p) @@ -283,6 +429,12 @@ struct is_enum< ::boost::container::container_detail::pair<T, U> > static const bool value = false; }; +template<class T, class U> +struct is_enum< ::std::pair<T, U> > +{ + static const bool value = false; +}; + template <class T> struct is_class; @@ -325,8 +477,43 @@ struct is_class_or_union< std::pair<T1, T2> > static const bool value = true; }; +template<class T> +struct is_union; + +template <class T1, class T2> +struct is_union< ::boost::container::container_detail::pair<T1, T2> > +//This specialization is needed to avoid instantiation of pair in +//is_class, and allow recursive maps. +{ + static const bool value = false; +}; + +template <class T1, class T2> +struct is_union< std::pair<T1, T2> > +//This specialization is needed to avoid instantiation of pair in +//is_class, and allow recursive maps. +{ + static const bool value = false; +}; +template<class T> +struct is_class; +template <class T1, class T2> +struct is_class< ::boost::container::container_detail::pair<T1, T2> > +//This specialization is needed to avoid instantiation of pair in +//is_class, and allow recursive maps. +{ + static const bool value = true; +}; + +template <class T1, class T2> +struct is_class< std::pair<T1, T2> > +//This specialization is needed to avoid instantiation of pair in +//is_class, and allow recursive maps. +{ + static const bool value = true; +}; } //namespace move_detail{ diff --git a/boost/container/detail/tree.hpp b/boost/container/detail/tree.hpp index 0fd6097650..853d0ad843 100644 --- a/boost/container/detail/tree.hpp +++ b/boost/container/detail/tree.hpp @@ -25,6 +25,7 @@ #include <boost/container/allocator_traits.hpp> #include <boost/container/container_fwd.hpp> #include <boost/container/options.hpp> +#include <boost/container/node_handle.hpp> // container/detail #include <boost/container/detail/algorithm.hpp> //algo_equal(), algo_lexicographical_compare @@ -135,7 +136,7 @@ struct tree_node typedef typename tree_internal_data_type<T>::type internal_type; typedef tree_node< T, VoidPointer - , tree_type_value, OptimizeSize> node_type; + , tree_type_value, OptimizeSize> node_t; BOOST_CONTAINER_FORCEINLINE T &get_data() { @@ -199,11 +200,11 @@ class insert_equal_end_hint_functor Icont &icont_; public: - insert_equal_end_hint_functor(Icont &icont) + BOOST_CONTAINER_FORCEINLINE insert_equal_end_hint_functor(Icont &icont) : icont_(icont) {} - void operator()(Node &n) + BOOST_CONTAINER_FORCEINLINE void operator()(Node &n) { this->icont_.insert_equal(this->icont_.cend(), n); } }; @@ -213,11 +214,11 @@ class push_back_functor Icont &icont_; public: - push_back_functor(Icont &icont) + BOOST_CONTAINER_FORCEINLINE push_back_functor(Icont &icont) : icont_(icont) {} - void operator()(Node &n) + BOOST_CONTAINER_FORCEINLINE void operator()(Node &n) { this->icont_.push_back(n); } }; @@ -294,18 +295,18 @@ struct intrusive_tree_type allocator_traits<Allocator>::size_type size_type; typedef typename container_detail::tree_node < value_type, void_pointer - , tree_type_value, OptimizeSize> node_type; + , tree_type_value, OptimizeSize> node_t; typedef value_to_node_compare - <node_type, ValueCompare> node_compare_type; - //Deducing the hook type from node_type (e.g. node_type::hook_type) would - //provoke an early instantiation of node_type that could ruin recursive + <node_t, ValueCompare> node_compare_type; + //Deducing the hook type from node_t (e.g. node_t::hook_type) would + //provoke an early instantiation of node_t that could ruin recursive //tree definitions, so retype the complete type to avoid any problem. typedef typename intrusive_tree_hook <void_pointer, tree_type_value , OptimizeSize>::type hook_type; public: typedef typename intrusive_tree_dispatch - < node_type, node_compare_type + < node_t, node_compare_type , size_type, hook_type , tree_type_value>::type type; }; @@ -328,14 +329,14 @@ template< boost::container::tree_type_enum tree_type_value struct intrusive_tree_proxy { template<class Icont> - static void rebalance(Icont &) {} + BOOST_CONTAINER_FORCEINLINE static void rebalance(Icont &) {} }; template<boost::container::tree_type_enum tree_type_value> struct intrusive_tree_proxy<tree_type_value, true> { template<class Icont> - static void rebalance(Icont &c) + BOOST_CONTAINER_FORCEINLINE static void rebalance(Icont &c) { c.rebalance(); } }; @@ -351,7 +352,7 @@ template<class AllocHolder, bool DoMove> class RecyclingCloner { typedef typename AllocHolder::intrusive_container intrusive_container; - typedef typename AllocHolder::Node node_type; + typedef typename AllocHolder::Node node_t; typedef typename AllocHolder::NodePtr node_ptr_type; public: @@ -359,13 +360,13 @@ class RecyclingCloner : m_holder(holder), m_icont(itree) {} - static void do_assign(node_ptr_type &p, const node_type &other, bool_<true>) - { p->do_move_assign(const_cast<node_type &>(other).m_data); } + BOOST_CONTAINER_FORCEINLINE static void do_assign(node_ptr_type &p, const node_t &other, bool_<true>) + { p->do_move_assign(const_cast<node_t &>(other).m_data); } - static void do_assign(node_ptr_type &p, const node_type &other, bool_<false>) + BOOST_CONTAINER_FORCEINLINE static void do_assign(node_ptr_type &p, const node_t &other, bool_<false>) { p->do_assign(other.m_data); } - node_ptr_type operator()(const node_type &other) const + node_ptr_type operator()(const node_t &other) const { if(node_ptr_type p = m_icont.unlink_leftmost_without_rebalance()){ //First recycle a node (this can't throw) @@ -393,59 +394,63 @@ class RecyclingCloner intrusive_container &m_icont; }; -template<class KeyValueCompare, class Node> -//where KeyValueCompare is tree_value_compare<Key, T, Compare, KeyOfValue> +template<class KeyCompare, class KeyOfValue> struct key_node_compare - : private KeyValueCompare + : public boost::intrusive::detail::ebo_functor_holder<KeyCompare> { - explicit key_node_compare(const KeyValueCompare &comp) - : KeyValueCompare(comp) + BOOST_CONTAINER_FORCEINLINE explicit key_node_compare(const KeyCompare &comp) + : base_t(comp) {} - template<class T> - struct is_node - { - static const bool value = is_same<T, Node>::value; - }; - - template<class T> - typename enable_if_c<is_node<T>::value, const typename KeyValueCompare::value_type &>::type - key_forward(const T &node) const - { return node.get_data(); } - - template<class T> - #if defined(BOOST_MOVE_HELPERS_RETURN_SFINAE_BROKEN) - const T &key_forward(const T &key, typename enable_if_c<!is_node<T>::value>::type* =0) const - #else - typename enable_if_c<!is_node<T>::value, const T &>::type key_forward(const T &key) const - #endif - { return key; } - - template<class KeyType, class KeyType2> - bool operator()(const KeyType &key1, const KeyType2 &key2) const - { return KeyValueCompare::operator()(this->key_forward(key1), this->key_forward(key2)); } + typedef boost::intrusive::detail::ebo_functor_holder<KeyCompare> base_t; + typedef KeyCompare key_compare; + typedef KeyOfValue key_of_value; + typedef typename KeyOfValue::type key_type; + + BOOST_CONTAINER_FORCEINLINE const key_compare &key_comp() const + { return static_cast<const key_compare &>(*this); } + + BOOST_CONTAINER_FORCEINLINE key_compare &key_comp() + { return static_cast<key_compare &>(*this); } + + BOOST_CONTAINER_FORCEINLINE bool operator()(const key_type &key1, const key_type &key2) const + { return this->key_comp()(key1, key2); } + + template<class U> + BOOST_CONTAINER_FORCEINLINE bool operator()(const key_type &key1, const U &nonkey2) const + { return this->key_comp()(key1, key_of_value()(nonkey2.get_data())); } + + template<class U> + BOOST_CONTAINER_FORCEINLINE bool operator()(const U &nonkey1, const key_type &key2) const + { return this->key_comp()(key_of_value()(nonkey1.get_data()), key2); } + + template<class U, class V> + BOOST_CONTAINER_FORCEINLINE bool operator()(const U &nonkey1, const V &nonkey2) const + { return this->key_comp()(key_of_value()(nonkey1.get_data()), key_of_value()(nonkey2.get_data())); } }; -template <class Key, class T, class KeyOfValue, +template <class T, class KeyOfValue, class Compare, class Allocator, class Options = tree_assoc_defaults> class tree - : protected container_detail::node_alloc_holder + : public container_detail::node_alloc_holder < Allocator , typename container_detail::intrusive_tree_type - < Allocator, tree_value_compare<Key, T, Compare, KeyOfValue> //ValComp + < Allocator, tree_value_compare + <typename allocator_traits<Allocator>::pointer, Compare, KeyOfValue> , Options::tree_type, Options::optimize_size>::type > { typedef tree_value_compare - <Key, T, Compare, KeyOfValue> ValComp; + < typename allocator_traits<Allocator>::pointer + , Compare, KeyOfValue> ValComp; typedef typename container_detail::intrusive_tree_type < Allocator, ValComp, Options::tree_type , Options::optimize_size>::type Icont; typedef container_detail::node_alloc_holder <Allocator, Icont> AllocHolder; typedef typename AllocHolder::NodePtr NodePtr; - typedef tree < Key, T, KeyOfValue + typedef tree < T, KeyOfValue , Compare, Allocator, Options> ThisType; typedef typename AllocHolder::NodeAlloc NodeAlloc; typedef boost::container:: @@ -462,7 +467,7 @@ class tree public: - typedef Key key_type; + typedef typename KeyOfValue::type key_type; typedef T value_type; typedef Allocator allocator_type; typedef Compare key_compare; @@ -479,32 +484,36 @@ class tree allocator_traits<Allocator>::size_type size_type; typedef typename boost::container:: allocator_traits<Allocator>::difference_type difference_type; - typedef difference_type tree_difference_type; - typedef pointer tree_pointer; - typedef const_pointer tree_const_pointer; - typedef reference tree_reference; - typedef const_reference tree_const_reference; + typedef container_detail::iterator_from_iiterator + <iiterator, false> iterator; + typedef container_detail::iterator_from_iiterator + <iiterator, true > const_iterator; + typedef boost::container::reverse_iterator + <iterator> reverse_iterator; + typedef boost::container::reverse_iterator + <const_iterator> const_reverse_iterator; + typedef node_handle + < Node, value_type, allocator_type, void> node_type; + typedef insert_return_type_base + <iterator, node_type> insert_return_type; + typedef NodeAlloc stored_allocator_type; private: - typedef key_node_compare<value_compare, Node> KeyNodeCompare; + typedef key_node_compare<key_compare, KeyOfValue> KeyNodeCompare; public: - typedef container_detail::iterator_from_iiterator<iiterator, false> iterator; - typedef container_detail::iterator_from_iiterator<iiterator, true > const_iterator; - typedef boost::container::reverse_iterator<iterator> reverse_iterator; - typedef boost::container::reverse_iterator<const_iterator> const_reverse_iterator; - tree() + BOOST_CONTAINER_FORCEINLINE tree() : AllocHolder() {} - explicit tree(const key_compare& comp, const allocator_type& a = allocator_type()) + BOOST_CONTAINER_FORCEINLINE explicit tree(const key_compare& comp, const allocator_type& a = allocator_type()) : AllocHolder(ValComp(comp), a) {} - explicit tree(const allocator_type& a) + BOOST_CONTAINER_FORCEINLINE explicit tree(const allocator_type& a) : AllocHolder(a) {} @@ -604,18 +613,19 @@ class tree , container_detail::push_back_functor<Node, Icont>(this->icont())); } - tree(const tree& x) + BOOST_CONTAINER_FORCEINLINE tree(const tree& x) : AllocHolder(x.value_comp(), x) { this->icont().clone_from (x.icont(), typename AllocHolder::cloner(*this), Destroyer(this->node_alloc())); } - tree(BOOST_RV_REF(tree) x) + BOOST_CONTAINER_FORCEINLINE tree(BOOST_RV_REF(tree) x) + BOOST_NOEXCEPT_IF(boost::container::container_detail::is_nothrow_move_constructible<Compare>::value) : AllocHolder(BOOST_MOVE_BASE(AllocHolder, x), x.value_comp()) {} - tree(const tree& x, const allocator_type &a) + BOOST_CONTAINER_FORCEINLINE tree(const tree& x, const allocator_type &a) : AllocHolder(x.value_comp(), a) { this->icont().clone_from @@ -634,7 +644,7 @@ class tree } } - ~tree() + BOOST_CONTAINER_FORCEINLINE ~tree() {} //AllocHolder clears the tree tree& operator=(BOOST_COPY_ASSIGN_REF(tree) x) @@ -669,8 +679,9 @@ class tree } tree& operator=(BOOST_RV_REF(tree) x) - BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value - && boost::container::container_detail::is_nothrow_move_assignable<Compare>::value ) + BOOST_NOEXCEPT_IF( (allocator_traits_type::propagate_on_container_move_assignment::value || + allocator_traits_type::is_always_equal::value) && + boost::container::container_detail::is_nothrow_move_assignable<Compare>::value) { BOOST_ASSERT(this != &x); NodeAlloc &this_alloc = this->node_alloc(); @@ -712,43 +723,43 @@ class tree public: // accessors: - value_compare value_comp() const + BOOST_CONTAINER_FORCEINLINE value_compare value_comp() const { return this->icont().value_comp().predicate(); } - key_compare key_comp() const + BOOST_CONTAINER_FORCEINLINE key_compare key_comp() const { return this->icont().value_comp().predicate().key_comp(); } - allocator_type get_allocator() const + BOOST_CONTAINER_FORCEINLINE allocator_type get_allocator() const { return allocator_type(this->node_alloc()); } - const stored_allocator_type &get_stored_allocator() const + BOOST_CONTAINER_FORCEINLINE const stored_allocator_type &get_stored_allocator() const { return this->node_alloc(); } - stored_allocator_type &get_stored_allocator() + BOOST_CONTAINER_FORCEINLINE stored_allocator_type &get_stored_allocator() { return this->node_alloc(); } - iterator begin() + BOOST_CONTAINER_FORCEINLINE iterator begin() { return iterator(this->icont().begin()); } - const_iterator begin() const + BOOST_CONTAINER_FORCEINLINE const_iterator begin() const { return this->cbegin(); } - iterator end() + BOOST_CONTAINER_FORCEINLINE iterator end() { return iterator(this->icont().end()); } - const_iterator end() const + BOOST_CONTAINER_FORCEINLINE const_iterator end() const { return this->cend(); } - reverse_iterator rbegin() + BOOST_CONTAINER_FORCEINLINE reverse_iterator rbegin() { return reverse_iterator(end()); } - const_reverse_iterator rbegin() const + BOOST_CONTAINER_FORCEINLINE const_reverse_iterator rbegin() const { return this->crbegin(); } - reverse_iterator rend() + BOOST_CONTAINER_FORCEINLINE reverse_iterator rend() { return reverse_iterator(begin()); } - const_reverse_iterator rend() const + BOOST_CONTAINER_FORCEINLINE const_reverse_iterator rend() const { return this->crend(); } //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container. @@ -756,7 +767,7 @@ class tree //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Constant. - const_iterator cbegin() const + BOOST_CONTAINER_FORCEINLINE const_iterator cbegin() const { return const_iterator(this->non_const_icont().begin()); } //! <b>Effects</b>: Returns a const_iterator to the end of the container. @@ -764,7 +775,7 @@ class tree //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Constant. - const_iterator cend() const + BOOST_CONTAINER_FORCEINLINE const_iterator cend() const { return const_iterator(this->non_const_icont().end()); } //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning @@ -773,7 +784,7 @@ class tree //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Constant. - const_reverse_iterator crbegin() const + BOOST_CONTAINER_FORCEINLINE const_reverse_iterator crbegin() const { return const_reverse_iterator(cend()); } //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end @@ -782,19 +793,19 @@ class tree //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Constant. - const_reverse_iterator crend() const + BOOST_CONTAINER_FORCEINLINE const_reverse_iterator crend() const { return const_reverse_iterator(cbegin()); } - bool empty() const + BOOST_CONTAINER_FORCEINLINE bool empty() const { return !this->size(); } - size_type size() const + BOOST_CONTAINER_FORCEINLINE size_type size() const { return this->icont().size(); } - size_type max_size() const + BOOST_CONTAINER_FORCEINLINE size_type max_size() const { return AllocHolder::max_size(); } - void swap(ThisType& x) + BOOST_CONTAINER_FORCEINLINE void swap(ThisType& x) BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value && boost::container::container_detail::is_nothrow_swappable<Compare>::value ) { AllocHolder::swap(x); } @@ -808,7 +819,7 @@ class tree (const key_type& key, insert_commit_data &data) { std::pair<iiterator, bool> ret = - this->icont().insert_unique_check(key, KeyNodeCompare(value_comp()), data); + this->icont().insert_unique_check(key, KeyNodeCompare(key_comp()), data); return std::pair<iterator, bool>(iterator(ret.first), ret.second); } @@ -817,19 +828,10 @@ class tree { BOOST_ASSERT((priv_is_linked)(hint)); std::pair<iiterator, bool> ret = - this->icont().insert_unique_check(hint.get(), key, KeyNodeCompare(value_comp()), data); + this->icont().insert_unique_check(hint.get(), key, KeyNodeCompare(key_comp()), data); return std::pair<iterator, bool>(iterator(ret.first), ret.second); } - iterator insert_unique_commit(const value_type& v, insert_commit_data &data) - { - NodePtr tmp = AllocHolder::create_node(v); - scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc()); - iterator ret(this->icont().insert_unique_commit(*tmp, data)); - destroy_deallocator.release(); - return ret; - } - template<class MovableConvertible> iterator insert_unique_commit (BOOST_FWD_REF(MovableConvertible) v, insert_commit_data &data) @@ -841,17 +843,6 @@ class tree return ret; } - std::pair<iterator,bool> insert_unique(const value_type& v) - { - insert_commit_data data; - std::pair<iterator,bool> ret = - this->insert_unique_check(KeyOfValue()(v), data); - if(ret.second){ - ret.first = this->insert_unique_commit(v, data); - } - return ret; - } - template<class MovableConvertible> std::pair<iterator,bool> insert_unique(BOOST_FWD_REF(MovableConvertible) v) { @@ -866,6 +857,17 @@ class tree private: + template<class KeyConvertible, class M> + iiterator priv_insert_or_assign_commit + (BOOST_FWD_REF(KeyConvertible) key, BOOST_FWD_REF(M) obj, insert_commit_data &data) + { + NodePtr tmp = AllocHolder::create_node(boost::forward<KeyConvertible>(key), boost::forward<M>(obj)); + scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc()); + iiterator ret(this->icont().insert_unique_commit(*tmp, data)); + destroy_deallocator.release(); + return ret; + } + bool priv_is_linked(const_iterator const position) const { iiterator const cur(position.get()); @@ -896,7 +898,7 @@ class tree //No throw insertion part, release rollback destroy_deallocator.release(); return std::pair<iterator,bool> - ( iterator(iiterator(this->icont().insert_unique_commit(*p, data))) + ( iterator(this->icont().insert_unique_commit(*p, data)) , true ); } @@ -911,7 +913,7 @@ class tree Destroyer(this->node_alloc())(p); return ret.first; } - return iterator(iiterator(this->icont().insert_unique_commit(*p, data))); + return iterator(this->icont().insert_unique_commit(*p, data)); } public: @@ -919,11 +921,11 @@ class tree #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) template <class... Args> - std::pair<iterator, bool> emplace_unique(BOOST_FWD_REF(Args)... args) + BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> emplace_unique(BOOST_FWD_REF(Args)... args) { return this->emplace_unique_impl(AllocHolder::create_node(boost::forward<Args>(args)...)); } template <class... Args> - iterator emplace_hint_unique(const_iterator hint, BOOST_FWD_REF(Args)... args) + BOOST_CONTAINER_FORCEINLINE iterator emplace_hint_unique(const_iterator hint, BOOST_FWD_REF(Args)... args) { return this->emplace_unique_hint_impl(hint, AllocHolder::create_node(boost::forward<Args>(args)...)); } template <class... Args> @@ -947,6 +949,22 @@ class tree return ret; } + template <class KeyType, class... Args> + BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> try_emplace + (const_iterator hint, BOOST_FWD_REF(KeyType) key, BOOST_FWD_REF(Args)... args) + { + insert_commit_data data; + const key_type & k = key; //Support emulated rvalue references + std::pair<iiterator, bool> ret = + hint == const_iterator() ? this->icont().insert_unique_check( k, KeyNodeCompare(key_comp()), data) + : this->icont().insert_unique_check(hint.get(), k, KeyNodeCompare(key_comp()), data); + if(ret.second){ + ret.first = this->icont().insert_unique_commit + (*AllocHolder::create_node(try_emplace_t(), boost::forward<KeyType>(key), boost::forward<Args>(args)...), data); + } + return std::pair<iterator, bool>(iterator(ret.first), ret.second); + } + #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) #define BOOST_CONTAINER_TREE_EMPLACE_CODE(N) \ @@ -978,6 +996,22 @@ class tree destroy_deallocator.release();\ return ret;\ }\ + \ + template <class KeyType BOOST_MOVE_I##N BOOST_MOVE_CLASS##N>\ + BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool>\ + try_emplace(const_iterator hint, BOOST_FWD_REF(KeyType) key BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ + {\ + insert_commit_data data;\ + const key_type & k = key;\ + std::pair<iiterator, bool> ret =\ + hint == const_iterator() ? this->icont().insert_unique_check( k, KeyNodeCompare(key_comp()), data)\ + : this->icont().insert_unique_check(hint.get(), k, KeyNodeCompare(key_comp()), data);\ + if(ret.second){\ + ret.first = this->icont().insert_unique_commit\ + (*AllocHolder::create_node(try_emplace_t(), boost::forward<KeyType>(key) BOOST_MOVE_I##N BOOST_MOVE_FWD##N), data);\ + }\ + return std::pair<iterator, bool>(iterator(ret.first), ret.second);\ + }\ // BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_TREE_EMPLACE_CODE) #undef BOOST_CONTAINER_TREE_EMPLACE_CODE @@ -1044,27 +1078,21 @@ class tree this->insert_equal(*first); } - template<class KeyConvertible> - iterator insert_from_key(BOOST_FWD_REF(KeyConvertible) key) + template<class KeyType, class M> + std::pair<iterator, bool> insert_or_assign(const_iterator hint, BOOST_FWD_REF(KeyType) key, BOOST_FWD_REF(M) obj) { insert_commit_data data; const key_type & k = key; //Support emulated rvalue references std::pair<iiterator, bool> ret = - this->icont().insert_unique_check(k, KeyNodeCompare(value_comp()), data); - return ret.second - ? this->insert_unique_key_commit(boost::forward<KeyConvertible>(key), data) - : iterator(ret.first); - } - - template<class KeyConvertible> - iterator insert_unique_key_commit - (BOOST_FWD_REF(KeyConvertible) key, insert_commit_data &data) - { - NodePtr tmp = AllocHolder::create_node_from_key(boost::forward<KeyConvertible>(key)); - scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc()); - iterator ret(this->icont().insert_unique_commit(*tmp, data)); - destroy_deallocator.release(); - return ret; + hint == const_iterator() ? this->icont().insert_unique_check(k, KeyNodeCompare(key_comp()), data) + : this->icont().insert_unique_check(hint.get(), k, KeyNodeCompare(key_comp()), data); + if(ret.second){ + ret.first = this->priv_insert_or_assign_commit(boost::forward<KeyType>(key), boost::forward<M>(obj), data); + } + else{ + ret.first->get_data().second = boost::forward<M>(obj); + } + return std::pair<iterator, bool>(iterator(ret.first), ret.second); } iterator erase(const_iterator position) @@ -1073,8 +1101,8 @@ class tree return iterator(this->icont().erase_and_dispose(position.get(), Destroyer(this->node_alloc()))); } - size_type erase(const key_type& k) - { return AllocHolder::erase_key(k, KeyNodeCompare(value_comp()), alloc_version()); } + BOOST_CONTAINER_FORCEINLINE size_type erase(const key_type& k) + { return AllocHolder::erase_key(k, KeyNodeCompare(key_comp()), alloc_version()); } iterator erase(const_iterator first, const_iterator last) { @@ -1083,43 +1111,117 @@ class tree return iterator(AllocHolder::erase_range(first.get(), last.get(), alloc_version())); } - void clear() + node_type extract(const key_type& k) + { + iterator const it = this->find(k); + if(this->end() != it){ + return this->extract(it); + } + return node_type(); + } + + node_type extract(const_iterator position) + { + BOOST_ASSERT(position != this->cend() && (priv_is_linked)(position)); + iiterator const iit(position.get()); + this->icont().erase(iit); + return node_type(iit.operator->(), this->node_alloc()); + } + + insert_return_type insert_unique_node(BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh) + { + return this->insert_unique_node(this->end(), boost::move(nh)); + } + + insert_return_type insert_unique_node(const_iterator hint, BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh) + { + insert_return_type irt; //inserted == false, node.empty() + if(!nh.empty()){ + insert_commit_data data; + std::pair<iterator,bool> ret = + this->insert_unique_check(hint, KeyOfValue()(nh.value()), data); + if(ret.second){ + irt.inserted = true; + irt.position = iterator(this->icont().insert_unique_commit(*nh.get_node_pointer(), data)); + nh.release(); + } + else{ + irt.position = ret.first; + irt.node = boost::move(nh); + } + } + else{ + irt.position = this->end(); + } + return BOOST_MOVE_RET(insert_return_type, irt); + } + + iterator insert_equal_node(BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh) + { + if(nh.empty()){ + return this->end(); + } + else{ + NodePtr const p(nh.release()); + return iterator(this->icont().insert_equal(*p)); + } + } + + iterator insert_equal_node(const_iterator hint, BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh) + { + if(nh.empty()){ + return this->end(); + } + else{ + NodePtr const p(nh.release()); + return iterator(this->icont().insert_equal(hint.get(), *p)); + } + } + + template<class C2> + BOOST_CONTAINER_FORCEINLINE void merge_unique(tree<T, KeyOfValue, C2, Allocator, Options>& source) + { return this->icont().merge_unique(source.icont()); } + + template<class C2> + BOOST_CONTAINER_FORCEINLINE void merge_equal(tree<T, KeyOfValue, C2, Allocator, Options>& source) + { return this->icont().merge_equal(source.icont()); } + BOOST_CONTAINER_FORCEINLINE void clear() { AllocHolder::clear(alloc_version()); } // search operations. Const and non-const overloads even if no iterator is returned // so splay implementations can to their rebalancing when searching in non-const versions - iterator find(const key_type& k) - { return iterator(this->icont().find(k, KeyNodeCompare(value_comp()))); } + BOOST_CONTAINER_FORCEINLINE iterator find(const key_type& k) + { return iterator(this->icont().find(k, KeyNodeCompare(key_comp()))); } - const_iterator find(const key_type& k) const - { return const_iterator(this->non_const_icont().find(k, KeyNodeCompare(value_comp()))); } + BOOST_CONTAINER_FORCEINLINE const_iterator find(const key_type& k) const + { return const_iterator(this->non_const_icont().find(k, KeyNodeCompare(key_comp()))); } - size_type count(const key_type& k) const - { return size_type(this->icont().count(k, KeyNodeCompare(value_comp()))); } + BOOST_CONTAINER_FORCEINLINE size_type count(const key_type& k) const + { return size_type(this->icont().count(k, KeyNodeCompare(key_comp()))); } - iterator lower_bound(const key_type& k) - { return iterator(this->icont().lower_bound(k, KeyNodeCompare(value_comp()))); } + BOOST_CONTAINER_FORCEINLINE iterator lower_bound(const key_type& k) + { return iterator(this->icont().lower_bound(k, KeyNodeCompare(key_comp()))); } - const_iterator lower_bound(const key_type& k) const - { return const_iterator(this->non_const_icont().lower_bound(k, KeyNodeCompare(value_comp()))); } + BOOST_CONTAINER_FORCEINLINE const_iterator lower_bound(const key_type& k) const + { return const_iterator(this->non_const_icont().lower_bound(k, KeyNodeCompare(key_comp()))); } - iterator upper_bound(const key_type& k) - { return iterator(this->icont().upper_bound(k, KeyNodeCompare(value_comp()))); } + BOOST_CONTAINER_FORCEINLINE iterator upper_bound(const key_type& k) + { return iterator(this->icont().upper_bound(k, KeyNodeCompare(key_comp()))); } - const_iterator upper_bound(const key_type& k) const - { return const_iterator(this->non_const_icont().upper_bound(k, KeyNodeCompare(value_comp()))); } + BOOST_CONTAINER_FORCEINLINE const_iterator upper_bound(const key_type& k) const + { return const_iterator(this->non_const_icont().upper_bound(k, KeyNodeCompare(key_comp()))); } std::pair<iterator,iterator> equal_range(const key_type& k) { std::pair<iiterator, iiterator> ret = - this->icont().equal_range(k, KeyNodeCompare(value_comp())); + this->icont().equal_range(k, KeyNodeCompare(key_comp())); return std::pair<iterator,iterator>(iterator(ret.first), iterator(ret.second)); } std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const { std::pair<iiterator, iiterator> ret = - this->non_const_icont().equal_range(k, KeyNodeCompare(value_comp())); + this->non_const_icont().equal_range(k, KeyNodeCompare(key_comp())); return std::pair<const_iterator,const_iterator> (const_iterator(ret.first), const_iterator(ret.second)); } @@ -1127,40 +1229,40 @@ class tree std::pair<iterator,iterator> lower_bound_range(const key_type& k) { std::pair<iiterator, iiterator> ret = - this->icont().lower_bound_range(k, KeyNodeCompare(value_comp())); + this->icont().lower_bound_range(k, KeyNodeCompare(key_comp())); return std::pair<iterator,iterator>(iterator(ret.first), iterator(ret.second)); } std::pair<const_iterator, const_iterator> lower_bound_range(const key_type& k) const { std::pair<iiterator, iiterator> ret = - this->non_const_icont().lower_bound_range(k, KeyNodeCompare(value_comp())); + this->non_const_icont().lower_bound_range(k, KeyNodeCompare(key_comp())); return std::pair<const_iterator,const_iterator> (const_iterator(ret.first), const_iterator(ret.second)); } - void rebalance() + BOOST_CONTAINER_FORCEINLINE void rebalance() { intrusive_tree_proxy_t::rebalance(this->icont()); } - friend bool operator==(const tree& x, const tree& y) + BOOST_CONTAINER_FORCEINLINE friend bool operator==(const tree& x, const tree& y) { return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin()); } - friend bool operator<(const tree& x, const tree& y) + BOOST_CONTAINER_FORCEINLINE friend bool operator<(const tree& x, const tree& y) { return ::boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); } - friend bool operator!=(const tree& x, const tree& y) + BOOST_CONTAINER_FORCEINLINE friend bool operator!=(const tree& x, const tree& y) { return !(x == y); } - friend bool operator>(const tree& x, const tree& y) + BOOST_CONTAINER_FORCEINLINE friend bool operator>(const tree& x, const tree& y) { return y < x; } - friend bool operator<=(const tree& x, const tree& y) + BOOST_CONTAINER_FORCEINLINE friend bool operator<=(const tree& x, const tree& y) { return !(y < x); } - friend bool operator>=(const tree& x, const tree& y) + BOOST_CONTAINER_FORCEINLINE friend bool operator>=(const tree& x, const tree& y) { return !(x < y); } - friend void swap(tree& x, tree& y) + BOOST_CONTAINER_FORCEINLINE friend void swap(tree& x, tree& y) { x.swap(y); } }; @@ -1172,11 +1274,11 @@ struct has_trivial_destructor_after_move; //!has_trivial_destructor_after_move<> == true_type //!specialization for optimizations -template <class Key, class T, class KeyOfValue, class Compare, class Allocator, class Options> +template <class T, class KeyOfValue, class Compare, class Allocator, class Options> struct has_trivial_destructor_after_move < ::boost::container::container_detail::tree - <Key, T, KeyOfValue, Compare, Allocator, Options> + <T, KeyOfValue, Compare, Allocator, Options> > { typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer; diff --git a/boost/container/detail/value_init.hpp b/boost/container/detail/value_init.hpp index eb4c976d92..faba70ee14 100644 --- a/boost/container/detail/value_init.hpp +++ b/boost/container/detail/value_init.hpp @@ -37,6 +37,8 @@ struct value_init operator T &() { return m_t; } + T &get() { return m_t; } + T m_t; }; diff --git a/boost/container/detail/variadic_templates_tools.hpp b/boost/container/detail/variadic_templates_tools.hpp index d8c8443038..f5101c577c 100644 --- a/boost/container/detail/variadic_templates_tools.hpp +++ b/boost/container/detail/variadic_templates_tools.hpp @@ -21,6 +21,7 @@ #include <boost/container/detail/config_begin.hpp> #include <boost/container/detail/workaround.hpp> +#include <boost/move/utility_core.hpp> #include <boost/container/detail/type_traits.hpp> #include <cstddef> //std::size_t @@ -42,13 +43,13 @@ class tuple<Head, Tail...> typedef tuple<Tail...> inherited; public: - tuple() { } + tuple() + : inherited(), m_head() + {} - // implicit copy-constructor is okay - // Construct tuple from separate arguments. - tuple(typename add_const_reference<Head>::type v, - typename add_const_reference<Tail>::type... vtail) - : inherited(vtail...), m_head(v) + template<class U, class ...Args> + tuple(U &&u, Args && ...args) + : inherited(::boost::forward<Args>(args)...), m_head(::boost::forward<U>(u)) {} // Construct tuple from another tuple. @@ -77,8 +78,8 @@ class tuple<Head, Tail...> template<typename... Values> -tuple<Values&&...> tie_forward(Values&&... values) -{ return tuple<Values&&...>(values...); } +tuple<Values&&...> forward_as_tuple(Values&&... values) +{ return tuple<Values&&...>(::boost::forward<Values>(values)...); } template<int I, typename Tuple> struct tuple_element; @@ -135,18 +136,18 @@ typename get_impl<I, tuple<Values...> >::const_type get(const tuple<Values...>& // in a function call. //////////////////////////////////////////////////// -template<int... Indexes> +template<std::size_t ... Indexes> struct index_tuple{}; template<std::size_t Num, typename Tuple = index_tuple<> > struct build_number_seq; -template<std::size_t Num, int... Indexes> +template<std::size_t Num, std::size_t ... Indexes> struct build_number_seq<Num, index_tuple<Indexes...> > : build_number_seq<Num - 1, index_tuple<Indexes..., sizeof...(Indexes)> > {}; -template<int... Indexes> +template<std::size_t ... Indexes> struct build_number_seq<0, index_tuple<Indexes...> > { typedef index_tuple<Indexes...> type; }; diff --git a/boost/container/detail/workaround.hpp b/boost/container/detail/workaround.hpp index ae9151c32d..64ecd6fd6b 100644 --- a/boost/container/detail/workaround.hpp +++ b/boost/container/detail/workaround.hpp @@ -29,12 +29,30 @@ #define BOOST_CONTAINER_UNIMPLEMENTED_PACK_EXPANSION_TO_FIXED_LIST #endif +#if defined(BOOST_GCC_VERSION) +# if (BOOST_GCC_VERSION < 40700) || !defined(BOOST_GCC_CXX11) +# define BOOST_CONTAINER_NO_CXX11_DELEGATING_CONSTRUCTORS +# endif +#elif defined(BOOST_MSVC) +# if _MSC_FULL_VER < 180020827 +# define BOOST_CONTAINER_NO_CXX11_DELEGATING_CONSTRUCTORS +# endif +#elif defined(BOOST_CLANG) +# if !__has_feature(cxx_delegating_constructors) +# define BOOST_CONTAINER_NO_CXX11_DELEGATING_CONSTRUCTORS +# endif +#endif + #if !defined(BOOST_FALLTHOUGH) #define BOOST_CONTAINER_FALLTHOUGH #else #define BOOST_CONTAINER_FALLTHOUGH BOOST_FALLTHOUGH; #endif +#if !defined(BOOST_NO_CXX11_HDR_TUPLE) || (defined(BOOST_MSVC) && (BOOST_MSVC == 1700 || BOOST_MSVC == 1600)) +#define BOOST_CONTAINER_PAIR_TEST_HAS_HEADER_TUPLE +#endif + //Macros for documentation purposes. For code, expands to the argument #define BOOST_CONTAINER_IMPDEF(TYPE) TYPE #define BOOST_CONTAINER_SEEDOC(TYPE) TYPE |