A Tour of C++ (Second Edition)

Book Details

Full Title: A Tour of C++ (Second Edition)
Author: Bjarne Stroustrup
ISBN/URL: 978-0-13-499783-4
Reading Period: 2021.06–2021.06.28
Source: Recommended by the man himself in one of his talks about modern C++

General Review

One particular good point of the book is how it is able to be short, but yet useful (IMHO) to a person who first wrote C++ in a DOS environment (was it Borland?) over fifteen years ago and haven't seriously revisited it since (i.e., me).
Provides a broad and (somewhat) deep coverage of select areas of C++ that Bjarne thinks is relevant for someone new to C++. The topics are arranged in a coherent manner where later chapters build on earlier chapters.
- Coverage is also general complete with respect to the topic addressed. For example, Bjarne will introduce the union language feature, then also mention that the standard library's variant is usually a better choice. This provides the historical context and best practice.
Also slightly opinionated (but it's good, since the opinion is from Bjarne, who has worked with C++ for a long time, and is presumably influential in deciding the direction that C++ will develop).
- For example, there seems to be a preference to use initialize list when declaring and initializing variables. Also, Bjarne is rather optimistic of the benefits of concepts in C++20.
At the end of each chapter is a bullet list of advice, without elaboration, but with references to the C++ Core Guidelines. This would be useful to look through if any advice seems weird, we can then consult the reference provided.
- The advice provided will relate to the same general topic covered in the chapter, but may not have otherwise been touched on at all in the chapter.

Specific Takeaways

Chapter 1 - The Basics

Types, Variables, and Arithmetic

The char type is of the natural size to hold a character on a given machine.
The single quote character can be used as digit separator: e.g., 3.14159'26535'89793

Initialization

Besides the usual = operator, variables can also be initialized using initializer lists:

  double d1 = 2.3;
  double d2 {2.3};
  double d3 = {2.3};
  complex<double> z = 1;
  complex<double> z2 {d1, d2};
  complex<double> z3 = {d1, d2};

  vector<int> v {1, 2, 3, 4, 5, 6};

If in doubt, use the {...} form, as it avoids conversions that lose information:
```
  int i1 = 7.8;  // i1 becomes 7
  int i2 {7.8};  // error
```
auto can be use to avoid stating the variable's type explicitly.

Scope and Lifetime

A declaration introduces its name into one of four scopes:
- Local scope: e.g., within a function, between the enclosing curly braces
- Class scope: i.e., within the curly braces of the class definition, but outside any function etc. Such a variable is called a class member.
- Namespace scope
- Global scope

Constants

C++ supports two notions of immutability:
- const: which roughly means "I promise not to change this value"
  - Primarily used to specify interfaces so that data can be passed using pointers and references without fear if it being modified.
- constexpr: which roughly means "to be evaluated at compile time"
  - Primarily used to specify constants, to allow placement of data in read-only memory (where) it is unlikely to be corrupted, and for performance.
  - Functions can be annotated with constexpr so that they may be used to derive other constexpr.

Pointers, Arrays and References

When we don't want to modify an argument but still don't want the cost of copying, we use a const reference; for example:
```
  double sum(const vector<double>&)
```

Chapter 2 - User-Defined Types

Introduction

C++'s abstraction mechanisms are primarily designed to let programmers design and implement their own types, with suitable representations and operations, and for programmers to simply and elegantly use such types.

Structures

struct is used to organize the elements of a type into a data structure

Classes

Classes are used to separate the interface of a type from the implementation of the type.
The basic technique for handling varying amount of information in C++ is to have a fixed-size handle referring to a variable amount of data elsewhere (e.g., on the free store allocated by new).

A member initializer list can be used to initialize a variable in the constructor, for example:

  class Vector {
  public:
    Vector(int s) :elem{new double[s]}, sz{s} {} // using member initializer list
  private:
    double *elem; // pointer to the elements
    int sz;       // the number of elements
  }

There is no fundamental difference between a struct and a class; a struct is simply a class with members public by default.
- For example, we can define constructors and other member functions for a struct.

Unions

A union is a struct in which all members are allocated at the same address so that the union occupies only as much space as its largest member.
- The language doesn't keep track of what kind of value is held by a union.
- As such, it is common to use tagged unions where the union is encapsulated on accessible only through member functions.

The standard library provides the variant type to eliminate most direct uses of unions. For example:

  struct Entry {
    string name;
    variant<Node*, int> v;
  };

  void f(Entry* pe) {
    if (holds_alternative<int>(pe->v)) // testing which variant is held in pe
      cout << get<int>(pe->v);
    // ...
  }

Enumerations

Enumerations, being a user-defined type, can have their operators overloaded (e.g., the + operator), allowing for more natural usage where applicable.

Chapter 3 - Modularity

Introduction

A C++ program consists of many separately developed parts, such as:
- functions,
- user-defined types,
- class hierarchies, and
- templates.
It is important to clearly define the interaction among these parts.
At the language level, C++ represents interfaces by declaration.
- The definition may be elsewhere, be it the actual data representation, or implementation of functions.

Separate Compilation

C++ supports a notion of separate compilation where user code sees only declarations of the types and functions used.
- The definitions of those types and functions are in separate source file and are compiled separately.
A .cpp file that is compiled by itself is called a translation unit.

Modules

C++20 will support modules that will avoid the problem where each #include directive results in the verbatim insertion of another source file, and each time the other source file is included, it'll be processed again during compilation.

Namespaces

In addition to functions, classes, and enumeration, C++ offers namespaces as a mechanism for expressing that some declaration belong together and that their names shouldn't clash with other names.

Error Handling

Exceptions in C++ is not meant as an alternate mechanism for returning values; instead, exceptions are designed to be used to report failure to complete a given task.
Exceptions are also integrated with constructors and destructors.
Compilers are optimized to make returning a value much cheaper than throwing the same value as an exception.
A function can indicate that it cannot perform its allotted task by:
1. throwing an exception
2. somehow returning a value indicating failure
3. terminating the program
We throw an exception when:
- An error is so rare that a programmer is likely to forget to check for it (e.g., printf()).
- An error cannot be handled by an immediate caller, and has to percolate back to an ultimate caller. For example, it is infeasible to have every function reliably handle every allocation failure or network outage.
- ? New kinds of errors can be added in lower parts of the application, and these new errors will not be handled by existing code in higher levels.
- No suitable return path for error codes are available (e.g., a constructor).
- The return path is made more complicated or expensive by a need to pass both a value and an error indicator back.
- The function that found the error was a callback, so the immediate caller may not even know what function was called.
- ? An error implies that some "undo action" is needed.
We return an error indicator when:
- A failure is normal and expected (e.g., file opening).
- An immediate caller can reasonably be expected to handle the failure.
We terminate when:
- We can't possibly recover from the error (e.g., memory exhaustion).
- The system is one where the error-handling is based on restarting a thread, process, or computer.
Adding a noexcept to a function will result in any throw within the function to turn into a terminate().

Function Arguments and Return Values

The primary and recommended way of passing information from one part of a program to another is through a function call, via function arguments and return values.
Other mechanisms include:
- Global variables
- Pointer and reference parameters
- Shared state in a class object
Key concerns when passing information to and from functions include:
- Is an object copied or shared?
- If share, is it mutable?
- Is an object moved, leaving an "empty object" behind?
The default behavior is copying, but can implicitly be optimized to moves.
Small values are typically passed by values while larger ones are passed by reference. "Small" means "something that's really cheap to copy", and a good rule of thumb is "the size of two or three pointers or smaller".
To return values from functions without copying, we can implement the move constructor.
- The traditional way is to manually allocate memory in the function, and return a pointer.

Structured Binding

A function can return only a single value, but that value can be a class object with many members.

Basic example of returning multiple values, and destructuring:

  struct Entry {
    string name;
    int value;
  };

  Entry read_entry(istream& is) { // naive implementation
    string s;
    int i;
    is >> s >> i;
    return {s, i};
  }

  auto e = read_entry(cin); // alternatively, auto [n, v] = read_entry(cin);

  cout << "{" << e.name  << " ," << e.value << "}\n";

Example of destructuring with const / reference:

  map <string, int> m;
  // populate m...
  for (const auto [k, v] : m)
    cout << "{ " << k << ", " << v << " }\n";

  // OR

  void incr(map<string, int>& m) {
    for (auto& [k, v] : m)
      ++v;
  }

There will not be any difference in the object code quality when using structure binding as compared to explicitly using a composite object.

Chapter 4 - Classes

Introduction

The central language feature of C++ is the class.
The three important kinds of classes (among others) are:
1. Concrete classes
2. Abstract classes
3. Classes in class hierarchies

Concrete Types

The defining characteristic of a concrete type is that its representation is part of its definition, allowing implementation to be optimally efficient in time and space.
In particular, it allows us to:
- place objects of concrete types on the stack, in statically allocated memory, and in other objects
- refer to object directly (and not just through pointers and references)
- initialize objects immediately and completely
- copy and move object
If the representation change in any significant way, a user must recompile.
By defining a default constructor we can eliminate the possibility of uninitialized variables of that type.
Functions defined in a class are inlined by default.
The const keyword at the end of a member function indicates that the function will not modify the class instance.
- A const member function can be invoked for both const and non-const objects, but a non-const member function can only be invoked for non-const objects.

A constructor that supports initializer list can be declared and defined as follows:

  class Vector {
  public:
    Vector(std::initializer_list<double> lst) // initialize with a list of doubles
      :elem{new double[lst.size()]}, sz{static_cast<int>(lst.size())}
    // ...
    void push_back(double);
    // ...
  };

  // static_cast is required above because the standard library uses unsigned
  // integers for sizes and subscripts

When we use a {...} initializer list, the compiler will create an object of type initializer_list to give to the program.

static_cast does not check the value it is converting, and it is the programmer's responsibility to ensure so (or check).
- Other casts include: reinterpret_cast for treating an object as simply a sequence of bytes; and const_cast for "casting away const".
- Judicious use of the type system and well-designed libraries allow us to eliminate unchecked casts in higher-level software.

Abstract Types

An abstract type is a type that completely insulates a user from implementation details.
The virtual keyword can be interpreted to mean "may be redefined later in a class derived from this one".
- The =0 syntax means a function is pure virtual: that is, a derived class must define the function.
A class with a pure virtual function is called an abstract class.

Virtual Functions

The virtual call mechanism can be made almost as efficient as the "normal function call" mechanism (within 25%). The space overhead is one pointer in each object of a class with virtual functions plus one virtual table for each such class.

Class Hierarchies

A class hierarchy is a set of classes ordered in a lattice created by derivation.
We used class hierarchies to represent concepts that have hierarchical relationships.
A virtual destructor is essential for an abstract class because an object of a derived class is usually manipulated through the interface provided by its abstract base class.
dynamic_cast can be used to convert a pointer to a base class to a pointer to a derived class at runtime, allowing us to use member functions on the derived class.
- If the object pointer to is not of the correct type, nullptr will be returned.
- We can use dynamic_cast to cast to a reference type to make it throw bad_cast exception if the object is not of the expected type.
unique_ptr can sometimes be used in place of a naked pointer to avoid memory leak.
- The compiler will implicitly generate a destructor (for the class containing the unique_ptr) that does the destruction of unique_ptr.
- The code using unique_ptr will be as efficient as code using the raw pointers correctly.

Chapter 5 - Essential Operations

Introduction

Constructors, destructors, and copy and move operations for a type are logically related, and should be defined as a matched set. Otherwise, we will likely suffer logical or performance problems.

If a class X has a destructor that performs a non-trivial task, such as free-store deallocation or lock release, the class is likely to need the full complement of functions:

  class X {
  public:
    X(Sometype); // "ordinary constructor": create an object
    X();         // default constructor
    X(const X&); // copy constructor
    X(X&&);      // move constructor
    X& operator=(const X&); // copy assignment: clean up target and copy
    X& operator=(X&&);      // move assignment: clean up target and move
    ~X();        // destructor: clean up
    // ...
  };

There are five situations in which an object can be copied or moved:
- As the source of an assignment
- As an object initializer
- As a function argument
- As a function return value
- As an exception
As regard the preceding list, assignment uses a copy or move assignment operator; in principle, the other cases use a copy or move constructor, but the constructor invocation is often optimized away (by constructing the object used to initialize right in the target object).
As regard the code sample above, besides the "ordinary constructor", the other can be implicitly generated by the compiler.
- However, we can be explicit about using the default implementation by using something like Y(const Y&) = default;.
- Once we are explicit about one or more defaults, the others will not be generated.
When a class has a pointer member, it is usually a good idea to be explicit about copy and move operations because the default implementation will copy only the pointer, and would usually be wrong.
A good rule of thumb (sometimes called the "rule of zero") is to either define all of the essential operations or none.
Using =delete can suppress the generation of default implementation. This is generally useful is abstract base classes to prevent memberwise copy.
- The =delete syntax can be used to suppress any other functions too.
Conversions
- A constructor taking a single argument defines a conversion from its argument type. For example, the class below defines a conversion from double:
```
  class complex {
    double re, im;
  public:
    complex(double r, double i) :re{r}, im{i} {}
    complex(double r): re{r}, im{0} {}
    complex() :re{0}, im{0} {}

    // ...
  };
```
- The above class would allow initializing variables of complex type using implicit conversion from double as follows:
```
  complex z1 = 3.14;
```
- However, sometimes such implicit conversion might be misleading; to prevent such implicit conversion, we can write our constructor using the explicit keyword as follows:
```
  class Vector {
  public:
    explicit Vector(int s);
    // ...
  };
```
- Variables of the above Vector class can be initialized using Vector v1(7) but not Vector v2 = 7, making it clearer that 7 refers to the size, and not the single element.

Copy and Move

By default, objects can be copied, and the default meaning of copy is memberwise copy.
When a class is a resource handle, the default memberwise copy is usually not what we want.
- For example, when do use memberwise copy on a vector class defined using a pointer member pointing to the actually data, we only copy the pointer, but not the data. Consequently, modifications via the "copied" instance will affect the original.
To avoid the default memberwise copy, we need to define two member functions on the class: a copy constructor and a copy assignment.
- That is, MyClass(const MyClass& mc) and MyClass& operator=(const MyClass& mc) respectively.
When we want to avoid the cost of copying—such as when returning a large object created in a function—we can define the move constructor and move assignment on the type.
- That is, MyClass(MyClass&& mc) and MyClass& operator=(MyClass&& mc) respectively.
- We can use y = std::move(x) to move x into y.
The && means "rvalue reference", and is a reference to which we can bind an rvalue.
- The word "rvalue" is intended to complement "lvalue", which roughly means "something that can appear on the left-hand side of an assignment". So rvalue is a value that we cannot assign to, making it safe to "steal" (AKA move).
After a move, a moved-from object should be in a state that allows a destructor to be run. Although typically, we also allow assignment to a moved-from object.
The compiler eliminate most copies associated with initialization, so move constructors are not invoked as often as we might imagine. However, it is typically not possible to implicitly copy or move operations from assignments, so move assignments can be critical for performance.

Resource Management

By defining constructors, copy operations, move operations, and a destructor, a programmer can provide complete control of the lifetime of a contained resource.
Resource handles, such as Vector and thread are superior alternatives to direct use of built-in pointers in many cases.
- Much is the same way new and delete disappear from application code, we can make pointers disappear into resource handles.
- For example, vector holds memory, thread holds system threads, and fstream holds file handles.
Before resorting to garbage collection, systematically use resource handles: let each resource have an owner in some scope and by default be released at the end of its owners scope.
- When required, resources can be moved using move semantics or "smart pointers", and shared ownership can be represented by "shared pointers".

Conventional Operations

When defining a new type, consider implementing the conventional set of operations for ease of use. Such operations include:
- Comparisons: ==, !=, <, <=, >, and >=
- Container operations: size(), begin(), and end()
- Input and output operations: >> and <<
- User-defined literals
- swap()
- Hash functions: hash<>

Chapter 6 - Templates

Introduction

A template is a class or a function that we parameterize with a set of types or values. We use templates to represent ideas that are best understood as something general from which we can generate specific types and functions by specifying arguments.

Parameterized Types

Templates are a compile-time mechanism, and incurs no run-time overhead compared to hand-crafted code.
A template plus a set of template arguments is called an instantiation or a specialization.
C++ 20 supports concepts, where the type arguments must meet certain requirements, or it will be a compiler error (YJ: broadly similar to Java's <? extends SomeType> and <? super SomeType>).
In additional to type arguments, a template can take value arguments. For example:
```
  template<typename T, int N>
  struct Buffer {
    using value_type = T;
    constexpr int size() { return N; }
    T[N];
    // ...
  };
```
- The alias (value_type) and the constexpr function are provided to allow users (read-only) access to the template arguments.
- Templates with value arguments are useful in many contexts. For example, it allow us to create arbitrarily sized buffers with no use of the free store.
The compiler will try to deduce the type arguments for templated types, allowing us to avoid explicitly specifying the type arguments.
- For example, given the following template:
```
  template<typename T>
  class Vector {
  public:
    Vector(int);
    Vector(initializer_list<T>);
    // ...
  };
```
  we can initialize variables as follows:
```
  Vector v1 {1, 2, 3} // deduce using the element type from initializer list
  Vector v2 = v1;     // deduce using v1's element type
```
- The type of a C-style string literal is const char*, if that is not the intended type, use the s suffix to make it a proper string.
- When a template argument cannot be deduced from the constructor arguments, we can help by providing a deduction guide in the function template for the particular constructor.

Parameterized Operations

There are three ways of expressing an operation parameterized by types or values:
1. Function template
2. Function object (AKA functor)
3. Lambda expression

A function object might look something like the following:

  template(typename T)
  class Less_than {
    const T val;
  public:
    Less_than(const T& v) :val{v} {}
    bool operator()(const T& x) const { return x<val; }
  };

Lambda expression is a way to implicitly generate function object, and looks something like the following:
```
  [&](int a){ return a<x; }
```
- The [&] specifies a capture list specifying that all local names used in the lambda body will be accessed through references. We could have captured only x with [&x]. Capturing all by value is [=].
- Using lambda, we can turn any statement into an expression (YJ: allowing us to assign the result of the expression). In the example below, a lambda is used to "assign" the result of a switch case statement to v (much like how the if form is an expression in Rust, and can be directly assigned):
```
  vector<int> v = [&] {
    switch (m) { // m might be an enum specifying type an initialization mode
    case zero:
      return vector<int>(n); // n elements initialized to 0
    case seq:
      return vector<int>{p, q}; // copy from sequence [p:q)
    case cpy:
      return arg;
    }
   }();
```

Template Mechanisms

To define good templates, we need some good supporting language facilities:
- Values dependent on a type: variable templates
- Aliases for types and templates: alias templates
- A compile-time selection mechanism: if constexpr
- A compile-time mechanism to inquire about properties of types and expressions: require expressions
Variable templates are simply variables typed using the template's type argument.

Aliases

Every standard library container type provides the value_type alias as the name of its element's type. This allows us to use T::value_type to refer to the type of the elements contained within another template.

Alias can also be used to partially bind the template arguments. For example:

  template<typename Key, typename Value>
  class Map {
    // ...
  }; // templated class with two template arguments

  template<typename Value>
  using String_map = Map<string, Value>; // binding the second template argument

  String_map<int> m; // "binding" the remaining template argument

Compile-Time if
- Compile-time if can be used to choose between alternative implementation based on the actual template argument provided. For example, the is_pod function can be used to check whether a type is plain-old data, and uses different implementation whether the template:
```
  template<typename T>
  void update(T& target) {
    // ...
    if constexpr(is_pod<T>::value)
      implementation_one(target);
    else
      implementation_two(target);
    // ...
  }
```

Chapter 7 - Concepts and Generic Program

YJ Note: Concepts has not yet reached C++20 when the book is published, and the syntax might have changed since.

Introduction

Recall that templates offers the following benefits:
- The ability to pass types (as well as values and templates) as arguments without loss of information. This creates excellent inlining opportunities.
- Opportunities to weave together information from different contexts at instantiation time. This creates optimization opportunities.
- The ability to pass constant values as arguments. This allows compile-time computation.
In gist, templates provide a powerful mechanism for compile-time computation and type manipulation that can lead to very compact and efficient code.
Templates provide (compile-time) parametric polymorphism.

Concepts

A concept is a compile-time predicate specifying how one or more types can be used. The value of a concept is always bool.
Concepts are requirements we place on template arguments. In the example below, instead of using typename, we use Sequence and Number to place additional requirements on the template arguments; additionally, we use the Arithmetic concept to ensure that we can perform arithmetic operations on the element type of Seq with Num:
```
  template<Sequence Seq, Number Num>
      requires Arithmetic<Value_type<Seq>, Num>
  Num sum(Seq s, num n);
```
With concepts, it is also possible to have overloaded templates, much like overloaded functions. In our source code, we define multiple templates, with different concepts requirements. At compile time, when it comes to specialization of the template, the compiler will look at the actual type argument provided, and select the most appropriate template.
The requires expression can be used to place requirements on template arguments. In the example below, the template argument must support both indexing and addition operation:
```
  template<Forward_iterator Iter, int n>
    requires requires(Iter p, int i) { p[i]; p+i; } // the repeated "requires" is a typo
  void advance(Iter p, int n)
```
- The requires expression is a predicate that returns true if the statements within are valid code.
- Note however that we should generally used name concepts instead of requires expressions directly.

Generic Programming

Good, useful concepts are fundamental and are discovered more than they are designed.
A type is Regular (a concept) when in behaves much like an int or a vector:
- can be default constructed
- can be copied using a constructor or an assignment
- can be compared using == and !=
- doesn't suffer from technical problems from overly clever programming tricks.

Variadic Templates

C++ supports variadic templates. Additionally, fold expressions and forwarding arguments provides us more flexibility when working with templates.

Template Compilation Model

Chapter 8 - Library Overview

Introduction

The standard library provides a hosts of useful types like string, ostream, variant, vector, map, path, unique_ptr, thread, regex, and complex.

Standard-Library Components

The facilities provided by the standard library can be classified like this:
- Run-time language support (e.g., allocation and run-time type information)
- The C standard library
- Strings
- Regular expression matchings
- I/O streams
- A framework of containers (e.g., vector and map) and algorithms (e.g., find(), sort(), and merge()). Conventionally called the STL.
- Support for numerical computation
- Support for concurrent programming
- Parallel versions of most STL algorithms
- Utilities to support template metaprogramming, STL-style generic programming, general programming, and clock.
- Support for efficient and safe management of general resources, plus an interface to optional garbage collectors
- "Smart pointers" for resource management.
- Special-purpose containers, such as array, bitset, and tuple.
- Suffixes for popular units, such as ms for milliseconds and i for imaginary.

Some useful types and functions, together with the header files they declared:

header	types & functions
<algorithm>	copy(), find(), sort()
<array>	array
<chrono>	duration, time_point
<cmath>	sqrt(), pow()
<complex>	complex, sqrt(), pow()
<filesystem>	path
<forward_list>	forward_list
<fstream>	fstream, ifstream, ofstream
<future>	future, promise
<ios>	hex, dec, scientific, fixed, defaultfloat
<iostream>	istream, ostream, cin, cout
<map>	map, multimap
<memory>	unique_ptr, shared_ptr, allocator
<random>	default_random_engine, normal_distribution
<regex>	regex, smatch
<string>	string, basic_string
<set>	set, multiset
<sstream>	istringstream, ostringstream
<stdexcept>	length_error, out_of_range, runtime_error
<thread>	thread
<unordered_map>	unordered_map, unorder_multimap
<utility>	move(), swap(), pair
<variant>	variant
<vector>	vector

Chapter 9 - Strings and Regular Expressions

Modern implementation of string types typically have short-string optimization, where short string values are kept in the object itself (i.e., on the stack), and only longer strings are placed on the free store.

Chapter 10 - Input and Output

The C++ standard library also supports the C standard-library I/O, including printf() and scanf(), but many uses of this library are unsafe from a type and security point-of-view.

Chapter 11 - Containers

map in C++ is a balanced binary search tree (usually a red-black tree). Use unordered_map for a hash table.

Standard Container Summary

type	description
vector<T>	A variable-size vector
list<T>	A doubly-linked list
forward_list<T>	A singly-linked list
deque<T>	A double-ended queue
set<T>	A set (a `map` with just a key and no value)
multiset<T>	A set in which a value can occur many times
map<K,V>	An associative array
unordered_map<K,V>	A map using a hashed lookup
unordered_multimap<K,V>	A multimap using a hashed lookup
unordered_set<T>	A set using a hashed lookup
unordered_multiset<T>	A multiset using a hashed lookup

Chapter 12 - Algorithms

Algorithm Overview

Selected Standard Algorithms

algorithm	description
f=for_each(b,e,f)	For each element x in [b:e) do f(x)
p=find(b,e,x)	p is the first p in [b:e) so that *p==x
p=find_if(b,e,f)	p is the first p in [b:e) so that f(*p)
n=count(b,e,x)	n is the number of elements q in [b:e) so that q==x
n=count_if(b,e,f)	n is the number of elements q in [b:e) so that f(q)
replace(b,e,v,v2)	Replace elements q in [b:e) so that q==v with v2
replace_if(b,e,f,v2)	Replace elements q in [b:e) so that f(q) with v2
p=copy(b,e,out)	Copy [b:e) to [out:p)
p=copy_if(b,e,out,f)	Copy elements q from [b:e) so that f(q) to [out:p)
p=move(b,e,out)	Move [b:e) to [out:p)
p=unique_copy(b,e,out)	Copy [b:e) to [out:p); don't copy adjacent duplicates
sort(b,e)	Sort elements of [b:e) using < as the sorting criterion
sort(b,e,f)	Sort elements of [b:e) using f as the sorting criterion
(p1,p2)=equal_range(b,e,v)	[p1:p2) is the subsequence of sorted sequence [b:e) with the value v; basically a binary search for v
p=merge(b,e,b2,e2,out)	Merge two sorted sequences [b:e) and [b2:e2) into [out:p)
p=merge(b,e,b2,e2,out,f)	Merge two sorted sequences [b:e) and [b2:e2) into [out:p) using f as the comparison

Concepts

Concepts can largely be classified as follows:
- Core language concepts
- Comparison concepts
- Object concepts
- Callable concepts
- Iterator concepts
- Range concepts
Refer to this section (12.7) for helpful summary tables of the available concepts that I might actually need to use.
The concepts library from cppreference.com is also helpful.
- Along with the iterator library and ranges library.

Chapter 13 - Utilities

Introduction

Not all standard-library components come as part of obviously labeled facilities. This section contains examples of small, widely useful components. These are often called vocabulary types because they are part of the common vocabulary used to describe our designs and programs.

Resource Management

mutex and scoped_lock might be used as follows:

  mutex m;
  // ...
  void f() {
    scoped_lock<mutex> lck {m}; // acquire the mutex m, will block
    // ... manipulate shared data
  }

We use unique_ptr to represent unique ownership and shared_ptr to represent shared ownership. The make_unique() and make_shared() functions make it more convenient to create such smart pointers.
Use move() and forward() to achieve performance improvement where warranted.

Range Checking: `gsl::span`

The Guidelines Support Library (GSL) provides the helpful span type for referring to a range of elements, much like string_view.

Specialized Containers

"Almost Containers"

type description

Alternatives

The standard library offers three types to express alternatives:
- variant to represent one of a specified set of alternatives
- optional to represent a value of a specified type or no value
- any to represent one of an unbounded set of alternative types

Allocators

By default, standard library containers allocate space using new.
- The new and delete operators are very general, providing a general free store that can hold objects of arbitrary size and user-controlled lifetime.
- The above mentioned generality implies opportunities for optimization when such generality is not required.
- For example, by using synchronized_pool_resource in the pmr ("polymorphic memory resource") sub-namespace of std, we can avoid memory fragmentation from creating and destroying many instances of a particular objects is an tight or long-running loop.

Function Adaption

When we want to pass a function as function argument but the type of the function argument doesn't quite match, we can use the following alternatives:
- Lambda
- Use std::mem_fn() to make a function object from a member function
- Define the function to accept a std::function, which can hold any object that we can invoke using the call operator (()).

Type Functions

Type functions are functions evaluated at compile time that (a) accepts a type as its argument or (b) returns a type.
- For example, numeric_limits from <limits> provides information such as the smallest possible float.
iterator_traits allows us to write functions and templates that applies only for specific types of iterators (for example, iterators that supports random access). Also see iterator category on cppreference.com.
- The mechanism is called tag dispatch.
- Note however that many traits and traits-based techniques will be made redundant by concepts in C++20.
The ~<type_traits> standard library provides various type predicates that each answers a fundamental question about types (for example, does the type has virtual destructor), and are particularly useful when writing templates.
- Examples are is_class, is_pod, is_literal_type, has_virtual_destructor, and is_base_of.
The enable_if function can be used to conditionally define members during template specialization, depending on the actual template arguments.

Chapter 14 - Numerics

Numerical Algorithms

The <numeric> standard library contains helpful algorithms like accumulate(), inner_product(), partial_sum() adjacent_difference(), and also the parallel versions like reduce(), exclusive_scan(), etc.
- The parallel version also accept policies such as std::execution::par, std::execution::seq, std::execution::par_unseq, and std::execution::unseq.

Random Numbers

Random number generators in the <random> standard library consists of two parts:
1. An engine that produces a sequence of random or pseudo-random values
2. A distribution that maps those values into a mathematical distribution in a range

The random number API provided by the standard library might be cumbersome for simple usages. Instead we might define a helper class like this:

  class Rand_int {
  public:
    Rand_in(int low, int high) :dist{low,high} {}
    int operator()() { return dist(re); }
    void seed(int s) { re.seed(s); }
  private:
    default_random_engine re; // use the default engine from the standard library
    uniform_int_distribution<> dist; // use a uniform distribution as is commonly what is expected
  }

Vector Arithmetic

The standard library provides valarray that is similar to vector, but is less general and more amenable to optimization for numerical computation.

Chapter 15 - Concurrency

Introduction

The concurrency features provided by the standard library include thread, mutex, lock(), packaged_task, and futures.
These features are built directly upon what the operating systems offer and do not incur performance penalties compared to those.

Passing Arguments

The ref() function (from <functional>) is sometimes needed when passing arguments to another thread using the variadic thread() template constructor to let the constructor treat the arguments as references, instead of objects and passing by value.

Returning Results

Results can be "returned" from a different thread by passing a non-const reference to the thread in the first place.
Alternatively, we can pass the arguments by const reference, and also pass a location for the thread to store the result.

Sharing Data

scoped_lock can be used to acquire multiple locks simultaneously, and the calling thread will only proceed when locks are acquired on all the mutex arguments passed into the constructor, and will never block while holding a mutex.
shared_mutex, together with shared_lock and unique_lock, allows us to implement the "reader-writer lock" idiom where data is shared among many readers and a single writer.

Waiting for Events

condition_variable can be used for signalling between multiple threads on the occurrence of events.
The condition_variable should be pair with a mutex for synchronizing access to the condition_variable (as per normal concurrent programming).
- The mutex lock should be acquired using unique_lock (rather than scoped_lock) because the lock needs to be passed int the condition_variable::wait() function, and a scoped_lock cannot be copied.

Communicating Tasks

The standard library provides facilities for programmers to operate at the conceptual level of tasks rather than directly at the lower level of threads and locks:
- future and promise for returning a value from a task spawned on a separate thread.
  - Specifically, one thread sets the value or exception on the promise, and the value/exception will be available on the future in another thread.
- packaged_task to help launch tasks and connect up the mechanisms for returning a result.
  - The packaged_task is first constructed with the function to be executed. Next, we call packaged_task::get_future() to get references to future in the current thread. Following that, we create new thread, passing in the packaged_task and the required arguments for the function to be executed. Finally, we join the threads and get results from the future.
- async() for launching a task in a manner similar to calling a function.
  - Essentially, async() separates the calling for a function from the retrieval of results.
  - Note however that async() can't be used for tasks that share resources requiring locks.

Chapter 16 - History and Compatibility

C/C++ Compatibility

With minor exceptions, C++ is a superset of C.
The major problems for converting a C program to C++ are likely to be:
- Suboptimal design and programming style
- A void* implicitly to a T*
- C++ keywords, such as class and private, used as identifiers in C code
- Incompatible linkage of code fragments compiled as C and fragments compiled as C++
extern "C" can be used to make C++ functions callable from C code.

To Internalize Now

N.A.

To Learn/Do Soon

Check out various topics listed on the landing page of cppreference.com.
- Especially the C-related portion, since I wasted my time on the other C book recently.

To Revisit When Necessary

Section 4.2.1 An Arithmetic Type

Refer to the example complex class for illustration of various basic techniques for writing a concrete class, including:
- Default constructor
- const function
- Operator overloading

Section 4.2.2 A Container

Refer to the example vector class for basic destructor implementation.

Section 4.4 Virtual Functions

Refer to this section of details of virtual functions, like how function calls are resolved.

Section 5.4 Conventional Operations

Refer to this section of a list of functions that we should consider implementing on new classes we define, to provide a conventional usage experience.
- The section also contains brief guidelines where applicable.

Section 7.3 Generic Programming

Refer to this section for some general high-level comments and intuition on what makes good concepts.
The section also provides an example of how we might start with a sum() function definition, and abstract it into the accumulate() function in the standard library.

Chapters 9 through 15

These chapters provides an overview to a select portion of the standard library. Before starting on any substantial C++ project, I should at least revisit the section headings to be reminded of what is available to me.

Section 16.2.3.1 Style Problems

Refer to this section on how to convert a C program to C++, while reaping the benefits of C++.

Other Resources Referred To

I should check out the following references made in the book

I'm Yong Jie