Cleaning up url_index_private_data and in_memory_url_index_types.

components/omnibox/browser/url_index_private_data.cc

 // Copyright (c) 2012 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.
 
 #include "components/omnibox/browser/url_index_private_data.h"
 
 #include <stdint.h>
 
 #include <functional>
 #include <iterator>
@@ skipping 19 matching lines @@
 #include "components/omnibox/browser/in_memory_url_index.h"
 #include "components/search_engines/template_url_service.h"
 #include "components/url_formatter/url_formatter.h"
 
 #if defined(USE_SYSTEM_PROTOBUF)
 #include <google/protobuf/repeated_field.h>
 #else
 #include "third_party/protobuf/src/google/protobuf/repeated_field.h"
 #endif
 
+namespace {
+
 using google::protobuf::RepeatedField;
 using google::protobuf::RepeatedPtrField;
 using in_memory_url_index::InMemoryURLIndexCacheItem;
 
 typedef in_memory_url_index::InMemoryURLIndexCacheItem_WordListItem
     WordListItem;
 typedef in_memory_url_index::InMemoryURLIndexCacheItem_WordMapItem_WordMapEntry
     WordMapEntry;
 typedef in_memory_url_index::InMemoryURLIndexCacheItem_WordMapItem WordMapItem;
 typedef in_memory_url_index::InMemoryURLIndexCacheItem_CharWordMapItem
@@ skipping 20 matching lines @@
         WordStartsMapEntry;
 
 // Algorithm Functions ---------------------------------------------------------
 
 // Comparison function for sorting search terms by descending length.
 bool LengthGreater(const base::string16& string_a,
                    const base::string16& string_b) {
   return string_a.length() > string_b.length();
 }
 
+}  // namespace
 
 // UpdateRecentVisitsFromHistoryDBTask -----------------------------------------
 
 // HistoryDBTask used to update the recent visit data for a particular
 // row from the history database.
 class UpdateRecentVisitsFromHistoryDBTask : public history::HistoryDBTask {
  public:
   explicit UpdateRecentVisitsFromHistoryDBTask(
       URLIndexPrivateData* private_data,
       history::URLID url_id);
@@ skipping 90 matching lines @@
     // the index we need individual, lower-cased words, ignoring escapings. For
     // the final filtering we need whitespace separated substrings possibly
     // containing escaped characters.
     base::string16 lower_raw_string(base::i18n::ToLower(search_string));
     base::string16 lower_unescaped_string = net::UnescapeURLComponent(
         lower_raw_string,
         net::UnescapeRule::SPACES | net::UnescapeRule::PATH_SEPARATORS |
             net::UnescapeRule::URL_SPECIAL_CHARS_EXCEPT_PATH_SEPARATORS);
 
     // Extract individual 'words' (as opposed to 'terms'; see comment in
-    // HistoryIdSetToScoredMatches()) from the search string. When the user
-    // types "colspec=ID%20Mstone Release" we get four 'words': "colspec", "id",
+    // HistoryIdsToScoredMatches()) from the search string. When the user types
+    // "colspec=ID%20Mstone Release" we get four 'words': "colspec", "id",
     // "mstone" and "release".
     String16Vector lower_words(
         String16VectorFromString16(lower_unescaped_string, false, nullptr));
     if (lower_words.empty())
       continue;
-    HistoryIDSet history_id_set = HistoryIDSetFromWords(lower_words);
-    history_ids_were_trimmed |= TrimHistoryIdsPool(&history_id_set);
 
-    ScoredHistoryMatches temp_scored_items;
-    HistoryIdSetToScoredMatches(history_id_set, lower_raw_string,
-                                template_url_service, bookmark_model,
-                                &temp_scored_items);
-    scored_items.insert(scored_items.end(), temp_scored_items.begin(),
-                        temp_scored_items.end());
+    HistoryIDVector history_ids = HistoryIDsFromWords(lower_words);
+    history_ids_were_trimmed |= TrimHistoryIdsPool(&history_ids);
+
+    HistoryIdsToScoredMatches(std::move(history_ids), lower_raw_string,
+                              template_url_service, bookmark_model,
+                              &scored_items);

[dyaroshev, 2017/02/26 01:12:17]

In fixed version of HistoryIdsToScoredMatches() we don't actually need a
temporary.

   }
   // Select and sort only the top |max_matches| results.
   if (scored_items.size() > max_matches) {
     std::partial_sort(scored_items.begin(), scored_items.begin() + max_matches,
                       scored_items.end(),
                       ScoredHistoryMatch::MatchScoreGreater);
     scored_items.resize(max_matches);
   } else {
     std::sort(scored_items.begin(), scored_items.end(),
               ScoredHistoryMatch::MatchScoreGreater);
@@ skipping 229 matching lines @@
   //    search_term_cache_
 }
 
 bool URLIndexPrivateData::Empty() const {
   return history_info_map_.empty();
 }
 
 void URLIndexPrivateData::Clear() {
   last_time_rebuilt_from_history_ = base::Time();
   word_list_.clear();
-  available_words_.clear();
+  available_words_ = {};
   word_map_.clear();
   char_word_map_.clear();
   word_id_history_map_.clear();
   history_id_word_map_.clear();
   history_info_map_.clear();
   word_starts_map_.clear();
 }
 
 URLIndexPrivateData::~URLIndexPrivateData() {}
 
