C++ language mechanics and library internals.

This guide explains object lifetime, storage, ownership, value categories, keywords, generic and dynamic dispatch, concurrency, ranges, and standard-library container implementations. The separate pattern library develops algorithm families through recognition signals, invariants, tested C++ implementations, and grouped examples.

Objects, storage, and lifetime

Storage is a region of bytes. An object is an instance of a type whose lifetime has begun in some storage. The storage can exist before construction and after destruction. Access through a pointer or reference is valid only while the pointed-to object is alive and the access satisfies the type, alignment, and aliasing rules.

Lifetime versus storage duration

Lifetime describes when an object may be used. Storage duration describes how long its storage remains available. Construction starts lifetime. Destruction ends lifetime. These events can occur inside a longer storage-duration interval.

#include <cstddef>
#include <memory>

struct Packet {
    int sequence;
};

alignas(Packet) std::byte bytes[sizeof(Packet)]; // storage exists; no Packet yet

Packet* packet = std::construct_at(
    reinterpret_cast<Packet*>(bytes), Packet{42});
int sequence = packet->sequence;                 // lifetime is active

std::destroy_at(packet);                         // Packet lifetime ends
// packet->sequence would now have undefined behavior
// bytes still exists until the enclosing scope ends

Ordinary code should express this sequence through a container or smart pointer. Placement construction matters when implementing containers, allocators, variants, object pools, and shared-memory layouts.

Automatic, static, thread, and dynamic storage

“Stack” and “heap” describe common machine and allocator implementations. The C++ specification states storage-duration rules. Automatic objects may live entirely in registers, and an allocator may obtain dynamic storage from an arena, shared memory, or a fixed pool.

#include <memory>
#include <string>

std::string program_name = "telemetry"; // static storage duration
thread_local int messages_seen = 0;     // one object per thread

void consume() {
    int batch_size = 64;                // automatic storage duration
    auto buffer = std::make_unique<int[]>(batch_size);
                                            // dynamic array; owner is automatic
}                                           // unique_ptr releases the array

lvalue, xvalue, and prvalue

Every expression has a type and a value category. An lvalue identifies a persistent object or function. An xvalue identifies an object whose resources may be reused. A prvalue computes a value used to initialize an object or operand.

#include <string>
#include <utility>

void use(const std::string& text); // accepts lvalues and temporaries; reads
void use(std::string&& text);      // accepts xvalues and prvalues; may consume

std::string name = "radar";
use(name);                         // lvalue overload
use(std::move(name));              // xvalue overload
use(std::string{"camera"});        // prvalue binds to rvalue reference

// A named rvalue-reference variable is itself an lvalue expression.
void forward_to_use(std::string&& text) {
    use(text);                     // lvalue overload
    use(std::move(text));          // rvalue overload
}

What std::move does

std::move(value) performs a cast to an rvalue reference. The cast invokes no constructor and transfers no bytes. A later overload resolution may select a move constructor or move assignment operator because the expression is an xvalue.

#include <type_traits>
#include <utility>
#include <vector>

template<class T>
constexpr std::remove_reference_t<T>&& move_equivalent(T&& value) noexcept {
    return static_cast<std::remove_reference_t<T>&&>(value);
}

std::vector<int> source{1, 2, 3};
std::vector<int> destination = std::move(source);
// vector's move constructor normally transfers its allocation.
// source remains valid and may be assigned to, cleared, or destroyed.
// Its element count is unspecified by the general moved-from contract.

Move operations on integers and other trivially copyable values usually copy the value. Resource-owning types typically transfer a pointer or handle and place the source in a destructible state. Code should assign a new value before relying on a moved-from object's contents unless that type documents a stronger state.

Forwarding references and std::forward

In a deduced parameter of the form T&&, T becomes an lvalue-reference type when the caller passes an lvalue. Reference collapsing turns T& && into T&. For an rvalue argument, T is a non-reference type and the parameter remains T&&. std::forward<T>(value) reconstructs that original category at the next call.

#include <utility>

template<class Function, class... Args>
decltype(auto) invoke_preserving_categories(Function&& function,
                                            Args&&... args)
    noexcept(noexcept(
        std::forward<Function>(function)(
            std::forward<Args>(args)...))) {
    return std::forward<Function>(function)(
        std::forward<Args>(args)...);
}

The parameters have names, so each parameter expression is an lvalue inside the function. Forwarding applies the caller's category when passing them onward. Use it in forwarding wrappers and factories where the wrapper should preserve overload selection.

Copy elision and return-value optimization

Since C++17, a prvalue used to initialize an object can construct that object directly in its destination. The language requires this in cases such as return Widget{};. Named return value optimization, or NRVO, allows the same treatment for a named local returned by value. NRVO remains an optimization, although major compilers apply it in ordinary cases.

struct Image {
    Image(int width, int height);
    Image(const Image&);
    Image(Image&&) noexcept;
};

Image make_direct() {
    return Image{1920, 1080}; // guaranteed direct construction since C++17
}

Image make_named() {
    Image image{1920, 1080};
    return image;             // NRVO candidate
}

