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..bf5ccd28eaec33386f74cc90883bc65ceb785c33 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);
+
   template <class... Args>
   std::pair<iterator, bool> emplace(Args&&... args);
 
@@ -603,6 +606,39 @@ auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::insert(
 }
 
 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();

[jdoerrie, 2017/05/08 14:52:52]

Here we could add checks to immediately return if first == last or to dispatch
to single element insert when std::next(first) == last.

I did not do this, because in the current implementation all operations are
no-ops if first == last and explicitly checking if std::next(first) == last
breaks this algorithm for InputIterators (strictly speaking, the optimization
would only work for ForwardIterators).

This is also one of the reasons why I did not add a call to reserve here. This
also would break for ForwardIterators and could potentially lead to very bad
performance if insert(Iter, Iter) and thus reserve() would be called in a loop.

+  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 prev_end = std::next(begin(), prev_size);
+  std::stable_sort(prev_end, end(), value_comp());
+  erase(std::unique(prev_end, end(),
+                    [this](const value_type& lhs, const value_type& rhs) {
+                      // lhs is already <= rhs due to sort, therefore
+                      // !(lhs < rhs) <=> lhs == rhs.
+                      return !value_comp()(lhs, rhs);
+                    }),
+        end());
+
+  // Merge the old and new elements, do a binary search for the first inversion.
+  if (prev_end != end()) {
+    std::inplace_merge(
+        std::lower_bound(begin(), prev_end, *prev_end, value_comp()), prev_end,

[jdoerrie, 2017/05/08 14:52:52]

Here I'm assuming standard library implementations are smart enough to simply
return immediately when lower_bound() == prev_end. We could add explicit checks
for this, and also add a O(1) check to skip the binary search when it's clearly
not necessary (i.e. when the whole range is already sorted). In this version I
decided against it, because I wanted to keep explicit checks to a minimum and
just make the algorithm as fast as possible for the general case. What is your
opinion here?

[jdoerrie, 2017/05/08 23:11:43]

I ended up implementing the extra check for sorted-ness, because I realized I
could do it in the same if condition and it removes the need to hope library
implementations are doing the optimization.

+        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)
     -> std::pair<iterator, bool> {