Use of Templates

Templates are used to allow generic programming. They make it possible to write code that can work with all kinds of objects, even objects unknown to the programmer when writing the code. The obligation of the programmer writing the template code is to specify the requirements of the classes that define these objects; for example, that they have an operator for comparison, or a copy constructor, or whatever is deemed appropriate, and then making sure the code that is written uses only those required capabilities. The obligation of the programmer creating the objects is to supply those operators and methods that the template writer requires.

Unfortunately, many programmers consider templates to be the most difficult part of C++ and, for that reason, tend to avoid them. However, even if you never write your own templates, you need to understand their syntax and capabilities in order to use the Standard Library. Templates are described in detail in Chapter 12. If you skipped that chapter and are not familiar with templates, I suggest you first read Chapter 12, and then come back to learn more about the Standard Library.

Use of Operator Overloading

Operator overloading is another feature used extensively by the C++ Standard Library. Chapter 9 has a whole section devoted to operator overloading. Make sure you read that section and understand it before tackling this and subsequent chapters. In addition, Chapter 15 presents much more detail on the subject of operator overloading, but those details are not required to understand the following chapters.

Strings

C++ provides a built-in string class, defined in the <string> header. Although you may still use C-style strings of character arrays, the C++ string class is superior in almost every way. It handles the memory management; provides some bounds checking, assignment semantics, and comparisons; and supports manipulations such as concatenation, substring extraction, and substring or character replacement.

The Standard Library also provides a string_view class, defined in <string_view>. It is a read-only view of all kind of string representations, and can be used as a drop-in replacement for const string&, but without the overhead. It never copies strings!

C++ provides support for Unicode and localization. These features allow you to write programs that work with different languages, for example, Chinese. Locales, defined in <locale>, allow you to format data such as numbers and dates according to the rules of a certain country or region.

In case you missed it, Chapter 2 provides all the details of the string and string_view classes, while Chapter 19 discusses Unicode and localization.

Regular Expressions

Regular expressions are available through the <regex> header file. They make it easy to perform so-called pattern-matching, often used in text processing. Pattern-matching allows you to search special patterns in strings and optionally to replace them with a new pattern. Regular expressions are discussed in Chapter 19.

I/O Streams

C++ includes a model for input and output called streams. The C++ library provides routines for reading and writing built-in types from and to files, console/keyboard, and strings. C++ also provides the facilities for coding your own routines for reading and writing your own objects. The I/O functionality is defined in several header files: <fstream>, <iomanip>, <ios>, <iosfwd>, <iostream>, <istream>, <ostream>, <sstream>, <streambuf>, and <strstream>. Chapter 1 reviews the basics of I/O streams, and Chapter 13 discusses streams in detail.

Smart Pointers

One of the problems faced in robust programming is knowing when to delete an object. There are several failures that can happen. A first problem is not deleting the object at all (failing to free the storage). These are known as memory leaks, where objects accumulate and take up space but are not used. Another problem is where a piece of code deletes the storage while another piece of code is still pointing to that storage, resulting in pointers to storage that either is no longer in use or has been reallocated for another purpose. These are known as dangling pointers. One more problem is when one piece of code frees the storage, and another piece of code attempts to free the same storage. This is known as double-freeing. All of these problems tend to result in program failures of some sort. Some failures are readily detected; others cause the program to produce erroneous results. Most of these errors are difficult to discover and repair.

C++ addresses these problems with smart pointers: unique_ptr, shared_ptr, and weak_ptr. shared_ptr and weak_ptr are thread-safe. They are all defined in the <memory> header. These smart pointers are introduced in Chapter 1 and discussed in more detail in Chapter 7.

Before C++11, the functionality of unique_ptr was handled by a type called auto_ptr, which has been removed from C++17 and should not be used anymore. There was no equivalent to shared_ptr in the earlier Standard Library, although many third-party libraries (for example, Boost) did provide this capability.

