Sequence Containers

Abstract¶

Encapsulation is a fundamental principle of object-oriented programming that promotes modularity and data protection by bundling data and the methods that operate on it within a single unit. Standard library containers such as array, vector, list, set, and map exemplify encapsulation by exposing well-defined interfaces while hiding internal implementation details. Encapsulation also facilitates resource management strategies like move semantics, where rvalue references and universal references allow efficient transfer and reuse of resources. This notebook introduces the basic idea of encapsulation using sequence containers such as vector and list.

from __init__ import *
%reload_ext divewidgets
!mkdir -p private

%%cpp
#include "utility.hpp"

Motivation¶

Encapsulation is the technique of capturing resources such as variables (properties) and functions (methods) into an entity (object). This lays the foundation for object‑oriented programming (OOP). We will go into how sequence containers such as the vector and list in C++ hides the internal mechanics behind a clean interface.

To motivate the concept, consider the problem of enumerating combinations in combinatorics:

How to define a function to compute combinations?

A divide-and-conquer approach is as follows:

Proposition 1

A $k$ -combination $S$ of $n$ items satisfies the recurrence relation for $1\leq k\leq n$ :

$S\setminus \Set{n-1}$ is a combination of $n-1$ items with
$k-1$ items if ${{\color{red}n-1}}\in S$ ; or
${\color{blue}k}$ items otherwise.

Reversing the above removal process gives a way of constructing a $k$ -combination $S$ from a smaller combination $T$ of $n-1$ items with

${\color{blue}k}$ items; or
$k-1$ items and add ${\color{red}n-1}$ to it.

If $0=k< n$ , $S=\Set{}$ . $S$ does not exist for other choices of $(n, k)$ . E.g., $k=2$ -combinations of $n=3$ items $\Set{0,1,2}$ can be constructed as follows:

\overbrace{{\color{blue}\Set{0, 1}}}^{\mathclap{\text{\scriptsize ${\color{blue}2}$-combination of $\{0, 1\}$}}}, \underbrace{\Set{0, {\color{red}2}}, \Set{1, {\color{red}2}}}_{\mathclap{\text{\scriptsize $2$ added to $1$-combinations of $\{0, 1\}$}}}.

(1)

A $k$ -combination in Definition 1 can be implemented as a vector container of indices from $\Set{0, \dots, n-1}$ :

%%cpp
vector<size_t>{0,1,2}

(std::vector<size_t>) { 0, 1, 2 }

The collection of combinations can be a vector of a vector of indices:

%%cpp
vector<vector<size_t> > {{0,1},{0,2},{1,2}}

(std::vector<std::vector<size_t> >) { { 0, 1 }, { 0, 2 }, { 1, 2 } }

To implements the divide-and-conquer approach in Proposition 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * @brief Generates all k-combinations of the set {0, 1, ..., n-1}.
 *
 * This function uses recursion to build combinations by either:
 * - excluding the last element (n-1) and generating k-combinations of the first n-1 elements
 * - including the last element (n-1) and generating (k-1)-combinations of the first n-1 elements,
 *   then appending n-1 to each of those to form a full k-combination.
 *
 * @param n The size of the set to choose from.
 * @param k The number of elements to choose.
 * @return A vector of vectors, each representing a k-combination of the set {0, ..., n-1}.
 */
std::function<std::vector<vector<size_t> >(const size_t, const size_t)>
combination=[&combination](const size_t n, const size_t k) {
    vector<vector<size_t> > output; // base case when k is not in {0, ..., n}.
    if (k<=n) {
        if (k) {
            // Case 1: k-combinations from the first n-1 elements
            for (auto &subset : combination(n-1, k)) output.push_back(subset);
            
            // Case 2: (k-1)-combinations from the first n-1 elements, with n-1 added
            for (auto &subset : combination(n-1, k-1)) {
                subset.push_back(n-1);
                output.push_back(subset);
            }
        } else output.push_back(vector<size_t>()); // base case: only one combination of size 0 (empty set)
    } // Hidden base case: No combinations if k is not in the range {0, ..., n}
    return output;
};

Program 1:Returning a std::vector of $k$ -combinations of $n$ items $\Set{0,1, \dots, n-1}$ .

%%cpp
std::function<std::vector<vector<size_t> >(const size_t, const size_t)>
combination=[&combination](const size_t n, const size_t k) {
    vector<vector<size_t> > output;
    if (k<=n) {
        if (k) {
            for (auto &subset : combination(n-1, k)) output.push_back(subset);
            for (auto &subset : combination(n-1, k-1)) {
                subset.push_back(n-1);
                output.push_back(subset);
            }
        } else output.push_back(vector<size_t>());
    }
    return output;
};

The following generates different combinations of 3 items:

%%cpp
combination(3, 0)

(std::vector<std::vector<unsigned long, std::allocator<unsigned long> >, std::allocator<std::vector<unsigned long, std::allocator<unsigned long> > > >) { {} }

%%cpp
combination(3, 1)

(std::vector<std::vector<unsigned long, std::allocator<unsigned long> >, std::allocator<std::vector<unsigned long, std::allocator<unsigned long> > > >) { { 0 }, { 1 }, { 2 } }

%%cpp
combination(3, 2)

(std::vector<std::vector<unsigned long, std::allocator<unsigned long> >, std::allocator<std::vector<unsigned long, std::allocator<unsigned long> > > >) { { 0, 1 }, { 0, 2 }, { 1, 2 } }

%%cpp
combination(3, 3)

(std::vector<std::vector<unsigned long, std::allocator<unsigned long> >, std::allocator<std::vector<unsigned long, std::allocator<unsigned long> > > >) { { 0, 1, 2 } }

%%cpp
combination(3, 4)

(std::vector<std::vector<unsigned long, std::allocator<unsigned long> >, std::allocator<std::vector<unsigned long, std::allocator<unsigned long> > > >) {}

%%cpp
combination(-1,0).empty()

(bool) false

Solution to Exercise 1

This is because the first parameter n is unsigned.

Consider counting the number of combinations using the method size:

size_type size() const;

%%hermes
Explain in one line what does `const` mean for the method. 
What are other possible qualifiers:
--
size_type size() const;

Hermes

One line: For a method, const means the implicit this is a pointer to const — so size() may inspect the object’s state but may not modify any member.

Other possible qualifiers on a member function:

Ref-qualifiers & (callable only on lvalues) or && (only on rvalues), optionally combined with const: e.g. int f() &;, int g() &&;, int k() const &;.
Exception specification — notably noexcept: e.g. size_type size() const noexcept;.

g++-verified (-std=c++23 -O2 -Wall -Wextra): all of const, &, &&, const &, and noexcept are accepted as written above, and a negative probe confirms the const guarantee — assigning inside a const method fails with error: assignment of member 'S::x' in read-only object.

So in the lecture’s declaration size_type size() const;, the only qualifier present is the cv-qualifier const; the standard library also typically adds the exception spec, i.e. size() const noexcept.

For instance, the total number of 11-combinations of 22 items is:

%%cpp
combination(22, 11).size()

(unsigned long) 705432

Similarly, the following computes the total number of 12-combinations of 24 items: (The computation is about 5 times slower than the above. You have been warned.)

%%cpp
combination(24, 12).size()

(unsigned long) 2704156

How to improve the performance?

If the goal is to compute the number of combinations, we can do it simply by computing the binomial coefficient:

%%cpp
unsigned long binomial_coefficient(const size_t n, const size_t k) {
    return k<=n? (k? binomial_coefficient(n-1, k) + binomial_coefficient(n-1, k-1) : 1uL) : 0uL;
}

%%cpp
binomial_coefficient(24, 12)

(unsigned long) 2704156

How to improve the performance of combination?

Thanks to encapsulation, we can easily improve our code by choosing a suitable object and its associated methods:

1
2
3
4
5
6
7
8
9
10
11
12
13
std::function<std::list<vector<size_t> >(const size_t, const size_t)>
combination=[&combination](const size_t n, const size_t k) {
    list<vector<size_t> > output;
    if (k<=n) {
        if (k) {
            output.splice(output.cend(), combination(n-1, k));
            list<vector<size_t> > subset_seq=combination(n-1, k-1);
            for (auto &subset : subset_seq) subset.push_back(n-1);
            output.splice(output.cend(), subset_seq);
        } else output.emplace_back();
    }
    return output;
};

Program 2:Returning a std::list of $k$ -combinations of $n$ items $\Set{0,1, \dots, n-1}$ .

%%cpp
std::function<std::list<vector<size_t> >(const size_t, const size_t)>
combination=[&combination](const size_t n, const size_t k) {
    list<vector<size_t> > output;
    if (k<=n) {
        if (k) {
            output.splice(output.cend(), combination(n-1, k));
            list<vector<size_t> > subset_seq=combination(n-1, k-1);
            for (auto &subset : subset_seq) subset.push_back(n-1);
            output.splice(output.cend(), subset_seq);
        } else output.emplace_back();
    }
    return output;
};

%%cpp
combination(3, 2)

(std::list<std::vector<unsigned long, std::allocator<unsigned long> >, std::allocator<std::vector<unsigned long, std::allocator<unsigned long> > > >) { { 0, 1 }, { 0, 2 }, { 1, 2 } }

The following call is about 4 times faster than before:

%%cpp
combination(22, 11).size()

(unsigned long) 705432

The following call is about 5 times faster than before:

%%cpp
combination(24, 12).size()

(unsigned long) 2704156

The speed up is larger for larger $n$ and $k$ ! How does it work?

In Program 1, we mainly used the method push_back to create each combination and the collection of all combinations. There are two overloads:

void push_back( const T& value );
void push_back( T&& value );

Which overload is used and why?

%%hermes
Explain very briefly what are the differences between the two overloads:
--
void push_back( const T& value );
void push_back( T&& value );

🌿 Fork/new: main (will create on click)

Hermes

push_back(const T& value) — called with an lvalue (a named object): the element is copied into the container.

push_back(T&& value) — called with an rvalue (a temporary / movable object): the element is moved, transferring its internal resources instead of deep-copying them.

Overload resolution picks by argument category: lvalue → first overload, rvalue → second. So in the combination code above, combinations.push_back(c) copies c (it’s a named variable), while combinations.push_back(std::vector<size_t>{...}) would move the temporary. For cheap types like int it makes no observable difference (a move degenerates to a copy); for heap-backed objects (e.g. another vector) it’s the difference between allocating+copying vs. stealing a pointer. It’s also what makes std::move work, and what makes move-only types (std::unique_ptr) usable with push_back at all.

