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..9aa88ce2419ac8607569738fb3e3e83cb9da6c71 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);
 
@@ -602,6 +605,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) -> 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());
+               });

[dyaroshev, 2017/05/09 01:38:49]

You are doing binary search for the first non-unique element twice.
Save the result.
When you do - please split into find_if and copy_if, so you do not do
unnecessary if checks for remaining elements, they seem to be expensive.

[dyaroshev, 2017/05/09 11:31:42]

I thought about it a bit - you would have to find new minimal element and cache
binary search for it, not the first guy in new elements.

[jdoerrie, 2017/05/09 17:03:30]

Yeah, I gave this some though as well. Given that the vector might reallocate
during insertion, we would need to cache the index instead of an iterator to the
first insertion point and use that later. It's doable, but it makes the code a
bit more ugly. What do you think?

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

I think, that this binary search might be why you are noticably slower than
insert(value_type). It's base - I say - worth it.

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

Done.

+
+  // The new elements might be unordered and contain duplicates, so post-process
+  // the just inserted elements.
+  iterator middle = std::next(begin(), prev_size);
+  std::stable_sort(middle, end(), value_comp());
+  erase(std::unique(middle, 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());

[dyaroshev, 2017/05/09 01:38:49]

Just add begin/end to sort_and_unque method?

[jdoerrie, 2017/05/09 17:03:30]

Done.

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

[dyaroshev, 2017/05/09 01:52:50]

!value_comp()(*std::prev(middle), *middle)) <==> lower_bound == middle.
For an empty range standard library should shortcut efficiently.

[jdoerrie, 2017/05/09 17:03:30]

That is true, however an advantage with the current implementation is that it
also skips the binary search when its not necessary. This can result in a
speed-up of about 25% for doing single element range inserts in ascending order:

Number of Items: 1048576    Method: Without Check=  121599 us
Number of Items: 1048576    Method: With Check=      94437 us

Number of Items: 2097152    Method: Without Check=  242699 us
Number of Items: 2097152    Method: With Check=     152297 us

Number of Items: 4194304    Method: Without Check=  385009 us
Number of Items: 4194304    Method: With Check=     293204 us

Number of Items: 8388608    Method: Without Check=  788019 us
Number of Items: 8388608    Method: With Check=     609145 us

Number of Items: 16777216   Method: Without Check= 1628433 us
Number of Items: 16777216   Method: With Check=    1240901 us

Number of Items: 33554432   Method: Without Check= 3341725 us
Number of Items: 33554432   Method: With Check=    2590313 us

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

Is it your binary search or is it the one in inplace_merge? If it yours, caching
it would help. I'm all for caching.

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

Yeah, this was my binary search. I think (buffered) inplace_merge can't do
binary search because of the at most n-1 comparisons requirement. In the worst
case binary search does not help at all and you have to do N - 1 + O(log N)
comparisons.

I did implement the caching solution in the new patch set, however.

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