end() 在 STL 映射/集中是否需要保持不变？
标准中的第 §23.1.2.8 规定，集合/映射上的插入/删除操作不会使这些对象的任何迭代器无效（指向已删除元素的迭代器除外）。
现在，考虑以下情况：您想要实现一个具有唯一编号节点的图，其中每个节点都有固定数量（假设为 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;
};
编辑：由于第 4 行中 Node 的不完整性，字面意思不是这样的（请参阅回复/评论），但无论如何，沿着这些线）
这很好，因为这样您可以插入和删除节点，而不会导致结构的一致性失效（假设您跟踪删除操作并从每个节点的数组中删除已删除的迭代器）。
但假设您还希望能够存储“无效”或“不存在”的邻居值。不用担心，我们可以使用nodes.end()...或者可以吗？是否有某种保证，在无数次插入/删除之后，上午 8 点的 nodes.end() 与晚上 10 点的 nodes.end() 相同？也就是说，我可以安全地 == 将作为参数接收的迭代器与 Graph 的某种方法中的 nodes.end() 进行比较吗？
如果没有，这行得通吗？
class Graph {
private:
std::map<int, Node> nodes;
std::map<int, Node>::iterator _INVALID;
public:
Graph() { _INVALID = nodes.end(); }
};
也就是说，我可以在构造时将 nodes.end() 存储在变量中，然后每当我想要将邻居设置为无效状态时使用该变量，或者将其与方法中的参数进行比较？或者是否有可能在某个地方，指向现有对象的有效迭代器将比较等于_INVALID？
如果这也不起作用，我可以做什么来为无效的邻居值留出空间？
§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?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（10）
我相信这完全取决于所使用的迭代器类型。
在向量中，end() 是结束指针后面的那个，随着元素的插入和删除，它显然会发生变化。
在另一种容器中，end() 迭代器可能是特殊值，如 NULL 或默认构造元素。在这种情况下，它不会改变，因为它不指向任何东西。 end() 不是一个类似指针的东西，它只是一个要比较的值。
我相信集合和映射迭代器是第二种，但我不知道有什么需要它们以这种方式实现。
I believe that this depends entirely on what type of iterator is being used.
In a vector, end() is the one past the end pointer and it will obviously change as elements are inserted and removed.
In another kind of container, the end() iterator might be a special value like NULL or a default constructed element. In this case it doesn't change because it doesn't point at anything. Instead of being a pointer-like thing, end() is just a value to compare against.
I believe that set and map iterators are the second kind, but I don't know of anything that requires them to be implemented in that way.
C++ 标准规定迭代器应该保持有效。确实如此。标准在23.1.2/8中明确规定：
在 21.1/7 中：
因此迭代器
old_end和new_end将是有效的。这意味着我们可以获得--old_end（称为it1）和--new_end（称为it2） ）并且它将是结束值迭代器（来自end()返回的定义），因为关联容器的迭代器属于双向迭代器类别（根据23.1.2/6）并根据--r操作的定义（表75）。现在，
it1应该等于it2，因为它给出的最终值只有 1 (23.1.2/9)。然后从 24.1.3 可以得出：条件 a == b 意味着 ++a == ++b。并且++it1和++it2将给出old_end和new_end迭代器（来自 ++r 操作的定义表 74）。现在我们知道old_end和new_end应该相等。C++ Standard states that iterators should stay valid. And it is. Standard clearly states that in 23.1.2/8:
And in 21.1/7:
So iterators
old_endandnew_endwill be valid. That means that we could get--old_end(call itit1) and--new_end(call itit2) and it will be the-end value iterators (from definition of whatend()returns), since iterator of an associative container is of the bidirectional iterator category (according to 23.1.2/6) and according to definition of--roperation (Table 75).Now
it1should be equalit2since it gives the-end value, which is only one (23.1.2/9). Then from 24.1.3 follows that: The condition that a == b implies ++a == ++b. And++it1and++it2will giveold_endandnew_enditerators (from definition of ++r operation Table 74). Now we get thatold_endandnew_endshould be equal.我最近有一个类似的问题，但我想知道调用
end()来检索迭代器以进行比较是否可能存在竞争条件。根据标准，如果两个迭代器都可以取消引用并且
&*a == &*b或者两者都不能取消引用，则认为两个迭代器是等效的。声明花了一段时间，并且在这里非常相关。因为
std::map::iterator不能失效，除非它指向的元素已被删除，所以您可以保证end返回两个迭代器，无论什么地图的状态是它们获得时的状态，总是会相互比较为真实的。I had a similar question recently, but I was wondering if calling
end()to retrieve an iterator for comparison purposes could possibly have race conditions.According to the standard, two iterators are considered equivalent if both can be dereferenced and
&*a == &*bor if neither can be dereferenced. Finding the bolded statement took a while and is very relevant here.Because an
std::map::iteratorcannot be invalidated unless the element it points to has been removed, you're guaranteed that two iterators returned byend, regardless of what the state of the map was when they were obtained, will always compare to each other as true.你写的（我强调的）：
实际上，23.1.2/8 的文本有点不同（再次强调）：
我将其解读为：如果您有一个地图，并且以某种方式获得该地图中的迭代器（再次强调：它没有说到地图中的对象），则尽管插入和删除，该迭代器仍将保持有效去除元素。假设 std::map::end() 获得“映射中的迭代器”，则它不应因插入/删除而失效。
当然，这留下了一个问题：“未失效”是否意味着它始终具有相同的值。我个人的假设是，这没有指定。但是，为了使“未失效”短语有意义，同一映射的
std::map::end() 的所有结果必须始终比较相等，即使在插入/删除的面：我的解释是，如果
old_end在整个映射更改过程中保持“有效”（如标准承诺），那么该断言应该通过。免责声明：我不是母语人士，并且非常很难消化神圣 PDF 中可怕的法律规定。事实上，总的来说，我像躲避瘟疫一样躲避它。
哦，我的第一个想法也是：从学术角度来看这个问题很有趣，但为什么他不简单地存储键而不是迭代器呢？
You write (emphasis by me):
Actually, the text of 23.1.2/8 is a bit different (again, emphasis by me):
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.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 interpretation is that, if
old_endremains "valid" throughout changes to the map (as the standard promisses), then that assertion should pass.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.
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?
23.1/7 说 end() 返回一个迭代器
首先，它确认
end()返回的是迭代器。其次，它表示迭代器不指向特定元素。由于删除只能使指向某处（指向被删除的元素）的迭代器无效，因此删除不能使end()无效。23.1/7 says that end() returns an iterator that
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 invalidateend().好吧，只要进行比较和此类工作，就没有什么可以阻止特定的集合实现使
end()依赖于集合的实例和一天中的时间。这意味着，end()值可能会改变，但old_end == end()比较仍应产生 true。 （编辑：虽然在阅读了 j_random_hacker 的评论后，我怀疑这一段本身的评估结果是否为true；-），不是普遍的 - 请参阅下面的讨论）我也怀疑你可以由于类型不完整，因此在
Node类中使用std::map::iterator （但不确定）。此外，由于您的节点是唯一编号的，因此您可以使用
int来对它们进行键控并保留一些无效值。Well, there's nothing preventing particular collection implementation from having
end()depend on the instance of collection and time of day, as long as comparisons and such work. Which means, that, perhaps,end()value may change, butold_end == end()comparison should still yield true. (edit: although after reading the comment from j_random_hacker, I doubt this paragraph itself evaluates to true ;-), not universally — see the discussion below )I also doubt you can use
std::map<int,Node>::iteratorin theNodeclass due to the type being incomplete, yet (not sure, though).Also, since your nodes are uniquely numbered, you can use
intfor keying them and reserve some value for invalid.（多）集合和（多）映射中的迭代器在插入和删除时不会失效，因此将 .end() 与之前存储的 .end() 值进行比较将始终产生 true。
以 GNU libstdc++ 实现为例，其中映射中的 .end() 返回
来自 stl_tree.h 的
Rb_tree_node默认初始化值：Iterators in (multi)sets and (multi)maps won't be invalidated in insertions and deletions and thus comparing .end() against previous stored values of .end() will always yield true.
Take as an example GNU libstdc++ implementation where .end() in maps returns the default intialized value of
Rb_tree_nodeFrom stl_tree.h:
假设（1）用红黑树实现的映射（2）“在无数次插入/删除之后”使用相同的实例 - 回答“是”。
相对实现我可以看出我所知道的所有 stl 的化身都使用树算法。
Assuming that (1) map implemented with red-black tree (2) you use same instance "after a zillion insertions/deletions"- answer "Yes".
Relative implmentation I can tell that all incarnation of stl I ever know use the tree algorithm.
有几点：
1) end() 引用超出容器末尾的元素。当插入或删除更改容器时它不会改变，因为它不指向元素。
2）我认为也许你在 Node 中存储 4 个迭代器的数组的想法可以改变，以使整个问题更有意义。您想要的是将新的迭代器类型添加到能够迭代单个节点的邻居的 Graph 对象。此迭代器的实现将需要访问映射的成员，这可能会引导您走上使 Graph 类扩展映射集合的道路。由于 Graph 类是扩展的 std::map，因此语言会发生变化，您不再需要存储无效的迭代器，而只需编写算法来确定谁是映射中的“下一个邻居”。
A couple points:
1) end() references an element that is past the end of the container. It doesn't change when inserts or deletes change the container because it's not pointing to an element.
2) I think perhaps your idea of storing an array of 4 iterators in the Node could be changed to make the entire problem make more sense. What you want is to add a new iterator type to the Graph object that is capable of iterating over a single node's neighbours. The implementation of this iterator will need to access the members of the map, which possibly leads you down the path of making the Graph class extend the map collection. With the Graph class being an extended std::map, then the language changes, and you no longer need to store an invalid iterator, but instead simply need to write the algorithm to determine who is the 'next neighbour' in the map.
我认为很清楚：
end() 返回一个指向末尾元素的迭代器。
插入/删除不会影响现有的迭代器，因此返回的值始终有效（除非您尝试删除末尾的元素（但这无论如何都会导致未定义的行为））。
因此，与原始的使用运算符==相比，由 end() 生成的任何新迭代器（会有所不同，但是）都会返回 true。
此外，使用赋值运算符=生成的任何中间值都有一个后置条件，即它们与运算符==比较相等，并且运算符==对于迭代器是传递的。
所以是的，存储 end() 返回的迭代器是有效的（但只是因为关联容器的保证，因此它对于向量等无效）。
请记住，迭代器不一定是指针。它可能是一个对象，容器的设计者已经定义了该类的所有操作。
I think it is clear:
end() returns an iterator to the element one past the end.
Insertion/Deletion do not affect existing iterators so the returned values are always valid (unless you try to delete the element one past the end (but that would result in undefined behavior anyway)).
Thus any new iterator generated by end() (would be different but) when compared with the original using operator== would return true.
Also any intermediate values generated using the assignment operator= have a post condition that they compare equal with operator== and operator== is transitive for iterators.
So yes, it is valid to store the iterator returned by end() (but only because of the guarantees with associative containers, therefor it would not be valid for vector etc).
Remember the iterator is not necessarily a pointer. It can potentially be an object where the designer of the container has defined all the operations on the class.