Lesson 15: Pointers and Containers

Lesson 0015 — A Tour of C++, Chapter 15 (§15.1–§15.5)

C++ offers simple built-in low-level types to hold and refer to data: objects and arrays hold data; pointers and arrays refer to such data. But we need both more specialized and more general ways of holding and using data — the standard-library containers (Chapter 12) and iterators (§13.3) support general algorithms, and the abstractions in this chapter — resource-management pointers, span, "almost containers," and the alternative types — encapsulate built-in language types and are required to perform as well in time and space as correct uses of those types. There is nothing "magic" about them: we can design and implement our own smart pointers and specialized containers as needed, using the same techniques.

15.1 Introduction

The main commonality among the container and pointer abstractions is that their correct and efficient use requires encapsulation of data together with a set of functions to access and manipulate them. For example, pointers are very general and efficient abstractions of machine addresses, but using them correctly to represent ownership of resources has proven excessively difficult. So the standard library offers resource-management pointers — classes that encapsulate pointers and provide operations that simplify their correct use.

15.2 Pointers

The general notion of a pointer is something that allows us to refer to an object and to access it according to its type. A built-in pointer, such as int*, is an example but there are many more:

There can be more than one pointer pointing to an object. An owning pointer is one that is responsible for eventually deleting the object it refers to. A non-owning pointer (e.g., a T* or a span) can dangle — point to a location where an object has been deleted or gone out of scope. Reading or writing through a dangling pointer is one of the nastiest kinds of bugs: the result is technically undefined; in practice that often means accessing an object that happens to occupy the location — a read gets an arbitrary value, and a write scrambles an unrelated data structure. The best we can hope for is a crash; that's usually preferable to a wrong result.

The C++ Core Guidelines [CG] offer rules for avoiding this and advice for statically checking that it never happens. Approaches for avoiding pointer problems:

• Don't retain a pointer to a local object after the object goes out of scope. In particular, never return a pointer to a local object from a function or store a pointer of uncertain provenance in a long-lived data structure. Systematic use of containers and algorithms (Chapters 12, 13) often saves us from employing programming techniques that make it hard to avoid pointer problems.
• Use owning pointers to objects allocated on the free store.
• Pointers to static objects (e.g., global variables) can't dangle.
• Leave pointer arithmetic to the implementation of resource handles (such as vectors and unordered_maps).
• Remember that string_views and spans are kinds of non-owning pointers.

15.2.1 unique_ptr and shared_ptr

One of the key tasks of any nontrivial program is to manage resources — something that must be acquired and later (explicitly or implicitly) released. Examples are memory, locks, sockets, thread handles, and file handles. For a long-running program, failing to release a resource in a timely manner ("a leak") can cause serious performance degradation (§12.7) and possibly even a miserable crash. The standard-library components are designed not to leak resources; they rely on the basic language support for resource management using constructor/destructor pairs — RAII (§5.2.2) — which interacts correctly with error handling using exceptions. This is the technique behind the standard-library lock classes:

mutex m;                       // used to protect access to shared data
void f() {
    scoped_lock lck {m};        // acquire the mutex m
    // ... manipulate shared data ...
}   // lck's destructor releases the mutex on any exit (return, fall-off-end, or throw)

That handles objects defined in a scope. For objects allocated on the free store, <memory> provides two "smart pointers":

