Improve a poor implementation of "find duplicates".

content/child/webcrypto/test/test_helpers.cc

Index: content/child/webcrypto/test/test_helpers.cc
diff --git a/content/child/webcrypto/test/test_helpers.cc b/content/child/webcrypto/test/test_helpers.cc
index 07462d637730ec0afcc167b6e59401ad89759911..64f27166d80afbb8f70623792afda1473658dc97 100644
--- a/content/child/webcrypto/test/test_helpers.cc
+++ b/content/child/webcrypto/test/test_helpers.cc
@@ -4,6 +4,8 @@
 
 #include "content/child/webcrypto/test/test_helpers.h"
 
+#include <set>
+
 #include "base/file_util.h"
 #include "base/json/json_reader.h"
 #include "base/json/json_writer.h"
@@ -239,14 +241,11 @@ blink::WebCryptoAlgorithm GetDigestAlgorithm(base::DictionaryValue* dict,
   return blink::WebCryptoAlgorithm::createNull();
 }
 
-// Returns true if any of the vectors in the input list have identical content.
-// Dumb O(n^2) implementation but should be fast enough for the input sizes that
-// are used.
 bool CopiesExist(const std::vector<std::vector<uint8_t> >& bufs) {
+  std::set<std::vector<uint8_t> > values;
   for (size_t i = 0; i < bufs.size(); ++i) {
-    for (size_t j = i + 1; j < bufs.size(); ++j) {
-      if (CryptoData(bufs[i]) == CryptoData(bufs[j]))
-        return true;
+    if (!values.insert(bufs[i]).second) {
+      return true;
     }

[Ryan Sleevi, 2014/08/27 17:15:58]

This seems to be memory intensive.

Why not just sort and then do a linear scan?

[eroman, 2014/08/27 18:47:06]

Done. I also modified it to sort a vector of indices to avoid moving lots of
data.

   }
   return false;