为什么要使用迭代器而不是数组索引？

Question

为什么要使用迭代器而不是数组索引？

281

考虑以下两行代码：

for (int i = 0; i < some_vector.size(); i++)
{
    //do stuff
}

还有这个：

for (some_iterator = some_vector.begin(); some_iterator != some_vector.end();
    some_iterator++)
{
    //do stuff
}

我被告知第二种方式更受欢迎。为什么呢?

- Jason Baker

77

若你将 some_iterator++ 修改为 ++some_iterator，则更倾向于使用第二种方式。因为后置自增会创建一个不必要的临时迭代器。 - jason

6

你还应该将 end() 加入声明子句。 - Lightness Races in Orbit

5

使用效率低下的vector::end(向量的结尾) 的C++实现，可能存在比它是否被提取出循环更值得担心的问题。就我个人而言，我更喜欢清晰易懂的代码——如果终止条件中涉及到find操作，那么我会感到有点担忧。 - Steve Jessop

13

@Tomalak: 这段代码并不邋遢（除了后置递增可能有点），就C++迭代器的允许范围而言，它是简洁明了的。增加更多的变量只是为了过早优化而增加认知负担，这才是邋遢的做法。 - Steve Jessop

8

如果它不是瓶颈，那么现在就进行还为时过早。你的第二点对我来说似乎很荒谬，因为正确的比较不是 it != vec.end() 和 it != end，而是 (vector<T>::iterator it = vec.begin(); it != vec.end(); ++it) 和 (vector<T>::iterator it = vec.begin(), end = vec.end(); it != end; ++it)。我不需要计算字符数。当然可以更喜欢其中一个，但别人对你偏好的异议并不是“粗心”，而是更喜欢变量更少、阅读时更易考虑的简化代码。 - Steve Jessop

显示剩余5条评论

27个回答

61

这是现代C++教化过程的一部分。迭代器是大多数容器迭代的唯一方式，所以即使在使用向量时也要使用它来进入正确的思维模式。说真的，这是我这样做的唯一原因——我从来没有用其他类型的容器替换过向量。

哇，三周后还在遭受投票否定。我猜开玩笑可不太好。

我认为数组索引更易读。它与其他语言使用的语法相匹配，也符合旧式C数组的语法。它也不那么冗长。如果你的编译器很好，效率应该差不多，而且几乎没有什么情况需要考虑效率。

即便如此，我仍然经常使用向量的迭代器。我认为迭代器是一个重要的概念，所以我尽可能地宣传它。

- Mark Ransom

2

C++ 迭代器在概念上也是非常糟糕的。对于向量，我刚刚被卡住了，因为结束指针实际上是 end+1(!)。对于流，迭代器模型就像超现实主义——一个不存在的虚构标记。链表同理。这种范式只对数组有意义，而且并不多。为什么我需要两个迭代器对象，而不是一个... - Tuntable

6

@aberglas，它们并不是完全损坏的，只是你还不习惯使用它们，这就是为什么我建议即使没有必要也要使用它们！半开区间是一个常见的概念，而从来不直接访问的哨兵和编程本身一样古老。 - Mark Ransom

4

看看流迭代器，并思考“==”被曲解以适应该模式的原因，然后告诉我迭代器没有损坏！即使是对于链表和数组也是如此。甚至对于数组来说，指定一个超过末尾的位置是一种破碎的 C 风格思想 - 指向永无止境的东西的指针。它们应该像 Java 或 C# 或任何其他语言的迭代器一样，只需要一个迭代器（而不是两个对象）和一个简单的结束测试。 - Tuntable

@MarkRansom 你的if语句是错误的，因为“intuitive”并不意味着在掌握它之前要练习一百万次。直觉意味着你自然能够使用这个东西。 - user13947194

@MarkRansom 这意味着一切都是直观的。 - user13947194

显示剩余3条评论

53

因为你没有将你的代码绑定到特定的 some_vector 列表实现上。如果使用数组索引，它必须是某种形式的数组；如果使用迭代器，你可以在任何列表实现中使用该代码。

- cruizer

24

std::list的接口有意不提供operator[](size_t n)，因为它的时间复杂度为O(n)。我的翻译是否能够满足您的要求？ - MSalters

35

