C++ STL：哪种STL容器的迭代方法更好？

Question

对于一些人来说，这可能看起来是琐碎的问题，但以下两种遍历STL容器的方法哪种更好？为什么？

class Elem;
typedef vector<Elem> ElemVec;
ElemVec elemVec;

// Method 0
for (ElemVec::iterator i = elemVec.begin(); i != elemVec.end(); ++i)
{
    Elem& e = *i;
    // Do something
}

// Method 1
for (int i = 0; i < elemVec.size(); ++i)
{
    Elem& e = elemVec.at(i);
    // Do something
}

方法0看起来像是更干净的STL，但方法1用更少的代码实现了相同的功能。在任何源代码中都出现了对容器的简单迭代循环。因此，我倾向于选择似乎可以减少视觉混乱和代码大小的方法1。

PS：我知道迭代器可以做比简单的索引更多的事情。但请保持回复/讨论集中在像上面展示的简单容器迭代上。

- Ash

Answer 1

第一个版本适用于任何容器，因此在接受任何容器作为参数的模板函数中更有用。即使对于向量，它也可能略微更有效。

第二个版本仅适用于向量和其他整数索引的容器。对于这些容器来说，它更符合惯用法，新手易于理解，并且如果您需要执行其他操作而不是常见操作，则非常有用。

像往常一样，恐怕没有简单的“哪个更好”的答案。

- anon

---

谢谢Neil。我的代码通常不使用模板，而是使用已知类型的向量。您能详细说明一下为什么您在答案中提到的方法0更有效吗？ - Ashwin Nanjappa

如果迭代器直接实现为指针，则可能会稍微更有效率。请注意使用“可能”和“稍微”这些词语 - 您需要进行测量以确保。 - anon

是的，实际上对于大多数容器而言，迭代器只不过是一个指针。但是，这怎么能使代码更快呢？据我所知，即使是方法1最终也会变成指针算术运算，不是吗？ - Ashwin Nanjappa

@ash 是的，但是还需要进行算术运算 (ptr+index) 和 (index++)，更不用说如果 [] 没有被内联，它可能是一个函数调用。但正如我所说 - 你需要进行测量。 - anon

就记录而言，我从未看到过性能上的可衡量差异。 - Robert Gould

Answer 2

如果您不介意（非常）小的效率损失，我建议使用Boost.Foreach。

BOOST_FOREACH( Elem& e, elemVec )
{
    // Your code
}

- Benoît

---

我现在大多数情况下不会使用Boost。谢谢这个提示，Benoît！这很有用 :-) - Ashwin Nanjappa

+1，Benoît，我的程序到处都是循环，而BOOST_FOREACH让我保持理智，因为在使用其他支持真正foreach的语言之后。 - philsquared

C++也有真正的foreach支持：std::for_each。语法只是略有不同 ;) - jalf

Jalf: STL有for_each，但这几乎不是大多数循环的使用方式，因为它需要定义另一个函数。 - Ashwin Nanjappa

当lambda在C++09中出现时，stl::foreach将非常有用。 - Robert Gould

是的，C++1x将包含一个本地的for-each循环，无需使用那些begin/end混乱的数组即可在elemVec上工作。 - Johannes Schaub - litb

Answer 3

建议使用方法0，因为它更快。

方法1使用size()函数，具体取决于容器和STL实现，可能是O(1)的。

- Stefan

---

谢谢Stefan，我忘记了size() :-) - Ashwin Nanjappa

size() 应该在符合标准的向量中为O(1)。并且它与v.end()一样高效，因为它很可能会被内联。这里的效率是相同的（每次访问之间不超过几个指令的差异）。 - David Rodríguez - dribeas

@davidrodríguez-dribeas：效率通常不同，因为第一种方法需要额外的指针加载（即在添加偏移量之前加载数据指针）。如果您在此代码旁边有任何其他代码，则编译器可能会对别名产生困惑，并避免缓存该指针，使您从内存中发出两倍于所需的负载。这在一个琐碎的循环中不太可能发生，但在实践中并不常见。 - user541686

@Mehrdad：size()的缓存可能不是初始代码的问题（注释只针对size()的缓存）。在OP中，访问向量是通过at()进行的，这涉及到代码中的额外分支和一些额外的代码。 - David Rodríguez - dribeas

@DavidRodríguez-dribeas：我说的是指针缓存。size()不是指针。我在谈论begin()和end()--使用迭代器/指针通常比索引更快，因为它需要较少的加载。（at()显然更慢，但我在谈论常规、未经检查的索引。） - user541686

Answer 4

以下是迭代标准库容器的最佳方法。

使用c++11（及以上版本）的基于范围的for循环和auto限定符：

// Method 2
for (auto& e: elemVec)
{
    // Do something with e...
}

