Insertion by one sometimes gives drammatically better results than

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>
 
@@ skipping 182 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 <typename I>
+  void insert_by_one(I first, I last) {
+    std::copy(first, last, std::inserter(*this, end()));
+  }
+
+  template <typename I>
+  void insert_merge(I first, I last) {
+    size_type original_size = size();
+    impl_.body_.insert(end(), first, last);
+    iterator new_elements = begin() + original_size;
+    std::stable_sort(new_elements, end(), value_compare());
+    std::inplace_merge(begin(), new_elements, end());
+    auto comparator = [this](const value_type& lhs, const value_type& rhs) {
+      return !value_comp()(lhs, rhs);
+    };
+    erase(std::unique(begin(), end(), comparator), end());
+  }
+
   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 555 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_