Image inhibit_nrvo() {
    Image image{1920, 1080};
    return std::move(image);  // forces an xvalue; usually requires a move
}

Returning an owning standard-library object by value is the normal interface. Direct construction, NRVO, and move construction cover the transfer efficiently. A manual std::move on the named return object commonly prevents NRVO.

Copying, ownership, and polymorphic destruction

Rule of Zero, Three, and Five

The Rule of Zero applies when every data member already implements the required ownership behavior. The compiler-generated destructor, copy operations, and move operations then compose those member operations correctly.

A class that directly manages a resource and declares a destructor, copy constructor, or copy assignment operator usually needs all three. C++11 adds the move constructor and move assignment operator, producing the Rule of Five. Direct resource management is mainly used to implement reusable ownership types. Application classes can usually use the Rule of Zero.

#include <string>
#include <vector>

class Recording {
public:
    Recording(std::string name, std::vector<float> samples)
        : name_(std::move(name)), samples_(std::move(samples)) {}

private:
    std::string name_;
    std::vector<float> samples_;
};

// Destructor, copy, and move operations are generated.
// string and vector already implement ownership correctly.

Deep and shallow copy

A shallow copy duplicates handle values. Copying a raw owning pointer this way makes two objects refer to the same allocation and often causes a double deletion. A deep copy allocates a distinct resource and copies the owned content. shared_ptr implements explicit shared ownership through a tracked control block.

#include <algorithm>
#include <cstddef>
#include <memory>

class Buffer {
public:
    explicit Buffer(std::size_t size)
        : size_(size), data_(std::make_unique<std::byte[]>(size)) {}

    Buffer(const Buffer& other) : Buffer(other.size_) {
        std::copy_n(other.data_.get(), size_, data_.get()); // deep copy
    }

    Buffer& operator=(const Buffer& other) {
        Buffer copy(other);
        swap(copy);                                         // strong guarantee
        return *this;
    }

    Buffer(Buffer&&) noexcept = default;
    Buffer& operator=(Buffer&&) noexcept = default;
    ~Buffer() = default;

    void swap(Buffer& other) noexcept {
        std::swap(size_, other.size_);
        data_.swap(other.data_);
    }

private:
    std::size_t size_{};
    std::unique_ptr<std::byte[]> data_;
};

unique_ptr, shared_ptr, and weak_ptr

#include <memory>
#include <vector>

struct Node {
    std::vector<std::shared_ptr<Node>> children;
    std::weak_ptr<Node> parent; // avoids a strong parent-child cycle
};

auto root = std::make_shared<Node>();
auto child = std::make_shared<Node>();
child->parent = root;
root->children.push_back(child);

if (auto parent = child->parent.lock()) {
    // parent is kept alive by this local shared_ptr
}

make_shared commonly places the object and control block in one allocation. The reference counts support safe ownership updates across threads. Access to the pointed-to object still needs its own synchronization when threads mutate it.

Virtual destructors and object slicing

Deleting a derived object through a base pointer requires a virtual base destructor. The virtual call reaches the derived destructor, then the base destructor runs. Without that virtual destructor, the deletion has undefined behavior.

Passing or assigning a derived object by value as its base type copies only the base subobject. The derived fields and dynamic type are sliced away. Polymorphic interfaces therefore pass base objects through references or pointers.

#include <memory>
#include <string>

struct Sensor {
    virtual ~Sensor() = default;
    virtual std::string read() const = 0;
};

struct Camera final : Sensor {
    std::string read() const override { return "frame"; }
    std::unique_ptr<int[]> pixels = std::make_unique<int[]>(1024);
};

std::string poll(const Sensor& sensor) { // reference preserves dynamic type
    return sensor.read();
}

std::unique_ptr<Sensor> sensor = std::make_unique<Camera>();
// Destroying sensor calls Camera::~Camera, then Sensor::~Sensor.

Virtual calls made during base construction or destruction dispatch to the currently constructed or destructed class, because the derived portion is outside its active lifetime at that point.

Templates, concepts, virtual dispatch, and variant

#include <concepts>
#include <string>
#include <variant>

template<class T>
concept HasArea = requires(const T& value) {
    { value.area() } -> std::convertible_to<double>;
};

template<HasArea T>
double area_of(const T& value) {
    return value.area();
}

struct Circle { double radius; };
struct Rectangle { double width, height; };
using Shape = std::variant<Circle, Rectangle>;

double area_of(const Shape& shape) {
    return std::visit([](const auto& value) -> double {
        using T = std::remove_cvref_t<decltype(value)>;
        if constexpr (std::same_as<T, Circle>) {
            return 3.141592653589793 * value.radius * value.radius;
        } else {
            return value.width * value.height;
        }
    }, shape);
}

Keywords and syntax that carry semantic weight

C++ keywords often change lifetime, overload resolution, constant evaluation, code generation, or the set of accepted programs. The examples below show the operation controlled by each keyword.

const, constexpr, consteval, and constinit