In Program 2, we used the std::list object to store the collection of combinations, and its method splice to concatenate lists of combinations:

void splice( const_iterator pos, list& other );
void splice( const_iterator pos, list&& other );
void splice( const_iterator pos, list& other, const_iterator it );
void splice( const_iterator pos, list&& other, const_iterator it );
void splice( const_iterator pos, list& other,
             const_iterator first, const_iterator last );
void splice( const_iterator pos, list&& other,
             const_iterator first, const_iterator last );

Again, which overload is used and why?

%%hermes
Explain very briefly what are the differences between the two overloads:
--
void splice( const_iterator pos, list& other );
void splice( const_iterator pos, list&& other );
void splice( const_iterator pos, list& other, const_iterator it );
void splice( const_iterator pos, list&& other, const_iterator it );
void splice( const_iterator pos, list& other,
             const_iterator first, const_iterator last );
void splice( const_iterator pos, list&& other,
             const_iterator first, const_iterator last );

↻ Session: main (ACP: 0bd63afe-722…)

Hermes

The difference is again lvalue vs rvalue — with a meaningful performance consequence.

list& other (lvalue): elements are transferred by relinking nodes, and afterwards other is guaranteed valid — empty for the whole-list overload, still usable for the single/range ones.
list&& other (rvalue): since you won’t use other again, the implementation may do a bulk transfer of the node block instead of relinking each node (e.g. moving the list’s internal head/tail pointers) — faster. The cost: other is left in a valid but unspecified state.

So the rvalue overload trades a validity guarantee for speed; the two are picked by overload resolution just like push_back.

In Program 2 this is exactly why it’s fast:

output.splice(output.cend(), combination(n-1, k)) passes a temporary → list&& overload → whole sub-list moved in bulk, no per-node work.
output.splice(output.cend(), subset_seq) passes a named list → list& overload → same effect, but subset_seq must be left valid (empty), since it’s a local object still in scope.

We also used the method emplace_back() in Program 2 in place of push_back(vector<size_t>()) in Program 1 to add an empty combination, without constructing the combination explicitly:

template< class... Args >
reference emplace_back( Args&&... args );

What does the ... mean and why is it used?

%%hermes
Explain very briefly the following syntax:
--
template< class... Args >
reference emplace_back( Args&&... args );

Hermes

class... Args is a parameter pack: the template accepts any number of argument types, inferred from the call. Args&&... args is a pack of forwarding (universal) references — each caller argument binds to its own element of the pack, preserving whether it’s an lvalue or rvalue.

So v.emplace_back(a, b, c) forwards a, b, c perfectly into the element’s constructor: the object is built in place inside the container’s storage, with no temporary created and then moved/copied. That’s the point vs. push_back: e.g. v.emplace_back(3, 1) directly constructs a vector<size_t> from its initializer list, skipping the temporary that push_back(vector<size_t>{3,1}) would make.

%%hermes
Why construct in-place using `emplace_back` instead of `push_back`?

↻ Session: main (ACP: 0bd63afe-722…)

Hermes

Because emplace_back builds the element directly inside the container’s storage, so no intermediate object is ever created:

push_back(x) needs a ready-made object — it must first exist (as a temporary), then be copied or moved into place.
emplace_back(args...) forwards the arguments straight into the element’s constructor and constructs once, in place — no temporary, no copy, no move.

So it saves work that scales with the element’s size: for a vector<size_t> in the combination code above, emplace_back() (or emplace_back(3)) skips allocating and filling a throwaway vector that push_back(vector<size_t>{3}) would create. For trivial types (int) the compiler elides it anyway, so the win only shows up for heap-backed / larger elements — which is exactly the performance theme of this lecture.

While we can reuse code easily with OOP, we need to know how to choose the object, its methods, and their overloads. That demands a deeper understanding of the design of the object and how its resources are managed. We will take a closer look at std::vector and st::list.

Referencing Resources¶

To understand the difference between && and &, recall the following code from a previous lecture. What is the value of a after executing the following code?

%%cpp
auto a=1, &b=a;
b+=1;
a

(int) 2

To see why a is 2 instead of 1, we can print the addresses of a and b and show that the addresses are the same:

%%cpp
auto a=1, &b=L(a);
L(b)+=1;
a

(int) a @0x707a385aa000
(int &) b @0x707a385aa000
(int) 2

L is a macro defined in the header file “utility.hpp” as

#define L(x) loc(x, std::string("(")+std::string(type<decltype(x)>())+") "+#x)

which calls a function called loc defined in the same file. This function

decorates a value by printing its address, but
preserves the original value so that the behavior of the original code remains unchanged.

How to properly pass an argument by reference to implement the loc function?

Lvalue Reference¶

The following implementation passes the argument and return it by lvalue reference:

%%cpp
auto &loc1(auto &x) {
    cout << format("@{:p}\n", static_cast<void *>(&x));
    return x;
}

It appears to work:

%%cpp
auto a=1, &b=loc1(a);
loc1(b)+=1;
a

@0x707a385a6000
@0x707a385a6000
(int) 2

%%cpptutor
#include <iostream>
#include <format>

using std::cout, std::format;

auto &loc1(auto &x) {
    cout << format("@{:p}\n", static_cast<void *>(&x));
    return x;
}

int main() {
    const auto a=1, &b=loc1(a);
    loc1(b);
    return 0;
}

Solution to Exercise 2

To print the address &x, loc1 casts it statically to <void *>, which is not a constant type. This is not allowed since the original type const int * is constant.

Instead of using const_cast, it is safer to implement the following fix:

%%cpp
auto &loc1(auto &x) {
    cout << format("@{:p}\n", static_cast<const void *>(&x));
    return x;
}

loc1 now works for constants:

%%cpp
const auto a=1, &b=loc1(a);
loc1(b)

@0x707a38591014
@0x707a38591014
(const int) 1

%%hermes
Explain briefly when it is essential to use const_cast instead of static_cast
for constant pointers.

Hermes

static_cast can only add const-qualification (T* → const T*) — it can never remove it. So whenever you need a pointer type that is less const than your source, static_cast won’t compile and const_cast is the only option.

Essential cases:

Calling through to an API that lacks a const overload — e.g. a legacy C function taking char*, or an old class method that isn’t marked const. If the object is truly non-const (only a local view is const), casting away const is safe and necessary.
Mutating something logically mutable — e.g. a “dirty” flag or cache stored on a const object; the standard pattern is const_cast<T*>(this) inside a non-const accessor.

What NOT to do (as in this notebook): using const_cast<void*>(&x) just to print an address was unnecessary and unsafe — printing doesn’t mutate, so the safe fix was static_cast<const void*>(&x). Rule of thumb: if you don’t actually write through the pointer, add const (static_cast<const void*>); if you must hand a non-const pointer to something that won’t modify it (or will legitimately modify a non-const object), that’s when const_cast becomes essential — and writing through it is UB (Undefined Behavior) if the object itself was defined const.

Consider the following direct initialization:

%%cpp
auto u(vector<int>{1, 2, 3});

Does u reuse the memory allocated to the rvalue vector<int>{1, 2, 3}?

Exercise 3

Why using loc1 as follows leads to an error?

auto u(loc1(vector<int>{1, 2, 3}));
loc1(u);

As the following program shows, loc1 appears to work for C-string but fail for the compound literal for char. Why?

%%cpp
loc1("a")        // works?!

@0x707a3859d014
(const char[2]) "a"

%%cpp
// loc1((char[]){'a'});  // fails: expects an lvalue for 1st argument
// loc1(static_cast<char * const>((char[]){'a', 0})); // making it constant also fail
(char[]){'a', 0}            // isn't it just "a"?

(char[2]) "a"

Solution to Exercise 3

It fails as it expects an lvalue for the first argument. The string literal works because it is a constant array, which can therefore be passed by constant lvalue reference. However, (char[]){'a', 0} is not constant and therefore fails. Note that static_cast<char * const>((char[]){'a', 0}) does not make it a constant. Instead, the following works:

loc1((const char[]){'a', 0});

A potential fix is to add const qualifier to the parameter x:

%%cpp
auto &loc2(const auto &x) {
    cout << format("@{:p}\n", static_cast<const void *>(&x));
    return x;
}

%%cpp
auto u(loc2(vector<int>{1, 2, 3}));
loc2(u)

@0x7ffc7fe8b130
@0x707a3858f000
(const std::vector<int, std::allocator<int> > &) { 1, 2, 3 }

%%cpptutor
#include <iostream>
#include <format>
#include <vector>

using std::cout, std::format, std::vector;

auto &loc2(const auto &x) {
    cout << format("@{:p}\n", static_cast<const void *>(&x));
    return x;
}

int main() {
    auto u(loc2(vector<int>{1, 2, 3}));
    loc2(u).push_back(4);
    return 0;
}

Solution to Exercise 4

loc2 implicitly casts the input vector to const, so u becomes immutable and can no longer be modified. In other words, loc2 changed the original code by treating u as a constant vector.

Rvalue Reference¶

A potential fix is to pass the argument by rvalue reference using && instead of &:

auto &loc3(auto &&x) {
    cout << format("@{:p}\n", static_cast<const void *>(&x));
    return x;
}

This appears to work: loc3_C++20.ipynb. However, it fails for C++23?

%%cpptutor
#include <iostream>
#include <format>
#include <vector>

using std::cout, std::format, std::vector;

auto &loc3(auto &&x) {
    cout << format("@{:p}\n", static_cast<const void *>(&x));
    return x;
}

int main() {
    auto u(loc3(vector<int>{1, 2, 3}));
    loc3(u).push_back(4);
    return 0;
}

C++23: Disallow Binding a Returned Glvalue to a Temporary

C++23 adopted the proposal P2748R5, which tightens the rules around returning references that would immediately dangle. The key wording introduced by the proposal is:

In a function whose return type is a reference, other than an invented function for std::is_convertible, a return statement that binds the returned reference to a temporary expression is ill-formed.

This change turns a class of subtle lifetime bugs that previously compiled (and often produced dangling references at runtime) into compile-time errors.

