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..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 big? (Do not insist)

[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 invoke copy even for
move_iterators.
Sinse we don't have generic lambdas and you need perfect forwarding, I don't
think it's possible to use a lambda here.

[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 loop, because copy can be
unsafe if std::distance(first, last) >= 2. Since end() is only evaluated once,
it will be invalidated should the first inserted element trigger a reallocation.
For the second element we then would try to dereference an invalid iterator.

[dyaroshev, 2017/05/17 10:15:19]

Nah, it assigns the iterator. Smth like:
pos = container.insert(pos, val);

[jdoerrie, 2017/05/17 11:32:05]

You are right, my bad. Here's libc++'s implementation:
https://github.com/llvm-mirror/libcxx/blob/master/include/iterator#L852-L857

When initially looking this up I missed the assignment and only saw ++iter.

+    }
+
+    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 made the interface of
append_* more awkward. Furthermore, the reason for this optimization was mainly
efficiency for small ranges, however given that we do insertion inplace in this
case it is no longer critical.

Getting rid of it makes the code cleaner and has to measurable performance
implication for bigger ranges.

[dyaroshev, 2017/05/17 10:15:19]

I think that inserting small ranges is actually an important use case.

[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_back out of here - you won't
need it.

[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)