• const prevents mutation through that name or access path.
• constexpr permits compile-time evaluation when the arguments and executed operations satisfy constant-expression rules.
• consteval requires every potentially evaluated call to produce a constant expression.
• constinit requires static or thread-local initialization to occur statically. The object may remain mutable.

#include <array>
#include <cstddef>

constexpr int square(int value) {
    return value * value;
}

consteval std::size_t checked_extent(std::size_t value) {
    if (value == 0) {
        throw "extent must be positive"; // causes compile-time failure
    }
    return value;
}

constinit int process_counter = 0;       // static initialization; mutable later
constexpr auto buffer_size = checked_extent(256);
std::array<int, buffer_size> buffer{};

int runtime_input();
const int sample = runtime_input();      // read-only after runtime initialization
const int folded = square(12);           // compiler may constant-fold
constexpr int required = square(12);     // must be a constant expression

auto, decltype, and decltype(auto)

auto uses template-style deduction and usually drops top-level references and const. decltype(expression) inspects the declared type or the expression's type and value category. decltype(auto) applies the decltype rules to a return or variable declaration and can preserve a reference.

#include <vector>

const int count = 7;
auto copied = count;               // int
const auto& borrowed = count;      // const int&

std::vector<int> values{10, 20};

auto first_copy(std::vector<int>& input) {
    return input.front();           // int
}

decltype(auto) first_reference(std::vector<int>& input) {
    return (input.front());         // int&; parentheses make an lvalue expression
}

static_assert(std::is_same_v<decltype(values[0]), int&>);

explicit, override, final, and [[nodiscard]]

explicit blocks unintended implicit conversion through a constructor or conversion operator. override asks the compiler to verify that a virtual function overrides a base declaration. final prevents another override or derived class. [[nodiscard]] requests a diagnostic when a caller discards a result that represents required state.

#include <optional>

class FileDescriptor {
public:
    explicit FileDescriptor(int descriptor) : descriptor_(descriptor) {}
    explicit operator bool() const noexcept { return descriptor_ >= 0; }
private:
    int descriptor_;
};

struct Parser {
    virtual ~Parser() = default;
    [[nodiscard]] virtual std::optional<int> parse() = 0;
};

struct BinaryParser final : Parser {
    [[nodiscard]] std::optional<int> parse() override { return 42; }
};

typename, the template disambiguator, and dependent names

A name that depends on a template parameter cannot always be parsed before instantiation. Prefix a dependent nested type with typename. Prefix a dependent member template with template when the following angle bracket begins template arguments.

template<class Container>
auto first_or_default(const Container& input)
    -> typename Container::value_type {
    using Value = typename Container::value_type;
    return input.empty() ? Value{} : input.front();
}

template<class Registry>
void attach(Registry& registry) {
    registry.template add<int>(42);
    // "add" depends on Registry; template tells the parser how to read <int>.
}

requires, concepts, if constexpr, and static_assert

A requires-expression checks whether syntax and type requirements are valid. A concept gives that Boolean requirement a name. if constexpr discards the unselected branch during instantiation. static_assert rejects a translation when a compile-time condition is false.

#include <concepts>
#include <ranges>

template<class R>
concept NumericRange =
    std::ranges::input_range<R> &&
    std::integral<std::ranges::range_value_t<R>>;

template<NumericRange R>
long long sum(const R& range) {
    static_assert(sizeof(std::ranges::range_value_t<R>) <= sizeof(long long));
    long long result = 0;
    for (const auto value : range) {
        if constexpr (std::signed_integral<decltype(value)>) {
            result += value;
        } else {
            result += static_cast<long long>(value);
        }
    }
    return result;
}

Casts and less frequently used language controls

Exception guarantees and noexcept

A noexcept function promises that an exception will not escape. If one escapes, the runtime calls std::terminate. Standard containers use std::move_if_noexcept during reallocation so they can preserve the strong guarantee when copying is available and a move constructor may throw.

#include <type_traits>
#include <utility>
#include <vector>

template<class T>
void append_transactionally(std::vector<T>& destination,
                            const std::vector<T>& source) {
    auto next = destination;                 // may throw; original unchanged
    next.insert(next.end(), source.begin(), source.end());
    destination.swap(next);                  // noexcept for compatible allocators
}

template<class T>
void relocate(T* destination, T& source)
    noexcept(std::is_nothrow_move_constructible_v<T>) {
    std::construct_at(destination, std::move(source));
}

Destructors and cleanup paths should complete without throwing. Recovery code can then release partially constructed state during stack unwinding. Functions should declare noexcept when their implementation and called operations satisfy that contract.

Alignment, padding, locality, and false sharing

Every complete object has a size and an alignment requirement. A compiler inserts padding so that each member begins at a suitable address and each element of an array has the same alignment. Member order can therefore change sizeof.

#include <atomic>
#include <cstddef>
#include <new>

struct Mixed {
    char tag;       // offset 0
    double value;   // commonly offset 8 after 7 padding bytes
    int count;      // commonly offset 16
};                  // commonly 24 bytes after tail padding

struct PackedByOrder {
    double value;
    int count;
    char tag;
};                  // commonly 16 bytes

