Phase 1 Projects — Building Under Pressure¶

“Reading about modern C++ makes you literate. Shipping three projects with sanitizers clean and benchmarks passing makes you employable.”

Every concept in Phase 1 must land in code you can point to. Three projects do that job. Each one is scoped to be finishable in the target weeks with 10–15 hours of focused work, produces a portfolio-grade GitHub repository, and forces you to confront the exact idioms this phase teaches: templates, ownership, moves, RAII, thread safety, and modern error handling.

Do not skip the acceptance criteria. “It works on my machine” is not shippable; “it passes tests, benchmarks, ASan, and UBSan” is. Publish each project to GitHub with a README that includes design rationale, benchmark numbers with a chart, and a short paragraph on what you’d do differently next time. That reflection is what turns exercises into portfolio pieces.

P1.1 — Templated LRU Cache (Week 6)¶

Goal¶

Build an LRUCache<K, V> class template supporting O(1) get and put operations with least-recently-used eviction. Single-threaded for now — thread safety comes in P1.3.

Interface¶

template<class K, class V>
class LRUCache {
public:
    explicit LRUCache(std::size_t capacity);

    std::optional<V> get(const K& key);           // moves entry to MRU
    void             put(K key, V value);         // insert or update, evicts LRU on overflow

    std::size_t size()     const noexcept;
    std::size_t capacity() const noexcept;
    bool        empty()    const noexcept;
    void        clear();

    // Optional: iterate MRU→LRU
    // begin() / end() returning a range-compatible iterator
};

Design¶

The classic O(1) LRU is std::list<std::pair<K, V>> + std::unordered_map<K, std::list<...>::iterator>. On get, the list node is moved to the front via splice (no allocation). On put overflow, the back of the list is popped and the corresponding map entry removed.

template<class K, class V>
class LRUCache {
    using ListEntry = std::pair<K, V>;
    using ListType  = std::list<ListEntry>;
    using MapType   = std::unordered_map<K, typename ListType::iterator>;

    std::size_t capacity_;
    ListType    order_;         // front = MRU, back = LRU
    MapType     lookup_;

public:
    std::optional<V> get(const K& key) {
        auto it = lookup_.find(key);
        if (it == lookup_.end()) return std::nullopt;
        order_.splice(order_.begin(), order_, it->second);   // move to front, O(1)
        return it->second->second;
    }

    void put(K key, V value) {
        if (auto it = lookup_.find(key); it != lookup_.end()) {
            it->second->second = std::move(value);
            order_.splice(order_.begin(), order_, it->second);
            return;
        }
        if (order_.size() >= capacity_) {
            lookup_.erase(order_.back().first);
            order_.pop_back();
        }
        order_.emplace_front(key, std::move(value));
        lookup_.emplace(std::move(key), order_.begin());
    }
};

Read this three times. Notice: std::list::splice moves a node between lists (or within one list) without allocation or copy — it just relinks pointers. That’s the O(1) move-to-front. Notice: std::unordered_map stores iterators, which for std::list are stable across other operations. That’s why we chose list and not deque.

Acceptance Criteria¶

Correctness. Unit tests with GoogleTest or Catch2 cover:
- Basic get/put/eviction ordering.
- Update semantics (putting an existing key does not evict).
- Move-only value types (std::unique_ptr<T> as V).
- Copyable key types.
- Boundary: capacity 1, capacity 0 (should throw or assert).
Performance. Benchmark with google-benchmark or a simple std::chrono harness:
- 1 million random get/put operations on a cache of capacity 10 000, uniform key distribution over 100 000 keys.
- Target: < 500 ms on Apple M-series silicon. Below 300 ms is a good result.
Sanitizer clean. Build and run tests under -fsanitize=address,undefined. No reports.
Warnings clean. Compile with -Wall -Wextra -Wpedantic -Wshadow -Wconversion — zero warnings.
Modern C++. Rule of zero (rely on std::list and std::unordered_map compiler-generated moves). No raw new/delete. std::optional for get return.

