Index: base/containers/flat_tree.h |
diff --git a/base/containers/flat_tree.h b/base/containers/flat_tree.h |
index 8e85f2377655f954c585be08bea9749edd79240c..adf2701e0b305fefdaaa60badb330a9186096997 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 { |
@@ -17,6 +18,15 @@ enum FlatContainerDupes { |
namespace internal { |
+// This is a convenience method returning true if Iterator is at least a |
+// ForwardIterator and thus supports multiple passes over a range. |
+template <class Iterator> |
+constexpr bool is_multipass() { |
+ return std::is_base_of< |
+ std::forward_iterator_tag, |
+ typename std::iterator_traits<Iterator>::iterator_category>::value; |
+} |
+ |
// This algorithm is like unique() from the standard library except it |
// selects only the last of consecutive values instead of the first. |
template <class Iterator, class BinaryPredicate> |
@@ -187,9 +197,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 +209,14 @@ class flat_tree { |
iterator insert(const_iterator position_hint, const value_type& x); |
iterator insert(const_iterator position_hint, value_type&& x); |
+ // This method inserts the values from the range [first, last) into the |
+ // current tree. In case of KEEP_LAST_OF_DUPES newly added elements can |
+ // overwrite existing values. |
+ template <class InputIterator> |
+ void insert(InputIterator first, |
+ InputIterator last, |
+ FlatContainerDupes dupes); |
+ |
template <class... Args> |
std::pair<iterator, bool> emplace(Args&&... args); |
@@ -316,9 +333,11 @@ class flat_tree { |
return std::next(begin(), distance); |
} |
- void sort_and_unique(FlatContainerDupes dupes) { |
+ void sort_and_unique(iterator first, |
+ iterator last, |
+ FlatContainerDupes dupes) { |
// Preserve stability for the unique code below. |
- std::stable_sort(begin(), end(), impl_.get_value_comp()); |
+ std::stable_sort(first, last, impl_.get_value_comp()); |
auto comparator = [this](const value_type& lhs, const value_type& rhs) { |
// lhs is already <= rhs due to sort, therefore |
@@ -329,13 +348,13 @@ class flat_tree { |
iterator erase_after; |
switch (dupes) { |
case KEEP_FIRST_OF_DUPES: |
- erase_after = std::unique(begin(), end(), comparator); |
+ erase_after = std::unique(first, last, comparator); |
break; |
case KEEP_LAST_OF_DUPES: |
- erase_after = LastUnique(begin(), end(), comparator); |
+ erase_after = LastUnique(first, last, comparator); |
break; |
} |
- erase(erase_after, end()); |
+ erase(erase_after, last); |
} |
// To support comparators that may not be possible to default-construct, we |
@@ -377,7 +396,7 @@ flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::flat_tree( |
FlatContainerDupes dupe_handling, |
const KeyCompare& comp) |
: impl_(comp, first, last) { |
- sort_and_unique(dupe_handling); |
+ sort_and_unique(begin(), end(), dupe_handling); |
} |
template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
@@ -394,7 +413,7 @@ flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::flat_tree( |
FlatContainerDupes dupe_handling, |
const KeyCompare& comp) |
: impl_(comp, std::move(items)) { |
- sort_and_unique(dupe_handling); |
+ sort_and_unique(begin(), end(), dupe_handling); |
} |
template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
@@ -422,7 +441,7 @@ template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::operator=( |
std::initializer_list<value_type> ilist) -> flat_tree& { |
impl_.body_ = ilist; |
- sort_and_unique(KEEP_FIRST_OF_DUPES); |
+ sort_and_unique(begin(), end(), KEEP_FIRST_OF_DUPES); |
return *this; |
} |
@@ -602,6 +621,59 @@ 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, |
+ FlatContainerDupes dupes) -> void { |
+ if (first == last) |
+ return; |
+ |
+ // Cache results whether existing elements should be overwritten and whether |
+ // inserting new elements happens immediately or will be done in a batch. |
+ const bool overwrite_existing = dupes == KEEP_LAST_OF_DUPES; |
+ const bool insert_inplace = |
+ is_multipass<InputIterator>() && std::next(first) == last; |
+ |
+ // For batch updates initialize the first insertion point and provide a |
+ // convenience lambda to obtain an iterator pointing past the last old |
+ // element. This needs to be dymanic due to possible re-allocations. |
+ const size_type original_size = size(); |
+ auto middle = [this, original_size]() { |
+ return std::next(begin(), original_size); |
+ }; |
+ difference_type pos_first_new = original_size; |
+ |
+ // Loop over all elements in the range, inserting new values at the end of the |
+ // tree, while overwriting existing ones in case of KEEP_LAST_OF_DUPES. Keep |
+ // track of the first insertion point for the following merge step. |
+ for (; first != last; ++first) { |
+ iterator lower = std::lower_bound(begin(), middle(), *first, value_comp()); |
+ const bool is_unique = lower == middle() || value_comp()(*first, *lower); |
+ if (is_unique) { |
+ if (insert_inplace) |
+ impl_.body_.insert(lower, *first); |
+ else { |
+ pos_first_new = std::min(pos_first_new, std::distance(begin(), lower)); |
+ impl_.body_.push_back(*first); |
+ } |
+ } else if (overwrite_existing) |
+ *lower = *first; |
+ } |
dyaroshev
2017/05/12 11:23:28
Ok, I seem to fail to explain. Check out this CL f
jdoerrie
2017/05/12 21:03:16
Thanks for the clarification. I tried my best to r
|
+ |
+ // No further processing is necessary to elements inserted inplace. |
+ if (insert_inplace) |
+ return; |
+ |
+ // The new elements might be unordered and contain duplicates, so post-process |
+ // the just inserted elements and merge them with the rest, inserting them at |
+ // the previously found spot. |
+ sort_and_unique(middle(), end(), dupes); |
+ std::inplace_merge(std::next(begin(), pos_first_new), 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) |