struct alignas(std::hardware_destructive_interference_size) WorkerCounter {
    std::atomic<std::size_t> value{0};
};

static_assert(offsetof(Mixed, value) % alignof(double) == 0);

Contiguous elements improve spatial locality because one cache-line fill supplies several neighboring values. Pointer-linked nodes can require a separate load for each traversal step. False sharing occurs when different threads write different objects that occupy one cache line. The coherence protocol then transfers ownership of that line between cores. Separating frequently written per-thread state with measured cache-line spacing removes that interaction at the cost of extra memory.

Standard containers and their common implementations

vector: one allocation and three positions

A typical vector<T> stores pointers to the start of allocated storage, one past the last live element, and one past the allocation. Size is finish - start. Capacity is end_of_storage - start. Elements between finish and end-of-storage have storage but no active T objects.

#include <algorithm>
#include <memory>
#include <utility>

template<class T>
struct VectorCore {
    T* start = nullptr;
    T* finish = nullptr;
    T* end_of_storage = nullptr;
    std::allocator<T> allocator;

    VectorCore() = default;
    VectorCore(const VectorCore&) = delete;
    VectorCore& operator=(const VectorCore&) = delete;

    std::size_t size() const {
        return start ? static_cast<std::size_t>(finish - start) : 0;
    }
    std::size_t capacity() const {
        return start ? static_cast<std::size_t>(end_of_storage - start) : 0;
    }

    void grow() {
        const std::size_t old_size = size();
        const std::size_t old_capacity = capacity();
        const std::size_t next_capacity =
            std::max<std::size_t>(1, old_capacity * 2);
        T* next = std::allocator_traits<decltype(allocator)>::allocate(
            allocator, next_capacity);
        T* next_finish = next;
        try {
            for (T* current = start; current != finish; ++current, ++next_finish) {
                std::construct_at(next_finish, std::move_if_noexcept(*current));
            }
        } catch (...) {
            std::destroy(next, next_finish);
            std::allocator_traits<decltype(allocator)>::deallocate(
                allocator, next, next_capacity);
            throw;
        }
        std::destroy(start, finish);
        if (start != nullptr) {
            std::allocator_traits<decltype(allocator)>::deallocate(
                allocator, start, old_capacity);
        }
        start = next;
        finish = next + old_size;
        end_of_storage = next + next_capacity;
    }

    ~VectorCore() {
        const std::size_t old_capacity = capacity();
        std::destroy(start, finish);
        if (start != nullptr) {
            std::allocator_traits<decltype(allocator)>::deallocate(
                allocator, start, old_capacity);
        }
    }
};

Growth allocates a larger region, move-constructs or copy-constructs the live elements, destroys the old elements, and releases the old allocation. Libraries choose their own growth factor. Geometric growth makes a sequence of push_back operations amortized constant time.

• Reallocation invalidates every pointer, reference, and iterator into the vector.
• Insertion without reallocation invalidates iterators and references at or after the insertion point.
• reserve(n) performs at most one planned reallocation before a known append workload.
• resize(n) changes the number of live elements. reserve(n) changes only capacity.

array and span: embedded storage and borrowed access

array<T, N> contains its elements inside the array object. A common implementation has one member equivalent to T elems[N], with a special representation for N == 0. Its size belongs to the type and it performs no dynamic allocation.

A dynamic-extent span<T> commonly stores a pointer and an element count. A fixed-extent span can encode the count in its type and store only the pointer. A span never creates, destroys, or owns the referenced elements.

#include <cstddef>

template<class T, std::size_t N>
struct ArrayLayout {
    T elements[N]; // production libraries specialize the N == 0 case
};

template<class T>
struct DynamicSpanLayout {
    T* data;
    std::size_t size;

    T& operator[](std::size_t index) const { return data[index]; }
    T* begin() const { return data; }
    T* end() const { return data + size; }
};

deque: a map of fixed-size blocks

Common deque implementations allocate fixed-size element blocks and maintain a small array of pointers to those blocks. An iterator carries a block-map position plus a pointer within the current block. Indexing divides the logical offset into a block number and an in-block offset.

#include <cstddef>
#include <memory>
#include <vector>

template<class T, std::size_t BlockElements = 64>
struct DequeLayout {
    std::vector<std::unique_ptr<T[]>> blocks;
    std::size_t first_offset = 0;
    std::size_t element_count = 0;

    T& at_unchecked(std::size_t index) {
        const std::size_t absolute = first_offset + index;
        const std::size_t block = absolute / BlockElements;
        const std::size_t offset = absolute % BlockElements;
        return blocks[block][offset];
    }
};

Spare positions at both ends allow constant-time end insertion until another block or a larger block map is needed. Existing elements stay in their blocks when the block map grows, which supports stronger reference stability than vector. Iterators still contain block-map state and have separate invalidation rules. Deque provides random access with an extra indirection and loses whole-range contiguity.

list: nodes linked through a sentinel

A typical list<T> is a circular doubly linked structure. A sentinel represents both end() and the connection between the first and last nodes. Each element resides in a separately allocated node containing forward and backward links.

