Index: base/containers/flat_tree.h |
diff --git a/base/containers/flat_tree.h b/base/containers/flat_tree.h |
index 8e85f2377655f954c585be08bea9749edd79240c..9aa88ce2419ac8607569738fb3e3e83cb9da6c71 100644 |
--- a/base/containers/flat_tree.h |
+++ b/base/containers/flat_tree.h |
@@ -6,6 +6,7 @@ |
#define BASE_CONTAINERS_FLAT_TREE_H_ |
#include <algorithm> |
+#include <iterator> |
#include <vector> |
namespace base { |
@@ -187,9 +188,8 @@ class flat_tree { |
// Insert operations. |
// |
// Assume that every operation invalidates iterators and references. |
- // Insertion of one element can take O(size). See the Notes section in the |
- // class comments on why we do not currently implement range insertion. |
- // Capacity of flat_tree grows in an implementation-defined manner. |
+ // Insertion of one element can take O(size). Capacity of flat_tree grows in |
+ // an implementation-defined manner. |
// |
// NOTE: Prefer to build a new flat_tree from a std::vector (or similar) |
// instead of calling insert() repeatedly. |
@@ -200,6 +200,9 @@ class flat_tree { |
iterator insert(const_iterator position_hint, const value_type& x); |
iterator insert(const_iterator position_hint, value_type&& x); |
+ template <class InputIterator> |
+ void insert(InputIterator first, InputIterator last); |
+ |
template <class... Args> |
std::pair<iterator, bool> emplace(Args&&... args); |
@@ -602,6 +605,40 @@ auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::insert( |
return insert(std::move(val)).first; |
} |
+template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
+template <class InputIterator> |
+auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::insert( |
+ InputIterator first, |
+ InputIterator last) -> void { |
+ // Only add elements that are not already present. |
+ size_type prev_size = size(); |
+ std::copy_if(first, last, std::back_inserter(impl_.body_), |
+ [this, prev_size](const value_type& val) { |
+ return !std::binary_search( |
+ begin(), std::next(begin(), prev_size), val, value_comp()); |
+ }); |
dyaroshev
2017/05/09 01:38:49
You are doing binary search for the first non-uniq
dyaroshev
2017/05/09 11:31:42
I thought about it a bit - you would have to find
jdoerrie
2017/05/09 17:03:30
Yeah, I gave this some though as well. Given that
dyaroshev
2017/05/09 21:37:19
I think, that this binary search might be why you
jdoerrie
2017/05/10 15:39:18
Done.
|
+ |
+ // The new elements might be unordered and contain duplicates, so post-process |
+ // the just inserted elements. |
+ iterator middle = std::next(begin(), prev_size); |
+ std::stable_sort(middle, end(), value_comp()); |
+ erase(std::unique(middle, end(), |
+ [this](const value_type& lhs, const value_type& rhs) { |
+ // lhs is already <= rhs due to sort, therefore |
+ // !(lhs < rhs) <=> lhs == rhs. |
+ return !value_comp()(lhs, rhs); |
+ }), |
+ end()); |
dyaroshev
2017/05/09 01:38:49
Just add begin/end to sort_and_unque method?
jdoerrie
2017/05/09 17:03:30
Done.
|
+ |
+ // Merge the old and new elements if necessary, do a binary search for the |
+ // first inversion. |
+ if (middle != begin() && middle != end() && |
+ !value_comp()(*std::prev(middle), *middle)) { |
+ std::inplace_merge(std::lower_bound(begin(), middle, *middle, value_comp()), |
dyaroshev
2017/05/09 01:52:50
!value_comp()(*std::prev(middle), *middle)) <==> l
jdoerrie
2017/05/09 17:03:30
That is true, however an advantage with the curren
dyaroshev
2017/05/09 21:37:19
Is it your binary search or is it the one in inpla
jdoerrie
2017/05/10 15:39:18
Yeah, this was my binary search. I think (buffered
|
+ middle, end(), value_comp()); |
+ } |
+} |
+ |
template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
template <class... Args> |
auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::emplace(Args&&... args) |