summaryrefslogtreecommitdiff
path: root/boost/container/detail/flat_tree.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'boost/container/detail/flat_tree.hpp')
-rw-r--r--boost/container/detail/flat_tree.hpp510
1 files changed, 264 insertions, 246 deletions
diff --git a/boost/container/detail/flat_tree.hpp b/boost/container/detail/flat_tree.hpp
index 319cad69a7..5f212e3fc8 100644
--- a/boost/container/detail/flat_tree.hpp
+++ b/boost/container/detail/flat_tree.hpp
@@ -47,6 +47,7 @@
#include <boost/move/iterator.hpp>
#include <boost/move/adl_move_swap.hpp>
#include <boost/move/algo/adaptive_sort.hpp>
+#include <boost/move/algo/detail/pdqsort.hpp>
#if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
#include <boost/move/detail/fwd_macros.hpp>
@@ -56,7 +57,7 @@
//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_BEG namespace boost { namespace container { namespace dtl {
#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
@@ -64,7 +65,7 @@
//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_BEG namespace boost { namespace container { namespace dtl {
#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
@@ -72,7 +73,7 @@
//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_BEG namespace boost { namespace container { namespace dtl {
#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
@@ -80,7 +81,7 @@
//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_BEG namespace boost { namespace container { namespace dtl {
#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
@@ -88,7 +89,7 @@
//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_BEG namespace boost { namespace container { namespace dtl {
#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
@@ -96,7 +97,7 @@
//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_BEG namespace boost { namespace container { namespace dtl {
#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
@@ -106,196 +107,297 @@
namespace boost {
namespace container {
-namespace container_detail {
+namespace dtl {
+
+///////////////////////////////////////
+//
+// Helper functions to merge elements
+//
+///////////////////////////////////////
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_)
+///////////////////////////////////////
+//
+// flat_tree_container_inplace_merge
+//
+///////////////////////////////////////
+template<class SequenceContainer, class Compare>
+void flat_tree_container_inplace_merge //is_contiguous_container == true
+ (SequenceContainer& dest, typename SequenceContainer::iterator it, Compare comp , dtl::true_)
{
- dest.merge(first, last, comp);
+ typedef typename SequenceContainer::value_type value_type;
+ 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());
+ boost::movelib::adaptive_merge(braw, iraw, eraw, comp, eraw, 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::true_)
+template<class SequenceContainer, class Compare>
+void flat_tree_container_inplace_merge //is_contiguous_container == false
+ (SequenceContainer& dest, typename SequenceContainer::iterator it, Compare comp, dtl::false_)
{
- typedef typename SequenceContainer::iterator iterator;
- typedef typename SequenceContainer::value_type value_type;
+ boost::movelib::adaptive_merge(dest.begin(), it, dest.end(), comp);
+}
- iterator const it = dest.insert( dest.end(), first, last );
- value_type *const braw = boost::movelib::iterator_to_raw_pointer(dest.begin());
+///////////////////////////////////////
+//
+// flat_tree_container_inplace_sort_ending
+//
+///////////////////////////////////////
+template<class SequenceContainer, class Compare>
+void flat_tree_container_inplace_sort_ending //is_contiguous_container == true
+ (SequenceContainer& dest, typename SequenceContainer::iterator it, Compare comp, dtl::true_)
+{
+ typedef typename SequenceContainer::value_type value_type;
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());
+ boost::movelib::adaptive_sort(iraw, eraw, comp, eraw, 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_)
+template<class SequenceContainer, class Compare>
+void flat_tree_container_inplace_sort_ending //is_contiguous_container == false
+ (SequenceContainer& dest, typename SequenceContainer::iterator it, Compare comp , dtl::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);
}
+///////////////////////////////////////
+//
+// flat_tree_merge
+//
+///////////////////////////////////////
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_)
+ (SequenceContainer& dest, Iterator first, Iterator last, Compare comp, dtl::true_)
{
- (flat_tree_merge_equal_non_merge_member)( dest, first, last, comp
- , container_detail::bool_<is_contiguous_container<SequenceContainer>::value>());
+ dest.merge(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::true_)
+BOOST_CONTAINER_FORCEINLINE void flat_tree_merge_equal //has_merge_unique == false
+ (SequenceContainer& dest, Iterator first, Iterator last, Compare comp, dtl::false_)
+{
+ typedef typename SequenceContainer::iterator iterator;
+ iterator const it = dest.insert( dest.end(), first, last );
+ dtl::bool_<is_contiguous_container<SequenceContainer>::value> contiguous_tag;
+ (flat_tree_container_inplace_merge)(dest, it, comp, contiguous_tag);
+}
+
+///////////////////////////////////////
+//
+// flat_tree_merge_unique
+//
+///////////////////////////////////////
+template<class SequenceContainer, class Iterator, class Compare>
+BOOST_CONTAINER_FORCEINLINE void flat_tree_merge_unique //has_merge_unique == true
+ (SequenceContainer& dest, Iterator first, Iterator last, Compare comp, dtl::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_)
+BOOST_CONTAINER_FORCEINLINE void flat_tree_merge_unique //has_merge_unique == false
+ (SequenceContainer& dest, Iterator first, Iterator last, Compare comp, dtl::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());
+ typedef typename SequenceContainer::iterator iterator;
+ typedef typename SequenceContainer::size_type size_type;
+
+ size_type const old_sz = dest.size();
+ iterator const first_new = dest.insert(dest.cend(), first, last );
+ iterator e = boost::movelib::inplace_set_difference(first_new, dest.end(), dest.begin(), first_new, comp);
+ dest.erase(e, dest.end());
+ dtl::bool_<is_contiguous_container<SequenceContainer>::value> contiguous_tag;
+ (flat_tree_container_inplace_merge)(dest, dest.begin()+old_sz, comp, contiguous_tag);
}
+///////////////////////////////////////
+//
+// flat_tree_index_of
+//
+///////////////////////////////////////
template<class SequenceContainer, class Iterator>
BOOST_CONTAINER_FORCEINLINE typename SequenceContainer::size_type
- flat_tree_index_of
- (SequenceContainer& cont, Iterator p, container_detail::true_)
+ flat_tree_index_of // has_index_of == true
+ (SequenceContainer& cont, Iterator p, dtl::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_)
+ flat_tree_index_of // has_index_of == false
+ (SequenceContainer& cont, Iterator p, dtl::false_)
{
typedef typename SequenceContainer::size_type size_type;
return static_cast<size_type>(p - cont.begin());
}
+///////////////////////////////////////
+//
+// flat_tree_nth
+//
+///////////////////////////////////////
template<class Iterator, class SequenceContainer>
BOOST_CONTAINER_FORCEINLINE Iterator
- flat_tree_nth
- (SequenceContainer& cont, typename SequenceContainer::size_type n, container_detail::true_)
+ flat_tree_nth // has_nth == true
+ (SequenceContainer& cont, typename SequenceContainer::size_type n, dtl::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_)
+ flat_tree_nth // has_nth == false
+ (SequenceContainer& cont, typename SequenceContainer::size_type n, dtl::false_)
{
return cont.begin()+ n;
}
+///////////////////////////////////////
+//
+// flat_tree_get_stored_allocator
+//
+///////////////////////////////////////
template<class SequenceContainer>
BOOST_CONTAINER_FORCEINLINE typename SequenceContainer::stored_allocator_type &
- flat_tree_get_stored_allocator
- (SequenceContainer& cont, container_detail::true_)
+ flat_tree_get_stored_allocator // has_get_stored_allocator == true
+ (SequenceContainer& cont, dtl::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_)
+ flat_tree_get_stored_allocator // has_get_stored_allocator == true
+ (const SequenceContainer& cont, dtl::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_)
+ flat_tree_get_stored_allocator // has_get_stored_allocator == false
+ (SequenceContainer& cont, dtl::false_)
{
return cont.get_allocator();
}
+///////////////////////////////////////
+//
+// flat_tree_adopt_sequence_equal
+//
+///////////////////////////////////////
template<class SequenceContainer, class Compare>
-void flat_tree_adopt_sequence_equal(SequenceContainer &tseq, BOOST_RV_REF(SequenceContainer) seq, Compare comp, container_detail::true_)
+void flat_tree_sort_contiguous_to_adopt // is_contiguous_container == true
+ (SequenceContainer &tseq, BOOST_RV_REF(SequenceContainer) seq, Compare comp)
{
- 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());
+ if(tseq.capacity() >= (seq.capacity() - seq.size())) {
+ 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.capacity());
+ }
+ else{
+ 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(seq.end())
+ , seq.capacity() - seq.size());
+ }
+}
+
+template<class SequenceContainer, class Compare>
+void flat_tree_adopt_sequence_equal // is_contiguous_container == true
+ (SequenceContainer &tseq, BOOST_RV_REF(SequenceContainer) seq, Compare comp, dtl::true_)
+{
+ flat_tree_sort_contiguous_to_adopt(tseq, boost::move(seq), comp);
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_)
+void flat_tree_adopt_sequence_equal // is_contiguous_container == false
+ (SequenceContainer &tseq, BOOST_RV_REF(SequenceContainer) seq, Compare comp, dtl::false_)
{
boost::movelib::adaptive_sort(seq.begin(), seq.end(), comp);
tseq = boost::move(seq);
}
+///////////////////////////////////////
+//
+// flat_tree_adopt_sequence_unique
+//
+///////////////////////////////////////
template<class SequenceContainer, class Compare>
-void flat_tree_adopt_sequence_unique(SequenceContainer &tseq, BOOST_RV_REF(SequenceContainer) seq, Compare comp, container_detail::true_)
+void flat_tree_adopt_sequence_unique// is_contiguous_container == true
+ (SequenceContainer &tseq, BOOST_RV_REF(SequenceContainer) seq, Compare comp, dtl::true_)
{
- boost::movelib::adaptive_sort
+ boost::movelib::pdqsort
( 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());
+ , comp);
seq.erase(boost::movelib::unique
- ( seq.begin(), seq.end(), boost::movelib::negate<Compare>(comp))
- , seq.cend());
+ (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_)
+void flat_tree_adopt_sequence_unique// is_contiguous_container == false
+ (SequenceContainer &tseq, BOOST_RV_REF(SequenceContainer) seq, Compare comp, dtl::false_)
{
- boost::movelib::adaptive_sort(seq.begin(), seq.end(), comp);
+ boost::movelib::pdqsort(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);
}
+///////////////////////////////////////
+//
+// flat_tree_reserve
+//
+///////////////////////////////////////
template<class SequenceContainer>
-BOOST_CONTAINER_FORCEINLINE void
- flat_tree_reserve(SequenceContainer &tseq, typename SequenceContainer::size_type cap, container_detail::true_)
+BOOST_CONTAINER_FORCEINLINE void // has_reserve == true
+ flat_tree_reserve(SequenceContainer &tseq, typename SequenceContainer::size_type cap, dtl::true_)
{
tseq.reserve(cap);
}
template<class SequenceContainer>
-BOOST_CONTAINER_FORCEINLINE void
- flat_tree_reserve(SequenceContainer &, typename SequenceContainer::size_type, container_detail::false_)
+BOOST_CONTAINER_FORCEINLINE void // has_reserve == false
+ flat_tree_reserve(SequenceContainer &, typename SequenceContainer::size_type, dtl::false_)
{
}
-template<class SequenceContainer>
+///////////////////////////////////////
+//
+// flat_tree_capacity
+//
+///////////////////////////////////////
+template<class SequenceContainer> // has_capacity == true
BOOST_CONTAINER_FORCEINLINE typename SequenceContainer::size_type
- flat_tree_capacity(const SequenceContainer &tseq, container_detail::true_)
+ flat_tree_capacity(const SequenceContainer &tseq, dtl::true_)
{
return tseq.capacity();
}
-template<class SequenceContainer>
+template<class SequenceContainer> // has_capacity == false
BOOST_CONTAINER_FORCEINLINE typename SequenceContainer::size_type
- flat_tree_capacity(const SequenceContainer &tseq, container_detail::false_)
+ flat_tree_capacity(const SequenceContainer &tseq, dtl::false_)
{
return tseq.size();
}
+///////////////////////////////////////
+//
+// flat_tree_value_compare
+//
+///////////////////////////////////////
+
template<class Compare, class Value, class KeyOfValue>
class flat_tree_value_compare
: private Compare
@@ -324,21 +426,14 @@ class flat_tree_value_compare
Compare &get_comp()
{ return *this; }
};
-/*
-template<class Pointer>
-struct get_flat_tree_iterators
-{
- typedef typename boost::container::container_detail::
- vec_iterator<Pointer, false> iterator;
- typedef typename boost::container::container_detail::
- vec_iterator<Pointer, true > const_iterator;
- typedef boost::container::reverse_iterator<iterator> reverse_iterator;
- typedef boost::container::reverse_iterator<const_iterator> const_reverse_iterator;
-};
-*/
+///////////////////////////////////////
+//
+// select_container_type
+//
+///////////////////////////////////////
template < class Value, class AllocatorOrContainer
- , bool = boost::container::container_detail::is_container<AllocatorOrContainer>::value >
+ , bool = boost::container::dtl::is_container<AllocatorOrContainer>::value >
struct select_container_type
{
typedef AllocatorOrContainer type;
@@ -350,6 +445,12 @@ struct select_container_type<Value, AllocatorOrContainer, false>
typedef boost::container::vector<Value, AllocatorOrContainer> type;
};
+
+///////////////////////////////////////
+//
+// flat_tree
+//
+///////////////////////////////////////
template <class Value, class KeyOfValue,
class Compare, class AllocatorOrContainer>
class flat_tree
@@ -452,20 +553,20 @@ class flat_tree
//!Standard extension
typedef BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_DEFAULT
- (boost::container::container_detail::, container_type
+ (boost::container::dtl::, 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);
+ BOOST_INTRUSIVE_HAS_TYPE(boost::container::dtl::, container_type, stored_allocator_type);
private:
typedef allocator_traits<stored_allocator_type> stored_allocator_traits;
public:
- typedef typename container_detail::if_c
+ typedef typename dtl::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
+ typedef typename dtl::if_c
<has_stored_allocator_type, stored_allocator_type &, allocator_type>::type get_stored_allocator_noconst_return_t;
BOOST_CONTAINER_FORCEINLINE flat_tree()
@@ -489,7 +590,7 @@ class flat_tree
{ }
BOOST_CONTAINER_FORCEINLINE flat_tree(BOOST_RV_REF(flat_tree) x)
- BOOST_NOEXCEPT_IF(boost::container::container_detail::is_nothrow_move_constructible<Compare>::value)
+ BOOST_NOEXCEPT_IF(boost::container::dtl::is_nothrow_move_constructible<Compare>::value)
: m_data(boost::move(x.m_data))
{ }
@@ -599,7 +700,7 @@ class flat_tree
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)
+ boost::container::dtl::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
@@ -632,12 +733,12 @@ class flat_tree
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>());
+ return flat_tree_get_stored_allocator(this->m_data.m_seq, dtl::bool_<has_stored_allocator_type>());
}
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>());
+ return flat_tree_get_stored_allocator(this->m_data.m_seq, dtl::bool_<has_stored_allocator_type>());
}
BOOST_CONTAINER_FORCEINLINE iterator begin()
@@ -687,7 +788,7 @@ class flat_tree
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 )
+ && boost::container::dtl::is_nothrow_swappable<Compare>::value )
{ this->m_data.swap(other.m_data); }
public:
@@ -767,109 +868,51 @@ class flat_tree
template <class InIt>
void insert_unique(InIt first, InIt last)
{
- for ( ; first != last; ++first){
- this->insert_unique(*first);
- }
- }
+ dtl::bool_<is_contiguous_container<container_type>::value> contiguous_tag;
+ container_type &seq = this->m_data.m_seq;
+ value_compare &val_cmp = this->priv_value_comp();
- template <class InIt>
- void insert_equal(InIt first, InIt last
- #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
- , typename container_detail::enable_if_c
- < container_detail::is_input_iterator<InIt>::value
- >::type * = 0
- #endif
- )
- { this->priv_insert_equal_loop(first, last); }
+ //Step 1: put new elements in the back
+ typename container_type::iterator const it = seq.insert(seq.cend(), first, last);
+
+ //Step 2: sort them
+ boost::movelib::pdqsort(it, seq.end(), val_cmp);
+
+ //Step 3: only left unique values from the back not already present in the original range
+ typename container_type::iterator const e = boost::movelib::inplace_set_unique_difference
+ (it, seq.end(), seq.begin(), it, val_cmp);
+ seq.erase(e, seq.cend());
+
+ //Step 4: merge both ranges
+ (flat_tree_container_inplace_merge)(seq, it, this->priv_value_comp(), contiguous_tag);
+ }
template <class InIt>
- void insert_equal(InIt first, InIt last
- #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
- , typename container_detail::enable_if_c
- < !container_detail::is_input_iterator<InIt>::value
- >::type * = 0
- #endif
- )
+ void insert_equal(InIt first, InIt last)
{
- const size_type len = static_cast<size_type>(boost::container::iterator_distance(first, last));
- this->reserve(this->size()+len);
- this->priv_insert_equal_loop(first, last);
+ dtl::bool_<is_contiguous_container<container_type>::value> contiguous_tag;
+ container_type &seq = this->m_data.m_seq;
+ typename container_type::iterator const it = seq.insert(seq.cend(), first, last);
+ (flat_tree_container_inplace_sort_ending)(seq, it, this->priv_value_comp(), contiguous_tag);
+ (flat_tree_container_inplace_merge) (seq, it, this->priv_value_comp(), contiguous_tag);
}
//Ordered
template <class InIt>
- void insert_equal(ordered_range_t, InIt first, InIt last
- #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
- , typename container_detail::enable_if_c
- < container_detail::is_input_iterator<InIt>::value
- >::type * = 0
- #endif
- )
- { this->priv_insert_equal_loop_ordered(first, last); }
-
- template <class FwdIt>
- void insert_equal(ordered_range_t, FwdIt first, FwdIt last
- #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
- , typename container_detail::enable_if_c
- < !container_detail::is_input_iterator<FwdIt>::value &&
- container_detail::is_forward_iterator<FwdIt>::value
- >::type * = 0
- #endif
- )
- {
- const size_type len = static_cast<size_type>(boost::container::iterator_distance(first, last));
- this->reserve(this->size()+len);
- this->priv_insert_equal_loop_ordered(first, last);
- }
-
- template <class BidirIt>
- void insert_equal(ordered_range_t, BidirIt first, BidirIt last
- #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
- , typename container_detail::disable_if_or
- < void
- , container_detail::is_input_iterator<BidirIt>
- , container_detail::is_forward_iterator<BidirIt>
- >::type * = 0
- #endif
- )
- {
- 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>());
+ void insert_equal(ordered_range_t, InIt first, InIt last)
+ {
+ const bool value = boost::container::dtl::
+ has_member_function_callable_with_merge_unique<container_type, InIt, InIt, value_compare>::value;
+ (flat_tree_merge_equal)(this->m_data.m_seq, first, last, this->priv_value_comp(), dtl::bool_<value>());
}
template <class InIt>
- void insert_unique(ordered_unique_range_t, InIt first, InIt last
- #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
- , typename container_detail::enable_if_or
- < void
- , container_detail::is_input_iterator<InIt>
- , container_detail::is_forward_iterator<InIt>
- >::type * = 0
- #endif
- )
- {
- const_iterator pos(this->cend());
- for ( ; first != last; ++first){
- pos = this->insert_unique(pos, *first);
- ++pos;
- }
- }
-
- template <class BidirIt>
- void insert_unique(ordered_unique_range_t, BidirIt first, BidirIt last
- #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
- , typename container_detail::enable_if_c
- < !(container_detail::is_input_iterator<BidirIt>::value ||
- container_detail::is_forward_iterator<BidirIt>::value)
- >::type * = 0
- #endif
- )
+ void insert_unique(ordered_unique_range_t, InIt first, InIt last)
{
- 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>());
+ const bool value = boost::container::dtl::
+ has_member_function_callable_with_merge_unique<container_type, InIt, InIt, value_compare>::value;
+ (flat_tree_merge_unique)(this->m_data.m_seq, first, last, this->priv_value_comp(), dtl::bool_<value>());
}
#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
@@ -878,7 +921,7 @@ class flat_tree
std::pair<iterator, bool> emplace_unique(BOOST_FWD_REF(Args)... args)
{
typename aligned_storage<sizeof(value_type), alignment_of<value_type>::value>::type v;
- value_type &val = *static_cast<value_type *>(static_cast<void *>(&v));
+ value_type &val = *static_cast<value_type *>(static_cast<void *>(v.data));
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, value_type> d(a, val);
@@ -890,7 +933,7 @@ 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));
+ value_type &val = *static_cast<value_type *>(static_cast<void *>(v.data));
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, value_type> d(a, val);
@@ -901,7 +944,7 @@ class flat_tree
iterator emplace_equal(BOOST_FWD_REF(Args)... args)
{
typename aligned_storage<sizeof(value_type), alignment_of<value_type>::value>::type v;
- value_type &val = *static_cast<value_type *>(static_cast<void *>(&v));
+ value_type &val = *static_cast<value_type *>(static_cast<void *>(v.data));
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, value_type> d(a, val);
@@ -913,7 +956,7 @@ 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));
+ value_type &val = *static_cast<value_type *>(static_cast<void *>(v.data));
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, value_type> d(a, val);
@@ -950,7 +993,7 @@ class flat_tree
std::pair<iterator, bool> emplace_unique(BOOST_MOVE_UREF##N)\
{\
typename aligned_storage<sizeof(value_type), alignment_of<value_type>::value>::type v;\
- value_type &val = *static_cast<value_type *>(static_cast<void *>(&v));\
+ value_type &val = *static_cast<value_type *>(static_cast<void *>(v.data));\
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, value_type> d(a, val);\
@@ -961,7 +1004,7 @@ class flat_tree
iterator emplace_hint_unique(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
{\
typename aligned_storage<sizeof(value_type), alignment_of<value_type>::value>::type v;\
- value_type &val = *static_cast<value_type *>(static_cast<void *>(&v));\
+ value_type &val = *static_cast<value_type *>(static_cast<void *>(v.data));\
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, value_type> d(a, val);\
@@ -972,7 +1015,7 @@ class flat_tree
iterator emplace_equal(BOOST_MOVE_UREF##N)\
{\
typename aligned_storage<sizeof(value_type), alignment_of<value_type>::value>::type v;\
- value_type &val = *static_cast<value_type *>(static_cast<void *>(&v));\
+ value_type &val = *static_cast<value_type *>(static_cast<void *>(v.data));\
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, value_type> d(a, val);\
@@ -983,7 +1026,7 @@ class flat_tree
iterator emplace_hint_equal(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
{\
typename aligned_storage <sizeof(value_type), alignment_of<value_type>::value>::type v;\
- value_type &val = *static_cast<value_type *>(static_cast<void *>(&v));\
+ value_type &val = *static_cast<value_type *>(static_cast<void *>(v.data));\
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, value_type> d(a, val);\
@@ -1069,30 +1112,30 @@ class flat_tree
BOOST_CONTAINER_FORCEINLINE iterator nth(size_type n) BOOST_NOEXCEPT_OR_NOTHROW
{
- const bool value = boost::container::container_detail::
+ const bool value = boost::container::dtl::
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>());
+ return flat_tree_nth<iterator>(this->m_data.m_seq, n, dtl::bool_<value>());
}
BOOST_CONTAINER_FORCEINLINE const_iterator nth(size_type n) const BOOST_NOEXCEPT_OR_NOTHROW
{
- const bool value = boost::container::container_detail::
+ const bool value = boost::container::dtl::
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>());
+ return flat_tree_nth<const_iterator>(this->m_data.m_seq, n, dtl::bool_<value>());
}
BOOST_CONTAINER_FORCEINLINE size_type index_of(iterator p) BOOST_NOEXCEPT_OR_NOTHROW
{
- const bool value = boost::container::container_detail::
+ const bool value = boost::container::dtl::
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>());
+ return flat_tree_index_of(this->m_data.m_seq, p, dtl::bool_<value>());
}
BOOST_CONTAINER_FORCEINLINE size_type index_of(const_iterator p) const BOOST_NOEXCEPT_OR_NOTHROW
{
- const bool value = boost::container::container_detail::
+ const bool value = boost::container::dtl::
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>());
+ return flat_tree_index_of(this->m_data.m_seq, p, dtl::bool_<value>());
}
// set operations:
@@ -1141,26 +1184,26 @@ class flat_tree
BOOST_CONTAINER_FORCEINLINE void merge_unique(flat_tree& source)
{
- const bool value = boost::container::container_detail::
+ const bool value = boost::container::dtl::
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>());
+ , dtl::bool_<value>());
}
BOOST_CONTAINER_FORCEINLINE void merge_equal(flat_tree& source)
{
- const bool value = boost::container::container_detail::
+ const bool value = boost::container::dtl::
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>());
+ , dtl::bool_<value>());
}
BOOST_CONTAINER_FORCEINLINE iterator lower_bound(const key_type& k)
@@ -1189,16 +1232,16 @@ class flat_tree
BOOST_CONTAINER_FORCEINLINE size_type capacity() const
{
- const bool value = boost::container::container_detail::
+ const bool value = boost::container::dtl::
has_member_function_callable_with_capacity<container_type>::value;
- return (flat_tree_capacity)(this->m_data.m_seq, container_detail::bool_<value>());
+ return (flat_tree_capacity)(this->m_data.m_seq, dtl::bool_<value>());
}
BOOST_CONTAINER_FORCEINLINE void reserve(size_type cnt)
{
- const bool value = boost::container::container_detail::
+ const bool value = boost::container::dtl::
has_member_function_callable_with_reserve<container_type, size_type>::value;
- (flat_tree_reserve)(this->m_data.m_seq, cnt, container_detail::bool_<value>());
+ (flat_tree_reserve)(this->m_data.m_seq, cnt, dtl::bool_<value>());
}
BOOST_CONTAINER_FORCEINLINE container_type extract_sequence()
@@ -1214,13 +1257,13 @@ class flat_tree
BOOST_CONTAINER_FORCEINLINE void adopt_sequence_equal(BOOST_RV_REF(container_type) 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>());
+ , dtl::bool_<is_contiguous_container<container_type>::value>());
}
BOOST_CONTAINER_FORCEINLINE void adopt_sequence_unique(BOOST_RV_REF(container_type) 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>());
+ , dtl::bool_<is_contiguous_container<container_type>::value>());
}
void adopt_sequence_equal(ordered_range_t, BOOST_RV_REF(container_type) seq)
@@ -1270,14 +1313,10 @@ class flat_tree
//for the constructor
//Call end() every iteration as reallocation might have invalidated iterators
if(unique_insertion){
- for ( ; first != last; ++first){
- this->insert_unique(this->cend(), *first);
- }
+ this->insert_unique(first, last);
}
else{
- for ( ; first != last; ++first){
- this->insert_equal(this->cend(), *first);
- }
+ this->insert_equal (first, last);
}
}
@@ -1474,30 +1513,9 @@ class flat_tree
}
return std::pair<RanIt, RanIt>(lb, ub);
}
-
- template<class InIt>
- void priv_insert_equal_loop(InIt first, InIt last)
- {
- for ( ; first != last; ++first){
- this->insert_equal(*first);
- }
- }
-
- template<class InIt>
- void priv_insert_equal_loop_ordered(InIt first, InIt last)
- {
- const_iterator pos(this->cend());
- for ( ; first != last; ++first){
- //If ordered, then try hint version
- //to achieve constant-time complexity per insertion
- //in some cases
- pos = this->insert_equal(pos, *first);
- ++pos;
- }
- }
};
-} //namespace container_detail {
+} //namespace dtl {
} //namespace container {
@@ -1505,9 +1523,9 @@ class flat_tree
//!specialization for optimizations
template <class T, class KeyOfValue,
class Compare, class AllocatorOrContainer>
-struct has_trivial_destructor_after_move<boost::container::container_detail::flat_tree<T, KeyOfValue, Compare, AllocatorOrContainer> >
+struct has_trivial_destructor_after_move<boost::container::dtl::flat_tree<T, KeyOfValue, Compare, AllocatorOrContainer> >
{
- typedef typename boost::container::container_detail::select_container_type<T, AllocatorOrContainer>::type container_type;
+ typedef typename boost::container::dtl::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 &&