Index: base/containers/flat_tree.h |
diff --git a/base/containers/flat_tree.h b/base/containers/flat_tree.h |
index 8e85f2377655f954c585be08bea9749edd79240c..2537731a768c35d3512d523f16ef7bf72bb9e616 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; |
} |
@@ -556,7 +575,8 @@ auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::crend() const |
template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::insert( |
const value_type& val) -> std::pair<iterator, bool> { |
- auto position = lower_bound(val); |
+ GetKeyFromValue extractor; |
+ auto position = lower_bound(extractor(val)); |
if (position == end() || impl_.get_value_comp()(val, *position)) |
return {impl_.body_.insert(position, val), true}; |
@@ -602,6 +622,86 @@ 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; |
+ |
+ if (insert_inplace) { |
dyaroshev
2017/05/12 22:10:03
Maybe factor this piece out? Function seems quite
jdoerrie
2017/05/17 06:41:15
Done.
|
+ if (overwrite_existing) { |
+ std::for_each(first, last, [this](const value_type& val) { |
dyaroshev
2017/05/12 22:10:03
This won't work for move only types, and you will
jdoerrie
2017/05/17 06:41:16
Done.
|
+ std::pair<iterator, bool> result = insert(val); |
+ if (!result.second) |
+ *result.first = val; |
+ }); |
+ } else { |
+ std::copy(first, last, std::inserter(*this, end())); |
jdoerrie
2017/05/17 06:41:16
I dropped the call to copy in favor of an explicit
dyaroshev
2017/05/17 10:15:19
Nah, it assigns the iterator. Smth like:
pos = con
jdoerrie
2017/05/17 11:32:05
You are right, my bad. Here's libc++'s implementat
|
+ } |
+ |
+ return; |
+ } |
+ |
+ // For batch updates initialize the first insertion point. |
+ const size_type original_size = size(); |
+ difference_type pos_first_new = original_size; |
jdoerrie
2017/05/17 06:41:15
I dropped this optimization, because it would have
dyaroshev
2017/05/17 10:15:19
I think that inserting small ranges is actually an
jdoerrie
2017/05/17 11:32:05
Acknowledged.
|
+ |
+ // Lambda that tries to find |val| in the sorted range [first, last). If |val| |
+ // is not present, it is appened to the underlying body while potentially |
+ // updating |pos_first_new|. |
+ // It returns an iterator and bool pair with the same semantics as |insert|'s |
+ // return value. |
+ auto append_new = [this, &pos_first_new](iterator first, iterator last, |
+ const value_type& val) { |
dyaroshev
2017/05/12 22:10:03
Again, move is problematic. If you take the push_b
jdoerrie
2017/05/17 06:41:15
Done.
|
+ iterator lower = std::lower_bound(first, last, val, value_comp()); |
+ if (lower == last || value_comp()(val, *lower)) { |
+ pos_first_new = std::min(pos_first_new, std::distance(begin(), lower)); |
+ impl_.body_.push_back(val); |
+ return std::make_pair(std::prev(end()), true); |
+ } |
+ |
+ return std::make_pair(lower, false); |
+ }; |
+ |
+ // Provide a convenience lambda to obtain an iterator pointing past the last |
+ // old element. This needs to be dymanic due to possible re-allocations. |
+ auto middle = [this, original_size]() { |
+ return std::next(begin(), original_size); |
+ }; |
+ |
+ // Loop over the input range and append and track new values. Use the returned |
+ // iterator to overwrite existing values if applicable. |
+ if (overwrite_existing) { |
+ std::for_each( |
+ first, last, [this, append_new, middle](const value_type& val) { |
+ std::pair<iterator, bool> result = append_new(begin(), middle(), val); |
+ if (!result.second) |
+ *result.first = val; |
+ }); |
+ } else { |
+ std::for_each(first, last, |
+ [this, append_new, middle](const value_type& val) { |
+ append_new(begin(), middle(), val); |
+ }); |
+ } |
+ |
+ // 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) |