这与你的Method 0类似，但需要更少的打字、更少的维护，并且适用于任何与std::begin()和std::end()兼容的容器，包括普通的数组。

- johnsyweb

---

-1、auto＆是这个问题的正确等价物，而且这个代码是错误的，i不是一个迭代器。 - NoSenseEtAl

@NoSenseEtAl：谢谢你帮助我改进我的答案 ☺ - johnsyweb

Answer 5

方法0的一些优点：

• 如果您从向量移动到另一个容器，循环保持不变，
• 如果需要，易于从迭代器移动到const_iterator，
• 当c++0x到达时，自动类型将减少一些代码混乱。

主要缺点是在许多情况下您需要扫描两个容器，在这种情况下，使用索引比保留两个迭代器更清晰。

- David Lehavi

---

谢谢David。我猜你是指方法0吧;-) - Ashwin Nanjappa

是的，David，请你编辑你的答案以反映这一点吗？谢谢 :-) - Ashwin Nanjappa

Answer 6

恰巧最近我做了一个速度测试（用rand()函数填充10 * 1024 * 1024个整数）。
以下是3次运行的结果，时间以纳秒为单位。

vect[i] time      : 373611869  
vec.at(i) time    : 473297793  
*it = time        : 446818590  
arr[i] time       : 390357294  
*ptr time         : 356895778  

更新：添加了stl-algorithm std::generate，它似乎运行速度最快，因为有特殊的迭代器优化（VC++2008）。时间以微秒为单位。

vect[i] time      : 393951
vec.at(i) time    : 551387
*it = time        : 596080
generate = time   : 346591
arr[i] time       : 375432
*ptr time         : 334612

结论：使用标准算法，它们可能比显式循环更快！（也是良好的实践）

更新：上述时间是在I/O绑定情况下进行的。我用CPU绑定进行了相同的测试（迭代一个相对较短的向量，应该能够重复适合缓存，将每个元素乘以2并写回向量）。

//Visual Studio 2008 Express Edition
vect[i] time      : 1356811
vec.at(i) time    : 7760148
*it = time        : 4913112
for_each = time   : 455713
arr[i] time       : 446280
*ptr time         : 429595

//GCC
vect[i] time      : 431039
vec.at(i) time    : 2421283
*it = time        : 381400
for_each = time   : 380972
arr[i] time       : 363563
*ptr time         : 365971  

有趣的是，在VC ++中，迭代器和operator[]比for_each慢得多（似乎通过一些模板魔法将迭代器降级为指针以提高性能）。
在GCC中，只有at()的访问时间更差，这很正常，因为它是测试中唯一进行范围检查的函数。

- qwerty

---

几乎没有统计上的差异。除非在频繁使用的紧密循环中，否则大约10%的差异对实际使用的程序没有影响。一次缓存未命中，时间将会相等。 - Robert Gould

如果您定义了以下内容： #define _SECURE_SCL 0 #define _SECURE_SCL_THROWS 0 指针和迭代器的性能将没有区别。 - Vadim Ferderer

Answer 7

方法0，有几个原因：

• 它更好地表达了您的意图，这有助于编译器优化和可读性
• 偏移量错误的可能性较小
• 即使您将向量替换为不具有operator[]的列表，它也可以工作

当然，最好的解决方案通常是解决方案2：使用std算法之一。std::for_each、std::transform、std::copy或其他您需要的算法。这还有一些进一步的优点：

• 它更好地表达了您的意图，并允许一些重要的编译器优化（MS的安全SCL对您的方法0和1执行边界检查，但会跳过std算法）
• 它的代码量更少（至少在调用站点上是如此）。当然，您必须编写一个函数对象或类来替换循环体，但在使用站点上，代码会变得更加简洁，这可能是最重要的地方。

总的来说，避免过度指定代码。只指定您想要完成的任务，什么都不多。通常情况下，std算法是最佳选择，但即使没有它们，如果您不需要索引i，为什么要使用它？在这种情况下，使用迭代器。

- jalf

Answer 8

这取决于使用哪种类型的容器。对于 vector，可能使用哪种都无所谓。方法0已经更加惯用，但差别不大，正如每个人所说的那样。

如果您决定使用 list，那么原则上，方法1将是 O（N），但实际上没有 list at() 方法，因此您甚至无法以这种方式执行它。（所以在某种程度上，您的问题有点片面。）

但这本身又是支持方法0的另一个主张：它为不同的容器使用相同的语法。

- Andrew Jaffe

Answer 9

一个未被考虑的可能性是：根据“做某事”的具体细节，可以同时采用方法0和方法1，你不必选择其中一种。

for (auto i = elemVec.begin(), ii = 0; ii < elemVec.size(); ++i, ++ii)
{
    // Do something with either the iterator i or the index ii
}

这样，查找索引或访问相应成员都可以以微不足道的复杂度获得。

- user2747939