用于检查有序数据是否在集合中的C++容器

只是想详细说明一下已经说过的话。

分类容器

不变性在这里非常重要: std::map 和 std::set 由于插入、检索和删除操作的要求(尤其是由于迭代器要求的无效性),通常以二叉树(少数STL版本的红黑树)的形式实现。

然而,由于不可变性,正如您怀疑的那样,还有其他候选者,尤其是像数组一样的容器。它们在这里有一些优势:

• 最小开销(内存方面)
• 内存的连续性,从而缓存位置

这里有几个“随机访问容器”:

• Boost.Array
• std::vector
• std::deque

因此,你真正需要做的事情只有两个步骤:

• 将所有值推送到所选容器中,然后(插入所有值之后)使用 std::sort 关于它。
• 使用搜索值 std::binary_search ,其复杂性为o(log(n))。

由于缓存位置的原因,即使渐进行为相似,搜索实际上也会更快。

如果你不想重新发明轮子,你也可以检查亚历山德里斯科的 [AssocVector][1] . Alexandrescu基本上移植了 标准::设置 和 STD::地图 接口 标准::矢量 以下内容:

• 因为它对小数据集来说更快
• 因为对于冻结的数据集来说,它可以更快

未分类的容器

实际上,如果你真的不在乎订单,而且你的收藏量很大,那么 unordered_set 会更快,尤其是因为整数对于哈希来说太小了 size_t hash_method(int i) { return i; } .

这可以很好地工作…除非您面临一个以某种方式导致大量冲突的集合,否则未排序的容器将在线性时间内搜索给定哈希的“冲突”列表。

结论

试一试 排序的 STD::载体 方法和 boost::unordered_set 使用“真实”数据集(以及所有优化)进行处理,然后选择能给您带来最佳结果的数据集。

不幸的是,我们不能在那里提供更多帮助,因为它在很大程度上取决于数据集的大小及其元素的重新划分。

如果数据在有序的随机访问容器中(例如 std::vector , std::deque 或者一个普通数组),然后 std::binary_search 将查找一个值是否以对数时间存在。如果您需要找到它的位置,请使用 std::lower_bound (也是对数的)。

使用A sort 预计起飞时间 std::vector 并使用 std::binary_search 搜索它。

您的其他选项将是HASHMAP(不在C++标准中) 然而 但还有其他选择,例如 SGI's hash_map 和 boost::unordered_map ) std::map .

如果你从不添加到你的集合中,使用二进制搜索的排序向量很可能比地图有更好的性能。

我建议使用std::vector<int>来存储它们,并使用std::binary_search或std::lower_bound来检索它们。

std::unordered_set和std::set都会增加大量的内存开销-即使unordered_set提供O(1)查找,O(logn)二进制搜索可能会优于它,因为数据是连续存储的(没有指针跟随,更少的页面错误等),并且您不需要计算哈希函数。

如果您已经有一个有序的数组或 std::vector<int> 或类似的数据容器,您只需使用 std::binary_search 探测每个值。没有设置时间,但是每个探针都需要O(log n)时间,其中n是您得到的有序整数。

或者,可以使用某种哈希,例如 boost::unordered_set<int> . 这将需要一些时间来设置,可能需要更多的空间,但每个探针平均需要O(1)时间。(对于小的n,这个o(1)可能比以前的o(log n)多。当然,对于较小的n,时间可以忽略不计。)

看什么都没有意义 std::set 或 std::map ,因为它们没有比二进制搜索更好的优势,因为要匹配的数字列表在初始化后不会改变。

所以,问题是n的近似值,以及您打算探测表的次数。如果您不想检查许多值以查看它们是否在提供的ints中,那么设置时间非常重要,并且 std::二进制搜索 在经过分类的容器上是一条路。如果要检查很多值,可能需要设置哈希表。如果n很大,哈希表的探测速度将比二进制搜索快,如果探测次数多,这是主要成本。

因此,如果要比较的整数的数量相当小,或者探针值的数量很小,则使用二进制搜索。如果int的数目很大,探测的数目也很大,那么使用哈希表。