struct ListLink {
    ListLink* next;
    ListLink* previous;
};

template<class T>
struct ListNode : ListLink {
    T value;
};

void link_before(ListLink* position, ListLink* node) {
    node->next = position;
    node->previous = position->previous;
    position->previous->next = node;
    position->previous = node;
}

void unlink(ListLink* node) {
    node->previous->next = node->next;
    node->next->previous = node->previous;
}

Relinking known nodes is constant time, which enables splice. Finding a position is linear. Per-element allocation, two link pointers, and pointer chasing make list traversal expensive on modern caches. Iterators and references to other nodes remain valid across insertion and erasure.

map: an ordered balanced search tree

libstdc++ implements map with a red-black tree. Other conforming libraries may choose another structure that satisfies ordered iteration and logarithmic search, insertion, and erasure. Each node stores parent, left, and right links, a balance marker, and a pair<const Key, Value>.

A red-black tree is a binary search tree with coloring constraints: the root is black, a red node has black children, and every path from a node to an empty descendant contains the same number of black nodes. These constraints keep the height within a constant factor of log₂(n). Rotations repair local shape while preserving in-order key order.

#include <utility>

enum class Color : unsigned char { red, black };

template<class Key, class Value>
struct TreeNode {
    TreeNode* parent = nullptr;
    TreeNode* left = nullptr;
    TreeNode* right = nullptr;
    Color color = Color::red;
    std::pair<const Key, Value> entry;
};

template<class Node>
void rotate_left(Node*& root, Node* pivot) {
    Node* promoted = pivot->right;
    pivot->right = promoted->left;
    if (promoted->left) promoted->left->parent = pivot;

    promoted->parent = pivot->parent;
    if (!pivot->parent) root = promoted;
    else if (pivot == pivot->parent->left) pivot->parent->left = promoted;
    else pivot->parent->right = promoted;

    promoted->left = pivot;
    pivot->parent = promoted;
}

template<class Node>
void rotate_right(Node*& root, Node* pivot) {
    Node* promoted = pivot->left;
    pivot->left = promoted->right;
    if (promoted->right) promoted->right->parent = pivot;

    promoted->parent = pivot->parent;
    if (!pivot->parent) root = promoted;
    else if (pivot == pivot->parent->right) pivot->parent->right = promoted;
    else pivot->parent->left = promoted;

    promoted->right = pivot;
    pivot->parent = promoted;
}

Insertion first follows the comparator exactly as an ordinary binary search tree. The new node begins red. If its parent is also red, the repair step either recolors a red uncle or rotates around a black uncle. The same cases repeat toward the root, which is finally colored black. Erasure has a corresponding repair for a removed black node.

template<class Node>
void repair_after_insert(Node*& root, Node* node) {
    while (node != root && node->parent->color == Color::red) {
        Node* parent = node->parent;
        Node* grandparent = parent->parent;

        if (parent == grandparent->left) {
            Node* uncle = grandparent->right;
            if (uncle && uncle->color == Color::red) {
                parent->color = Color::black;
                uncle->color = Color::black;
                grandparent->color = Color::red;
                node = grandparent;
            } else {
                if (node == parent->right) {
                    node = parent;
                    rotate_left(root, node);
                    parent = node->parent;
                    grandparent = parent->parent;
                }
                parent->color = Color::black;
                grandparent->color = Color::red;
                rotate_right(root, grandparent); // mirror of rotate_left
            }
        } else {
            Node* uncle = grandparent->left;
            if (uncle && uncle->color == Color::red) {
                parent->color = Color::black;
                uncle->color = Color::black;
                grandparent->color = Color::red;
                node = grandparent;
            } else {
                if (node == parent->left) {
                    node = parent;
                    rotate_right(root, node);
                    parent = node->parent;
                    grandparent = parent->parent;
                }
                parent->color = Color::black;
                grandparent->color = Color::red;
                rotate_left(root, grandparent);
            }
        }
    }
    root->color = Color::black;
}

This code covers both insertion-repair orientations. A complete container also supplies allocator-aware node construction, exception rollback, iterators, lookup, and the separate deletion repair algorithm.

unordered_map: buckets, hash codes, and equality

A common implementation uses a bucket array plus linked nodes. The hash function maps a key to a size_t. A range reduction operation maps that hash code to a bucket index. Lookup traverses the selected bucket and confirms matches with the key equality predicate. Hash equality is only a candidate test because different keys may collide.

#include <cstddef>
#include <functional>
#include <memory>
#include <utility>
#include <vector>

template<class Key, class Value, class Hash = std::hash<Key>,
         class Equal = std::equal_to<Key>>
class ChainedHashMapCore {
    struct Node {
        std::pair<const Key, Value> entry;
        std::unique_ptr<Node> next;
    };

    std::vector<std::unique_ptr<Node>> buckets_{16};
    std::size_t size_ = 0;
    Hash hash_;
    Equal equal_;

    std::size_t bucket_index(const Key& key) const {
        return hash_(key) % buckets_.size();
    }

