缓存结束迭代器 - 好主意还是坏主意？

一般来说，为了效率和速度的目的，缓存一个结束迭代器（特别是STL容器）是一个好主意吗？例如在以下代码位中：缓存结束迭代器 - 好主意还是坏主意？

std::vector<int> vint; 
const std::vector<int>::const_iterator end = vint.end(); 
std::vector<int>::iterator it = vint.begin(); 

while (it != end) 
{ 
    .... 
    ++it; 
}

在什么情况下会使最终值失效？将从容器中删除原因结束被取消全部 STL容器还是只是一些？

来源

2010-06-21 Hippicoder

首先问自己，你的分析器告诉你std :: vector :: end（）的调用花费了大量的处理时间吗？ – daramarak 2010-06-21 12:34:50

在vector的简单情况下，当您向容器添加或移除元素时，迭代器将发生更改;尽管如此，假设如果在遍历容器的同时改变容器，所有的迭代器都会失效，这通常是最安全的。迭代器可以在任何给定的STL实现中以不同的方式实现。

关于缓存迭代器 - 缓存它当然是有效的，但为了确定它是否实际上更快，最好的方法是让你分析代码并查看。虽然检索end迭代器从vector很可能是一个快速实现与最近的STL库和编译器，我有工作过去的项目，其中缓存迭代器给我们一个显着的速度提升。（这是在PlayStation 2上，所以请尽情享用。）

来源

2010-06-21 12:03:17

从您当前迭代的容器中擦除始终是一个糟糕的主意。结束迭代器的实际缓存不会改变这一点。 h。

h。

来源

2010-06-21 11:17:25 haavee

一点都不，如果你做得对。例如，std :: vector的'erase'成员会返回一个合适的新迭代器。所以只要你正确地编写你的代码（也就是说，记住其他迭代器现在是无效的），你将不会从你正在迭代的容器中删除问题。 – 2010-06-21 11:36:36

如果我们谈论效率和速度：由于编译器优化和内联，缓存结束迭代器是不必要的。

来源

2010-06-21 11:28:03

真的吗？我所看到的大多数使用STL算法的建议（如'for_each'）都会缓存'end'迭代器，因此在每次迭代时都不会计算。 – 2010-06-21 13:24:02

@Matthieu：迭代器不能保证在某些容器的修改过程中不能存活（例如，调整矢量无效化*全部*迭代器到矢量的大小）。 for_each不给函数对象访问迭代器，容器不能改变，因此可以缓存迭代器。但是如果欺骗系统和函数对象以使迭代器无效的方式修改容器，那么很显然，当通过现在无效的迭代器访问容器时，会导致* undefined behavior *，可能会崩溃。 – Dummy00001 2010-06-21 16:18:00

实际上，调整矢量大小只会在迭代器发生重新分配时使迭代器失效，并且如果只调整容量，则可以确保它不会调整大小。但是我的问题仍然存在，我不确定编译器是否能够优化循环中'end（）'的计算，即使将编译器作为先验内联也无法知道该值是否可能得到据我所知，由循环内的操作修改。但后来我不太了解编译器优化，因此我的问题:) – 2010-06-21 17:35:19

我经常使用这种风格的迭代容器：

// typedef std::vector<Person> Persons; 
Persons::iterator it = persons.begin(), end = persons.end(); 
for (; it != end; ++it) 
{ 
    Person & person = *it; 
    // ... 
}

删除从向量元素无效擦除的位置毕竟迭代器。

我不确定其他容器类型。无论如何，我认为假设所有迭代器在擦除后变得无效是安全的。如果你真的需要非常具体的信息，那么你总是可以查看它。我很少需要这个，因为我的编码风格比较保守。

来源

2010-06-21 11:51:08 StackedCrooked

通常，缓存结束迭代器应该没有关系。如果你觉得它确实很重要，那么你应该已经在你的代码中使用了一个分析器，并且能够分析这两个变体。我怀疑它会根据容器类型而有所不同 - 但是鉴于给定的编译器，优化和STL供应商，分析器将是唯一可以确定的方法。

来源

2010-06-21 12:01:32

一般来说是一个好主意缓存的效率和速度目的的结束迭代器（特别是 STL容器）？

如果使用STL容器算法，无论如何都会发生结束迭代器的缓存（因为您将container.end（）的结果作为参数传递）。

如果修改容器的内存（插入/移除元素），这是一个坏主意。另外，高效缓存很少有意义：在大多数情况下，end（）是由编译器内联的，如果不是，那么很可能您的效率不会挂在end（）结果上被缓存。 YMMV。

来源

2010-06-21 12:02:28 utnapistim

无效规则（对于迭代器）是为每种类型的容器都非常明确地定义的。我发现SGI现场非常有用http://www.sgi.com/tech/stl/table_of_contents.html

具体而言为载体我发现：

[5]时，其重新分配内存的矢量的迭代器被无效。另外，在向量中插入或删除元素会使所有指向插入或删除点后面元素的迭代器无效。因此，如果使用reserve（）预先分配向量将使用的尽可能多的内存，并且所有的插入和删除都位于向量的末尾，则可以防止向量的迭代器失效。

来源

2010-06-21 15:17:07

缓存结束迭代器 - 好主意还是坏主意？

回答

相关问题