c++ - C++ 中的存在图

Question

我想要一个类似std::map的东西，但我只想看看该项目是否存在，我实际上不需要一个键和一个值。我应该使用什么？

Answer 1

看起来你需要一个std::set。

Answer 2

如果您想要与 相同类型的行为std::map，那么您想要std::set.

如果您正在混合插入/删除和查询操作，那么std::set可能是最好的选择。但是，如果您可以先填充集合，然后使用查询跟随它，则可能值得查看使用std::vector、对其进行排序，然后使用二分搜索来检查向量中是否存在。

Answer 3

如果你真的只需要存在，甚至不需要命令，你需要一个unordered_set. 它可以从您最喜欢的 C++0x 供应商或boost.org 获得。

Answer 4

如果您的数据是数字的，您可以使用针对空间优化的 std::vector：

D:\Temp>type vectorbool.cpp
#include <iostream>
#include <vector>

using namespace std;

int main() {
        vector<bool> vb(10);
        vb[5] = true;

        for (vector<bool>::const_iterator ci = vb.begin(); ci != vb.end(); ++ci) {
                cout << *ci << endl;
        }
}

D:\Temp>cl /nologo /W4 /EHsc vectorbool.cpp
vectorbool.cpp

D:\Temp>vectorbool.exe
0
0
0
0
0
1
0
0
0
0

Answer 5

你可能应该看看stl::set你需要什么。Astl::bitset是另一种选择。

这将取决于您需要如何使用将定义哪些更好的信息。Aset是一个有序的数据结构，插入、查找和删除需要O(LOG N)时间。但是，如果您需要遍历标记为“存在”的所有值，那么这set是要走的路。

如果您只需要标记和查找某物是集合成员的事实bitset，那么这可能对您更好。插入、查找和删除只需要 O(1)，但你只能收集int值。遍历所有标记的值将花费 O(N)，因为您需要遍历整个集合以找到设置为 的成员true。您可以将它与stl::map一起使用，以将您拥有的值映射到所需的数值bitset。

查看您需要对集合中的值执行的操作，您应该能够选择适当的数据结构

Answer 6

您可以继续将 std::map 用于所需目的。

要检查地图中是否存在特定项目（键类型），您可以使用以下代码：

if (mapObj.count(item) != 0)
{
   // item exists
}

如前所述， std::set 也可以完成这项工作。有趣的是，set 和 map 在内部都表示为 Trees。

Answer 7

如果键是值，那么您也可以考虑使用“bloom 过滤器”而不是集合。