工作更快的std::find替代品

Question

我有一些代码，可以在一个容器中找到新的单词，并将它们添加到类的私有变量中。dict. 该功能 Learner::Learn 需要优化，使其运行速度更快。的元素。dict 向量可以互相重复，但'newWords'应该总是返回新的（非重复的）单词的数量。

#include <algorithm>
#include <string>
#include <vector>

using namespace std;

class Learner {
private:
  vector<string> dict;

public:
  int Learn(const vector<string>& words) {
    int newWords = 0;
    for (const auto& word : words) {
      if (find(dict.begin(), dict.end(), word) == dict.end()) {
        ++newWords;
        dict.push_back(word);
      }
    }
    return newWords;
  }

我试过这种方式，但执行时间是一样的。

class Learner {
 private:
  vector<string> dict;

 public:
  int Learn(const vector<string>& words) {
    std::size_t index = dict.size();
    dict.resize(dict.size() + words.size());
    vector<string>::iterator nth = dict.begin() + index;
    int newWords = 0;
    for (const auto& word : words) {
      if (find(dict.begin(), dict.end(), word) == dict.end()) {
        ++newWords;
        *nth++ = word;
      }
    }
    return newWords;
  }

我应该避免使用 push_back() 方法。

Answer 1

如果你总是保持 words sorted你可以使用二进制搜索，总运行时间为O(n log n)，但你必须将整个向量移位到中间插入东西。 (这会使它回到O(n^2))

不过你应该换一个容器，才能有明显的改善。

• std::set (O(log n) lookup, O(log n) insert)
• std::map (O(log n)查找，O(log n)插入)
• std::unordered_set (O(1)查找，O(1)插入)

Answer 2

Trie 是一个有效的替代方案，但是在std中没有，所以你必须自己写或者使用外部库。

在std.C中，你必须自己写或使用外部库。std::setstd::map 和无序版本(std::unordered_setstd::unordered_map)可能有助于