Make flat containers stable, allow constructing from vector.

base/containers/flat_tree.h

Index: base/containers/flat_tree.h
diff --git a/base/containers/flat_tree.h b/base/containers/flat_tree.h
index 57335d8882b0268fb6d607595b4bec9579f27c55..23642976057a73a8141f726eac649fd43f37c0b9 100644
--- a/base/containers/flat_tree.h
+++ b/base/containers/flat_tree.h
@@ -9,6 +9,37 @@
 #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
@@ -24,7 +55,6 @@ namespace internal {
 //   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>;
 
@@ -71,21 +101,30 @@ class flat_tree {
   // 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();
@@ -97,7 +136,7 @@ class flat_tree {
 
   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);
 
   // --------------------------------------------------------------------------
@@ -276,17 +315,26 @@ class flat_tree {
     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
@@ -325,9 +373,10 @@ 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>
@@ -340,9 +389,19 @@ flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::flat_tree(flat_tree&&) =
 
 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;
@@ -362,7 +421,7 @@ 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;
 }