Expected Traps¶

Iterator invalidation in unordered_map. Rehashing invalidates iterators. You store list iterators (stable) in the map — not map iterators. Reversed, you’d corrupt state.
Moving from the key twice. In put, key is moved into lookup_.emplace. Don’t reference key after that.
splice semantics. list::splice(pos, source_list, iter) moves iter’s node from source_list before pos. When source_list == *this, it’s a self-move (still valid, still O(1)).
Hash function for custom keys. If K is a user type, you must provide std::hash<K> or pass a custom hasher. Skipping this produces a cryptic error.

Extension Challenges¶

TTL support. Add per-entry expiry. On get, check std::chrono::steady_clock::now() against a stored deadline; expired entries return std::nullopt and are removed.
Sharding. For a preview of thread safety, split the cache into N shards keyed by std::hash(key) % N. Each shard has its own mutex. This is exactly how production caches like Caffeine and Guava work.
Segmented LRU (SLRU). Two internal LRUs — a small “protected” one and a larger “probationary” one. Entries promote on second hit. Better hit rate for scan-resistant workloads.
Custom hasher. Template the class on a Hasher type parameter that defaults to std::hash<K>, allowing users to plug in absl::Hash or a domain-specific hash.

Publish¶

Repository: lru-cache-cpp on your GitHub.
README sections: overview, complexity analysis, benchmark numbers with a chart (generate with matplotlib or gnuplot — hit rate vs capacity, throughput vs cache size), build instructions, running tests, extension ideas.
CI: GitHub Actions running the tests and benchmarks on push. ubuntu-latest with GCC 13 and Clang 17.

P1.2 — Simple JSON Parser (Weeks 8–9)¶

Goal¶

Build a recursive-descent JSON parser from scratch — no external dependencies — that handles the full JSON grammar (objects, arrays, strings, numbers, booleans, null), reports errors with line and column, and exposes a Value type that models the JSON data model cleanly.

Interface¶

namespace mjson {

struct Value;
using Object = std::map<std::string, Value>;      // std::map for stable ordering; use unordered_map if perf matters more than order
using Array  = std::vector<Value>;
using Null   = std::monostate;

struct Value {
    std::variant<Null, bool, double, std::string, Array, Object> data;

    // Accessors
    bool           is_null()   const noexcept;
    bool           is_bool()   const noexcept;
    // ... etc.
    const Object&  as_object() const;              // throws if wrong type
    const Array&   as_array()  const;
    const std::string& as_string() const;
    double         as_number() const;
    bool           as_bool()   const;
};

struct ParseError {
    std::string message;
    std::size_t line;
    std::size_t column;
};

std::expected<Value, ParseError> parse(std::string_view input);

}  // namespace mjson

Design¶

Recursive-descent parser with a Lexer that produces tokens on demand and a Parser that consumes them via recursive functions: parse_value, parse_object, parse_array, parse_string, parse_number. Line/column tracking lives in the lexer.

Key design decisions:

std::variant for the value type. Six alternatives model JSON exactly. std::monostate represents null cleanly.
std::string_view inside the lexer, std::string in the final Value. The lexer views the input; the parser copies into owning strings.
std::expected<Value, ParseError> as the top-level return. Errors propagate without exceptions; the caller decides.
Recursion limit. Add a max-depth check (e.g., 128) to prevent stack overflow on adversarial input.

class Parser {
    std::string_view src_;
    std::size_t      pos_ = 0;
    std::size_t      line_ = 1;
    std::size_t      col_  = 1;
    int              depth_ = 0;
    static constexpr int MaxDepth = 128;

    std::expected<Value, ParseError> parse_value();
    std::expected<Value, ParseError> parse_object();
    std::expected<Value, ParseError> parse_array();
    std::expected<std::string, ParseError> parse_string();
    std::expected<double,      ParseError> parse_number();
    void skip_whitespace();
    void advance();               // updates pos_, line_, col_
    // ...
};