-HistoryIDSet URLIndexPrivateData::HistoryIDSetFromWords(
+HistoryIDVector URLIndexPrivateData::HistoryIDsFromWords(
     const String16Vector& unsorted_words) {
+  // This histogram name reflects the historic name of this function.
   SCOPED_UMA_HISTOGRAM_TIMER("Omnibox.HistoryQuickHistoryIDSetFromWords");
   // Break the terms down into individual terms (words), get the candidate
   // set for each term, and intersect each to get a final candidate list.
   // Note that a single 'term' from the user's perspective might be
   // a string like "http://www.somewebsite.com" which, from our perspective,
   // is four words: 'http', 'www', 'somewebsite', and 'com'.
-  HistoryIDSet history_id_set;
+  HistoryIDVector history_ids;
   String16Vector words(unsorted_words);
   // Sort the words into the longest first as such are likely to narrow down
   // the results quicker. Also, single character words are the most expensive
   // to process so save them for last.
   std::sort(words.begin(), words.end(), LengthGreater);
+
+  // TODO(dyaroshev): write a generic algorithm(crbug.com/696167).
   for (String16Vector::iterator iter = words.begin(); iter != words.end();
        ++iter) {
     base::string16 uni_word = *iter;

[Peter Kasting, 2017/02/28 00:33:54]

Nit: Inline into next statement.

     HistoryIDSet term_history_set = HistoryIDsForTerm(uni_word);
     if (term_history_set.empty()) {
-      history_id_set.clear();
+      history_ids.clear();

[Peter Kasting, 2017/02/28 00:33:54]

Nit: Just "return HistoryIDVector();" rather than clear() + break; + return. 
(here, plus two similar places below)

       break;
     }
     if (iter == words.begin()) {
-      history_id_set.swap(term_history_set);
+      history_ids = {term_history_set.begin(), term_history_set.end()};
     } else {
-      HistoryIDSet new_history_id_set = base::STLSetIntersection<HistoryIDSet>(
-          history_id_set, term_history_set);
-      history_id_set.swap(new_history_id_set);
+      history_ids = base::STLSetIntersection<HistoryIDVector>(history_ids,
+                                                              term_history_set);
     }
   }
-  return history_id_set;
+  return history_ids;
 }
 
 bool URLIndexPrivateData::TrimHistoryIdsPool(
-    HistoryIDSet* history_id_set) const {
+    HistoryIDVector* history_ids) const {
   constexpr size_t kItemsToScoreLimit = 500;
-  if (history_id_set->size() <= kItemsToScoreLimit)
+  if (history_ids->size() <= kItemsToScoreLimit)
     return false;
 
-  HistoryIDVector history_ids(history_id_set->begin(), history_id_set->end());
-
   // Trim down the set by sorting by typed-count, visit-count, and last
   // visit.
-  auto new_end = history_ids.begin() + kItemsToScoreLimit;
+  auto new_end = history_ids->begin() + kItemsToScoreLimit;
   HistoryItemFactorGreater item_factor_functor(history_info_map_);
 
-  std::nth_element(history_ids.begin(), new_end, history_ids.end(),
+  std::nth_element(history_ids->begin(), new_end, history_ids->end(),
                    item_factor_functor);
-  history_ids.erase(new_end, history_ids.end());
+  history_ids->erase(new_end, history_ids->end());
 
-  *history_id_set = {history_ids.begin(), history_ids.end()};
   return true;
 }
 
 HistoryIDSet URLIndexPrivateData::HistoryIDsForTerm(
     const base::string16& term) {
   if (term.empty())
     return HistoryIDSet();
 
   // TODO(mrossetti): Consider optimizing for very common terms such as
   // 'http[s]', 'www', 'com', etc. Or collect the top 100 more frequently
@@ skipping 47 matching lines @@
 
     // Reduce the word set with any leftover, unprocessed characters.
     if (!unique_chars.empty()) {
       WordIDSet leftover_set(WordIDSetForTermChars(unique_chars));
       // We might come up empty on the leftovers.
       if (leftover_set.empty()) {
         search_term_cache_[term] = SearchTermCacheItem();
         return HistoryIDSet();
       }
       // Or there may not have been a prefix from which to start.
-      if (prefix_chars.empty()) {
-        word_id_set.swap(leftover_set);
-      } else {
-        WordIDSet new_word_id_set = base::STLSetIntersection<WordIDSet>(
-            word_id_set, leftover_set);
-        word_id_set.swap(new_word_id_set);
-      }
+      word_id_set = prefix_chars.empty() ? std::move(leftover_set)
+                                         : base::STLSetIntersection<WordIDSet>(
+                                               word_id_set, leftover_set);
     }
 
     // We must filter the word list because the resulting word set surely
     // contains words which do not have the search term as a proper subset.
     for (WordIDSet::iterator word_set_iter = word_id_set.begin();
          word_set_iter != word_id_set.end(); ) {
       if (word_list_[*word_set_iter].find(term) == base::string16::npos)
         word_set_iter = word_id_set.erase(word_set_iter);
       else
         ++word_set_iter;
     }
   } else {
     word_id_set = WordIDSetForTermChars(Char16SetFromString16(term));
   }
 
   // If any words resulted then we can compose a set of history IDs by unioning
   // the sets from each word.
   HistoryIDSet history_id_set;
-  if (!word_id_set.empty()) {
-    for (WordIDSet::iterator word_id_iter = word_id_set.begin();
-         word_id_iter != word_id_set.end(); ++word_id_iter) {
-      WordID word_id = *word_id_iter;
-      WordIDHistoryMap::iterator word_iter = word_id_history_map_.find(word_id);
-      if (word_iter != word_id_history_map_.end()) {
-        HistoryIDSet& word_history_id_set(word_iter->second);
-        history_id_set.insert(word_history_id_set.begin(),
-                              word_history_id_set.end());
-      }
+  for (WordID word_id : word_id_set) {
+    WordIDHistoryMap::iterator word_iter = word_id_history_map_.find(word_id);
+    if (word_iter != word_id_history_map_.end()) {
+      HistoryIDSet& word_history_id_set(word_iter->second);
+      history_id_set.insert(word_history_id_set.begin(),
+                            word_history_id_set.end());
     }
   }
 
   // Record a new cache entry for this word if the term is longer than
   // a single character.
   if (term_length > 1)
     search_term_cache_[term] = SearchTermCacheItem(word_id_set, history_id_set);
 
   return history_id_set;
 }
 
 WordIDSet URLIndexPrivateData::WordIDSetForTermChars(
     const Char16Set& term_chars) {
+  // TODO(dyaroshev): write a generic algorithm(crbug.com/696167).
+
   WordIDSet word_id_set;
   for (Char16Set::const_iterator c_iter = term_chars.begin();
        c_iter != term_chars.end(); ++c_iter) {
     CharWordIDMap::iterator char_iter = char_word_map_.find(*c_iter);
     if (char_iter == char_word_map_.end()) {
       // A character was not found so there are no matching results: bail.
       word_id_set.clear();

[Peter Kasting, 2017/02/28 00:33:54]

Nit: Same comment as above

       break;
     }
     WordIDSet& char_word_id_set(char_iter->second);

[Peter Kasting, 2017/02/28 00:33:54]

Nit: Can be const

     // It is possible for there to no longer be any words associated with
     // a particular character. Give up in that case.
     if (char_word_id_set.empty()) {
       word_id_set.clear();
       break;
     }
 
     if (c_iter == term_chars.begin()) {
       // First character results becomes base set of results.

[Peter Kasting, 2017/02/28 00:33:55]

Nit: These comments just restate the code, remove.

       word_id_set = char_word_id_set;
     } else {
       // Subsequent character results get intersected in.
-      WordIDSet new_word_id_set = base::STLSetIntersection<WordIDSet>(
-          word_id_set, char_word_id_set);
-      word_id_set.swap(new_word_id_set);
+      word_id_set =
+          base::STLSetIntersection<WordIDSet>(word_id_set, char_word_id_set);
     }
   }
   return word_id_set;
 }
 
-void URLIndexPrivateData::HistoryIdSetToScoredMatches(
-    HistoryIDSet history_id_set,
+void URLIndexPrivateData::HistoryIdsToScoredMatches(
+    HistoryIDVector history_ids,
     const base::string16& lower_raw_string,
     const TemplateURLService* template_url_service,
     bookmarks::BookmarkModel* bookmark_model,
     ScoredHistoryMatches* scored_items) const {
-  if (history_id_set.empty())
+  if (history_ids.empty())
     return;
 
   // Break up the raw search string (complete with escaped URL elements) into
   // 'terms' (as opposed to 'words'; see comment in HistoryItemsForTerms()).
   // We only want to break up the search string on 'true' whitespace rather than
   // escaped whitespace.  For example, when the user types
   // "colspec=ID%20Mstone Release" we get two 'terms': "colspec=id%20mstone" and
   // "release".
   String16Vector lower_raw_terms =
       base::SplitString(lower_raw_string, base::kWhitespaceUTF16,
                         base::KEEP_WHITESPACE, base::SPLIT_WANT_NONEMPTY);
 
   // Don't score matches when there are no terms to score against.  (It's
   // possible that the word break iterater that extracts words to search for in
   // the database allows some whitespace "words" whereas SplitString excludes a
   // long list of whitespace.)  One could write a scoring function that gives a
   // reasonable order to matches when there are no terms (i.e., all the words
   // are some form of whitespace), but this is such a rare edge case that it's
   // not worth the time.
   if (lower_raw_terms.empty())
     return;
 
   WordStarts lower_terms_to_word_starts_offsets;
   CalculateWordStartsOffsets(lower_raw_terms,
                              &lower_terms_to_word_starts_offsets);
 
   // Filter bad matches and other matches we don't want to display.
-  for (auto it = history_id_set.begin();;) {
-    it = std::find_if(it, history_id_set.end(),
-                      [this, template_url_service](const HistoryID history_id) {
-                        return ShouldFilter(history_id, template_url_service);
-                      });
-    if (it == history_id_set.end())
-      break;
-    it = history_id_set.erase(it);
-  }
+  auto filter = [this, template_url_service](const HistoryID history_id) {
+    return ShouldFilter(history_id, template_url_service);
+  };
+  history_ids.erase(
+      std::remove_if(history_ids.begin(), history_ids.end(), filter),
+      history_ids.end());
 
   // Score the matches.
-  const size_t num_matches = history_id_set.size();
+  const size_t num_matches = history_ids.size();
   const base::Time now = base::Time::Now();
-  std::transform(
-      history_id_set.begin(), history_id_set.end(),
-      std::back_inserter(*scored_items), [&](const HistoryID history_id) {
-        auto hist_pos = history_info_map_.find(history_id);
-        const history::URLRow& hist_item = hist_pos->second.url_row;
-        auto starts_pos = word_starts_map_.find(history_id);
-        DCHECK(starts_pos != word_starts_map_.end());
-        return ScoredHistoryMatch(
-            hist_item, hist_pos->second.visits, lower_raw_string,
-            lower_raw_terms, lower_terms_to_word_starts_offsets,
-            starts_pos->second,
-            bookmark_model && bookmark_model->IsBookmarked(hist_item.url()),
-            num_matches, now);
-      });
 

[dyaroshev, 2017/02/26 01:12:17]

First transforming and then removing seems unnecessary - it's better to filter
prior to putting in.

-  // Filter all matches that ended up scoring 0.  (These are usually matches
-  // which didn't match the user's raw terms.)
-  scored_items->erase(std::remove_if(scored_items->begin(), scored_items->end(),
-                                     [](const ScoredHistoryMatch& match) {
-                                       return match.raw_score == 0;
-                                     }),
-                      scored_items->end());
+  for (HistoryID history_id : history_ids) {
+    auto hist_pos = history_info_map_.find(history_id);
+    const history::URLRow& hist_item = hist_pos->second.url_row;
+    auto starts_pos = word_starts_map_.find(history_id);
+    DCHECK(starts_pos != word_starts_map_.end());
+    ScoredHistoryMatch new_scored_match(
+        hist_item, hist_pos->second.visits, lower_raw_string, lower_raw_terms,
+        lower_terms_to_word_starts_offsets, starts_pos->second,
+        bookmark_model && bookmark_model->IsBookmarked(hist_item.url()),
+        num_matches, now);
+    // Filter new matches that ended up scoring 0. (These are usually matches
+    // which didn't match the user's raw terms.)
+    if (new_scored_match.raw_score != 0)

[Peter Kasting, 2017/02/28 00:33:54]

Nit: > 0?

+      scored_items->push_back(std::move(new_scored_match));
+  }
 }
 
 // static
 void URLIndexPrivateData::CalculateWordStartsOffsets(
     const String16Vector& lower_terms,
     WordStarts* lower_terms_to_word_starts_offsets) {
   // Calculate offsets for each term.  For instance, the offset for
   // ".net" should be 1, indicating that the actual word-part of the term
   // starts at offset 1.
   lower_terms_to_word_starts_offsets->resize(lower_terms.size(), 0u);
@@ skipping 71 matching lines @@
   HistoryID history_id = static_cast<HistoryID>(row.id());
   // Split URL into individual, unique words then add in the title words.
   const GURL& gurl(row.url());
   const base::string16& url =
       bookmarks::CleanUpUrlForMatching(gurl, nullptr);
   String16Set url_words = String16SetFromString16(url,
       word_starts ? &word_starts->url_word_starts_ : nullptr);
   const base::string16& title = bookmarks::CleanUpTitleForMatching(row.title());
   String16Set title_words = String16SetFromString16(title,
       word_starts ? &word_starts->title_word_starts_ : nullptr);
-  String16Set words = base::STLSetUnion<String16Set>(url_words, title_words);
-  for (String16Set::iterator word_iter = words.begin();
-       word_iter != words.end(); ++word_iter)
-    AddWordToIndex(*word_iter, history_id);
+  for (const auto& word :
+       base::STLSetUnion<String16Set>(url_words, title_words))
+    AddWordToIndex(word, history_id);
 
   search_term_cache_.clear();  // Invalidate the term cache.
 }
 
 void URLIndexPrivateData::AddWordToIndex(const base::string16& term,
                                          HistoryID history_id) {
-  WordMap::iterator word_pos = word_map_.find(term);
-  if (word_pos != word_map_.end())
-    UpdateWordHistory(word_pos->second, history_id);
-  else
-    AddWordHistory(term, history_id);
+  WordMap::iterator word_pos;
+  bool is_new;
+  std::tie(word_pos, is_new) = word_map_.emplace(term, WordID());
+
+  // Adding a new word (i.e. a word that is not already in the word index).
+  if (is_new) {
+    word_pos->second = AddNewWordToWordList(term);
+
+    // For each character in the newly added word add the word to the character
+    // index.
+    for (base::char16 uni_char : Char16SetFromString16(term))
+      char_word_map_[uni_char].insert(word_pos->second);
+  }
+
+  word_id_history_map_[word_pos->second].insert(history_id);
+  history_id_word_map_[history_id].insert(word_pos->second);
 }
 
-void URLIndexPrivateData::AddWordHistory(const base::string16& term,
-                                         HistoryID history_id) {
+WordID URLIndexPrivateData::AddNewWordToWordList(const base::string16& term) {
   WordID word_id = word_list_.size();
   if (available_words_.empty()) {
     word_list_.push_back(term);
-  } else {
-    word_id = *(available_words_.begin());
-    word_list_[word_id] = term;
-    available_words_.erase(word_id);
+    return word_id;
   }
-  word_map_[term] = word_id;
 
-  HistoryIDSet history_id_set;
-  history_id_set.insert(history_id);
-  word_id_history_map_[word_id] = history_id_set;
-  AddToHistoryIDWordMap(history_id, word_id);
-
-  // For each character in the newly added word (i.e. a word that is not
-  // already in the word index), add the word to the character index.
-  Char16Set characters = Char16SetFromString16(term);
-  for (Char16Set::iterator uni_char_iter = characters.begin();
-       uni_char_iter != characters.end(); ++uni_char_iter) {
-    base::char16 uni_char = *uni_char_iter;
-    CharWordIDMap::iterator char_iter = char_word_map_.find(uni_char);
-    if (char_iter != char_word_map_.end()) {
-      // Update existing entry in the char/word index.
-      WordIDSet& word_id_set(char_iter->second);
-      word_id_set.insert(word_id);
-    } else {
-      // Create a new entry in the char/word index.
-      WordIDSet word_id_set;
-      word_id_set.insert(word_id);
-      char_word_map_[uni_char] = word_id_set;
-    }
-  }
-}
-
-void URLIndexPrivateData::UpdateWordHistory(WordID word_id,
-                                            HistoryID history_id) {
-  WordIDHistoryMap::iterator history_pos = word_id_history_map_.find(word_id);
-  DCHECK(history_pos != word_id_history_map_.end());
-  HistoryIDSet& history_id_set(history_pos->second);
-  history_id_set.insert(history_id);
-  AddToHistoryIDWordMap(history_id, word_id);
-}
-
-void URLIndexPrivateData::AddToHistoryIDWordMap(HistoryID history_id,
-                                                WordID word_id) {
-  HistoryIDWordMap::iterator iter = history_id_word_map_.find(history_id);
-  if (iter != history_id_word_map_.end()) {
-    WordIDSet& word_id_set(iter->second);
-    word_id_set.insert(word_id);
-  } else {
-    WordIDSet word_id_set;
-    word_id_set.insert(word_id);
-    history_id_word_map_[history_id] = word_id_set;
-  }
+  word_id = available_words_.top();
+  available_words_.pop();
+  word_list_[word_id] = term;
+  return word_id;
 }
 
 void URLIndexPrivateData::RemoveRowFromIndex(const history::URLRow& row) {
   RemoveRowWordsFromIndex(row);
   HistoryID history_id = static_cast<HistoryID>(row.id());
   history_info_map_.erase(history_id);
   word_starts_map_.erase(history_id);
 }
 
 void URLIndexPrivateData::RemoveRowWordsFromIndex(const history::URLRow& row) {
   // Remove the entries in history_id_word_map_ and word_id_history_map_ for
   // this row.
   HistoryID history_id = static_cast<HistoryID>(row.id());
   WordIDSet word_id_set = history_id_word_map_[history_id];
   history_id_word_map_.erase(history_id);
 
   // Reconcile any changes to word usage.
-  for (WordIDSet::iterator word_id_iter = word_id_set.begin();
-       word_id_iter != word_id_set.end(); ++word_id_iter) {
-    WordID word_id = *word_id_iter;
-    word_id_history_map_[word_id].erase(history_id);
-    if (!word_id_history_map_[word_id].empty())
-      continue;  // The word is still in use.
+  for (WordID word_id : word_id_set) {
+    auto word_id_history_map_iter = word_id_history_map_.find(word_id);
+    DCHECK(word_id_history_map_iter != word_id_history_map_.end());
+
+    word_id_history_map_iter->second.erase(history_id);
+    if (!word_id_history_map_iter->second.empty())
+      continue;
 
     // The word is no longer in use. Reconcile any changes to character usage.
     base::string16 word = word_list_[word_id];
-    Char16Set characters = Char16SetFromString16(word);
-    for (Char16Set::iterator uni_char_iter = characters.begin();
-         uni_char_iter != characters.end(); ++uni_char_iter) {
-      base::char16 uni_char = *uni_char_iter;
-      char_word_map_[uni_char].erase(word_id);
-      if (char_word_map_[uni_char].empty())
-        char_word_map_.erase(uni_char);  // No longer in use.
+    for (base::char16 uni_char : Char16SetFromString16(word)) {
+      auto char_word_map_iter = char_word_map_.find(uni_char);
+      char_word_map_iter->second.erase(word_id);
+      if (char_word_map_iter->second.empty())
+        char_word_map_.erase(char_word_map_iter);
     }
 
     // Complete the removal of references to the word.
-    word_id_history_map_.erase(word_id);
+    word_id_history_map_.erase(word_id_history_map_iter);
     word_map_.erase(word);
     word_list_[word_id] = base::string16();
-    available_words_.insert(word_id);
+    available_words_.push(word_id);
   }
 }
 
 void URLIndexPrivateData::ResetSearchTermCache() {
-  for (SearchTermCacheMap::iterator iter = search_term_cache_.begin();
-       iter != search_term_cache_.end(); ++iter)
-    iter->second.used_ = false;
+  for (auto& item : search_term_cache_)
+    item.second.used_ = false;
 }
 
 bool URLIndexPrivateData::SaveToFile(const base::FilePath& file_path) {
   base::TimeTicks beginning_time = base::TimeTicks::Now();
   InMemoryURLIndexCacheItem index_cache;
   SavePrivateData(&index_cache);
   std::string data;
   if (!index_cache.SerializeToString(&data)) {
     LOG(WARNING) << "Failed to serialize the InMemoryURLIndex cache.";
     return false;
@@ skipping 24 matching lines @@
   SaveWordIDHistoryMap(cache);
   SaveHistoryInfoMap(cache);
   SaveWordStartsMap(cache);
 }
 
 void URLIndexPrivateData::SaveWordList(InMemoryURLIndexCacheItem* cache) const {
   if (word_list_.empty())
     return;
   WordListItem* list_item = cache->mutable_word_list();
   list_item->set_word_count(word_list_.size());
-  for (String16Vector::const_iterator iter = word_list_.begin();
-       iter != word_list_.end(); ++iter)
-    list_item->add_word(base::UTF16ToUTF8(*iter));
+  for (const base::string16& word : word_list_)
+    list_item->add_word(base::UTF16ToUTF8(word));
 }
 
 void URLIndexPrivateData::SaveWordMap(InMemoryURLIndexCacheItem* cache) const {
   if (word_map_.empty())
     return;
   WordMapItem* map_item = cache->mutable_word_map();
   map_item->set_item_count(word_map_.size());
-  for (WordMap::const_iterator iter = word_map_.begin();
-       iter != word_map_.end(); ++iter) {
+  for (const auto& elem : word_map_) {
     WordMapEntry* map_entry = map_item->add_word_map_entry();
-    map_entry->set_word(base::UTF16ToUTF8(iter->first));
-    map_entry->set_word_id(iter->second);
+    map_entry->set_word(base::UTF16ToUTF8(elem.first));
+    map_entry->set_word_id(elem.second);
   }
 }
 
 void URLIndexPrivateData::SaveCharWordMap(
     InMemoryURLIndexCacheItem* cache) const {
   if (char_word_map_.empty())
     return;
   CharWordMapItem* map_item = cache->mutable_char_word_map();
   map_item->set_item_count(char_word_map_.size());
-  for (CharWordIDMap::const_iterator iter = char_word_map_.begin();
-       iter != char_word_map_.end(); ++iter) {
+  for (const auto& entry : char_word_map_) {
     CharWordMapEntry* map_entry = map_item->add_char_word_map_entry();
-    map_entry->set_char_16(iter->first);
-    const WordIDSet& word_id_set(iter->second);
+    map_entry->set_char_16(entry.first);
+    const WordIDSet& word_id_set = entry.second;
     map_entry->set_item_count(word_id_set.size());
-    for (WordIDSet::const_iterator set_iter = word_id_set.begin();
-         set_iter != word_id_set.end(); ++set_iter)
-      map_entry->add_word_id(*set_iter);
+    for (WordID word_id : word_id_set)
+      map_entry->add_word_id(word_id);
   }
 }
 
 void URLIndexPrivateData::SaveWordIDHistoryMap(
     InMemoryURLIndexCacheItem* cache) const {
   if (word_id_history_map_.empty())
     return;
   WordIDHistoryMapItem* map_item = cache->mutable_word_id_history_map();
   map_item->set_item_count(word_id_history_map_.size());
-  for (WordIDHistoryMap::const_iterator iter = word_id_history_map_.begin();
-       iter != word_id_history_map_.end(); ++iter) {
+  for (const auto& entry : word_id_history_map_) {
     WordIDHistoryMapEntry* map_entry =
         map_item->add_word_id_history_map_entry();
-    map_entry->set_word_id(iter->first);
-    const HistoryIDSet& history_id_set(iter->second);
+    map_entry->set_word_id(entry.first);
+    const HistoryIDSet& history_id_set = entry.second;
     map_entry->set_item_count(history_id_set.size());
-    for (HistoryIDSet::const_iterator set_iter = history_id_set.begin();
-         set_iter != history_id_set.end(); ++set_iter)
-      map_entry->add_history_id(*set_iter);
+    for (HistoryID history_id : history_id_set)
+      map_entry->add_history_id(history_id);
   }
 }
 
 void URLIndexPrivateData::SaveHistoryInfoMap(
     InMemoryURLIndexCacheItem* cache) const {
   if (history_info_map_.empty())
     return;
   HistoryInfoMapItem* map_item = cache->mutable_history_info_map();
   map_item->set_item_count(history_info_map_.size());
-  for (HistoryInfoMap::const_iterator iter = history_info_map_.begin();
-       iter != history_info_map_.end(); ++iter) {
+  for (const auto& entry : history_info_map_) {
     HistoryInfoMapEntry* map_entry = map_item->add_history_info_map_entry();
-    map_entry->set_history_id(iter->first);
-    const history::URLRow& url_row(iter->second.url_row);
+    map_entry->set_history_id(entry.first);
+    const history::URLRow& url_row = entry.second.url_row;
     // Note: We only save information that contributes to the index so there
     // is no need to save search_term_cache_ (not persistent).
     map_entry->set_visit_count(url_row.visit_count());
     map_entry->set_typed_count(url_row.typed_count());
     map_entry->set_last_visit(url_row.last_visit().ToInternalValue());
     map_entry->set_url(url_row.url().spec());
     map_entry->set_title(base::UTF16ToUTF8(url_row.title()));
-    const VisitInfoVector& visits(iter->second.visits);
-    for (VisitInfoVector::const_iterator visit_iter = visits.begin();
-         visit_iter != visits.end(); ++visit_iter) {
+    for (const auto& visit : entry.second.visits) {
       HistoryInfoMapEntry_VisitInfo* visit_info = map_entry->add_visits();
-      visit_info->set_visit_time(visit_iter->first.ToInternalValue());
-      visit_info->set_transition_type(visit_iter->second);
+      visit_info->set_visit_time(visit.first.ToInternalValue());
+      visit_info->set_transition_type(visit.second);
     }
   }
 }
 
 void URLIndexPrivateData::SaveWordStartsMap(
     InMemoryURLIndexCacheItem* cache) const {
   if (word_starts_map_.empty())
     return;
   // For unit testing: Enable saving of the cache as an earlier version to
   // allow testing of cache file upgrading in ReadFromFile().
   // TODO(mrossetti): Instead of intruding on production code with this kind of
   // test harness, save a copy of an older version cache with known results.
   // Implement this when switching the caching over to SQLite.
   if (saved_cache_version_ < 1)
     return;
 
   WordStartsMapItem* map_item = cache->mutable_word_starts_map();
   map_item->set_item_count(word_starts_map_.size());
-  for (WordStartsMap::const_iterator iter = word_starts_map_.begin();
-       iter != word_starts_map_.end(); ++iter) {
+  for (const auto& entry : word_starts_map_) {
     WordStartsMapEntry* map_entry = map_item->add_word_starts_map_entry();
-    map_entry->set_history_id(iter->first);
-    const RowWordStarts& word_starts(iter->second);
-    for (WordStarts::const_iterator i = word_starts.url_word_starts_.begin();
-         i != word_starts.url_word_starts_.end(); ++i)
-      map_entry->add_url_word_starts(*i);
-    for (WordStarts::const_iterator i = word_starts.title_word_starts_.begin();
-         i != word_starts.title_word_starts_.end(); ++i)
-      map_entry->add_title_word_starts(*i);
+    map_entry->set_history_id(entry.first);
+    const RowWordStarts& word_starts = entry.second;
+    for (auto url_word_start : word_starts.url_word_starts_)
+      map_entry->add_url_word_starts(url_word_start);
+    for (auto title_word_start : word_starts.title_word_starts_)
+      map_entry->add_title_word_starts(title_word_start);
   }
 }
 
 bool URLIndexPrivateData::RestorePrivateData(
     const InMemoryURLIndexCacheItem& cache) {
   last_time_rebuilt_from_history_ =
       base::Time::FromInternalValue(cache.last_rebuild_timestamp());
   const base::TimeDelta rebuilt_ago =
       base::Time::Now() - last_time_rebuilt_from_history_;
   if ((rebuilt_ago > base::TimeDelta::FromDays(7)) ||
@@ skipping 21 matching lines @@
 
 bool URLIndexPrivateData::RestoreWordList(
     const InMemoryURLIndexCacheItem& cache) {
   if (!cache.has_word_list())
     return false;
   const WordListItem& list_item(cache.word_list());
   uint32_t expected_item_count = list_item.word_count();
   uint32_t actual_item_count = list_item.word_size();
   if (actual_item_count == 0 || actual_item_count != expected_item_count)
     return false;
-  const RepeatedPtrField<std::string>& words(list_item.word());
-  for (RepeatedPtrField<std::string>::const_iterator iter = words.begin();
-       iter != words.end(); ++iter)
-    word_list_.push_back(base::UTF8ToUTF16(*iter));
+  const RepeatedPtrField<std::string>& words = list_item.word();
+  word_list_.reserve(words.size());
+  std::transform(
+      words.begin(), words.end(), std::back_inserter(word_list_),
+      [](const std::string& word) { return base::UTF8ToUTF16(word); });
   return true;
 }
 
 bool URLIndexPrivateData::RestoreWordMap(
     const InMemoryURLIndexCacheItem& cache) {
   if (!cache.has_word_map())
     return false;
-  const WordMapItem& list_item(cache.word_map());
+  const WordMapItem& list_item = cache.word_map();
   uint32_t expected_item_count = list_item.item_count();
   uint32_t actual_item_count = list_item.word_map_entry_size();
   if (actual_item_count == 0 || actual_item_count != expected_item_count)
     return false;
-  const RepeatedPtrField<WordMapEntry>& entries(list_item.word_map_entry());
-  for (RepeatedPtrField<WordMapEntry>::const_iterator iter = entries.begin();
-       iter != entries.end(); ++iter)
-    word_map_[base::UTF8ToUTF16(iter->word())] = iter->word_id();
+  for (const auto& entry : list_item.word_map_entry())
+    word_map_[base::UTF8ToUTF16(entry.word())] = entry.word_id();
+
   return true;
 }
 
 bool URLIndexPrivateData::RestoreCharWordMap(
     const InMemoryURLIndexCacheItem& cache) {
   if (!cache.has_char_word_map())
     return false;
   const CharWordMapItem& list_item(cache.char_word_map());
   uint32_t expected_item_count = list_item.item_count();
   uint32_t actual_item_count = list_item.char_word_map_entry_size();
   if (actual_item_count == 0 || actual_item_count != expected_item_count)
     return false;
-  const RepeatedPtrField<CharWordMapEntry>&
-      entries(list_item.char_word_map_entry());
-  for (RepeatedPtrField<CharWordMapEntry>::const_iterator iter =
-       entries.begin(); iter != entries.end(); ++iter) {
-    expected_item_count = iter->item_count();
-    actual_item_count = iter->word_id_size();
+
+  for (const auto& entry : list_item.char_word_map_entry()) {
+    expected_item_count = entry.item_count();
+    actual_item_count = entry.word_id_size();
     if (actual_item_count == 0 || actual_item_count != expected_item_count)
       return false;
-    base::char16 uni_char = static_cast<base::char16>(iter->char_16());
-    WordIDSet word_id_set;
-    const RepeatedField<int32_t>& word_ids(iter->word_id());
-    for (RepeatedField<int32_t>::const_iterator jiter = word_ids.begin();
-         jiter != word_ids.end(); ++jiter)
-      word_id_set.insert(*jiter);
-    char_word_map_[uni_char] = word_id_set;
+    base::char16 uni_char = static_cast<base::char16>(entry.char_16());
+    const RepeatedField<int32_t>& word_ids = entry.word_id();
+    char_word_map_[uni_char] = {word_ids.begin(), word_ids.end()};
   }
   return true;
 }
 
 bool URLIndexPrivateData::RestoreWordIDHistoryMap(
     const InMemoryURLIndexCacheItem& cache) {
   if (!cache.has_word_id_history_map())
     return false;
   const WordIDHistoryMapItem& list_item(cache.word_id_history_map());
   uint32_t expected_item_count = list_item.item_count();
   uint32_t actual_item_count = list_item.word_id_history_map_entry_size();
   if (actual_item_count == 0 || actual_item_count != expected_item_count)
     return false;
-  const RepeatedPtrField<WordIDHistoryMapEntry>&
-      entries(list_item.word_id_history_map_entry());
-  for (RepeatedPtrField<WordIDHistoryMapEntry>::const_iterator iter =
-       entries.begin(); iter != entries.end(); ++iter) {
-    expected_item_count = iter->item_count();
-    actual_item_count = iter->history_id_size();
+  for (const auto& entry : list_item.word_id_history_map_entry()) {
+    expected_item_count = entry.item_count();
+    actual_item_count = entry.history_id_size();
     if (actual_item_count == 0 || actual_item_count != expected_item_count)
       return false;
-    WordID word_id = iter->word_id();
-    HistoryIDSet history_id_set;
-    const RepeatedField<int64_t>& history_ids(iter->history_id());
-    for (RepeatedField<int64_t>::const_iterator jiter = history_ids.begin();
-         jiter != history_ids.end(); ++jiter) {
-      history_id_set.insert(*jiter);
-      AddToHistoryIDWordMap(*jiter, word_id);
-    }
-    word_id_history_map_[word_id] = history_id_set;
+    WordID word_id = entry.word_id();
+    const RepeatedField<int64_t>& history_ids = entry.history_id();
+    word_id_history_map_[word_id] = {history_ids.begin(), history_ids.end()};
+    for (HistoryID history_id : history_ids)
+      history_id_word_map_[history_id].insert(word_id);
   }
   return true;
 }
 
 bool URLIndexPrivateData::RestoreHistoryInfoMap(
     const InMemoryURLIndexCacheItem& cache) {
   if (!cache.has_history_info_map())
     return false;
   const HistoryInfoMapItem& list_item(cache.history_info_map());
   uint32_t expected_item_count = list_item.item_count();
   uint32_t actual_item_count = list_item.history_info_map_entry_size();
   if (actual_item_count == 0 || actual_item_count != expected_item_count)
     return false;
-  const RepeatedPtrField<HistoryInfoMapEntry>&
-      entries(list_item.history_info_map_entry());
-  for (RepeatedPtrField<HistoryInfoMapEntry>::const_iterator iter =
-       entries.begin(); iter != entries.end(); ++iter) {
-    HistoryID history_id = iter->history_id();
-    GURL url(iter->url());
-    history::URLRow url_row(url, history_id);
-    url_row.set_visit_count(iter->visit_count());
-    url_row.set_typed_count(iter->typed_count());
-    url_row.set_last_visit(base::Time::FromInternalValue(iter->last_visit()));
-    if (iter->has_title()) {
-      base::string16 title(base::UTF8ToUTF16(iter->title()));
-      url_row.set_title(title);
-    }
-    history_info_map_[history_id].url_row = url_row;
+
+  for (const auto& entry : list_item.history_info_map_entry()) {
+    HistoryID history_id = entry.history_id();
+    history::URLRow url_row(GURL(entry.url()), history_id);
+    url_row.set_visit_count(entry.visit_count());
+    url_row.set_typed_count(entry.typed_count());
+    url_row.set_last_visit(base::Time::FromInternalValue(entry.last_visit()));
+    if (entry.has_title())
+      url_row.set_title(base::UTF8ToUTF16(entry.title()));
+    history_info_map_[history_id].url_row = std::move(url_row);
 
     // Restore visits list.
     VisitInfoVector visits;
-    visits.reserve(iter->visits_size());
-    for (int i = 0; i < iter->visits_size(); ++i) {
-      visits.push_back(std::make_pair(
-          base::Time::FromInternalValue(iter->visits(i).visit_time()),
-          ui::PageTransitionFromInt(iter->visits(i).transition_type())));
+    visits.reserve(entry.visits_size());
+    for (const auto& entry_visit : entry.visits()) {
+      visits.emplace_back(
+          base::Time::FromInternalValue(entry_visit.visit_time()),
+          ui::PageTransitionFromInt(entry_visit.transition_type()));
     }
-    history_info_map_[history_id].visits = visits;
+    history_info_map_[history_id].visits = std::move(visits);
   }
   return true;
 }
 
 bool URLIndexPrivateData::RestoreWordStartsMap(
     const InMemoryURLIndexCacheItem& cache) {
   // Note that this function must be called after RestoreHistoryInfoMap() has
   // been run as the word starts may have to be recalculated from the urls and
   // page titles.
   if (cache.has_word_starts_map()) {
     const WordStartsMapItem& list_item(cache.word_starts_map());
     uint32_t expected_item_count = list_item.item_count();
     uint32_t actual_item_count = list_item.word_starts_map_entry_size();
     if (actual_item_count == 0 || actual_item_count != expected_item_count)
       return false;
-    const RepeatedPtrField<WordStartsMapEntry>&
-        entries(list_item.word_starts_map_entry());
-    for (RepeatedPtrField<WordStartsMapEntry>::const_iterator iter =
-         entries.begin(); iter != entries.end(); ++iter) {
-      HistoryID history_id = iter->history_id();
+    for (const auto& entry : list_item.word_starts_map_entry()) {
+      HistoryID history_id = entry.history_id();
       RowWordStarts word_starts;
       // Restore the URL word starts.
-      const RepeatedField<int32_t>& url_starts(iter->url_word_starts());
-      for (RepeatedField<int32_t>::const_iterator jiter = url_starts.begin();
-           jiter != url_starts.end(); ++jiter)
-        word_starts.url_word_starts_.push_back(*jiter);
+      const RepeatedField<int32_t>& url_starts = entry.url_word_starts();
+      word_starts.url_word_starts_ = {url_starts.begin(), url_starts.end()};
+
       // Restore the page title word starts.
-      const RepeatedField<int32_t>& title_starts(iter->title_word_starts());
-      for (RepeatedField<int32_t>::const_iterator jiter = title_starts.begin();
-           jiter != title_starts.end(); ++jiter)
-        word_starts.title_word_starts_.push_back(*jiter);
-      word_starts_map_[history_id] = word_starts;
+      const RepeatedField<int32_t>& title_starts = entry.title_word_starts();
+      word_starts.title_word_starts_ = {title_starts.begin(),
+                                        title_starts.end()};
+
+      word_starts_map_[history_id] = std::move(word_starts);
     }
   } else {
     // Since the cache did not contain any word starts we must rebuild then from
     // the URL and page titles.
-    for (HistoryInfoMap::const_iterator iter = history_info_map_.begin();
-         iter != history_info_map_.end(); ++iter) {
+    for (const auto& entry : history_info_map_) {
       RowWordStarts word_starts;
-      const history::URLRow& row(iter->second.url_row);
+      const history::URLRow& row = entry.second.url_row;
       const base::string16& url =
           bookmarks::CleanUpUrlForMatching(row.url(), nullptr);
       String16VectorFromString16(url, false, &word_starts.url_word_starts_);
       const base::string16& title =
           bookmarks::CleanUpTitleForMatching(row.title());
       String16VectorFromString16(title, false, &word_starts.title_word_starts_);
-      word_starts_map_[iter->first] = word_starts;
+      word_starts_map_[entry.first] = std::move(word_starts);
     }
   }
   return true;
 }
 
 // static
 bool URLIndexPrivateData::URLSchemeIsWhitelisted(
     const GURL& gurl,
     const std::set<std::string>& whitelist) {
   return whitelist.find(gurl.scheme()) != whitelist.end();
@@ skipping 62 matching lines @@
   // First cut: typed count, visit count, recency.
   // TODO(mrossetti): This is too simplistic. Consider an approach which ranks
   // recently visited (within the last 12/24 hours) as highly important. Get
   // input from mpearson.
   if (r1.typed_count() != r2.typed_count())
     return (r1.typed_count() > r2.typed_count());
   if (r1.visit_count() != r2.visit_count())
     return (r1.visit_count() > r2.visit_count());
   return (r1.last_visit() > r2.last_visit());
 }