Add range insertion for base::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 <iterator>
 #include <vector>
 
 namespace base {
 
 enum FlatContainerDupes {
   KEEP_FIRST_OF_DUPES,
   KEEP_LAST_OF_DUPES,
 };
 
 namespace internal {
 
+// This is a convenience method returning true if Iterator is at least a
+// ForwardIterator and thus supports multiple passes over a range.
+template <class Iterator>
+constexpr bool is_multipass() {
+  return std::is_base_of<
+      std::forward_iterator_tag,
+      typename std::iterator_traits<Iterator>::iterator_category>::value;
+}
+
 // 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)
     return last;
 
@@ skipping 150 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.
-  // 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.
 
   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);
 
+  // This method inserts the values from the range [first, last) into the
+  // current tree. In case of KEEP_LAST_OF_DUPES newly added elements can
+  // overwrite existing values.
+  template <class InputIterator>
+  void insert(InputIterator first,
+              InputIterator last,
+              FlatContainerDupes dupes);
+
   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 96 matching lines @@
     const key_compare& key_comp_;
   };
 
   const flat_tree& as_const() { return *this; }
 
   iterator const_cast_it(const_iterator c_it) {
     auto distance = std::distance(cbegin(), c_it);
     return std::next(begin(), distance);
   }
 
-  void sort_and_unique(FlatContainerDupes dupes) {
+  // This method is inspired by both std::map::insert(P&&) and
+  // std::map::insert_or_assign(const K&, V&&). It inserts val if an equivalent
+  // element is not present yet, otherwise it overwrites. It returns an iterator
+  // to the modified element and a flag indicating whether insertion or
+  // assignment happened.
+  template <class V>
+  std::pair<iterator, bool> insert_or_assign(V&& val) {
+    auto position = lower_bound(GetKeyFromValue()(val));
+
+    if (position == end() || value_comp()(val, *position))
+      return {impl_.body_.emplace(position, std::forward<V>(val)), true};
+
+    *position = std::forward<V>(val);
+    return {position, false};
+  }
+
+  // This method is similar to insert_or_assign, with the following differences:
+  // - Instead of searching [begin(), end()) it only searches [first, last).
+  // - In case no equivalent element is found, val is appended to the end of the
+  //   underlying body.
+  template <class V>
+  std::pair<iterator, bool> append_or_assign(iterator first,

[dyaroshev, 2017/05/17 10:15:19]

I don't actually believe, that in these methods returning where the element
landed is more useful than returning lower_bound result.
This solves the awkward interface problem for cashing binary search result.

[jdoerrie, 2017/05/17 11:32:05]

Done.

+                                             iterator last,
+                                             V&& val) {
+    auto position = std::lower_bound(first, last, val, value_comp());
+
+    if (position == last || value_comp()(val, *position)) {
+      impl_.body_.emplace_back(std::forward<V>(val));
+      return {std::prev(end()), true};
+    }
+
+    *position = std::forward<V>(val);
+    return {position, false};
+  }
+
+  // This method is similar to insert, with the following differences:
+  // - Instead of searching [begin(), end()) it only searches [first, last).
+  // - In case no equivalent element is found, val is appended to the end of the
+  //   underlying body.
+  template <class V>
+  std::pair<iterator, bool> append_unique(iterator first,
+                                          iterator last,
+                                          V&& val) {
+    auto position = std::lower_bound(first, last, val, value_comp());
+
+    if (position == last || value_comp()(val, *position)) {
+      impl_.body_.emplace_back(std::forward<V>(val));
+      return {std::prev(end()), true};
+    }
+
+    return {position, false};
+  }
+
+  void sort_and_unique(iterator first,
+                       iterator last,
+                       FlatContainerDupes dupes) {
     // Preserve stability for the unique code below.
-    std::stable_sort(begin(), end(), impl_.get_value_comp());
+    std::stable_sort(first, last, 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);
     };
 
     iterator erase_after;
     switch (dupes) {
       case KEEP_FIRST_OF_DUPES:
-        erase_after = std::unique(begin(), end(), comparator);
+        erase_after = std::unique(first, last, comparator);
         break;
       case KEEP_LAST_OF_DUPES:
-        erase_after = LastUnique(begin(), end(), comparator);
+        erase_after = LastUnique(first, last, comparator);
         break;
     }
-    erase(erase_after, end());
+    erase(erase_after, last);
   }
 
   // To support comparators that may not be possible to default-construct, we
   // have to store an instance of Compare. Using this to store all internal
   // state of flat_tree and using private inheritance to store compare lets us
   // take advantage of an empty base class optimization to avoid extra space in
   // the common case when Compare has no state.
   struct Impl : private value_compare {
     Impl() = default;
 
@@ skipping 21 matching lines @@
     : impl_(comp) {}
 
 template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
 template <class InputIterator>
 flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::flat_tree(
     InputIterator first,
     InputIterator last,
     FlatContainerDupes dupe_handling,
     const KeyCompare& comp)
     : impl_(comp, first, last) {
-  sort_and_unique(dupe_handling);
+  sort_and_unique(begin(), end(), dupe_handling);
 }
 
 template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
 flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::flat_tree(
     const flat_tree&) = default;
 
 template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
 flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::flat_tree(flat_tree&&) =
     default;
 
 template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
 flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::flat_tree(
     std::vector<value_type> items,
     FlatContainerDupes dupe_handling,
     const KeyCompare& comp)
     : impl_(comp, std::move(items)) {
-  sort_and_unique(dupe_handling);
+  sort_and_unique(begin(), end(), dupe_handling);
 }
 
 template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
 flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::flat_tree(
     std::initializer_list<value_type> ilist,
     FlatContainerDupes dupe_handling,
     const KeyCompare& comp)
     : flat_tree(std::begin(ilist), std::end(ilist), dupe_handling, comp) {}
 
 template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
 flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::~flat_tree() = default;
 
 // ----------------------------------------------------------------------------
 // Assignments.
 
 template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::operator=(
     const flat_tree&) -> flat_tree& = default;
 
 template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::operator=(flat_tree &&)
     -> flat_tree& = default;
 
 template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::operator=(
     std::initializer_list<value_type> ilist) -> flat_tree& {
   impl_.body_ = ilist;
-  sort_and_unique(KEEP_FIRST_OF_DUPES);
+  sort_and_unique(begin(), end(), KEEP_FIRST_OF_DUPES);
   return *this;
 }
 
 // ----------------------------------------------------------------------------
 // Memory management.
 
 template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
 void flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::reserve(
     size_type new_capacity) {
   impl_.body_.reserve(new_capacity);
@@ skipping 113 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,
+    FlatContainerDupes dupes) -> void {

[dyaroshev, 2017/05/17 10:15:19]

Nit: we just wrote void, cause the type doesn't depend on the flat_tree.

[jdoerrie, 2017/05/17 11:32:05]

Done.

+  if (first == last)
+    return;
+
+  // Cache results whether existing elements should be overwritten and whether
+  // inserting new elements happens immediately or will be done in a batch.
+  const bool overwrite_existing = dupes == KEEP_LAST_OF_DUPES;
+  const bool insert_inplace =
+      is_multipass<InputIterator>() && std::next(first) == last;

[jdoerrie, 2017/05/17 06:41:16]

You were right with your earlier comment that this should be generalized to
std::distance(first, last) <= kSomeThreshold. I did some quick testing and for
me the sweet spot seems to be around 6 elements. However, as you said, this
change should be done in a future CL.

[dyaroshev, 2017/05/17 10:15:19]

I suspect it depends on two numbers: size() and distance(first, last).

[jdoerrie, 2017/05/17 11:32:05]

Acknowledged.

+
+  if (insert_inplace) {
+    if (overwrite_existing) {
+      for (; first != last; ++first)
+        insert_or_assign(*first);
+    } else {
+      for (; first != last; ++first)
+        insert(*first);

[dyaroshev, 2017/05/17 10:15:19]

Nit: std::copy(first, last, std::inserter(*this, end());

I've seen your comment and will explain there.

+    }
+    return;
+  }
+
+  // For batch updates initialize the first insertion point.
+  const size_type original_size = size();
+
+  // Provide a convenience lambda to obtain an iterator pointing past the last
+  // old element. This needs to be dymanic due to possible re-allocations.
+  auto middle = [this, original_size]() {
+    return std::next(begin(), original_size);
+  };
+
+  // Loop over the input range while appending new values and overwriting
+  // existing ones, if applicable.
+  if (overwrite_existing) {
+    for (; first != last; ++first)
+      append_or_assign(begin(), middle(), *first);
+  } else {
+    for (; first != last; ++first)
+      append_unique(begin(), middle(), *first);
+  }
+
+  // The new elements might be unordered and contain duplicates, so post-process
+  // the just inserted elements and merge them with the rest. Binary search for
+  // the first insertion spot.
+  sort_and_unique(middle(), end(), dupes);
+  if (middle() != end()) {
+    std::inplace_merge(
+        std::lower_bound(begin(), middle(), *middle(), value_comp()), middle(),

[dyaroshev, 2017/05/17 10:15:19]

I really think you ought to cache binary search.

[jdoerrie, 2017/05/17 11:32:05]

Done.

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