Containers

The previous lesson, Non-Copyable and Non-Movable Types, showed a class deciding for itself, by writing its own move constructor, what empty state it leaves a moved-from source in — Handle‘s id became -1 because the move constructor was written that way. This lesson turns to the standard library’s ready-made containers and asks the same question of a read this time: writing stock["pear"] looks like reading a value. But if the key "pear" is not in the map, what does this line leave in the source?

Reading with operator[] Is Actually Writing

std::map<std::string, int>::operator[] returns the value bound to a key that is already in the map. If the key is absent, it does something different: it inserts a new element with a zero-initialized value and returns a reference to that element. This is a side effect that its signature does not reveal — the square brackets of [] read as “query” to most programmers, but for map they mean “get it if it is there, build it if it is not.”

// container-read.cpp — does reading with operator[] insert into the map
#include <cstdio>
#include <map>
#include <string>

int main() {
    std::map<std::string, int> stock{{"apple", 4}};
    std::size_t before = stock.size();

    int count = stock["pear"];
    (void)count;

    std::printf("element count changed %s\n",
        (stock.size() != before) ? "yes" : "no");
    std::printf("pear value %d\n", stock["pear"]);
    return 0;
}

element count changed yes
pear value 0

SL1. The call stock["pear"] changed the map while "pear" was absent from it: the element count went up by one, and the new element’s value became 0, int’s default value. The value assigned to count looks like a read, but that read itself wrote into the map. The kind of this expression is changed — the source still carries a value and the standard states it (not an empty map, but a one-element map), but the value differs from what it was before the operation.

find and contains: Asking the Same Question Without Inserting

There are two ways to learn whether a key is in the map that do not call operator[]. find returns an iterator to the element if it finds the key, or end() if it does not — it never inserts an element in either case. contains, a C++20 addition, is the more direct route; it returns only a bool.

// container-query.cpp — do find and contains change the container
#include <cstdio>
#include <map>
#include <string>

int main() {
    std::map<std::string, int> stock{{"apple", 4}};
    auto before = stock;

    auto it = stock.find("pear");
    bool present = stock.contains("cherry");

    std::printf("find result %s\n", (it == stock.end()) ? "not found" : "found");
    std::printf("contains result %s\n", present ? "yes" : "no");
    std::printf("map changed %s\n", (stock != before) ? "yes" : "no");
    return 0;
}

find result not found
contains result no
map changed no

SL2. find("pear") and contains("cherry") both queried keys that were not in the map, and both left the map unchanged: stock still equals its pre-operation copy. The end() iterator that find returns is a way of saying “not here,” not a trigger for insertion. Code that only wants to check whether a key exists in a map should use find or contains instead of operator[] — otherwise the query changes the structure it is querying.

Container Families and the Criterion for Choosing

The standard library’s containers fall into three families. Sequence containers (vector, deque, list, array) take an element’s position from the order it was inserted in — “sequence” here does not mean sorted by size, an element’s place is wherever the programmer put it. vector sits in contiguous memory, and appending at the end is amortized constant time; access at an index is constant time. list is a doubly linked list; inserting in the middle is constant time, but there is no indexed access, only traversal from the start.

Associative containers (map, set) keep elements ordered by a key; they are typically implemented as a balanced binary search tree, and search, insertion and deletion are O(log n). Unordered containers (unordered_map, unordered_set) keep elements in a hash table; search and insertion are O(1) on average, but fall to O(n) in the worst case if every element lands in the same bucket. The choice depends on which operation happens often: ordered traversal that runs often calls for map; fast lookup where order does not matter calls for unordered_map.

// family-choice.cpp — reading from a sequence, associative and unordered container
#include <cstdio>
#include <map>
#include <unordered_map>
#include <vector>

