Add range insertion for base::flat_tree

base/containers/flat_tree.h

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 for example:
https://codereview.chromium.org/2807933002/
It gains up to two times speed up by removing the if statement in the middle of
the loop.

What I suggest is some form of:

```
if (insert_inplace) {
  std::copy(first, last, std::inserter(*this, end());
}
if (overwrite_existing) {
  // replace_or_pushback
} else {
  std::copy_if(first, last, ...);
}
```

Branches in the middle of the loop cause problems. Other than that I'm good.

[jdoerrie, 2017/05/12 21:03:16]

Thanks for the clarification. I tried my best to remove branches within loops
while still keeping code duplication to a minimum. The performance is still very
good, please let me know what you think.

+
+  // 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)