Iterators, Moves, Smart Pointers, Concurrency

01Iterator Invalidation

An iterator, pointer, or reference into a container is a promise that a particular element sits at a particular place. Container operations can break that promise — and using a broken one is undefined behavior (UB), not an exception, not a null check. It often "works" in testing and corrupts memory in production. Interviewers probe this because it's the easiest live-coding bug to write.

Why each container invalidates — from memory layout

You already know the layouts, so the rules derive rather than memorize:

• vector: one contiguous block. When it grows past capacity it reallocates — new block, elements moved, old block freed. Every iterator/pointer/reference into the old block now dangles. Insert/erase in the middle also shifts everything after the point.
• list/map/set: node-based. Elements never move; only the erased node's memory goes away.
• unordered_map/unordered_set: node-based buckets, but growth triggers a rehash — nodes get re-distributed among new buckets. Iterators (which walk buckets) break; pointers/references to elements (the nodes themselves didn't move) survive.
• deque: chunked blocks + an index map. Push at either end keeps existing elements in place (references survive) but rebuilds the index (iterators break). Insert/erase in the middle breaks everything.

The table (know this cold)

The two ⚠️ rows are the interview favorites: operations where iterators die but references survive. Being able to explain why (index rebuilt / rehash, but nodes stayed put) is the senior answer.

The classic bugs

// Bug 1: reference held across push_back
std::vector<int> v = {1, 2, 3};
int& first = v[0];
v.push_back(4);        // may reallocate
first = 99;            // UB if it did — writes to freed memory

// Bug 2: inserting from yourself
v.push_back(v[0]);     // SAFE — the standard requires push_back to handle an
// argument aliasing the vector's own storage (copied before the old block dies).
v.insert(v.end(), v.begin(), v.end());   // UB — RANGE insert from the same
// container: the source iterators invalidate mid-operation. Single-element
// self-insert is handled; self-range is not. Worth voicing in an interview.

// Bug 3: erasing inside a range-for
for (int x : v)
    if (x % 2 == 0) v.erase(...);  // UB — range-for holds iterators

Erasing correctly, per container

// vector / deque: erase returns the next valid iterator
for (auto it = v.begin(); it != v.end(); ) {
    if (bad(*it)) it = v.erase(it);   // reseat from return value
    else          ++it;
}

// vector, erasing many: erase-remove idiom (single O(n) pass)
v.erase(std::remove_if(v.begin(), v.end(), bad), v.end());

// C++20: same thing, one call
std::erase_if(v, bad);

// map / set / unordered_*: same reseat pattern works (C++11 erase returns next)
for (auto it = m.begin(); it != m.end(); )
    it = bad(*it) ? m.erase(it) : std::next(it);

Second-order points (the follow-up questions)

• Why is erase-remove two steps? std::remove_if can't erase — it only sees iterators, not the container. It compacts survivors to the front and returns the new logical end; the tail is moved-from junk still counted in size(). The outer erase(newEnd, end()) does the actual truncation. "What's in the tail after remove_if?" is a standard follow-up: valid-but-unspecified leftovers.
• Indices survive reallocation; pointers don't. v[7] means the same element after any growth. When you must remember a position across mutations, storing an index instead of an iterator/pointer is the standard fix — cheap, and worth saying unprompted.
• Iterator categories: random-access (vector/deque/arrays: it + n, it2 - it1) → bidirectional (map/set/list: only ++/--) → forward (unordered_*, forward_list). This is why std::sort won't compile on a list (needs random access; list::sort exists instead) and why std::next(it, n)/std::advance are O(n) on node containers.
• Views obey the same rules: .data(), c_str(), spans and string_views into a container are invalidated exactly like pointers into it. A string_view of a string that then grows — or of a temporary that died — is the modern dangling-pointer bug.

↑ back to top

02Move Semantics

The problem moves solve

Copying a vector<string> means allocating and copying every buffer. But if the source is a temporary about to die, copying is waste — you could just steal its buffers. Move semantics is the language machinery for "steal, don't copy, when the source won't need it."

Value categories (the 60-second version)

• lvalue — has a name/identity, you can take its address: variables, members, *p. Might be used again → not safe to steal from.
• prvalue — a pure temporary: f() returning by value, x + y, literals. Dying at the semicolon → safe to steal.
• xvalue — an "expiring" lvalue: something with identity that you've declared done with, i.e. std::move(x).

rvalue = prvalue or xvalue. An rvalue reference T&& binds only to rvalues — that's how a function can offer a separate overload for "sources you may gut":

void take(const std::string& s);  // binds to everything (copies)
void take(std::string&& s);        // binds to rvalues only (steals)

std::string name = "yel";
take(name);             // lvalue → const& overload
take(name + "!");       // prvalue → && overload
take(std::move(name));  // xvalue  → && overload

Writing move operations

class Buffer {
    char* data_ = nullptr;
    size_t n_ = 0;
public:
    Buffer(Buffer&& o) noexcept
        : data_(std::exchange(o.data_, nullptr)),  // steal + null the source
          n_(std::exchange(o.n_, 0)) {}

    Buffer& operator=(Buffer&& o) noexcept {
        if (this != &o) {
            delete[] data_;
            data_ = std::exchange(o.data_, nullptr);
            n_    = std::exchange(o.n_, 0);
        }
        return *this;
    }
};

• Inside the move ctor, o is an lvalue (it has a name!) — so moving members needs std::move(o.member) or std::exchange. Forgetting this silently copies. ⚠️
• Leave the source valid but unspecified: destructible and assignable. Nulling pointers achieves that.
• Mark moves noexcept. vector reallocation moves elements only if the move ctor is noexcept — otherwise it copies, to preserve the strong exception guarantee (std::move_if_noexcept). A non-noexcept move can silently make your vector O(n) copies on every growth. ⚠️
• Compiler generates move ops only if you declare no copy ops, no destructor, no other move op. Declaring a destructor — even = default — suppresses implicit moves. Rule of Five / Rule of Zero.

RVO and copy elision

std::string make() {
    std::string s = "long string ...";
    return s;                 // NRVO: usually constructed in place, zero copies/moves
    // return std::move(s);   // PESSIMIZATION — disables NRVO, forces a move
}

• RVO (return value optimization): returning a prvalue (return std::string("x");) constructs directly in the caller's storage — guaranteed since C++17, not even a move happens.
• NRVO (named RVO): returning a local variable by name — permitted and near-universal, but not guaranteed. If it can't apply, the return is treated as a move automatically.
• ⚠️ Therefore return std::move(local); is an anti-pattern: it can't help (the return already moves at worst) and it breaks NRVO. Compilers warn about it now. Saying this unprompted is a strong signal.
• ⚠️ The exception — where an explicit move in a return IS correct: returning a member or a parameter (return std::move(pair_.first);, return std::move(param);). Those never qualify for NRVO (it applies only to plain local variables), so without the move you'd get a copy. Don't let the anti-pattern rule make you call correct code a bug.

Sink parameters (the API-design question)

class Person {
    std::string name_;
public:
    Person(std::string name) : name_(std::move(name)) {}  // by value + move
};
// rvalue arg: move + move (≈free).  lvalue arg: copy + move (minimum possible).

For parameters the function will keep, take by value and move into place: one signature, optimal for both call styles. The const&/&& overload pair saves one cheap move at the cost of 2ⁿ overloads. "By value and move for sinks" is the expected answer to "how should this constructor take its arguments?"

Generation rules (what silently disappears)

• Declaring a destructor or any copy op (even = default) → implicit moves not generated; "moves" silently become copies. Declaring any move op → copies deleted. Declare one of the five, deal with all five (Rule of Five), or declare none (Rule of Zero).
• Verify instead of hoping: static_assert(std::is_nothrow_move_constructible_v<Widget>);

Full treatment — value categories, reference collapsing, the Noisy trap gallery — lives in the dedicated move-semantics deep dive.

Perfect forwarding (recognize, use correctly)

template <typename T>
void wrapper(T&& arg) {                // forwarding reference, NOT rvalue ref
    target(std::forward<T>(arg));      // lvalue stays lvalue, rvalue stays rvalue
}

• T&& where T is deduced is a forwarding reference — it binds to anything. Reference collapsing (& && → &) makes it work.
• std::forward<T> = conditional move: casts back to rvalue only if the caller passed an rvalue. Use forward with forwarding references, move with everything else. This is how make_unique, emplace_back, etc. pass your arguments through without extra copies.
• ⚠️ Buffer&& (concrete type) is a plain rvalue reference. T&& (deduced) is forwarding. Same syntax, different beast — a favorite trick question.

↑ back to top

03Smart Pointer Internals

unique_ptr — ownership at zero cost

auto p = std::make_unique<Widget>(42);  // preferred over unique_ptr<Widget>(new ...)
auto q = std::move(p);                  // ownership transfers; p is now null
// auto r = q;                          // COMPILE ERROR — copy is deleted

• Layout: with the default deleter, sizeof(unique_ptr<T>) == sizeof(T*) — exactly one raw pointer. The deleter is a stateless empty type stored via the empty base optimization, so it occupies zero bytes. Zero runtime overhead vs a raw pointer; the destructor call is the same delete you'd have written.
• ⚠️ A custom deleter changes that: unique_ptr<T, void(*)(T*)> stores the function pointer → 16 bytes. A capture-less lambda deleter stays at 8 (stateless type). Knowing this distinction is a senior tell.
• Move-only: copying is = deleted — that's the entire single-ownership guarantee, enforced by the type system.
• Why make_unique: shorter, no naked new, and (pre-C++17) exception safety when two allocations sat in one expression.
• get() for non-owning access, release() to hand ownership back as a raw pointer, reset() to replace/delete.

shared_ptr — the control block

A shared_ptr is two pointers (16 bytes): one to the object, one to a heap-allocated control block containing:

• strong count — how many shared_ptrs own the object. Hits 0 → object destroyed.
• weak count — how many weak_ptrs observe it. Both hit 0 → control block itself freed.
• the deleter and allocator (type-erased).

auto a = std::make_shared<Widget>();   // ONE allocation: object + control block together
auto b = std::shared_ptr<Widget>(new Widget);  // TWO allocations

auto c = a;             // copy: strong count 1 → 2 (atomic increment)
auto d = std::move(a);  // move: counts untouched — a just goes null

• make_shared wins because it fuses object + control block into one allocation: fewer allocations, better locality. Trade-off worth naming: the object's memory can't be freed until the weak count also drops, since they share one block — with long-lived weak_ptrs to big objects, the two-allocation form releases object memory sooner.
• Refcount updates are atomic — thread-safe, but each copy costs a contended atomic op. That's why you pass const shared_ptr& (or better, Widget&/Widget*) down call chains instead of copying, and why moves beat copies (no count touch).
• ⚠️ Thread-safety scope: the counts are atomic; the pointed-to object is not protected at all, and mutating one shared_ptr instance from two threads is a data race.

weak_ptr — observing without owning

std::weak_ptr<Widget> w = a;      // weak count++, strong count unchanged
if (auto s = w.lock()) {          // atomically: still alive? then take a strong ref
    s->use();                      // safe for s's lifetime
}                                  // else the object is gone

• The canonical use: breaking cycles. Parent holds shared_ptr to child, child holds shared_ptr back to parent → both strong counts stuck at ≥1 → neither ever destroyed → leak with no dangling pointer to catch. Fix: the back-edge (child→parent) becomes weak_ptr. Rule of thumb: ownership edges shared, back/observer edges weak.
• lock() not expired()+deref — expired() then use is a race in threaded code.

Second-order points (the follow-up questions)

• Passing conventions — signatures are ownership statements: take unique_ptr<T> by value to take ownership (caller must std::move); take shared_ptr<T> by value to participate in ownership; take T& or T* to merely use the object. A function that only reads a widget should not mention smart pointers at all — asking for const shared_ptr& to "be safe" is a design smell interviewers probe.
• Deleter placement contrast: shared_ptr's deleter lives in the control block, type-erased — so sizeof(shared_ptr) is always two pointers, custom deleter or not, and the deleter is chosen at creation. Consequence worth knowing: shared_ptr<Base> p = make_shared<Derived>(); destroys the Derived correctly even without a virtual destructor, because the control block captured Derived's deleter. (Still write virtual destructors — don't lean on this.) unique_ptr stores its deleter inline, which is why a stateful deleter grows it.
• unique_ptr<T[]> exists and calls delete[]; unique_ptr<T> holding a new[] array is UB. In practice: prefer vector/array unless an API hands you a raw array.
• shared_from_this() timing: only valid once some shared_ptr already owns the object — calling it in the constructor throws std::bad_weak_ptr (no control block exists yet). The standard workaround is a static factory that creates the shared_ptr first.
• Aliasing constructor: shared_ptr<Part>(owner, &owner->part) — points at a member while sharing the owner's control block and lifetime. How you hand out a piece of an object without splitting ownership.

↑ back to top

04Concurrency Basics

What a data race actually is

Two threads access the same memory location, at least one access is a write, and there's no synchronization ordering them → data race → UB. Not "sometimes wrong values" — undefined, the compiler may assume it can't happen and optimize accordingly. The famous demo:

int counter = 0;
// two threads each run: for (int i = 0; i < 1'000'000; ++i) ++counter;
// result: almost never 2'000'000. ++counter is read-modify-write, three steps,
// and interleavings lose updates. Also formally UB regardless of the count.

Mutexes and the lock types

std::mutex m;
int counter = 0;

void inc() {
    std::lock_guard<std::mutex> lk(m);   // RAII: locks now, unlocks in destructor
    ++counter;
}                                        // unlock even if an exception flies

• Never raw m.lock()/m.unlock() — an early return or exception between them deadlocks the next locker. RAII (resource acquisition is initialization) makes unlock unskippable. This is the RAII example interviewers want.
• lock_guard: lock in ctor, unlock in dtor, nothing else. Default choice.
• unique_lock: same plus unlock/relock ability, deferred locking, movability — needed by condition_variable. Slightly heavier; use only when you need the flexibility.
• scoped_lock (C++17): locks multiple mutexes atomically with a deadlock-avoidance algorithm. Two threads locking A-then-B and B-then-A is the classic deadlock; scoped_lock(a, b) or a global lock ordering are the two standard answers. ⚠️

condition_variable — waiting for a fact to become true

std::mutex m;
std::condition_variable cv;
std::queue<Task> q;

// consumer
std::unique_lock<std::mutex> lk(m);
cv.wait(lk, [&]{ return !q.empty(); });  // unlocks while asleep, relocks to test
Task t = std::move(q.front()); q.pop();
lk.unlock();

// producer
{ std::lock_guard<std::mutex> lk(m); q.push(std::move(task)); }
cv.notify_one();

• ⚠️ Always the predicate form (or an explicit while-loop). Two reasons: spurious wakeups — the OS may wake a waiter with no notify at all — and the wakeup/recheck gap where another consumer may have already taken the item. if + wait is the bug; the predicate is a loop.
• wait requires unique_lock because it must unlock during the sleep and relock before returning.
• notify_one wakes one waiter; notify_all wakes all (use when different waiters wait for different conditions, or on shutdown).
• This producer/consumer skeleton is the "implement a thread-safe queue / bounded buffer" interview question — practice writing it cold.

atomics — when a mutex is overkill

std::atomic<int> counter{0};
counter.fetch_add(1);          // or ++counter — single indivisible instruction
bool was = flag.exchange(true); // test-and-set

• Right tool for single-variable state: counters, flags, sequence numbers. The moment an invariant spans two variables (queue + its size, check-then-act), you need a mutex — two atomics don't make their combination atomic. ⚠️
• Default memory ordering is seq_cst (sequentially consistent) — the safe one. Weaker orderings (acquire/release/relaxed) exist for performance; in an interview, name them, say the default is seq_cst and that you'd reach for weaker orderings only with a benchmark and a careful proof. Overclaiming lock-free expertise backfires.

Threads themselves + odds and ends

std::thread t(work, arg);       // starts immediately; args are COPIED into the thread
t.join();                        // must join or detach before t is destroyed,
                                 // else std::terminate
std::jthread jt(work);           // C++20: joins automatically in its destructor

• ⚠️ Thread args copy by default — std::thread(f, std::ref(x)) to pass a reference; dangling references into dead stack frames are the classic bug.
• Prefer std::async/futures or a thread pool for task-shaped work; raw threads for long-lived workers.
• Magic statics: initialization of a function-local static is thread-safe since C++11 — the Meyers singleton (static Widget w; return w;) needs no locking. std::call_once/once_flag for the general case.

Second-order points (the follow-up questions)

• Read-heavy data → std::shared_mutex: many concurrent readers (shared_lock) or one exclusive writer (unique_lock). Know the caveat: for very short critical sections the bookkeeping can cost more than a plain mutex — "reader/writer lock" is an answer you propose with a measurement plan.
• ⚠️ The std::async trap: the future returned by std::async blocks in its destructor (waits for the task). So std::async(std::launch::async, work); — discarding the future — runs effectively synchronously: the temporary future's destructor waits right there. Also: the default launch policy is async | deferred, and deferred means "run lazily on .get(), possibly never." Request std::launch::async explicitly and keep the future.
• CAS — compare-and-swap, the lock-free primitive: a.compare_exchange_weak(expected, desired) atomically does "if a == expected, write desired; else load a into expected," returning success. Lock-free algorithms are CAS retry loops: read, compute, attempt swap, retry on failure. weak may fail spuriously (fine inside a loop, slightly faster); strong doesn't. If asked to "implement X lock-free," the shape of the answer is a CAS loop — and a caveat that you'd benchmark it against a mutex.
• acquire/release, one level deeper: a release store publishes every write made before it; an acquire load that reads that value is guaranteed to see them. That pairing is the "producer fills data, sets ready-flag; consumer sees flag, reads data" handoff. seq_cst (the default) = acquire/release plus one global order all threads agree on. That's the depth to have; deriving fence placements live is not expected.
• thread_local: one instance per thread — the tool for per-thread caches, counters, and scratch buffers that make sharing (and its costs) disappear, combined at the end. Often the right answer to "how do we reduce contention on this counter."
• Performance side: false sharing (two threads writing different variables on one 64-byte cache line → coherence ping-pong; fix with alignas(64)) and contention economics live in the performance guide — flag them here because "make this concurrent code fast" questions blend both docs.

↑ back to top

05Combined Cheat Sheet

Iterator invalidation

• vector reallocation kills everything; reserve() prevents it and you should say so
• erase returns the next iterator — reseat with it = c.erase(it)
• bulk removal from vector: erase-remove idiom or std::erase_if (C++20); remove_if compacts, erase truncates — that's why two steps
• deque push at ends / unordered rehash: iterators die, references survive — know why
• never erase inside a range-for
• indices survive reallocation; pointers/iterators/string_views don't
• iterator categories: random-access → bidirectional → forward; sort needs random access

Move semantics

• std::move = cast; const kills moves silently (falls back to copy)
• move ctor: parameter is an lvalue — std::move/std::exchange each member; null the source
• moves marked noexcept, or vector copies on reallocation
• dtor/copy declaration kills implicit moves; move declaration deletes copies — Rule of Five/Zero
• never return std::move(local) — but DO move returned members and parameters (NRVO never applies to those)
• sinks: pass by value + std::move into place
• deduced T&& = forwarding reference → std::forward<T>; concrete X&& = rvalue ref → std::move

Smart pointers

• unique_ptr = 8 bytes, zero overhead, move-only; function-pointer deleter doubles it
• shared_ptr = 2 pointers + control block {strong, weak, deleter}; copies do atomic ops, moves don't
• shared_ptr's deleter lives in the control block — size always 16, correct Derived destruction captured at creation
• make_shared: one allocation; caveat — weak_ptrs pin the whole block
• never two shared_ptrs from one raw pointer; never shared_ptr(this) — enable_shared_from_this (but not in the constructor)
• cycles: back-edges are weak_ptr; access via lock(), not expired()
• signatures: unique_ptr by value = takes ownership; shared_ptr by value = shares it; T&/T* = just uses it

Concurrency

• data race = concurrent access + a write + no sync = UB
• lock_guard default, unique_lock for condition_variable waits and flexibility, scoped_lock for multiple mutexes, shared_mutex for read-heavy
• cv.wait always with a predicate (spurious + stolen wakeups)
• producer/consumer queue: be able to write it cold
• atomics for one variable, mutex for an invariant across variables; compare_exchange = the CAS loop primitive
• release publishes, acquire observes; seq_cst = that plus one global order (the default)
• std::async: future's destructor blocks — request launch::async and keep the future
• join or detach every thread; jthread auto-joins; std::ref to pass references; thread_local for per-thread state
• function-local static init is thread-safe (Meyers singleton)

↑ back to top