StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POIs end() required to be constant in an STL map/set?
text
Body
copied!<p>§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).</p> <p>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:</p> <pre><code>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; }; </code></pre> <p>(<strong>EDIT</strong>: Not literally like this due to the incompleteness of <code>Node</code> in line 4 (see responses/comments), but along these lines anyway)</p> <p>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).</p> <p>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 <code>nodes.end()</code>... or can we? Is there some sort of guarantee that <code>nodes.end()</code> at 8 AM will be the same as <code>nodes.end()</code> at 10 PM after a zillion insertions/deletions? That is, can I safely <code>==</code> compare an iterator received as a parameter to <code>nodes.end()</code> in some method of Graph?</p> <p>And if not, would this work?</p> <pre><code>class Graph { private: std::map<int, Node> nodes; std::map<int, Node>::iterator _INVALID; public: Graph() { _INVALID = nodes.end(); } }; </code></pre> <p>That is, can I store <code>nodes.end()</code> 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 <code>_INVALID</code>?</p> <p>And if this doesn't work either, what <em>can</em> I do to leave room for an invalid neighbor value?</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload