Now that you understand the basics, it is time to start moving on to more exciting challenges. Let’s write a real program, something nontrivial but still simple enough to master this early in the book. Your job is to write a program that reads integers from the standard input, sorts them into ascending order, and then prints the sorted numbers, one per line.

At this point, the book has not quite covered enough material for you to solve this problem, but it is instructive to think about the problem and the tools you may need to solve it. Your first task in this Exploration is to write pseudo-code for the program. Write C++ code where you can and make up whatever you need to tackle the problem.

Vectors for Arrays

You need an array to store the numbers. Given only that much new information, you can write a program to read, sort, and print numbers, but only by hand-coding the sort code. Those of you who suffered through a college algorithms course may remember how to write a bubble sort or quick sort, but why should you need to muck about with such low-level code? Surely, you say, there’s a better way. There is: the C++ standard library has a fast sort function that can sort just about anything. Jump straight into the solution in Listing 9-1.

Listing 9-1.  Sorting Integers

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <vector>
 4
 5 int main()
 6 {
 7   std::vector<int> data{};     // initialized to be empty
 8   int x{};
 9
10   // Read integers one at a time.
11   while (std::cin >> x)
12     // Store each integer in the vector.
13     data.push_back(x);
14
15   // Sort the vector.
16   std::sort(data.begin(), data.end());
17
18   // Print the vector, one number per line.
19   for (std::vector<int>::size_type i{0}, end{data.size()}; i != end; ++i)
20     std::cout << data.at(i) << '
';
21 }

Notice anything unusual about the program? Where is the array? C++ has a type called vector, which is a resizable array type. The next section explains it all to you.

Vectors

Line 7 defines the variable data, of type std::vector<int>. C++ has several container types, that is, data structures that can contain a bunch of objects. One of those containers is vector, which is an array that can change size. All C++ containers require an element type, that is, the type of object that you intend to store in the container. In this case, the element type is int. Specify the element type in angle brackets: <int>. That tells the compiler that you want data to be a vector and that the vector will store integers.

What’s missing from the definition?

_____________________________________________________________

The vector has no size. Instead, the vector can grow or shrink while the program runs. (If you know that you need an array of a specific, fixed size, you can use the type array. You will use vector much more often than array.) Thus, data is initially empty. Like std::string, vector is a library type, and it has a well-defined initial value, namely, empty, so you can omit the {} initializer if you wish.

You can insert and erase items at any position in the vector, although the performance is best when you add items only at the end or erase them only from the end. That’s how the program stores values in data: by calling push_back, which adds an element to the end of a vector (line 13). The “back” of a vector is the end, with the highest index. The “front” is the beginning, so back() returns the last element of the vector, and front() returns the first. (Don’t call these functions if the vector is empty; that yields undefined behavior.) If you want to refer to a specific element, use at(n), where n is a zero-based index, as shown on line 20. The size() function (line 19) returns the number of elements in the vector. Therefore, valid indices range from 0 to size() - 1.

When you read C++ programs, you will most likely see square brackets (data[n]) used to access elements of a vector. The difference between square brackets and the at function is that the at function provides an additional level of safety. If the index is out of bounds, the program will terminate cleanly. On the other hand, using square brackets with an invalid index will result in undefined behavior: you don’t know what will happen. Most dangerous is that your program will not terminate but will continue to run with the bad data. That’s why I recommend using at for now.

As you can tell from the std:: prefix, the vector type is part of the standard library and is not built into the compiler. Therefore, you need #include <vector>, as shown on line 3. No surprises there.

All the functions mentioned so far are member functions; that is, you must supply a vector object on the left-hand side of the dot operator (.) and the function call on the right-hand side. Another kind of function does not use the dot operator and is free from any particular object. In most languages, this is the typical kind of function, but sometimes C++ programmers call them free functions, to distinguish them from member functions. Line 16 shows an example of a free function, std::sort.

How would you define a vector of strings?

_____________________________________________________________

Substitute std::string for int to get std::vector<std::string>. You can also define a vector of vectors, which is a kind of two-dimensional array: std::vector<std::vector<int>>. (Prior to C++ 11, you needed to insert a space between the closing angle brackets, so you will see a lot of code written that way. But in C++ 11, you don’t need to concern yourself with that syntax oddity.)

Iterators

The std::sort function sorts stuff, as you can tell from the name. In some other object-oriented language, you might expect vector to have a sort() member function. Alternatively, the standard library could have a sort function that can sort anything the library can throw at it. The C++ library falls into the latter category, but with a twist.

The twist is that the std::sort function does not take a vector as an argument to sort the contents of the vector. Instead, you pass two values to the sort function: the start of a range and the one past the end of the range. The sort function sorts the values in that range. The elements in the range can be any type, as long as the compiler knows how to compare objects with the less-than (<) operator. The example program specifies the starting position by calling data.begin() and one past the end by calling data.end().

These “positions” are called iterators. An iterator is an object that can refer to an element of a sequence. As the name implies, an iterator can also iterate over a sequence. The sequence might be elements of a vector or they could be data in a file or database or nodes in a tree. The implementation of the sequence is irrelevant, and the std::sort function knows nothing about it. Instead, the sort function sees only the iterators.

Iterators present a simple interface, even if their implementation is complicated. The * operator returns the value to which the iterator refers (*iter), and you can advance an iterator to the next element of the sequence (++iter). You can compare two iterators to see if they refer to the same element (iter1 == iter2). Iterators come in different flavors, and some flavors let you modify the element or move backward in the sequence.

A bounded loop requires a starting and ending position. One way to specify these for a vector is to specify the positions of the first and last elements, but that raises a thorny issue of what to do with an empty vector. Long ago, computer scientists invented the concept of a sentry or guard. Sometimes, the sentry was a real element added after the last element of a container, marking the position one past the last element. In that case, a container with only the sentry element was empty. Iterators work similarly, but whether the container has a true sentry is a hidden implementation detail. A special iterator value represents the sentry at a position of one past the last element in the container, even if the container has no actual sentry element. The notion of “one past the end” is a common idiom in the C++ library and programs.

Thus, data.begin() returns an iterator that refers to the first element of data, and data.end() returns an iterator with the special one-past-the-end value, as shown in Figure 9-1.

What is the value of data.begin() if data.size() is zero?

_____________________________________________________________

That’s right. If the vector is empty, data.begin() returns the same value as data.end(), and that value is a special sentry value that you are not allowed to dereference. In other words, *data.end() results in undefined behavior. Because you can compare two iterators, one way to determine if a vector is empty is to test, as demonstrated in the following code:

data.begin() == data.end()

A better way, however, is to call data.empty(), which returns true if the vector is empty and false if the vector contains at least one element.

Iterators have many uses beyond accessing elements of a vector, and you will see them used often in this book, for input, output, and more, starting with the next Exploration.