如何测试无序序列 (C++) 中的项目成员资格？

Question

我已经使用python很长时间了，并且刚刚开始使用C++

在python中，如果有一个集合或字典，那么相对容易获得一个布尔值来指示特定项目是否在该序列中使用 in 关键字。 也就是说，

a = set(2,4,3)   
if 4 in a  
print "yes, 4 is in a, thank you for asking!"

它比这样做更有效：

a = [2,3,4]  
for number in a
>if number == 4  
>>return "yes, 4 is in a, thank you for asking!"

有没有一种方法可以使 cpp 中的成员资格测试变得简单而高效，或者您是否总是必须迭代某些有序序列？

Answer 1

您在 std::set 和 tr1::unordered_set （不是但在 C++ 标准中）。

#include <set>
#include <cstdio>

int main() {
     std::set<int> s;
     s.insert(1);        
     s.insert(2);
     s.insert(4);
     if (s.find(4) != s.end())
          puts("4 found!");
     return 0;
}

实际上，如果您的数据集很小，线性搜索可能仍然是更快的选择。

Answer 2

了解 C++ 标准模板库。 set 类（和其他类）有一个 find() 方法，该方法将返回指向集合中某个项目（如果存在）的迭代器。

Answer 3

查看 STL 提供的容器及其性能特征。

Answer 4

Python 的方法并不是“高效得多”，因为你不知道 in 构造的复杂性。

C++中有很多存储数据的方法。二叉树最适合搜索。

如果您使用 2、3、4 等数字，您可以考虑使用布尔数组，并简单地查看是否 array[4] == true

Answer 5

template<typename T>
bool contains(const std::set<T>& a, const T& value) {
    return a.find(value) != a.end();
}

if (contains(a, 4)) {
    std::cout << "A contains 4\n";
}

Answer 6

std::find 可以判断某个元素是否存在存在于任何无序容器或序列中。如果序列是无序的并且没有存储在为查找而设计的专用容器中，那么您不可能做得比 O(N) 更好。