一个简单的带TTL的LRU的C++实现

实际上这个实现还是有点小问题，因为cv.notify之后不一定能保证线程立刻执行，因此有可能进入put方法后有个元素过期导致空了一个位置出来，因此在判断元素满了的分支里还需要手动清理一下，但是懒得改了（

using namespace std::chrono;
using namespace std::chrono_literals;class LRUCache {
private:struct Node {int key, value;steady_clock::time_point ttl;int version;std::shared_ptr<Node> next;std::weak_ptr<Node> prev;Node(): key(0), value(0), ttl(steady_clock::time_point{}), version(0), next(nullptr) {prev.reset();}Node(int x, int y): key(x), value(y), ttl(steady_clock::time_point{}), version(0), next(nullptr) {prev.reset();}Node(int x, int y, int z): key(x), value(y), ttl(steady_clock::time_point{}), version(z), next(nullptr) {prev.reset();}};struct Task {steady_clock::time_point ttl;int key, version;bool operator>(const Task& rhs) const {return ttl > rhs.ttl;}};std::shared_ptr<Node> head, tail;int capacity;std::unordered_map<int, std::shared_ptr<Node>> mp;bool stop;std::thread worker;std::recursive_mutex mutex;std::condition_variable_any cv;std::priority_queue<Task, std::vector<Task>, std::greater<Task>> que;void detach(std::shared_ptr<Node>& cur) {auto prev = cur->prev.lock();prev->next = cur->next;cur->next->prev = prev;cur->next = nullptr;cur->prev.reset();}void insert_after(std::shared_ptr<Node>& prev, std::shared_ptr<Node>& cur) {cur->next = prev->next;cur->prev = prev;prev->next->prev = cur;prev->next = cur;}bool check_key(int key) {return mp.count(key) && (mp[key]->ttl == steady_clock::time_point{} || steady_clock::now() < mp[key]->ttl);}void run() {while (true) {std::unique_lock<std::recursive_mutex> lock(mutex);cv.wait(lock, [this]{ return stop || !que.empty(); });if (stop) break;while (!que.empty() && que.top().ttl < steady_clock::now()) {const auto [_, key, version] = que.top();que.pop();if (mp.count(key) && mp[key]->version == version) {auto cur = mp[key];mp.erase(key);detach(cur);}}if (!que.empty()) {cv.wait_until(lock, que.top().ttl);}}}public:LRUCache(int capacity) {this->capacity = capacity;stop = false;worker = std::thread(&LRUCache::run, this);head = std::make_shared<Node>();tail = std::make_shared<Node>();head->next = tail;tail->prev = head;}~LRUCache() {{std::lock_guard<std::recursive_mutex> lock(mutex);stop = true;cv.notify_one();}if (worker.joinable()) {worker.join();}}int get(int key) {std::lock_guard<std::recursive_mutex> lock(mutex);if (check_key(key)) {auto cur = mp[key];detach(cur);insert_after(head, cur);return cur->value;}return -1;}void put(int key, int value) {std::lock_guard<std::recursive_mutex> lock(mutex);if (mp.count(key)) {auto cur = mp[key];detach(cur);insert_after(head, cur);cur->value = value;cur->version++;cur->ttl = {};} else if (mp.size() < capacity) {auto cur = std::make_shared<Node>(key, value, 0);mp[key] = cur;insert_after(head, cur);} else {auto cur = tail->prev.lock();detach(cur);insert_after(head, cur);mp.erase(cur->key);mp[key] = cur;cur->key = key; cur->value = value;cur->ttl = {}; cur->version = 0;}cv.notify_one();}void put(int key, int value, steady_clock::duration ttl) {std::lock_guard<std::recursive_mutex> lock(mutex);put(key, value);auto cur = mp[key];cur->ttl = steady_clock::now() + ttl;que.push({cur->ttl, key, cur->version});cv.notify_one();}
};