Ch21: STL & Ranges

TL;DR: STL Containers & Adaptors: C++ standard containers offer standardized contiguous arrays (vector, array), linked lists (list, forward_list), ordered/unordered trees and hashes (set, map), and LIFO/FIFO interface adaptors (stack, queue, priority_queue). | Unlike sequence containers (vector, list) which store elements by position, associative containers (map, set, and their unordered_ variants) store elements by key, giving fast lookup at the cost of no guaranteed insertion order (for the unordered_ family) or sorted order (for the ordered family).

⚡ Quick Reference

#include <iostream>
#include <vector>
#include <array>
#include <deque>
#include <list>
#include <forward_list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stack>
#include <queue>
#include <algorithm>
#include <ranges>

int main() {
    std::vector<int> v = {10, 20, 30};
    std::array<int, 3> arr = {1, 2, 3};

    auto start = v.begin();
    auto stop = v.end();

    std::deque<int> d = {1, 2};
    std::list<int> lst = {5, 6};
    std::forward_list<int> fl = {7, 8};

    std::set<int> s = {3, 1, 2};
    std::map<int, std::string> m = {{1, "one"}};

    std::ranges::sort(v);

    auto lazy_view = v | std::views::filter([](int x){ return x > 10; })
                       | std::views::transform([](int x){ return x * 2; });

    return 0;
}

Associative Containers

#include <iostream>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <string>

int main() {
    // std::map<K, V> - sorted by key (red-black tree), O(log n) operations
    std::map<std::string, int> ages;
    ages["Alice"] = 30;
    ages.insert({"Bob", 25});

    // .find() - returns iterator, or .end() if not found (never throws)
    if (auto it = ages.find("Alice"); it != ages.end()) {
        std::cout << it->first << " is " << it->second << '\n';
    }

    // .at() - throws std::out_of_range if key missing (vs operator[] which inserts a default)
    try {
        std::cout << ages.at("Charlie") << '\n';
    } catch (const std::out_of_range&) {
        std::cout << "Charlie not found\n";
    }

    // std::set<T> - sorted, unique elements only
    std::set<int> uniqueNums{5, 3, 5, 1, 3};   // duplicates silently dropped -> {1, 3, 5}

    // std::unordered_map<K, V> - hash table, O(1) average lookup, no ordering guarantee
    std::unordered_map<std::string, int> fastLookup;
    fastLookup["x"] = 1;

    // std::unordered_set<T> - hash table version of set
    std::unordered_set<int> fastUnique{5, 3, 5, 1};

    // Range-based iteration over a map yields key-value pairs
    for (const auto& [name, age] : ages) {
        std::cout << name << ": " << age << '\n';
    }

    return 0;
}

🧠 Core Concepts

• STL Containers & Adaptors: C++ standard containers offer standardized contiguous arrays (vector, array), linked lists (list, forward_list), ordered/unordered trees and hashes (set, map), and LIFO/FIFO interface adaptors (stack, queue, priority_queue).
• Ranges & Adaptor Views: C++20 ranges (std::ranges) replace iterator pairs with full container algorithms. Views (filter, transform, take, iota) provide lazy, zero-overhead compile-time pipelining via the | operator.
• Custom Iterator Protocols: Custom containers integrate with STL algorithms by defining five type aliases (iterator_category, value_type, difference_type, pointer, reference) and implementing dereference, increment, and comparison operators.
• Ordered vs Unordered: std::map/std::set maintain elements sorted by key (typically via a red-black tree), giving O(log n) operations and in-order iteration. std::unordered_map/std::unordered_set use a hash table for O(1) average-case operations but no ordering guarantee.
• Key Uniqueness: map/set/unordered_map/unordered_set all require unique keys — inserting a duplicate key is a no-op (the existing element stays). Use the multimap/multiset variants when duplicate keys are needed.
• operator[] vs .at(): operator[] on a map silently default-constructs and inserts a new element if the key doesn't exist — convenient but can hide bugs. .at() throws std::out_of_range instead, making missing-key bugs loud and catchable.
• Structured Bindings with Maps: Iterating a map yields std::pair<const Key, Value> elements; for (const auto& [key, value] : myMap) unpacks them cleanly (C++17 and later).

⚠️ Pitfalls (Quick Scan)

