最适合快速查找的STL容器

Question

我需要存储一个整数列表，并能够快速确定某个整数是否已经存在于该列表中。不会存储重复的值。

我不会插入或删除任何值，但我会添加值（可能会被实现为插入）。

哪种STL容器类最适合这种情况？我在Google上找到了std::multimap，但那似乎需要一个键/值对，而我并没有。

我对STL还比较新，请给些建议吗？

- Jonathan Wood

---

未来参考，请点击此处查看所有标准容器的列表。 - François Andrieux

无序集合（unordered_set）是一个存储 int 类型元素的集合容器。 - Retired Ninja

@FrançoisAndrieux：谢谢你。但我不清楚哪个查找速度最快。set似乎是一个可能性。但是，我还不确定它有多快。 - Jonathan Wood

整数将落在哪个值范围内？ - 1201ProgramAlarm

您已经给出了复杂度，但是通常需要基准测试来适应您的使用时间（线性搜索可能比使用缓存、分支预测等技术的二进制搜索更快）。 - Jarod42

Answer 1

如果值和键不是分离的，可以使用set代替map。

可以使用不存储重复项的非多重版本来替代multiset/-map。

作为替代方案，您可以使用std::unordered_set。在您的用例中，它可能更快。

还有其他不太通用的数据结构可用于表示整数集合，其中一些根据用例可能更有效。但这些其他数据结构并不一定由标准库提供。

但我不清楚哪个查找速度最快。

无序集比有序集具有更好的查找渐近复杂度。是否适用于您的用例，可以通过测量来确定。

不太可能超过一千左右

在这种情况下，渐近复杂度未必相关。

特别是对于这样的小集合，排序向量可能会非常高效。鉴于您“不会插入或删除任何值”，向量也不应具有显着的缺点。标准库没有提供一个使用排序向量内部实现的集容器，但它提供了一个向量容器以及所有必要的算法。

我不知道容器如何计算哈希。

您可以为无序容器提供哈希函数。默认情况下，它使用std::hash。std::hash使用一个实现定义的哈希函数。

- eerorika

Answer 2

std::unordered_set<int> 是一个很好的选择，用于跟踪 int 的重复项，因为平均插入和查找都可以在常数时间内完成。

---

插入

使用insert()成员函数可以将新的int插入到集合中：

std::unordered_set<int> s;
s.insert(7);

查找

可以使用find()成员函数来检查集合中是否存在给定的int：

bool is_present(const std::unordered_set<int>& s, int value) {
   return s.find(value) != s.end();
}

- JFMR