Lesson 12: Containers

Lesson 0012 — A Tour of C++, Chapter 12 (§12.1–§12.9)

Most computing involves creating collections of values and then manipulating such collections. A class with the main purpose of holding objects is commonly called a container. This chapter tours the standard library's containers — vector, list, forward_list, map, unordered_map, and the rest — and shows how they're built: every container is a resource handle (RAII, §6.3) over elements it owns, templates over their element type (§7.2), and sequences exposing begin()/end() (§13.1). The choice of which container to use is a data-layout decision with measurable consequences.

12.1 Introduction

Providing suitable containers for a given task and supporting them with useful fundamental operations are important steps in the construction of any program. To illustrate, the chapter follows a phone-book program: a list of (name, number) pairs, where Entry (§11.5) holds one entry. Different containers make different aspects of that program "simple and obvious."

12.2 vector

The most useful standard-library container is vector: a sequence of elements of a given type, stored contiguously in memory. A typical implementation is a handle holding pointers to the first element, one-past-the-last element, and one-past-the-last allocated space (§13.1) — plus an allocator from which the vector acquires memory (default: new/delete, §12.7). With a slightly advanced technique, simple allocators need no stored data inside the vector object.

vector<Entry> phone_book = { {"David Hume",123456}, {"Karl Popper",234567}, {"Bertrand Arthur William Russell",345678} };

void print_book(const vector<Entry>& book) {
    for (int i = 0; i!=book.size(); ++i) cout << book[i] << '\n';   // subscripting
}
// or, since the elements form a range:
void print_book(const vector<Entry>& book) {
    for (const auto& x : book) cout << x << '\n';   // range-for (§1.7)
}

Indexing starts at 0; size() gives the number of elements. When defining a vector, we give it an initial size — and the initializer syntax matters:

vector<int> v1 = {1, 2, 3, 4};   // size is 4
vector<string> v2;                // size is 0
vector<Shape*> v3(23);            // size is 23; initial element value: nullptr
vector<double> v4(32, 9.9);       // size is 32; initial element value: 9.9

An explicit size is enclosed in ordinary parentheses; elements default to the element type's default value (nullptr for pointers, 0 for numbers) unless a second argument is given.

The initial size can be changed. The most useful operation is push_back(), which adds a new element at the end, increasing the size by one — e.g., for (Entry e; cin>>e; ) phone_book.push_back(e);. The standard-library vector is implemented so that growing by repeated push_back()s is efficient:

template<typename T> class Vector {
    allocator<T> alloc;   // standard-library allocator of space for Ts
    T* elem;              // pointer to first element
    T* space;             // pointer to first unused (and uninitialized) slot
    T* last;              // pointer to last slot
public:
    int size() const     { return space-elem; }   // number of elements
    int capacity() const { return last-elem; }    // number of slots available for elements
    void reserve(int newsz);   // increase capacity() to newsz
    void push_back(const T& t);  // copy t into Vector
    void push_back(T&& t);      // move t into Vector
};

template<typename T> void Vector<T>::push_back(const T& t) {
    if (capacity()<=size())               // make sure we have space for t
        reserve(size()==0 ? 8 : 2*size()); // double the capacity
    construct_at(space, t);               // initialize *space to t ("place t at space")
    ++space;
}

Allocation and relocation happen only infrequently (amortized O(1) per push_back). Stroustrup's note on reserve(): he used to call it for performance, "but that turned out to be a waste of effort: the heuristic used by vector is on average better than my guesses." He now only uses reserve() explicitly to avoid reallocation of elements when he wants to use pointers to elements — because when reserve() moves elements to a new, larger allocation, any pointers to those elements are invalidated and must not be used.

A vector can be copied in assignments and initializations (vector<Entry> book2 = phone_book;) — implemented by the copy constructors/assignment operators of §6.2, and assigning copies every element. For a vector holding many elements, innocent-looking assignments can be expensive: use references or pointers, or move operations (§6.2.2), where copying is undesirable. The standard-library vector is very flexible and efficient — use it as your default container, unless you have a solid reason to use another. "If you avoid vector because of vague concerns about 'efficiency,' measure. Our intuition is most fallible in matters of the performance of container uses."

12.2.1 Elements

Just about any type qualifies as an element type: built-in numeric types, user-defined types (string, Entry, list<int>, Matrix<double,2>), and pointers. When you insert a new element, its value is copied into the container — the element is not a reference or a pointer to some other object. This makes for compact containers with fast access. Crucially:

vector<Shape> vs;                      // No, don't — no room for a Circle or a Smiley (§5.5)
vector<Shape*> vps;                   // better, but see §5.5.3 (don't leak)
vector<unique_ptr<Shape>> vups;       // OK

If you have a class hierarchy relying on virtual functions for polymorphic behavior, do not store objects directly in a container — slicing would discard derived parts. Store a pointer (or a smart pointer, §15.2.1).

