C++ for Non-C++ Programmers - From Mathematics to Generic Programming (2015)

From Mathematics to Generic Programming (2015)

Appendix C. C++ for Non-C++ Programmers

This book generally uses a subset of C++ that should be easily understandable to most programmers who have used a language like C or Java. However, there are a few important features and idioms specific to C++ that we rely on. These are described in this Appendix. Except where noted, we use only features of C++ that have been available in the 1998 standard version of the language. For a good brief introduction to C++11, see A Tour of C++ by Bjarne Stroustrup. For a complete reference, see Stroustrup’s The C++ Programming Language.

C.1 Template Functions

One way C++ supports the generic programming paradigm is through the use of templates. Suppose you have a function like this:

int my_function(int x) {
int y;
... do something complicated ...
return y;
}

Now you want to do the same set of computations, but this time you want the function to take and return a double-precision floating-point number. C++ allows you to overload the function name, so you can write a whole new function with the same name that works with different types:

double my_function(double x) {
double y;
... do something complicated ...
return y;
}

But if everything is the same except for the type, writing a whole separate function is wasteful.

Templates avoid this problem. With templates, you can write a single function to work on any type that satisfies both the syntactic and semantic requirements of the code, like this:

template <typename T>
T my_function(T x) {
T y;
... do something complicated ...
return y;
}

Now we have a function that takes type T and returns type T, where T depends on how the function is called. On the one hand, if you say

int x(1);
int y = my_function(x);

then my_function() will be called with T set to int. On the other hand, if you say

double x(1.0);
double y = my_function(x);

then my_function() will be called with T set to double. This is done at compile time, so there is no performance penalty for using templates.

C.2 Concepts

Concepts are the essential part of generic programming, and we discuss them in some detail in Section 10.3. The following discussion is intended to be a quick reference.

Ideally, we would like to have a way to tell the programmer what the requirements are on a given template argument. For instance, we’d like to say

template <Number N>

and have that mean that whatever type this function gets called with must be a number. This means the code is intended to work for things ints and doubles and uint64_ts, but not, say, for strings. A restriction like “Number” is an example of a concept. Unfortunately, as of this writing, C++ does not support concepts as a built-in part of the language—that is, C++ does not have any way to enforce requirements on template types.

Despite this limitation, we will write our code examples as if concepts were present in the language. We can implement this by just defining our favorite concepts as aliases for typename:

#define Number typename

So when we write

template <Number N>

as far as the compiler is concerned, it’s as if we wrote

template <typename N>

but the human programmer will understand the intended restriction.

C.3 Declaration Syntax and Typed Constants

C++ provides multiple ways to declare and initialize a variable. While the traditional C syntax

int x = y;

is legal, the common way to write this in C++ is

int x(y);

This is more consistent with the syntax used to construct arbitrary C++ objects. (Note: The current version of C++ supports an additional way to do initialization:

int x{y};

However, this usage is still less widespread, so we do not use it in our examples.)

When using numeric constants, we’ll be very careful about types. For example, a traditional C program might contain a line like this:

if (something) return 0;

This is a bit sloppy. Which type is the 0 returned by the function? By default, it’s an int, but suppose our program was supposed to return a specific kind of integer, like a 16-bit unsigned integer, or one specified by a template argument. Rather than rely on implicit type conversion, we’ll try to be explicit about what we’re returning by writing something like this:

if (something) return uint16_t(0);

or, in the case of a template argument:

if (something) return T(0);

where T is the type specified in the template.

C.4 Function Objects

Often we’d like to have a function that requires some initialization and maintains some state. A common way to implement this in C++ is by the use of a function object, also called a functor. A function object is an object that encapsulates a single (unnamed) function. Let’s look at a simple example—a function object for doing currency conversion:

struct converter {
double exchange_rate;

converter(double ex) : exchange_rate(ex) {}

double operator()(double amt) {
return amt * exchange_rate;
}
};

