Rung 2 (M3) — Templated LRU Cache

Rung 2 is your first standalone repo. One artifact, one repo, one clean story: a header-mostly templated LRU cache with benchmarks. It is the first artifact on this ladder that a stranger on r/cpp will look at and form an opinion of your C++ from. Treat it accordingly.

Why an LRU cache? Because it is small enough to finish in a month at 10-15 hrs/week, but rich enough to demonstrate templates, iterators, std::list splicing, std::unordered_map, RAII, move semantics, exception safety, and benchmarking discipline. If you write one that is really good, it will get more r/cpp engagement than any other Rung 2 candidate topic — people love arguing about cache invariants.

What It Is

A public GitHub repo named lru-cache-cpp containing:

  • A header-only templated lru_cache<Key, Value, Hash = std::hash<Key>> class.

  • Constant-time get, put, and contains.

  • Configurable capacity, set at construction.

  • Optional TTL variant lru_cache_ttl<K,V> in a second header, using std::chrono.

  • A thread-safe wrapper synchronized_lru_cache<K,V> in a third header (mutex-based; the lock-free version waits for Rung 5).

  • Unit tests using Catch2 or GoogleTest, covering: capacity eviction, TTL expiry, exception safety on copy failure, move-only value types, custom hashers.

  • Benchmarks using google/benchmark or nanobench: single-thread throughput at capacities 1K / 10K / 100K / 1M.

  • A matplotlib-generated PNG chart of the benchmark results, committed to the repo at docs/benchmarks.png and rendered in the README.

  • CI on GitHub Actions: build + test + sanitizers (ASan, UBSan) on GCC and Clang.

Why It Matters (Employer Signal)

One line: “Understands templates + STL + benchmarking, and knows a data structure well enough to measure it.”

Many candidates can implement LRU on a whiteboard in Python. Very few of them publish a C++ one with move semantics that survives ASan/UBSan and includes a benchmark chart. This artifact separates “I know LRU exists” from “I can ship LRU in C++.” It is also a natural study talking point — you will get asked “walk me through how you built this” and having real numbers to point to changes the conversation.

Acceptance Checklist

  • Public GitHub repo named lru-cache-cpp.

  • Header-only — no .cpp files needed to consume the library. Include-what-you-use is clean.

  • get(key) -> std::optional<Value>, put(key, value), contains(key), size(), capacity(), clear().

  • Correctness: all unit tests pass under ASan and UBSan.

  • Correctness: LRU invariant is checked by tests (evict order after specific access patterns).

  • Move-only values (e.g. std::unique_ptr<T>) work.

  • Custom hasher works (test with a struct + custom std::hash specialization).

  • TTL variant expires entries lazily on access; a test verifies both lazy and manual evict_expired().

  • Benchmark: 1M put + 1M get operations complete in < 500ms on a modern laptop (document the machine in the README).

  • Benchmark chart committed as PNG under docs/ and rendered inline in README.

  • README has the 5 required sections plus a Benchmarks section with the chart and a table.

  • CI green: build + test on GCC-13 and Clang-17, with ASan+UBSan runs.

  • License: MIT.

  • Repo shared on r/cpp with [Show r/cpp] tag.

README Structure (Extending the Rung-1 5-Section Bar)

Use the same 5 sections you used at Rung 1 (What / Build / Run / Tests / Notes) and add:

  1. Benchmarks — The chart, the table, the machine specs. Explicitly show “1M ops in Xms.” Also show what happens as capacity scales (this reveals hash collision behavior).

  2. API — Public method list with one-line descriptions. Not full Doxygen — just a reference. Doxygen HTML is a nice stretch.

  3. Design notes — Two paragraphs. Why std::list<std::pair<K,V>> + std::unordered_map<K, iterator>. Why splice for O(1) reorder. What you would do differently if you needed lock-free (foreshadows Rung 5).

Where to Publish and Share

  • GitHub: public repo, MIT license, topic tags: cpp, cpp20, lru-cache, data-structures, header-only.

  • Reddit: r/cpp with prefix [Show r/cpp] in the title. Example title: “[Show r/cpp] Header-only C++20 LRU cache with TTL, benchmarks, and thread-safe wrapper.” r/cpp is stricter than r/cpp_questions — make sure CI is green and the README chart renders before posting.

  • GitHub topic search: submit to awesome-cpp via PR if your implementation is genuinely clean. This is a bonus, not required.

  • Do not post to HN yet. Save HN for hard-gate rungs.

Common Ways This Rung Fails

  • You forget that iterators into std::unordered_map are stable across insert, but references to buckets are not. This causes subtle bugs. Test carefully with iterator invalidation in mind.

  • You use std::list::remove instead of std::list::erase(iterator). The former is O(n) and destroys your benchmark. This is the #1 LRU mistake.

  • You benchmark with -O0. Meaningless. Benchmarks must run with -O3 and -DNDEBUG. Document the flags in the README.

  • You skip the sanitizers. Then the r/cpp comments find your use-after-free and it looks worse than not shipping.

  • You publish before the chart is committed. The chart is the reason people click. Do not publish without it.

  • You benchmark against std::map and claim victory. That is not a fair comparison. Benchmark against a naive std::list-only cache and against boost::compute::detail::lru_cache if you want a fair fight.

What Most People Get Wrong

They ship an LRU cache that works but has no benchmark. That reduces the artifact from “understands templates AND measures” to just “understands templates.” The benchmark is what upgrades this rung from a homework assignment to a portfolio piece. If you finish the code and skip the chart because “the code works,” you have missed half the point of this rung.

The second-most-common failure: they use std::list::iterator incorrectly and their eviction order silently breaks under certain access patterns. Write a specific test: put A, B, C, D at capacity 3, then get A, then put E — assert B is evicted, not A. If that test isn’t there, the invariant isn’t checked.

Extension Challenges (Only If M3 Has Slack)

  • Segmented LRU (SLRU): implement the two-queue variant used by Redis and MySQL. Nice study talking point.

  • Doxygen + GitHub Pages: generate API docs and host them on gh-pages. Adds a real docs link to your README.

  • Concept-constrained API: use C++20 concepts to constrain Key to be hashable and Value to be moveable. Compiler errors improve dramatically.

  • Fuzz test the API sequence with libFuzzer: random sequences of put/get/clear should never crash under ASan.