12.2.2 Range Checking

The standard-library vector does not guarantee range checking: book[book.size()] compiles, and "is likely to place some random value in i rather than giving an error." Out-of-range errors are common, so Stroustrup often uses a range-checking adaptation:

template<typename T> struct Vec : std::vector<T> {
    using vector<T>::vector;   // use the constructors from vector (under the name Vec)
    T& operator[](int i) { return vector<T>::at(i); }          // range check
    const T& operator[](int i) const { return vector<T>::at(i); }  // range check const objects
    // begin()/end() return checked iterators (see §13.1)
};

void checked(Vec<Entry>& book) {
    try { book[book.size()] = {"Joe",999999}; }   // will throw out_of_range
    catch (out_of_range&) { cerr << "range error\n"; }
}

at() throws out_of_range (§4.2). If the user doesn't catch an exception, the program terminates in a well-defined manner rather than proceeding or failing in an undefined manner. One way to minimize surprises is a main() with a try-block as its body, providing default handlers that print to cerr. Why doesn't the standard guarantee range checking? Because many performance-critical applications use vectors and checking all subscripting implies a cost on the order of 10% — an overhead that can lead people to prefer the far more unsafe built-in arrays. A range-for avoids range errors at no cost by implicitly accessing all elements in the range; the standard-library algorithms do the same as long as their arguments are valid. If you use vector::at() directly, you don't need the Vec workaround.

12.3 list

The standard library offers a doubly-linked list called list — for sequences where we want to insert and delete elements without moving other elements (insertion and deletion of phone book entries could be common). With a linked list we tend not to use subscripting; we search:

int get_number(const string& s) {
    for (const auto& x : phone_book)
        if (x.name==s) return x.number;
    return 0;   // use 0 to represent "number not found"
}
// equivalently, with explicit iterators:
int get_number(const string& s) {
    for (auto p = phone_book.begin(); p!=phone_book.end(); ++p)
        if (p->name==s) return p->number;   // p->m is (*p).m
    return 0;
}

Every standard-library container provides begin() and end(), returning iterators to the first and to one-past-the-last elements — the range-for is roughly what the compiler expands the explicit loop into. Insertion and removal are easy:

phone_book.insert(p, ee);   // add ee before the element referred to by p (p may be end())
phone_book.erase(q);        // remove the element referred to by q and destroy it

These list examples could be written identically using vector and, "surprisingly, unless you understand machine architecture," often perform better with a vector. A vector performs better for traversal (find(), count()) and for sorting and searching (sort(), equal_range()). Unless you have a reason not to, use a vector.

12.4 forward_list

The standard library also offers a singly-linked list called forward_list. It differs from a doubly-linked list by only allowing forward iteration — the point is to save space: no predecessor pointer in each link, and the size of an empty forward_list is just one pointer. It doesn't even keep its number of elements: "If you need the number of elements, count. If you can't afford to count, you probably shouldn't use a forward_list."

12.5 map

Writing code to look up a name in a list of (name,number) pairs is tedious, and linear search is inefficient for all but the shortest lists. The standard library offers a balanced binary search tree (usually a red-black tree) called map — in other contexts known as an associative array or dictionary. A map is a container of pairs optimized for lookup and insertion:

map<string,int> phone_book { {"David Hume",123456}, {"Karl Popper",234567}, {"Bertrand Arthur William Russell",345678} };

int get_number(const string& s) { return phone_book[s]; }

When indexed by a value of its first type (the key), a map returns the corresponding value of the second type (the value or mapped type). Subscripting a map is essentially the lookup — with one crucial twist: if a key isn't found, it is entered into the map with a default value for its value. The default value for an integer type is 0, which conveniently represents an invalid telephone number here. If you want to avoid entering invalid numbers, use find() and insert() (§12.8) instead of [].

12.6 unordered_map

The cost of a map lookup is O(log(n)) — pretty good: for 1,000,000 elements, only about 20 comparisons and indirections. In many cases we can do better with a hashed lookup. The standard-library hashed containers are called "unordered" because they don't require an ordering function:

unordered_map<string,int> phone_book { {"David Hume",123456}, {"Karl Popper",234567}, {"Bertrand Arthur William Russell",345678} };
int get_number(const string& s) { return phone_book[s]; }   // like for a map

The standard library provides a default hash function for strings and other built-in and standard-library types; we can provide our own when needed — most commonly for an unordered container of one of our own types. A hash function is often implemented as a function object (§7.3.2):

struct Record { string name; int product_code; /* ... */ };

struct Rhash {   // a hash function for Record
    size_t operator()(const Record& r) const {
        return hash<string>()(r.name) ^ hash<int>()(r.product_code);
    }
};
unordered_set<Record,Rhash> my_set;   // set of Records using Rhash for lookup

