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

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 == &*b or if neither can be dereferenced. Finding the bolded statement took a while and is very relevant here.

Because an std::map::iterator cannot be invalidated unless the element it points to has been removed, you're guaranteed that two iterators returned by end, regardless of what the state of the map was when they were obtained, will always compare to each other as true.

Answer 2

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 3

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, but old_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>::iterator in the Node class due to the type being incomplete, yet (not sure, though).

Also, since your nodes are uniquely numbered, you can use int for keying them and reserve some value for invalid.

Answer 4

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.