summaryrefslogtreecommitdiff
path: root/boost/container/detail
diff options
context:
space:
mode:
Diffstat (limited to 'boost/container/detail')
-rw-r--r--boost/container/detail/advanced_insert_int.hpp2
-rw-r--r--boost/container/detail/container_or_allocator_rebind.hpp49
-rw-r--r--boost/container/detail/container_rebind.hpp258
-rw-r--r--boost/container/detail/copy_move_algo.hpp14
-rw-r--r--boost/container/detail/destroyers.hpp4
-rw-r--r--boost/container/detail/flat_tree.hpp522
-rw-r--r--boost/container/detail/is_container.hpp55
-rw-r--r--boost/container/detail/is_contiguous_container.hpp47
-rw-r--r--boost/container/detail/workaround.hpp6
9 files changed, 821 insertions, 136 deletions
diff --git a/boost/container/detail/advanced_insert_int.hpp b/boost/container/detail/advanced_insert_int.hpp
index 20adb523a6..db5e8df252 100644
--- a/boost/container/detail/advanced_insert_int.hpp
+++ b/boost/container/detail/advanced_insert_int.hpp
@@ -163,7 +163,7 @@ struct insert_copy_proxy
void copy_n_and_update(Allocator &, Iterator p, size_type n) const
{
BOOST_ASSERT(n == 1); (void)n;
- *p =v_;
+ *p = v_;
}
const value_type &v_;
diff --git a/boost/container/detail/container_or_allocator_rebind.hpp b/boost/container/detail/container_or_allocator_rebind.hpp
new file mode 100644
index 0000000000..c60d1c0c50
--- /dev/null
+++ b/boost/container/detail/container_or_allocator_rebind.hpp
@@ -0,0 +1,49 @@
+//////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2017-2017. 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_CONTAINER_OR_ALLOCATOR_REBIND_HPP
+#define BOOST_CONTAINER_DETAIL_CONTAINER_OR_ALLOCATOR_REBIND_HPP
+
+#ifndef BOOST_CONFIG_HPP
+# include <boost/config.hpp>
+#endif
+
+#if defined(BOOST_HAS_PRAGMA_ONCE)
+# pragma once
+#endif
+
+#include <boost/container/allocator_traits.hpp>
+#include <boost/container/detail/container_rebind.hpp>
+#include <boost/container/detail/is_container.hpp>
+
+namespace boost {
+namespace container {
+namespace container_detail {
+
+template<class AllocatorOrContainer, class ToType, bool = is_container<AllocatorOrContainer>::value>
+struct container_or_allocator_rebind_impl
+ : container_rebind<AllocatorOrContainer, ToType>
+{};
+
+template<class AllocatorOrContainer, class ToType>
+struct container_or_allocator_rebind_impl<AllocatorOrContainer, ToType, false>
+ : allocator_traits<AllocatorOrContainer>::template portable_rebind_alloc<ToType>
+
+{};
+
+template<class AllocatorOrContainer, class ToType>
+struct container_or_allocator_rebind
+ : container_or_allocator_rebind_impl<AllocatorOrContainer, ToType>
+{};
+
+} //namespace container_detail {
+} //namespace container {
+} //namespace boost {
+
+#endif //#ifndef BOOST_CONTAINER_DETAIL_CONTAINER_OR_ALLOCATOR_REBIND_HPP
diff --git a/boost/container/detail/container_rebind.hpp b/boost/container/detail/container_rebind.hpp
new file mode 100644
index 0000000000..79ad9d7739
--- /dev/null
+++ b/boost/container/detail/container_rebind.hpp
@@ -0,0 +1,258 @@
+//////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2017-2017. 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_CONTAINER_REBIND_HPP
+#define BOOST_CONTAINER_DETAIL_CONTAINER_REBIND_HPP
+
+#ifndef BOOST_CONFIG_HPP
+# include <boost/config.hpp>
+#endif
+
+#if defined(BOOST_HAS_PRAGMA_ONCE)
+# pragma once
+#endif
+
+#include <boost/container/allocator_traits.hpp>
+
+
+namespace boost {
+namespace container {
+namespace container_detail {
+
+ template <class Cont, class U>
+ struct container_rebind;
+
+#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
+
+ template <template <class, class, class...> class Cont, typename V, typename A, class... An, class U>
+ struct container_rebind<Cont<V, A, An...>, U>
+ {
+ typedef Cont<U, typename allocator_traits<A>::template portable_rebind_alloc<U>::type, An...> type;
+ };
+
+ //Needed for non-conforming compilers like GCC 4.3
+ template <template <class, class> class Cont, typename V, typename A, class U>
+ struct container_rebind<Cont<V, A>, U>
+ {
+ typedef Cont<U, typename allocator_traits<A>::template portable_rebind_alloc<U>::type> type;
+ };
+
+ template <template <class> class Cont, typename V, class U>
+ struct container_rebind<Cont<V>, U>
+ {
+ typedef Cont<U> type;
+ };
+
+ //for small_vector,static_vector
+
+ template <template <class, std::size_t, class, class...> class Cont, typename V, std::size_t N, typename A, class... An, class U>
+ struct container_rebind<Cont<V, N, A, An...>, U>
+ {
+ typedef Cont<U, N, typename allocator_traits<A>::template portable_rebind_alloc<U>::type, An...> type;
+ };
+
+ //Needed for non-conforming compilers like GCC 4.3
+ template <template <class, std::size_t, class> class Cont, typename V, std::size_t N, typename A, class U>
+ struct container_rebind<Cont<V, N, A>, U>
+ {
+ typedef Cont<U, N, typename allocator_traits<A>::template portable_rebind_alloc<U>::type> type;
+ };
+
+ template <template <class, std::size_t> class Cont, typename V, std::size_t N, class U>
+ struct container_rebind<Cont<V, N>, U>
+ {
+ typedef Cont<U, N> type;
+ };
+
+#else //C++03 compilers
+
+ template <template <class> class Cont //0arg
+ , typename V
+ , class U>
+ struct container_rebind<Cont<V>, U>
+ {
+ typedef Cont<U> type;
+ };
+
+ template <template <class, class> class Cont //0arg
+ , typename V, typename A
+ , class U>
+ struct container_rebind<Cont<V, A>, U>
+ {
+ typedef Cont<U, typename allocator_traits<A>::template portable_rebind_alloc<U>::type> type;
+ };
+
+ template <template <class, class, class> class Cont //1arg
+ , typename V, typename A, class P0
+ , class U>
+ struct container_rebind<Cont<V, A, P0>, U>
+ {
+ typedef Cont<U, typename allocator_traits<A>::template portable_rebind_alloc<U>::type, P0> type;
+ };
+
+ template <template <class, class, class, class> class Cont //2arg
+ , typename V, typename A, class P0, class P1
+ , class U>
+ struct container_rebind<Cont<V, A, P0, P1>, U>
+ {
+ typedef Cont<U, typename allocator_traits<A>::template portable_rebind_alloc<U>::type, P0, P1> type;
+ };
+
+ template <template <class, class, class, class, class> class Cont //3arg
+ , typename V, typename A, class P0, class P1, class P2
+ , class U>
+ struct container_rebind<Cont<V, A, P0, P1, P2>, U>
+ {
+ typedef Cont<U, typename allocator_traits<A>::template portable_rebind_alloc<U>::type, P0, P1, P2> type;
+ };
+
+ template <template <class, class, class, class, class, class> class Cont //4arg
+ , typename V, typename A, class P0, class P1, class P2, class P3
+ , class U>
+ struct container_rebind<Cont<V, A, P0, P1, P2, P3>, U>
+ {
+ typedef Cont<U, typename allocator_traits<A>::template portable_rebind_alloc<U>::type, P0, P1, P2, P3> type;
+ };
+
+ template <template <class, class, class, class, class, class, class> class Cont //5arg
+ , typename V, typename A, class P0, class P1, class P2, class P3, class P4
+ , class U>
+ struct container_rebind<Cont<V, A, P0, P1, P2, P3, P4>, U>
+ {
+ typedef Cont<U, typename allocator_traits<A>::template portable_rebind_alloc<U>::type, P0, P1, P2, P3, P4> type;
+ };
+
+ template <template <class, class, class, class, class, class, class, class> class Cont //6arg
+ , typename V, typename A, class P0, class P1, class P2, class P3, class P4, class P5
+ , class U>
+ struct container_rebind<Cont<V, A, P0, P1, P2, P3, P4, P5>, U>
+ {
+ typedef Cont<U, typename allocator_traits<A>::template portable_rebind_alloc<U>::type, P0, P1, P2, P3, P4, P5> type;
+ };
+
+ template <template <class, class, class, class, class, class, class, class, class> class Cont //7arg
+ , typename V, typename A, class P0, class P1, class P2, class P3, class P4, class P5, class P6
+ , class U>
+ struct container_rebind<Cont<V, A, P0, P1, P2, P3, P4, P5, P6>, U>
+ {
+ typedef Cont<U, typename allocator_traits<A>::template portable_rebind_alloc<U>::type, P0, P1, P2, P3, P4, P5, P6> type;
+ };
+
+ template <template <class, class, class, class, class, class, class, class, class, class> class Cont //8arg
+ , typename V, typename A, class P0, class P1, class P2, class P3, class P4, class P5, class P6, class P7
+ , class U>
+ struct container_rebind<Cont<V, A, P0, P1, P2, P3, P4, P5, P6, P7>, U>
+ {
+ typedef Cont<U, typename allocator_traits<A>::template portable_rebind_alloc<U>::type, P0, P1, P2, P3, P4, P5, P6, P7> type;
+ };
+
+ template <template <class, class, class, class, class, class, class, class, class, class, class> class Cont //9arg
+ , typename V, typename A, class P0, class P1, class P2, class P3, class P4, class P5, class P6, class P7, class P8
+ , class U>
+ struct container_rebind<Cont<V, A, P0, P1, P2, P3, P4, P5, P6, P7, P8>, U>
+ {
+ typedef Cont<U, typename allocator_traits<A>::template portable_rebind_alloc<U>::type, P0, P1, P2, P3, P4, P5, P6, P7, P8> type;
+ };
+
+ //For small_vector/static_vector
+ template <template <class, std::size_t> class Cont //0arg
+ , typename V, std::size_t N
+ , class U>
+ struct container_rebind<Cont<V, N>, U>
+ {
+ typedef Cont<U, N> type;
+ };
+
+ template <template <class, std::size_t, class> class Cont //0arg
+ , typename V, std::size_t N, typename A
+ , class U>
+ struct container_rebind<Cont<V, N, A>, U>
+ {
+ typedef Cont<U, N, typename allocator_traits<A>::template portable_rebind_alloc<U>::type> type;
+ };
+
+ template <template <class, std::size_t, class, class> class Cont //1arg
+ , typename V, std::size_t N, typename A, class P0
+ , class U>
+ struct container_rebind<Cont<V, N, A, P0>, U>
+ {
+ typedef Cont<U, N, typename allocator_traits<A>::template portable_rebind_alloc<U>::type, P0> type;
+ };
+
+ template <template <class, std::size_t, class, class, class> class Cont //2arg
+ , typename V, std::size_t N, typename A, class P0, class P1
+ , class U>
+ struct container_rebind<Cont<V, N, A, P0, P1>, U>
+ {
+ typedef Cont<U, N, typename allocator_traits<A>::template portable_rebind_alloc<U>::type, P0, P1> type;
+ };
+
+ template <template <class, std::size_t, class, class, class, class> class Cont //3arg
+ , typename V, std::size_t N, typename A, class P0, class P1, class P2
+ , class U>
+ struct container_rebind<Cont<V, N, A, P0, P1, P2>, U>
+ {
+ typedef Cont<U, N, typename allocator_traits<A>::template portable_rebind_alloc<U>::type, P0, P1, P2> type;
+ };
+
+ template <template <class, std::size_t, class, class, class, class, class> class Cont //4arg
+ , typename V, std::size_t N, typename A, class P0, class P1, class P2, class P3
+ , class U>
+ struct container_rebind<Cont<V, N, A, P0, P1, P2, P3>, U>
+ {
+ typedef Cont<U, N, typename allocator_traits<A>::template portable_rebind_alloc<U>::type, P0, P1, P2, P3> type;
+ };
+
+ template <template <class, std::size_t, class, class, class, class, class, class> class Cont //5arg
+ , typename V, std::size_t N, typename A, class P0, class P1, class P2, class P3, class P4
+ , class U>
+ struct container_rebind<Cont<V, N, A, P0, P1, P2, P3, P4>, U>
+ {
+ typedef Cont<U, N, typename allocator_traits<A>::template portable_rebind_alloc<U>::type, P0, P1, P2, P3, P4> type;
+ };
+
+ template <template <class, std::size_t, class, class, class, class, class, class, class> class Cont //6arg
+ , typename V, std::size_t N, typename A, class P0, class P1, class P2, class P3, class P4, class P5
+ , class U>
+ struct container_rebind<Cont<V, N, A, P0, P1, P2, P3, P4, P5>, U>
+ {
+ typedef Cont<U, N, typename allocator_traits<A>::template portable_rebind_alloc<U>::type, P0, P1, P2, P3, P4, P5> type;
+ };
+
+ template <template <class, std::size_t, class, class, class, class, class, class, class, class> class Cont //7arg
+ , typename V, std::size_t N, typename A, class P0, class P1, class P2, class P3, class P4, class P5, class P6
+ , class U>
+ struct container_rebind<Cont<V, N, A, P0, P1, P2, P3, P4, P5, P6>, U>
+ {
+ typedef Cont<U, N, typename allocator_traits<A>::template portable_rebind_alloc<U>::type, P0, P1, P2, P3, P4, P5, P6> type;
+ };
+
+ template <template <class, std::size_t, class, class, class, class, class, class, class, class, class> class Cont //8arg
+ , typename V, std::size_t N, typename A, class P0, class P1, class P2, class P3, class P4, class P5, class P6, class P7
+ , class U>
+ struct container_rebind<Cont<V, N, A, P0, P1, P2, P3, P4, P5, P6, P7>, U>
+ {
+ typedef Cont<U, N, typename allocator_traits<A>::template portable_rebind_alloc<U>::type, P0, P1, P2, P3, P4, P5, P6, P7> type;
+ };
+
+ template <template <class, std::size_t, class, class, class, class, class, class, class, class, class, class> class Cont //9arg
+ , typename V, std::size_t N, typename A, class P0, class P1, class P2, class P3, class P4, class P5, class P6, class P7, class P8
+ , class U>
+ struct container_rebind<Cont<V, N, A, P0, P1, P2, P3, P4, P5, P6, P7, P8>, U>
+ {
+ typedef Cont<U, N, typename allocator_traits<A>::template portable_rebind_alloc<U>::type, P0, P1, P2, P3, P4, P5, P6, P7, P8> type;
+ };
+
+#endif //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
+
+} //namespace container_detail {
+} //namespace container {
+} //namespace boost {
+
+#endif //#ifndef BOOST_CONTAINER_DETAIL_CONTAINER_REBIND_HPP
diff --git a/boost/container/detail/copy_move_algo.hpp b/boost/container/detail/copy_move_algo.hpp
index 9044960e79..5293260091 100644
--- a/boost/container/detail/copy_move_algo.hpp
+++ b/boost/container/detail/copy_move_algo.hpp
@@ -69,16 +69,12 @@ struct are_elements_contiguous< ::boost::move_iterator<It> >
// predeclarations
/////////////////////////
-#ifndef BOOST_CONTAINER_VECTOR_ITERATOR_IS_POINTER
-
template<class Pointer>
class vector_iterator;
template<class Pointer>
class vector_const_iterator;
-#endif //BOOST_CONTAINER_VECTOR_ITERATOR_IS_POINTER
-
} //namespace container_detail {
} //namespace container {
@@ -97,8 +93,6 @@ namespace container_detail {
//vector_[const_]iterator
/////////////////////////
-#ifndef BOOST_CONTAINER_VECTOR_ITERATOR_IS_POINTER
-
template<class Pointer>
struct are_elements_contiguous<boost::container::container_detail::vector_iterator<Pointer> >
{
@@ -111,8 +105,6 @@ struct are_elements_contiguous<boost::container::container_detail::vector_const_
static const bool value = true;
};
-#endif //BOOST_CONTAINER_VECTOR_ITERATOR_IS_POINTER
-
/////////////////////////
// offset_ptr
/////////////////////////
@@ -1073,21 +1065,21 @@ inline typename container_detail::enable_if_c
std::memcpy(short_ptr, stora_ptr, sizeof_storage);
large_ptr += sizeof_storage;
short_ptr += sizeof_storage;
- BOOST_CONTAINER_FALLTHOUGH
+ BOOST_FALLTHROUGH;
case 3:
std::memcpy(stora_ptr, large_ptr, sizeof_storage);
std::memcpy(large_ptr, short_ptr, sizeof_storage);
std::memcpy(short_ptr, stora_ptr, sizeof_storage);
large_ptr += sizeof_storage;
short_ptr += sizeof_storage;
- BOOST_CONTAINER_FALLTHOUGH
+ BOOST_FALLTHROUGH;
case 2:
std::memcpy(stora_ptr, large_ptr, sizeof_storage);
std::memcpy(large_ptr, short_ptr, sizeof_storage);
std::memcpy(short_ptr, stora_ptr, sizeof_storage);
large_ptr += sizeof_storage;
short_ptr += sizeof_storage;
- BOOST_CONTAINER_FALLTHOUGH
+ BOOST_FALLTHROUGH;
case 1:
std::memcpy(stora_ptr, large_ptr, sizeof_storage);
std::memcpy(large_ptr, short_ptr, sizeof_storage);
diff --git a/boost/container/detail/destroyers.hpp b/boost/container/detail/destroyers.hpp
index b110561a4a..c3a5d90af3 100644
--- a/boost/container/detail/destroyers.hpp
+++ b/boost/container/detail/destroyers.hpp
@@ -270,12 +270,12 @@ class scoped_destructor
};
-template<class Allocator>
+template<class Allocator, class Value = typename Allocator::value_type>
class value_destructor
{
typedef boost::container::allocator_traits<Allocator> AllocTraits;
public:
- typedef typename Allocator::value_type value_type;
+ typedef Value value_type;
value_destructor(Allocator &a, value_type &rv)
: rv_(rv), a_(a)
{}
diff --git a/boost/container/detail/flat_tree.hpp b/boost/container/detail/flat_tree.hpp
index 9aab87308a..319cad69a7 100644
--- a/boost/container/detail/flat_tree.hpp
+++ b/boost/container/detail/flat_tree.hpp
@@ -37,10 +37,10 @@
#include <boost/container/detail/is_sorted.hpp>
#include <boost/container/detail/type_traits.hpp>
#include <boost/container/detail/iterators.hpp>
+#include <boost/container/detail/mpl.hpp>
+#include <boost/container/detail/is_contiguous_container.hpp>
+#include <boost/container/detail/is_container.hpp>
-#ifdef BOOST_CONTAINER_VECTOR_ITERATOR_IS_POINTER
-#include <boost/intrusive/pointer_traits.hpp>
-#endif
#include <boost/intrusive/detail/minimal_pair_header.hpp> //pair
#include <boost/move/make_unique.hpp>
@@ -52,11 +52,250 @@
#include <boost/move/detail/fwd_macros.hpp>
#endif
+#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
+
+//merge_unique
+#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME merge_unique
+#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEG namespace boost { namespace container { namespace container_detail {
+#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END }}}
+#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MIN 3
+#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MAX 3
+#include <boost/intrusive/detail/has_member_function_callable_with.hpp>
+
+//merge_equal
+#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME merge
+#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEG namespace boost { namespace container { namespace container_detail {
+#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END }}}
+#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MIN 3
+#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MAX 3
+#include <boost/intrusive/detail/has_member_function_callable_with.hpp>
+
+//index_of
+#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME index_of
+#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEG namespace boost { namespace container { namespace container_detail {
+#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END }}}
+#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MIN 1
+#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MAX 1
+#include <boost/intrusive/detail/has_member_function_callable_with.hpp>
+
+//nth
+#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME nth
+#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEG namespace boost { namespace container { namespace container_detail {
+#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END }}}
+#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MIN 1
+#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MAX 1
+#include <boost/intrusive/detail/has_member_function_callable_with.hpp>
+
+//reserve
+#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME reserve
+#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEG namespace boost { namespace container { namespace container_detail {
+#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END }}}
+#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MIN 1
+#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MAX 1
+#include <boost/intrusive/detail/has_member_function_callable_with.hpp>
+
+//capacity
+#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME capacity
+#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEG namespace boost { namespace container { namespace container_detail {
+#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END }}}
+#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MIN 0
+#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MAX 0
+#include <boost/intrusive/detail/has_member_function_callable_with.hpp>
+
+#endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
namespace boost {
namespace container {
namespace container_detail {
+BOOST_INTRUSIVE_INSTANTIATE_DEFAULT_TYPE_TMPLT(stored_allocator_type)
+
+template<class SequenceContainer, class Iterator, class Compare>
+BOOST_CONTAINER_FORCEINLINE void flat_tree_merge_equal
+ (SequenceContainer& dest, Iterator first, Iterator last, Compare comp, container_detail::true_)
+{
+ dest.merge(first, last, comp);
+}
+
+template<class SequenceContainer, class Iterator, class Compare>
+BOOST_CONTAINER_FORCEINLINE void flat_tree_merge_equal_non_merge_member
+ (SequenceContainer& dest, Iterator first, Iterator last, Compare comp, container_detail::true_)
+{
+ typedef typename SequenceContainer::iterator iterator;
+ typedef typename SequenceContainer::value_type value_type;
+
+ iterator const it = dest.insert( dest.end(), first, last );
+ value_type *const braw = boost::movelib::iterator_to_raw_pointer(dest.begin());
+ value_type *const iraw = boost::movelib::iterator_to_raw_pointer(it);
+ value_type *const eraw = boost::movelib::iterator_to_raw_pointer(dest.end());
+ value_type *const sraw = boost::movelib::iterator_to_raw_pointer(dest.begin()+dest.size());
+ boost::movelib::adaptive_sort(iraw, eraw, comp, sraw, dest.capacity());
+ boost::movelib::adaptive_merge(braw, iraw, eraw, comp, sraw, dest.capacity()- dest.size());
+}
+
+template<class SequenceContainer, class Iterator, class Compare>
+BOOST_CONTAINER_FORCEINLINE void flat_tree_merge_equal_non_merge_member
+ (SequenceContainer& dest, Iterator first, Iterator last, Compare comp, container_detail::false_)
+{
+ typedef typename SequenceContainer::iterator iterator;
+
+ iterator const it = dest.insert( dest.end(), first, last );
+ boost::movelib::adaptive_sort(it, dest.end(), comp);
+ boost::movelib::adaptive_merge(dest.begin(), it, dest.end(), comp);
+}
+
+template<class SequenceContainer, class Iterator, class Compare>
+BOOST_CONTAINER_FORCEINLINE void flat_tree_merge_equal
+ (SequenceContainer& dest, Iterator first, Iterator last, Compare comp, container_detail::false_)
+{
+ (flat_tree_merge_equal_non_merge_member)( dest, first, last, comp
+ , container_detail::bool_<is_contiguous_container<SequenceContainer>::value>());
+}
+
+template<class SequenceContainer, class Iterator, class Compare>
+BOOST_CONTAINER_FORCEINLINE void flat_tree_merge_unique
+ (SequenceContainer& dest, Iterator first, Iterator last, Compare comp, container_detail::true_)
+{
+ dest.merge_unique(first, last, comp);
+}
+
+template<class SequenceContainer, class Iterator, class Compare>
+BOOST_CONTAINER_FORCEINLINE void flat_tree_merge_unique
+ (SequenceContainer& dest, Iterator first, Iterator last, Compare comp, container_detail::false_)
+{
+ (flat_tree_merge_equal)(dest, first, last, comp, container_detail::false_());
+ dest.erase(boost::movelib::unique
+ (dest.begin(), dest.end(), boost::movelib::negate<Compare>(comp)), dest.cend());
+}
+
+template<class SequenceContainer, class Iterator>
+BOOST_CONTAINER_FORCEINLINE typename SequenceContainer::size_type
+ flat_tree_index_of
+ (SequenceContainer& cont, Iterator p, container_detail::true_)
+{
+ return cont.index_of(p);
+}
+
+template<class SequenceContainer, class Iterator>
+BOOST_CONTAINER_FORCEINLINE typename SequenceContainer::size_type
+ flat_tree_index_of
+ (SequenceContainer& cont, Iterator p, container_detail::false_)
+{
+ typedef typename SequenceContainer::size_type size_type;
+ return static_cast<size_type>(p - cont.begin());
+}
+
+template<class Iterator, class SequenceContainer>
+BOOST_CONTAINER_FORCEINLINE Iterator
+ flat_tree_nth
+ (SequenceContainer& cont, typename SequenceContainer::size_type n, container_detail::true_)
+{
+ return cont.nth(n);
+}
+
+template<class Iterator, class SequenceContainer>
+BOOST_CONTAINER_FORCEINLINE Iterator
+ flat_tree_nth
+ (SequenceContainer& cont, typename SequenceContainer::size_type n, container_detail::false_)
+{
+ return cont.begin()+ n;
+}
+
+template<class SequenceContainer>
+BOOST_CONTAINER_FORCEINLINE typename SequenceContainer::stored_allocator_type &
+ flat_tree_get_stored_allocator
+ (SequenceContainer& cont, container_detail::true_)
+{
+ return cont.get_stored_allocator();
+}
+
+template<class SequenceContainer>
+BOOST_CONTAINER_FORCEINLINE const typename SequenceContainer::stored_allocator_type &
+ flat_tree_get_stored_allocator
+ (const SequenceContainer& cont, container_detail::true_)
+{
+ return cont.get_stored_allocator();
+}
+
+template<class SequenceContainer>
+BOOST_CONTAINER_FORCEINLINE typename SequenceContainer::allocator_type
+ flat_tree_get_stored_allocator
+ (SequenceContainer& cont, container_detail::false_)
+{
+ return cont.get_allocator();
+}
+
+template<class SequenceContainer, class Compare>
+void flat_tree_adopt_sequence_equal(SequenceContainer &tseq, BOOST_RV_REF(SequenceContainer) seq, Compare comp, container_detail::true_)
+{
+ tseq.clear();
+ boost::movelib::adaptive_sort
+ (boost::movelib::iterator_to_raw_pointer(seq.begin())
+ , boost::movelib::iterator_to_raw_pointer(seq.end())
+ , comp
+ , boost::movelib::iterator_to_raw_pointer(tseq.begin() + tseq.size())
+ , tseq.capacity() - tseq.size());
+ tseq = boost::move(seq);
+}
+
+template<class SequenceContainer, class Compare>
+void flat_tree_adopt_sequence_equal(SequenceContainer &tseq, BOOST_RV_REF(SequenceContainer) seq, Compare comp, container_detail::false_)
+{
+ boost::movelib::adaptive_sort(seq.begin(), seq.end(), comp);
+ tseq = boost::move(seq);
+}
+
+template<class SequenceContainer, class Compare>
+void flat_tree_adopt_sequence_unique(SequenceContainer &tseq, BOOST_RV_REF(SequenceContainer) seq, Compare comp, container_detail::true_)
+{
+ boost::movelib::adaptive_sort
+ ( boost::movelib::iterator_to_raw_pointer(seq.begin())
+ , boost::movelib::iterator_to_raw_pointer(seq.end())
+ , comp
+ , boost::movelib::iterator_to_raw_pointer(tseq.begin() + tseq.size())
+ , tseq.capacity() - tseq.size());
+ seq.erase(boost::movelib::unique
+ ( seq.begin(), seq.end(), boost::movelib::negate<Compare>(comp))
+ , seq.cend());
+ tseq = boost::move(seq);
+}
+
+template<class SequenceContainer, class Compare>
+void flat_tree_adopt_sequence_unique(SequenceContainer &tseq, BOOST_RV_REF(SequenceContainer) seq, Compare comp, container_detail::false_)
+{
+ boost::movelib::adaptive_sort(seq.begin(), seq.end(), comp);
+ seq.erase(boost::movelib::unique
+ (seq.begin(), seq.end(), boost::movelib::negate<Compare>(comp)), seq.cend());
+ tseq = boost::move(seq);
+}
+
+template<class SequenceContainer>
+BOOST_CONTAINER_FORCEINLINE void
+ flat_tree_reserve(SequenceContainer &tseq, typename SequenceContainer::size_type cap, container_detail::true_)
+{
+ tseq.reserve(cap);
+}
+
+template<class SequenceContainer>
+BOOST_CONTAINER_FORCEINLINE void
+ flat_tree_reserve(SequenceContainer &, typename SequenceContainer::size_type, container_detail::false_)
+{
+}
+
+template<class SequenceContainer>
+BOOST_CONTAINER_FORCEINLINE typename SequenceContainer::size_type
+ flat_tree_capacity(const SequenceContainer &tseq, container_detail::true_)
+{
+ return tseq.capacity();
+}
+
+template<class SequenceContainer>
+BOOST_CONTAINER_FORCEINLINE typename SequenceContainer::size_type
+ flat_tree_capacity(const SequenceContainer &tseq, container_detail::false_)
+{
+ return tseq.size();
+}
+
template<class Compare, class Value, class KeyOfValue>
class flat_tree_value_compare
: private Compare
@@ -85,42 +324,49 @@ class flat_tree_value_compare
Compare &get_comp()
{ return *this; }
};
-
+/*
template<class Pointer>
struct get_flat_tree_iterators
{
- #ifdef BOOST_CONTAINER_VECTOR_ITERATOR_IS_POINTER
- typedef Pointer iterator;
- typedef typename boost::intrusive::
- 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;
- #else //BOOST_CONTAINER_VECTOR_ITERATOR_IS_POINTER
typedef typename boost::container::container_detail::
vec_iterator<Pointer, false> iterator;
typedef typename boost::container::container_detail::
vec_iterator<Pointer, true > const_iterator;
- #endif //BOOST_CONTAINER_VECTOR_ITERATOR_IS_POINTER
typedef boost::container::reverse_iterator<iterator> reverse_iterator;
typedef boost::container::reverse_iterator<const_iterator> const_reverse_iterator;
};
+*/
+
+template < class Value, class AllocatorOrContainer
+ , bool = boost::container::container_detail::is_container<AllocatorOrContainer>::value >
+struct select_container_type
+{
+ typedef AllocatorOrContainer type;
+};
+
+template <class Value, class AllocatorOrContainer>
+struct select_container_type<Value, AllocatorOrContainer, false>
+{
+ typedef boost::container::vector<Value, AllocatorOrContainer> type;
+};
template <class Value, class KeyOfValue,
- class Compare, class Allocator>
+ class Compare, class AllocatorOrContainer>
class flat_tree
{
public:
- typedef boost::container::vector<Value, Allocator> sequence_type;
+ typedef typename select_container_type<Value, AllocatorOrContainer>::type container_type;
+ typedef container_type sequence_type; //For backwards compatibility
private:
- typedef Allocator allocator_t;
- typedef allocator_traits<Allocator> allocator_traits_type;
+ typedef typename container_type::allocator_type allocator_t;
+ typedef allocator_traits<allocator_t> allocator_traits_type;
public:
typedef flat_tree_value_compare<Compare, Value, KeyOfValue> value_compare;
private:
+
struct Data
//Inherit from value_compare to do EBO
: public value_compare
@@ -152,11 +398,11 @@ class flat_tree
: value_compare(boost::move(static_cast<value_compare&>(d))), m_seq(boost::move(d.m_seq))
{}
- Data(const Data &d, const Allocator &a)
+ Data(const Data &d, const allocator_t &a)
: value_compare(static_cast<const value_compare&>(d)), m_seq(d.m_seq, a)
{}
- Data(BOOST_RV_REF(Data) d, const Allocator &a)
+ Data(BOOST_RV_REF(Data) d, const allocator_t &a)
: value_compare(boost::move(static_cast<value_compare&>(d))), m_seq(boost::move(d.m_seq), a)
{}
@@ -181,7 +427,7 @@ class flat_tree
this->m_seq.swap(d.m_seq);
}
- sequence_type m_seq;
+ container_type m_seq;
};
Data m_data;
@@ -189,28 +435,39 @@ class flat_tree
public:
- typedef typename sequence_type::value_type value_type;
- typedef typename sequence_type::pointer pointer;
- typedef typename sequence_type::const_pointer const_pointer;
- typedef typename sequence_type::reference reference;
- typedef typename sequence_type::const_reference const_reference;
+ typedef typename container_type::value_type value_type;
+ typedef typename container_type::pointer pointer;
+ typedef typename container_type::const_pointer const_pointer;
+ typedef typename container_type::reference reference;
+ typedef typename container_type::const_reference const_reference;
typedef typename KeyOfValue::type key_type;
typedef Compare key_compare;
- typedef typename sequence_type::allocator_type allocator_type;
- typedef typename sequence_type::size_type size_type;
- typedef typename sequence_type::difference_type difference_type;
- typedef typename sequence_type::iterator iterator;
- typedef typename sequence_type::const_iterator const_iterator;
- typedef typename sequence_type::reverse_iterator reverse_iterator;
- typedef typename sequence_type::const_reverse_iterator const_reverse_iterator;
+ typedef typename container_type::allocator_type allocator_type;
+ typedef typename container_type::size_type size_type;
+ typedef typename container_type::difference_type difference_type;
+ typedef typename container_type::iterator iterator;
+ typedef typename container_type::const_iterator const_iterator;
+ typedef typename container_type::reverse_iterator reverse_iterator;
+ typedef typename container_type::const_reverse_iterator const_reverse_iterator;
//!Standard extension
- typedef allocator_type stored_allocator_type;
+ typedef BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_DEFAULT
+ (boost::container::container_detail::, container_type
+ ,stored_allocator_type, allocator_type) stored_allocator_type;
+
+ static const bool has_stored_allocator_type =
+ BOOST_INTRUSIVE_HAS_TYPE(boost::container::container_detail::, container_type, stored_allocator_type);
private:
typedef allocator_traits<stored_allocator_type> stored_allocator_traits;
public:
+ typedef typename container_detail::if_c
+ <has_stored_allocator_type, const stored_allocator_type &, allocator_type>::type get_stored_allocator_const_return_t;
+
+ typedef typename container_detail::if_c
+ <has_stored_allocator_type, stored_allocator_type &, allocator_type>::type get_stored_allocator_noconst_return_t;
+
BOOST_CONTAINER_FORCEINLINE flat_tree()
: m_data()
{ }
@@ -357,6 +614,11 @@ class flat_tree
BOOST_CONTAINER_FORCEINLINE key_compare &priv_key_comp()
{ return this->priv_value_comp().get_comp(); }
+ struct insert_commit_data
+ {
+ const_iterator position;
+ };
+
public:
// accessors:
BOOST_CONTAINER_FORCEINLINE Compare key_comp() const
@@ -368,11 +630,15 @@ class flat_tree
BOOST_CONTAINER_FORCEINLINE allocator_type get_allocator() const
{ return this->m_data.m_seq.get_allocator(); }
- BOOST_CONTAINER_FORCEINLINE const stored_allocator_type &get_stored_allocator() const
- { return this->m_data.m_seq.get_stored_allocator(); }
+ BOOST_CONTAINER_FORCEINLINE get_stored_allocator_const_return_t get_stored_allocator() const
+ {
+ return flat_tree_get_stored_allocator(this->m_data.m_seq, container_detail::bool_<has_stored_allocator_type>());
+ }
- BOOST_CONTAINER_FORCEINLINE stored_allocator_type &get_stored_allocator()
- { return this->m_data.m_seq.get_stored_allocator(); }
+ BOOST_CONTAINER_FORCEINLINE get_stored_allocator_noconst_return_t get_stored_allocator()
+ {
+ return flat_tree_get_stored_allocator(this->m_data.m_seq, container_detail::bool_<has_stored_allocator_type>());
+ }
BOOST_CONTAINER_FORCEINLINE iterator begin()
{ return this->m_data.m_seq.begin(); }
@@ -432,7 +698,8 @@ class flat_tree
insert_commit_data 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));
+ : this->begin() + (data.position - this->cbegin());
+ //: iterator(vector_iterator_get_ptr(data.position));
return ret;
}
@@ -442,7 +709,8 @@ class flat_tree
insert_commit_data 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));
+ : this->begin() + (data.position - this->cbegin());
+ //: iterator(vector_iterator_get_ptr(data.position));
return ret;
}
@@ -466,7 +734,8 @@ class flat_tree
insert_commit_data data;
return this->priv_insert_unique_prepare(hint, KeyOfValue()(val), data)
? this->priv_insert_commit(data, val)
- : iterator(vector_iterator_get_ptr(data.position));
+ : this->begin() + (data.position - this->cbegin());
+ //: iterator(vector_iterator_get_ptr(data.position));
}
iterator insert_unique(const_iterator hint, BOOST_RV_REF(value_type) val)
@@ -475,7 +744,8 @@ class flat_tree
insert_commit_data 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));
+ : this->begin() + (data.position - this->cbegin());
+ //: iterator(vector_iterator_get_ptr(data.position));
}
iterator insert_equal(const_iterator hint, const value_type& val)
@@ -563,7 +833,11 @@ class flat_tree
>::type * = 0
#endif
)
- { this->m_data.m_seq.merge(first, last, static_cast<const value_compare &>(this->m_data)); }
+ {
+ const bool value = boost::container::container_detail::
+ has_member_function_callable_with_merge_unique<container_type, iterator, iterator, value_compare>::value;
+ (flat_tree_merge_equal)(this->m_data.m_seq, first, last, this->priv_value_comp(), container_detail::bool_<value>());
+ }
template <class InIt>
void insert_unique(ordered_unique_range_t, InIt first, InIt last
@@ -592,7 +866,11 @@ class flat_tree
>::type * = 0
#endif
)
- { this->m_data.m_seq.merge_unique(first, last, static_cast<const value_compare &>(this->m_data)); }
+ {
+ const bool value = boost::container::container_detail::
+ has_member_function_callable_with_merge_unique<container_type, iterator, iterator, value_compare>::value;
+ (flat_tree_merge_unique)(this->m_data.m_seq, first, last, this->priv_value_comp(), container_detail::bool_<value>());
+ }
#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
@@ -601,9 +879,9 @@ class flat_tree
{
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();
+ get_stored_allocator_noconst_return_t a = this->get_stored_allocator();
stored_allocator_traits::construct(a, &val, ::boost::forward<Args>(args)... );
- value_destructor<stored_allocator_type> d(a, val);
+ value_destructor<stored_allocator_type, value_type> d(a, val);
return this->insert_unique(::boost::move(val));
}
@@ -613,9 +891,9 @@ class flat_tree
//hint checked in insert_unique
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();
+ get_stored_allocator_noconst_return_t a = this->get_stored_allocator();
stored_allocator_traits::construct(a, &val, ::boost::forward<Args>(args)... );
- value_destructor<stored_allocator_type> d(a, val);
+ value_destructor<stored_allocator_type, value_type> d(a, val);
return this->insert_unique(hint, ::boost::move(val));
}
@@ -624,9 +902,9 @@ class flat_tree
{
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();
+ get_stored_allocator_noconst_return_t a = this->get_stored_allocator();
stored_allocator_traits::construct(a, &val, ::boost::forward<Args>(args)... );
- value_destructor<stored_allocator_type> d(a, val);
+ value_destructor<stored_allocator_type, value_type> d(a, val);
return this->insert_equal(::boost::move(val));
}
@@ -636,9 +914,9 @@ class flat_tree
//hint checked in insert_equal
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();
+ get_stored_allocator_noconst_return_t a = this->get_stored_allocator();
stored_allocator_traits::construct(a, &val, ::boost::forward<Args>(args)... );
- value_destructor<stored_allocator_type> d(a, val);
+ value_destructor<stored_allocator_type, value_type> d(a, val);
return this->insert_equal(hint, ::boost::move(val));
}
@@ -673,9 +951,9 @@ class flat_tree
{\
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();\
+ get_stored_allocator_noconst_return_t 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);\
+ value_destructor<stored_allocator_type, value_type> d(a, val);\
return this->insert_unique(::boost::move(val));\
}\
\
@@ -684,9 +962,9 @@ class flat_tree
{\
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();\
+ get_stored_allocator_noconst_return_t 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);\
+ value_destructor<stored_allocator_type, value_type> d(a, val);\
return this->insert_unique(hint, ::boost::move(val));\
}\
\
@@ -695,9 +973,9 @@ class flat_tree
{\
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();\
+ get_stored_allocator_noconst_return_t 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);\
+ value_destructor<stored_allocator_type, value_type> d(a, val);\
return this->insert_equal(::boost::move(val));\
}\
\
@@ -706,9 +984,9 @@ class flat_tree
{\
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();\
+ get_stored_allocator_noconst_return_t 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);\
+ value_destructor<stored_allocator_type, value_type> d(a, val);\
return this->insert_equal(hint, ::boost::move(val));\
}\
template <class KeyType BOOST_MOVE_I##N BOOST_MOVE_CLASS##N>\
@@ -790,16 +1068,32 @@ class flat_tree
{ this->m_data.m_seq.shrink_to_fit(); }
BOOST_CONTAINER_FORCEINLINE iterator nth(size_type n) BOOST_NOEXCEPT_OR_NOTHROW
- { return this->m_data.m_seq.nth(n); }
+ {
+ const bool value = boost::container::container_detail::
+ has_member_function_callable_with_nth<container_type, size_type>::value;
+ return flat_tree_nth<iterator>(this->m_data.m_seq, n, container_detail::bool_<value>());
+ }
BOOST_CONTAINER_FORCEINLINE const_iterator nth(size_type n) const BOOST_NOEXCEPT_OR_NOTHROW
- { return this->m_data.m_seq.nth(n); }
+ {
+ const bool value = boost::container::container_detail::
+ has_member_function_callable_with_nth<container_type, size_type>::value;
+ return flat_tree_nth<const_iterator>(this->m_data.m_seq, n, container_detail::bool_<value>());
+ }
BOOST_CONTAINER_FORCEINLINE size_type index_of(iterator p) BOOST_NOEXCEPT_OR_NOTHROW
- { return this->m_data.m_seq.index_of(p); }
+ {
+ const bool value = boost::container::container_detail::
+ has_member_function_callable_with_index_of<container_type, iterator>::value;
+ return flat_tree_index_of(this->m_data.m_seq, p, container_detail::bool_<value>());
+ }
BOOST_CONTAINER_FORCEINLINE size_type index_of(const_iterator p) const BOOST_NOEXCEPT_OR_NOTHROW
- { return this->m_data.m_seq.index_of(p); }
+ {
+ const bool value = boost::container::container_detail::
+ has_member_function_callable_with_index_of<container_type, const_iterator>::value;
+ return flat_tree_index_of(this->m_data.m_seq, p, container_detail::bool_<value>());
+ }
// set operations:
iterator find(const key_type& k)
@@ -832,33 +1126,41 @@ class flat_tree
}
template<class C2>
- void merge_unique(flat_tree<Value, KeyOfValue, C2, Allocator>& source)
+ BOOST_CONTAINER_FORCEINLINE void merge_unique(flat_tree<Value, KeyOfValue, C2, AllocatorOrContainer>& 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)
+ BOOST_CONTAINER_FORCEINLINE void merge_equal(flat_tree<Value, KeyOfValue, C2, AllocatorOrContainer>& source)
{
this->insert( boost::make_move_iterator(source.begin())
, boost::make_move_iterator(source.end()));
}
- void merge_unique(flat_tree& source)
+ BOOST_CONTAINER_FORCEINLINE void merge_unique(flat_tree& source)
{
- this->m_data.m_seq.merge_unique
- ( boost::make_move_iterator(source.begin())
- , boost::make_move_iterator(source.end())
- , static_cast<const value_compare &>(this->m_data));
+ const bool value = boost::container::container_detail::
+ has_member_function_callable_with_merge_unique<container_type, iterator, iterator, value_compare>::value;
+ (flat_tree_merge_unique)
+ ( this->m_data.m_seq
+ , boost::make_move_iterator(source.m_data.m_seq.begin())
+ , boost::make_move_iterator(source.m_data.m_seq.end())
+ , this->priv_value_comp()
+ , container_detail::bool_<value>());
}
- void merge_equal(flat_tree& source)
+ BOOST_CONTAINER_FORCEINLINE void merge_equal(flat_tree& source)
{
- this->m_data.m_seq.merge
- ( boost::make_move_iterator(source.begin())
- , boost::make_move_iterator(source.end())
- , static_cast<const value_compare &>(this->m_data));
+ const bool value = boost::container::container_detail::
+ has_member_function_callable_with_merge<container_type, iterator, iterator, value_compare>::value;
+ (flat_tree_merge_equal)
+ ( this->m_data.m_seq
+ , boost::make_move_iterator(source.m_data.m_seq.begin())
+ , boost::make_move_iterator(source.m_data.m_seq.end())
+ , this->priv_value_comp()
+ , container_detail::bool_<value>());
}
BOOST_CONTAINER_FORCEINLINE iterator lower_bound(const key_type& k)
@@ -886,60 +1188,51 @@ class flat_tree
{ return this->priv_lower_bound_range(this->cbegin(), this->cend(), k); }
BOOST_CONTAINER_FORCEINLINE size_type capacity() const
- { return this->m_data.m_seq.capacity(); }
+ {
+ const bool value = boost::container::container_detail::
+ has_member_function_callable_with_capacity<container_type>::value;
+ return (flat_tree_capacity)(this->m_data.m_seq, container_detail::bool_<value>());
+ }
BOOST_CONTAINER_FORCEINLINE void reserve(size_type cnt)
- { this->m_data.m_seq.reserve(cnt); }
+ {
+ const bool value = boost::container::container_detail::
+ has_member_function_callable_with_reserve<container_type, size_type>::value;
+ (flat_tree_reserve)(this->m_data.m_seq, cnt, container_detail::bool_<value>());
+ }
- BOOST_CONTAINER_FORCEINLINE sequence_type extract_sequence()
+ BOOST_CONTAINER_FORCEINLINE container_type extract_sequence()
{
return boost::move(m_data.m_seq);
}
- BOOST_CONTAINER_FORCEINLINE sequence_type &get_sequence_ref()
+ BOOST_CONTAINER_FORCEINLINE container_type &get_sequence_ref()
{
return m_data.m_seq;
}
- void adopt_sequence_equal(BOOST_RV_REF(sequence_type) seq)
+ BOOST_CONTAINER_FORCEINLINE void adopt_sequence_equal(BOOST_RV_REF(container_type) seq)
{
- sequence_type &tseq = m_data.m_seq;
- boost::movelib::adaptive_sort
- ( boost::movelib::iterator_to_raw_pointer(seq.begin())
- , boost::movelib::iterator_to_raw_pointer(seq.end())
- , this->priv_value_comp()
- , boost::movelib::iterator_to_raw_pointer(tseq.begin() + tseq.size())
- , tseq.capacity() - tseq.size());
- tseq = boost::move(seq);
+ (flat_tree_adopt_sequence_equal)( m_data.m_seq, boost::move(seq), this->priv_value_comp()
+ , container_detail::bool_<is_contiguous_container<container_type>::value>());
}
- void adopt_sequence_equal(ordered_range_t, BOOST_RV_REF(sequence_type) seq)
+ BOOST_CONTAINER_FORCEINLINE void adopt_sequence_unique(BOOST_RV_REF(container_type) seq)
{
- BOOST_ASSERT((is_sorted)(seq.cbegin(), seq.cend(), this->priv_value_comp()));
- sequence_type &tseq = m_data.m_seq;
- tseq = boost::move(seq);
+ (flat_tree_adopt_sequence_unique)(m_data.m_seq, boost::move(seq), this->priv_value_comp()
+ , container_detail::bool_<is_contiguous_container<container_type>::value>());
}
- void adopt_sequence_unique(BOOST_RV_REF(sequence_type) seq)
+ void adopt_sequence_equal(ordered_range_t, BOOST_RV_REF(container_type) seq)
{
- sequence_type &tseq = m_data.m_seq;
- boost::movelib::adaptive_sort
- ( boost::movelib::iterator_to_raw_pointer(seq.begin())
- , boost::movelib::iterator_to_raw_pointer(seq.end())
- , this->priv_value_comp()
- , boost::movelib::iterator_to_raw_pointer(tseq.begin() + tseq.size())
- , tseq.capacity() - tseq.size());
- seq.erase( boost::movelib::unique
- (seq.begin(), seq.end(), boost::movelib::negate<value_compare>(this->m_data.get_comp()))
- , seq.cend());
- tseq = boost::move(seq);
+ BOOST_ASSERT((is_sorted)(seq.cbegin(), seq.cend(), this->priv_value_comp()));
+ m_data.m_seq = boost::move(seq);
}
- void adopt_sequence_unique(ordered_unique_range_t, BOOST_RV_REF(sequence_type) seq)
+ void adopt_sequence_unique(ordered_unique_range_t, BOOST_RV_REF(container_type) seq)
{
BOOST_ASSERT((is_sorted_and_unique)(seq.cbegin(), seq.cend(), this->priv_value_comp()));
- sequence_type &tseq = m_data.m_seq;
- tseq = boost::move(seq);
+ m_data.m_seq = boost::move(seq);
}
BOOST_CONTAINER_FORCEINLINE friend bool operator==(const flat_tree& x, const flat_tree& y)
@@ -993,11 +1286,6 @@ class flat_tree
return (this->begin() <= pos) && (pos <= this->end());
}
- struct insert_commit_data
- {
- const_iterator position;
- };
-
// insert/erase
void priv_insert_equal_prepare
(const_iterator pos, const value_type& val, insert_commit_data &data)
@@ -1216,11 +1504,13 @@ class flat_tree
//!has_trivial_destructor_after_move<> == true_type
//!specialization for optimizations
template <class T, class KeyOfValue,
-class Compare, class Allocator>
-struct has_trivial_destructor_after_move<boost::container::container_detail::flat_tree<T, KeyOfValue, Compare, Allocator> >
+class Compare, class AllocatorOrContainer>
+struct has_trivial_destructor_after_move<boost::container::container_detail::flat_tree<T, KeyOfValue, Compare, AllocatorOrContainer> >
{
- typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer;
- static const bool value = ::boost::has_trivial_destructor_after_move<Allocator>::value &&
+ typedef typename boost::container::container_detail::select_container_type<T, AllocatorOrContainer>::type container_type;
+ typedef typename container_type::allocator_type allocator_t;
+ typedef typename ::boost::container::allocator_traits<allocator_t>::pointer pointer;
+ static const bool value = ::boost::has_trivial_destructor_after_move<allocator_t>::value &&
::boost::has_trivial_destructor_after_move<pointer>::value;
};
diff --git a/boost/container/detail/is_container.hpp b/boost/container/detail/is_container.hpp
new file mode 100644
index 0000000000..6052f045e0
--- /dev/null
+++ b/boost/container/detail/is_container.hpp
@@ -0,0 +1,55 @@
+//////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2017-2017. 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_CONTAINER_HPP
+#define BOOST_CONTAINER_DETAIL_IS_CONTAINER_HPP
+
+#ifndef BOOST_CONFIG_HPP
+# include <boost/config.hpp>
+#endif
+
+#if defined(BOOST_HAS_PRAGMA_ONCE)
+# pragma once
+#endif
+
+//empty
+#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME empty
+#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEG namespace boost { namespace container { namespace is_container_detail {
+#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END }}}
+#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MIN 0
+#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MAX 0
+#include <boost/intrusive/detail/has_member_function_callable_with.hpp>
+
+//size
+#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME size
+#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEG namespace boost { namespace container { namespace is_container_detail {
+#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END }}}
+#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MIN 0
+#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MAX 0
+#include <boost/intrusive/detail/has_member_function_callable_with.hpp>
+
+namespace boost {
+namespace container {
+namespace container_detail {
+
+template <class Container>
+struct is_container
+{
+ static const bool value =
+ boost::container::is_container_detail::
+ has_member_function_callable_with_size <const Container>::value &&
+ boost::container::is_container_detail::
+ has_member_function_callable_with_empty<const Container>::value;
+};
+
+} //namespace container_detail {
+} //namespace container {
+} //namespace boost {
+
+#endif //#ifndef BOOST_CONTAINER_DETAIL_IS_CONTAINER_HPP
diff --git a/boost/container/detail/is_contiguous_container.hpp b/boost/container/detail/is_contiguous_container.hpp
new file mode 100644
index 0000000000..af98c7f18b
--- /dev/null
+++ b/boost/container/detail/is_contiguous_container.hpp
@@ -0,0 +1,47 @@
+//////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2017-2017. 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_CONTIGUOUS_CONTAINER_HPP
+#define BOOST_CONTAINER_DETAIL_IS_CONTIGUOUS_CONTAINER_HPP
+
+#ifndef BOOST_CONFIG_HPP
+# include <boost/config.hpp>
+#endif
+
+#if defined(BOOST_HAS_PRAGMA_ONCE)
+# pragma once
+#endif
+
+//data
+#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME data
+#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEG namespace boost { namespace container { namespace is_contiguous_container_detail {
+#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END }}}
+#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MIN 0
+#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MAX 0
+#include <boost/intrusive/detail/has_member_function_callable_with.hpp>
+
+namespace boost {
+namespace container {
+namespace container_detail {
+
+template <class Container>
+struct is_contiguous_container
+{
+ static const bool value =
+ boost::container::is_contiguous_container_detail::
+ has_member_function_callable_with_data<Container>::value &&
+ boost::container::is_contiguous_container_detail::
+ has_member_function_callable_with_data<const Container>::value;
+};
+
+} //namespace container_detail {
+} //namespace container {
+} //namespace boost {
+
+#endif //#ifndef BOOST_CONTAINER_DETAIL_IS_CONTIGUOUS_CONTAINER_HPP
diff --git a/boost/container/detail/workaround.hpp b/boost/container/detail/workaround.hpp
index 816d3cc84d..736326b779 100644
--- a/boost/container/detail/workaround.hpp
+++ b/boost/container/detail/workaround.hpp
@@ -43,12 +43,6 @@
# endif
#endif
-#if !defined(BOOST_FALLTHOUGH)
- #define BOOST_CONTAINER_FALLTHOUGH
-#else
- #define BOOST_CONTAINER_FALLTHOUGH BOOST_FALLTHOUGH;
-#endif
-
#if defined(BOOST_MSVC) && (_MSC_VER < 1400)
#define BOOST_CONTAINER_TEMPLATED_CONVERSION_OPERATOR_BROKEN
#endif