Is end() required to be constant in an STL map/set?

Question

§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?

Answer 1

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

Answer 2

You write (emphasis by me):

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

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.

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_map_t::iterator old_end = my_map.end(); // wildly change my_map assert( old_end == my_map.end() );  

My interpretation is that, if old_end remains "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?