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 think it is clear:

• end() returns an iterator to the element one passed the end.

• Insertion/Deletion do not affect existing iterators so the returned values is always valid (unless you try to delete the element one passed then 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.

Answer 2

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.

Answer 3

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.

Answer 4

C++ Standard states that iterators should stay valid. And it is. Standard clearly states that in 23.1.2/8:

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.

And in 21.1/7:

end() returns an iterator which is the past-the-end value for the container.

So iterators old_end and new_end will be valid. That means that we could get --old_end (call it it1) and --new_end (call it it2) and it will be the-end value iterators (from definition of what end() returns), since iterator of an associative container is of the bidirectional iterator category (according to 23.1.2/6) and according to definition of --r operation (Table 75).

Now it1 should be equal it2 since 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 ++it1 and ++it2 will give old_end and new_end iterators (from definition of ++r operation Table 74). Now we get that old_end and new_end should be equal.

Answer 5

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_node

From stl_tree.h:

  _M_initialize()
  {
    this->_M_header._M_color = _S_red;
    this->_M_header._M_parent = 0;
    this->_M_header._M_left = &this->_M_header;
    this->_M_header._M_right = &this->_M_header;
  }

Answer 6

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?