Herb Sutter (http://www.gotw.ca/) chairs the ISO C++ Standard committee and is a software architect in Microsoft's Developer Division. His most recent books are Exceptional C++ Style and C++ Coding Standards.
This article isn't "off the deep end" in terms of being super advanced. Rather, it's about analyzing what happens when you go "off the deep end" with pointers and iterators.
Why You Should Be Using a Checked STL
Checked STL implementations, which means among other things implementations of the C++ Standard Library that are able to do extra iterator validation, aren't new [1]. Way back in the mists of time (in this case, in 1995), Cay Horstmann was the first person I know of to specify a "Safe STL" [2]. The idea caught on, as good ideas are wont to do, and today most major C++ Standard Library implementations offer a mode that does some level of iterator checking. For example, Dinkumware, Metrowerks, and STLport all offer such "checked" or "debug" modes [3, 4, 5].
If you haven't already done so, run (don't walk) to get a checked STL implementation, and use it. Really.
As noted in [1], as well as [2, 3, 4, 5], here are some of the mistakes that a checked STL implementation can find for you:
- Using an invalidated or uninitialized iterator. Invalidation often happens when we don't expect it, so creating an invalidated iterator by mistake is a distressingly common and subtle problem.
- Using an out-of-bounds index. Clearly we shouldn't be trying to access element 113 of a 100-element container, but sometimes we do.
- Comparing incomparable iterators. We are only allowed to compare iterators that refer into the same container. Sometimes we assume too much about iterators, especially iterators that someone else gives us, only to find that our assumptions break.
- Using an iterator "range" that isn't really a range. Similarly, passing an iterator range (e.g., first and last in the call copy( first, last, output )) is only a valid range when first precedes last, and both refer into the same container.
- Using an invalid iterator position. When we call a container member function that takes an iterator position, the iterator has to be valid and point into the container (not, for example, into some other container).
- Using an invalid ordering. Providing an invalid ordering rule for ordering an associative container or as a comparison criterion with the sorting algorithms. Without a checked STL, these would typically manifest at runtime as erratic behavior or infinite loops, not as hard errors.
Yes, checked STL implementations do have to incur some performance and bookkeeping overhead. For example, each iterator has to know the container it refers into, so that iterator pairs can be checked for comparability and range validity. For another example, each container has to keep track of all the outstanding iterators that refer into it, so that it can mark them invalid as needed.
If this overhead matters, you might choose to ship your product with iterator checking turned off. But at minimum, you should ensure that part of your routine internal testing includes running your full product test suite against a build of your product that has iterator checking turned on. If you haven't done it yet, do it, and you'll almost certainly find at least a few latent bugs the first time out (which ought to more than justify the one-time work of adding a checked build to your test plan).
Going Off the Deep End
What brings this to mind is a recent e-mail from Ilia Faingold who was using a checked STL implementation, but who wanted iterators checked for validity only if the code actually tried to dereference them. "After all," someone might reasonably wonder, "what's the harm in creating an invalid iterator (say, five off the end of a collection) if you never try to dereference it?"
No harm, probably, but it does give us a case in point to talk about why iterators are like pointers, and what that means. Here's what Ilia wrote, citing a reasonable motivating sorting algorithm example:
Many algorithms need to iterate through an array with a step of more than one (the well-known example is the Shell's sorting). When implementing such an algorithm using pointers, one may write code like the following:
int A[17]; int* endA = A + 17; for( int* ptr = A; ptr < endA; ptr += 5 ) { // ... }This fragment is pretty Standard-compliant. However, the last value assigned to ptr in the above loop is A + 20, and it points to the three-past-the-end element of array A.
It depends what you mean by "pretty Standard-compliant." Forming such a three-past-the-end pointer is undefined behavior in C and C++. You'll usually get away with this kind of minor infraction just because the software and hardware doesn't generally beat you over the head for doing this, but technically it's still undefined behavior.
To be both valid and dereferenceable, a C or C++ pointer must point to a specific object (either to an individual standalone object or to an object in an array). In addition, a pointer could point to the one-past-the-end position of an array of objects, in which case the pointer is valid but not dereferenceable. Them thar's the rules, but the C and C++ Standards don't say exactly what happens if'n you break 'em: Undefined behavior can do anything, including what you expect—in this case, nothing. The aforementioned code is counting on "nothing," though it happens that it can get away with it on most platforms.
But infracting code like this won't always be able to outrun the long arm of the Standard's law. It really is living dangerously, whether the authorities have caught it yet or not. First, this code certainly is not portable, because the undefined behavior could be different on different systems. Second, on some CPU architectures, including current ones, the aforementioned code can cause a hardware trap to occur at the point where the three-past-the-end pointer is created, whether that pointer is ever dereferenced or not. On such hardware, just loading an invalid pointer can cause a fault, whether you do anything with the pointer or not. Technically, you can't even reliably try to compare an invalid pointer to see if it's null, not because the comparison can fail but because you're not even allowed to make it exist in the first place.
The e-mail continued:
The same fragment rewritten for vectors and iterators will look like the following:
std::vector<int> V(17); for (std::vector<int>::iterator it = V.begin(); it < V.end(); it += 5) { // ... }And once more, iterator's values used inside the loop are all perfectly valid, but the last value assigned to it points to the three-past-the-end element of vector V. Certainly, I do not want this assignment to throw exceptions!
But that can already happen with pointers, even if illegal programs can sometimes live on the edge and appear to get away with it. And iterators were deliberately designed to be pointerlike.
Pointers and iterators behave alike because Alex Stepanov designed the STL so that pointers would be valid iterators over arrays. That's why you get the same behavior between pointers and iterators, and why "invalid iterator" problems generally tend to mirror all the classic characteristics of "invalid pointer" problems, including that we have problems like dangling iterators (e.g., to an object that was removed from a container, or into a deallocated container) that are directly analogous to dangling pointers (e.g., to a deallocated object).
Finally, Ilia alludes to a good answer to his question:
Nobody will insist to prohibit assignment of value 20 to an integer index i in a vector only because the 20th element of the vector does not exist, right?
Right. So one solution that makes both the pointer and iterator loops legal is to change both examples to use integer indexes. That is, change:
int A[17];
int* endA = A + 17;
for( int* ptr = A; ptr < endA; ptr += 5 )
{
// ...
}
std::vector<int> V(17);
for( std::vector<int>::iterator it = V.begin(); it < V.end(); it += 5 )
{
// ...
}
to:
int A[17];
for( int i = A; i < 17; i += 5 )
{
// ... and use A[i] instead of *ptr
}
std::vector<int> V(17);
for( int it = 0; it < V.size(); it += 5 )
{
// ... and use V[it] or *(V.begin()+it) instead of *it
}
But if it works for integer indexes, why not for iterators? That's the final question:
So why is it done for iterators?
Because iterators aren't like integer indexes, they're like pointers, and we can't do that with pointers either.
A Workaround to Fool the System?
Finally, in a follow-up conversion, Ilia came up with an interesting workaround that would let C and C++ compilers reliably support creating invalid pointers (as long as they're never dereferenced). Here's the idea:
By storing pointers as a pair of integers and loading them into the address registers only when dereferencing, it could be possible to keep the generality of pointer arithmetic.
Ilia's idea is to store pointers as a base plus an offset; for example, a pointer to the start of the array plus an integer index. Only when the pointer gets derefenced would you actually perform the addition, form the (possibly invalid) pointer, and get busted if it was out of bounds.
This would work. Unfortunately, it is impractical.
First, a minor issue is that it could only be done on a new operating-system platform. All existing operating systems I know of implement a pointer as (essentially) a plain old memory address, and so a new version of a compiler for such a platform couldn't switch to a base+offset pointer implementation without being incompatible with all existing libraries and operating-system services on that platform. The compiler would have to bend over backwards to insert extra logic that could convert back and forth across the boundary between new and old code.
The bigger issue is performance. The minor performance problem is that you'd have to do an extra addition (and possibly use an extra register) on every pointer dereference. The major performance problem is that this scheme would double the size of pointers, which is a big deal because of the impact on the working set. Remember that size is speed: A larger working set (due to having to store larger pointers) means more cache misses and less performance. On a 32-bit system, double-sized pointers would get all the performance loss of 64-bit pointers, without any of the advantages. (And, on a 64-bit system, they get the performance loss of 128-bit pointers, again with no compensating advantages.) Today we already see that different applications will run faster, slower, or just break even when built in 64-bit mode to run on 64-bit hardware, compared to the same sources built in 32-bit mode to run on 32-bit hardware. Whether a given application wins or loses by being built as 64-bit depends in part on whether the performance gain from faster hardware (and more registers, etc.) outweighs the larger working set size to store larger pointers (and therefore more cache misses, etc.). There are other issues with 64-bit, but these are the ones that directly affect size and so are applicable to the question of having larger pointers.
To incur the working set bloat and performance penalty of bigger pointers, but without getting a compensating gain in some other form, is pretty much a nonstarter. In this case, the only gain would be having the ability to legally form pointers that can't ever be dereferenced, and that isn't enough to justify the cost.
Conclusion
Stay away from the dark corners of the language, especially dark corners that actually go beyond the edge of legally defined behavior. Don't create invalid pointers, because even when it seems like you're getting away with it, the code's behavior is actually undefined and therefore nonportable, and can break at runtime on other hardware or operating systems. If you have to skip through a loop with increments that can be greater than one, prefer to use indexes instead of iterators.
But, most of all: Do get a checked STL and turn all the checking on. Use it daily and automatically, at least in test builds. You'll be glad you did.
References
- Sutter, H. and A. Alexandrescu. "Item 83: Use a Checked STL Implementation," in C++ Coding Standards, Addison-Wesley, 2005.
- Horstmann, C.S. "Safe STL," 1995; http://www.horstmann.com/ safestl.html.
- Dinkum Unabridged Library; http://www.dinkumware.com/libdual .html.
- Metrowerks C++ Standard Library; http://www.metrowerks.com/.
- Fomitchev, B. "STLport: Debug Mode"; http://www.stlport.org/doc/ debug_mode.html.
CUJ
