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..4b748816a75fd026e6ba619e425fc11895b059dc 100644
--- a/base/containers/flat_tree.h
+++ b/base/containers/flat_tree.h
@@ -9,6 +9,38 @@
 #include <vector>
 
 namespace base {
+
+enum FlatContainerDupes {
+  KEEP_FIRST_OF_DUPES,
+  KEEP_LAST_OF_DUPES,
+};

[dyaroshev, 2017/03/31 07:46:52]

I would prefer delegates that do the algorithm.

[dyaroshev, 2017/03/31 13:58:46]

Possible implementation:

https://godbolt.org/g/RddXRt

+
+// 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>
+typename Iterator LastUnique(Iterator first,
+                             Iterator last,
+                             BinaryPredicate compare) {
+  if (first == last)
+    return last;
+
+  InputIterator dest = first;
+  Iterator cur = first;
+  Iterator prev = cur;
+  while (++cur != last) {
+    if (!compare(*prev, *cur) && dest != prev) {
+      // Non-identical one.
+      *dest = std::move(*prev);
+      ++dest;
+    }
+    prev = cur;
+  }
+
+  if (dest != prev)
+    *dest = std::move(*prev);
+  return ++dest;
+}

[dyaroshev, 2017/03/31 13:58:46]

A - this should be defined as std::unique - it uses the negation of compare as a
predicate.

B - this is a generic algorithm - it should be tested individually for different
cases

What about: 1, 2, 2? Will this algorithm works? I'm concerned about  keeping
dest == first until the first !compare.

I don't like dest comparisons - this should be two loops.
Here is my take on it:
https://godbolt.org/g/XQyhHA

+
 namespace internal {
 
 // Implementation of a sorted vector for backing flat_set and flat_map. Do not
@@ -24,7 +56,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 +102,29 @@ 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
+  // 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 = KEEP_FIRST_OF_DUPES,
             const key_compare& comp = key_compare());

[dyaroshev, 2017/03/31 07:46:52]

I think this parametr should go first. And should always be stated explicitly.

 
   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 = KEEP_FIRST_OF_DUPES,
+            const key_compare& comp = key_compare());
+
   flat_tree(std::initializer_list<value_type> ilist,
+            FlatContainerDupes dupe_handling = KEEP_FIRST_OF_DUPES,
             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,29 @@ 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.
+    std::stable_sort(begin(), end(), impl_.get_value_comp());
+    iterator erase_after;
+    switch (dupes) {
+      case KEEP_FIRST_OF_DUPES:
+        erase_after =
+            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);
+                        }) break;
+      case KEEP_LAST_OF_DUPES:
+        erase_after =
+            LastUnique(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);
+                       }) break;
+    }

[dyaroshev, 2017/03/31 07:46:52]

Just do the unique algorithm first.

And, I still think it should be Sorter. And then we call sorter to do sort and
unique for us.

+    erase(erase_after, end());
   }
 
   // To support comparators that may not be possible to default-construct, we
@@ -325,9 +376,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 +392,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;