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>
 
 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)
+  Iterator replacable = std::adjacent_find(first, last, compare);
+
+  if (replacable == last)
     return last;

[brettw, 2017/04/26 21:48:51]

Can you append to this line "No duplicate elements found."

 
-  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;
-  }
+  first = std::next(replacable);
 
-  if (dest != prev)
-    *dest = std::move(*prev);
-  return ++dest;
+  if (first == last)
+    return replacable;
+
+  // adjacent_find will force us to use BidirectionalIterator.

[brettw, 2017/04/26 21:48:51]

This comment is confusing by itself here. I think you mean "...so do the search
manually instead." Can you add something like that? Otherwise it seems like the
comment might be explaining why you're calling adjacent_find. If this isn't what
you mean, can you expand on this comment a bit more (or delete it)?

[dyaroshev, 2017/04/27 19:11:46]

I've done smth. Looks better?

+  // to get the previous element.
+  for (Iterator next = std::next(first); next != last; ++next, ++first)

[brettw, 2017/04/26 21:48:51]

This should have {} by our style guide (# lines is > 1).

[dyaroshev, 2017/04/27 19:11:46]

Done.

+    if (!compare(*first, *next))
+      *replacable++ = std::move(*first);
+
+  // last element should be copied unconditionally.

[brettw, 2017/04/26 21:48:51]

Minor nit: capital letter @ beginning.

[dyaroshev, 2017/04/27 19:11:46]

Done.

+  *replacable++ = std::move(*first);
+  return replacable;
 }
 
 // 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.
 //
@@ skipping 712 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_