Mistake	Fix
Constructing vectors with braced initializer lists (e.g., vector<int>{20, 55}) to pre-size them	Use parentheses construction vector<int>(20, 55) for size-based initialization
Dereferencing or advancing iterators past the end() boundary	Always verify it != container.end() before dereferencing
Inserting or erasing elements from a vector while using active iterators	Re-evaluate iterator positions or assign returned iterators from insertion/deletion methods
Accessing missing keys in std::map using operator[]	Use .find() or .at() for read-only lookups, reserving operator[] for writes
Using std::copy or std::transform on unallocated destination containers	Pre-size destination containers or wrap the destination in std::back_inserter to grow dynamically
Providing a non-strict weak ordering comparator (e.g., <=) to std::sort	Always use strict inequality < (not <=) in custom sorting comparators
Failing to pair std::views::iota with a termination condition	Combine iota with a terminating adapter like std::views::take
Implementing a custom iterator post-increment without returning a copy	Create a temporary copy of the current state, increment, and return the temporary
Failing to define separate mutable and const custom iterator types	Implement a distinct ConstIterator class or use raw const T* pointers for const containers
Using operator[] to check if a key exists	This inserts a default-constructed value as a side effect — use .find() or .contains() instead
Expecting unordered_map iteration order to be stable/insertion order	No ordering guarantee at all — use std::map if order matters
Assuming duplicate insert overwrites the existing value	insert() is a no-op on duplicate keys — use operator[] or insert_or_assign() to overwrite
Using a mutable custom struct as a std::set element and mutating it	Mutating in place breaks the tree's sort invariant; erase and reinsert instead
Forgetting a hash specialization for custom types in unordered_map/unordered_set	Provide std::hash<T> specialization or a custom hasher, or compilation fails

📖 Full Details

Cause → Effect → Fix with timestamp (click to expand)

* **Constructing vectors with braced initializer lists (e.g., `vector{20, 55}`) to pre-size them** -> **Creates a vector containing exactly two elements (`20` and `55`) instead of `20` copies of `55`** -> **Use parentheses construction `vector(20, 55)` for size-based initialization (115:00)** * **Dereferencing or advancing iterators past the `end()` boundary** -> **Undefined behavior, crashes, or memory reading junk values** -> **Always verify `it != container.end()` before dereferencing (116:00)** * **Inserting or erasing elements from a `vector` while using active iterators** -> **Iterators pointing to elements at or after the mutation point are invalidated, causing logic bugs or crashes** -> **Re-evaluate iterator positions or assign returned iterators from insertion/deletion methods (120:00)** * **Accessing missing keys in `std::map` using `operator[]`** -> **Silently default-constructs and inserts the missing key, polluting map structures** -> **Use `.find()` or `.at()` for read-only lookups, reserving `operator[]` for writes (126:00)** * **Using `std::copy` or `std::transform` on unallocated destination containers** -> **Out-of-bounds memory writes, leading to undefined behavior or immediate program crashes** -> **Pre-size destination containers or wrap the destination in `std::back_inserter` to grow dynamically (134:00)** * **Providing a non-strict weak ordering comparator (e.g., `<=`) to `std::sort`** -> **Infinite loops, crash loops, or corrupted sort outputs** -> **Always use strict inequality `<` (not `<=`) in custom sorting comparators (137:00)** * **Failing to pair `std::views::iota` with a termination condition** -> **Creates an infinite loop that hangs the program during iteration** -> **Combine `iota` with a terminating adapter like `std::views::take` (145:00)** * **Implementing a custom iterator post-increment without returning a copy** -> **Changes the iterator state in place and returns void or wrong references, violating STL conventions** -> **Create a temporary copy of the current state, increment, and return the temporary (192:00)** * **Failing to define separate mutable and const custom iterator types** -> **Compile errors when accessing elements in const container context** -> **Implement a distinct `ConstIterator` class or use raw `const T*` pointers for const containers (194:00)** * **Using `operator[]` just to check whether a key exists** -> **A new element is silently default-constructed and inserted into the container as a side effect of the lookup, growing the container unintentionally and corrupting size-based logic** -> **Use `.find(key) != container.end()` or (C++20) `.contains(key)` for existence checks that don't mutate** * **Expecting `std::unordered_map` to preserve insertion order or produce stable iteration order across runs** -> **Hash table bucket layout can differ between runs, compilers, or after rehashing, so iteration order is effectively unspecified** -> **Use `std::map` (ordered by key) if any predictable order is required** * **Assuming `.insert()` overwrites an existing key's value** -> **`insert()` is a no-op when the key already exists — the original value silently remains unchanged** -> **Use `operator[]` to overwrite, or `.insert_or_assign()` (C++17) to make the intent explicit** * **Mutating an object stored in a `std::set` in place (e.g. via a non-const iterator hack)** -> **The tree's internal ordering invariant is violated since the tree was built assuming the key never changes after insertion, leading to undefined lookup behavior** -> **Erase the old element and insert a new one instead of mutating in place** * **Using a custom struct/class as the key of `unordered_map`/`unordered_set` without a hash function** -> **Compilation fails because the standard library has no default `std::hash` for arbitrary user types** -> **Provide a `std::hash` template specialization, or pass a custom hasher as the container's second template parameter**