Acceptance Criteria¶

Correctness. 10 test JSONs pass round-trip:
- Empty object, empty array, deeply nested (10+ levels), unicode strings (\uXXXX escapes), scientific notation, negative numbers, exact null/true/false, arrays of mixed types, whitespace in every legal position, JSON conformance suite subset (e.g., a few from JSONTestSuite).
Error reporting. For 10 malformed JSONs, error messages include:
- The line and column of the error.
- What was expected (“expected } or ,”).
- What was seen. Test that error messages are stable and grep-able.
No external dependencies. No third-party libraries. Only the C++ standard library. -std=c++23 for std::expected.
Sanitizer clean. ASan + UBSan on all test inputs.
Fuzz test. Run libFuzzer for at least 30 minutes on the parser entry point. No crashes, no memory errors.

Expected Traps¶

Number parsing. JSON numbers are a strict subset of C++ literal syntax — no leading +, no leading zero except 0 itself, no hex, no NaN/Infinity. Do not use std::stod directly — it’s too permissive. Use std::from_chars (C++17) which does the right thing.
String escapes. \u needs 4 hex digits. Surrogate pairs (\uD83D\uDE00 → emoji) require decoding two consecutive \uXXXX sequences into a single code point, then UTF-8 encoding. Skip on version 1; add for extension.
Recursive stack overflow. Adversarial input like [[[[[[[[[[[[[[[[[[[[...]]]]]]]]]]]]]]]]]]]] — 10K deep — blows the stack. The max-depth check saves you.
Line/column accuracy after \r\n. Handle both \n and \r\n as newlines. Test explicitly.
std::variant heavy visitation. Using std::visit on every access is idiomatic but slow. For accessors like as_object(), std::get_if<Object>(&data) is faster.

Extension Challenges¶

Pretty-printer. std::string serialize(const Value&, int indent = 2); — the inverse.
JSON Pointer (RFC 6901) evaluator. Given a Value and a path like /users/0/name, return the sub-value.
Streaming parser. Instead of holding the entire input, consume from std::istream chunk-by-chunk. Trickier than it sounds; use a state machine.
SAX-style callback API. Instead of building a tree, invoke user callbacks on each token (on_object_start, on_key, on_value, …). Faster for large inputs where the caller wants only a subset.
Comparison with nlohmann::json and simdjson. Benchmark against both on a 1MB and 100MB input. Do not expect to beat simdjson (it uses SIMD tricks that took years). Do expect to be within 5–10x of nlohmann::json.

Publish¶

Repository: mjson on your GitHub.
README sections: grammar (as a BNF snippet), design rationale, error message examples, benchmark table (parse time on 1KB / 100KB / 1MB / 10MB inputs vs nlohmann::json), test coverage, fuzz-testing log.
CI: GitHub Actions with matrix builds (GCC, Clang) and ASan/UBSan configurations.

P1.3 — Thread-Safe Object Pool (Weeks 11–12)¶

Goal¶

Build a templated ObjectPool<T> that preallocates a fixed number of objects, hands them out via RAII “checkouts,” and reclaims them on scope exit. Thread-safe via std::mutex. Benchmark against direct new/delete and prove the speedup.

Interface¶

template<class T>
class ObjectPool {
public:
    class Handle {                        // RAII checkout token; returns object on destruction
    public:
        T& operator*();
        T* operator->();
        ~Handle();                        // returns object to pool
        // move-only
    };

    explicit ObjectPool(std::size_t initial_size);

    template<class... Args>
    Handle acquire(Args&&... args);        // constructs (or reuses) a T
    // Blocks if pool is empty and grow=false; or grows the pool if grow=true.

    std::size_t available() const;
    std::size_t total()     const;
};

Design¶