WG21 proposal papers such as P2748R5 are working documents used by the ISO C++ committee to discuss, justify, and specify changes to the C++ language and standard library. When a proposal is accepted, its wording (possibly after further revision) is incorporated into a future version of the C++ standard. Consequently, these papers are often the best source for understanding the motivation, design rationale, examples, and precise wording behind a language change.

Does it really work for C++20?

loc3 returns an lvalue instead, which is assignable even for simple integer type. In other words, loc3 changed the behavior of the original code.

%%cpp
[](int &&x) {x=0;}(1);  // change 1 to 0
auto x=1                // x is 0?

(int) 1

Solution to Exercise 5

1 is just a literal. The memory locations for the first 1 and second 1 can be different.

How about returning the output by rvalue reference as well as in:

auto &&loc4(auto &&x) {
    cout << format("@{:p}\n", static_cast<const void *>(&x));
    return x;
}

This fails for C++20: loc4_C++20.ipynb

Solution to Exercise 6

This is because an rvalue reference cannot bind to the lvalue x:

template <class T>
T &&loc4(T &&x, ...) {
    ...
    return x;
}

A potential fix is to cast x to an rvalue reference using std::move(x):

%%cpp
template <class T>
T &&loc5(T &&x) {
    cout << format("@{:p}\n", static_cast<const void *>(&x));
    return std::move(x);
}

It appears to work now:

%%cpp
auto u(loc5(vector<int>{1, 2, 3}));
// loc5(1) = 0;   // fails: expression is not assignable

@0x7ffc7fe8b130

Does it really work? loc5 fails to handle lvalue:

%%cpp
auto a=1;
// loc5(a); // error

The error message is:

1
2
3
4
error: non-const lvalue reference to type 'int' cannot bind to a temporary of type 'typename
std::remove_reference<int &>::type' (aka 'int')
    return std::move(x);
           ^~~~~~~~~~~~

Universal Reference¶

A potential fix is to use static_cast instead of std::move:

%%cpp
template <class T>
T &&loc6(T &&x) {
    cout << format("@{:p}\n", static_cast<const void *>(&x));
    return static_cast<T &&>(x);
}

%%cpp
auto u(loc6(vector<int>{1, 2, 3}));
loc6(u)

@0x7ffc7fe8b130
@0x707a38575000
(std::vector &) { 1, 2, 3 }

But how can that make a difference? According to the documentation:

It (std::move) is exactly equivalent to a static_cast to an rvalue reference type.

The same fix does not work below:

%%cpp
int a=1;
[](int &&b) { return static_cast<int &&>(b); }
// (a);  // fails: expects an rvalue for 1st argument

((lambda at input_line_105:3:1)) @0x5f14a6d519b0

An important clue comes from the error message of loc5(a):

std::remove_reference<int &>::type' (aka 'int')

The return type from loc5 is an lvalue, not an rvalue!

Universal reference

For parameters of function templates, && is a forwarding/universal reference instead of an rvalue reference. It simply forwards the argument, preserving its value category:

For the code loc5(a);, a is passed by lvalue reference, i.e., T && becomes int &, which is also the return type by the function declaration T &&loc5(T &&x). The return lvalue reference is non-const and therefore cannot bind to a temporary std::move(x).
loc6(a); works because static_cast<T &&>(x) instantiates to static_cast<int &>(x), which is an lvalue reference instead of a temporary!

We can use std::forward<T> instead of static_cast<T &&> to make it less confusing:

/**
 * @brief Logs the memory address of a variable along with an optional label.
 * 
 * This function is useful for educational purposes, especially when tracking
 * object lifetimes, locations in memory, or verifying move semantics.
 * 
 * @tparam T Type of the variable (supports universal references).
 * @param x The variable to log.
 * @param label Optional label to identify the variable in the output.
 * @return T&& Perfectly forwarded variable.
 */
template <class T>
T &&loc(T &&x, const string &label="") {
    cout << format("{} @{:p}\n",
        label,
        static_cast<const void*>(&x));
    return std::forward<T>(x);
}

Program 4:The implementation of loc in “utility.hpp”.

%%cpp
auto u(loc(vector<int>{1, 2, 3}));
loc(u)

 @0x7ffc7fe8b128
 @0x707a3856d000
(std::vector &) { 1, 2, 3 }

It turns out that an explicit std::forward<T>(x) is not required for C++23:

%%cpp
template <class T>
T &&loc4(T &&x) {
    cout << format("@{:p}\n", static_cast<const void *>(&x));
    return x;
}

%%cpp
auto u(loc4(vector<int>{1, 2, 3}));
loc4(u)

@0x7ffc7fe8b130
@0x707a38560000
(std::vector &) { 1, 2, 3 }

Back to our original endeavor, does u reuse the memory allocated to the rvalue vector<int>{1, 2, 3}?

It seems that the rvalue vector<int>{1, 2, 3} occupies a different memory location than the lvalue u does. What about copy initializations?

%%cpp
auto u=LB((vector<int>{1, 2, 3}));
auto v=LB(u);
LB(v)

(std::vector<int>) (vector<int>{1, 2, 3}) begin@0x5f14abc52cb0
(std::vector<int>) u begin@0x5f14abc52cb0
(std::vector<int>) v begin@0x5f14abb29740
(std::vector &) { 1, 2, 3 }

%%hermes
Explain very briefly how direct initialization in C++ is different from
copy initialization and list initialization?

Hermes

Direct — T x(e);: arguments go straight to a constructor. Copy — T x = e;: the compiler imagines an object of type T being copied from e; the converting constructor must be non-explicit. List — T x{e,...};: if a viable initializer_list constructor exists it takes priority, otherwise normal construction — but narrowing conversions are forbidden.

The practical differences:

struct S { int i; };

int i(1.5);      // direct: OK (narrowing allowed)
int j = 1.5;     // copy:   OK
int k{1.5};      // list:   ERROR — narrowing

explicit struct E { E(int) {} };
E e(3);          // direct: OK
E f = 3;         // copy:   ERROR — explicit ctor not allowed
E g{3};          // list:   OK (direct-list-init)

vector<int> v1{1, 2, 3};  // list: initializer_list ctor → 3 elements
vector<int> v2(1, 2);     // direct: size=1, value=2       → 1 element {2}

Two rules matter most in this lecture’s code: explicit blocks only copy-init (that’s why T t(expr); still works), and braces change which constructor wins (emplace_back() vs push_back(vector<...>{...}) is exactly this mechanism).

We are now ready to dive into how objects are constructed using different constructors and initializations.

Vector Construction¶

There many constructors available for constructing vectors. Unlike other methods, constructors have no names but can be called in various ways to create rvalues or to initialize variables.

Converting Constructors¶

Constructors that take a single argument and is not marked as explicit are called converting constructors. These constructors can be used for implicit conversions or copy initialization.

Initializer‑List Constructor¶

vector( std::initializer_list<T> init,
        const Allocator& alloc = Allocator() );

adds elements from a (braced) initializer list.

%%cpp
vector<size_t> {0, 1, 2}     // vector constructed with braced initializer list

(std::vector<size_t>) { 0, 1, 2 }

%%cpp
vector<size_t> u {0, 1, 2}   // list initialization

(std::vector<size_t> &) { 0, 1, 2 }

%%cpp
vector<size_t> u({0, 1, 2})  // direct initialization with braced initializer list

(std::vector<size_t> &) { 0, 1, 2 }

%%cpp
vector<size_t> u={0, 1, 2}   // copy-list initialization

(std::vector<size_t> &) { 0, 1, 2 }

To use an initializer list explicitly:

%%cpp
initializer_list<size_t> ilist {0, 1, 2};
(vector<size_t>(ilist))  // vector constructed with initializer list

(std::vector<size_t>) { 0, 1, 2 }

%%cpp
vector<size_t> u(ilist)  // direct initialization with initializer list

(std::vector<size_t> &) { 0, 1, 2 }

%%hermes
Explain very briefly how is copy-list initialization different from
list initialization for `std::vector`.

🌿 Fork/new: main (will create on click)

Hermes

Very briefly: for std::vector, nothing observable differs — both call the same initializer_list constructor:

List initialization — std::vector<size_t> u{0, 1, 2};: direct-initializes u with the braced list straight into the initializer_list constructor.
Copy-list initialization — std::vector<size_t> u={0, 1, 2};: same effect; it’s T u = {…}, so formally the braces make an rvalue of type std::initializer_list<T> which is then “copied” into u.

The only place the = distinction can bite is for other types: in copy-init, a non-matching list may fall back to other constructors (and explicit ones are rejected — verified: S s2 = {3} with an explicit S(int) fails with “converting from initializer list would use explicit constructor”, while S s1{3} compiles). For std::vector, the non-explicit initializer_list constructor wins either way, so the two cells at indices 142/144 construct identical vectors.

Move Constructor¶

vector( vector&& other );

moves elements from another vector:

%%cpp
vector<int>(vector<int>{1, 2, 3}) // vector constructed with elements moved from other

(std::vector<int>) { 1, 2, 3 }

%%cpp
auto u(vector<int>{1, 2, 3})      // direct initialization

(std::vector<int> &) { 1, 2, 3 }

%%cpp
auto u=vector<int>{1, 2, 3}       // copy initialization

(std::vector<int> &) { 1, 2, 3 }

To see that elements are not duplicated:

%%cpp
auto u(LB(L((vector<int>{1, 2, 3}))));
LB(L(u))

(std::vector<int>) (vector<int>{1, 2, 3}) @0x7fff1e0d4ef0
(std::vector<int> &&) L((vector<int>{1, 2, 3})) begin@0x62a2f47998f0
(std::vector<int>) u @0x7a00aab84000
(std::vector<int> &) L(u) begin@0x62a2f47998f0
(std::vector &) { 1, 2, 3 }

Even though the lvalue u and rvalue vector<int>{1, 2, 3} have different memory locations, they begin storing their elements at the same location, i.e., the lvalue reuses the memory allocated to the rvalue.

What is LB?

LB is a macro defined as

#define LB(x) loc_begin(x, std::string("(")+std::string(type<decltype(x)>())+") "+#x)

which expands to a call to loc_begin in “utility.hpp” to locate the beginning of the vector:

// Overload for containers with .cbegin()
template <class T>
std::enable_if_t<has_begin<T>::value, T&&>
&&loc_begin(T &&x, const string &label="") {
    cout << format("{} begin@{:p}\n", label, static_cast<const void*>(&*(x.cbegin())));
    return std::forward<T>(x);
}

