To ask Pete a question about C or C++, send e-mail to pbecker@wpo.borland.com, use subject line: Questions and Answers, or write to Pete Becker, C/C++ Users Journal, 1601 W. 23rd St., Ste. 200, Lawrence, KS 66046.
Q
I compiled the following program with several different compilers and got a couple different results. Some said the result was 0 and some said it was 1. Which is the right answer?
#include <stdio.h> int main() { int i = 0; i = i++; /* what's up with this? */ printf( "Value is: %d\n", i ); return 0; }A
Both. And many others, as well, although these two results are probably the most common. The effect of the expression i=i++ is undefined. The C Standard does not specify what a compiler must do with an expression like this.
This expression has generated extensive discussion recently on the Internet, in the comp.lang.c newsgroup. The discussion has been most notable for its absence of insight into how to approach problems like this. The most vehement participants in the discussion seem to fall into two camps: those who argue for 0 as the correct result, and those who argue for 1. Neither of these groups seem to be interested in what the language definition says, preferring to argue from personal preference and from what they consider to be common knowledge. I have seen a few messages from people who have read and understood the pertinent parts of the language definition, but the more vocal of the posters tend to ignore these messages.
Those who expect i=i++ to produce 0 argue as follows: the value of the sub-expression i++ is 0, so that's what should be assigned to i by this expression. The argument that i=i++ should produce the value 1 is equally simple: post-increments happen after everything else in the expression, so the assignment itself copies 0 into i, then the increment increases the value of i to 1. Each of these arguments work fine in less incestuous expressions like j=i++: each gives the correct result, with j ending up with the value 0 and i ending up with the value 1. Neither agrument is actually correct according to the language definition.
The root of the problem here is that we tend to develop our own rules for analyzing and writing code. Our internal rules are generally easier to apply than the detailed rules of the language definition, primarily because they are simplified versions of the actual rules. This ease of use is deceptive, though, because our simplified rules are incorrect for the edge cases, which are responsible for the apparent wordiness and detail in the language definition itself.
If you find yourself deeply embroiled in an argument over a piece of C code ask yourself this: are you blindly applying some internal rule instead of the rule provided by the language definition? There's a good chance that you are, and that looking for the true rule will lead you to a better understanding of how the code actually works.
In the case of i=i++, most people apply the internal rules I set out earlier: look at the right-hand side of an assignment first, then look at the left side; and post-increments happen last. This approach seems sensible because breaking a statement down into simpler parts makes it easier to understand the complex statements that C allows programmers to write. But focusing our attention on parts of the expression diverts us from our true goal, which is understanding the expression as a whole. We're very good at analysis — breaking a complex object expression down into simpler pieces; we're not so good at synthesis, which is rebuilding that complex expression once we understand its pieces.
Rebuilding a code sequence from its constituent parts often entails a few rules that were not involved in breaking that expression into parts. These new rules deal with combining expressions into larger ones. For example, in analyzing i++ we usually wouldn't concern ourselves, initially, with whether i had previously been defined or how it was initialized. However, once it becomes part of a larger expression we must pay attention to more things than simply the meaning of the ++ operator.
One of the most important concepts pertaining to expression interpretation is the sequence point. A sequence point is a point in the source code which separates which side effects must have executed and which must not have executed. Specifically, all side effects that show up in the source code after the preceding sequence point must have occurred (been executed), and all side effects that occur after the current sequence point must not have occurred.
The semicolon at the end of a statement is the most common sequence point. When the compiler reaches a semicolon it has to finish up any side effects that haven't executed. The C Standard defines several other sequence points, but they are not relevant here. Note, however, that an assignment operator is not a sequence point. C has no requirement that side effects of sub-expressions in an assignment expression take place before the assignment itself.
As a consequence of the sequence points rules, the argument for i=i++ producing 0 falls apart. This expression contains no sequence point, so the language definition does not require that the increment take place before the assignment. Under the same sequence point rules, the argument for i=i++ producing 1 falls apart as well. Again, because there is no sequence point inside the expression, the language definition does not require that the increment take place after the assignment. Sequence points do not govern the relative order of the assignment and the post-increment in this expression. (The only requirement imposed by sequence points is that the increment must take place before moving past the next sequence point.) The rules defining C give us insufficient information to evaluate i=i++. Understanding sequence points will lead you to question the meaning of an expression like i=i++.
In fact, the C language definition goes a step further: it says that the effect of an expression that modifies a value twice without an intervening sequence point is undefined. Undefined means that a Standard-conforming C compiler is free to treat such a statement in any way at all. It can generate code that produces 0 or 1, it can generate code that produces any other value, it can generate code that plays a game of NetHack, or it can produce code that crashes your program. If your program uses i=i++ it is not a valid C program. You cannot rely on it doing any particular thing. Don't use expressions like this in your code.
Q
I've been playing a little with the Standard Template Library, and I don't understand iterators. I can get an iterator to move through a container, but I can't figure out how to tell when it's done. I tried using !iter, but the compiler said that wasn't legal. How do I do this?
A
The Standard Template Library has recently been added to the working paper for the C++ language standard. STL lets you write algorithms that work with the contents of any container without having to know about the internal implementation of the container. Every STL-compliant container must provide a type known as an iterator, which allows the algorithm to transfer data in and out of the container, while hiding details of the container's implementation.
Most iterators are meant to be used in pairs. The first iterator in the pair points to the beginning of the range of data that you want to work with. The second iterator points just past the end of the data range. You move through the container's contents by incrementing the first iterator until it compares equal to the second. For example, consider the following code to display an array of integers' contents:
#include <iostream> void show( int *begin, int *end ) { while( begin != end ) cout << *begin++; } int main() { int a[100]; for( int i = 0; i < 100; i++ ) a[i] = i; show( a, a+100 ); return 0; }In main we create an array of integers and initialize its contents. Then we call show, passing a pointer to the first element of the array and a pointer past the end of the array. Inside show we simply walk through the array by incrementing begin until it is equal to end. That's all there is to using iterators.
If we want to make show into a general purpose STL algorithm all we need do is rewrite it slightly so that it takes an arbitrary iterator type instead of a pointer to int:
#include <iostream> template <class InputIterator> void show( InputIterator begin, InputIterator end ) { while( begin != end ) cout << *begin++; }We can use this template exactly as we used the earlier show function:
int main() { int a[100]; for( int i = 0; i < 100; i++ ) a[i] = i; show( a, a+100 ); return 0; }The compiler sees a call to a function named with show two arguments of type pointer to int, so it instantiates the function template show with InputIterator replaced by int *. The result is a template instantiation that does exactly the same thing as our earlier function version: it walks through an array of integer values, displaying them one by one, until begin is equal to end.
We can use the same template to show a range of values held in an STL vector:
#include <vector> int main() { vector<int> v; for( int i = 0; i < 100; i++ ) v[i] = i; show( v.begin(), v.end() ); return 0; }This use of show is a little more complicated. The compiler sees a call to a function named show with two arguments. The type of the first argument is whatever type is returned by the function vector<int>::begin(), and the second argument's type is the type returned by vector<int>::end(). You can't tell by looking at this code whether begin and end return pointers or classes, but it doesn't matter. As long as begin and end return the same type the compiler will try to instantiate show for that type.
Of course, instantiating show for the type returned by begin and end is only valid if the operations that show does on this type are valid. A careful examination of show reveals that it requires argument types supporting four operations: copying of arguments when they are passed to the function; comparison of arguments inside the while statement; dereferencing of the first argument, and incrementing of the first argument as part of the insertion into cout. These four operations define what STL refers to as an input iterator. In fact, naming the template parameter InputIterator is intended to remind users of this algorithm that the algorithm requires only the operations that are defined for an input iterator. Any type that provides these four operations can be used as the argument type in a call to show. That's why we can use show with pointers: they support copying, comparing, dereferencing, and incrementing. We can also use show with the type returned by begin and end, because the writer of vector made sure that begin and end return a type that is suitable for use as in input iterator.
In addition to requiring these four operations of input iterators, STL requires that the pair of iterators used for input define a range. The first iterator, when dereferenced, produces a reference to the first element in the range. The second iterator won't be dereferenced by any STL-conforming algorithm, but will compare equal to the first when the first has been incremented through the entire range of interest. The ability to compare iterators enables us to loop through the entire range and know when to stop, without dereferencing the second iterator. That's the abstraction that STL presents, and that is the abstraction that you should keep clearly in mind when you are using STL in your code.
Rules for Containers
We've been looking at how iterators work, but we should also look at the requirements STL imposes on containers. For example, every STL container has a nested typedef that names its iterator type. That is, if you want to explicitly create an iterator into a container you can do something like this:
#include <vector> vector<int>::iterator iter;The actual type of the iterator usually isn't important. What matters is that you can create an iterator object when you need to, and can do so in exactly the same way for all STL containers.
STL containers also provide the two member functions begin and end. As we saw above, these functions return an iterator that points to the first element in the container and an iterator that points past the end of the container. Most of the time the iterators returned by these functions will be used as temporary objects, created only as arguments to a template function. Once again, the actual type of these iterators is not important. The compiler will figure it out, and generate the appropriate code for the template function.
So, to answer your question, finally, the reason you can't use !iter to determine when you have reached the end of a container is that STL wasn't designed to work that way. STL works with pairs of iterators which define a range. An algorithm has completed its work when the two iterators compare equal. Once you've learned to think in terms of ranges rather than individual iterators you'll have a much easier time using STL.
Pete Becker is Senior QA Project Manager for C++ at Borland International. He has been involved with C++ as a developer and manager at Borland for the past six years, and is Borland's principal representative to the ANSI/ISO C++ standardization committee.