    void rehash(std::size_t bucket_count) {
        std::vector<std::unique_ptr<Node>> next_buckets(bucket_count);
        for (auto& bucket : buckets_) {
            while (bucket) {
                auto node = std::move(bucket);
                bucket = std::move(node->next);
                const std::size_t next_index =
                    hash_(node->entry.first) % bucket_count;
                node->next = std::move(next_buckets[next_index]);
                next_buckets[next_index] = std::move(node);
            }
        }
        buckets_ = std::move(next_buckets);
    }

public:
    Value* find(const Key& key) {
        Node* node = buckets_[bucket_index(key)].get();
        while (node) {
            if (equal_(node->entry.first, key)) return &node->entry.second;
            node = node->next.get();
        }
        return nullptr;
    }

    bool insert(Key key, Value value) {
        if (find(key) != nullptr) return false;
        if ((size_ + 1) * 4 > buckets_.size() * 3) rehash(buckets_.size() * 2);
        const std::size_t bucket = bucket_index(key);
        auto node = std::make_unique<Node>(
            Node{{std::move(key), std::move(value)}, std::move(buckets_[bucket])});
        buckets_[bucket] = std::move(node);
        ++size_;
        return true;
    }
};

Rehashing creates a new bucket array and redistributes nodes using their hash codes. It invalidates iterators and changes bucket positions. reserve(expected_elements) lets the container choose enough buckets before a known insertion phase. Load factor is size() / bucket_count(). A high load factor saves bucket memory and increases chain or probe work.

Writing a hash function

A hash function must produce the same value for keys considered equal by the equality predicate. Useful hashes spread structured input changes through the output bits. Hash combination should mix both value and position. Plain XOR makes (a, b) collide with (b, a).

#include <bit>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <utility>

struct GridPointHash {
    std::size_t operator()(const std::pair<int, int>& point) const noexcept {
        std::uint64_t left = std::hash<int>{}(point.first);
        std::uint64_t right = std::hash<int>{}(point.second);

        // Position-sensitive combination followed by a 64-bit avalanche.
        std::uint64_t value = left ^ std::rotl(right, 32) ^
                              0x9e3779b97f4a7c15ULL;
        value ^= value >> 30;
        value *= 0xbf58476d1ce4e5b9ULL;
        value ^= value >> 27;
        value *= 0x94d049bb133111ebULL;
        value ^= value >> 31;
        return static_cast<std::size_t>(value);
    }
};

This mixer is suitable for a general in-process composite key. It provides no keyed defense against attacker-controlled collision attacks. Network-facing hash tables may need a per-process keyed hash. A poor hash or adversarial input can place many keys in one bucket and produce linear lookup time.

priority_queue: a container adaptor over a heap

priority_queue<T> uses vector<T> by default and stores a comparator. The vector is arranged as a binary heap: children of index i are 2*i + 1 and 2*i + 2. The default less<T> produces a max-heap, so top() returns the largest element.

#include <cstddef>
#include <functional>
#include <utility>
#include <vector>

template<class T, class Compare = std::less<T>>
class PriorityQueueCore {
    std::vector<T> heap_;
    Compare lower_priority_;

public:
    const T& top() const { return heap_.front(); }

    void push(T value) {
        heap_.push_back(std::move(value));
        std::size_t child = heap_.size() - 1;
        while (child > 0) {
            const std::size_t parent = (child - 1) / 2;
            if (!lower_priority_(heap_[parent], heap_[child])) break;
            std::swap(heap_[parent], heap_[child]);
            child = parent;
        }
    }

    void pop() {
        std::swap(heap_.front(), heap_.back());
        heap_.pop_back();
        std::size_t parent = 0;
        while (true) {
            const std::size_t left = parent * 2 + 1;
            if (left >= heap_.size()) break;
            const std::size_t right = left + 1;
            std::size_t best = left;
            if (right < heap_.size() &&
                lower_priority_(heap_[left], heap_[right])) {
                best = right;
            }
            if (!lower_priority_(heap_[parent], heap_[best])) break;
            std::swap(heap_[parent], heap_[best]);
            parent = best;
        }
    }
};

Push and pop touch one root-to-leaf path, giving logarithmic time. Top is constant time. Iteration is intentionally absent because the underlying heap order only guarantees the relationship between each parent and its children.

map versus unordered_map

Choose map when order, range operations, stable logarithmic bounds, or iterator behavior is part of the interface. Choose unordered_map for exact-key lookup when hashing is available and average-case behavior fits the workload. Measure both for hot paths because key size, allocation, hash cost, node layout, and access distribution affect the result.

span and string_view lifetime

Both types borrow a contiguous sequence. A span stores element access. A string view stores character access. Copying either view copies its pointer and length. The source storage must remain alive and must stay at the same address for every later access.

#include <span>
#include <string>
#include <string_view>
#include <vector>

int sum(std::span<const int> values);

std::vector<int> samples{1, 2, 3};
std::span<const int> view = samples;
samples.push_back(4);            // may reallocate
// view may now contain a dangling pointer