Exceptions

The C++ language supports exceptions, which allow functions or methods to pass errors of various types up to calling functions or methods. The C++ Standard Library provides a class hierarchy of exceptions that you can use in your code as is, or that you can derive from to create your own exception types. Exception support is defined in a couple of header files: <exception>, <stdexcept>, and <system_error>. Chapter 14 covers the details of exceptions and the standard exception classes.

Mathematical Utilities

The C++ Standard Library provides a collection of mathematical utility classes and functions.

A whole range of common mathematical functions is available, such as abs(), remainder(), fma(), exp(), log(), pow(), sqrt(), sin(), atan2(), sinh(), erf(), tgamma(), ceil(), floor(), and more. C++17 adds a number of special mathematical functions to work with Legendre polynomials, beta functions, elliptic integrals, Bessel functions, cylindrical Neumann functions, and so on.

There is a complex number class called complex, defined in <complex>, which provides an abstraction for working with numbers that contain both real and imaginary components.

The compile-time rational arithmetic library provides a ratio class template, defined in the <ratio> header file. This ratio class template can exactly represent any finite rational number defined by a numerator and denominator. This library is discussed in Chapter 20.

The Standard Library also contains a class called valarray, defined in <valarray>, which is similar to the vector class but is more optimized for high-performance numerical applications. The library provides several related classes to represent the concept of vector slices. From these building blocks, it is possible to build classes to perform matrix mathematics. There is no built-in matrix class; however, there are third-party libraries like Boost that include matrix support. The valarray class is not further discussed in this book.

C++ also provides a standard way to obtain information about numeric limits, such as the maximum possible value for an integer on the current platform. In C, you could access #defines, such as INT_MAX. While those are still available in C++, it’s recommended to use the numeric_limits class template defined in the <limits> header file. Its use is straightforward, as shown in the following code:

cout << "int:" << endl;
cout << "Max int value: " << numeric_limits<int>::max() << endl;
cout << "Min int value: " << numeric_limits<int>::min() << endl;
cout << "Lowest int value: " << numeric_limits<int>::lowest() << endl;

cout << endl << "double:" << endl;
cout << "Max double value: " << numeric_limits<double>::max() << endl;
cout << "Min double value: " << numeric_limits<double>::min() << endl;
cout << "Lowest double value: " << numeric_limits<double>::lowest() << endl;

The output of this code snippet on my system is as follows:

int:
Max int value: 2147483647
Min int value: -2147483648
Lowest int value: -2147483648

double:
Max double value: 1.79769e+308
Min double value: 2.22507e-308
Lowest double value: -1.79769e+308

Note the differences between min() and lowest(). For an integer, the minimum value equals the lowest value. However, for floating-point types, the minimum value is the smallest positive value that can be represented, while the lowest value is the most negative value representable, which equals -max().

Time Utilities

C++ includes the chrono library, defined in the <chrono> header file. This library makes it easy to work with time; for example, to time certain durations, or to perform actions based on timing. The chrono library is discussed in detail in Chapter 20. Other time and date utilities are provided in the <ctime> header.

Random Numbers

C++ already has support for generating pseudo-random numbers for a long time with the srand() and rand() functions. However, those functions provide only very basic random numbers. For example, you cannot change the distribution of the generated random numbers.

Since C++11, a random number library has been added to the standard, which is much more powerful. The new library is defined in <random>, and comes with random number engines, random number engine adaptors, and random number distributions. All of these can be used to give you random numbers more suited to your problem domain, such as normal distributions, negative exponential distributions, and so on.

Consult Chapter 20 for details on this library.

Initializer Lists

Initializer lists are defined in the <initializer_list> header file. They make it easy to write functions that can accept a variable number of arguments and are discussed in Chapter 1.

Pair and Tuple

