如何检查向量中是否不存在元素？

Question

这在Visual C++ 2010 Express上编译和运行正常，但它只检查[2]元素："Fish"。

int main()
    {
        vector<string> words;
        string temp;
        vector<string> disliked(3);
        disliked[0] = "Broccoli";
        disliked[1] = "Mushrooms";
        disliked[2] = "Fish";
        while (cin >> temp)
            words.push_back(temp);
        cout << "Number of words: " << words.size() << endl;
        for (int i=0; i<words.size(); ++i) {
            if (words[i]!=disliked[2])
                cout << words[i] << " ";
            else cout << "BLEEP" << " ";
        }
        cout << endl;
        keep_window_open();
        return 0;
    }

如何使其检查所有向量元素而无需打字：

if (words[i]!=disliked[0] && words[i]!=disliked[1] && words[i]!=disliked[2])

“还有什么其他建议可以让它更好或更优雅吗？”

- Kensai

---

我碰巧喜欢花椰菜、蘑菇和鱼。 - sbi

我也是！别担心，这只是 Stroustrup 的《C++程序设计》书中一个愚蠢的练习题。 :) - Kensai

我喜欢蘑菇和鱼比西兰花更多。不过西兰花也还好，只是没有蘑菇和鱼好吃。 - jalf

可能是重复的问题：如何在std::vector中查找一个元素？ - Ciro Santilli OurBigBook.com

Answer 1

if (std::find(disliked.begin(), disliked.end(), words[i]) == disliked.end()) {
   cout << words[i] << " ";
} else {
   cout << "BLEEP" << " ";
}

如果你将 std::vector<string> disliked(3); 替换为 std::set<string> disliked;，它的速度会更快。

std::set<string> disliked;
disliked.insert("Broccoli");
disliked.insert("Mushrooms");
disliked.insert("Fish");
//....

if (disliked.find(words[i]) == disliked.end()) {
   cout << words[i] << " ";
} else {
   cout << "BLEEP" << " ";
}

- Alexey Malistov

---

+1，只需修复 std::set 构造函数中的拼写错误即可。它不应该带任何参数。 - Charles Salvia

@Charles：我擅自修复了它。 - fredoverflow

Answer 2

你可以简单地使用std::find在向量中搜索单词。但是一般来说，向量并不适用于这种随机访问查找。你可能想考虑使用std::set来存储你不喜欢的食物。

然后你就可以这样说：

std::set<std::string> dislike;
dislike.insert("Broccoli");
dislike.insert("Mushrooms");
dislike.insert("Fish");

...

if (dislike.find("whatever") != dislike.end()) std::cout << "BLEEP" << std::endl;

此外，考虑使用其他代替语而不是“BLEEP”。

- Charles Salvia

---

你说“向量不适用于这种查找”。我想知道为什么。实际上，表达式 if（words [i]！= disliked [0,2]）/注意0/ 是被接受的并且可以运行，但仍然只为Fish给我一个Bleep。 - Kensai

因为当您在向量中搜索单词时，必须扫描整个向量。这就是std::find函数实际执行的操作，导致O(N)运行时间。使用std::set，每次查找仅需要O(Log(N))运行时间，速度更快。尽管对于只有3个项目，不会有任何明显的差异。 - Charles Salvia

此外，disliked[0,2]并不是你想象中的那样。它并不意味着你实际上在将words[i]与向量中的0到2元素进行比较。这只是C语言中逗号运算符的误用（大多数情况下是无用的）。请参见http://en.wikipedia.org/wiki/Comma_operator。 - Charles Salvia

非常感谢！我想这是学习任何语言中最困难的部分。有时编译器允许你做一些事情而不抱怨，你认为它已经按照你的意思工作了。 - Kensai

@Kensai：你需要提高编译器的警告级别。然后它应该会显示“警告：逗号运算符的左操作数没有效果”或类似的内容。 - fredoverflow

FredOverflow，感谢您的建议。我该如何在MS VC++ 2010 Express上实现呢？！（请不要开新手玩笑）:p - Kensai

Answer 3

C++0x引入了三个算法，您可能想要查看：all_of、any_of和none_of。

#include <algorithm>
#include <functional>

for (vector<string>::size_type i = 0; i < words.size(); ++i)
{
    if (any_of(disliked.begin(),
               disliked.end(),
               bind2nd(equal_to<string>(), words[i])))
    {
        cout << "BLEEP" << " ";
    }
    else
    {
        cout << words[i] << " ";
    }
}

但正如Alexey所指出的那样，在这种特定情况下，您可能最好使用std::set。您也可以在向量上执行binary_search，但是您必须确保它已排序。

（还要注意，我将循环计数器类型从int更改为vector<string>::size_type。）

- fredoverflow

---

太棒了！我期待着C++0x的新功能。 - Kensai

@Kensai：请注意，any_of的实现几乎是微不足道的。如果你的“令人印象深刻”的评论是指bind2nd和equal_to，那么这是老古董C++98了。 - fredoverflow

Answer 4

虽然其他方法，包括set或std::find非常好和快速，但你应该能够理解如何自己制作。
如果你想检查words中的所有元素与disliked中的所有元素，你实际上需要另一个for循环。

   for (std::size_t i = 0; i < words.size(); ++i) {
     bool found = false;
     for (std::size_t j = 0; j < disliked.size(); ++j) {
        if (words[i] == disliked[j]) {
          found = true;
          break;
        }
      if (not found)    
        cout << words[i] << " ";
      else
        cout << "BLEEP" << " ";
    }

这基本上是你将使用std::find调用的代码。请注意，std::set的find方法使用一种不同的方法，通常使用red-black tree实现，这种方法更加高效。

- log0

Answer 5

你基本上想要检查所有元素是否相同。最好的方法是使用set。如果你需要vector做其他事情，最快的方法是对vector进行排序，遍历它并检查任何后续元素是否相同（O(n log(n) + n)）。如果你的向量不大，用两个循环的答案就可以完成任务（O(n^2)）。

- Klark