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

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>
 
+#include "base/algorithm/sorted_ranges.h"
+
 namespace base {
 
 enum FlatContainerDupes {
   KEEP_FIRST_OF_DUPES,
   KEEP_LAST_OF_DUPES,
 };
 
 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.
 //
 // 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:
@@ skipping 267 matching lines @@
       // !(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);
+        erase_after = UniquePickLast(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.
@@ skipping 422 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_