--- title: Containers source: 'https://academia.sh/en/courses/cpp-standard-library/containers' course: 'Resource Management and the Standard Library' language: en updated: '2026-09-26T03:02:47+00:00' license: 'CC BY-SA 4.0' objectives: - 'Measures that reading a std::map with operator[] inserts a zero-initialized element when the key is absent' - 'Shows that find and contains leave the same map unchanged' - 'Chooses among sequence, associative and unordered containers by complexity' - 'Explains why an operator[] call on a const map does not compile' --- # Containers The measurement of how a map's operator[] read inserts an element when the key is absent, and how find and contains leave the source unchanged. 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::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." ```cpp // container-read.cpp — does reading with operator[] insert into the map #include #include #include int main() { std::map 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; } ``` ```text 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`. ```cpp // container-query.cpp — do find and contains change the container #include #include #include int main() { std::map 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; } ``` ```text 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`. ```cpp // family-choice.cpp — reading from a sequence, associative and unordered container #include #include #include #include int main() { std::vector sequence{30, 10, 20}; std::map associative{{1, 10}, {2, 20}}; std::unordered_map 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; } ``` ```text 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. ```cpp // at-access.cpp — what at() does with a key out of range #include #include #include #include int main() { const std::map 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; } ``` ```text 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. ```cpp // insert-emplace.cpp — does insert change the source when the key already exists #include #include #include int main() { std::map 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; } ``` ```text 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. ```cpp // erase-complexity.cpp — does vector erase shift the remaining elements #include #include int main() { std::vector 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; } ``` ```text 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& 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`: ```cpp // const-map.cpp — why operator[] cannot be used on a const map #include #include #include int main() { const std::map 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; } ``` ```text 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?