To see that the elements are moved:

%%cpp
vector<size_t> u {1,2,3}, v(std::move(LB(u))); // move elements of `u` to `v`
LB(u).empty()? LB(v): throw runtime_error("Elements of `u` should be moved!")

(std::vector<unsigned long>) u begin@0x62a2f3c6a2e0
(std::vector<unsigned long>) u begin@0x0
(std::vector<unsigned long>) v begin@0x62a2f3c6a2e0
(std::vector &) { 1, 2, 3 }

std::move casts u as an rvalue reference, which is then passed to the move constructor:

The move constructor steals the resources from u, making it empty and
the address of its first element becomes the nullptr.

Copy Constructor¶

vector( const vector& other );

can be used to copy elements from another vector:

%%cpp
vector<size_t> u {1,2,3};
(vector<size_t>(u))  // vector constructed with elements copied from other

(std::vector<size_t>) { 1, 2, 3 }

%%cpp
auto v(u)  // direct initialization

(std::vector<size_t> &) { 1, 2, 3 }

%%cpp
auto v=u  // copy initialization

(std::vector<size_t> &) { 1, 2, 3 }

To see that the elements are duplicated:

%%cpp
(LB(u) == LB(v))

(std::vector<unsigned long>) u begin@0x62a2f45b2a10
(std::vector<unsigned long>) v begin@0x62a2f4616420
(bool) true

v is equal to u but it does not begin at the same location as u.

Shallow copy is prone to mutability bug. For instance:

Exercise 7

Explain why s at the end of the following code is not "aba"?

Hint

The first call LB(s) uses the overload

// Overload for C-style arrays
template <class T, size_t N>
T (&loc_begin(T (&x)[N], const string &label = ""))[N] {
    cout << format("{} begin@{:p}\n", label, static_cast<const void*>(&x[0]));
    return x;
}

but the second call LB(t) uses the overload

// For pointers or decayed arrays
template <class T>
typename std::enable_if<std::is_pointer<T>::value, T>::type
loc_begin(T x, const string& label = "") {
    cout << format("{} begin@{:p}\n", label, static_cast<const void*>(x));
    return x;
}

%%cpp
char s[]="aba";
auto t(LB(s));
LB(t)[1]='v';
s // aba?

(char[4]) s begin@0x7a00aa34e000
(char *) t begin@0x7a00aa34e000
(char[4]) "ava"

Solution to Exercise 7

Since s decays to a pointer when initializing t, i.e., t points to the first element of s, so LB(t)[1]='v' mutates s.

%%cpp
auto u=vector<vector<size_t> > {{1}, {2, 3}}, v=u;
v

(std::vector<std::vector<size_t> > &) { { 1 }, { 2, 3 } }

Solution to Exercise 8

The declaration calls

the initializer constructor to convert {{1}, {2, 3}} to a vector;
the move constructor to initialize u; and
the copy constructor to copy u to v.

Explicit Constructors¶

There are also constructors that cannot be used in copy initialization nor implicit conversion.

Default Constructor¶

vector() noexcept(noexcept(Allocator())) : vector(Allocator()) {}

takes no argument and returns an empty vector:

%%cpp
vector<size_t>()

(std::vector<size_t>) {}

%%cpp
vector<size_t> u

(std::vector<size_t> &) {}

%%hermes
Explain brielfy the motivation of `noexcept` in the constructor:
`vector() noexcept(noexcept(Allocator())) : vector(Allocator()) \{\}`

Hermes

noexcept(noexcept(Allocator())) makes the promise conditional: the vector’s default constructor only claims “cannot throw” if constructing the default allocator cannot throw.

Why conditional, not noexcept(true): it delegates to vector(Allocator()), which constructs a default allocator. A custom allocator could throw — a hard noexcept(true) would be a lie, turning any throw into immediate std::terminate.
Why not unconditional (or noexcept(false)): the standard allocator genuinely never throws, so hardcoding false would understate the guarantee. Containers and algorithms key optimizations on this — e.g. vector’s move constructor is itself noexcept (and hence used instead of copy during reallocation) precisely because its elements’ moves/allocations are exception-free. The propagated guarantee is what makes those nothrow paths available.

So the pattern: inherit the guarantee from what you delegate to, neither stronger nor weaker than reality.

Fill Constructors¶

1
2
explicit vector( size_type count, const Allocator& alloc = Allocator() );
vector( size_type count, const T& value, const Allocator& alloc = Allocator() );

fill a vector with n copies of value, if available, and 0 otherwise:

%%cpp
vector<size_t>(3, 4)           // vector constructed by the fill constructor

(std::vector<size_t>) { 4, 4, 4 }

%%cpp
vector<size_t> u(2)      // direct initialization

(std::vector<size_t> &) { 0, 0 }

Solution to Exercise 9

This is because the first overload of the fill constructor

explicit vector( size_type count, const Allocator& alloc = Allocator() );

is marked explicit. Therefore, it is not a converting constructor and cannot be used in copy initialization.

Range Constructor¶

template<class InputIt> vector(InputIt first, InputIt last, const Allocator& a = Allocator())

copies elements within a range from the position first up to but excluding last:

%%cpp
vector<size_t> u {0, 1, 2, 3};
vector<size_t>(u.cbegin(), u.cend()-1)   // vector constructed by coping elements of u except for the last

(std::vector<size_t>) { 0, 1, 2 }

%%cpp
vector<size_t> v(u.cbegin(), u.cend()-2) // direct initialization

(std::vector<size_t> &) { 0, 1 }

To show that the elements are copied:

%%cpp
LB(u), LB(v)

(std::vector<unsigned long>) u begin@0x62a2f4a93b00
(std::vector<unsigned long>) v begin@0x62a2f526d220
(std::vector &) { 0, 1 }

%%cpp
vector<size_t> u {0, 1, 2, 3};
vector<size_t>(u.crbegin(), u.crend())  // vector constructed by coping elements of u in reverse

(std::vector<size_t>) { 3, 2, 1, 0 }

Iterator¶

We can traverse the elements of a vector as follows:

%%cpp
vector<size_t> u {0, 1, 2, 3};
for (auto ui: u) cout << ui << '\n';

What if we want to traverse only parts of the vector?

The position of an element in a container is specified using an iterator, which is a generalization of pointers to elements of an array.

u.cbegin() is the position of the first element of u.
u.cend() gives the position of an imaginary element one past the last element of u.
u.crbegin() gives the position of the last (first) element of (reversed) u.
u.crend() gives the position of an imaginary element one before (past) the first (last) element of (reversed) u.

Similar to a pointer, * can be used to dereference the element stored at a position. Other elements can also be accessed by incrementing the iterator:

%%cpp
vector<size_t> u {0, 1, 2, 3};
for (auto it=u.cbegin()+1; it!=u.cend()-1; it++) cout << *it << '\n';

1
2

%%cpp
vector<size_t> u {0, 1, 2, 3};
for (auto it=u.crbegin()+1; it!=u.crend()-1; it++) cout << *it << '\n';

2
1

To modify the container, we need to use non-constant iterators returned by begin, end, rbegin, and rend:

%%cpp
vector<size_t> u {0, 1, 2, 3};
// for (auto it=u.cbegin()+1; it!=u.cend(); it++) *it=*it+*(it-1);
// error: cannot assign to return value because function 'operator*' returns a const value
for (auto it=u.begin()+1; it!=u.end(); it++) *it=*it+*(it-1);
u

(std::vector<size_t> &) { 0, 1, 3, 6 }

There are also other methods for iterators:

For containers that do not occupy continuous memory such as std::list, we may use std::advance(u, i) instead.

template< class InputIt, class Distance > void advance( InputIt& it, Distance n );
template< class InputIt, class Distance > constexpr void advance( InputIt&    it, Distance n );

pos - u.cbegin() or distance(u.cbegin(), pos) calculates how far an iterator pos of u is from its first element.
u.cend()-pos or distance(u.cend(), pos) calculates how far an iterator pos of u is from the element one past the last element of u.

%%cpp
vector<size_t> v {1, 2, 3, 4};
auto it=v.cbegin();
advance(it, 3);
it=v.erase(it);
advance(it, -2);
it=v.erase(it);
cout << format("Elements before and after {} removed.\n", *it);
v

Elements before and after 3 removed.
(std::vector<size_t> &) { 1, 3 }

%%cpp
it-v.cbegin()

(long) 1

%%cpp
distance(v.cbegin(), it)

(long) 1

%%hermes
Explain in one line the difference between begin vs cbegin, and end vs cend 
for std::vector.

Hermes

begin/end return non-const iterators (elements are writable through them), while cbegin/cend always return const iterators — dereferencing them is read-only, as the cell at index 210 shows with its commented-out *it=*it+… modification (verified: *it=9 on a cbegin() iterator fails with error: assignment of read-only location, while the identical begin() variant compiles).

Vector Contraction¶

We can clear all elements of a vector using the clear method:

void clear();

%%cpp
vector<size_t> v {1, 2, 3};
v.clear();
v

(std::vector<size_t> &) {}

To erase only some of the elements, use the erase method:

1
2
iterator erase( const_iterator pos );
iterator erase( const_iterator first, const_iterator last );

which returns an iterator pointing to the element that follows the last removed element, or end() if the last element was erased.

%%cpp
vector<size_t> v {1, 2, 3};
auto it=v.erase(v.cbegin()+1);
cout << format("Element before {} was removed.\n", *it);
v

Element before 3 was removed.
(std::vector<size_t> &) { 1, 3 }

We can also erase a range of elements by specifying the first and last (exclusive) positions:

%%cpp
vector<size_t> v {1, 2, 3};
v.erase(v.cbegin()+1, v.cend());
v

(std::vector<size_t> &) { 1 }

Vector Expansion¶

Insert at the Back¶

There are various ways to append an element to a std::vector.

One way is to use push_back(), which has two overloads:

1
2
void push_back( const T& value );
void push_back( T&& value );

%%cpp
vector<vector<size_t> > u;
vector<size_t> v {0,1,2};
u.push_back(v);
u

(std::vector<std::vector<size_t> > &) { { 0, 1, 2 } }

Solution to Exercise 10

The above invokes the first overload since the rvalue reference in the second overload cannot bind to the lvalue v. Hence, v is copied but not moved to the back of u.

