C++ for循环：条件的评估

Question

我有一个关于循环的（愚蠢？）C / C++问题：

for (size_t i = 0; i < std::distance(begin, end); ++i) {
  a.push_back(i);
}

begin和end是两个迭代器。我的问题是，std::distance(begin, end)在循环中是否为每个元素计算？还是使用这个版本更好：

size_t dist = std::distance(begin, end);
for (size_t i = 0; i < dist; ++i) {
  a.push_back(i);
}

- martinus

---

我不是完全确定，但我认为第一个可能会慢得多。我不认为编译器能够确定 std::distance(begin, end) 是常数，但我可能错了。 - flight

@quasiverse：恐怕你错了 :-S 由于迭代器类别和特性检查，随机访问迭代器允许实现distance的常数时间。看看你的编译器实现吧！ - Kerrek SB

一个简化且相关的问题是，在 for (auto it = v.begin(); it != v.end(); ++it) 中，对 v.end() 的调用是否在每轮中执行。标准要求程序表现得好像每次都被调用一样，因此编译器只能在它能证明结果始终相同（并且没有副作用）时将其优化掉。 - Kerrek SB

@Kerrel：如果它是随机访问迭代器。但是quasiverse说它可能会慢得多。例如，当begin/end不是随机访问时，distance是否被提升就变得非常重要。如果编译器无法执行，则程序员应该这样做。 - Steve Jessop

请注意，如果需要，您可以在循环内部限定额外变量的作用域：for (size_t i = 0, dist = std::distance(begin, end); i < dist; ++i)。 - Mike Seymour

Answer 1

第二个版本更好。在第一个版本中，条件每次被评估（没有关于结果不变的自动假设）。

- cma

Answer 2

是的，第二个版本更好。

至于第一个版本，如果容器类型a是std::vector，并且begin和end是a的迭代器，则push_back操作可能会导致向量大小调整，从而使begin和end迭代器失效，并且在下一次迭代中使用它们计算距离将引发未定义行为。 在这种情况下，第二种方法不仅更好，而且也被明确定义。

- Nawaz

---

等等，谁说begin和end是a的迭代器了？ - Kerrek SB

@KerrekSB：好观点。我就是这么假设的 :P。让我在我的答案中加入这个假设。 - Nawaz

我非常确定迭代器实际上不能指向所讨论的容器，否则该循环将永远不会终止（除非OP实际上对此有所困惑，但我没有这样的印象）。 - Kerrek SB

@KerrekSB：也许是，也许不是。我只是想记录一下这个。 - Nawaz

@Kerrek：但从优化的角度来看，提问者是否对问题感到困惑并不重要，重要的是编译器是否知道循环不是无限的！当然，如果没有看到周围的代码，我们无法确定编译器知道什么。 - Steve Jessop

Answer 3

很可能这取决于编译器优化。如果它们被关闭，std::distance将在每次循环中执行，这是确定的。原因是迭代器可能在循环体内被更改。

所以，如果你没有改变迭代器，尽管它非常小，还是应该选择第二个版本进行优化。在大多数情况下，这是个人选择的问题（如果这不是瓶颈，这是非常不可能的）。

编辑：我的答案假设您代码中的begin和end不是向量（或其他东西）a的begin和end。如果是，那么你实际上想要做什么就取决于你的问题。

- Kiril Kirov

---

即使输入不变，返回值也可能会改变。是的，std::distance() 不会像这样工作，但编译器/优化器无法知道（通用）。 - mah

是否真的有编译器足够智能，能够意识到 std::distance 的值是不变的？ - Raedwald

@Raedwald：当然，这取决于begin和end是什么。例如，使用std::vector<int> v(5); std::vector<int>::const_iterator begin = v.begin(), end = v.end();，在GCC 4.5.3中使用-O2，我在循环中得到了add $0x1,%ebx // cmp $0x5,%ebx。它不仅意识到std::distance结果是不变的，而且在编译时计算它。 - Steve Jessop

Answer 4

如果不进行优化，每次都需要计算。在实践中进行优化后，这应该不会有什么影响。如果不希望每次都计算（例如因为这是您要执行的最内部操作），您可以始终选择第二个选项以确保安全。

- b.buchhold

---

即使进行了优化，它也应该有所改变...编译器不知道std::distance(begin, end)会返回一个常量值，因此它必须检查每个迭代。 - mah

我不是100%确定。我假设std::distance将被内联处理，并且进一步的优化可能能够检测到结果不可能改变。 - b.buchhold

"可能能够", 但这取决于许多因素。 - curiousguy

Answer 5

编译器能否执行优化取决于所涉及的类型。例如，如果begin和end是列表迭代器，a是一个列表，并且end是在a末尾的迭代器，则这是一个无限循环（直到发生内存不足）。如果更改程序的含义，编译器无法进行“优化”。假设它不会更改程序的含义，否则您就不会提出问题，但编译器必须以某种方式排除这种可能性，例如通过跟踪从何处设置了end的值。在某些情况下，您可能会发现这很明显，但超出了编译器证明的能力。

相反，如果begin和end是向量迭代器，则实际上它们是指针或围绕其的薄包装器。然后，编译器可能能够看到它们的值在循环中永远不会改变，因此它们的距离永远不会改变，并进行优化。即使它没有进行优化，对于向量迭代器来说，distance也很便宜。因此，在这种情况下，优化可能并不那么重要。

相反地，向量迭代器的检查实现理论上可能包括代码来查看自迭代器被获取以来向量是否已重新分配（因此迭代器不再有效）。这个事实在循环中可能会改变，因此如果std::distance间接调用该检查，则在该实现中无法提升。虽然通常不会将检查迭代器与优化结合使用，但这是可能的。

一如既往，优化取决于实现。如果您真的关心，您需要查看您关心的编译器生成的代码。

至于你的第二个片段，有些人更喜欢这种风格：

for (size_t i = 0, dist = std::distance(begin, end); i < dist; ++i) {
  a.push_back(i);
}

它依赖于比较中的类型相同，但避免将dist放入不需要的周围作用域。

- Steve Jessop

Answer 6

两者的性能都将与任何良好的编译器将代码转换为第二个版本相同。如果关闭编译器优化，请使用第二个版本。

- r15habh

---

任何一个良好的编译器都会将代码转换成第二个版本。哪些编译器是“良好的”？ - curiousguy

主观的回答...但是任何能够正确执行基本功能并且在一般优化方面表现良好的编译器都是不错的编译器。现在，这些基本功能和一般优化的定义可能因人而异，使得整个“不错的编译器”概念有点主观 ;) - r15habh

list<>::iterator γö³ distance δΗçεÉè vector<>::iterator γö³ distance ι²ΘδΙàε°Ιφ‰™δ։娕ψIJ - curiousguy