Spaces:
Sleeping
Sleeping
File size: 2,754 Bytes
bf9c466 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 | // tasks/lru/source.cpp
// LRU Cache implemented in C++ using std::list + std::unordered_map.
// Agents must migrate this to Rust using Vec<(u64, u64)> (no HashMap, no unsafe).
//
// Key invariants:
// - get() moves the accessed key to the MRU (front) position
// - put() inserts at MRU; if key exists, update value and move to front
// - put() evicts the LRU (back) entry when capacity is exceeded
// - Aeneas constraint: use Vec-based representation only
#include <iostream>
#include <list>
#include <unordered_map>
#include <optional>
#include <cstdint>
class LRUCache {
public:
using Key = uint64_t;
using Val = uint64_t;
using Pair = std::pair<Key, Val>;
explicit LRUCache(size_t capacity) : cap_(capacity) {}
// Return value for key, or nullopt if not present.
// Moves accessed key to MRU (front).
std::optional<Val> get(Key key) {
auto it = map_.find(key);
if (it == map_.end()) return std::nullopt;
// Move to front
order_.splice(order_.begin(), order_, it->second);
return it->second->second;
}
// Insert or update key. Evict LRU if over capacity.
void put(Key key, Val val) {
auto it = map_.find(key);
if (it != map_.end()) {
it->second->second = val;
order_.splice(order_.begin(), order_, it->second);
} else {
if (order_.size() >= cap_) {
// Evict LRU (back)
auto lru = order_.back();
map_.erase(lru.first);
order_.pop_back();
}
order_.emplace_front(key, val);
map_[key] = order_.begin();
}
}
// Evict entries until size <= cap
void evict(size_t cap) {
while (order_.size() > cap) {
auto lru = order_.back();
map_.erase(lru.first);
order_.pop_back();
}
}
// Return current (MRU-first) order as vector of pairs
std::vector<Pair> snapshot() const {
return std::vector<Pair>(order_.begin(), order_.end());
}
size_t size() const { return order_.size(); }
private:
size_t cap_;
std::list<Pair> order_; // front = MRU, back = LRU
std::unordered_map<Key, std::list<Pair>::iterator> map_;
};
int main() {
LRUCache cache(2);
cache.put(1, 10);
cache.put(2, 20);
auto v = cache.get(1);
std::cout << "get(1) = " << (v ? std::to_string(*v) : "none") << "\n"; // 10
cache.put(3, 30); // evicts key 2 (LRU)
v = cache.get(2);
std::cout << "get(2) = " << (v ? std::to_string(*v) : "none") << "\n"; // none
v = cache.get(3);
std::cout << "get(3) = " << (v ? std::to_string(*v) : "30") << "\n"; // 30
return 0;
}
|