Cheer up spell-checking code

chrome/browser/spellchecker/spellcheck_custom_dictionary.cc

Index: chrome/browser/spellchecker/spellcheck_custom_dictionary.cc
diff --git a/chrome/browser/spellchecker/spellcheck_custom_dictionary.cc b/chrome/browser/spellchecker/spellcheck_custom_dictionary.cc
index c9d113fd6025caf53e4ccf184a5626712bff11f2..bb46fb4490d690fde1f75cff49c5a8ca1480f4dc 100644
--- a/chrome/browser/spellchecker/spellcheck_custom_dictionary.cc
+++ b/chrome/browser/spellchecker/spellcheck_custom_dictionary.cc
@@ -14,6 +14,7 @@
 #include "base/strings/string_number_conversions.h"
 #include "base/strings/string_split.h"
 #include "base/strings/string_util.h"
+#include "chrome/browser/spellchecker/set_difference_container.h"
 #include "chrome/browser/spellchecker/spellcheck_host_metrics.h"
 #include "chrome/common/chrome_constants.h"
 #include "chrome/common/spellcheck_common.h"
@@ -96,18 +97,21 @@ int SanitizeWordsToAdd(const std::set<std::string>& existing,
                        std::set<std::string>* to_add) {
   DCHECK(to_add);
   // Do not add duplicate words.
-  std::set<std::string> new_words =
-      base::STLSetDifference<std::set<std::string>>(*to_add, existing);
+  spellcheck::set_difference_container<std::set<std::string>,
+                                       std::set<std::string> >

[please use gerrit instead, 2016/02/03 23:59:11]

No space inside of ">>".

[Kevin Bailey, 2016/02/04 16:34:12]

Done.

+     new_words(*to_add, existing);
   int result = VALID_CHANGE;
-  if (to_add->size() != new_words.size())
-    result |= DETECTED_DUPLICATE_WORDS;
+  unsigned new_words_size = 0;

[please use gerrit instead, 2016/02/03 23:59:11]

size_t, since we're comparing it to std::set::size(), which returns a size_t. A
size_t can be different from "unsigned int" on some platforms. For example, it
could be "unsigned long".

[Kevin Bailey, 2016/02/04 16:34:12]

If true, the unsigned would be promoted. I think you're think of the dangers of
comparing signed and unsigned.

[groby-ooo-7-16, 2016/02/04 19:38:36]

We're trying to avoid implicit promotions. 

Quoth the Chromium style guide: 
  Use size_t for object and allocation sizes, object counts, array and pointer
offsets, vector indices, and so on

   // Do not add invalid words.
   std::set<std::string> valid_new_words;
   for (const std::string& word : new_words) {
+    ++new_words_size;
     if (IsValidWord(word))
       valid_new_words.insert(valid_new_words.end(), word);
   }
-  if (valid_new_words.size() != new_words.size())
+  if (to_add->size() != new_words_size)
+    result |= DETECTED_DUPLICATE_WORDS;
+  if (valid_new_words.size() != new_words_size)
     result |= DETECTED_INVALID_WORDS;
   // Save the sanitized words to be added.
   std::swap(*to_add, valid_new_words);
@@ -445,12 +449,8 @@ void SpellcheckCustomDictionary::Apply(const Change& dictionary_change) {
     words_.insert(dictionary_change.to_add().begin(),
                   dictionary_change.to_add().end());
   }
-  if (!dictionary_change.to_remove().empty()) {
-    std::set<std::string> updated_words =
-        base::STLSetDifference<std::set<std::string>>(
-            words_, dictionary_change.to_remove());
-    std::swap(words_, updated_words);
-  }
+  for (const auto& word : dictionary_change.to_remove())
+    words_.erase(word);

[please use gerrit instead, 2016/02/03 23:59:11]

Let's not switch this algorithm, because it's O(n*log(n)), as opposed to the old
one, which is O(n).

[Kevin Bailey, 2016/02/04 16:34:12]

The old one is very O(n ln(n)). :) Consider:

line 445: go through ...to_add() and insert them in a set<>
line 450: go through ...to_remove() and insert them in a new set<>
line 449: assign to yet another set<>, but here you *might* get an RVO, or you
might not and hit another O(n ln(n))

The new code is also n.ln(n) but at least doesn't create any new sets<>s, and
IMHO is much more easy to read.

[groby-ooo-7-16, 2016/02/04 19:38:36]

Even if it were an O(n) vs O(n ln n) difference - and it isn't, STLSetDifference
is a O(n ln n) because it inserts -  it _really_ doesn't matter that much -
because changes and dictionaries are usually pretty small.

In terms of readability, I agree with Kevin - this is slightly better. IIRC we
used STLSetDifference because pre-C++11, the for loop was a bit more hideous to
read than this. 

As Bob Dylan says, the times, they are a-changing ;)

So let's do Kevin's version - unless I suffer from E_LOW_COFFEE and am missing
something critical?

(And if we were _really_ performance-obsessed, we'd handcode a loop and use the
hinting insert. But we really aren't. Really :)


On 2016/02/04 16:34:12, Kevin Bailey wrote:

 }
 
 void SpellcheckCustomDictionary::FixInvalidFile(