Storage. std::vector<std::unique_ptr<T>> for owned slots + std::vector<T*> (or a free-list intrusive linked list) for available pointers.
Synchronization. std::mutex protecting the free list. On acquire, lock, pop a pointer, unlock. On Handle::~Handle, lock, push, unlock, notify_one on a std::condition_variable if any thread is waiting.
RAII checkout. Handle is move-only, non-copyable. Its destructor returns the object. Users cannot leak by forgetting to release — same guarantee as unique_ptr.
Object reuse. On acquire, if the object needs reset, invoke T::reset() or reconstruct via placement-new. For simple types, just reuse in place.
Perfect forwarding. acquire(Args&&...) forwards to T’s constructor. For pool reuse, you may need to destroy + placement-new-construct in-place; for a simpler MVP, only construct once (at pool creation) and reuse without reconstruction.

template<class T>
class ObjectPool {
    struct Slot {
        alignas(T) std::byte storage[sizeof(T)];
        bool constructed = false;
    };

    std::vector<Slot>      slots_;
    std::vector<Slot*>     free_;
    mutable std::mutex     mu_;
    std::condition_variable cv_;

public:
    class Handle {
        ObjectPool*  pool_ = nullptr;
        Slot*        slot_ = nullptr;
    public:
        Handle(ObjectPool* p, Slot* s) : pool_(p), slot_(s) {}
        Handle(Handle&& other) noexcept
            : pool_(std::exchange(other.pool_, nullptr))
            , slot_(std::exchange(other.slot_, nullptr)) {}
        Handle& operator=(Handle&&) noexcept;
        Handle(const Handle&) = delete;
        Handle& operator=(const Handle&) = delete;

        T& operator*()  { return *std::launder(reinterpret_cast<T*>(slot_->storage)); }
        T* operator->() { return &**this; }

        ~Handle() {
            if (slot_ && pool_) pool_->release(slot_);
        }
    };

    template<class... Args>
    Handle acquire(Args&&... args) {
        std::unique_lock lock(mu_);
        cv_.wait(lock, [this] { return !free_.empty(); });
        auto* slot = free_.back();
        free_.pop_back();
        lock.unlock();

        if (slot->constructed) {
            std::destroy_at(reinterpret_cast<T*>(slot->storage));
        }
        std::construct_at(reinterpret_cast<T*>(slot->storage), std::forward<Args>(args)...);
        slot->constructed = true;

        return Handle{this, slot};
    }

private:
    void release(Slot* slot) {
        std::lock_guard lock(mu_);
        free_.push_back(slot);
        cv_.notify_one();
    }
};

Read the storage discipline carefully. alignas(T) std::byte storage[sizeof(T)] reserves aligned bytes for a T without constructing one. std::construct_at and std::destroy_at (C++20) do explicit placement-new and destroy. std::launder addresses the pointer-provenance rule when reading from placement-new storage — it says “even though I obtained this pointer by casting, please give me a pointer that refers to the just-constructed object.” This is dense, but it’s the correct pattern.

Acceptance Criteria¶

Correctness. Unit tests cover:
- Sequential acquire/release preserves object identity where useful.
- Handle is move-only and correctly transfers ownership.
- Pool blocks correctly when exhausted, unblocks on release.
- Multithreaded acquire/release across 8 threads with 100K ops each yields no data corruption and no lost objects.
Sanitizer clean.
- ASan clean on all tests.
- UBSan clean (no misaligned access, no invalid placement).
- TSan clean — this is the critical one. Any data race here is a real bug.
Benchmark.
- Allocate + free 10 000 objects (a struct with a 1KB payload). Measure:
  - Baseline: direct new / delete per allocation.
  - Pool: pool.acquire() per allocation.
