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

ekqde3dh  于 2023-05-20  发布在  其他
关注(0)|答案(9)|浏览(211)

就时空复杂度而言,以下哪种方法是迭代std::vector的最佳方法,为什么?

方式一:

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

方式二:

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

方式四:

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

eivnm1vs1#

首先,Way 2Way 3在几乎所有标准库实现中都是相同的。
除此之外,你发布的选项几乎是等同的。唯一显著的区别是,在Way 1Way 2/3中,依赖编译器优化对v.end()v.size() out的调用。如果这个假设是正确的,那么两个循环之间就没有性能差异。
如果不是,方式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) { /* ... */ }

这将向量的每个元素复制到循环变量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... */ });

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

tf7tbtn2

tf7tbtn22#

更喜欢迭代器而不是索引/键。

虽然对于vectorarray,form 1之间应该没有区别,但对于其他容器来说,这是一个好习惯。
1* 当然,只要你使用[]而不是.at()来按索引访问。*

记住结束绑定。

由于两个原因,在每次迭代时重新计算端界是低效的:

  • 一般来说:局部变量没有别名,这对优化器更友好。
  • 在vector以外的容器上:计算末端/大小可能稍微昂贵一些。

您可以使用一行程序来执行此操作:

for (auto it = vec.begin(), end = vec.end(); it != end; ++it) { ... }
  • (这是一般禁止一次声明一个变量的例外。

使用for-each循环形式。

for-each循环表单将自动:

  • 使用迭代器。
  • 记住终点。

因此:

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

内置类型取值,其他类型取引用。

在按值获取元素和按引用获取元素之间有一个不明显的权衡:

  • 通过引用获取元素可以避免复制,而复制操作的开销很大。
  • 按值取元素更有利于优化1。

在极端情况下,选择应该是显而易见的:

  • 内置类型(intstd::int64_tvoid*,...)应该按值取。
  • 潜在的分配类型(std::string,...)应该通过引用来获取。

在中间,或者当面对泛型代码时,我建议从引用开始:最好避免性能悬崖,而不是试图挤出最后一个周期。
因此,一般形式为:

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

如果你正在处理一个内置的:

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

1* 这是优化的一般原则,实际上:局部变量比指针/引用更友好,因为优化器知道局部变量的所有潜在别名(或不存在别名)。

7gs2gvoe

7gs2gvoe3#

添加到lubgranswer
除非你通过分析发现有问题的代码是一个瓶颈,否则效率(你可能是指效率而不是“有效性”)不应该是你的首要关注点,至少在这个级别的代码上不应该。更重要的是代码的可读性和可维护性!所以你应该选择读起来最好的循环变量,通常是方式4。
如果步长大于1,则索引可能很有用(无论何时您都需要...):

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

虽然+= 2本身在迭代器上也是法律的的,但如果向量的大小是奇数,那么在循环结束时会有未定义行为的风险,因为你的增量超过了结束位置的1!(一般来说:如果你递增 n,如果size不是 n 的整数倍,你会得到UB。)所以你需要额外的代码来捕捉这个,而你不需要索引变量...

csga3l58

csga3l584#

懒惰的回答:复杂性是相等的。

  • 所有解的时间复杂度为Θ(η)。
  • 所有解的空间复杂度为Θ(1)。

各种解决方案中涉及的恒定因素是实现细节。如果您需要数字,那么您最好在您的特定目标系统上对不同的解决方案进行基准测试。
存储v.size() rsp可能会有帮助。v.end(),尽管这些通常是内联的,因此可能不需要这样的优化,或者performed automatically
请注意,索引(不需要记忆v.size())是正确处理可能添加额外元素(使用push_back())的循环体的唯一方法。但是,大多数用例不需要这种额外的灵活性。

4szc88ey

4szc88ey5#

更喜欢方法4,std::for_each(如果你真的需要),或者方法5/6:

void method5(std::vector<float>& v) {
    for(std::vector<float>::iterator it = v.begin(), e = v.end(); it != e; ++it) {
        *it *= *it; 
    }
}
void method6(std::vector<float>& v) {
    auto ptr = v.data();
    for(std::size_t i = 0, n = v.size(); i != n; i++) {
        ptr[i] *= ptr[i]; 
    }
}

前3种方法可能会遇到指针别名问题 (如前面的答案中所提到的),但它们都同样糟糕。考虑到可能有另一个线程 * 可能 * 正在访问这个向量,大多数编译器都会谨慎行事,并在每次迭代中重新计算[] end()和size()。这将阻止所有SIMD优化。
你可以在这里看到证据:
https://godbolt.org/z/BchhmU
你会注意到只有4/5/6使用了vmulps SIMD指令,而1/2/3只使用了非SIMD的vmulss指令。
注意:我在godbolt链接中使用VC++,因为它很好地演示了这个问题。gcc/clang也会出现同样的问题,但用godbolt演示并不容易--通常需要拆开DSO才能看到这种情况。

oknwwptz

oknwwptz6#

为了完整起见,我想提一下你的循环可能想改变向量的大小。

std::vector<int> v = get_some_data();
for (std::size_t i=0; i<v.size(); ++i)
{
    int x = some_function(v[i]);
    if(x) v.push_back(x);
}

在这样的示例中,您必须使用索引,并且必须在每次迭代中重新计算v.size()
如果你对一个基于范围的for循环或迭代器做同样的事情,你可能会以 undefined behavior 结束,因为向向量添加新元素可能会使你的迭代器无效。
顺便说一下,我更喜欢使用while-循环来处理这种情况,而不是for-循环,但这是另一回事。

t5fffqht

t5fffqht7#

这在很大程度上取决于你所指的“有效”。
其他的答案都提到了 * 效率 *,但我将专注于C++代码最重要的目的:将您的意图传达给其他程序员¹。
从这个Angular 来看,方法4显然是最有效的。不仅仅是因为要阅读的字符更少,主要是因为认知负荷更少:我们不需要检查边界或步长是否异常,循环迭代变量(iit)是否在其他地方被使用或修改,是否有打字错误或复制/粘贴错误,如for (auto i = 0u; i < v1.size(); ++i) { std::cout << v2[i]; },或数十种其他可能性。
快速测验:给定std::vector<int> v1, v2, v3;,以下循环中有多少是正确的?

for (auto it = v1.cbegin();  it != v1.end();  ++it)
{
    std::cout << v1[i];
}

for (auto i = 0u;  i < v2.size();  ++i)
{
    std::cout << v1[i];
}

for (auto const i: v3)
{
    std::cout << i;
}

尽可能清楚地表达循环控制可以让开发人员的头脑对高级逻辑有更多的理解,而不是被实现细节弄得一团糟--毕竟,这就是我们首先使用C++的原因!
要明确的是,当我写代码时,我认为最重要的“其他程序员”是未来的我,试图理解,“谁写了这些垃圾?”*"...

t98cgbkg

t98cgbkg8#

你列出的所有方法都具有相同的时间复杂度和空间复杂度(这并不奇怪)。
使用for(auto& value : v)语法稍微更有效,因为使用其他方法时,编译器可能会在每次执行测试时从内存中重新加载v.size()v.end(),而使用for(auto& value : v)时,这种情况永远不会发生(它只加载begin()end()迭代器一次)。
我们可以在这里观察每种方法产生的组件的比较:https://godbolt.org/z/LnJF6p
有趣的是,编译器将method3实现为method2jmp指令。

sqougxex

sqougxex9#

除了最后一个算法理论上更快之外,所有算法的复杂度都是一样的,因为容器的末尾只计算一次。
最后一个也是最好读和写的,但有一个缺点,那就是没有给予你索引(这通常是很重要的)。
然而,你忽略了我认为是一个很好的替代方案(当我需要索引而不能使用for (auto& x : v) {...}时,这是我的首选方案):

for (int i=0,n=v.size(); i<n; i++) {
    ... use v[i] ...
}

注意,我使用了int而不是size_t,并且end只计算一次,并且在主体中也可以作为局部变量使用。
通常,当需要索引和大小时,也会对它们执行数学计算,并且size_t在用于数学时表现得“奇怪”(例如a+1 < ba < b-1是不同的东西)。

相关问题