相关疑难解决方法(0)

C++容器的迭代器失效规则是什么？

优选地以摘要列表格式.

_{(注意:这是Stack Overflow的C++常见问题解答的一个条目.如果你想批评在这种形式下提供常见问题解答的想法,那么发布所有这些的元数据的发布将是这样做的地方.这个问题在C++聊天室中受到监控,其中FAQ的想法一开始就出现了,所以你的答案很可能被那些提出想法的人阅读.)}

标准中的§23.1.2.8声明对set/map的插入/删除操作不会使对这些对象的任何迭代器无效(指向已删除元素的迭代器除外).

现在,考虑以下情况:您希望实现具有唯一编号节点的图形,其中每个节点具有固定数量(假设4个)邻居.利用上述规则,你可以这样做:

class Node {
    private:
        // iterators to neighboring nodes
        std::map<int, Node>::iterator neighbors[4];
        friend class Graph;
};

class Graph {
    private:
        std::map<int, Node> nodes;
};

(编辑:由于Node第4行的不完整性(参见回复/评论),并非字面意思,但无论如何都沿着这些方向)

这很好,因为这样您就可以插入和删除节点而不会使结构的一致性失效(假设您跟踪删除并从每个节点的数组中删除已删除的迭代器).

但是,假设您还希望能够存储"无效"或"不存在"的邻居值.不用担心,我们可以使用nodes.end()...或者我们可以吗？是否存在某种保证,nodes.end()在nodes.end()经过多次插入/删除后,上午8点将与下午10点相同？也就是说,我可以安全地==将作为参数接收的迭代器nodes.end()与Graph的某些方法进行比较吗？

如果没有,这会有效吗？

class Graph {
    private:
        std::map<int, Node> nodes;
        std::map<int, Node>::iterator _INVALID;
    public:
        Graph() { _INVALID = nodes.end(); }
};

也就是说,我可以nodes.end()在构造时存储变量,然后每当我想将邻居设置为无效状态时使用此变量,或者将它与方法中的参数进行比较吗？或者有可能在某个地方,指向现有对象的有效迭代器将比较等于_INVALID？

如果这也不行,有什么可怎么办留有余地无效邻居价值？