📎 Repo Files

• 43.StlContainersAndIterators/43.2StdVector/main.cpp
• 43.StlContainersAndIterators/43.3StdArray/main.cpp
• 43.StlContainersAndIterators/43.4Iterators/main.cpp
• 43.StlContainersAndIterators/43.6ReverseIterators/main.cpp
• 43.StlContainersAndIterators/43.7ContantIterators/main.cpp
• 43.StlContainersAndIterators/43.9StdBeginStdEnd/main.cpp
• 44.ZoomingOnSTLContainers/44.2Deque/main.cpp
• 44.ZoomingOnSTLContainers/44.3ForwardList/main.cpp
• 44.ZoomingOnSTLContainers/44.4List/main.cpp
• 44.ZoomingOnSTLContainers/44.5Vector/main.cpp
• 44.ZoomingOnSTLContainers/44.6Array/main.cpp
• 44.ZoomingOnSTLContainers/44.8Pair/main.cpp
• 44.ZoomingOnSTLContainers/44.9Set/main.cpp
• 44.ZoomingOnSTLContainers/44.10Map/main.cpp
• 44.ZoomingOnSTLContainers/44.11MultisetMultimap/main.cpp
• 44.ZoomingOnSTLContainers/44.12UnorderedSetUnorderedMap/main.cpp
• 44.ZoomingOnSTLContainers/44.14Stack/main.cpp
• 44.ZoomingOnSTLContainers/44.15Queue/main.cpp
• 44.ZoomingOnSTLContainers/44.16PriorityQueue/main.cpp
• 45.StlAlgorithms/45.2AllOf/main.cpp
• 45.StlAlgorithms/45.3ForEach/main.cpp
• 45.StlAlgorithms/45.4.MaxEltMinElt/main.cpp
• 45.StlAlgorithms/45.5FindAndFindIf/main.cpp
• 45.StlAlgorithms/45.6Copy/main.cpp
• 45.StlAlgorithms/45.7Sort/main.cpp
• 45.StlAlgorithms/45.8Transform/main.cpp
• 46.RangesLibraryInCpp20/46.2RangeAlgorithms/main.cpp
• 46.RangesLibraryInCpp20/46.4Projections/main.cpp
• 46.RangesLibraryInCpp20/46.5ViewsAndRangeAdaptors/main.cpp
• 46.RangesLibraryInCpp20/46.6ViewCompositionAndPipeOperator/main.cpp
• 46.RangesLibraryInCpp20/46.7RangeFactories/main.cpp
• 47.BuildingIteratorsForCustomContainers/40.02.IteratorPowers/main.cpp
• 47.BuildingIteratorsForCustomContainers/40.04CustomInputIterator/main.cpp
• 47.BuildingIteratorsForCustomContainers/40.05CustomOutputIterator/main.cpp
• 47.BuildingIteratorsForCustomContainers/40.06CustomForwardIterator/main.cpp
• 47.BuildingIteratorsForCustomContainers/40.07CustomBidirectionalIteator/main.cpp
• 47.BuildingIteratorsForCustomContainers/40.08CustomRandomAccessIterator/main.cpp
• 47.BuildingIteratorsForCustomContainers/40.09CustomIteratorsWithViews/main.cpp
• 47.BuildingIteratorsForCustomContainers/40.10ConstantIterators/main.cpp
• 47.BuildingIteratorsForCustomContainers/40.11RawPointersAsIterators/main.cpp
• 47.BuildingIteratorsForCustomContainers/40.12WrappingIteratorsFromOtherContainers/main.cpp
• 43.StlContainersAndIterators/main.cpp
• 44.ZoomingOnSTLContainers/main.cpp