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) {
+  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 {
+  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;
+
+  if (insert_inplace) {

[dyaroshev, 2017/05/12 22:10:03]

Maybe factor this piece out? Function seems quite big? (Do not insist)

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

Done.

+    if (overwrite_existing) {
+      std::for_each(first, last, [this](const value_type& val) {

[dyaroshev, 2017/05/12 22:10:03]

This won't work for move only types, and you will invoke copy even for
move_iterators.
Sinse we don't have generic lambdas and you need perfect forwarding, I don't
think it's possible to use a lambda here.

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

Done.

+        std::pair<iterator, bool> result = insert(val);
+        if (!result.second)
+          *result.first = val;
+      });
+    } else {
+      std::copy(first, last, std::inserter(*this, end()));

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

I dropped the call to copy in favor of an explicit loop, because copy can be
unsafe if std::distance(first, last) >= 2. Since end() is only evaluated once,
it will be invalidated should the first inserted element trigger a reallocation.
For the second element we then would try to dereference an invalid iterator.

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

Nah, it assigns the iterator. Smth like:
pos = container.insert(pos, val);

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

You are right, my bad. Here's libc++'s implementation:
https://github.com/llvm-mirror/libcxx/blob/master/include/iterator#L852-L857

When initially looking this up I missed the assignment and only saw ++iter.

+    }
+
+    return;
+  }
+
+  // For batch updates initialize the first insertion point.
+  const size_type original_size = size();
+  difference_type pos_first_new = original_size;

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

I dropped this optimization, because it would have made the interface of
append_* more awkward. Furthermore, the reason for this optimization was mainly
efficiency for small ranges, however given that we do insertion inplace in this
case it is no longer critical.

Getting rid of it makes the code cleaner and has to measurable performance
implication for bigger ranges.

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

I think that inserting small ranges is actually an important use case.

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

Acknowledged.

+
+  // Lambda that tries to find |val| in the sorted range [first, last). If |val|
+  // is not present, it is appened to the underlying body while potentially
+  // updating |pos_first_new|.
+  // It returns an iterator and bool pair with the same semantics as |insert|'s
+  // return value.
+  auto append_new = [this, &pos_first_new](iterator first, iterator last,
+                                           const value_type& val) {

[dyaroshev, 2017/05/12 22:10:03]

Again, move is problematic. If you take the push_back out of here - you won't
need it.

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

Done.

+    iterator lower = std::lower_bound(first, last, val, value_comp());
+    if (lower == last || value_comp()(val, *lower)) {
+      pos_first_new = std::min(pos_first_new, std::distance(begin(), lower));
+      impl_.body_.push_back(val);
+      return std::make_pair(std::prev(end()), true);
+    }
+
+    return std::make_pair(lower, false);
+  };
+
+  // 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 and append and track new values. Use the returned
+  // iterator to overwrite existing values if applicable.
+  if (overwrite_existing) {
+    std::for_each(
+        first, last, [this, append_new, middle](const value_type& val) {
+          std::pair<iterator, bool> result = append_new(begin(), middle(), val);
+          if (!result.second)
+            *result.first = val;
+        });
+  } else {
+    std::for_each(first, last,
+                  [this, append_new, middle](const value_type& val) {
+                    append_new(begin(), middle(), val);
+                  });
+  }
+
+  // The new elements might be unordered and contain duplicates, so post-process
+  // the just inserted elements and merge them with the rest, inserting them at
+  // the previously found spot.
+  sort_and_unique(middle(), end(), dupes);
+  std::inplace_merge(std::next(begin(), pos_first_new), middle(), 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_