Only Use Valid Iterators
Do you remember what a “dangling pointer” is?
Yes. It's when you use a pointer after you've deleted the object it points to. The thing you want isn't there any more, so it's not valid to try to use the pointer.
-
Right. It's your job as the programmer to only use pointers that point to things that are still there. And that's a good description: not valid.
And iterators are like pointers in this way! You can only use an iterator if it's valid to do so.
-
For example, if you have destroyed the data structure an iterator refers into, that iterator is no longer valid. It doesn't make sense to try to use it if the container has gone away.
-
Similarly, with array-backed lists, resizing moves the data to somewhere else in memory, so using them typically requires you to regard all preexisting iterators for that list invalid after an insertion.
In general, data structures that provide iterators make a contract with their users about which operations preserve iterator validity and which do not.
People often say that an operation such as resizing “invalidates iterators”. That phrasing might make you think that something is happening to the iterator—that somehow the iterator itself knows that it is invalid. But that's not true!
As an analogy, think of an invalid iterator like a ticket for yesterday's concert. The ticket has expired (i.e., it's no longer valid). We could say that “the passage of time invalidates concert tickets”, but no-one goes around stamping “VOID” in large letters on all expired tickets. Your ticket looks like it always did, but it's still invalid because you came on the wrong day.
If you try to use it anyway, you might get lucky and the ticket checkers aren't looking too closely at the dates, or they choose to be nice about your mistake, and you can still get in, but you're not supposed to do that, and trying and getting caught could cause them to do anything from turning you away, reporting you to venue security, banning you from the venue, roughing you up, or calling the cops. You simply can't know what the ultimate outcome will be if you try to use an invalid concert ticket, and trying and hoping that everything works out for the best could result in serious negative consequences.
-
It's your job as a programmer to only use iterators when they're valid, and to keep track of what events might cause them to become invalid!
For pointers, Valgrind can catch many kinds of invalid pointer use, but we don't have an equivalent tool for iterators, so it's important for you to be careful about following the rules.
The need to be so careful makes me anxious. I wish the compiler would just tell me when I screw up…
Could we have iterators that are MORE friendly? Ones that can detect misuse and throw errors?
-
You certainly could—if you're the person writing the code for your data structure's iterators. Adding checks to detect misuse is always an option, but some kinds of misuse are still tricky to detect, and, of course, checking for misuse can add overhead to your program that could result in speed penalties.
-
Remember that the C++ standard library prioritizes speed over safety, and that approach is deeply embedded in C++ culture.
Actually, our C++ library does have a debug mode that adds some checks to iterators. You can turn it on by adding
-D_GLIBCXX_DEBUGto your compiler flags. It's not perfect, but it can help you catch some kinds of iterator misuse.-
That's true, but in this class, we'll write our own iterators, so we'll have to be careful to follow the rules ourselves!
An Example
Take a look at this code snippet and determine if/when the iterator ceases to be valid.
StringList* l = new StringList; // 1
StringList::iterator iter = l->begin(); // 2
delete l; // 3
while (iter != l->end()) { // 4
++iter; // 5
} // 6
Key Idea
If a container is destroyed, all of its iterators cease to be valid.
(When logged in, completion status appears here.)