std::string_view stable = "literal"; // string literal has static storage

std::string_view dangling_text() {
    std::string local = "temporary";
    return local;                // returned view refers to destroyed characters
}

A string view stores a pointer and length without adding a null terminator. Passing view.data() to a C API that expects a terminated string can read beyond the view. Use a pointer-length API or create an owning string. Borrowed-view parameters are effective for synchronous calls because the caller retains ownership through the call. Storing a view in an object or callback requires an explicit lifetime relationship.

Ranges, pipes, views, and lambda capture

A range pipeline starts with a range expression on the left. Each adaptor closure on the right wraps that range in another view. The pipe expression below is equivalent to nested adaptor calls.

ranges_pipeline.cpp#include <ranges>
#include <vector>

std::vector<int> filtered_squares() {
    std::vector<int> values{1, 2, 3, 4, 5, 6};
    const int minimum = 3;

    auto filtered =
        values
        | std::views::filter([minimum](int value) { return value >= minimum; })
        | std::views::transform([](int value) { return value * value; });

    // Equivalent structure without pipe syntax:
    auto same = std::views::transform(
        std::views::filter(
            values,
            [minimum](int value) { return value >= minimum; }),
        [](int value) { return value * value; });
    (void)same;

    return {filtered.begin(), filtered.end()};
}

Read range | adaptor(arguments) as “construct this adaptor over range.” filter stores the predicate and skips elements for which it returns false. transform computes a value when an iterator is dereferenced. These views are lazy. Pipeline construction visits zero input elements.

Lambda syntax and capture clause

The brackets describe closure state, the parentheses describe call arguments, and the braces contain the function body: [captures](parameters) specifiers -> return_type { body }. For [](int value), the closure stores no local state and each call receives one integer.

lambda_capture.cpp#include <memory>

int capture_example() {
    int limit = 10;
    auto by_value = [limit](int value) { return value < limit; };
    auto by_reference = [&limit](int value) { return value < limit; };

    const bool copied_limit_result = by_value(9);
    limit = 5;
    const bool referenced_limit_result = by_reference(9);

    auto state = std::make_unique<int>(7);
    auto owns_state =
        [saved = std::move(state)](int value) mutable {
            *saved += value;
            return *saved;
        };

    // mutable permits modification of members captured by value.
    // Referenced variables keep the mutability of their original objects.
    return copied_limit_result && !referenced_limit_result
        ? owns_state(3)
        : -1;
}

View pipelines usually store their base view and callable objects. A predicate captured by reference can therefore dangle even when the underlying range still exists. Capture small configuration values by value. Use reference capture only when the pipeline's lifetime is bounded by the referenced object.

Defined failures, undefined behavior, and concurrency

Undefined behavior versus a defined error

Undefined behavior means the C++ specification places no requirements on the program after that operation. The optimizer may assume the operation never occurs. Out-of-bounds access through operator[], signed integer overflow, use after lifetime, invalid shifts, and data races are common examples.

A defined error has specified behavior: a function may throw, return an empty optional, produce an error code, set a stream state, or terminate according to a documented precondition. The API determines which channel applies.

#include <optional>
#include <vector>

std::optional<int> checked_element(const std::vector<int>& values,
                                   std::size_t index) {
    if (index >= values.size()) return std::nullopt;
    return values[index];
}

std::vector<int> values{1, 2, 3};
int defined_exception = values.at(10); // throws std::out_of_range
int undefined_access = values[10];     // precondition violated: undefined behavior

Data races and happens-before

A data race exists when two potentially concurrent evaluations access the same memory location, at least one access writes, neither access is atomic, and the evaluations lack a happens-before ordering. A data race has undefined behavior.

Happens-before is an ordering relation built from program order and synchronization. Unlocking a mutex synchronizes with a later successful lock of that mutex. Releasing an atomic value can synchronize with an acquiring load that observes it. Thread completion synchronizes with a successful join. These edges make earlier writes visible to later reads.

release_acquire.cpp#include <atomic>
#include <cassert>
#include <string>
#include <thread>

void release_acquire_example() {
    std::string message;
    std::atomic<bool> ready{false};

    std::thread producer([&] {
        message = "complete";                         // ordinary write
        ready.store(true, std::memory_order_release); // publishes prior writes
    });

    std::thread consumer([&] {
        while (!ready.load(std::memory_order_acquire)) {}
        assert(message == "complete");                // sees the published write
    });

    producer.join();
    consumer.join();
}

Atomicity applies to the atomic object. A shared_ptr's reference count and an atomic readiness flag protect unrelated mutable state only when the synchronization design connects their operations. The synchronization design must establish an ordering edge for every shared write that another thread reads.

Mutex, condition-variable predicate, and shutdown

A condition variable may wake without a notification. The waiting predicate therefore defines the state that permits progress. Testing that predicate while holding the same mutex used by producers prevents missed state transitions. Shutdown belongs in the predicate so blocked consumers can exit.

#include <condition_variable>
#include <deque>
#include <mutex>
#include <optional>
#include <stdexcept>

