diff options
Diffstat (limited to 'boost/container/detail/flat_tree.hpp')
-rw-r--r-- | boost/container/detail/flat_tree.hpp | 694 |
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 { |