Subject: [Boost-commit] svn:boost r85612 - in trunk: boost/container/detail libs/container/doc libs/container/test
From: igaztanaga_at_[hidden]
Date: 2013-09-08 14:58:21
Author: igaztanaga
Date: 2013-09-08 14:58:21 EDT (Sun, 08 Sep 2013)
New Revision: 85612
URL: http://svn.boost.org/trac/boost/changeset/85612
Log:
Fixes #9092
Text files modified:
trunk/boost/container/detail/flat_tree.hpp | 146 ++++++++++++++-------------------------
trunk/libs/container/doc/container.qbk | 1
trunk/libs/container/test/expand_bwd_test_template.hpp | 1
trunk/libs/container/test/flat_tree_test.cpp | 73 --------------------
4 files changed, 54 insertions(+), 167 deletions(-)
Modified: trunk/boost/container/detail/flat_tree.hpp
==============================================================================
--- trunk/boost/container/detail/flat_tree.hpp Sun Sep 8 14:45:41 2013 (r85611)
+++ trunk/boost/container/detail/flat_tree.hpp 2013-09-08 14:58:21 EDT (Sun, 08 Sep 2013) (r85612)
@@ -323,21 +323,21 @@
// 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 = this->priv_insert_unique_prepare(val, data);
- if(ret.second){
- ret.first = this->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 = this->priv_insert_unique_prepare(val, data);
- if(ret.second){
- ret.first = this->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;
}
@@ -357,22 +357,20 @@
iterator insert_unique(const_iterator pos, const value_type& val)
{
+ std::pair<iterator,bool> ret;
insert_commit_data data;
- std::pair<iterator,bool> ret = this->priv_insert_unique_prepare(pos, val, data);
- if(ret.second){
- ret.first = this->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 = this->priv_insert_unique_prepare(pos, mval, data);
- if(ret.second){
- ret.first = this->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)
@@ -553,13 +551,7 @@
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 =
- this->priv_insert_unique_prepare(val, data);
- if(ret.second){
- ret.first = this->priv_insert_commit(data, boost::move(val));
- }
- return ret;
+ return this->insert_unique(::boost::move(val));
}
template <class... Args>
@@ -570,12 +562,7 @@
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 = this->priv_insert_unique_prepare(hint, val, data);
- if(ret.second){
- ret.first = this->priv_insert_commit(data, boost::move(val));
- }
- return ret.first;
+ return this->insert_unique(hint, ::boost::move(val));
}
template <class... Args>
@@ -586,9 +573,7 @@
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>
@@ -599,10 +584,7 @@
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 = this->priv_insert_commit(data, boost::move(val));
- return i;
+ return this->insert_equal(hint, ::boost::move(val));
}
#else //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
@@ -618,12 +600,7 @@
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 = this->priv_insert_unique_prepare(val, data); \
- if(ret.second){ \
- ret.first = this->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, >) \
@@ -635,13 +612,8 @@
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 = this->priv_insert_unique_prepare(hint, val, data); \
- if(ret.second){ \
- ret.first = this->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, >) \
@@ -653,9 +625,7 @@
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, >) \
@@ -668,12 +638,8 @@
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 = this->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()
@@ -798,21 +764,19 @@
}
}
- std::pair<iterator,bool> priv_insert_unique_prepare
+ 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(b, e, KeyOfValue()(val));
- return std::pair<iterator,bool>
- ( iterator(vector_iterator_get_ptr(commit_data.position))
- , commit_data.position == e || value_comp(val, *commit_data.position));
+ return commit_data.position == e || value_comp(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 this->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!
@@ -827,37 +791,33 @@
//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>(iterator(vector_iterator_get_ptr(pos)), true);
- }
- else{
- return std::pair<iterator,bool>(iterator(vector_iterator_get_ptr(pos)), false);
- }
+ const const_iterator cend_it = this->cend();
+ if(pos == cend_it || value_comp(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(value_comp(*prev, val)){ //If previous element was less, then it should go between prev and pos
+ return true;
+ }
+ else if(!value_comp(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);
}
+ //return priv_insert_unique_prepare(val, commit_data);
}
template<class Convertible>
Modified: trunk/libs/container/doc/container.qbk
==============================================================================
--- trunk/libs/container/doc/container.qbk Sun Sep 8 14:45:41 2013 (r85611)
+++ trunk/libs/container/doc/container.qbk 2013-09-08 14:58:21 EDT (Sun, 08 Sep 2013) (r85612)
@@ -722,6 +722,7 @@
[@https://svn.boost.org/trac/boost/ticket/8473 #8473],
[@https://svn.boost.org/trac/boost/ticket/8892 #8892],
[@https://svn.boost.org/trac/boost/ticket/9064 #9064].
+ [@https://svn.boost.org/trac/boost/ticket/9092 #9092].
[endsect]
Modified: trunk/libs/container/test/expand_bwd_test_template.hpp
==============================================================================
--- trunk/libs/container/test/expand_bwd_test_template.hpp Sun Sep 8 14:45:41 2013 (r85611)
+++ trunk/libs/container/test/expand_bwd_test_template.hpp 2013-09-08 14:58:21 EDT (Sun, 08 Sep 2013) (r85612)
@@ -183,7 +183,6 @@
{
typedef typename VectorWithExpandBwdAllocator::value_type value_type;
typedef typename boost::remove_volatile<value_type>::type non_volatile_value_type;
- typedef std::vector<non_volatile_value_type> Vect;
const int MemorySize = 200;
const int Offset[] = { 50, 50, 50};
Modified: trunk/libs/container/test/flat_tree_test.cpp
==============================================================================
--- trunk/libs/container/test/flat_tree_test.cpp Sun Sep 8 14:45:41 2013 (r85611)
+++ trunk/libs/container/test/flat_tree_test.cpp 2013-09-08 14:58:21 EDT (Sun, 08 Sep 2013) (r85612)
@@ -638,76 +638,3 @@
#include <boost/container/detail/config_end.hpp>
-/*
-#include <boost/container/map.hpp>
-#include <boost/container/flat_map.hpp>
-#include <boost/container/vector.hpp>
-#include <boost/move/utility.hpp>
-#include <iostream>
-
-struct Request
-{
- Request() {};
-
- //Move semantics...
- Request(BOOST_RV_REF(Request) r) : rvals() //Move constructor
- {
- rvals.swap(r.rvals);
- };
-
- Request& operator=(BOOST_RV_REF(Request) r) //Move assignment
- {
- if (this != &r){
- rvals.swap(r.rvals);
- }
- return *this;
- };
-
- // Values I want to be moved, not copied.
- boost::container::vector<int> rvals;
-
- private:
- // Mark this class movable but not copyable
- BOOST_MOVABLE_BUT_NOT_COPYABLE(Request)
-};
-
-typedef boost::container::flat_map<int, Request> Requests;
-//typedef boost::container::map<int, Request> Requests2;
-
-int
-main() {
- Requests req;
- std::pair<Requests::iterator, bool> ret = req.insert( Requests::value_type( 7, Request() ) );
- std::cout << "Insert success for req: " << ret.second << std::endl;
-
- //Requests2 req2;
- //std::pair<Requests::iterator, bool> ret2 = req2.insert( Requests2::value_type( 7, Request() ) );
- //std::cout << "Insert success for req2: " << ret2.second << std::endl;
-
- return 0;
-}
-*/
-/*
-#include <cstdlib>
-#include <iostream>
-#include <boost/container/flat_set.hpp>
-
-using namespace std;
-
-int main(int , char *[])
-{
- double d[] = {0, 0.2, 0.8, 1, 2, 3, 4};
- boost::container::flat_set<double> set;
-
- set.insert(0);
- set.insert(set.end(), 1);
- set.insert(set.end(), 3);
- set.insert(boost::container::ordered_unique_range_t(), d, d + sizeof(d)/sizeof(*d));
- boost::container::flat_set<double>::iterator it(set.begin());
- boost::container::flat_set<double>::iterator const itend(set.end());
- while(it != itend)
- cout << *it++ << endl;
-
- return 0;
-}
-*/
\ No newline at end of file