Observe that v and u[0] start at different locations:

%%cpp
LB(v), LB(u[0])

(std::vector<unsigned long>) v begin@0x62a2f564c3c0
(std::vector<unsigned long> &) u[0] begin@0x62a2f480a7d0
(std::vector &) { 0, 1, 2 }

Modifying v does not affect u:

%%cpp
v[0]=2;
u

(std::vector<std::vector<size_t> > &) { { 0, 1, 2 } }

v can be added to u again:

%%cpp
u.push_back(v);
u

(std::vector<std::vector<size_t> > &) { { 0, 1, 2 }, { 2, 1, 2 } }

As a comparison, the following invokes the second overload by casting v as an rvalue reference using std::move:

%%cpp
vector<vector<size_t> > u;
vector<size_t> v {0,1,2};
u.push_back(std::move(v));
u.push_back(v);
u

(std::vector<std::vector<size_t> > &) { { 0, 1, 2 }, {} }

Note that v is cleared after the move. To show that the elements are moved:

%%cpp
vector<vector<size_t> > u;
vector<size_t> v {0,1,2};
L(v);
u.push_back(std::move(LB(v)));
LB(u[0]), L(u), L(v)

(std::vector<unsigned long>) v @0x7a00aa2dc018
(std::vector<unsigned long>) v begin@0x62a2f4e1d690
(std::vector<unsigned long> &) u[0] begin@0x62a2f4e1d690
(std::vector<std::vector<unsigned long>>) u @0x7a00aa2dc000
(std::vector<unsigned long>) v @0x7a00aa2dc018
(std::vector &) {}

Even though v and u[0] have different locations, their elements begin at the same location. In essence, the move constructor is invoked to move the elements from v to a new vector in u.

We can also add an rvalue directly without creating an extra variable:

%%cpp
vector<vector<size_t> > u;
u.push_back(vector<size_t>{0,1,2});
u

(std::vector<std::vector<size_t> > &) { { 0, 1, 2 } }

This can be further simplified:

%%cpp
vector<vector<size_t> > u;
u.push_back({0,1,2});
u

(std::vector<std::vector<size_t> > &) { { 0, 1, 2 } }

Solution to Exercise 11

In the above, {0,1,2} is a braced initializer list which is

implicitly converted to a vector using the initializer-list constructor, and then
added to the back of u using the move constructor.

Indeed, we can further simplify the code as follows:

%%cpp
vector<vector<size_t> > u;
u.emplace_back((initializer_list<size_t>){0,1,2});
u

(std::vector<std::vector<size_t> > &) { { 0, 1, 2 } }

The constructed vector is exactly the vector added to the back:

%%cpp
vector<vector<size_t> > u;
L(u.emplace_back((initializer_list<size_t>){0,1,2})), L(u[0])

(std::vector<unsigned long> &) u.emplace_back((initializer_list<size_t>){0,1,2}) @0x62a2f5b6d890
(std::vector<unsigned long> &) u[0] @0x62a2f5b6d890
(std::vector &) { 0, 1, 2 }

Unlike push_back, emplace_back() constructs the vector in-place, i.e., the constructed vector is at the same location as the added vector:

template< class... Args > reference emplace_back( Args&&... args );

... is a packing operator that declares a pack of parameters. This allows a variable number of arguments to be forwarded from emplace_back to the different overloads of the constructors for vector:

%%cpp
vector<vector<size_t> > u;
u.emplace_back();          // forward to the default constructor
u

(std::vector<std::vector<size_t> > &) { {} }

%%cpp
vector<vector<size_t> > u;
u.emplace_back(2);         // forward to the fill constructor
u.emplace_back(3,4);
u

(std::vector<std::vector<size_t> > &) { { 0, 0 }, { 4, 4, 4 } }

In comparison, Python uses * as the packing operator such as *args in print:

print?

Signature: print(*args, sep=' ', end='\n', file=None, flush=False)
Docstring:
Prints the values to a stream, or to sys.stdout by default.

sep
  string inserted between values, default a space.
end
  string appended after the last value, default a newline.
file
  a file-like object (stream); defaults to the current sys.stdout.
flush
  whether to forcibly flush the stream.
Type:      builtin_function_or_method

%%cpp
template <class T>
void splice(vector<T> &u, const vector<T> &v) {
    for (auto vi : v) u.push_back(vi);
}

%%cpp
template <class T>
void splice(vector<T> &u, vector<T> &&v) {
    /*
    ### BEGIN SOLUTION
    */
    for (auto &vi : v) u.push_back(std::move(vi));
    v.clear();
    /*
    ### END SOLUTION
    */
}

%%cpp
// test
vector<vector<size_t> > u {{1,2,3}};
vector<vector<size_t> > v {{4,5,6}};
splice(u, std::move(v));
splice(u, v);
splice(u, u);
u // ... { { 1, 2, 3 }, { 4, 5, 6 }, { 1, 2, 3 }, {} }

(std::vector<std::vector<size_t> > &) { { 1, 2, 3 }, { 4, 5, 6 }, { 1, 2, 3 }, {} }

Insertion¶

Elements can be inserted at different positions in a vector using the std::insert method:

1
2
3
4
5
iterator insert( const_iterator pos, const T& value );
iterator insert( const_iterator pos, T&& value );
iterator insert( const_iterator pos, size_type count, const T& value );
template< class InputIt > iterator insert( const_iterator pos, InputIt first, InputIt last );
iterator insert( const_iterator pos, std::initializer_list<T> ilist );

%%cpp
vector<size_t> u {0,2,3};
auto it=u.insert(u.cbegin()+1, 1);
u

(std::vector<size_t> &) { 0, 1, 2, 3 }

After the insertion, the position/iterator of the inserted element is also returned.

%%cpp
cout << *it << " inserted.\n";
it

1 inserted.
(std::vector<unsigned long, std::allocator<unsigned long> >::iterator &) @0x7a00aa1b4018

Note that insertion takes linear time even if the element is inserted at the back. Why?

%%cpp
vector<size_t> u {0,2,3};
L(u[0]), L(u[1]), L(u[2]);
cout << *u.insert(u.cbegin()+1, 1) << " inserted.\n";
L(u[0]), L(u[1]), L(u[2]), L(u[3]);
u

(unsigned long &) u[0] @0x62a2f5377960
(unsigned long &) u[1] @0x62a2f5377968
(unsigned long &) u[2] @0x62a2f5377970
1 inserted.
(unsigned long &) u[0] @0x62a2f60a2bb0
(unsigned long &) u[1] @0x62a2f60a2bb8
(unsigned long &) u[2] @0x62a2f60a2bc0
(unsigned long &) u[3] @0x62a2f60a2bc8
(std::vector<size_t> &) { 0, 1, 2, 3 }

Observe that the locations of the elements are changed after insertion. In comparison, push_back normally does not change the locations of the existing elements:

%%cpp
u.push_back(4);
L(u[0]), L(u[1]), L(u[2]), L(u[3]), L(u[4]);

(unsigned long &) u[0] @0x62a2f60a2bb0
(unsigned long &) u[1] @0x62a2f60a2bb8
(unsigned long &) u[2] @0x62a2f60a2bc0
(unsigned long &) u[3] @0x62a2f60a2bc8
(unsigned long &) u[4] @0x62a2f60a2bd0

push_back has an amortized constant time complexity because existing elements need to be moved only when there is no more free memory at the back of the vector.

The following behaves like the fill constructors that fill the vector with multiple copies of the same value:

%%cpp
vector<size_t> u {1,2,3};
cout << format("Three {}'s added at the beginning.\n", *u.insert(u.cbegin(), 3, 0));
u

Three 0's added at the beginning.
(std::vector<size_t> &) { 0, 0, 0, 1, 2, 3 }

The following behaves like the initializer-list constructor:

%%cpp
vector<size_t> u {1,2,3};
for (auto it=u.insert(u.cend(), {4,5,6}); it!=u.cend(); it++)
    cout << format("{} added.\n", *it);
u

4 added.
5 added.
6 added.
(std::vector<size_t> &) { 1, 2, 3, 4, 5, 6 }

We can also insert a sublist from another list:

%%cpp
vector<size_t> u {1,2,3};
vector<double> v {4.1,5.2,6.3};
auto it=u.insert(u.cend(), v.cbegin(), v.cend()-1);
u

(std::vector<size_t> &) { 1, 2, 3, 4, 5 }

Note that elements are copied but not moved except when passed by rvalue reference:

iterator insert( const_iterator pos, T&& value );

%%cpp
vector<vector<size_t> > u {{1,2,3}};
vector<size_t> v {4,5,6};
u.insert(u.cbegin(), std::move(LB(v)));
LB(u[0]);
u.insert(u.cbegin(), v);
u

(std::vector<unsigned long>) v begin@0x62a2f61fe0e0
(std::vector<unsigned long> &) u[0] begin@0x62a2f61fe0e0
(std::vector<std::vector<size_t> > &) { {}, { 4, 5, 6 }, { 1, 2, 3 } }

%%cpp
template <class T>
typename vector<T>::iterator splice(vector<T> &u, typename vector<T>::const_iterator pos, const vector<T> &v) {
    /*
    ### BEGIN SOLUTION
    */
    return u.insert(pos, v.cbegin(), v.cend());
    /*
    ### END SOLUTION
    */
}

%%cpp
template <class T>
typename vector<T>::iterator splice(vector<T> &u, typename vector<T>::const_iterator pos, vector<T> &&v) {
    auto i = pos-u.cbegin();
    for (auto& vi : v) u.insert(pos++, std::move(vi));
    v.clear();
    return u.begin() + i;
}

%%cpp
// test
vector<vector<size_t> > u {{1,2,3}};
vector<vector<size_t> > v {{4,5,6}};
auto it=splice(u, u.cbegin()+1, std::move(v));
it=splice(u, it-1, v);
it=splice(u, it, u);
u // ... { { 1, 2, 3 }, { 4, 5, 6 }, { 1, 2, 3 }, { 4, 5, 6 } }

(std::vector<std::vector<size_t> > &) { { 1, 2, 3 }, { 4, 5, 6 }, { 1, 2, 3 }, { 4, 5, 6 } }

%%hermes
Explain briefly why typename is used in:
--
void splice(vector<T> &u, typename vector<T>::const_iterator pos, const vector<T> &v);