The <utility> header defines the pair template, which can store two elements with two different types. This is known as storing heterogeneous elements. All Standard Library containers discussed further in this chapter store homogeneous elements, meaning that all the elements in the container must have the same type. A pair allows you to store exactly two elements of completely unrelated types in one object. The pair class template is discussed in more detail in Chapter 17.

tuple, defined in <tuple>, is a generalization of pair. It is a sequence with a fixed size that can have heterogeneous elements. The number and type of elements for a tuple instantiation is fixed at compile time. Tuples are discussed in Chapter 20.

optional, variant, and any

C++17 introduces the following new classes:

• optional, defined in <optional>, holds a value of a specific type, or nothing. It can be used for parameters or return types of a function if you want to allow for values to be optional.
• variant, defined in <variant>, can hold a single value of one of a given set of types, or nothing.
• any, defined in <any>, is a class that can contain a single value of any type.

These three types are discussed in Chapter 20.

Function Objects

A class that implements a function call operator is called a function object. Function objects can, for example, be used as predicates for certain Standard Library algorithms. The <functional> header file defines a number of predefined function objects and supports creating new function objects based on existing ones.

Function objects are discussed in detail in Chapter 18 together with the Standard Library algorithms.

Filesystem

C++17 introduces a filesystem support library. Everything is defined in the <filesystem> header, and lives in the std::filesystem namespace. It allows you to write portable code to work with a filesystem. You can use it for querying whether something is a directory or a file, iterating over the contents of a directory, manipulating paths, and retrieving information about files such as their size, extension, creation time, and so on. This filesystem support library is discussed in Chapter 20.

Multithreading

All major CPU vendors are selling processors with multiple cores. They are being used for everything from servers to consumer computers and even smartphones. If you want your software to take advantage of all these cores, then you need to write multithreaded code. The Standard Library provides a couple of basic building blocks for writing such code. Individual threads can be created using the thread class from the <thread> header.

In multithreaded code you need to take care that several threads are not reading and writing to the same piece of data at the same time. To prevent this, you can use atomics, defined in <atomic>, which give you thread-safe atomic access to a piece of data. Other thread synchronization mechanisms are provided by <condition_variable> and <mutex>.

If you just need to calculate something, possibly on a different thread, and get the result back with proper exception handling, you can use async and future. These are defined in the <future> header, and are easier to use than directly using the thread class.

Writing multithreaded code is discussed in detail in Chapter 23.

Type Traits

Type traits are defined in the <type_traits> header file and provide information about types at compile time. They are useful when writing advanced templates and are discussed in Chapter 22.

Standard Integer Types

The <cstdint> header file defines a number of standard integer types such as int8_t, int64_t and so on. It also includes macros specifying minimum and maximum values of those types. These integer types are discussed in the context of writing cross-platform code in Chapter 30.

Containers

The Standard Library provides implementations of commonly used data structures such as linked lists and queues. When you use C++, you should not need to write such data structures again. The data structures are implemented using a concept called containers, which store information called elements, in a way that implements the data structure (linked list, queue, and so on) appropriately. Different data structures have different insertion, deletion, and access behavior and performance characteristics. It is important to be familiar with the available data structures so that you can choose the most appropriate one for any given task.

All the containers in the Standard Library are class templates, so you can use them to store any type, from built-in types such as int and double to your own classes. Each container instance stores objects of only one type; that is, they are homogeneous collections. If you need non-fixed-sized heterogeneous collections, you can wrap each element in an std::any instance and store those any instances in a container. Alternatively, you can store std::variant instances in a container. A variant can be used if the number of different required types is limited and known at compile time. Both any and variant are introduced with C++17, and are discussed in Chapter 20. If you needed heterogeneous collections before C++17, you could create a class that had multiple derived classes, and each derived class could wrap an object of your required type.

Note that the C++ standard specifies the interface, but not the implementation, of each container and algorithm. Thus, different vendors are free to provide different implementations. However, the standard also specifies performance requirements as part of the interface, which the implementations must meet.

