关于使迭代器无效

Question

STL容器存在迭代器在容器更改时可能失效的问题。容器是否可以通过添加一个调用has_changed（）来通知它已经改变了？

在某些操作之前查询empty（）很常见。如果容器对会影响迭代器的操作（例如insert（）或erase（））设置布尔值，那么在重用迭代器之前可以查询has_changed（）。

疯了吗？

编辑感谢您的一堆好回复和思考。我希望我能授予不止一个获胜者。

Answer 1

在Java中工作的（近似的）快速失败迭代器的工作原理是容器在每次更改时都增加一个计数器。迭代器在创建时复制此计数器，并在每次通过容器更改容器时增加它。如果迭代器检测到不匹配，则会抛出异常。

C++有令人兴奋的属性，一些操作使容器上的迭代器无效，但其他操作无效。例如，假设已经保留足够的空间vector::insert使迭代器在插入点之后失效，但不在之前。

另一个难题是list::remove。这将使所有迭代器都有效，除了被删除的迭代器，和它的所有副本。

正如你可以想象的那样，要精确跟踪这一点非常困难。实践中发生的事情是，您的实现可能会提供调试选项，其中迭代器将尽最大努力检测它们是否有效。但是，这可能取决于他们目前是否“有效”的实施细节，而不是标准是否保证他们仍然有效。

在C++中执行类似于Java中的“版本号”的操作是可能的，但它会给出错误的迭代器错误，它们看起来无效但实际上是有效的。

Answer 2

有点疯了，如果有意的话。

我认为这个问题的主要原因是容器如何知道它何时“不变”？换句话说，一些东西被抹去，并且“已更改”标志被设置。由于重新恢复正常或稳定状态，重置旗子的事件是什么？它实际上是迭代器而不是处于无效状态的容器。

我认为为了在所有迭代器中工作，需要比现在更多，更智能，并且更像操作容器的观察者。容器可以发送一个事件给它已经改变的注册迭代器，并且他们可以在尝试操作之前检查它们自己的状态。但即使有这么多漏洞，它可能会导致比你想要解决的更大的混乱。

Answer 3

这将是低效的，因为容器需要A）提供另一个数据字段并且B）相应地更新它。然而，STL被认为是为了做不可能的事情，并将效率与抽象结合起来。 （它成功了，我要补充。）

如果你需要保持引用到不断变化的容器，要么使用一个不坏的迭代器（std::list，std::set）或保留指数为std::vector。

Answer 4

迭代器失效的规则已经足够清晰，如果您按规则付费，则不应要求询问容器何时失效。

此外，迭代器并不总是同时失效。从矢量中移除一个元素只会使该元素和后一个元素无效。但是指向矢量开始的迭代器仍然有效。

在列表中，迭代器通常只在它们指向的特定节点被销毁时才会失效。

所以你不能问容器你的迭代器是否有效。

通用标准库实现可以选择启用与请求类似的附加运行时检查，尽管实现更复杂（它必须是为了正确）并且会损害性能。

Answer 5

这在技术上是可行的，并且MSVC实现了提供类似功能的'checked iterators'（http://msdn.microsoft.com/en-us/library/aa985965.aspx）。尽管当迭代器失效时你没有得到通知，并且你不能直接查询状态（我知道的），但是抛出异常并且/或者调用invalid_parameter，这取决于构建的配置。

但是，它绝对是非标准的，并且显着提高了性能。这对调试很有用。

Answer 6

容器是否可以通过添加一个调用has_changed（）来宣告它已经改变了？

我想，是的，它可以实施。这是一个非常简单的尝试（不那么优雅，但仍然）：

bool has_changed(std::vector<int> &v) 
{ 
    static std::map<void*, size_t> has_changed_info; 
    void *ptr = &v; 
    std::map<void*, size_t>::iterator it = has_changed_info.find(ptr); 
    if (it == has_changed_info.end()) 
    { 
     has_changed_info[ptr] = v.capacity(); 
     return false; 
    } 
    if (it->second != v.capacity()) 
    { 
     it->second = v.capacity(); 
     return true; 
    } 
    return false; 
} 

测试代码：

int main() { 
     std::vector<int> v; 
     has_changed(v); 
     for (int i = 0 ; i < 100 ; ++i) 
     { 
      v.push_back(i); 
      if (has_changed(v)) 
        cout << "changed at " << i << endl; 
     }  
     return 0; 
} 

输出（GCC-4.3.4）：

changed when inserting i = 0 
changed when inserting i = 1 
changed when inserting i = 2 
changed when inserting i = 4 
changed when inserting i = 8 
changed when inserting i = 16 
changed when inserting i = 32 
changed when inserting i = 64 

在线演示：http://www.ideone.com/QmO5q