Flat Tree Perftest

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..d265d07230a857e242399d61b4bbe14f7a92a329 100644
--- a/base/containers/flat_tree.h
+++ b/base/containers/flat_tree.h
@@ -8,6 +8,8 @@
 #include <algorithm>
 #include <vector>
 
+#include "base/memory/ptr_util.h"
+
 namespace base {
 
 enum FlatContainerDupes {
@@ -15,6 +17,13 @@ enum FlatContainerDupes {
   KEEP_LAST_OF_DUPES,
 };
 
+enum RangeInsertMethod {
+  ONE_BY_ONE,
+  STABLE_SORT_ALL,
+  STABLE_SORT_SMART,
+  STABLE_SORT_SMARTER,
+};
+
 namespace internal {
 
 // This algorithm is like unique() from the standard library except it
@@ -200,6 +209,11 @@ 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,
+              RangeInsertMethod method);
+
   template <class... Args>
   std::pair<iterator, bool> emplace(Args&&... args);
 
@@ -556,7 +570,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};
@@ -603,6 +618,67 @@ 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,
+    RangeInsertMethod method) -> void {
+  switch (method) {
+    case ONE_BY_ONE:
+      for (; first != last; ++first) {
+        insert(*first);
+      }
+      return;
+
+    case STABLE_SORT_ALL:
+      impl_.body_.insert(impl_.body_.end(), first, last);
+      sort_and_unique(KEEP_FIRST_OF_DUPES);
+      return;
+
+    case STABLE_SORT_SMART: {
+      const size_type prev_size = size();
+      impl_.body_.insert(impl_.body_.end(), first, last);
+      std::stable_sort(std::next(begin(), prev_size), end(), value_comp());
+      std::inplace_merge(begin(), std::next(begin(), prev_size), end(),
+                         value_comp());
+      erase(std::unique(begin(), 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());
+    }
+
+    case STABLE_SORT_SMARTER: {
+      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());
+                   });
+
+      iterator prev_end = 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());
+
+      if (prev_end != end()) {
+        std::inplace_merge(
+            std::lower_bound(begin(), prev_end, *prev_end, value_comp()),
+            prev_end, 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> {