Previous | Table of Contents | Next |
Once we have our data stored in the map, we must retrieve it. To that end, the library supplies a type called a map iterator. We can think of an object of such a type as behaving somewhat like a pointer: It identifies a location in the map and lets us step through the map one element at a time.
When we say
map<string, int>::const_iterator it;
we are defining a local variable named it whose type is appropriate for a constant iterator (i.e. an iterator that does not have permission to change the values of the map over which it iterates) over a map from string to int. We are not intended to know the type of this object directly, but the library guarantees that we can do certain things with objects of that type.
The for statement that follows the definition of it could just as well have been written as
it = m.begin(); while (it != m.end()) { cout << setw(8) << it->second << << it->first << endl; ++it; }
The map type defines m.begin and m.end as functions that return iterators that refer directly to the first element and one past the last element of m, respectively. The reason that m.end() does not refer to an element is that an empty map has no elements to which to refer. Instead, many C++ library facilities adopt the notion of asymmetric bounds by delimiting a range by its first element (if there is one) and one past its last element (or where its last element would be). This practice implies, for example, that m.begin() and m.end() are equal if and only if m has no elements.
Each time through the loop, we execute ++it. Earlier, we noted that ++m[s] added 1 to m[s], but we could say that only because we knew that m[s] was an integer. Here, on the other hand, we do not know the type of itso what does it mean to add 1 to it?
In fact, it might not mean anything at all. Instead, when we deal with iterators or other C++ abstract data types, we should think of ++ as a way to cause an object to take on the next value in the sequence of values that it might have. Fortunately,1 that treatment does what we wanted, which is to cause it to refer to each of the elements of m in turn.
1By design, actually.
All we need to know, for now, about it is that if the value of m[s] is i, then at some point it will take on a value such that it->first is s and it->second is i. We shall see later how such things are possible. For now, our knowledge indicates that if we print the values of it->second and it->first, in that order, for each value of it, we will get the results we seek.
We have already seen how to use cout to print values. The one other new idea in this example is the use of setw to control the output format: Saying cout << setw(8) guarantees that the next value written on cout will occupy at least 8 characters in the output stream. Think of setw as meaning set the width.
If we run this program with
as I was going down the stair I saw a man who wasnt there he wasnt there again today I wish that man would go away
as input, its output will be
3 I 1 a 1 again 1 as 1 away 1 down 1 go 1 going 1 he 2 man 1 saw 1 stair 1 that 1 the 2 there 1 today 1 was 2 wasnt 1 who 1 wish 1 would
If you were to conclude from this output that C++ associative arrays store their elements in increasing order by subscript, you would be quite correct.
It would have been possible to define C++ so that types like map were built into the compiler. Indeed, some languages, such as Awk (described in The Awk Programming Language, by Aho, Kernighan, and Weinberger [1988]), make it possible to write programs that look quite a bit like these C++ examples. C++, in contrast, takes a more general approach: The language includes facilities that make it possible for libraries to define these data types, as well as others.
The language needs a substantial amount of mechanism in order to allow the construction of libraries that make these examples possible. For example, consider just the input loop of our word-counting program:
string s; while (cin >> s) ++m[s];
Even if we ignore, for the moment, the associative array that does the word counting, there is still a lot going on behind the scenes in
cin >> s
After we execute this expression, s contains a word that has been read from the standard input. Aside from the total amount of memory available, there is no limit on how long that word might be. Therefore, the library must allocate dynamic memory to contain that word, and must continue to allocate more memory as needed if the word turns out to be very long.
Similarly, if we were to say
string t = s;
the library would have to arrange to copy the characters stored in s into the newly created string t, again without knowing, until the statement is actually executed, how much memory the string might occupy. Note again that it is not sufficient that the language contain such mechanisms directly. Rather, it must contain mechanisms that allow such flexible strings to be implemented in the library, even though the language does not know about strings on its own account.
Sections 7.2 through 7.5 talk about these mechanisms. We will begin with an overview of the fundamental types, after which we will talk about classes, or user-defined abstract types. Next, we will discuss templates, which are the main mechanism for writing generic programs, and virtual functions, which are essential for writing object-oriented programs. Section 6 gives a brief overview of the key ideas behind the C++ standard library.
Previous | Table of Contents | Next |