Algorithms

The std::ranges::sort function is an example of a generic algorithm, so named because these functions implement common algorithms and operate generically. That is, they work for just about anything you can express as a sequential range of values. Most of the standard algorithms are declared in the <algorithm> header, although the <numeric> header contains a few that are numerically oriented.

The standard algorithms run the gamut of common programming activities: sorting, searching, copying, comparing, modifying, and more. Searches can be linear or binary. A number of functions, including std::ranges::sort, reorder elements within a sequence. No matter what they do, nearly all generic algorithms share some common features. (A few algorithms, such as std::max, std::min, and std::minmax, operate on values instead of ranges.) Ranges come in different flavors, depending on the type of the iterator and the nature of the ranged data.

A vector is an example of a sized range, that is, a range with a size that the C++ library can determine in constant time. Suppose a program defines a range of lines of text read from a file; the number of lines cannot be known beforehand, so such a range could not be a sized range.

The flavor of range also depends on the iterator type. C++ has six different kinds of iterators, but you can broadly group them into two categories: read and write.

A read iterator refers to a position in a sequence of values that enables reading from the sequence. Most algorithms require a read iterator with a corresponding sentinel in order to obtain the input data. Some algorithms are read-only and others can modify the iterated values.

Most algorithms also require a write iterator, more commonly known as an output iterator. Most algorithms use only the single output iterator instead of an output range. This is because the size of the output range is not necessarily known until the algorithm has run its course over its input.

If the input range is sized, an algorithm could use that information to set the size of an output range, but not all output ranges are sized. For example, writing the values of a vector to an output stream has a sized input but not a sized output. In order to keep algorithms generic, they rarely require a sized range as input and rarely accept a range as output.

Because a typical algorithm does not and cannot check for overflow of the output iterator, you must ensure the output sequence has sufficient room to accommodate everything the algorithm will write.

The assert function is a quick way to verify that what you think is true actually is true. You assert a logical statement, and if you are wrong, the program terminates with a message that identifies the assertion. The assert function is declared differently than the rest of the standard library, using #include <cassert> instead of import. The c means the C++ library inherits this header from the C standard library, and #include is how C imports declarations. Note that assert is one of the rare exceptions to the rule that standard library members begin with std::.

If the program is correct, it runs and exits normally. But if we make a mistake, the assertion triggers, and the programs fails with a message.

Also note the initialization of input. Listing 10-1 demonstrates another application of “universal initialization” (as introduced in Exploration 4). The comma-separated values inside the curly braces are used to initialize the elements of the vector.

Output Iterators

Good guess, but remember that the input is a range and the output is just an iterator. Wouldn’t it be nice if the name of the class that treats the input as a range were std::input_range? But the name is actually std::ranges::istream_view. A view is a kind of range that is easy to copy or assign. By naming this type a view, it tells you that you can assign an istream_view variable without incurring a runtime penalty.

The job is now to use the std::ranges::copy() function to copy a range of int values from std::cin to the data vector. But here we run into a problem of setting the size of data to match the number of input values. The emplace_back() function extends the size of a vector to accommodate the new value, so how do we arrange to call emplace_back() for every element that is read from the istream_view?

Ugly C++ truth: sometimes you need parentheses and sometimes you need curly braces and sometimes you need angle brackets and sometimes you need square brackets. How do you know when to use what? By memorizing the rules of the language and library. Okay, it’s not quite that bad. Square brackets are used for subscripts and angle brackets are used for types. But parentheses and curly braces can be downright confusing.

In Exploration 2, I enhorted you to use curly braces when initializing a variable. You do the same when creating an object, such as an iterator, on the fly. For example, you can create an ostream_iterator object and pass it to a function, such as copy. Because you are creating an object, you should use curly braces. But what about back_inserter? It is actually a function that takes its argument and uses it to create and return a back_insert_iterator object. By using the type (std::vector<int>) of its argument (data), back_inserter() can create the right kind of back_insert_iterator object. A result of this complication is that you need to remember what’s a function and what’s a type.

In Exploration 9, I threw an ugly for loop at you just to scare you prior to introducing the ranged for loop. It’s time to start breaking down that ugly code and understand what the various pieces mean. The next Exploration takes a closer look at the handy increment (++) operator.