是不是调用`list <T> :: end()`效率低下？

Question

在C++编程书中,我看到了以下std::list迭代器:

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

一直打电话效率不高list.end()吗？将结尾保存到另一个变量或者C++编译器(即g ++)会自动处理这个变量会更好吗？

Answer 1

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

如果您的算法允许,那么存储该值可能稍微更高效(同样,对于特别是链接列表,差异可能不大).

哦,并且阅读了Steve Jessop关于自己测试效率的答案!

Answer 2

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

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

iterator++顺便说一句，我对使用而不是有一个更大的性能问题++iterator，特别是这确实是作者在书中使用的。尽管如此，这仍然是一种微观优化，就像存储结果一样，list.end()但做起来很便宜。