base: Add bulk insert to flat_tree.

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 166 matching lines @@
   const_reverse_iterator crbegin() const;
 
   reverse_iterator rend();
   const_reverse_iterator rend() const;
   const_reverse_iterator crend() const;
 
   // --------------------------------------------------------------------------
   // 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.
+  // 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.
 
   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);
+
   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 383 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>
+void flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::insert(
+    InputIterator first,
+    InputIterator last) {
+  // Insert the values at the end.
+  auto size = impl_.body_.size();
+  impl_.body_.insert(end(), first, last);
+  auto mid = begin() + size;
+
+  // Sort the newly inserted elements.
+  std::stable_sort(mid, end(), impl_.get_value_comp());
+
+  // Merge the two sublists and unique them.
+  std::inplace_merge(begin(), mid, end(), impl_.get_value_comp());
+  auto comparator = [this](const value_type& lhs, const value_type& rhs) {
+    // lhs is already <= rhs due to sort, therefore
+    // !(lhs < rhs) <=> lhs == rhs.
+    return !impl_.get_value_comp()(lhs, rhs);
+  };
+  auto erase_after = std::unique(begin(), end(), comparator);
+  erase(erase_after, end());
+}
+
+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_