在STL映射/集合中，end（）是否必须是常量？ [英] Is end() required to be constant in an STL map/set?

问题描述

§23.1.2.8在标准状态下，在集合/映射上的插入/删除操作不会使任何迭代器无效到那些对象（除了指向被删除的元素的迭代器）。

现在，考虑以下情况：要实现具有唯一编号节点的图，其中每个节点具有固定数量（假设为4）的邻居。利用上述规则，您可以这样做：

  class Node {
 private：
 //迭代器到相邻节点
 std :: map< int，Node> :: iterator neighbors [4]; 
 friend class Graph; 
}; 
 
 class Graph {
 private：
 std :: map< int，Node>节点; 
}; 
  

（ EDIT ：由于不完整的 Node 在第4行（见回复/注释），但是沿这些行）

你可以插入和删除节点而不会使结构的一致性失效（假设你记住删除并从每个节点的数组中删除迭代器）。

也希望能够存储无效或不存在的邻居值。不用担心，我们可以使用 nodes.end（） ...或者我们可以吗？是否有保证 nodes.end（）在8 AM将与 nodes.end（）下午10点，在zillion插入/删除后？也就是说，我可以安全地 == 在一些方法中将作为参数接收的迭代器与 nodes.end（）

  
 class Graph {
 private：
 std :: map< int，Node>节点; 
 std :: map< int，Node> :: iterator _INVALID; 
 public：
 Graph（）{_INVALID = nodes.end（）; } 
}; 
  

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

解决方案如果这样做不起作用， div>

23.1 / 7说end（）返回一个迭代器，

是容器的过去值。

首先，它确认 end（）返回的是迭代器。第二，它说迭代器不指向一个特定的元素。因为删除只能使指向某处（被删除的元素）的迭代器无效，删除不能使 end（）无效。

§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).

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: 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).

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

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/7 says that end() returns an iterator that

is the past-the-end value for the container.

First, it confirms that what end() returns is the iterator. Second, it says that the iterator doesn't point to a particular element. Since deletion can only invalidate iterators that point somewhere (to the element being deleted), deletions can't invalidate end().

这篇关于在STL映射/集合中，end（）是否必须是常量？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！