c++ - 迭代 std::vector 的最有效方法是什么，为什么？

Question

就时空复杂度而言，以下哪一项是迭代 std::vector 的最佳方式，为什么？

方式一:

for(std::vector<T>::iterator it = v.begin(); it != v.end(); ++it) {
    /* std::cout << *it; ... */
}

方式 2:

for(std::vector<int>::size_type i = 0; i != v.size(); i++) {
    /* std::cout << v[i]; ... */
}

方式 3:

for(size_t i = 0; i != v.size(); i++) {
    /* std::cout << v[i]; ... */
}

方式 4:

for(auto const& value: a) {
     /* std::cout << value; ... */

Answer 1

首先，Way 2 和 Way 3 在几乎所有标准库实现中都是相同的。

除此之外，您发布的选项几乎相同。唯一显着的区别是，在 Way 1 和 Way 2/3 中，您依赖编译器来优化对 v.end() 的调用> 和 v.size() 出来。如果该假设正确，则循环之间没有性能差异。

如果不是，方式 4 是最有效的。回想一下基于范围的 for 循环如何扩展为

{
   auto && __range = range_expression ;
   auto __begin = begin_expr ;
   auto __end = end_expr ;
   for ( ; __begin != __end; ++__begin) {
      range_declaration = *__begin;
      loop_statement
   }
}

这里的重要部分是这保证了 end_expr 只被评估一次。另请注意，要使基于范围的 for 循环成为最有效的迭代，您不得更改迭代器取消引用的处理方式，例如

for (auto value: a) { /* ... */ }

这会将 vector 的每个元素复制到循环变量value中，这可能比for (const auto& value : a)慢，具体取决于大小 vector 中的元素。

请注意，使用 C++17 中的并行算法工具，您也可以尝试

#include <algorithm>
#include <execution>

std::for_each(std::par_unseq, a.cbegin(), a.cend(),
   [](const auto& e) { /* do stuff... */ });

但这是否比普通循环更快取决于可能的环境细节。