缓存最终迭代器 - 好主意还是坏主意？

Question

一般来说，出于效率和速度的目的，缓存结束迭代器（特别是 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 容器中的 end 失效还是仅在某些容器中失效？

Answer 1

在 vector 的简单情况下，当您从容器中添加或删除元素时，end 迭代器将发生变化；不过，通常最安全的假设是，如果在迭代容器时改变容器，则它的所有迭代器都会变得无效。在任何给定的 STL 实现中，迭代器的实现方式可能不同。

关于缓存 end 迭代器——缓存它当然是有效的，但要了解它在您的情况下是否实际上更快，最好的办法是分析您的代码并查看。虽然从 vector 检索 end 迭代器可能是使用最新的 STL 库和编译器的快速实现，但我曾经参与过过去的项目，其中缓存end 迭代器给我们带来了显着的速度提升。 （这是在 PlayStation 2 上进行的，所以请持保留态度。）

Answer 2

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

Answer 3

从当前正在迭代的容器中删除始终是一个坏主意。最终迭代器的实际缓存不会改变这一点。

h.

Answer 4

一般来说这是一个好主意
缓存一个结束迭代器（具体来说
STL 容器）以提高效率和
速度目的？

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

如果您修改容器的内存（插入/删除元素），这是一个坏主意。

此外，为了提高效率而进行缓存几乎没有多大意义：在大多数情况下，end() 是由编译器内联的，如果不是，则您的效率很可能不会取决于缓存的 end() 结果。不过，YMMV。

Answer 5

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

特别针对我发现的向量：

[5] 当向量的内存被重新分配时，向量的迭代器将失效。此外，在向量中间插入或删除元素会使指向插入或删除点之后的元素的所有迭代器无效。因此，如果使用 Reserve() 预分配向量将使用的内存，并且所有插入和删除都位于向量的末尾，则可以防止向量的迭代器失效。

Answer 6

我经常使用这种样式来迭代容器：

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

从向量中删除元素会使删除位置之后的所有迭代器无效。

我不确定其他容器类型。无论如何，我认为可以安全地假设所有迭代器在擦除后都变得无效。如果您确实需要非常具体的信息，那么您可以随时查找。我很少需要这个，因为我的编码风格相当保守。

Answer 7

一般来说，如果缓存结束迭代器应该没有关系。如果您认为这确实很重要，那么您应该已经在代码上使用分析器并且能够分析这两种变体。我怀疑它可能会根据容器类型而有所不同 - 但分析器将是确定您的编译器、优化和 STL 供应商的唯一方法。

Answer 8

这真的非常取决于您在 ... 代码中做什么。

如果编译器可以证明 vint.end() 不会改变，那么这可能并不重要，但你会受到编译器优化的支配，并且 有多清晰。 . 代码。

您的方法是对编译器帮助最大的方法，您承诺 end 迭代器不会失效，并且您不会修改 end 中的元素（无论如何都是无效的）。对于您在 ... 中承诺要做的事情，您再明确不过了。

现在是 2019 年，for-range 循环基本上等同于您的代码： https: //en.cppreference.com/w/cpp/language/range-for

{
    auto && __range = range_expression ;
    auto __begin = begin_expr ;
    auto __end = end_expr ;
    for ( ; __begin != __end; ++__begin) {

        range_declaration = *__begin;
        loop_statement

    }
}

顺便说一句，这意味着如果您不是真正对it感兴趣，而是对*it感兴趣code>，你可以结束（没有双关语）这个困境，只需写：

std::vector<int> vint;
for(auto&& e : vint)
{
   .... // use `e` instead of `*it`.
}