Index: base/containers/flat_tree.h |
diff --git a/base/containers/flat_tree.h b/base/containers/flat_tree.h |
index 8e85f2377655f954c585be08bea9749edd79240c..bf5ccd28eaec33386f74cc90883bc65ceb785c33 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); |
@@ -603,6 +606,39 @@ auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::insert( |
} |
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(); |
jdoerrie
2017/05/08 14:52:52
Here we could add checks to immediately return if
|
+ 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()); |
+ }); |
+ |
+ // The new elements might be unordered and contain duplicates, so post-process |
+ // the just inserted elements. |
+ iterator prev_end = std::next(begin(), prev_size); |
+ std::stable_sort(prev_end, end(), value_comp()); |
+ erase(std::unique(prev_end, 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()); |
+ |
+ // Merge the old and new elements, do a binary search for the first inversion. |
+ if (prev_end != end()) { |
+ std::inplace_merge( |
+ std::lower_bound(begin(), prev_end, *prev_end, value_comp()), prev_end, |
jdoerrie
2017/05/08 14:52:52
Here I'm assuming standard library implementations
jdoerrie
2017/05/08 23:11:43
I ended up implementing the extra check for sorted
|
+ 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) |
-> std::pair<iterator, bool> { |