Hermes

Because inside a template, vector<T>::const_iterator is a dependent name — its meaning isn’t known until T is instantiated, so the compiler can’t tell whether it names a type. typename explicitly declares it as one. Without it (verified): error: 'std::vector<T, ...>::const_iterator' is not a type, and the whole function fails to compile; with it, the exact same code compiles and runs. (Since C++20 this keyword remains mandatory in such positions.)

Linked List¶

The splice function in Exercise 12 and Exercise 13 takes linear time as it inserts the elements of v to u one-by-one.

Can we concatenate two vectors more efficiently?

One idea is to link the end of one vector to the beginning of another. However, this isn’t possible because std::vector stores its elements in a single, contiguous block of memory. This design enables constant-time access via indexing, i.e., v[i] is equivalent to *(v + i), but it also means vectors cannot be physically joined without copying or reallocating their contents.

Program 2 uses another container std::list, which implements a doubly linked list data structure. Unlike std::vector, it takes constant time to insert or erase a single element anywhere in the std::list. Furthermore, using the splice method from std::list, two lists can be concatenated efficiently in constant time by modifying the end of one list to link to the beginning of another list:

1
2
3
4
5
6
void splice( const_iterator pos, list& other );
void splice( const_iterator pos, list&& other );
void splice( const_iterator pos, list& other, const_iterator it );
void splice( const_iterator pos, list&& other, const_iterator it );
void splice( const_iterator pos, list& other, const_iterator first, const_iterator last );
void splice( const_iterator pos, list&& other, const_iterator first, const_iterator last );

%%cpp
list<int> a{1,2,3}, b{4,5,6,7};
a.splice(a.cend(), b);
a

(std::list<int> &) { 1, 2, 3, 4, 5, 6, 7 }

All elements of b are now moved (not copied) to a:

%%cpp
b

(std::list<int> &) {}

However, these come at the cost of linear time lookup.

%%cpp
list<int> a{1,2,3,4,5,6,7};
// a[5];            // fails: type 'list' does not provide a subscript operator
auto it=a.cbegin();
// a.cbegin() + 5;  // fails: invalid operands to binary expression
for (auto i=5; i>0; i--) it++;  
// advance(it, 5) // more readible alternative that is equally inefficient
*it

(const int) 6

As another example, consider the problem of enumerating the permutations in combinatorics:

A simple way to generate permutations is by the following recurrence relation.

Proposition 3

A $k$ -permutation of $n$ satisfies the recurrence relation for $1\leq k \leq n$ :

Removing the first element of a $k$ -permutation of $n$ objects gives a different $(k-1)$ -permutation of the remaining $n-1$ objects.

(a_{i_0}, \underbrace{a_{i_1},\dots,a_{i_{k-1}}}_{\text{\scriptsize $(k-1)$-permutation of $a_{i_1},\dots,a_{i_{k-1}}$.}\kern-5em} )

(4)

Reversing the above removal process gives a way of constructing a $k$ -permutation from a $(k-1)$ -permutation.
E.g., the permutations of $1,2,3$ can be constructed as follows:

[\overbrace{({\color{red} 1}, {\color{blue}{2, 3}}), ({\color{red} 1}, {\color{blue}{3, 2}})}^{\text{\scriptsize prepend 1 to permutations of $2,3$.} }, \overbrace{({\color{red} 2}, {\color{blue}{1, 3}}), ({\color{red} 2}, {\color{blue}{3, 1}})}^{\text{\scriptsize prepend 2 to permutations of $1,3$.} }, \overbrace{({\color{red} 3}, {\color{blue}{1, 2}}), ({\color{red} 3}, {\color{blue}{2, 1}})}^{\text{\scriptsize prepend 3 to permutations of $1,2$.} }]

(5)

We can represent each permutation as a vector. The following implements the recursion:

%%cpp
void permutation_helper(const vector<size_t> &items, int k, 
                        vector<size_t> &current, 
                        vector<vector<size_t> > &result) {
    if (k == 0) result.push_back(current);
    else
        for (size_t i = 0; i < items.size(); ++i) {
            vector<size_t> remaining = items;
            remaining.erase(remaining.cbegin() + i);
            current.push_back(items[i]);
            permutation_helper(remaining, k - 1, current, result);
            current.pop_back();
        }
}

In the above function:

current keeps track of the beginning of the permutations to be built.
k is the number of elements that need to be appended to current to complete each desired permutation.
items is the remaining elements to choose from.
result is a vector to store all completed permutations.

Isn’t it more efficient to use std::list instead of std::vector for result?

No, because result is generated by appending current, which can be done in amortized constant time for std::vector.

The desired function that computes and returns the permutations can be a thin wrapper of the helper function:

%%cpp
std::vector<vector<size_t> > permutation(const vector<size_t> & items, int k) {
    vector<vector<size_t> > result;
    vector<size_t>  current;

    if (k >= 0 && k <= items.size()) {
        permutation_helper(items, k, current, result);
    }
    return result;
}

permutation(vector<size_t> {1,2,3}, 2)

(std::vector<std::vector<size_t> >) { { 1, 2 }, { 1, 3 }, { 2, 1 }, { 2, 3 }, { 3, 1 }, { 3, 2 } }

Why not check the range of

k

in the helper function instead?

This is because the check only needs to be done once. If it were placed inside the helper function, the check would be executed repeatedly in every recursive call.

To make $k$ an optional argument that defaults to $n$ :

%%cpp
std::vector<vector<size_t> > permutation(const vector<size_t> &items) {
    return permutation(items, items.size());  // default to full length
}

permutation(vector<size_t> {1,2,3})

(std::vector<std::vector<size_t> >) { { 1, 2, 3 }, { 1, 3, 2 }, { 2, 1, 3 }, { 2, 3, 1 }, { 3, 1, 2 }, { 3, 2, 1 } }

Why is it better to overload the function than to give a default argument to k?

items.size() is not available when defining the default value for k. Setting k to a value outside the valid range, say -1, is not ideal either because calling the function with k=-1 will no longer be regarded an invalid.

There is an inefficiency in the above program: Erasing an element from a vector is linear time, but removing an element from a list is constant time.

%%hermes
Explain briefly why `remaining.erase(it);` is more efficient if `remaining`
is a `std::list` instead of `std::vector`.

↻ Session: main (ACP: a2eadcad-290…)

Hermes

In permutation_helper, remaining is a fresh copy of items with position i removed. A std::vector erases by shifting every element after it one slot left — $O(n−i)$ element moves each time — while a std::list erases by unlinking a single node via its prev/next pointers: constant time, zero elements touched (verified with $n=8$ : vector shifts 6 elements when erasing position 1, 28 total over all positions; list moves none). Since the helper runs this erase once per recursive branch (exponentially many times), the $O(n)$ shifts dominate the runtime — which is exactly what cell 313 means by “erasing an element from a vector is linear time.”

The following implementation of permutation operates directly on a list. No helper function is needed, since list merging and element removal are efficient.

%%cpp
std::list<list<size_t> > permutation(const list<size_t> &items, int k) {
    list<list<size_t> > output;
    if (k == 0) {
        output.push_back(list<size_t> {});
    } else {
        list<size_t>  remaining = items;
        for (auto it = remaining.cbegin(); it != remaining.cend(); ++it) {
            auto i = *it;
            it=remaining.erase(it);
            list<list<size_t> > perm_seq = permutation(remaining, k - 1);
            it=remaining.insert(it, i);
            for (auto& perm : perm_seq) {
                perm.push_front(i);
            }
            output.splice(output.cend(), perm_seq);
        }
    }
    return output;
}

permutation(list<size_t> {1,2,3}, 2)

(std::list<std::list<size_t> >) { { 1, 2 }, { 1, 3 }, { 2, 1 }, { 2, 3 }, { 3, 1 }, { 3, 2 } }

%%cpp
std::list<list<size_t> > permutation(const list<size_t> &items) {
    return permutation(items, items.size());  // default to full length
}

permutation(list<size_t> {1,2,3})

(std::list<std::list<size_t> >) { { 1, 2, 3 }, { 1, 3, 2 }, { 2, 1, 3 }, { 2, 3, 1 }, { 3, 1, 2 }, { 3, 2, 1 } }

String¶

Matrix of Stars¶

Consider the following function matrix_of_stars to create a C-string of m rows and n columns of '*':

%%cpp
void matrix_of_stars(unsigned m, unsigned n, char s[]) {
    if (n) {
        for (auto i=0u; i<m; i++) {
            for (auto j=0u; j<n; j++) s[i*(n+1)+j]='*';
            s[i*(n+1)+n]='\n';
        }
        s[m*(n+1)]=0;
    } else s[0]=0;
}

const int m=3, n=2;         // constant size for static array
char s[m*(n+1)+1];
matrix_of_stars(m, n, s);   // pass `s` by reference to get stars
cout << s;

**
**
**

%%cpp
char* matrix_of_stars_(unsigned m, unsigned n) {
    auto s=new char[m*(n+1)+1];
    matrix_of_stars(m, n, s);
    return s;
}

int m=2, n=3; // non-constant size allowed.
auto s=matrix_of_stars_(m, n);
cout << s;
delete[] s;   // 😈: This line can be removed. 👨🏻‍🏫: No.
s = nullptr;

***
***

Solution to Exercise 14

There is a potential of memory leak if the programmer forgot to clean up the heap-allocated memory.

A safe way to return a string is to use std::string from <string>, which can be viewed as a special vector container whose elements are characters:

%%cpp
string matrix_of_stars(unsigned m, unsigned n) {
    string s;
    while(m--) s+=string(n,'*')+(n>0?"\n":"");
    return s;
}
cout << matrix_of_stars(3,2);

**
**
**

@interact(m=(0, 10), n=(0, 10))
def print_matrix_of_stars(m=5, n=5):
    print(ROOT.matrix_of_stars(m, n))

string(n,'*') uses the fill constructor to create n copies of *:

basic_string( size_type count, CharT ch, const Allocator& alloc = Allocator() );

s+=string(n,'*')+(n>0?"\n":""); uses
- the non-member operator + to concatenate strings, and
- the member operator = to assign the resulting string to s.

Exercise 15

Explain which of the following overloads was used in the above string concatenation.

 template< class CharT, class Traits, class Alloc >
 std::basic_string<CharT,Traits,Alloc>
     operator+( std::basic_string<CharT,Traits,Alloc>&& lhs,
                std::basic_string<CharT,Traits,Alloc>&& rhs );

