Removing (dest != prev) check from LastUnique algorithm.

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 c3a234fa784c4f0e0e151d9711d0265b756473fd..e462b1688335dab8c5a00191831b6f728242c289 100644
--- a/base/containers/flat_tree.h
+++ b/base/containers/flat_tree.h
@@ -8,6 +8,8 @@
 #include <algorithm>
 #include <vector>
 
+#include "base/algorithm/sorted_ranges.h"
+
 namespace base {
 
 enum FlatContainerDupes {
@@ -17,31 +19,6 @@ enum FlatContainerDupes {
 
 namespace internal {
 
-// 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) {
-  if (first == last)
-    return last;
-
-  Iterator dest = first;
-  Iterator cur = first;
-  Iterator prev = cur;
-  while (++cur != last) {
-    if (!compare(*prev, *cur)) {
-      // Non-identical one.
-      if (dest != prev)

[dyaroshev, 2017/04/08 16:48:03]

I suspect, that the main reason why this way is slower is because of this check.
It makes sense only once: when you find first element to remove an we do it on
every iteration of the loop.
When we split this in two loops: before & after first element to remove - this
check goes away.

Branches are somewhat expensive (in very hot loops).

-        *dest = std::move(*prev);
-      ++dest;
-    }
-    prev = cur;
-  }
-
-  if (dest != prev)
-    *dest = std::move(*prev);
-  return ++dest;
-}
-
 // Implementation of a sorted vector for backing flat_set and flat_map. Do not
 // use directly.
 //
@@ -329,7 +306,7 @@ class flat_tree {
         erase_after = std::unique(begin(), end(), comparator);
         break;
       case KEEP_LAST_OF_DUPES:
-        erase_after = LastUnique(begin(), end(), comparator);
+        erase_after = UniquePickLast(begin(), end(), comparator);
         break;
     }
     erase(erase_after, end());