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

Performance differences between std::count and std::find

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

如果您要查找的项目不在范围内,countfind都将遍历整个序列,因此两者的速度大致相同。

如果您要查找的项目 范围内,find 将在找到后 return。所以find会更快,找到的元素越靠近序列的前面。

一般不会执行"vectorize"这个算法。但是,在 std::vector<bool> 的情况下,一个实现 (libc++) 确实进行了优化。它优化了 count find 以一次查看 64 位(在 64 位平台上),因此这两个操作都将大大加快up 与 std::vector<char> 上的相同操作。这些优化描述如下:

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

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

为了找到这个问题的答案,我查看了这两个函数的行为。根据我在 C++ Reference 上可以找到的内容,std::count 函数的行为如下:

template <class InputIterator, class T>
  typename iterator_traits<InputIterator>::difference_type
    count (InputIterator first, InputIterator last, const T& val)
{
  typename iterator_traits<InputIterator>::difference_type ret = 0;
  while (first!=last) {
    if (*first == val) ++ret;
    ++first;
  }
  return ret;
}

std::find 函数如下所示:

template<class InputIterator, class T>
  InputIterator find (InputIterator first, InputIterator last, const T& val)
{
  while (first!=last) {
    if (*first==val) return first;
    ++first;
  }
  return last;
}

这意味着 std::count 函数将始终遍历整个向量,即使只能找到一个值。但是,std::find 函数实际上在找到该值时停止。这意味着如果您只想知道向量是否包含值,则 std::find 函数平均比 std::count 函数更快。如果您还想知道找到了多少,std::count 函数是最好的解决方案,尽管我认为这不是您的意图。

总的来说,这意味着 std::find 函数将与 std::count 函数一样快,甚至更快。

来源: http://www.cplusplus.com/reference/algorithm/find/ http://www.cplusplus.com/reference/algorithm/count/