Note the use of the syntax operator() to declare the unnamed function that belongs to the object.

To use this function, we first construct an instance of our converter object (which initializes the exchange rate). In this example we want to convert euros to U.S. dollars, so we’ll name our instance eur_to_usd. Then we can invoke the function by using that instance:

int main() {

converter eur_to_usd(1.3043);

double euros;
do {
std::cout << "Enter amount in Euros: ";
std::cin >> euros;
std::cout << euros << " euros is "
<< eur_to_usd(euros) << " dollars "
<< std::endl;
} while (euros > 0.0);
}

Function objects have the benefit that we can pass them as arguments to functions. (C++ does not allow passing functions directly, only function pointers, which requires the added cost of an indirect function call.) In addition, function objects can contain state information.

C.5 Preconditions, Postconditions, and Assertions

Given valid arguments, a function performs a certain computation. Another way to put this is that if its preconditions are satisfied, certain postconditions will be true. Sometimes we write these preconditions and postconditions as comments in our code, like this:

// precondition: y != 0.0
double my_ratio(double x, double y) {
return x / y;
}
// postcondition: returned value is x/y

However, the library also provides a mechanism called assert for checking some conditions. So we could write:

double my_ratio(double x, double y) {
assert(y != 0.0);
return x / y;
}

If the assert expression evaluates to true, nothing happens. But if it evaluates to false, execution of the program halts and an error message is printed.

In production code, assertions are typically disabled to avoid a performance penalty.

C.6 STL Algorithms and Data Structures

The C++ language contains a library of standard software components, known as the Standard Template Library (STL). This library includes data structures, algorithms, and other utilities commonly used by C++ programmers. All STL components belong to the namespace std; we will explicitly use the prefix std:: when we refer to them in our code examples.

STL is a generic library, meaning that each component can be used with any appropriate type. In the case of data structures, the types are specified as template arguments when the object is declared. For example,

std::vector<int> v;

declares a vector of integers, while

std::vector<bool> v;

declares a vector of Booleans.

The following STL components are used in this book:

Function objects for arithmetic operations and comparisons (see Section C.4 for explanation of function objects):

• std::plus—Computes the sum of its operator’s two arguments.

• std::multiplies—Computes the product of its operator’s two arguments.

• std::negate—Computes the negation of its operator’s argument.

• std::less—Returns true when its operator’s first argument is less than its second, false otherwise.

• std:less_equal—Returns true when its operator’s first argument is less than or equal to its second, false otherwise.

Data structures:

• std::pair—A struct that stores two arbitrary objects; typically used to return two things from a function.

• std::vector—A container for a sequence of elements of a single type that supports constant-time random access.

Algorithms:

• std::fill—Fills the range specified by its first two arguments with the value specified by the third argument.

• std::swap—Exchanges the contents of its arguments.

• std::partition_point—Returns an iterator to the first element in an already partitioned range (specified by the first two arguments) for which the given predicate (third argument) is not true. See discussion in Section 10.8.

Other utilities:

• std::advance—Increments the position of an iterator (its first argument) by a distance (second argument).

For a more detailed description of these and other STL components, see Part IV of Stroustrup’s The C++ Programming Language.

C.7 Iterators and Ranges

Iterators are an important part of generic programming, and we discuss them in greater detail in Section 10.4. The following discussion is intended to be a quick reference.

Iterators are an abstraction of pointers; an iterator indicates a position in a sequence. The examples in this book use these four types of iterators, each with its own iterator tag.

• Input iterators support one-directional traversal, but only once, as is found in single-pass algorithms. The canonical model of an input iterator is the position in an input stream.

Tag: std::input_iterator_tag

• Forward iterators also support only one-directional traversal, but this traversal can be repeated as needed, as in multi-pass algorithms. The canonical model of a forward iterator is the position in a singly linked list.

Tag: std::forward_iterator_tag

