From bf1e73305ac1b6bc9021b80fc8da99fda032c018 Mon Sep 17 00:00:00 2001
From: Artur Ryt <artur.ryt@gmail.com>
Date: Sun, 3 Mar 2019 14:19:18 +0100
Subject: cmAlgorithms: Refactor cmRemoveDuplicates

Use an iterator-based implementation with range-based one simply
deferring to it.

Also optimize a little by storing iterators to unique values to prevent
creating value copies.
---
 Source/cmAlgorithms.h | 54 ++++++++++++++++++++++++++++++++++-----------------
 1 file changed, 36 insertions(+), 18 deletions(-)

diff --git a/Source/cmAlgorithms.h b/Source/cmAlgorithms.h
index 2ff1ed0..0980416 100644
--- a/Source/cmAlgorithms.h
+++ b/Source/cmAlgorithms.h
@@ -233,27 +233,45 @@ typename Range::const_iterator cmRemoveMatching(Range& r, MatchRange const& m)
                         ContainerAlgorithms::BinarySearcher<MatchRange>(m));
 }
 
-template <typename Range>
-typename Range::const_iterator cmRemoveDuplicates(Range& r)
+template <typename ForwardIterator>
+ForwardIterator cmRemoveDuplicates(ForwardIterator first, ForwardIterator last)
 {
-  typedef typename Range::value_type T;
-  std::unordered_set<T> unique;
-  std::vector<size_t> indices;
-  size_t count = 0;
-  const typename Range::const_iterator end = r.end();
-  for (typename Range::const_iterator it = r.begin(); it != end;
-       ++it, ++count) {
-    const typename std::unordered_set<T>::iterator occur = unique.find(*it);
-    if (occur == unique.end()) {
-      unique.insert(*it);
-    } else {
-      indices.push_back(count);
+  using Value = typename std::iterator_traits<ForwardIterator>::value_type;
+  using Hash = struct
+  {
+    std::size_t operator()(ForwardIterator it) const
+    {
+      return std::hash<Value>{}(*it);
     }
+  };
+
+  using Equal = struct
+  {
+    bool operator()(ForwardIterator it1, ForwardIterator it2) const
+    {
+      return *it1 == *it2;
+    }
+  };
+  std::unordered_set<ForwardIterator, Hash, Equal> uniq;
+
+  ForwardIterator result = first;
+  while (first != last) {
+    if (uniq.find(first) == uniq.end()) {
+      if (result != first) {
+        *result = std::move(*first);
+      }
+      uniq.insert(result);
+      ++result;
+    }
+    ++first;
   }
-  if (indices.empty()) {
-    return end;
-  }
-  return cmRemoveIndices(r, indices);
+  return result;
+}
+
+template <typename Range>
+typename Range::const_iterator cmRemoveDuplicates(Range& r)
+{
+  return cmRemoveDuplicates(r.begin(), r.end());
 }
 
 template <typename Range>
-- 
cgit v0.12