Flat Tree Perftest

base/containers/flat_tree.h

 // Copyright 2017 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #ifndef BASE_CONTAINERS_FLAT_TREE_H_
 #define BASE_CONTAINERS_FLAT_TREE_H_
 
 #include <algorithm>
 #include <vector>
 
+#include "base/memory/ptr_util.h"
+
 namespace base {
 
 enum FlatContainerDupes {
   KEEP_FIRST_OF_DUPES,
   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
 // selects only the last of consecutive values instead of the first.
 template <class Iterator, class BinaryPredicate>
 Iterator LastUnique(Iterator first, Iterator last, BinaryPredicate compare) {
   Iterator replacable = std::adjacent_find(first, last, compare);
 
   // No duplicate elements found.
   if (replacable == last)
@@ skipping 165 matching lines @@
   //
   // NOTE: Prefer to build a new flat_tree from a std::vector (or similar)
   // instead of calling insert() repeatedly.
 
   std::pair<iterator, bool> insert(const value_type& val);
   std::pair<iterator, bool> insert(value_type&& val);
 
   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);
 
   template <class... Args>
   iterator emplace_hint(const_iterator position_hint, Args&&... args);
 
   // --------------------------------------------------------------------------
   // Erase operations.
   //
   // Assume that every operation invalidates iterators and references.
@@ skipping 336 matching lines @@
 //
 // Currently we use position_hint the same way as eastl or boost:
 // https://github.com/electronicarts/EASTL/blob/master/include/EASTL/vector_set.h#L493
 //
 // We duplicate code between copy and move version so that we can avoid
 // creating a temporary value.
 
 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};
 
   return {position, false};
 }
 
 template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::insert(
     value_type&& val) -> std::pair<iterator, bool> {
@@ skipping 26 matching lines @@
   if (position_hint == end() || impl_.get_value_comp()(val, *position_hint)) {
     if (position_hint == begin() ||
         impl_.get_value_comp()(*(position_hint - 1), val))
       // We have to cast away const because of crbug.com/677044.
       return impl_.body_.insert(const_cast_it(position_hint), std::move(val));
   }
   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,
+    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: {
+      reserve(size() + std::distance(first, last));
+      auto prev_end = end();
+      std::copy_if(first, last, std::back_inserter(impl_.body_),
+                   [this, prev_end](const value_type& val) {
+                     return !std::binary_search(begin(), prev_end, val,
+                                                value_comp());
+                   });
+
+      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 != begin() && prev_end != end() &&
+          !value_comp()(*std::prev(prev_end), *prev_end)) {
+        std::inplace_merge(begin(), 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> {
   return insert(value_type(std::forward<Args>(args)...));
 }
 
 template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
 template <class... Args>
 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::emplace_hint(
     const_iterator position_hint,
@@ skipping 152 matching lines @@
 void EraseIf(base::internal::flat_tree<Key, Value, GetKeyFromValue, KeyCompare>&
                  container,
              Predicate pred) {
   container.erase(std::remove_if(container.begin(), container.end(), pred),
                   container.end());
 }
 
 }  // namespace base
 
 #endif  // BASE_CONTAINERS_FLAT_TREE_H_