6

在一本 C++ 编程书中，我看到了以下std::list迭代器：

for (iterator = list.start(); iterator != list.end(); iterator++)

一直打电话不是效率低list.end()吗？将结尾保存到另一个变量会更好，还是 C++ 编译器（即 g++）会自动处理这个问题？

4

8 回答 8

8

list::end()应该具有恒定的时间复杂度，特别是对于链表，这意味着它可能非常有效。

如果您的算法允许，存储该值可能会稍微更有效（同样，对于特别是链表，差异不太可能很大）。

哦，请阅读史蒂夫·杰索普关于自己测试效率的回答！

于 2012-08-28T19:43:43.473 回答
4

不太可能有任何区别。

标准容器函数是内联的，所以应该没有明显的函数调用开销。剩下的就是优化器是否足够聪明，可以避免不必要的开销，而这些开销对于执行比较并不是绝对必要的。例如：它实际上是创建一个临时list::iterator对象，填充其当前位置字段，然后读回该字段，还是比较最终只是一个值iterator与列表头部的值之间的指针比较？

即使有一些不必要的开销，与递增迭代器相比，它可能可以忽略不计，与循环体相比甚至可以忽略不计。

你可以测试它，这比猜测更可靠。记住启用优化——在没有优化的情况下测试性能有点像说如果布莱克从热身赛道走到公共汽车的速度更快，布莱克必须比博尔特快。

于 2012-08-28T19:44:48.827 回答
4

一般来说，不，它不是低效的。end()通常是一个内联函数，编译器会生成好的代码来做任何事情。更重要的是，与什么相比效率低下？是的，您可以添加代码来创建一个变量来保存结果，这可能会或可能不会比简单地调用end(). 这样的改变似乎不太可能产生足够大的速度差异，从而将一个太慢的程序变成满足要求的程序。

于 2012-08-28T19:45:18.433 回答
4

调用std::list<T>::end()不太可能是一个大的效率问题，可能只是读取一个值。但是，您会给编译器一个提示，它并不意味着通过将其存储为变量来进行更改。对于其他容器，除了读取涉及更多的基地址之外，还可能涉及计算。仍然没有什么戏剧性的，但可能值得避免。

但是请注意，它也可能会改变循环的语义：如果循环的主体可以附加元素，则前一个末端可能会移动。有趣的是，我在标准中没有找到任何具体要求，说明std::list<T>::end()在将元素插入容器时是否会发生变化（我可以想象它确实发生变化的实现以及一些没有发生变化的实现；很可能它不会改变，尽管）。如果您还想在修改列表时获得有保证的行为，您可能会list.end()在每次迭代中调用。

顺便说一句，我对使用iterator++而不是有更大的性能问题++iterator，尤其是作者在书中使用的内容。尽管如此，这是一个微优化，就像存储list.end()一个便宜的结果一样。

于 2012-08-28T19:54:17.117 回答
2

在实践中，对于 STL 容器来说，container::end()是极其便宜的。事实上，C++ 标准规定了几个类（如果不是全部）的几种方法的算法复杂性，并且container::end()始终是常数时间。

此外，编译器可以自由地内联这些方法，基本上消除了它可能产生的任何开销。除了存储它之外，我想不出其他方法可以在恒定时间内获取列表的末尾，因此您的list.end()调用可能最终成为字段访问，这在 x86 平台上并不比将其存储在堆栈中更昂贵。

您的里程可能会因其他收藏而异，但可以肯定的是，这list.end()不会成为您的瓶颈。

于 2012-08-28T19:44:39.623 回答
1

如果您需要进行微优化，可以。

一般来说，调用list.end()不会有显着的性能损失，也可能不会成为问题。它可能每次调用都返回相同的值，也可能是内联的，等等。虽然不慢，但确实需要一些时间。

如果你绝对需要速度，你想使用for (iterator = list.start(), end = list.end; iteration != end; ++iterator). 这会缓存结束迭代器（并执行 pre-inc），并且不应重复调用。

第二种类型通常是不必要的，但如果.end()价格昂贵或循环非常大，可能会有用。

于 2012-08-28T19:45:21.553 回答
1

虽然过早的优化是邪恶的，但良好的习惯却不是。如果您不希望循环终止条件发生变化，即您没有更改容器，则可以使用此模式：

for (mylist::iterator it = alist.begin(), finish = alist.end();  it != finish;  ++it)

如果编译器无法确定容器没有发生变化，则编译器不太可能为您进行此优化。

请注意，这不太可能产生可测量的时间差异，但不会造成伤害。

于 2012-08-28T19:54:18.267 回答
0

end()不缓存的一个很好的理由std::list是它可以防止您犯以下错误：

for (iterator = list.rstart(), end = list.rend(); iterator != end; iterator++) {
    // modify list

当您在 中进行修改时，任何迭代器都不会失效std::list，但rend它不是哨兵（它指向底层列表的第一个元素），这意味着如果您附加到反向列表的末尾，它将不再是列表的末尾列表（又名添加到未反转列表的开头。）

于 2017-07-24T18:22:55.333 回答