This section provides an overview of the various containers available in the Standard Library.

Algorithms

In addition to containers, the Standard Library provides implementations of many generic algorithms. An algorithm is a strategy for performing a particular task, such as sorting or searching. These algorithms are implemented as function templates, so they work on most of the different container types. Note that the algorithms are not generally part of the containers. The Standard Library takes the approach of separating the data (containers) from the functionality (algorithms). Although this approach seems counter to the spirit of object-oriented programming, it is necessary in order to support generic programming in the Standard Library. The guiding principle of orthogonality maintains that algorithms and containers are independent, with (almost) any algorithm working with (almost) any container.

Note that the generic algorithms do not work directly on the containers. They use an intermediary called an iterator. Each container in the Standard Library provides an iterator that supports traversing the elements in the container in a sequence. The different iterators for the various containers adhere to standard interfaces, so algorithms can perform their work by using iterators without worrying about the underlying container implementation. The <iterator> header defines the following helper functions that return specific iterators for containers.

This section gives an overview of what kinds of algorithms are available in the Standard Library without going into detail. Chapter 17 goes deeper into iterators, and Chapter 18 discusses a selection of algorithms with coding examples. For the exact prototypes of all the available algorithms, consult a Standard Library Reference.

There are approximately 100 algorithms in the Standard Library, depending on how you count them. The following sections divide these algorithms into different categories. The algorithms are defined in the <algorithm> header file unless otherwise noted. Note that whenever the following algorithms are specified as working on a “sequence” of elements, that sequence is presented to the algorithm via iterators.

Modifying Sequence Algorithms

The modifying algorithms modify some or all of the elements in a sequence. Some of them modify elements in place, so that the original sequence changes. Others copy the results to a different sequence, so that the original sequence remains unchanged. All of them have a linear worst-case complexity. The following table summarizes the modifying algorithms.

ALGORITHM NAME	ALGORITHM SYNOPSIS
copy() copy_backward()	Copies elements from one sequence to another.
copy_if()	Copies elements for which a predicate returns true from one sequence to another.
copy_n()	Copies n elements from one sequence to another.
fill()	Sets all elements in the sequence to a new value.
fill_n()	Sets the first n elements in the sequence to a new value.
generate()	Calls a specified function to generate a new value for each element in the sequence.
generate_n()	Calls a specified function to generate a new value for the first n elements in the sequence.
move() move_backward()	Moves elements from one sequence to another. This uses efficient move semantics (see Chapter 9).
remove() remove_if() remove_copy() remove_copy_if()	Removes elements that match a given value or that cause a predicate to return true, either in place or by copying the results to a different sequence.
replace() replace_if() replace_copy() replace_copy_if()	Replaces all elements matching a value or that cause a predicate to return true with a new element, either in place or by copying the results to a different sequence.
reverse() reverse_copy()	Reverses the order of the elements in the sequence, either in place or by copying the results to a different sequence.
rotate() rotate_copy()	Swaps the first and second “halves” of the sequence, either in place or by copying the results to a different sequence. The two subsequences to be swapped need not be equal in size.
sample()	Selects n random elements from the sequence.
shuffle() random_shuffle()	Shuffles the sequence by randomly reordering the elements. It is possible to specify the properties of the random number generator used for shuffling. random_shuffle() is deprecated since C++14, and is removed from C++17.
transform()	Calls a unary function on each element of a sequence or a binary function on parallel elements of two sequences. This is an in-place transformation.
unique() unique_copy()	Removes consecutive duplicates from the sequence, either in place or by copying results to a different sequence.

Operational Algorithms

Operational algorithms execute a function on individual elements of a sequence. There are two operational algorithms provided. Both have a linear complexity and do not require the source sequence to be ordered.

ALGORITHM NAME	ALGORITHM SYNOPSIS
for_each()	Executes a function on each element in the sequence. The sequence is specified with a begin and end iterator.
for_each_n()	Similar to for_each() but only processes the first n elements in the sequence. The sequence is specified by a begin iterator and a number of elements (n).

