在循环中正确检查 std::vector 大小的方法

Question

我是一位有用的助手，可以帮助您翻译文本。

我有一个std::vector需要经常循环。 我看到两种方法可以做到：

第一种方法：

const size_t SIZE = myVec.size();
for (size_t i = 0; i < SIZE; i++)
{
    myVec[i] = 0;
}

第二种方式：

for (size_t i = 0; i < myVec.size(); i++)
{
    myVec[i] = 0;
}

第一种实现比第二种更有效，或者现代编译器知道如何优化第二种实现，使其与第一种一样有效吗？

顺便说一下，我在使用Visual Studio 2013。

- The Vivandiere

---

任何一个不错的编译器都应该能够优化第二种方法；但是要确定最好还是进行测试。那么for (auto & x : myVec) x = 0;这种方式呢？或者使用std::fill(myVec.begin(), myVec.end(), 0)？ - Mike Seymour

@MikeSeymour是正确的：这是std::fill或std::fill_n的工作。 - Jerry Coffin

еңЁиҝҷз§Қжғ…еҶөдёӢпјҢжӮЁеҸҜд»ҘдҪҝз”Ёstd::generateжҲ–std::generate_nгҖӮ std::generate(myVec.begin(), myVec.end(), [=]{ return a+b*c+d*e/f; }); - Jerry Coffin

@user3670482：那么你可能想要通过引用而不是值进行捕获：[&]{/* ... */}（当然，你只能使用为它们定义的语法，所以 a+b 不会起作用，除非你在某个地方定义了它）。 - Jerry Coffin

@user3670482 因为当你遇到同名的预处理器宏时，你会花费很多时间来破解晦涩难懂的错误信息。 - Slava

Answer 1

第一个版本通常会更快，即使使用现代编译器也是如此。优化器难以证明大小不会因循环体中写入位置的别名而改变，因此在许多情况下，第二个版本将不得不在每次循环迭代中重新计算大小。

我在Visual Studio 2013 Release中进行了测量，并发现32位和64位代码都存在性能差异。 std :: fill（）轻松击败了两个版本。这些测量是对1000次运行的平均值，使用了1000万个元素向量（将元素数量增加到10亿会略微减少性能差异，因为内存访问成为瓶颈）。

Method                   Time relative to uncached for loop
                         x86      x64

uncached for loop        1.00     1.00
cached for loop          0.70     0.98
std::fill()              0.42     0.57

循环代码的基本缓存大小：

const auto size = vec.size();
for (vector<int>::size_type i = 0; i < size; ++i) {
    vec[i] = val;
}

编译成这个循环体（x86 Release）：

00B612C0  mov         ecx,dword ptr [esi]  
00B612C2  mov         dword ptr [ecx+eax*4],edi  
00B612C5  inc         eax  
00B612C6  cmp         eax,edx  
00B612C8  jb          forCachedSize+20h (0B612C0h)  

如果不缓存向量的大小，则版本如下：

for (vector<int>::size_type i = 0; i < vec.size(); ++i) {
    vec[i] = val;
}

编译后的代码会在每次循环时重新计算vec.size()：

00B612F0  mov         dword ptr [edx+eax*4],edi  
00B612F3  inc         eax  
00B612F4  mov         ecx,dword ptr [esi+4]            <-- Load vec.end()
00B612F7  mov         edx,dword ptr [esi]              <-- Load vec.begin()
00B612F9  sub         ecx,edx                          <-- ecx = vec.end() - vec.begin()
00B612FB  sar         ecx,2                            <-- exc = (vec.end() - vec.begin()) / sizeof(int)
00B612FE  cmp         eax,ecx  
00B61300  jb          forComputedSize+20h (0B612F0h)  

- mattnewport

Answer 2

我更喜欢像第一种情况那样编写循环。使用第二种情况和std::vector::size()时，您可能会在编译器优化版本中支付一些额外的加载成本，但是当您开始使用更复杂的数据结构时，这些简单的加载可能会变得昂贵，因为需要进行树形查找。

即使有偏好，上下文有时也要求您以第二种形式编写循环。第一种情况暗示容器的大小没有发生变化，因为容器大小只检查了一次。当您阅读第二种情况时，容器大小在每次迭代中都会被检查，这提示用户主体可能会改变容器的大小。

如果您在循环体中修改容器，请使用第二种形式并注释说明您正在修改容器并希望检查其大小。否则，请使用第一种形式。

- Snowhawk

Answer 3

在任何像样的现代C++编译器中，这两个版本在性能方面不会有任何区别，因为优化器会优化掉任何恶化 。然而，我使用以下版本：

for (size_t i(0), ie(myVec.size()); i < ie; ++i) {
    // do stuff
}

- 101010

---

+1 但是请使用 for (size_t i = 0, sz = myVec.size(); i < sz; ++i)。直接初始化和不寻常的名称需要更多的阅读理解。我知道这只是小问题，但在大型代码库中，这些问题会累积起来。 - TemplateRex

任何像样的编译器都能够优化掉这种差异并不是真的。就像任何涉及性能的问题一样，在做出此类陈述之前，您确实应该进行测试。 - mattnewport

@mattnewport 噢，这非常非常正确。只是恰巧你对此一无所知。 - 101010

我进行了测量，发现在Visual Studio 2013的优化构建中，这确实会对性能和代码生成产生影响。这也是可以预料的——由于向量大小的可能别名，代码的语义不同，许多编译器将无法优化每次循环迭代重新加载大小。这就是导致Visual Studio性能差异的原因。两个版本的速度都比调用std::fill()慢得多。 - mattnewport

Answer 4

如此处所述，vector<T>::size的复杂度必须在所有编译器上保持恒定，因此您使用哪个编译器并不重要。

- Nikola Dimitroff

---

并非一定如此，复杂度是不变的，但不一定与本地存储相同。 - CashCow

Answer 5

获取向量的大小始终是恒定时间。

你的算法可能效率不高的地方在于每个索引使用myVec[i]。它会每次提取指针并将'i'添加到其中。指针算术运算很可能会胜过它的性能，如果你使用vector的iterator，因为它很可能被实现为指针，它可能会比你的循环更快。

如果你要将所有值设置为0，你可以通过单个函数调用而不是循环来完成，这种情况下：

myVec.assign( myVec.size(), 0 );

- CashCow