int main() {
    std::vector<int> sequence{30, 10, 20};
    std::map<int, int> associative{{1, 10}, {2, 20}};
    std::unordered_map<int, int> unordered{{1, 10}, {2, 20}};

    std::printf("vector first element %d\n", sequence.front());
    std::printf("map smallest key %d\n", associative.begin()->first);
    std::printf("unordered_map lookup %d\n", unordered.at(1));
    return 0;
}

vector first element 30
map smallest key 1
unordered_map lookup 10

SL3. All three reads left a container unchanged: front(), the first read through an iterator, and at() none of them wrote to the source. The order unordered_map keeps its elements in was never queried here, and never will be — an unordered container’s traversal order is implementation-defined and this course never prints it. begin()->first on map gives 1 on every run because map is ordered by key; the same call on an unordered_map would not give a reliable result.

at(): Access with Bounds Checking

operator[] has one more problem: it cannot be used on a const map, because the possibility of inserting an element when the key is absent makes it a mutating operation. at() removes this problem — it never inserts an element when the key is absent, it throws std::out_of_range instead, and it can be used on a const map.

// at-access.cpp — what at() does with a key out of range
#include <cstdio>
#include <map>
#include <stdexcept>
#include <string>

int main() {
    const std::map<std::string, int> stock{{"apple", 4}};

    try {
        int value = stock.at("pear");
        (void)value;
        std::printf("caught no\n");
    } catch (const std::out_of_range&) {
        std::printf("caught yes\n");
    }

    std::printf("element count %zu\n", stock.size());
    return 0;
}

caught yes
element count 1

SL4. stock.at("pear") threw an exception, and this lesson printed only that it was caught — it did not print the exception’s what() text, because that text’s exact form depends on the library implementation and is not what this lesson measures. After the throw, stock’s element count is still 1: the map stayed unchanged. This is what makes at() safe to use on a const container — an out-of-range key request never changes the source at all, it only reports the request through an exception.

insert and emplace: The Rule of Not Touching an Existing Key

operator[] does not just insert an element and return it when the key is absent; if the key already exists, it overwrites the value. insert and emplace carry the opposite guarantee: if the key already exists, they change nothing, and they report through a bool that they did not touch the existing element.

// insert-emplace.cpp — does insert change the source when the key already exists
#include <cstdio>
#include <map>
#include <string>

int main() {
    std::map<std::string, int> stock{{"apple", 4}};

    auto result = stock.insert({"apple", 99});
    bool inserted = result.second;

    std::printf("inserted %s\n", inserted ? "yes" : "no");
    std::printf("apple value %d\n", stock.at("apple"));
    return 0;
}

inserted no
apple value 4

SL5. The call insert({"apple", 99}) ran while "apple" was already in the map, and result.second returned false — no insertion took place. The value of apple is still 4: the map stayed unchanged after this call, the value 99 was never written. This is a clear difference from operator[] as a baseline: had stock["apple"] = 99 been written, the value would have been overwritten unconditionally and the kind would have been changed. This rejecting behavior of insert is the reason code that only wants to fill a map when a key is missing chooses insert or emplace over operator[] — emplace carries the same guarantee, differing only in that it builds the element directly in the container’s memory instead of constructing a temporary object first.

The Complexity of erase Depends on the Container

Deleting an element does not do the same work in every container. std::vector::erase shifts every element after the deleted position one slot to the left — the closer the deleted position is to the start, the more elements get moved, and its complexity is O(n). std::list::erase holds no contiguous memory, so it does no shifting; it only updates the links of the deleted node’s neighbors, and its complexity is O(1). std::map::erase looks up by key and then removes a node from the tree, O(log n) overall.

// erase-complexity.cpp — does vector erase shift the remaining elements
#include <cstdio>
#include <vector>

int main() {
    std::vector<int> sequence{10, 20, 30, 40};

    sequence.erase(sequence.begin());

    std::printf("element count %zu\n", sequence.size());
    std::printf("first element %d\n", sequence.front());
    return 0;
}

element count 3
first element 20