• Bidirectional iterators support bidirectional traversal, repeated as needed (i.e., they also can be used in multi-pass algorithms). The canonical model of a bidirectional iterator is the position in a doubly linked list.

Tag: std::bidirectional_iterator_tag

• Random-access iterators support random-access algorithms; that is, they allow access to any element in constant time. The canonical model is the position in an array.

Tag: std::random_access_iterator_tag

The iterator tags are special types that may be used in function signatures to ensure that the correct version of an overloaded function will be invoked when a given iterator is used; see Chapter 11 for an example.

* * *

STL functions often take two iterators representing the beginning and end of a range of data. By convention, the iterator for the end of the data (often called last) points to the position directly after the last element.

Iterators also have special attributes called iterator traits. The ones we use are:

• value_type: the type of the objects pointed to by the iterator.

• difference_type: an integral type large enough to express the number of increment operations needed to get from one iterator to another.

• iterator_category: the iterator tag, described earlier.

The syntax to access an iterator trait for a particular iterator type x is (for example)

std::iterator_traits<x>::value_type

For more information on iterators, see Chapter 10.

C.8 Type Aliases and Type Functions with using in C++11

C++11, the current standard version of C++, has a feature called using that allows programmers to provide aliases for types and other constructs. This is typically used to provide a short way to write a long and complicated type. For example:

using myptr = long_complicated_class_name*;

After writing this statement, programmers could refer to myptr in the code wherever they would have previously written long_complicated_class_name*.

Users of C and earlier versions of C++ may be familiar with an older aliasing mechanism, typedef, but using is more flexible. For example, the using feature allows us to write templatized type functions for iterator traits. If we write

template <InputIterator I>
using IteratorCategory =
typename std::iterator_traits<I>::iterator_category;

then every time we want to know the category of an iterator, we can say

IteratorCategory<I>

rather than

std::iterator_traits<I>::iterator_category

C.9 Initializer Lists in C++11

In C and C++, you can conveniently initialize an array by enclosing the list of values in curly braces, like this:

char my_array[5] = {'a', 'e', 'i', 'o', 'u'};

C++11 extends this syntax beyond arrays, so now you can also write things like this:

std::vector<char> = {'a', 'e', 'i', 'o', 'u'};
std::pair<int, double> = {42, 3.1415};

C.10 Lambda Functions in C++11

C++11 includes support for lambda functions. These are anonymous functions that are needed only once, often as arguments to another function.

Suppose for some application, we wanted to take a function that computed the cube of its argument and pass it to another function. Traditionally, we’d have to implement this as a function object, declare it separately, instantiate it, and pass the instance, like this:

struct cuber {
cuber() {}; // constructor

int operator()(int x) {
return x * x * x;
}
};

int main() {
...
cuber cube;
int a = some_other_function(cube);
...
}

But if this is the only time we ever need the cube function, that’s a lot of work. Why bother creating the function object, or even giving the function a name, when we’re never going to use it again? Instead, we can write a lambda function inline and pass the whole expression as an argument:

int main() {
...
int a = some_other_function([=](int x) { return x * x * x; });
...
}

The syntax for lambda functions is just like the syntax for implementing any other function, except that the name of the function is replaced by the expression [=], and the return type usually does not need to be specified; the compiler figures it out.

C.11 A Note about inline

The C++ directive inline before a function is a hint that tells the compiler that the programmer would like the body of the function to be included as part of the code of the caller, avoiding the usual function call overhead. In practice, many functions in this book would benefit today from being declared inline.

Inlining makes sense only for relatively small pieces of code. Larger inlined functions could end up increasing the size of the calling code enough to disrupt code caching or cause other performance problems. Compilers take this into account and ignore the inline request in those cases. At the same time, compilers are getting smart enough to inline code automatically when it makes sense. For these reasons, the inline directive will soon be obsolete, so we did not use it in our examples.