假设 some_vector 是用链表实现的。那么请求第 i 个位置的项需要执行 i 次操作来遍历节点列表。但是，如果使用迭代器，一般来说，它会尽最大努力尽可能高效（在链表的情况下，它将维护对当前节点的指针并在每次迭代中将其推进，只需要执行单个操作）。

因此，它提供了两个东西：

使用的抽象性: 你只需要迭代某些元素，不需要关心如何做到这一点
性能

- asterite

1

它将维护一个指向当前节点的指针并将其推进[关于效率的好东西] - 是的，我不明白为什么人们难以理解迭代器的概念。从概念上讲，它们只是指针的超集。为什么要一遍又一遍地计算某个元素的偏移量，而不是缓存一个指向它的指针呢？好吧，这也是迭代器所做的。 - underscore_d

29

我这里要充当反对者，不建议使用迭代器。主要原因是，从桌面应用程序开发到游戏开发的所有源代码中，我从未使用过迭代器，也没有必要使用它们。每次都不需要它们，并且在需要速度的任何应用程序中，由于迭代器产生的隐藏假设、代码混乱和调试噩梦，它们成为了一个不应该使用的典型示例。

即使从维护的角度来看，它们也很混乱。问题不在于迭代器本身，而是因为幕后发生的别名问题。我怎么知道你是否实现了自己的虚拟向量或数组列表，它们与标准完全不同？我如何知道当前运行时的类型是什么？你有没有重载我没有时间检查的运算符。天哪，我甚至不知道你正在使用哪个STL版本？

你接下来遇到的另一个问题就是泄漏的抽象，虽然有许多网站详细讨论了这个问题。

很抱歉，我以前没有看到过，也从未看到过迭代器的实际用途。如果它们将列表或向量抽象化了，事实上，如果你不知道正在处理的是哪个向量或列表，那么你将为自己设置一些出色的调试会话。

- Chad

24

如果您在迭代过程中要添加/删除向量中的元素，则可能需要使用迭代器。

some_iterator = some_vector.begin(); 
while (some_iterator != some_vector.end())
{
    if (/* some condition */)
    {
        some_iterator = some_vector.erase(some_iterator);
        // some_iterator now positioned at the element after the deleted element
    }
    else
    {
        if (/* some other condition */)
        {
            some_iterator = some_vector.insert(some_iterator, some_new_value);
            // some_iterator now positioned at new element
        }
        ++some_iterator;
    }
}

如果您使用索引，您将不得不在数组中上下移动项目来处理插入和删除。

- bmatthews68

4

如果你希望在容器中间插入元素，那么也许 vector 不是一个好的容器选择。当然，这就回到了为什么迭代器很棒的问题上；切换到 list 容器非常简单。 - wilhelmtell

与std::vector相比，遍历所有元素在std::list中是非常昂贵的，尽管如果您建议使用链表而不是std::vector。请参见第43页：http://ecn.channel9.msdn.com/events/GoingNative12/GN12Cpp11Style.pdf 根据我的经验，即使我在搜索整个向量并在任意位置删除元素，std::vector也比std::list更快。 - David Stone

索引是稳定的，因此我不认为在插入和删除时需要进行额外的洗牌。 - musiphil

而且使用链表 - 这是应该在这里使用的 - 你的循环语句将是 for (node = list->head; node != NULL; node = node->next)，这比你前两行代码加起来还要短（声明和循环头）。所以我再说一遍 - 在使用迭代器和不使用它们之间，在简洁性方面并没有太大的基本差异 - 即使你使用 while，你仍然必须满足 for 语句的三个部分：声明、迭代、检查终止。 - Engineer

16

关注点分离

将迭代代码与循环的“核心”关注点分离开来非常好。这几乎是一种设计决策。

事实上，按索引进行迭代会将您绑定到容器的实现。向容器请求开始和结束迭代器可以使循环代码可用于其他容器类型。

此外，在 std::for_each 的方式中，您要告诉集合该做什么，而不是询问它的内部情况。

0x 标准将引入闭包，这将使这种方法更易于使用 - 例如，请查看 Ruby 的表达能力：[1..6].each { |i| print i; }...

性能

但也许一个被忽视的问题是，使用 for_each 方法可以有机会并行化迭代 - 英特尔线程块可以将代码块分布在系统中的处理器数量上！