SL6. sequence.erase(sequence.begin()) deleted the first element, and the remaining three shifted one slot to the left — front() now gives 20, which used to sit second. The source changed after this operation: not only did the element count drop by one, the remaining elements’ positions in memory changed too. Had the same call been made on a std::list, the outcome’s kind would still be changed — the element count would still drop by one — but no shifting would happen; the remaining elements’ addresses would stay fixed. Because this lesson’s classification (unchanged/changed/empty/unspecified) measures not how much work an operation does but what state it leaves the source in, these two erase calls on vector and list fall under the same kind; the complexity difference is a separate axis, and complexity and kind are weighed together when choosing, neither one substitutes for the other.

Out-of-Range Indexing: Undefined Behavior and Its Defined Counterpart

std::vector::operator[] never checks whether the index it is given is within the container’s bounds. The call sequence[10] is undefined behavior when sequence‘s size is 3: the runtime may produce a crash, may return a garbage value, or may “work” without any error — all three are equally possible, and this course shows none of them, because undefined behavior’s output is not defined by the standard and cannot be verified. std::vector::at() gives the same request a defined counterpart: it throws std::out_of_range if the index is out of range, and accesses the same element as operator[] if the index is in range. The difference is in performance — at() performs a bounds check on every call, operator[] does not — but that difference is a visible cost only for accesses within bounds; operator[]‘s being “free” for an out-of-range access comes at the price of the source’s resulting state now being undefined. at() is preferred everywhere an index’s validity cannot be guaranteed; in tight loops where the caller already guarantees the index’s validity, operator[]’s uninspected speed is accepted.

The Bounding Measurement

Writing stock["pear"] on const std::map<std::string, int>& stock does not compile: operator[] has a non-const overload only, and it cannot be called on a const object, because the operator’s body can insert an element when the key is absent — this conflicts with the const contract. The block below carries that line as a comment and shows, in its place, a version that does compile, one that reads a const map only through find, at and contains:

// const-map.cpp — why operator[] cannot be used on a const map
#include <cstdio>
#include <map>
#include <string>

int main() {
    const std::map<std::string, int> stock{{"apple", 4}};

    // The line below does not compile, because operator[] is not a const member:
    // int count = stock["pear"];

    auto it = stock.find("apple");
    std::printf("apple found %s\n", (it != stock.end()) ? "yes" : "no");
    std::printf("element count %zu\n", stock.size());
    return 0;
}

apple found yes
element count 1

The compiler’s rejecting this line is not a limitation, it is a guarantee: it enforces, at compile time, that a const map can only be queried, that no read can change it. The operation this lesson measures — a read with operator[] on a mutable map — does not carry this guarantee; the path that writes to the source is open, and the compiler does not close it.

Summary

• Reading a std::map with operator[] inserts a zero-initialized element when the key is absent; the kind of the operation this lesson measures is changed.
• find and contains never write to the map while searching for a key; the source stays unchanged.
• Sequence (vector, deque, list, array), associative (map, set) and unordered (unordered_map, unordered_set) containers carry different complexity guarantees (erase, for instance, is O(n) on vector, O(1) on list, O(log n) on map); but that difference does not affect the classification, all of them leave the source changed.
• insert and emplace write nothing when the key already exists — the source stays unchanged; writing with operator[] overwrites unconditionally, and the kind is changed.
• at() throws an exception when the key is absent and never changes the map, which is why it can be used on a const container too; by contrast, an operator[] call on a const map does not compile — the compiler closes off, from the start, a path that could change the source, through the const contract.
• vector::operator[] enters undefined behavior at an out-of-range index; vector::at() answers the same request with a defined exception — both go no further than reading the source, the only difference is whether the response to an out-of-range request is defined or not.

Next Step

This lesson measured what happens to a container as a whole. The next lesson brings the boundary down to a position inside a container: can an iterator still be read after the operation that deletes the element it points to, or does touching that position enter undefined behavior?