cmAlgorithms: Speed up cmRemoveDuplicates method

Use a hash table instead of a sorted vector to track entries.

Co-authored-by: Chu Qinghao <me@qinghao1.com>

2 files changed, 38 insertions, 41 deletions

diff --git a/Source/cmAlgorithms.h b/Source/cmAlgorithms.h
index 244dc1c..c4eb62b 100644
--- a/Source/cmAlgorithms.h
+++ b/Source/cmAlgorithms.h
@@ -13,6 +13,7 @@
 #include <sstream>
 #include <string.h>
 #include <string>
+#include <unordered_set>
 #include <utility>
 #include <vector>
 
@@ -275,55 +276,19 @@ typename Range::const_iterator cmRemoveMatching(Range& r, MatchRange const& m)
                         ContainerAlgorithms::BinarySearcher<MatchRange>(m));
 }
 
-namespace ContainerAlgorithms {
-
-template <typename Range, typename T = typename Range::value_type>
-struct RemoveDuplicatesAPI
-{
-  typedef typename Range::const_iterator const_iterator;
-  typedef typename Range::const_iterator value_type;
-
-  static bool lessThan(value_type a, value_type b) { return *a < *b; }
-  static value_type uniqueValue(const_iterator a) { return a; }
-  template <typename It>
-  static bool valueCompare(It it, const_iterator it2)
-  {
-    return **it != *it2;
-  }
-};
-
-template <typename Range, typename T>
-struct RemoveDuplicatesAPI<Range, T*>
-{
-  typedef typename Range::const_iterator const_iterator;
-  typedef T* value_type;
-
-  static bool lessThan(value_type a, value_type b) { return a < b; }
-  static value_type uniqueValue(const_iterator a) { return *a; }
-  template <typename It>
-  static bool valueCompare(It it, const_iterator it2)
-  {
-    return *it != *it2;
-  }
-};
-}
-
 template <typename Range>
 typename Range::const_iterator cmRemoveDuplicates(Range& r)
 {
-  typedef ContainerAlgorithms::RemoveDuplicatesAPI<Range> API;
-  typedef typename API::value_type T;
-  std::vector<T> unique;
-  unique.reserve(r.size());
+  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::vector<T>::iterator low = std::lower_bound(
-      unique.begin(), unique.end(), API::uniqueValue(it), API::lessThan);
-    if (low == unique.end() || API::valueCompare(low, it)) {
-      unique.insert(low, API::uniqueValue(it));
+    const typename std::unordered_set<T>::iterator occur = unique.find(*it);
+    if (occur == unique.end()) {
+      unique.insert(*it);
     } else {
       indices.push_back(count);
     }
diff --git a/Source/cmFindPackageCommand.h b/Source/cmFindPackageCommand.h
index 150a51d..68b5ec0 100644
--- a/Source/cmFindPackageCommand.h
+++ b/Source/cmFindPackageCommand.h
@@ -6,11 +6,25 @@
 #include "cmConfigure.h" // IWYU pragma: keep
 
 #include "cm_kwiml.h"
+#include <cstddef>
 #include <map>
 #include <set>
 #include <string>
 #include <vector>
 
+// IWYU insists we should forward-declare instead of including <functional>,
+// but we cannot forward-declare reliably because some C++ standard libraries
+// put the template in an inline namespace.
+#ifdef CMAKE_IWYU
+/* clang-format off */
+namespace std {
+  template <class T> struct hash;
+}
+/* clang-format on */
+#else
+#include <functional>
+#endif
+
 #include "cmFindCommon.h"
 
 class cmCommand;
@@ -194,6 +208,24 @@ private:
     }
   };
   std::vector<ConfigFileInfo> ConsideredConfigs;
+
+  friend struct std::hash<ConfigFileInfo>;
+};
+
+namespace std {
+
+template <>
+struct hash<cmFindPackageCommand::ConfigFileInfo>
+{
+  typedef cmFindPackageCommand::ConfigFileInfo argument_type;
+  typedef size_t result_type;
+
+  result_type operator()(argument_type const& s) const noexcept
+  {
+    result_type const h(std::hash<std::string>{}(s.filename));
+    return h;
+  }
 };
+}
 
 #endif