end() 是否需要在 STL 映射/集中保持不变?

2022-01-10 00:00:00 iterator c++ stl

标准中的第 23.1.2.8 节规定，对集合/映射的插入/删除操作不会使这些对象的任何迭代器无效(指向已删除元素的迭代器除外).

§23.1.2.8 in the standard states that insertion/deletion operations on a set/map will not invalidate any iterators to those objects (except iterators pointing to a deleted element).

现在，考虑以下情况:您想要实现一个具有唯一编号节点的图，其中每个节点都有固定数量(比如 4 个)的邻居.利用上述规则，您可以这样做:

Now, consider the following situation: you want to implement a graph with uniquely numbered nodes, where every node has a fixed number (let's say 4) of neighbors. Taking advantage of the above rule, you do it like this:

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;
};

(EDIT:由于第 4 行中的 Node 不完整(见回复/评论)，因此并非字面上如此，但无论如何都是这样)

(EDIT: Not literally like this due to the incompleteness of Node in line 4 (see responses/comments), but along these lines anyway)

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

This is good, because this way you can insert and delete nodes without invalidating the consistency of the structure (assuming you keep track of deletions and remove the deleted iterator from every node's array).

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

But let's say you also want to be able to store an "invalid" or "nonexistent" neighbor value. Not to worry, we can just use nodes.end()... or can we? Is there some sort of guarantee that nodes.end() at 8 AM will be the same as nodes.end() at 10 PM after a zillion insertions/deletions? That is, can I safely == compare an iterator received as a parameter to nodes.end() in some method of Graph?

如果没有，这行得通吗?

And if not, would this work?

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

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

That is, can I store nodes.end() in a variable upon construction, and then use this variable whenever I want to set a neighbor to invalid state, or to compare it against a parameter in a method? Or is it possible that somewhere down the line a valid iterator pointing to an existing object will compare equal to _INVALID?

如果这也不起作用，我可以做什么为无效的邻居值留出空间?

And if this doesn't work either, what can I do to leave room for an invalid neighbor value?

推荐答案

你写(我强调):

标准中的第 23.1.2.8 节规定，对集合/映射的插入/删除操作不会使任何迭代器到这些对象无效(指向已删除元素的迭代器除外).

§23.1.2.8 in the standard states that insertion/deletion operations on a set/map will not invalidate any iterators to those objects (except iterators pointing to a deleted element).

其实 23.1.2/8 的文字有点不同(再次强调一下):

Actually, the text of 23.1.2/8 is a bit different (again, emphasis by me):

插入成员不应影响迭代器的有效性和对容器的引用，而擦除成员应仅使迭代器和对被擦除元素的引用无效.

The insert members shall not affect the validity of iterators and references to the container, and the erase members shall invalidate only iterators and references to the erased elements.

我将其解读为:如果您有一个地图，并且以某种方式获得了一个指向该地图的迭代器(同样:它没有说 指向地图中的一个对象)，这个迭代器将保持有效尽管插入和删除元素.假设 std::map<K,V>::end() 获得映射到地图的迭代器"，它不应因插入/删除而失效.

I read this as: If you have a map, and somehow obtain an iterator into this map (again: it doesn't say to an object in the map), this iterator will stay valid despite insertion and removal of elements. Assuming std::map<K,V>::end() obtains an "iterator into the map", it should not be invalidated by insertion/removal.

当然，这留下了未失效"是否意味着它将始终具有相同值的问题.我个人的假设是没有具体说明.但是，为了使未失效"短语有意义，同一地图的 std::map::end() 的所有结果必须始终比较相等，即使在插入/删除面:

This, of course, leaves the question whether "not invalidated" means it will always have the same value. My personal assumption is that this is not specified. However, in order for the "not invalidated" phrase to make sense, all results of std::map<K,V>::end() for the same map must always compare equal even in the face of insertions/removal: 

my_map_t::iterator old_end = my_map.end();
// wildly change my_map
assert( old_end == my_map.end() );

我的解释是，如果 old_end 在地图的整个更改过程中保持有效"(正如标准承诺的那样)，那么该断言应该通过.

My interpretation is that, if old_end remains "valid" throughout changes to the map (as the standard promisses), then that assertion should pass.

免责声明:我不是母语人士，非常很难消化神圣 PDF 的可怕合法化.事实上，总的来说，我像避免瘟疫一样避免它.

Disclaimer: I am not a native speaker and have a very hard time digesting that dreaded legaleze of the Holy PDF. In fact, in general I avoid it like the plague.

哦，我的第一个想法也是:这个问题在学术 POV 中很有趣，但他为什么不简单地存储键而不是迭代器?

Oh, and my first thought also was: The question is interesting from an academic POV, but why doesn't he simply store keys instead of iterators?

相关文章