C++ Interview Prep: STL, Memory, and Templates

// shared_ptr has two internal pointers:
// 1. The managed object pointer (T*)
// 2. A control block pointer

struct ControlBlock {
    std::atomic<long> use_count;    // reference count (shared_ptr copies)
    std::atomic<long> weak_count;   // weak_ptr count + 1 (the +1 is from shared owner group)
    // deleter (type-erased)
    // allocator (type-erased)
    // sometimes: the managed object itself (make_shared optimization)
};

// sizeof(shared_ptr<T>) == sizeof(T*) + sizeof(ControlBlock*)
//                       == 16 bytes (on 64-bit)

// Two separate allocations with new:
auto p = std::shared_ptr<Widget>(new Widget{});
// ↑ allocates Widget (1st), then allocates ControlBlock (2nd)

// One allocation with make_shared:
auto p = std::make_shared<Widget>();
// ↑ allocates Widget + ControlBlock in a single chunk — better cache locality

// Cost of a shared_ptr copy:
// - Atomic increment of use_count (memory_order_acq_rel on x86: locked XADD)
// - ~1-10ns latency + cache line invalidation across cores
// → Never copy shared_ptr in hot paths; pass by const reference

struct Node {
    std::shared_ptr<Node> next;   // strong ownership
    std::shared_ptr<Node> prev;   // ERROR: circular — never freed!
    // Fix:
    std::weak_ptr<Node> prev;     // weak — doesn't keep alive
};

// Breaking the cycle:
auto a = std::make_shared<Node>();
auto b = std::make_shared<Node>();
a->next = b;
b->prev = a;   // weak_ptr — a and b both freed when no strong refs remain

// Accessing through weak_ptr:
if (auto locked = b->prev.lock()) {   // returns shared_ptr or empty
    locked->do_something();
}

template<typename T, typename Deleter = std::default_delete<T>>
class UniquePtr {
    T* ptr_ = nullptr;
    [[no_unique_address]] Deleter del_;   // EBO: stateless deleter takes no space

public:
    explicit UniquePtr(T* p = nullptr) noexcept : ptr_(p) {}

    ~UniquePtr() noexcept {
        if (ptr_) del_(ptr_);
    }

    // Move-only: no copy
    UniquePtr(const UniquePtr&) = delete;
    UniquePtr& operator=(const UniquePtr&) = delete;

    UniquePtr(UniquePtr&& other) noexcept : ptr_(other.ptr_), del_(std::move(other.del_)) {
        other.ptr_ = nullptr;
    }

    UniquePtr& operator=(UniquePtr&& other) noexcept {
        if (this != &other) {
            reset();
            ptr_ = other.ptr_;
            del_ = std::move(other.del_);
            other.ptr_ = nullptr;
        }
        return *this;
    }

    T* get()      const noexcept { return ptr_; }
    T& operator*() const noexcept { return *ptr_; }
    T* operator->() const noexcept { return ptr_; }
    explicit operator bool() const noexcept { return ptr_ != nullptr; }

    T* release() noexcept { T* p = ptr_; ptr_ = nullptr; return p; }
    void reset(T* p = nullptr) noexcept { if (ptr_) del_(ptr_); ptr_ = p; }
};

std::vector<int> v = {1, 2, 3};
auto it = v.begin() + 1;   // iterator to element 2

v.push_back(4);    // if capacity exceeded: NEW allocation, ALL iterators invalid
                   // if capacity OK: only end() invalid; begin() to inserted point valid

v.insert(v.begin(), 0);  // always invalidates all iterators at and after insert point
v.erase(v.begin());      // invalidates all iterators at and after erase point
v.reserve(100);          // if reallocation needed: ALL invalid; otherwise NONE

// Safe pattern: after any potential resize, don't use old iterators
v.reserve(10);
for (auto& x : v) { ... }  // use range-for; it recomputes begin/end each iteration

std::vector<bool> bools{true, false, true};
auto b = bools[1];       // b is a PROXY object, not a bool&
bool& ref = bools[1];    // COMPILE ERROR — no reference possible!
auto* p = &bools[0];     // COMPILE ERROR — no address possible!

