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..50e12229186004a29829330afadbdb0c2afdb689 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,9 @@ 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, InputIterator last);

[brettw, 2017/05/09 20:25:45]

I hate diverging from STL, but we've been consistent in the other "range" cases
to specify a FlatContainerDupes parameter. We probably want that here also.

[dyaroshev, 2017/05/09 21:37:19]

I thought about that and I don't see how to do it efficiently (at the very least
right away). It's consistent with insert(value_type) - can we say that it's
consisten enough?

[dyaroshev, 2017/05/09 22:04:05]

I thought about it a bit more - probably we can make it work. Will KEEP_LAST
replace the elements that are already in?

[jdoerrie, 2017/05/10 15:39:18]

Done.

+
   template <class... Args>
   std::pair<iterator, bool> emplace(Args&&... args);
 
@@ -316,9 +319,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 +334,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 +382,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 +399,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 +427,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 +607,33 @@ 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) -> void {
+  // Only add elements that are not already present.
+  size_type prev_size = size();
+  std::copy_if(first, last, std::back_inserter(impl_.body_),
+               [this, prev_size](const value_type& val) {
+                 return !std::binary_search(
+                     begin(), std::next(begin(), prev_size), val, value_comp());
+               });
+
+  // The new elements might be unordered and contain duplicates, so post-process
+  // the just inserted elements.
+  iterator middle = std::next(begin(), prev_size);
+  sort_and_unique(middle, end(), KEEP_FIRST_OF_DUPES);
+
+  // Merge the old and new elements if necessary, do a binary search for the
+  // first inversion.
+  if (middle != begin() && middle != end() &&
+      !value_comp()(*std::prev(middle), *middle)) {
+    std::inplace_merge(std::lower_bound(begin(), middle, *middle, value_comp()),
+                       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)