LRU Cache

Recency is an ordering of accesses, not insertion timestamps. A hit and an update both move a key to the most recent end. A miss changes nothing. Separate value lookup from recency links so evicting the oldest entry removes both representations.

std::list<std::pair<std::string,Int>> order;
// list::splice moves a node without invalidating its iterator.

A hash map to list iterators supports expected O(1) operations; vector erasure or list-only scans are useful baselines but remain O(n). Iterator validity is part of the design: erasing a node invalidates the stored iterator for that key. Capacity zero should accept validated puts as no-ops. Return items() by value rather than exposing the list, so users cannot corrupt ordering. If using map-to-iterator state, default copying a cache is unsafe because copied iterators still target the original list; disable copying or rebuild the index.

C++ contract conventions: numeric values use signed Int (long long); all inputs and intermediate arithmetic are within its representable range. Opt<T> means std::optional<T> and absence is std::nullopt; Vec<T> means std::vector<T>. Invalid documented arguments throw std::invalid_argument. Inputs passed by const reference remain caller owned. Returned containers and records own their contents. Calls use the declared C++ parameter types. Implicit conversions performed by the caller are outside the runtime validation contract. Unless a lesson states otherwise, string ordering is lexicographic over Unicode code points (Text) or UTF-8 identifiers (std::string).

The C++ cache stores Int values and its optional fallback is also Int. This deliberately narrows an arbitrary-object default to a statically typed optional; absence remains distinct from any stored integer.