Swap and Exchange Algorithms

The C++ Standard Library provides the following swap and exchange algorithms.

ALGORITHM NAME	ALGORITHM SYNOPSIS
iter_swap() swap_ranges()	Swaps two elements or sequences of elements.
swap()	Swaps two values, defined in the <utility> header.
exchange()	Replaces a given value with a new value and returns the old value. Defined in the <utility> header.

Minimum/Maximum Algorithms

ALGORITHM NAME	ALGORITHM SYNOPSIS
clamp()	Makes sure a value (v) is between a given minimum (lo) and maximum (hi). Returns a reference to lo if v < lo; returns a reference to hi if v > hi; otherwise returns a reference to v.
min() max()	Returns the minimum or maximum of two or more values.
minmax()	Returns the minimum and maximum of two or more values as a pair.
min_element() max_element()	Returns the minimum or maximum element in a sequence.
minmax_element()	Returns the minimum and maximum element in a sequence as a pair.

Numerical Processing Algorithms

The <numeric> header provides the following numerical processing algorithms. None of them require the source sequences to be ordered. All of them have a linear complexity.

ALGORITHM NAME	ALGORITHM SYNOPSIS
iota()	Fills a sequence with successively incrementing values starting with a given value.
gcd()	Returns the greatest common divisor of two integer types.
lcm()	Returns the least common multiple of two integer types.
adjacent_difference()	Generates a new sequence in which each element is the difference (or other binary operation) of the second and first of each adjacent pair of elements in the source sequence.
partial_sum()	Generates a new sequence in which each element is the sum (or other binary operation) of an element and all its preceding elements in the source sequence.
exclusive_scan() inclusive_scan()	These are similar to partial_sum(). An inclusive scan is identical to a partial sum if the given summation operation is associative. However, inclusive_scan() sums in a non-deterministic order, while partial_sum() left to right, so for non-associative summation operations the result of the former is non-deterministic. The exclusive_scan() algorithm also sums in a non-deterministic order. For inclusive_scan(), the ith element is included in the ith sum, just as for partial_sum(). For exclusive_scan(), the ith element is not included in the ith sum.
transform_exclusive_scan() transform_inclusive_scan()	Applies a transformation to each element in a sequence, then performs an exclusive/inclusive scan.
accumulate()	“Accumulates” the values of all the elements in a sequence. The default behavior is to sum the elements, but the caller can supply a different binary function instead.
inner_product()	Similar to accumulate(), but works on two sequences. This algorithm calls a binary function (multiplication by default) on parallel elements in the sequences, accumulating the result using another binary function (addition by default). If the sequences represent mathematical vectors, the algorithm calculates the dot product of the vectors.
reduce()	Similar to accumulate(), but supports parallel execution. The order of evaluation for reduce() is non-deterministic, while it’s from left to right for accumulate(). This means that the behavior of the former is non-deterministic if the given binary operation is not associative or not commutative.
transform_reduce()	Applies a transformation to each element in a sequence, then performs a reduce().

What’s Missing from the Standard Library

The Standard Library is powerful, but it’s not perfect. Here are two examples of missing functionality:

• The Standard Library does not guarantee any thread safety for accessing containers simultaneously from multiple threads.
• The Standard Library does not provide any generic tree or graph structures. Although maps and sets are generally implemented as balanced binary trees, the Standard Library does not expose this implementation in the interface. If you need a tree or graph structure for something like writing a parser, you need to implement your own or find an implementation in another library.

It is important to keep in mind that the Standard Library is extensible. You can write your own containers or algorithms that work with existing algorithms or containers. So, if the Standard Library doesn’t provide exactly what you need, consider writing your desired code such that it works with the Standard Library. Chapter 21 covers the topic of customizing and extending the Standard Library.