Make flat containers stable, allow constructing from vector.

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>
 
 namespace base {
+
+enum FlatContainerDupes {
+  KEEP_FIRST_OF_DUPES,
+  KEEP_LAST_OF_DUPES,
+};
+
+// 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) {

[danakj, 2017/04/05 21:33:43]

Maybe this belongs in stl_util.h? Or somewhere.. but I don't think in
flat_tree.h

[brettw, 2017/04/07 21:59:04]

I started by writing this in a separate file (I think stl_util is too generic)
but I couldn't imagine when this would be used outside of this context. In the
interest of not cluttering up the common places with an algorithm that will
probably never be re-used, I just put it as an internal implementation detail of
flat_tree.

[danakj, 2017/04/07 22:02:53]

I think it should be in base::internal if you want it to be an implementation
detail. 

[brettw, 2017/04/07 22:13:37]

Oh, I meant to do that actually. Thanks.

+  if (first == last)

[danakj, 2017/04/05 21:33:43]

Curious why you wrote your own LastUnique instead of using reverse iterators and
std::unique?

[dyaroshev, 2017/04/06 09:45:18]

It moves elements in the wrong direction - you'll get elements collected in the
beginning of the vector.

PS: I still think this algorithm can be implemented better.

+    return last;
+
+  Iterator dest = first;
+  Iterator cur = first;
+  Iterator prev = cur;
+  while (++cur != last) {
+    if (!compare(*prev, *cur)) {
+      // Non-identical one.
+      if (dest != prev)
+        *dest = std::move(*prev);
+      ++dest;
+    }
+    prev = cur;
+  }
+
+  if (dest != prev)
+    *dest = std::move(*prev);
+  return ++dest;
+}
+
 namespace internal {
 
 // Implementation of a sorted vector for backing flat_set and flat_map. Do not
 // use directly.
 //
 // The use of "value" in this is like std::map uses, meaning it's the thing
 // contained (in the case of map it's a <Kay, Mapped> pair). The Key is how
 // things are looked up. In the case of a set, Key == Value. In the case of
 // a map, the Key is a component of a Value.
 //
 // The helper class GetKeyFromValue provides the means to extract a key from a
 // value for comparison purposes. It should implement:
 //   const Key& operator()(const Value&).
 template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
 class flat_tree {
- public:
  private:
   using underlying_type = std::vector<Value>;
 
  public:
   // --------------------------------------------------------------------------
   // Types.
   //
   using key_type = Key;
   using key_compare = KeyCompare;
   using value_type = Value;
@@ skipping 26 matching lines @@
       typename underlying_type::const_reverse_iterator;
 
   // --------------------------------------------------------------------------
   // Lifetime.
   //
   // Constructors that take range guarantee O(N * log^2(N)) + O(N) complexity
   // and take O(N * log(N)) + O(N) if extra memory is available (N is a range
   // length).
   //
   // Assume that move constructors invalidate iterators and references.
+  //
+  // The constructors that take ranges, lists, and vectors do not require that
+  // the input be sorted. If there are duplcates, the first one in the input

[danakj, 2017/04/05 21:33:43]

Same as from map, the first is kept part seems wrong?

[brettw, 2017/04/07 21:59:04]

Done.

+  // will be selected.
 
   flat_tree();
   explicit flat_tree(const key_compare& comp);
 
-  // Not stable in the presence of duplicates in the initializer list.
   template <class InputIterator>
   flat_tree(InputIterator first,
             InputIterator last,
+            FlatContainerDupes dupe_handling,
             const key_compare& comp = key_compare());
 
   flat_tree(const flat_tree&);
   flat_tree(flat_tree&&);
 
-  // Not stable in the presence of duplicates in the initializer list.
+  flat_tree(std::vector<value_type> items,
+            FlatContainerDupes dupe_handling,
+            const key_compare& comp = key_compare());
+
+  // Takes the first if there are duplicates in the initializer list.
   flat_tree(std::initializer_list<value_type> ilist,
+            FlatContainerDupes dupe_handling,
             const key_compare& comp = key_compare());
 
   ~flat_tree();
 
   // --------------------------------------------------------------------------
   // Assignments.
   //
   // Assume that move assignment invalidates iterators and references.
 
   flat_tree& operator=(const flat_tree&);
   flat_tree& operator=(flat_tree&&);
-  // Not stable in the presence of duplicates in the initializer list.
+  // Takes the first if there are duplicates in the initializer list.
   flat_tree& operator=(std::initializer_list<value_type> ilist);
 
   // --------------------------------------------------------------------------
   // Memory management.
   //
   // Beware that shrink_to_fit() simply forwards the request to the
   // underlying_type and its implementation is free to optimize otherwise and
   // leave capacity() to be greater that its size.
   //
   // reserve() and shrink_to_fit() invalidate iterators and references.
@@ skipping 158 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() {
-    // std::set sorts elements preserving stability because it doesn't have any
-    // performance wins in not doing that. We do, so we use an unstable sort.
-    std::sort(begin(), end(), impl_.get_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 !impl_.get_value_comp()(lhs, rhs);
-                      }),
-          end());
+  void sort_and_unique(FlatContainerDupes dupes) {
+    // We need to preserve stability here and take only the first element.

[danakj, 2017/04/05 21:33:43]

"first element" isn't always correct, right?

[brettw, 2017/04/07 21:59:04]

Done.

+    std::stable_sort(begin(), 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);
+    };
+
+    iterator erase_after;
+    switch (dupes) {
+      case KEEP_FIRST_OF_DUPES:
+        erase_after = std::unique(begin(), end(), comparator);
+        break;
+      case KEEP_LAST_OF_DUPES:
+        erase_after = LastUnique(begin(), end(), comparator);
+        break;
+    }
+    erase(erase_after, end());
   }
 
   // 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 18 matching lines @@
 template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
 flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::flat_tree(
     const KeyCompare& comp)
     : 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();
+  sort_and_unique(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);
+}
+
+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), 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();
+  sort_and_unique(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 332 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_