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

base/algorithm/sorted_ranges.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_ALGORITHM_SORTED_RANGES_H_
+#define BASE_ALGORITHM_SORTED_RANGES_H_
+
+#include <algorithm>
+#include <functional>
+#include <iterator>
+
+namespace base {
+
+//----------------------------------------------------------------------------
+// UniquePickLast/UniqueCopyPickLast are algorithms modeled after
+// std::unique/std::unique_copy but instead of choosing first equal element in
+// the equal group, they choose last.

[dyaroshev, 2017/04/08 17:03:12]

but they keep the last element in the group of equivalents.

+
+template <typename InputIterator,
+          typename OutputIterator,
+          typename BinaryPredicate>
+OutputIterator UniqueCopyPickLast(InputIterator first,
+                                  InputIterator last,
+                                  OutputIterator out,
+                                  BinaryPredicate pred) {
+  if (first == last)
+    return out;
+
+  // adjacent_find will force us to use BidirectionalIterator.
+  // to get the previous element.
+  for (InputIterator next = std::next(first); next != last; ++next, ++first)
+    if (!pred(*first, *next))
+      *out++ = *first;

[danakj, 2017/04/12 15:54:48]

Wouldn't this preclude the container from holding move-only types?

[dyaroshev, 2017/04/12 16:00:01]

This algorithm should not move elements - it's a copy algorithm (like
std::unique_copy). When we call it and we want to move elements, we ought to use
move_iterators (like in UniquePickLast). So no, it works.

There are tests for move only types (both new and for flat_tree).

+
+  // last element should be copied unconditionally.
+  *out++ = *first;
+
+  return out;
+}
+
+template <typename InputIterator, typename OutputIterator>
+OutputIterator UniqueCopyPickLast(InputIterator first,
+                                  InputIterator last,
+                                  OutputIterator out) {
+  using ValueType = typename std::iterator_traits<InputIterator>::value_type;
+  return UniqueCopyPickLast(first, last, out, std::equal_to<ValueType>{});
+}
+
+template <typename ForwardIterator, typename BinaryPredicate>
+ForwardIterator UniquePickLast(ForwardIterator first,
+                               ForwardIterator last,
+                               BinaryPredicate pred) {
+  ForwardIterator replacable = std::adjacent_find(first, last, pred);
+  return (replacable == last)
+             ? last
+             : UniqueCopyPickLast(
+                   std::next(std::make_move_iterator(replacable)),
+                   std::make_move_iterator(last), replacable, pred);
+}
+
+template <typename ForwardIterator>
+ForwardIterator UniquePickLast(ForwardIterator first, ForwardIterator last) {
+  using ValueType = typename std::iterator_traits<ForwardIterator>::value_type;
+
+  return UniquePickLast(first, last, std::equal_to<ValueType>{});
+}
+
+}  // namespace base
+
+#endif  // BASE_ALGORITHM_SORTED_RANGES_H_