template<class T>
class BlockingQueue {
public:
    void push(T value) {
        {
            std::lock_guard lock(mutex_);
            if (stopping_) throw std::logic_error("queue is stopping");
            queue_.push_back(std::move(value));
        }
        ready_.notify_one();
    }

    std::optional<T> pop() {
        std::unique_lock lock(mutex_);
        ready_.wait(lock, [&] { return stopping_ || !queue_.empty(); });

        if (queue_.empty()) return std::nullopt; // shutdown and drained
        T value = std::move(queue_.front());
        queue_.pop_front();
        return value;
    }

    void shutdown() {
        {
            std::lock_guard lock(mutex_);
            stopping_ = true;
        }
        ready_.notify_all();
    }

private:
    std::mutex mutex_;
    std::condition_variable ready_;
    std::deque<T> queue_;
    bool stopping_ = false;
};

The lock protects both the queue and the shutdown flag. Notification happens after releasing the lock so an awakened thread can acquire it immediately. Returning an empty optional distinguishes a drained shutdown from a value. A bounded queue would add a capacity predicate and a second notification path for producers.

Average, amortized, and worst-case complexity

One vector insertion that triggers reallocation is linear because it relocates the existing elements. Geometric growth ensures that a sequence of n appends performs linear total relocation work, giving constant amortized cost per append. Hash-table lookup uses an average-case statement instead: a suitable hash and bucket distribution keep each bucket short, while a collision-heavy state can require a linear scan.

Warnings, sanitizers, static analysis, tests, and measurements

• -Wall -Wextra -Wpedantic -Wconversion -Wshadow expose suspicious conversions and control flow.
• AddressSanitizer detects invalid memory access and lifetime violations.
• UndefinedBehaviorSanitizer instruments selected undefined operations.
• ThreadSanitizer detects data races. Run it separately from address instrumentation.
• clang-tidy checks ownership, API use, and bug patterns across source.
• Differential tests compare an optimized implementation with a small direct implementation.
• Google Benchmark supplies warm-up, repetitions, statistics, and optimization barriers.
• perf stat records cycles, instructions, branches, and cache events where the kernel permits access.

Language and library changes from C++11 through C++26

C++14 extended generic lambdas, return-type deduction, variable templates, and constexpr bodies between the C++11 and C++17 revisions. Build systems should select the standard level explicitly and code should test optional library support with feature-test macros.

#include <version>

#if defined(__cpp_lib_expected) && __cpp_lib_expected >= 202202L
#include <expected>
using ParseResult = std::expected<Packet, ParseError>;
#else
using ParseResult = ProjectExpected<Packet, ParseError>;
#endif

#if defined(__cpp_lib_span)
static_assert(__cpp_lib_span >= 202002L);
#endif

C++26 reflection, contracts, and execution support remains uneven across compiler and standard-library releases. The feature set and implementation status are separate facts. The references at the end of this page link both the working draft and library source.

C++ problem-solving pattern library

Algorithm material now lives in focused chapters rather than one long appendix. Each chapter starts from statement signals and a direct implementation, names the repeated work, states the invariant maintained by the optimized version, and groups problems that use the same state.

Coverage index

Each item links to the language or library mechanism that controls its storage, ownership, dispatch, invalidation, error, or synchronization behavior.

• Lifetime versus storage duration
• Stack, static storage, and free store
• lvalue, xvalue, prvalue
• What std::move actually does
• Copy elision and return-value optimization
• Rule of Zero, Three, and Five
• Deep versus shallow copy
• unique_ptr, shared_ptr, weak_ptr
• Virtual destructor and object slicing
• Templates, concepts, virtual dispatch, and variant
• const, constexpr, consteval
• Exception guarantees and noexcept
• vector growth and invalidation
• map versus unordered_map
• span and string_view lifetime
• Alignment, padding, locality, and false sharing
• Undefined behavior versus a defined error
• Data race and happens-before
• Mutex, condition-variable predicate, and shutdown
• Average, amortized, and worst-case complexity

Primary references and implementation status

1. WG21 editors, N5055 Editors' Report (Jul 16, 2026): N5054 is the current C++29 working draft. N5046 was the last approved C++26 draft.
2. Köppe et al., N5046 C++26 working draft (May 2026).
3. Revzin et al., P2996R13: Reflection for C++26.
4. Berne, Doumler, and Krzemieński, P2900R14: Contracts for C++.
5. Hober et al., P2300R10: std::execution.
6. GNU Project, C++ standards support in GCC (consulted Jul 27, 2026).
7. LLVM Project, Clang C++ language status (consulted Jul 27, 2026).
8. WG21, N4950 C++23 working draft: object lifetime, expressions, containers, ranges, concurrency, and complexity requirements.
9. GNU Project, libstdc++ implementation sources: vector, deque, list, red-black tree, hash table, priority queue, array, and span.
10. Google, Google Benchmark user guide: warm-up, repetitions, random interleaving, optimization barriers, and performance counters.
11. Perfetto, Track Event instrumentation: process and thread timeline tracing through the C++ SDK.