注意：发现 algorithms 库，特别是 foreach 后，我花了两三个月时间编写了一些非常小的“辅助”运算符结构，这可能会让你的同事们疯狂。之后，我回到了务实的方法 - 小循环体不再需要 foreach :)

关于迭代器，必读的参考书是"Extended STL"。

GoF在迭代器模式的结尾有一个小段落，讲到了这种迭代方式；它被称为“内部迭代器”。在这里也可以看到相关内容。

- xtofl

15

因为它更加面向对象。如果你正在使用索引进行迭代，那么你假设：
a) 那些对象是有序的
b) 这些对象可以通过索引获得
c) 索引递增将会遍历到每个项目
d) 索引从零开始
使用迭代器，你是在说"把所有东西都给我，让我来处理"，而不知道底层实现细节（在Java中，有些集合不能通过索引访问）
此外，使用迭代器时无需担心数组越界问题。

- cynicalman

2

我认为“面向对象”不是正确的术语。迭代器在设计上并不是“面向对象”的，它们更多地促进函数式编程，因为它们鼓励将算法与类分离。 - wilhelmtell

此外，迭代器不能帮助避免越界。标准算法可以，但仅靠迭代器是不行的。 - wilhelmtell

好的，@wilhelmtell，我显然是从Java为中心的角度考虑这个问题。 - cynicalman

1

我认为它确实促进了面向对象编程，因为它将集合操作与集合的实现分离开来。一个对象集合不一定要知道应该使用哪些算法来处理它们。 - cynicalman

实际上，有一些STL版本具有已检查的迭代器，这意味着当您尝试使用该迭代器执行某些操作时，它将抛出某种越界异常。 - Dominik Grabiec

15

除了其他优秀的答案外... int 可能对于您的向量来说不够大。因此，如果要使用索引，请使用容器的 size_type：

for (std::vector<Foo>::size_type i = 0; i < myvector.size(); ++i)
{
    Foo& this_foo = myvector[i];
    // Do stuff with this_foo
}

- Pat Notz

1

@Pat Notz，这是一个非常好的观点。在将基于STL的Windows应用程序移植到x64的过程中，我不得不处理数百个警告，涉及将size_t分配给int可能会导致截断的问题。 - bk1e

1

更不用说尺寸类型是无符号的，而int是有符号的，因此你需要进行非直观的、隐藏错误的转换才能将int i与myvector.size()进行比较。 - Adrian McCarthy

15

另一个迭代器的好处是，它更好地允许你表达（和强制执行）你的const偏好。这个例子确保你不会在循环中修改向量：


for(std::vector<Foo>::const_iterator pos=foos.begin(); pos != foos.end(); ++pos)
{
    // Foo & foo = *pos; // this won't compile
    const Foo & foo = *pos; // this will compile
}

- Pat Notz

这看起来很合理，但我仍然怀疑const_iterator的存在是否是出于这个原因。如果我在循环中修改向量，那么我肯定有我的理由，并且99.9%的情况下，这种修改不是偶然的，只有剩下的0.1%才是作者需要修复的问题，就像代码中的任何错误一样。因为在Java和许多其他语言中根本没有常量对象，但是那些语言的用户从未遇到过由于这些语言不支持常量而导致的问题。 - neevek

2

如果这不是拥有“const_iterator”的原因，那么地球上还可能有什么原因呢？ - underscore_d

@underscore_d，我也在想。虽然我不是专家，但是这个答案对我来说并不令人信服。 - neevek

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- wilhelmtell · Accepted Answer

如果vector.size()是一个快速操作，那么第一种形式是高效的。这对于向量来说是正确的，但是对于列表等其他数据结构则不然。此外，在循环体内你计划做什么？如果你计划像下面这样访问元素：

T elem = some_vector[i];

如果你认为容器定义了operator[](std::size_t)，那么你就在做这样的假设。对于vector来说是正确的，但对于其他容器则不然。

使用迭代器可以让你更加独立于容器。你不会对容器的随机访问能力或快速size()操作作出任何假设，只需要容器有迭代器的功能。

通过使用标准算法，你可以进一步优化你的代码。根据你想要实现的目标，你可以选择使用std::for_each()，std::transform()等函数。通过使用标准算法而非显式循环，你可以避免重复造轮子。你的代码可能会更加高效（前提是选择合适的算法），正确并且可重用。