Designing good hash functions is an art and often requires knowledge of the data. Creating a new hash by combining existing hashes with exclusive-or (^) is simple and often very effective — but be careful that every value taking part really helps distinguish values (combining the two hashes provides no benefit unless several names can share a product code or vice versa). We can avoid passing the hash operation explicitly by defining a specialization of the standard-library hash:

namespace std {
    template<> struct hash<Record> {
        using argument_type = Record;
        using result_type = size_t;
        result_type operator()(const Record& r) const {
            return hash<string>()(r.name) ^ hash<int>()(r.product_code);
        }
    };
}

The differences between a map and an unordered_map:

• A map requires an ordering function (default <) and yields an ordered sequence.
• An unordered_map requires an equality function (default ==) and does not maintain order among its elements.

Given a good hash function, an unordered_map is much faster than a map for large containers. However, the worst-case behavior of an unordered_map with a poor hash function is far worse than that of a map.

12.7 Allocators

By default, standard-library containers allocate space using new — a general free store holding objects of arbitrary size and user-controlled lifetime, implying time and space overheads that can be eliminated in many special cases. The containers therefore offer the opportunity to install allocators with specific semantics: pool allocators (performance), allocators that clean memory on deletion (security), per-thread allocation, and non-uniform memory architectures.

The motivating example: a long-running system used an event queue of vectors passed as shared_ptrs, logically simple and robust — but after 100,000 events had been passed among 16 producers and 4 consumers, more than 6GB of memory had been consumed due to fragmentation. The traditional solution is a pool allocator — one managing objects of a single fixed size, allocating space for many objects at a time rather than individually. C++ offers direct support via the pmr ("polymorphic memory resource") sub-namespace of std:

pmr::synchronized_pool_resource pool;   // make a pool
struct Event { vector<int> data = vector<int>{512, &pool}; };   // let Events use the pool
list<shared_ptr<Event>> q {&pool};                            // let q use the pool

void producer() {
    for (int n = 0; n!=LOTS; ++n) {
        scoped_lock lk {m};   // m is a mutex (§18.3)
        q.push_back(allocate_shared<Event, pmr::polymorphic_allocator<Event>>{&pool});
        cv.notify_one();      // cv is a condition_variable (§18.4)
    }
}

Now, after the same 100,000 events, less than 3MB had been consumed — about a 2000-fold improvement, with memory use stable over time so the system could run for months. (The amount of memory actually in use is unchanged; only the fragmentation waste is gone.) Other polymorphic memory resources: unsynchronized_polymorphic_resource (single-threaded only) and monotonic_polymorphic_resource (fast, releases memory only upon destruction, single-threaded). A polymorphic resource must derive from memory_resource and define allocate(), deallocate(), and is_equal() — users build their own resources to tune code.

12.8 Container Overview

The standard library provides some of the most general and useful container types:

The unordered containers are hash tables, optimized for lookup with a key (often a string). In addition, the standard library provides container adaptors — queue<T>, stack<T>, priority_queue<T> — and specialized container-like types such as array<T,N> (§15.3.1) and bitset<N> (§15.3.2).

The standard containers and their basic operations are designed to be similar notationally, with equivalent meanings: value_type, begin()/end(), size(), empty(), capacity(), c[k] / c.at(k), push_back(x), insert(p,x) / erase(p), assignment, and equality/lexicographical ordering (via <=>). This uniformity lets us write algorithms independently of individual container types — and to provide new container types used like the standard ones. Each has strengths and weaknesses: subscripting and traversing a vector is cheap, but vector elements move when we insert or remove; list has exactly the opposite properties. Note that a vector is usually more efficient than a list for short sequences of small elements — even for insert() and erase(). The singly-linked forward_list is optimized for the empty sequence: an empty forward_list occupies just one word, an empty vector three — and empty sequences, or sequences with only an element or two, are surprisingly common and useful.

An emplace operation takes arguments for an element's constructor and builds the object in a newly allocated space in the container, rather than copying an object in:

v.push_back(pair{1,"copy or move"});   // make a pair and move it into v
v.emplace_back(1,"build in place");     // build a pair in v directly

For simple examples, optimizations can result in equivalent performance for both calls.

12.9 Advice

Here is a summary of the guidance from this chapter. All 30 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 12: "Containers." Addison-Wesley.
Reference: Chapter 1–12 Quick Reference & Glossary — keep it beside you while you study.
Recommended supplement: cppreference on standard containers, std::vector, std::unordered_map, and polymorphic memory resources.

Questions? Ask your agent — your teacher — about anything unclear: when pointer invalidation bites, why [] on a map has a side effect, or how to sanity-check a hash function. 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 — this lesson)
13. Lesson 13: Algorithms (Ch. 13)
14. Lesson 14: Ranges (Ch. 14)
15. Lesson 15: Pointers and Containers (Ch. 15)
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)