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

Question

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

方法1：

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]; ... */
}

方式三：

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

方式4：

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

Answer 1

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

除此之外，您发布的选项几乎是等效的。唯一值得注意的区别是，在方法1和方法的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) { /* ... */ }

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

请注意，使用C ++ 17中的并行算法功能，您还可以尝试

#include <algorithm>
#include <execution>

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

但是，这是否比普通循环快要取决于环境细节。

Answer 2

优先于索引/键的迭代器。

尽管形式^1的 for vector或array两者之间应该没有区别，但进入其他容器是一个好习惯。

_{^1当然， 只要您使用[]而不是.at()用于通过索引进行访问。}

记住底限。

由于以下两个原因，在每次迭代时重新计算结束边界的效率很低：

• 通常：局部变量没有别名，这对优化程序更友好。
• 在除矢量以外的其他容器上：计算末端尺寸可能会更昂贵。

您可以单线执行此操作：

for (auto it = vec.begin(), end = vec.end(); it != end; ++it) { ... }

（这是一般禁止一次声明一个变量的例外。）

使用for-each循环形式。

for-each循环表单将自动：

• 使用迭代器。
• 记住底限。

从而：

for (/*...*/ value : vec) { ... }

按值获取内置类型，按引用获取其他类型。

在按值获取元素和按引用获取元素之间存在明显的权衡：

• 通过引用获取元素可以避免复制，这可能是一项昂贵的操作。
• 按值获取元素对优化器更友好¹。

在极端情况下，选择应该显而易见：

• 内置类型（int，std::int64_t，void*，...），应通过采取价值。
• 潜在的分配类型（std::string，...）应该作为参考。

在中间，或者遇到通用代码时，我建议从引用开始：避免性能下降比尝试挤出最后一个循环更好。

因此，一般形式为：

for (auto& element : vec) { ... }

如果您正在处理内置的：

for (int element : vec) { ... }

_{¹ 这实际上是优化的一般原则：局部变量比指针/引用更友好，因为优化器知道局部变量的所有潜在别名（或缺少别名）。}

Answer 3

除了lubgr的答案：

除非您通过对相关代码进行概要分析发现瓶颈，否则效率（不是用来表示“效率”）可能不是您的首要考虑因素，至少不是在此级别的代码上。更重要的是代码的可读性和可维护性！因此，您应该选择效果最好的循环变体，通常是方法4。

如果步长大于1（无论何时需要...），则索引可能非常有用：

for(size_t i = 0; i < v.size(); i += 2) { ... }

虽然+= 2本质上在迭代器上也是合法的，但是如果向量的大小为奇数，则可能会在循环结束时冒未定义行为的风险，因为您会增加一个超过结束位置的值！（通常说来：如果大小不是n的整数倍，则将n递增，则得到UB 。）因此，在不使用index变体的情况下，您需要其他代码来捕获它。