// Why: vector<bool> is specialized to pack bits (1 bit per bool instead of 8 bytes)
// This breaks container requirements — operator[] doesn't return T&

// Alternatives:
std::vector<char> chars{1, 0, 1};       // works as expected
std::deque<bool> dbools{true, false};   // standard deque is not specialized
std::bitset<8> bits;                    // if size is compile-time constant

// std::map<K,V>: red-black tree, O(log n) all ops, ordered, stable iteration
std::map<std::string, int> m;
m["a"] = 1;
// Keys always in sorted order; find/insert/erase are O(log n)

// std::unordered_map<K,V>: hash table, O(1) average, O(n) worst
std::unordered_map<std::string, int> um;
um["a"] = 1;
// Average O(1); worst case O(n) on hash collision (e.g., malicious input)
// Rehashing occurs when load_factor > max_load_factor (default 1.0)
// Rehashing invalidates ALL iterators

// When to use which:
// map: ordered traversal, range queries, predictable worst-case
// unordered_map: pure lookup by key, hot path performance

// Old way: SFINAE with std::enable_if (C++11/14)
template<typename T>
typename std::enable_if<std::is_integral_v<T>, T>::type
add_one(T x) { return x + 1; }
// Cryptic, slow to compile, terrible error messages when constraint not met

// C++17: constexpr if (simpler for branching within a single function)
template<typename T>
auto stringify(T x) {
    if constexpr (std::is_arithmetic_v<T>)
        return std::to_string(x);
    else
        return std::string(x);
}

// C++20: Concepts — readable, composable, fast compile, clear errors
template<std::integral T>
T add_one(T x) { return x + 1; }

// Or abbreviated (C++20):
auto add_one(std::integral auto x) { return x + 1; }

// Custom concept:
template<typename T>
concept Printable = requires(T x, std::ostream& os) {
    { os << x } -> std::same_as<std::ostream&>;
};

void print(Printable auto x) { std::cout << x << '\n'; }

// volatile: tells compiler the variable may change outside observable control flow
// → compiler must read/write it at every access, no caching in registers

// Correct use: memory-mapped hardware registers
volatile uint32_t* const STATUS_REG = reinterpret_cast<volatile uint32_t*>(0x40000000);

while (*STATUS_REG & 0x01) { }   // without volatile: compiler may cache the read!
                                  // with volatile: re-reads the register every iteration

// WRONG: volatile is NOT a threading primitive
volatile bool stop = false;   // BAD: no synchronization guarantee between threads

// Correct: use std::atomic for inter-thread communication
std::atomic<bool> stop{false};   // guarantees visibility across threads + no data race

// The difference:
// volatile: prevents register caching; no memory ordering guarantees
// std::atomic: prevents register caching + memory ordering + no data race (defined behavior)

#include <atomic>
#include <string>

std::atomic<bool> ready{false};
std::string data;

// Thread 1 (producer)
void producer() {
    data = "important result";               // (1) write data
    ready.store(true, std::memory_order_release);  // (2) store with release
    // All writes BEFORE (2) are visible to any thread that acquires this store
}

// Thread 2 (consumer)
void consumer() {
    while (!ready.load(std::memory_order_acquire))  // (3) load with acquire
        ;
    // Guaranteed: (1) happened-before we get here
    std::cout << data;   // safe: data is visible
}

// constexpr function: CAN run at compile-time or runtime
constexpr int square(int n) { return n * n; }

constexpr int a = square(4);   // compile-time: a = 16 in rodata
int x = 5;
int b = square(x);             // runtime: regular function call

// consteval: MUST run at compile-time (immediate function)
consteval int cube(int n) { return n * n * n; }
constexpr int c = cube(3);    // OK: compile-time
// int d = cube(x);           // ERROR: x is not a constant expression

// constinit: ensures compile-time initialization, but NOT const (can change at runtime)
constinit int counter = 0;    // initialized before any code runs (no static init order fiasco)
counter++;                     // fine: constinit ≠ const

// Why constinit matters: prevents static initialization order fiasco
// constexpr global = always constinit + always const
// constinit global = always compile-time init, but mutable