template< class CharT, class Traits, class Alloc >
 std::basic_string<CharT,Traits,Alloc>
     operator+( std::basic_string<CharT,Traits,Alloc>&& lhs,
                CharT rhs );

template< class CharT, class Traits, class Alloc >
std::basic_string<CharT,Traits,Alloc>
    operator+( std::basic_string<CharT,Traits,Alloc>&& lhs,
               const CharT* rhs );

template< class CharT, class Traits, class Alloc >
 std::basic_string<CharT,Traits,Alloc>
     operator+( const std::basic_string<CharT,Traits,Alloc>& lhs,
                std::basic_string<CharT,Traits,Alloc>&& rhs );

Solution to Exercise 15

string(n,'*')+(n>0?"\n":""); uses Overload 3 since the rhs is a C-string which decays to CharT*.
The compound assignment s+=... boils down to s=s+..., which uses Overload 4.

%%hermes
Explain briefly the difference between member vs non-member function, and why
`operator+` is a non-member function of `std::string`?

Hermes

A member function belongs to a class and is called on its objects, with the implicit this as the first operand; a non-member (free) function is declared outside the class and takes all operands as regular parameters.

operator+ must be non-member because a member operator+ would fix the left operand to be the object itself (a + b calls a.operator+(b)), so it could never handle cases like the lecture’s string(n,'*') + (n>0?"\n":"") or "bar" + a, where the left operand is a const char*/array, not a std::string. A free function takes both operands as parameters, so overloads can cover any mix — string + string, string + C-string, C-string + string — which is exactly what cell 332’s solution distinguishes (verified: "bar" + a compiles only because a non-member overload exists; no member can be invoked on a non-string LHS).

Is the previous implementation of matrix_of_stars efficient? Compare it with the following implementation:

%%cpp
string matrix_of_stars(unsigned m, unsigned n) {
    if (m == 0 || n == 0) return "";
    string s, row(n, '*');
    row += '\n';
    s.reserve(m * row.size());
    for (unsigned i = 0; i < m; ++i)
        s.append(row);
    return s;
}
cout << matrix_of_stars(3,2);

**
**
**

s.reserve(m * s.size()); uses the method reserve to inform s about the planned change in size, so it can manage the storage more efficiently.
```
constexpr void reserve( size_type new_cap );
```
s.append(row) append row to s instead of re-assigning s to a new string:
```
basic_string& append( const basic_string& str );
```

Solution to Exercise 16

The second implementation is faster:

The second implementation checks n==0 once, while the first implementation checks n>0 repeatedly in a for loop.
The second implementation reserves sufficient space once, while the first implementation may need to reallocate memory for s if the string grows too long.
The second implementation uses append to add row instead of reassigning s.

Instead of using += or append, we can also use the output string stream std::ostringstream from <sstream>:

%%cpp
string matrix_of_stars(unsigned m, unsigned n) {
    if (m == 0 || n == 0) return "";
    ostringstream oss;
    string row(n, '*');
    row += '\n';
    for (unsigned i = 0; i < m; ++i)
        oss << row;
    return std::move(oss).str();
}
cout << matrix_of_stars(3,2);

**
**
**

<< appends row repeatedly to the output string stream oss.
std::move(oss).str() gives the content of the string:
```
std::basic_string<CharT, Traits, Allocator> str() &&;
```
The above method overload has an rvalue reference qualifier &&, which restricts it to be called only on rvalue objects. It enables the move semantics std::move(oss).str() to return the desired string without unnecessary copies, unlike the overload with constant lvalue reference qualifier:
```
std::basic_string<CharT, Traits, Allocator> str() const&;
```

Unlike std::string, std::ostringstream does not let us preallocate memory. It also incurs overhead for formatting, buffering, and type safety checks. Nevertheless, std::ostringstream makes it very easy to create a string from values of different data types.

%%cpp
string matrix_of(unsigned m, unsigned n, auto value) {
    if (m == 0 || n == 0) return "";
    ostringstream oss;
    /*
    ### BEGIN SOLUTION
    */
    while (n--) oss << value;
    oss << '\n';
    /*
    ### END SOLUTION
    */
    string row=oss.str();
    for (unsigned i = 1; i < m; ++i)
        oss << row;
    return std::move(oss).str();
}

%%cpp
cout << matrix_of(3,2,"cs2310");
/* Expected output:
cs2310cs2310
cs2310cs2310
cs2310cs2310
*/

cs2310cs2310
cs2310cs2310
cs2310cs2310

%%cpp
cout << matrix_of(3,2,.2310);
/* Expected output:
0.2310.231
0.2310.231
0.2310.231
*/

0.2310.231
0.2310.231
0.2310.231

Caesar Cipher¶

Consider implementing the Caesar Cipher, which is one of the oldest substitution cipher. It works by shifting each character of a given plaintext by a fixed number of positions down the alphabet, wrapping around from Z to A if necessary.

To encrypt a message in plaintext:

%%cpp
auto cc_encrypt=[](string plaintext, unsigned char key) {
    constexpr unsigned char s='A', n=26;
    for (auto &c: plaintext) c=((c-s+key)%n+n)%n + s;
    return plaintext;
};

auto ciphertext = cc_encrypt("ATTACKNOW", 13)

(std::string &) "NGGNPXABJ"

To decrypt the ciphertext:

%%cpp
auto cc_decrypt=[](string ciphertext, unsigned char key) {
    constexpr unsigned char s='A', n=26;
    for (auto &c: ciphertext) c=((c-s-key)%n+n)%n + s;
    return ciphertext;
};

cc_decrypt(ciphertext, 13)

(std::string) "ATTACKNOW"

Indeed, cc_decrypt can be implemented using cc_encrypt as follows, avoiding code duplication:

%%cpp
auto cc_decrypt(string ciphertext, unsigned char key) {
    constexpr unsigned char n=26;
    return cc_encrypt(ciphertext, n-key);
}

cc_decrypt(ciphertext, 13)

(std::string) "ATTACKNOW"

The downside is that ciphertext is passed by value to cc_decrypt, causing unnecessary copy. To fix this, we should pass the ciphertext by constant lvalue reference:

%%cpp
auto cc_decrypt=[](const string &ciphertext, const unsigned char key) {
    constexpr unsigned char n=26;
    return cc_encrypt(ciphertext, n-key);
};

cc_decrypt(ciphertext, 13)

(std::string) "ATTACKNOW"

%%cpp
auto cc_encrypt=[](const string &plaintext, const unsigned char key) {
    constexpr unsigned char s='A', n=26;
    /*
    ### BEGIN SOLUTION
    */
    string ciphertext(plaintext);
    for (auto &c: ciphertext) c=((c-s+key)%n+n)%n + s;
    return ciphertext;
    /*
    ### END SOLUTION
    */
};

auto ciphertext = cc_encrypt("ATTACKNOW", 13)

(std::string &) "NGGNPXABJ"

Unfortunately, decryption can fail as follows:

%%cpp
string plaintext{"Flee at Once!"};
unsigned char key=11;
cc_decrypt(cc_encrypt(plaintext, key), key)

(std::string) "FRKKTGZTOTIKU"

To ensure decryptability, we should preprocess the plaintext to

convert lower case letters to upper case letters, and
remove non-letters.

This can be done using tools from <cctype>:

%%cpp
string cc_process(const string &plaintext) {
    string processed;
    processed.reserve(plaintext.size());
    for (auto c: plaintext) if (isalpha(c)) processed+=toupper(c);
    return processed;   
}

string s("Flee at once!");
cc_process(s)

(std::string) "FLEEATONCE"

%%cpp
unsigned char key=11;
cc_decrypt(cc_encrypt(plaintext, key), key)

(std::string) "FRKKTGZTOTIKU"

It is a good idea to implement an overload that takes an rvalue reference to avoid unnecessary copies:

%%cpp
string cc_process(string &&plaintext) {
    auto it=plaintext.begin();
    for (auto c: plaintext) if (isalpha(c)) *(it++)=toupper(c);
    plaintext.erase(it, plaintext.end());
    return plaintext;
}

string s("Flee at once!");
LB(L(cc_process(std::move(LB(L(s))))))

(std::basic_string<char>) s @0x7a00ac49f000
(std::basic_string<char> &) L(s) begin@0x7a00ac49f010
(std::basic_string<char>) cc_process(std::move(LB(L(s)))) @0x7fff1e0d4cf0
(std::basic_string<char> &&) L(cc_process(std::move(LB(L(s))))) begin@0x7fff1e0d4d00
(std::basic_string) "FLEEATONCE"

Why aren’t the elements of s moved to t? Because plaintext is not returned by rvalue reference?

Consider a different plaintext:

%%cpp
string s("Flee immediately!");
LB(L(cc_process(std::move(LB(L(s))))))

(std::basic_string<char>) s @0x7a00ac49c000
(std::basic_string<char> &) L(s) begin@0x62a2f8679d00
(std::basic_string<char>) cc_process(std::move(LB(L(s)))) @0x7fff1e0d4cf0
(std::basic_string<char> &&) L(cc_process(std::move(LB(L(s))))) begin@0x62a2f8679d00
(std::basic_string) "FLEEIMMEDIATELY"

The elements of s are now moved to t. Let’s do it again:

Why elements are not moved sometimes?

The string returned by cc_process is indeed constructed using the move constructor on plaintext. However, even though a move constructor can transfer ownership of resources from plaintext, it is not required to do so. In the case of std::string, many implementations apply Small String Optimization (SSO), which stores short strings directly within the object’s internal buffer—a fixed-size array embedded in the object itself. This buffer is part of the object’s memory layout and avoids heap allocation for short strings, enabling faster access and reduced memory overhead.

The last example "**************" consists of 15 characters, which is regarded as a small string that is stored directly in the object’s internal buffer. This also applies to the shorter string "Flee at once!".
The previous example "***************" consists of 16 characters, which is not regarded as a small string.

%%hermes
Explain in a paragraph what small string optimization (SSO) is in C++, and 
how small is small?

Hermes

SSO (small string optimization) means std::string embeds a fixed-size character buffer directly inside the string object (the 32 bytes of sizeof(std::string) double as pointer/size/capacity header and inline buffer), so short strings are stored without any heap allocation — no malloc, no indirection; the string object itself carries its characters, making construction/copy of short strings cheap. Only when the text outgrows that inline buffer does the string allocate heap memory and point to it.

