LRU Cache

Prototype: implement touch_order(keys, key). Assume keys contains distinct nonempty strings and key is a nonempty string. Return a fresh list in oldest-to-newest order, moving an existing key to the end or appending a missing key. Do not mutate keys. There is no capacity limit at this stage.

Final: implement LRUCache(capacity). Capacity must be a nonnegative integer, within the declared C++ numeric type; invalid capacity raises std::invalid_argument. Keys must be nonempty strings. Stored values must be integers within the declared C++ numeric type; negative values are valid. Invalid keys or stored values raise std::invalid_argument before any state or order change.

put(key, value) returns nullopt, inserts or updates the value, and makes the key most recent. Evict the least recent key only if needed. At zero capacity, valid puts are no-ops. get(key, default=nullopt) returns the value and refreshes recency on a hit; a miss returns the supplied default without changing state. Defaults may be any object. erase(key) returns true if removed and false if absent; it does not refresh other keys. items() returns a fresh list of (key, value) tuples ordered least recent first. Instances own independent state. Repeated updates occupy one entry.

The public C++ API below is authoritative for field types and return values. erase is used where another language might use a method named delete, because delete is a C++ keyword. Returned records are value snapshots with the documented named fields; mutating a record or its nested vectors cannot affect the service.

inline Strings touch_order(const Strings& keys,const std::string& key);
class LRUCache { public:
 explicit LRUCache(Int capacity);
 void put(const std::string& key,Int value);
 Opt<Int> get(const std::string& key,Opt<Int> fallback=std::nullopt);
 bool erase(const std::string& key);
 Vec<std::pair<std::string,Int>> items() const;
};

Compile and run from this directory:

c++ -std=c++20 -O2 -Wall -Wextra -pedantic -pthread main.cpp -o practice
./practice --stage prototype
./practice --stage final

Edit exercise.hpp. Both stages start unfinished and must report failures until implemented. Keep main.cpp as the executable contract. The runner returns nonzero for a failed check, an unexpected exception, an invalid stage, or an empty suite. C++20 and only the standard library are required.