Index: base/containers/flat_tree.h |
diff --git a/base/containers/flat_tree.h b/base/containers/flat_tree.h |
index 8e85f2377655f954c585be08bea9749edd79240c..78e0cb747be81b50e6fd90b73608012164598b9a 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,11 @@ 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, |
brettw
2017/05/10 16:52:06
Can you add a comment here about FlatContainerDupe
jdoerrie
2017/05/11 06:34:57
Done.
|
+ InputIterator last, |
+ FlatContainerDupes dupes); |
+ |
template <class... Args> |
std::pair<iterator, bool> emplace(Args&&... args); |
@@ -316,9 +321,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 +336,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 +384,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 +401,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 +429,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 +609,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, |
+ FlatContainerDupes dupes) -> void { |
+ // Initialize the first insertion point and provide a convenience lambda to |
+ // obtain an iterator pointing past the old element. This needs to be dymanic |
+ // due to possible re-allocations. |
+ difference_type pos_first_new = std::distance(begin(), end()); |
dyaroshev
2017/05/10 17:12:09
Nit:
Just say size()? Or are there problems with d
jdoerrie
2017/05/11 06:34:57
Done both now. There usually is a difference, diff
|
+ auto middle = [this, pos_first_new]() { |
+ return std::next(begin(), pos_first_new); |
+ }; |
dyaroshev
2017/05/10 17:12:09
How do you feel about reserve if we can compute di
jdoerrie
2017/05/11 06:34:57
I don't like using reserve, because it can lead to
dyaroshev
2017/05/11 09:46:43
That's a good point.
|
+ |
+ for (; first != last; ++first) { |
+ iterator lower = std::lower_bound(begin(), middle(), *first, value_comp()); |
+ if (lower == middle() || value_comp()(*first, *lower)) { |
+ // Insert completely new elements at the back. |
+ pos_first_new = std::min(pos_first_new, std::distance(begin(), lower)); |
+ impl_.body_.push_back(*first); |
+ } else if (lower != middle() && dupes == KEEP_LAST_OF_DUPES) { |
dyaroshev
2017/05/10 17:12:09
1 - The check for (dupes == KEEP_LAST_OF_DUPES) sh
jdoerrie
2017/05/11 06:34:57
Done.
|
+ // Only overwrite existing elements in case of KEEP_LAST_OF_DUPES. |
+ *lower = *first; |
+ } |
+ } |
+ |
+ // 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()); |
dyaroshev
2017/05/10 17:12:09
Have you measured? Are you closer now to inserting
jdoerrie
2017/05/11 06:34:57
See above.
|
+} |
+ |
template <class Key, class Value, class GetKeyFromValue, class KeyCompare> |
template <class... Args> |
auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::emplace(Args&&... args) |