How small is small: implementation-defined (not fixed by the standard), but on this host’s libstdc++ (GCC 15) it is 15 characters (verified: sizeof(std::string) = 32 bytes; strings of length 1–15 keep their data inside the object with capacity 15, and at length 16 it switches to a heap allocation of capacity 16). This matches the notebook’s experiment: "****************" (16 stars) got its buffer moved/reallocated through cc_process while 15-character strings stayed in place. Typical thresholds elsewhere: libstdc++ 15, libc++ MSVC 15–16.

Alternatively, we can return the processed plaintext by rvalue reference:

%%cpp
using stringrvr=string&&;  // a kludge to bypass an issue of ROOT kernel

%%cpp
stringrvr cc_process(string &&plaintext) {
    auto it=plaintext.begin();
    for (auto c: plaintext) if (isalpha(c)) *(it++)=toupper(c);
    plaintext.erase(it, plaintext.end());
    return std::move(plaintext);
}

string s("Flee at once!");
LB(L(cc_process(std::move(LB(L(s))))))

(std::basic_string<char>) s @0x7a00ac499000
(std::basic_string<char> &) L(s) begin@0x7a00ac499010
(std::basic_string<char> &&) cc_process(std::move(LB(L(s)))) @0x7a00ac499000
(std::basic_string<char> &&) L(cc_process(std::move(LB(L(s))))) begin@0x7a00ac499010
(std::basic_string) "FLEEATONCE"

Solution to Exercise 19

No. std::move simply casts s to an rvalue reference. No constructors of std::string are invoked.

Counting Characters and Words¶

Consider counting the number of characters in a string. Recall the function std::strlen from <cstring>, which calculates the length of a C‑string:

%%cpp
auto s="😎";
strlen(s)

(unsigned long) 4

It fails to give the correct number of characters since 😎 is a unicode character encoded using multiple bytes. What if it is in a string container?

%%cpp
string s("😎");
s.size()

(unsigned long) 4

The size method still fails, but it works if we use a wide string std::wstring, which is a basic string std::basic_string<wchar_t> of wide characters wchar_t:

%%cpp
wstring s(L"😎");
s.size()

(unsigned long) 1

std::string is a basic string std::basic_string<char> of char. There are many other basic string types:

std::string                 std::basic_string<char>
std::wstring                std::basic_string<wchar_t>
std::u8string       (c++23) std::basic_string<char8_t>
std::u16string      (C++11) std::basic_string<char16_t>
std::u32string      (C++11) std::basic_string<char32_t>
std::pmr::string    (C++17) std::pmr::basic_string<char>
std::pmr::wstring   (C++17) std::pmr::basic_string<wchar_t>
std::pmr::u8string  (c++23) std::pmr::basic_string<char8_t>
std::pmr::u16string (C++17) std::pmr::basic_string<char16_t>
std::pmr::u32string (C++17) std::pmr::basic_string<char32_t>

Recall the recursion for counting words:

/**
 * @brief Counts the number of words in a string using tail recursion.
 *
 * A word is defined as a sequence of non-whitespace characters separated by whitespace.
 * This function uses tail recursion to traverse the string and count words efficiently.
 *
 * @param s The input C-style string to be processed.
 * @param i The current index in the string (default is 0).
 * @param c The current count of words found (default is 0).
 * @param w A flag indicating whether the previous character was whitespace (default is true).
 * @return The total number of words in the string.
 */
size_t count_words(const char *s,
                   const size_t i=0, const size_t c=0, const bool w=true) {
    bool t = isspace(s[i]); // Check if the current character is a whitespace
    return s[i] ? count_words(s, i + 1, c + (w && !t), t) : c;
}

How to make it work for different types of string?

%%cpp
template<typename CharT>
size_t count_words(const basic_string<CharT>& input) {
    const auto whitespace = basic_string<CharT>{CharT(' ')} +
        CharT('\t') + CharT('\n') + CharT('\r') + CharT('\v') + CharT('\f');

    size_t count=0, pos=0;
    while (true) {
        // Find the start of the next word
        pos = input.find_first_not_of(whitespace, pos);
        if (pos == basic_string<CharT>::npos) break;

        // Find the end of the word
        pos = input.find_first_of(whitespace, pos);
        ++count;
    }

    return count;
}

%%cpp
wstring s(L"😎:\nHello, World!");
count_words(s)

(unsigned long) 3

The above code uses template<typename CharT, typename Traits, typename Alloc> to make the function generic for any std::basic_string type. The function count_words first creates a string of common white space characters:

' '  (space)
'\t' (tab)
'\n' (newline)
'\r' (carriage return)
'\v' (vertical tab)
'\f' (form feed)

It then finds and count the next word iteratively using the search methods

find_first_not_of to find the next non-whitespace character to locate the start of a word;
```
size_type find_first_not_of( const basic_string& str, size_type pos = 0 ) const;
```
find_first_of to find the next whitespace character to locate the end of the word.
```
size_type find_first_of( const basic_string& str, size_type pos = 0 ) const;
```

npos is a constant (std::size_t(-1)) returned by the search methods if the search target is not found.

The code can be much simplified using an input string stream:

%%cpp
template<typename CharT>
size_t count_words(const basic_string<CharT>& input) {
    basic_istringstream<CharT> stream(input);
    basic_string<CharT> word;

    size_t count = 0;
    while (stream >> word) ++count;
    return count;
}

%%cpp
wstring s(L"😎:\nHello, World!");
count_words(s)

(unsigned long) 3

The idea is to turn the input string into an input stream basic_istringstream:

>> can be used to extract the next word from the stream to the string word; and
the count can be incremented for each successful extraction.

The returned stream (stream >> word) is contextually converted to a boolean value that evaluates to

true when the extract succeeded; and
false when the end of file or an error occurs.

%%hermes
Explain in a paragraph how `(stream >> word)` for `basic_istringstream` signals
successful extraction of a word?

Hermes

(stream >> word) returns the stream itself by reference (basic_istream&), not a boolean — so the signal travels two steps: on success the extraction stores word and leaves the stream’s internal state clean; on failure (no word left, as at end of input) it sets the failbit (and usually eofbit) in the stream’s state. The reference is then contextually converted to bool via operator!(), which reports whether any error bit — failbit, badbit, or eofbit — is set, so the loop condition while (stream >> word) reads true exactly when nothing went wrong. Verified on "a b": after extracting a, then b (eofbit set, good()=0 but no failbit → still true); the next extraction hits end-of-input, sets failbit+eofbit, and the stream converts to false — so the loop stops with exactly 2 words counted.

The function count_lines below uses an input string stream to count the number of lines instead of words of a string:

template< class CharT, class Traits, class Allocator >
std::basic_istream<CharT, Traits>&
    getline( std::basic_istream<CharT, Traits>& input,
             std::basic_string<CharT, Traits, Allocator>& str );

%%cpp
template<typename CharT>
size_t count_lines(const basic_string<CharT>& input) {
    basic_istringstream<CharT> stream(input);
    basic_string<CharT> line;
    size_t count = 0;
    while (getline(stream, line)) ++count;
    return count;
}

%%cpp
string s("😎:\nHello, World!");
count_lines(s)

(unsigned long) 2

The code uses the function std::getline from <string> to

read characters from stream up to a delimiter (default: \n);
store the extracted characters excluding the delimiter in line; and
return the reference to stream.

Stream¶

%%cpp
void input_int(int &x) {
    do {
        cout << "Enter an integer: ";
        cin.clear();
        cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
    } while (!(cin >> x));
}

// test
istringstream fake_input{"Hello, World!\n123 456\n"};
cin.rdbuf(fake_input.rdbuf());
int x;
input_int(x);
cout << format("\nYou entered {}.\n", x);

Enter an integer: 
You entered 123.

Solution to Exercise 20

The improved function keeps asking user for input unless the user enters an integer as the first word, which is then assigned to x.

In the above code

cin.clear() uses the method
```
void clear( std::ios_base::iostate state = std::ios_base::goodbit );
```
from basic_ios to reset the stream’s error flags to allow the next read attempt to proceed.
cin.ignore
```
basic_istream& ignore( std::streamsize count = 1, int_type delim = Traits::eof() );
```
from basic_istream to discard a number count of characters from the input stream until and including the delimiter delim.

Why can cin uses method from different classes?

cin is an instance of std::istream, or more explicitly std::basic_istream<char>:

template<
    class CharT,
    class Traits = std::char_traits<CharT>
> class basic_istream : virtual public std::basic_ios<CharT, Traits>

This is a subclass derived from the superclass std::basic_ios and therefore inherits the method clear of the superclass.

%%hermes
Explain in a paragraph the idea of inheritance in C++.

Hermes

Inheritance lets a class (derived/subclass) acquire the members — data and methods — of another class (base/superclass) by naming it in its declaration, e.g. struct Derived : Base; the derived object is a base object, so it can be used wherever a base is expected, the base’s members are directly accessible, and the base subobject is constructed first before the derived part. The derived class may then override virtual base methods to change behavior, and because virtual calls dispatch on the dynamic type of the object, even a call through a base reference runs the derived version — exactly the pattern in this lecture: std::cin is a basic_istream<char>, which derives (virtually) from basic_ios<char>, so cin.clear() works because clear is inherited from the superclass. Verified: with Derived : Base overriding show(), both d.show() and b.show() (via const Base& b = d) print the Derived version, while b.x reads the inherited member.

Instead of writing to the standard output, we can write to files using output file stream std::ofstream from <fstream>:

%%cpp
std::ofstream file("private/hello.txt");
if (file.good()) {
    file << "😎:\n";
    file << "Hello, World!\n";
}
file.close();

!cat private/hello.txt

😎:
Hello, World!

The code used

file.good()
```
bool good() const;
```
which returns true if the stream error flags are all false, i.e., the most recent I/O operation completed successfully; and
file.close()
```
void close();
```
which closes the file, which ensures the data is written to disk immediately instead of when file goes out of scope.

%%cpp
string line;

ifstream file("private/hello.txt");
/*
### BEGIN SOLUTION
*/
while (getline(file, line)) cout << line << '\n';
/*
### END SOLUTION
*/
file.close();

😎:
Hello, World!