c++ - std::count 和 std::find 之间的性能差异

Question

这可能是一个愚蠢的问题，但我想检查一个容器(在本例中是 bool 的 std::vector 但更广泛的方法会更好)到检查值是否存在。据我了解，运行时 std::count 和 std::find 都是线性的，如果项目在范围内，计数可能会变慢，但我认为两者都应该是如果对象存在，则相同，但我可以看到编译器可以向量化 std::count 和 因此 制作 std::count 的可能性跑得更快。我对第一个假设是否正确，即两者将运行相同，或者第二个假设是否编译器可以向量化 std::count 为真？

Answer 1

如果您正在寻找的项目是不在范围内，count和 find都将遍历整个序列，因此两者的速度大致相同。

如果您要查找的项目在范围内，find一旦找到就会返回。所以find找到的元素越靠近序列的前面，就会越快。

一般来说，实现不会“向量化”这个算法。但是，在 std::vector<bool> 的情况下, 一个实现 ( libc++ ) 确实优化了。它同时优化了 count 和 find一次查看 64 位(在 64 位平台上)，因此与 std::vector<char> 上的相同操作相比，这两个操作将大大加快.这些优化描述如下:

http://howardhinnant.github.io/onvectorbool.html

我不是很肯定(如果我错了，请随时纠正我，我很乐意是错的)，但我认为 libc++ 目前是进行这些优化的唯一实现。