• unique_ptr represents unique ownership (its destructor destroys its object);
• shared_ptr represents shared ownership (the last shared pointer's destructor destroys the object).

void f(int i, int j) {          // X* vs. unique_ptr<X>
    X* p = new X;               // allocate a new X
    unique_ptr<X> sp {new X};   // allocate a new X and give its pointer to unique_ptr
    // ...
    if (i < 99) throw Z{};      // may throw an exception
    if (j < 77) return;         // may return "early"
    // ... use p and sp ...
    delete p;                   // destroy *p
}
// unique_ptr ensures its object is destroyed whichever way we exit f()
// — by throwing, returning, or falling off the end. (The simplest fix:
//   just use a local variable X x; and no pointer at all.)

When you really need the semantics of pointers, unique_ptr is a lightweight mechanism with no space or time overhead compared to correct use of a built-in pointer, and it passes free-store-allocated objects in and out of functions cleanly. A unique_ptr is a handle to an individual object (or an array) in much the same way that a vector is a handle to a sequence of objects: both control the lifetime of other objects (using RAII) and both rely on elimination of copying or on move semantics to make return simple and efficient (§6.2.2).

The shared_ptr is similar except that shared_ptrs are copied rather than moved; the shared_ptrs for an object share ownership, and the object is destroyed when the last of its shared_ptrs is destroyed. This provides a form of garbage collection that respects the destructor-based resource management of the memory-managed objects — neither cost free nor exorbitantly expensive, but it does make the lifetime of the shared object hard to predict. Use shared_ptr only if you actually need shared ownership.

Creating an object on the free store and then passing the pointer to it to a smart pointer is verbose and allows mistakes (forgetting to pass the pointer, or giving a pointer to something not on the free store to a shared_ptr). So <memory> provides make_shared() and make_unique():

struct S { int i; string s; double d; /* ... */ };
auto p1 = make_shared<S>(1, "Ankh Morpork", 4.65);   // p1 is a shared_ptr<S>
auto p2 = make_unique<S>(2, "Oz", 7.62);             // p2 is a unique_ptr<S>

Using make_shared() is not just more convenient than separately making an object with new and passing it to a shared_ptr — it is also notably more efficient, because it does not need a separate allocation for the use count essential to shared_ptr's implementation.

Given unique_ptr and shared_ptr, we can implement a complete "no naked new" policy (§5.2.2) for many programs. However, these smart pointers are still conceptually pointers and therefore only our second choice for resource management — after containers and other types that manage their resources at a higher conceptual level. In particular, shared_ptrs do not in themselves provide any rules for which of their owners can read and/or write the shared object: data races (§18.5) and other forms of confusion are not addressed simply by eliminating the resource management issues.

When do we use smart pointers rather than resource handles with operations designed specifically for the resource? "When we need pointer semantics":

• When we share an object, we need pointers (or references) to refer to it, so a shared_ptr becomes the obvious choice (unless there is an obvious single owner).
• When we refer to a polymorphic object in classical object-oriented code (§5.5), we need a pointer (or a reference) because we don't know the exact type of the object referred to (or even its size), so a unique_ptr becomes the obvious choice.
• A shared polymorphic object typically requires shared_ptrs.

We do not need a pointer to return a collection of objects from a function; a container that is a resource handle does that simply and efficiently by relying on copy elision (§3.4.2) and move semantics (§6.2.2).

15.2.2 span

Traditionally, range errors have been a major source of serious errors in C and C++ programs, leading to wrong results, crashes, and security problems. Containers (Chapter 12), algorithms (Chapter 13), and range-for have significantly reduced this problem, but more can be done. A key source of range errors: people pass pointers (raw or smart) and then rely on convention to know the number of elements pointed to. The best advice for code outside resource handles is to assume that at most one object is pointed to [CG: F.22], but without support that advice is unmanageable. A span gives access to a contiguous sequence of elements, stored in many ways (vectors, built-in arrays); like a pointer, a span does not own the elements it points to — in that it resembles a string_view and an STL pair of iterators.

void fpn(int* p, int n) {          // pointer + count: the count is only a convention
    for (int i = 0; i < n; ++i) p[i] = 0;
}
void use(int x) {
    int a[100];
    fpn(a, 100);       // OK
    fpn(a, 1000);      // oops, my finger slipped! (range error in fpn)
    fpn(a+10, 100);    // range error in fpn
    fpn(a, x);         // suspect, but looks innocent
}

void fs(span<int> p) {              // a span carries its size
    for (int& x : p) x = 0;
}
void use(int x) {
    int a[100];
    fs(a);             // implicitly creates a span<int>{a,100} — compiler computes the count
    fs(a, 1000);       // error: span expected
    fs({a+10, 100});   // a range error in fs — but now explicit
    fs({a, x});        // obviously suspect
}

The common case — creating a span directly from an array — is now safe (the compiler computes the element count) and notationally simple; in other cases the programmer has to explicitly compose a span, lowering the probability of mistakes and making error detection easier. Passing a span along from function to function is simpler than (pointer,count) interfaces and requires no extra checking. As for containers, when span is used for subscripting (e.g., r[i]), range checking is not done and an out-of-range access is undefined behavior — an implementation can implement that as range checking, but sadly few do; the original gsl::span from the Core Guidelines support library does.

15.3 Containers

The standard provides several containers that don't fit perfectly into the STL framework (Chapters 12, 13) — built-in arrays, array, and string are examples. "Almost containers" is not quite fair: they hold elements, so they are containers, but each has restrictions or added facilities that make them awkward in the context of the STL.

Why so many? They serve common but different (often overlapping) needs — if the standard library didn't provide them, many people would have to design and implement their own:

• pair and tuple are heterogeneous; all other containers are homogeneous (all elements the same type).
• array and tuple elements are contiguously allocated; list and map are linked structures.
• bitset and vector<bool> hold bits and access them through proxy objects; all others can hold a variety of types and access elements directly.
• basic_string requires its elements to be some form of character and to provide string manipulation (concatenation, locale-sensitive operations).
• valarray requires its elements to be numbers and to provide numerical operations.

No single container could serve all of these needs because some needs are contradictory: "ability to grow" vs. "guaranteed to be allocated in a fixed location," and "elements do not move when elements are added" vs. "contiguously allocated."

15.3.1 array

An array, defined in <array>, is a fixed-size sequence of elements of a given type, with the number of elements specified at compile time. It can be allocated with its elements on the stack, in an object, or in static storage, in the scope where it is defined. It is best understood as a built-in array with its size firmly attached, without implicit, potentially surprising conversions to pointer types, and with a few convenience functions. There is no overhead (time or space) compared to a built-in array. An array does not follow the "handle to elements" model of STL containers — it directly contains its elements, so it must be initialized by an initializer list:

array<int,3> a1 = {1,2,3};   // the number of initializers must be <= the size specified

void f(int n) {
    array<int> a0 = {1,2,3};            // error: size not specified
    array<string,n> a1 = {"John's", "Queens'"};   // error: size not a constant expression
    array<string,0> a2;                 // error: size must be positive
    array<2> a3 = {"John's", "Queens'"}; // error: element type not stated
}
// If you need the element count to be a variable, use vector.

When necessary, an array can be explicitly passed to a C-style function expecting a pointer via a.data() (there is no implicit conversion), while find(a, 777) uses it as a range in STL style. Why use array when vector is so much more flexible? An array is less flexible so it is simpler; occasionally there's a significant performance advantage to directly accessing elements allocated on the stack rather than allocating on the free store and accessing them indirectly through the vector handle. On the other hand, the stack is a limited resource (especially on some embedded systems), stack overflow is nasty, and some application areas (safety-critical real-time control) ban free store allocation (delete may lead to fragmentation, §12.7, or memory exhaustion, §4.3).

Why use array when we could use a built-in array? An array knows its size (so it works with standard-library algorithms), and it can be copied using =. But the main reason to prefer array is that it saves us from surprising and nasty conversions to pointers:

void h() {
    Circle a1[10];
    array<Circle,10> a2;
    // ...
    Shape* p1 = a1;   // OK: disaster waiting to happen
    Shape* p2 = a2;   // error: no conversion of array<Circle,10> to Shape* (Good!)
    p1[3].draw();     // disaster — wrong offset, since sizeof(Shape) < sizeof(Circle)
}

All standard containers provide this advantage over built-in arrays.

15.3.2 bitset

Aspects of a system, such as the state of an input stream, are often represented as a set of flags indicating binary conditions (good/bad, true/false, on/off). C++ supports small sets of flags efficiently through bitwise operations on integers (§1.4). Class bitset<N> generalizes this by providing operations on a sequence of N bits [0:N), where N is known at compile time. For sets of bits that don't fit into a long long int (often 64 bits), a bitset is much more convenient than using integers directly; for smaller sets, bitset is usually optimized. If you want to name the bits rather than number them, use a set (§12.5) or an enumeration (§2.4).

bitset<9> bs1 {"110001111"};
bitset<9> bs2 {0b1'1000'1111};          // binary literal using digit separators (§1.4)
bitset<9> bs3 = ~bs1;                   // complement: bs3 == "001110000"
bitset<9> bs4 = bs1 & bs3;              // all zeros
bitset<9> bs5 = bs1 << 2;               // shift left: bs5 == "000111100" (shifts in zeros)

void binary(int i) {
    bitset<8 * sizeof(int)> b = i;      // assume 8-bit byte (see also §17.7)
    cout << b.to_string() << '\n';      // write out the bits of i
}   // 123 gives: 00000000000000000000000001111011 (most significant bit leftmost)

to_ullong() and to_string() provide the inverse operations to the constructors; the bitset output operator is a simpler way to write the bits. A bitset offers many functions for using and manipulating sets of bits: all(), any(), none(), count(), flip().

15.3.3 pair

It is fairly common for a function to return two values. The simplest and often the best way is to define a struct for the purpose — e.g., a My_res { Entry* ptr; Error_code err; } returning a value and a success indicator. Encoding failure as the end iterator or a nullptr is more elegant but expresses just one kind of failure. Defining a named struct per pair of values works well and is quite readable with well-chosen names, but for large code bases it can lead to a proliferation of names and conventions, and it doesn't work well for generic code where consistent naming is essential. Consequently, the standard library provides pair (from <utility>) as general support for the "pair of values" use cases:

pair<Entry*, Error_code> complex_search(vector<Entry>& v, const string& s) { /* ... */ return {found, err}; }

void user(const string& s) {
    auto r = complex_search(entry_table, s);
    if (r.second != Error_code::good) { /* ... handle error ... */ }
    // ... use r.first ...
    // Or use structured binding (§3.4.5) to name the members:
    auto [ptr, success] = complex_search(entry_table, s);
    // ... use ptr and success ...
}

The members of pair are named first and second. The standard-library algorithm equal_range returns a pair of iterators specifying a subsequence meeting a predicate — e.g., searching a vector of Records sorted on "name" with a less lambda, then printing all equal records from [first,last). A pair provides operators, such as =, ==, and <, if its elements do. Type deduction makes it easy to create a pair without mentioning its type: pair p1 {v.begin(), 2}; (CTAD) or auto p2 = make_pair(v.begin(), 2); — both are pair<vector<string>::iterator, int>. When code doesn't need to be generic, a simple struct with named members often leads to more maintainable code.

15.3.4 tuple

The standard-library containers are homogeneous — all elements of a single type. Sometimes we want to treat a sequence of elements of different types as a single object: a heterogeneous container. pair is an example, but not all such sequences have just two elements; tuple generalizes pair to zero or more elements:

tuple t0 {};                                    // empty
tuple<string,int,double> t1 {"Shark",123,3.14}; // the type is explicitly specified
auto t2 = make_tuple(string{"Herring"},10,1.23); // the type is deduced to tuple<string,int,double>
tuple t3 {"Cod"s,20,9.99};                      // the type is deduced to tuple<string,int,double>

The elements of a tuple are independent; there is no invariant (§4.3) maintained among them — if you want an invariant, encapsulate the tuple in a class that enforces it. For a single, specific use, a simple struct is often ideal, but there are many generic uses where tuple's flexibility saves us from defining many structs — at the cost of no mnemonic names. Members are accessed through the get function template, taking the index as a template value argument (§7.2.2), which must be constant:

string fish = get<0>(t1);   // "Shark"
int count = get<1>(t1);     // 123
double price = get<2>(t1);  // 3.14
// An element of a tuple with a UNIQUE type can be named by its type:
auto fish2 = get<string>(t1);  // "Shark"
get<string>(t1) = "Tuna";      // get<> works for writing too
// And structured binding names all members at once:
auto [fish, count, price] = todays_catch();
cout << fish << ' ' << count << ' ' << price << '\n';

Index access is general, ugly, and somewhat error-prone; type-based access works only for unique types. Most uses of tuples are hidden in implementations of higher-level constructs — structured binding is typically backed by a tuple. The real strength of tuple: when you have to store or pass around an unknown number of elements of unknown types as an object. Explicitly iterating over a tuple's elements is a bit messy, requiring recursion and compile-time evaluation:

template <size_t N = 0, typename... Ts>   // variadic template (§8.4)
constexpr void print(tuple<Ts...> tup) {
    if constexpr (N < sizeof...(Ts)) {     // not yet at the end?
        cout << get<N>(tup) << ' ';        // print the Nth element
        print<N+1>(tup);                   // print the next element
    }
}
print(t2);   // Herring 10 1.23

Here sizeof...(Ts) gives the number of elements in Ts. Like pair, tuple provides operators such as =, ==, and < if its elements do; there are also conversions between a pair and a two-member tuple.

15.4 Alternatives

The standard offers three types to express alternatives, plus the built-in union:

These types offer related functionality, but unfortunately they don't offer a unified interface.

15.4.1 variant

A variant<A,B,C> is often a safer and more convenient alternative to explicitly using a union (§2.5). The simplest example: return either a value or an error code:

variant<string, Error_code> compose_message(istream& s) {
    string mess;
    // ... read from s and compose message ...
    if (no_problems) return mess;                 // return a string
    else return Error_code{some_problem};         // return an Error_code
}

auto m = compose_message(cin);
if (holds_alternative<string>(m)) {
    cout << get<string>(m);
} else {
    auto err = get<Error_code>(m);   // ... handle error ...
}

When you assign or initialize a variant with a value, it remembers the type of that value. This style appeals to some people who dislike exceptions (§4.4). A more interesting use: a simple compiler may need to distinguish different kinds of nodes with different representations:

using Node = variant<Expression, Statement, Declaration, Type>;
void check(Node* p) {
    if (holds_alternative<Expression>(*p)) { Expression& e = get<Expression>(*p); /* ... */ }
    else if (holds_alternative<Statement>(*p)) { Statement& s = get<Statement>(*p); /* ... */ }
    // ... Declaration and Type ...
}

This check-the-alternatives pattern is so common and relatively inefficient that it deserves direct support — visit():

void check(Node* p) {
    visit(overloaded {
        [](Expression& e) { /* ... */ },
        [](Statement& s) { /* ... */ },
        // ... Declaration and Type ...
    }, *p);
}

This is basically equivalent to a virtual function call, but potentially faster — and, as with all claims of performance, that "potentially faster" should be verified by measurements when performance is critical. The overloaded class is necessary and, strangely enough, not standard — a "piece of magic" that builds an overload set from a set of arguments (usually lambdas):

template<class... Ts> struct overloaded : Ts... {   // variadic template (§8.4)
    using Ts::operator()...;
};
template<class... Ts> overloaded(Ts...) -> overloaded<Ts...>;   // deduction guide

The "visitor" visit() then applies () to the overload object, which selects the most appropriate lambda according to the overload rules. A deduction guide is a mechanism for resolving subtle ambiguities, primarily for constructors of class templates in foundation libraries (§7.2.3). If we try to access a variant holding a different type from the expected one, bad_variant_access is thrown.

15.4.2 optional

An optional<A> can be seen as a special kind of variant (like a variant<A,nothing>) or as a generalization of the idea of an A* either pointing to an object or being nullptr. It is useful for functions that may or may not return an object:

optional<string> compose_message(istream& s) {
    string mess;
    // ... read from s and compose message ...
    if (no_problems) return mess;
    return {};                          // the empty optional
}
if (auto m = compose_message(cin)) cout << *m;   // note the dereference (*)
else { /* ... handle error ... */ }

Note the curious use of *: an optional is treated as a pointer to its object rather than the object itself. The optional equivalent to nullptr is the empty object, {}:

int sum(optional<int> a, optional<int> b) {
    int res = 0;
    if (a) res += *a;
    if (b) res += *b;
    return res;
}
int x = sum(17, 19);   // 36
int y = sum(17, {});   // 17
int z = sum({}, {});   // 0

If we try to access an optional that does not hold a value, the result is undefined — an exception is not thrown. Thus optional is not guaranteed type safe: return *a + *b; is "asking for trouble."

15.4.3 any

An any can hold an arbitrary type and know which type (if any) it holds — basically an unconstrained version of variant:

any compose_message(istream& s) {
    string mess;
    // ... read from s and compose message ...
    if (no_problems) return mess;   // return a string
    else return error_number;       // return an int
}

auto m = compose_message(cin);
string& s = any_cast<string>(m);    // assert the expected type
cout << s;

When you assign or initialize an any with a value, it remembers the type of that value; later we extract it by asserting the expected type. If we try to access an any holding a different type than the expected one, bad_any_access is thrown.

15.5 Advice

Here is a summary of the guidance from this chapter. All 24 items, with the section where each is introduced. The C++ Core Guidelines link each item to its recommended practice.

Retrieval Quiz

Notes

Primary source: Stroustrup, B. (2022). A Tour of C++, 3rd ed., Chapter 15: "Pointers and Containers." Addison-Wesley.
Reference: Chapter 1–12 Quick Reference & Glossary — keep it beside you while you study.
Recommended supplement: cppreference on std::unique_ptr, std::shared_ptr, std::span, and std::variant.

Questions? Ask your agent — your teacher — about anything unclear: when shared ownership is actually warranted, why span doesn't check ranges, or how visit compares to virtual calls. Follow-ups are expected, not optional.

Chapters

1. Lesson 1: The Basics (Ch. 1)
2. Lesson 2: User-Defined Types (Ch. 2)
3. Lesson 3: Separate Compilation (Ch. 3)
4. Lesson 4: Error Handling (Ch. 4)
5. Lesson 5: Classes (Ch. 5)
6. Lesson 6: Essential Operations (Ch. 6)
7. Lesson 7: Templates (Ch. 7)
8. Lesson 8: Concepts and Generic Programming (Ch. 8)
9. Lesson 9: Library Overview (Ch. 9)
10. Lesson 10: Strings and Regular Expressions (Ch. 10)
11. Lesson 11: Input and Output (Ch. 11)
12. Lesson 12: Containers (Ch. 12)
13. Lesson 13: Algorithms (Ch. 13)
14. Lesson 14: Ranges (Ch. 14)
15. Lesson 15: Pointers and Containers (Ch. 15 — this lesson)
16. Lesson 16: Utilities (Ch. 16)
17. Lesson 17: Numerics (Ch. 17)
18. Lesson 18: Concurrency (Ch. 18)
19. Lesson 19: History and Compatibility (Ch. 19)