- Target: pool is >= 2x faster than new/delete on single-threaded workload. On multi-threaded contention (say 4 threads), the pool may lose to malloc’s per-thread caches — that’s an interesting finding, not a failure.
Documentation. README with:
- Design rationale.
- Benchmark chart (throughput ops/sec) at 1, 2, 4, 8 threads.
- When to use a pool and when not to (spoiler: modern malloc implementations like jemalloc and tcmalloc have per-thread caches that make simple pools less compelling than 10 years ago).
Modern C++.
- std::mutex, std::condition_variable, std::unique_lock, std::lock_guard.
- RAII Handle, move-only.
- std::construct_at, std::destroy_at, std::launder for placement new correctness.
- noexcept on move operations.

Expected Traps¶

Placement-new pitfalls. Forgetting std::destroy_at before reconstructing leaks the previous object’s resources.
Alignment. Raw byte storage must be alignas(T). Miss this and UBSan flags misaligned loads.
Data races on available() and total(). These read shared state. Either take the lock, use atomics, or document that they are approximate.
condition_variable spurious wakeups. Always use the predicate form of cv_.wait(lock, pred). Never cv_.wait(lock) alone.
Deadlock in release path. If Handle::~Handle is called while holding a lock owned by the caller, and release() acquires the same mutex — deadlock. Keep locks tight and never call user code under a lock.
Exceptions in acquire. If T’s constructor throws under placement-new, the slot must return to free_ before the exception propagates. Use a scope guard.

Extension Challenges¶

Lock-free variant. Replace the mutex with a lock-free stack of free slots using std::atomic<Slot*> and CAS. Measure. Compare to the mutex version. This is hard — ABA problems, memory reclamation. Do it only after you finish the mutex version.
Adaptive sizing. Grow the pool when starved, shrink when idle for N seconds.
Per-thread free lists. One free list per thread, fall back to a global free list. Approaches jemalloc-style scaling.
std::pmr integration. Wrap the pool as a std::pmr::memory_resource and use it as an allocator for STL containers. Now std::vector<T, std::pmr::polymorphic_allocator<T>> pulls from your pool.

Publish¶

Repository: object-pool-cpp on your GitHub.
README sections: motivation (when pools beat malloc), API, design (alignment, placement-new, RAII), benchmarks with chart (throughput vs threads, throughput vs object size), sanitizer proof (screenshots or CI badges).
CI: GitHub Actions running -fsanitize=address, -fsanitize=undefined, -fsanitize=thread builds separately.

Cross-Project Discipline¶

Every project has, without exception:¶

A single CMakeLists.txt using target_compile_features(target PUBLIC cxx_std_20) (or cxx_std_23 for P1.2), never global CMAKE_CXX_STANDARD.
A tests/ directory with GoogleTest or Catch2. Run via ctest.
A benchmarks/ directory with google-benchmark or a hand-rolled std::chrono harness.
A .clang-format file. Format on commit. No debates about brace placement.
A README.md with build instructions, acceptance criteria checklist (all boxes ticked), and benchmark chart.
CI on GitHub Actions running tests and sanitizers.
A LICENSE (MIT unless you have a reason). Portfolio pieces without licenses are legally awkward.

What every project’s README must show at the top¶

Purpose in one sentence.
Benchmark headline number (“1M ops in 320ms”, “parses 100MB in 1.2s”, “2.7x faster than new/delete”).
Build one-liner.
Chart or table.

Recruiters and hiring engineers spend ~30 seconds on your README before deciding whether to keep reading. Make the first 30 seconds count.

Grading Yourself¶

At the end of Week 12, self-assess each project on a 1–10 scale for:

Correctness — all acceptance criteria met, tests green.
Modernity — no raw new/delete, RAII throughout, std::optional/std::expected used correctly, rule-of-zero where possible.
Performance — benchmark targets hit or documented misses with explanation.
Cleanliness — sanitizers clean, warnings zero, format consistent.
Documentation — a hiring manager reading only the README understands what the project does and why it’s non-trivial.

Any project below 7/10 on any axis gets one weekend of remedial work before moving to Phase 2. Do not accumulate debt.

Return to Phase 1 README · Next phase: Phase 2 (coming in the roadmap after Phase 1 exit)