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.hpp694
1 files changed, 373 insertions, 321 deletions
diff --git a/boost/container/detail/flat_tree.hpp b/boost/container/detail/flat_tree.hpp
index 23be0bfd13..a6f7568b43 100644
--- a/boost/container/detail/flat_tree.hpp
+++ b/boost/container/detail/flat_tree.hpp
@@ -1,6 +1,6 @@
////////////////////////////////////////////////////////////////////////////////
//
-// (C) Copyright Ion Gaztanaga 2005-2012. Distributed under the Boost
+// (C) Copyright Ion Gaztanaga 2005-2013. 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)
//
@@ -11,11 +11,11 @@
#ifndef BOOST_CONTAINER_FLAT_TREE_HPP
#define BOOST_CONTAINER_FLAT_TREE_HPP
-#if (defined _MSC_VER) && (_MSC_VER >= 1200)
+#if defined(_MSC_VER)
# pragma once
#endif
-#include "config_begin.hpp"
+#include <boost/container/detail/config_begin.hpp>
#include <boost/container/detail/workaround.hpp>
#include <boost/container/container_fwd.hpp>
@@ -25,7 +25,7 @@
#include <utility>
#include <boost/type_traits/has_trivial_destructor.hpp>
-#include <boost/move/move.hpp>
+#include <boost/move/utility_core.hpp>
#include <boost/container/detail/utilities.hpp>
#include <boost/container/detail/pair.hpp>
@@ -33,7 +33,11 @@
#include <boost/container/detail/value_init.hpp>
#include <boost/container/detail/destroyers.hpp>
#include <boost/container/allocator_traits.hpp>
+#ifdef BOOST_CONTAINER_VECTOR_ITERATOR_IS_POINTER
+#include <boost/intrusive/pointer_traits.hpp>
+#endif
#include <boost/aligned_storage.hpp>
+#include <boost/move/make_unique.hpp>
namespace boost {
@@ -48,7 +52,7 @@ class flat_tree_value_compare
typedef Value first_argument_type;
typedef Value second_argument_type;
typedef bool return_type;
- public:
+ public:
flat_tree_value_compare()
: Compare()
{}
@@ -65,7 +69,7 @@ class flat_tree_value_compare
const Compare &get_comp() const
{ return *this; }
-
+
Compare &get_comp()
{ return *this; }
};
@@ -73,12 +77,23 @@ class flat_tree_value_compare
template<class Pointer>
struct get_flat_tree_iterators
{
- typedef typename container_detail::
- vector_iterator<Pointer> iterator;
- typedef typename container_detail::
- vector_const_iterator<Pointer> const_iterator;
- typedef std::reverse_iterator<iterator> reverse_iterator;
- typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
+ #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::container_detail::
+ reverse_iterator<iterator> reverse_iterator;
+ typedef boost::container::container_detail::
+ reverse_iterator<const_iterator> const_reverse_iterator;
};
template <class Key, class Value, class KeyOfValue,
@@ -103,7 +118,7 @@ class flat_tree
: value_compare(), m_vect()
{}
- Data(const Data &d)
+ explicit Data(const Data &d)
: value_compare(static_cast<const value_compare&>(d)), m_vect(d.m_vect)
{}
@@ -119,15 +134,18 @@ class flat_tree
: value_compare(boost::move(static_cast<value_compare&>(d))), m_vect(boost::move(d.m_vect), a)
{}
- Data(const Compare &comp)
+ explicit Data(const Compare &comp)
: value_compare(comp), m_vect()
{}
- Data(const Compare &comp,
- const allocator_t &alloc)
+ Data(const Compare &comp, const allocator_t &alloc)
: value_compare(comp), m_vect(alloc)
{}
+ explicit Data(const allocator_t &alloc)
+ : value_compare(), m_vect(alloc)
+ {}
+
Data& operator=(BOOST_COPY_ASSIGN_REF(Data) d)
{
this->value_compare::operator=(d);
@@ -145,7 +163,7 @@ class flat_tree
void swap(Data &d)
{
value_compare& mycomp = *this, & othercomp = d;
- container_detail::do_swap(mycomp, othercomp);
+ boost::container::swap_dispatch(mycomp, othercomp);
this->m_vect.swap(d.m_vect);
}
@@ -191,6 +209,10 @@ class flat_tree
: m_data(comp, a)
{ }
+ explicit flat_tree(const allocator_type& a)
+ : m_data(a)
+ { }
+
flat_tree(const flat_tree& x)
: m_data(x.m_data)
{ }
@@ -214,8 +236,31 @@ class flat_tree
: m_data(comp, a)
{ this->m_data.m_vect.insert(this->m_data.m_vect.end(), first, last); }
+ template <class InputIterator>
+ flat_tree( bool unique_insertion
+ , InputIterator first, InputIterator last
+ , const Compare& comp = Compare()
+ , const allocator_type& a = allocator_type())
+ : m_data(comp, a)
+ {
+ //Use cend() as hint to achieve linear time for
+ //ordered ranges as required by the standard
+ //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);
+ }
+ }
+ else{
+ for ( ; first != last; ++first){
+ this->insert_equal(this->cend(), *first);
+ }
+ }
+ }
+
~flat_tree()
- { }
+ {}
flat_tree& operator=(BOOST_COPY_ASSIGN_REF(flat_tree) x)
{ m_data = x.m_data; return *this; }
@@ -223,11 +268,14 @@ class flat_tree
flat_tree& operator=(BOOST_RV_REF(flat_tree) mx)
{ m_data = boost::move(mx.m_data); return *this; }
- public:
+ public:
// accessors:
Compare key_comp() const
{ return this->m_data.get_comp(); }
+ value_compare value_comp() const
+ { return this->m_data; }
+
allocator_type get_allocator() const
{ return this->m_data.m_vect.get_allocator(); }
@@ -289,21 +337,21 @@ class flat_tree
// insert/erase
std::pair<iterator,bool> insert_unique(const value_type& val)
{
+ std::pair<iterator,bool> ret;
insert_commit_data data;
- std::pair<iterator,bool> ret = priv_insert_unique_prepare(val, data);
- if(ret.second){
- ret.first = priv_insert_commit(data, val);
- }
+ ret.second = this->priv_insert_unique_prepare(val, data);
+ ret.first = ret.second ? this->priv_insert_commit(data, val)
+ : iterator(vector_iterator_get_ptr(data.position));
return ret;
}
std::pair<iterator,bool> insert_unique(BOOST_RV_REF(value_type) val)
{
+ std::pair<iterator,bool> ret;
insert_commit_data data;
- std::pair<iterator,bool> ret = priv_insert_unique_prepare(val, data);
- if(ret.second){
- ret.first = priv_insert_commit(data, boost::move(val));
- }
+ ret.second = this->priv_insert_unique_prepare(val, data);
+ ret.first = ret.second ? this->priv_insert_commit(data, boost::move(val))
+ : iterator(vector_iterator_get_ptr(data.position));
return ret;
}
@@ -323,69 +371,134 @@ class flat_tree
iterator insert_unique(const_iterator pos, const value_type& val)
{
+ std::pair<iterator,bool> ret;
insert_commit_data data;
- std::pair<iterator,bool> ret = priv_insert_unique_prepare(pos, val, data);
- if(ret.second){
- ret.first = priv_insert_commit(data, val);
- }
- return ret.first;
+ return this->priv_insert_unique_prepare(pos, val, data)
+ ? this->priv_insert_commit(data, val)
+ : iterator(vector_iterator_get_ptr(data.position));
}
- iterator insert_unique(const_iterator pos, BOOST_RV_REF(value_type) mval)
+ iterator insert_unique(const_iterator pos, BOOST_RV_REF(value_type) val)
{
+ std::pair<iterator,bool> ret;
insert_commit_data data;
- std::pair<iterator,bool> ret = priv_insert_unique_prepare(pos, mval, data);
- if(ret.second){
- ret.first = priv_insert_commit(data, boost::move(mval));
- }
- return ret.first;
+ return this->priv_insert_unique_prepare(pos, val, data)
+ ? this->priv_insert_commit(data, boost::move(val))
+ : iterator(vector_iterator_get_ptr(data.position));
}
iterator insert_equal(const_iterator pos, const value_type& val)
{
insert_commit_data data;
this->priv_insert_equal_prepare(pos, val, data);
- return priv_insert_commit(data, val);
+ return this->priv_insert_commit(data, val);
}
iterator insert_equal(const_iterator pos, BOOST_RV_REF(value_type) mval)
{
insert_commit_data data;
this->priv_insert_equal_prepare(pos, mval, data);
- return priv_insert_commit(data, boost::move(mval));
+ return this->priv_insert_commit(data, boost::move(mval));
}
template <class InIt>
void insert_unique(InIt first, InIt last)
{
- for ( ; first != last; ++first)
+ for ( ; first != last; ++first){
this->insert_unique(*first);
+ }
}
template <class InIt>
- void insert_equal(InIt first, InIt last)
+ 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); }
+
+ 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
+ )
{
- typedef typename
- std::iterator_traits<InIt>::iterator_category ItCat;
- this->priv_insert_equal(first, last, ItCat());
+ const size_type len = static_cast<size_type>(std::distance(first, last));
+ this->reserve(this->size()+len);
+ this->priv_insert_equal_loop(first, last);
}
+ //Ordered
+
template <class InIt>
- void insert_equal(ordered_range_t, InIt first, InIt last)
+ 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
+ )
{
- typedef typename
- std::iterator_traits<InIt>::iterator_category ItCat;
- this->priv_insert_equal(ordered_range_t(), first, last, ItCat());
+ const size_type len = static_cast<size_type>(std::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::enable_if_c
+ < !container_detail::is_input_iterator<BidirIt>::value &&
+ !container_detail::is_forward_iterator<BidirIt>::value
+ >::type * = 0
+ #endif
+ )
+ { this->priv_insert_ordered_range(false, first, last); }
+
template <class InIt>
- void insert_unique(ordered_unique_range_t, InIt first, InIt last)
- {
- typedef typename
- std::iterator_traits<InIt>::iterator_category ItCat;
- this->priv_insert_unique(ordered_unique_range_t(), first, last, ItCat());
+ void insert_unique(ordered_unique_range_t, InIt first, InIt last
+ #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
+ , typename container_detail::enable_if_c
+ < container_detail::is_input_iterator<InIt>::value ||
+ container_detail::is_forward_iterator<InIt>::value
+ >::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
+ )
+ { this->priv_insert_ordered_range(true, first, last); }
+
#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
template <class... Args>
@@ -396,13 +509,7 @@ class flat_tree
stored_allocator_type &a = this->get_stored_allocator();
stored_allocator_traits::construct(a, &val, ::boost::forward<Args>(args)... );
value_destructor<stored_allocator_type> d(a, val);
- insert_commit_data data;
- std::pair<iterator,bool> ret =
- priv_insert_unique_prepare(val, data);
- if(ret.second){
- ret.first = priv_insert_commit(data, boost::move(val));
- }
- return ret;
+ return this->insert_unique(::boost::move(val));
}
template <class... Args>
@@ -413,12 +520,7 @@ class flat_tree
stored_allocator_type &a = this->get_stored_allocator();
stored_allocator_traits::construct(a, &val, ::boost::forward<Args>(args)... );
value_destructor<stored_allocator_type> d(a, val);
- insert_commit_data data;
- std::pair<iterator,bool> ret = priv_insert_unique_prepare(hint, val, data);
- if(ret.second){
- ret.first = priv_insert_commit(data, boost::move(val));
- }
- return ret.first;
+ return this->insert_unique(hint, ::boost::move(val));
}
template <class... Args>
@@ -429,9 +531,7 @@ class flat_tree
stored_allocator_type &a = this->get_stored_allocator();
stored_allocator_traits::construct(a, &val, ::boost::forward<Args>(args)... );
value_destructor<stored_allocator_type> d(a, val);
- iterator i = this->upper_bound(KeyOfValue()(val));
- i = this->m_data.m_vect.insert(i, boost::move(val));
- return i;
+ return this->insert_equal(::boost::move(val));
}
template <class... Args>
@@ -442,10 +542,7 @@ class flat_tree
stored_allocator_type &a = this->get_stored_allocator();
stored_allocator_traits::construct(a, &val, ::boost::forward<Args>(args)... );
value_destructor<stored_allocator_type> d(a, val);
- insert_commit_data data;
- this->priv_insert_equal_prepare(hint, val, data);
- iterator i = priv_insert_commit(data, boost::move(val));
- return i;
+ return this->insert_equal(hint, ::boost::move(val));
}
#else //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
@@ -461,12 +558,7 @@ class flat_tree
stored_allocator_traits::construct(a, &val \
BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _) ); \
value_destructor<stored_allocator_type> d(a, val); \
- insert_commit_data data; \
- std::pair<iterator,bool> ret = priv_insert_unique_prepare(val, data); \
- if(ret.second){ \
- ret.first = priv_insert_commit(data, boost::move(val)); \
- } \
- return ret; \
+ return this->insert_unique(::boost::move(val)); \
} \
\
BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \
@@ -478,13 +570,8 @@ class flat_tree
stored_allocator_type &a = this->get_stored_allocator(); \
stored_allocator_traits::construct(a, &val \
BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _) ); \
- value_destructor<stored_allocator_type> d(a, val); \
- insert_commit_data data; \
- std::pair<iterator,bool> ret = priv_insert_unique_prepare(hint, val, data); \
- if(ret.second){ \
- ret.first = priv_insert_commit(data, boost::move(val)); \
- } \
- return ret.first; \
+ value_destructor<stored_allocator_type> d(a, val); \
+ return this->insert_unique(hint, ::boost::move(val)); \
} \
\
BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \
@@ -496,9 +583,7 @@ class flat_tree
stored_allocator_traits::construct(a, &val \
BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _) ); \
value_destructor<stored_allocator_type> d(a, val); \
- iterator i = this->upper_bound(KeyOfValue()(val)); \
- i = this->m_data.m_vect.insert(i, boost::move(val)); \
- return i; \
+ return this->insert_equal(::boost::move(val)); \
} \
\
BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \
@@ -511,12 +596,8 @@ class flat_tree
stored_allocator_traits::construct(a, &val \
BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _) ); \
value_destructor<stored_allocator_type> d(a, val); \
- insert_commit_data data; \
- this->priv_insert_equal_prepare(hint, val, data); \
- iterator i = priv_insert_commit(data, boost::move(val)); \
- return i; \
+ return this->insert_equal(hint, ::boost::move(val)); \
} \
-
//!
#define BOOST_PP_LOCAL_LIMITS (0, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS)
#include BOOST_PP_LOCAL_ITERATE()
@@ -554,26 +635,26 @@ class flat_tree
// set operations:
iterator find(const key_type& k)
{
- const Compare &key_comp = this->m_data.get_comp();
iterator i = this->lower_bound(k);
-
- if (i != this->end() && key_comp(k, KeyOfValue()(*i))){
- i = this->end();
+ iterator end_it = this->end();
+ if (i != end_it && this->m_data.get_comp()(k, KeyOfValue()(*i))){
+ i = end_it;
}
return i;
}
const_iterator find(const key_type& k) const
{
- const Compare &key_comp = this->m_data.get_comp();
const_iterator i = this->lower_bound(k);
- if (i != this->end() && key_comp(k, KeyOfValue()(*i))){
- i = this->end();
+ const_iterator end_it = this->cend();
+ if (i != end_it && this->m_data.get_comp()(k, KeyOfValue()(*i))){
+ i = end_it;
}
return i;
}
+ // set operations:
size_type count(const key_type& k) const
{
std::pair<const_iterator, const_iterator> p = this->equal_range(k);
@@ -585,25 +666,57 @@ class flat_tree
{ return this->priv_lower_bound(this->begin(), this->end(), k); }
const_iterator lower_bound(const key_type& k) const
- { return this->priv_lower_bound(this->begin(), this->end(), k); }
+ { return this->priv_lower_bound(this->cbegin(), this->cend(), k); }
iterator upper_bound(const key_type& k)
{ return this->priv_upper_bound(this->begin(), this->end(), k); }
const_iterator upper_bound(const key_type& k) const
- { return this->priv_upper_bound(this->begin(), this->end(), k); }
+ { return this->priv_upper_bound(this->cbegin(), this->cend(), k); }
std::pair<iterator,iterator> equal_range(const key_type& k)
{ return this->priv_equal_range(this->begin(), this->end(), k); }
std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const
- { return this->priv_equal_range(this->begin(), this->end(), k); }
+ { return this->priv_equal_range(this->cbegin(), this->cend(), k); }
+
+ std::pair<iterator, iterator> lower_bound_range(const key_type& k)
+ { return this->priv_lower_bound_range(this->begin(), this->end(), k); }
+
+ std::pair<const_iterator, const_iterator> lower_bound_range(const key_type& k) const
+ { return this->priv_lower_bound_range(this->cbegin(), this->cend(), k); }
- size_type capacity() const
+ size_type capacity() const
{ return this->m_data.m_vect.capacity(); }
- void reserve(size_type count)
- { this->m_data.m_vect.reserve(count); }
+ void reserve(size_type cnt)
+ { this->m_data.m_vect.reserve(cnt); }
+
+ friend bool operator==(const flat_tree& x, const flat_tree& y)
+ {
+ return x.size() == y.size() && std::equal(x.begin(), x.end(), y.begin());
+ }
+
+ friend bool operator<(const flat_tree& x, const flat_tree& y)
+ {
+ return std::lexicographical_compare(x.begin(), x.end(),
+ y.begin(), y.end());
+ }
+
+ friend bool operator!=(const flat_tree& x, const flat_tree& y)
+ { return !(x == y); }
+
+ friend bool operator>(const flat_tree& x, const flat_tree& y)
+ { return y < x; }
+
+ friend bool operator<=(const flat_tree& x, const flat_tree& y)
+ { return !(y < x); }
+
+ friend bool operator>=(const flat_tree& x, const flat_tree& y)
+ { return !(x < y); }
+
+ friend void swap(flat_tree& x, flat_tree& y)
+ { x.swap(y); }
private:
struct insert_commit_data
@@ -624,10 +737,10 @@ class flat_tree
// insert val before upper_bound(val)
// else
// insert val before lower_bound(val)
- const value_compare &value_comp = this->m_data;
+ const value_compare &val_cmp = this->m_data;
- if(pos == this->cend() || !value_comp(*pos, val)){
- if (pos == this->cbegin() || !value_comp(val, pos[-1])){
+ if(pos == this->cend() || !val_cmp(*pos, val)){
+ if (pos == this->cbegin() || !val_cmp(val, pos[-1])){
data.position = pos;
}
else{
@@ -641,21 +754,19 @@ class flat_tree
}
}
- std::pair<iterator,bool> priv_insert_unique_prepare
- (const_iterator beg, const_iterator end, const value_type& val, insert_commit_data &commit_data)
+ bool priv_insert_unique_prepare
+ (const_iterator b, const_iterator e, const value_type& val, insert_commit_data &commit_data)
{
- const value_compare &value_comp = this->m_data;
- commit_data.position = this->priv_lower_bound(beg, end, KeyOfValue()(val));
- return std::pair<iterator,bool>
- ( *reinterpret_cast<iterator*>(&commit_data.position)
- , commit_data.position == end || value_comp(val, *commit_data.position));
+ const value_compare &val_cmp = this->m_data;
+ commit_data.position = this->priv_lower_bound(b, e, KeyOfValue()(val));
+ return commit_data.position == e || val_cmp(val, *commit_data.position);
}
- std::pair<iterator,bool> priv_insert_unique_prepare
+ bool priv_insert_unique_prepare
(const value_type& val, insert_commit_data &commit_data)
- { return priv_insert_unique_prepare(this->begin(), this->end(), val, commit_data); }
+ { return this->priv_insert_unique_prepare(this->cbegin(), this->cend(), val, commit_data); }
- std::pair<iterator,bool> priv_insert_unique_prepare
+ bool priv_insert_unique_prepare
(const_iterator pos, const value_type& val, insert_commit_data &commit_data)
{
//N1780. Props to Howard Hinnant!
@@ -669,37 +780,32 @@ class flat_tree
// insert val after pos
//else
// insert val before lower_bound(val)
- const value_compare &value_comp = this->m_data;
-
- if(pos == this->cend() || value_comp(val, *pos)){
- if(pos != this->cbegin() && !value_comp(val, pos[-1])){
- if(value_comp(pos[-1], val)){
- commit_data.position = pos;
- return std::pair<iterator,bool>(*reinterpret_cast<iterator*>(&pos), true);
- }
- else{
- return std::pair<iterator,bool>(*reinterpret_cast<iterator*>(&pos), false);
- }
+ const value_compare &val_cmp = this->m_data;
+ const const_iterator cend_it = this->cend();
+ if(pos == cend_it || val_cmp(val, *pos)){ //Check if val should go before end
+ const const_iterator cbeg = this->cbegin();
+ commit_data.position = pos;
+ if(pos == cbeg){ //If container is empty then insert it in the beginning
+ return true;
+ }
+ const_iterator prev(pos);
+ --prev;
+ if(val_cmp(*prev, val)){ //If previous element was less, then it should go between prev and pos
+ return true;
+ }
+ else if(!val_cmp(val, *prev)){ //If previous was equal then insertion should fail
+ commit_data.position = prev;
+ return false;
+ }
+ else{ //Previous was bigger so insertion hint was pointless, dispatch to hintless insertion
+ //but reduce the search between beg and prev as prev is bigger than val
+ return this->priv_insert_unique_prepare(cbeg, prev, val, commit_data);
}
- return this->priv_insert_unique_prepare(this->cbegin(), pos, val, commit_data);
}
-
- // Works, but increases code complexity
- //Next check
- //else if (value_comp(*pos, val) && !value_comp(pos[1], val)){
- // if(value_comp(val, pos[1])){
- // commit_data.position = pos+1;
- // return std::pair<iterator,bool>(pos+1, true);
- // }
- // else{
- // return std::pair<iterator,bool>(pos+1, false);
- // }
- //}
else{
- //[... pos ... val ... ]
//The hint is before the insertion position, so insert it
- //in the remaining range
- return this->priv_insert_unique_prepare(pos, this->end(), val, commit_data);
+ //in the remaining range [pos, end)
+ return this->priv_insert_unique_prepare(pos, cend_it, val, commit_data);
}
}
@@ -713,50 +819,50 @@ class flat_tree
}
template <class RanIt>
- RanIt priv_lower_bound(RanIt first, RanIt last,
+ RanIt priv_lower_bound(RanIt first, const RanIt last,
const key_type & key) const
{
- const Compare &key_comp = this->m_data.get_comp();
+ const Compare &key_cmp = this->m_data.get_comp();
KeyOfValue key_extract;
- difference_type len = last - first, half;
+ size_type len = static_cast<size_type>(last - first);
RanIt middle;
- while (len > 0) {
- half = len >> 1;
+ while (len) {
+ size_type step = len >> 1;
middle = first;
- middle += half;
+ middle += step;
- if (key_comp(key_extract(*middle), key)) {
- ++middle;
- first = middle;
- len = len - half - 1;
+ if (key_cmp(key_extract(*middle), key)) {
+ first = ++middle;
+ len -= step + 1;
+ }
+ else{
+ len = step;
}
- else
- len = half;
}
return first;
}
template <class RanIt>
- RanIt priv_upper_bound(RanIt first, RanIt last,
+ RanIt priv_upper_bound(RanIt first, const RanIt last,
const key_type & key) const
{
- const Compare &key_comp = this->m_data.get_comp();
+ const Compare &key_cmp = this->m_data.get_comp();
KeyOfValue key_extract;
- difference_type len = last - first, half;
+ size_type len = static_cast<size_type>(last - first);
RanIt middle;
- while (len > 0) {
- half = len >> 1;
+ while (len) {
+ size_type step = len >> 1;
middle = first;
- middle += half;
+ middle += step;
- if (key_comp(key, key_extract(*middle))) {
- len = half;
+ if (key_cmp(key, key_extract(*middle))) {
+ len = step;
}
else{
first = ++middle;
- len = len - half - 1;
+ len -= step + 1;
}
}
return first;
@@ -766,189 +872,135 @@ class flat_tree
std::pair<RanIt, RanIt>
priv_equal_range(RanIt first, RanIt last, const key_type& key) const
{
- const Compare &key_comp = this->m_data.get_comp();
+ const Compare &key_cmp = this->m_data.get_comp();
KeyOfValue key_extract;
- difference_type len = last - first, half;
- RanIt middle, left, right;
+ size_type len = static_cast<size_type>(last - first);
+ RanIt middle;
- while (len > 0) {
- half = len >> 1;
+ while (len) {
+ size_type step = len >> 1;
middle = first;
- middle += half;
+ middle += step;
- if (key_comp(key_extract(*middle), key)){
- first = middle;
- ++first;
- len = len - half - 1;
+ if (key_cmp(key_extract(*middle), key)){
+ first = ++middle;
+ len -= step + 1;
}
- else if (key_comp(key, key_extract(*middle))){
- len = half;
+ else if (key_cmp(key, key_extract(*middle))){
+ len = step;
}
else {
- left = this->priv_lower_bound(first, middle, key);
- first += len;
- right = this->priv_upper_bound(++middle, first, key);
- return std::pair<RanIt, RanIt>(left, right);
+ //Middle is equal to key
+ last = first;
+ last += len;
+ return std::pair<RanIt, RanIt>
+ ( this->priv_lower_bound(first, middle, key)
+ , this->priv_upper_bound(++middle, last, key));
}
}
return std::pair<RanIt, RanIt>(first, first);
}
- template <class BidirIt>
- void priv_insert_equal(ordered_range_t, BidirIt first, BidirIt last, std::bidirectional_iterator_tag)
+ template<class RanIt>
+ std::pair<RanIt, RanIt> priv_lower_bound_range(RanIt first, RanIt last, const key_type& k) const
{
- size_type len = static_cast<size_type>(std::distance(first, last));
- const size_type BurstSize = 16;
- size_type positions[BurstSize];
+ const Compare &key_cmp = this->m_data.get_comp();
+ KeyOfValue key_extract;
+ RanIt lb(this->priv_lower_bound(first, last, k)), ub(lb);
+ if(lb != last && static_cast<difference_type>(!key_cmp(k, key_extract(*lb)))){
+ ++ub;
+ }
+ return std::pair<RanIt, RanIt>(lb, ub);
+ }
- //Prereserve all memory so that iterators are not invalidated
- this->reserve(this->size()+len);
- const const_iterator beg(this->cbegin());
- const_iterator pos(beg);
- //Loop in burst sizes
- while(len){
- const size_type burst = len < BurstSize ? len : BurstSize;
- const const_iterator cend(this->cend());
- len -= burst;
- for(size_type i = 0; i != burst; ++i){
- //Get the insertion position for each key
- pos = const_cast<const flat_tree&>(*this).priv_upper_bound(pos, cend, KeyOfValue()(*first));
- positions[i] = static_cast<size_type>(pos - beg);
- ++first;
- }
- //Insert all in a single step in the precalculated positions
- this->m_data.m_vect.insert_ordered_at(burst, positions + burst, first);
- //Next search position updated
- pos += burst;
+ 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
+ pos = this->insert_equal(pos, *first);
+ ++pos;
}
}
template <class BidirIt>
- void priv_insert_unique(ordered_unique_range_t, BidirIt first, BidirIt last, std::bidirectional_iterator_tag)
+ void priv_insert_ordered_range(const bool unique_values, BidirIt first, BidirIt last)
{
size_type len = static_cast<size_type>(std::distance(first, last));
- const size_type BurstSize = 16;
- size_type positions[BurstSize];
- size_type skips[BurstSize];
-
//Prereserve all memory so that iterators are not invalidated
this->reserve(this->size()+len);
- const const_iterator beg(this->cbegin());
- const_iterator pos(beg);
- const value_compare &value_comp = this->m_data;
+ //Auxiliary data for insertion positions.
+ const size_type BurstSize = len;
+ const ::boost::movelib::unique_ptr<size_type[]> positions =
+ ::boost::movelib::make_unique_definit<size_type[]>(BurstSize);
+
+ const const_iterator b(this->cbegin());
+ const const_iterator ce(this->cend());
+ const_iterator pos(b);
+ const value_compare &val_cmp = this->m_data;
//Loop in burst sizes
- while(len){
- skips[0u] = 0u;
+ bool back_insert = false;
+ while(len && !back_insert){
const size_type burst = len < BurstSize ? len : BurstSize;
size_type unique_burst = 0u;
- const const_iterator cend(this->cend());
- while(unique_burst < burst && len > 0){
- //Get the insertion position for each key
- const value_type & val = *first++;
- --len;
- pos = const_cast<const flat_tree&>(*this).priv_lower_bound(pos, cend, KeyOfValue()(val));
+ size_type checked = 0;
+ for(; checked != burst; ++checked){
+ //Get the insertion position for each key, use std::iterator_traits<BidirIt>::value_type
+ //because it can be different from container::value_type
+ //(e.g. conversion between std::pair<A, B> -> boost::container::pair<A, B>
+ const typename std::iterator_traits<BidirIt>::value_type & val = *first;
+ pos = const_cast<const flat_tree&>(*this).priv_lower_bound(pos, ce, KeyOfValue()(val));
//Check if already present
- if(pos != cend && !value_comp(*pos, val)){
- ++skips[unique_burst];
- continue;
+ if (pos != ce){
+ ++first;
+ --len;
+ positions[checked] = (unique_values && !val_cmp(val, *pos)) ?
+ size_type(-1) : (++unique_burst, static_cast<size_type>(pos - b));
}
-
- //If not present, calculate position
- positions[unique_burst] = static_cast<size_type>(pos - beg);
- if(++unique_burst < burst)
- skips[unique_burst] = 0u;
+ else{ //this element and the remaining should be back inserted
+ back_insert = true;
+ break;
+ }
+ }
+ if(unique_burst){
+ //Insert all in a single step in the precalculated positions
+ this->m_data.m_vect.insert_ordered_at(unique_burst, positions.get() + checked, first);
+ //Next search position updated, iterator still valid because we've preserved the vector
+ pos += unique_burst;
}
- //Insert all in a single step in the precalculated positions
- this->m_data.m_vect.insert_ordered_at(unique_burst, positions + unique_burst, skips + unique_burst, first);
- //Next search position updated
- pos += unique_burst;
}
- }
-/*
- template <class FwdIt>
- void priv_insert_equal_forward(ordered_range_t, FwdIt first, FwdIt last, std::forward_iterator_tag)
- { this->priv_insert_equal(first, last, std::forward_iterator_tag()); }
-*/
- template <class InIt>
- void priv_insert_equal(ordered_range_t, InIt first, InIt last, std::input_iterator_tag)
- { this->priv_insert_equal(first, last, std::input_iterator_tag()); }
-
- template <class InIt>
- void priv_insert_unique(ordered_unique_range_t, InIt first, InIt last, std::input_iterator_tag)
- { this->priv_insert_unique(first, last, std::input_iterator_tag()); }
-/*
- template <class FwdIt>
- void priv_insert_equal_forward(FwdIt first, FwdIt last, std::forward_iterator_tag)
- {
- const size_type len = static_cast<size_type>(std::distance(first, last));
- this->reserve(this->size()+len);
- this->priv_insert_equal(first, last, std::input_iterator_tag());
- }
-*/
- template <class InIt>
- void priv_insert_equal(InIt first, InIt last, std::input_iterator_tag)
- {
- for ( ; first != last; ++first)
- this->insert_equal(*first);
+ //The remaining range should be back inserted
+ if(unique_values){
+ while(len--){
+ BidirIt next(first);
+ ++next;
+ if(next == last || val_cmp(*first, *next)){
+ const bool room = this->m_data.m_vect.stable_emplace_back(*first);
+ (void)room;
+ BOOST_ASSERT(room);
+ }
+ first = next;
+ }
+ BOOST_ASSERT(first == last);
+ }
+ else{
+ BOOST_ASSERT(size_type(std::distance(first, last)) == len);
+ if(len)
+ this->m_data.m_vect.insert(this->m_data.m_vect.cend(), len, first, last);
+ }
}
};
-template <class Key, class Value, class KeyOfValue,
- class Compare, class A>
-inline bool
-operator==(const flat_tree<Key,Value,KeyOfValue,Compare,A>& x,
- const flat_tree<Key,Value,KeyOfValue,Compare,A>& y)
-{
- return x.size() == y.size() &&
- std::equal(x.begin(), x.end(), y.begin());
-}
-
-template <class Key, class Value, class KeyOfValue,
- class Compare, class A>
-inline bool
-operator<(const flat_tree<Key,Value,KeyOfValue,Compare,A>& x,
- const flat_tree<Key,Value,KeyOfValue,Compare,A>& y)
-{
- return std::lexicographical_compare(x.begin(), x.end(),
- y.begin(), y.end());
-}
-
-template <class Key, class Value, class KeyOfValue,
- class Compare, class A>
-inline bool
-operator!=(const flat_tree<Key,Value,KeyOfValue,Compare,A>& x,
- const flat_tree<Key,Value,KeyOfValue,Compare,A>& y)
- { return !(x == y); }
-
-template <class Key, class Value, class KeyOfValue,
- class Compare, class A>
-inline bool
-operator>(const flat_tree<Key,Value,KeyOfValue,Compare,A>& x,
- const flat_tree<Key,Value,KeyOfValue,Compare,A>& y)
- { return y < x; }
-
-template <class Key, class Value, class KeyOfValue,
- class Compare, class A>
-inline bool
-operator<=(const flat_tree<Key,Value,KeyOfValue,Compare,A>& x,
- const flat_tree<Key,Value,KeyOfValue,Compare,A>& y)
- { return !(y < x); }
-
-template <class Key, class Value, class KeyOfValue,
- class Compare, class A>
-inline bool
-operator>=(const flat_tree<Key,Value,KeyOfValue,Compare,A>& x,
- const flat_tree<Key,Value,KeyOfValue,Compare,A>& y)
- { return !(x < y); }
-
-
-template <class Key, class Value, class KeyOfValue,
- class Compare, class A>
-inline void
-swap(flat_tree<Key,Value,KeyOfValue,Compare,A>& x,
- flat_tree<Key,Value,KeyOfValue,Compare,A>& y)
- { x.swap(y); }
-
} //namespace container_detail {
} //namespace container {
@@ -959,7 +1011,7 @@ template <class K, class V, class KOV,
class C, class A>
struct has_trivial_destructor_after_move<boost::container::container_detail::flat_tree<K, V, KOV, C, A> >
{
- static const bool value = has_trivial_destructor<A>::value && has_trivial_destructor<C>::value;
+ static const bool value = has_trivial_destructor_after_move<A>::value && has_trivial_destructor_after_move<C>::value;
};
*/
} //namespace boost {