C++实现一个简洁的 LRU 缓存

template <typename T, typename KeyT = int> 
struct lru_cache_t {
	size_t sz_;
	std::list<std::pair<KeyT, T>> cache_;

	using ListIt = typename std::list<std::pair<KeyT, T>>::iterator;
	std::unordered_map<KeyT, ListIt> hash_;

	lru_cache_t(size_t sz) : sz_(sz) {}

	bool full() const { return (cache_.size() == sz_); }

	template <typename F> bool lookup_update(KeyT key, F slow_get_page) {
		auto hit = hash_.find(key);
		if (hit == hash_.end()) {
			if (full()) {
				hash_.erase(cache_.back().first);
				cache_.pop_back();
			}
			cache_.emplace_front(key, slow_get_page(key));
			hash_.emplace(key, cache_.begin());
			return false;
		}

		auto eltit = hit->second;
		cache_.splice(cache_.begin(), cache_, eltit);
		return true;
	}
};

实现关键点：使用 std::list 存储避免 resize，使用 std::unordered_map 实现快速查找。使用 splice 方法将命中的元素移动到链表头部。

int slow_get_page_int(int key) { return key; }

int main() {
    int hits = 0;
    int n;
    size_t m;

    std::cin >> m >> n;
    assert(std::cin.good());
    caches::lru_cache_t<int> c{m};

    for (int i = 0; i < n; ++i) {
        int q;
        std::cin >> q;
        assert(std::cin.good());
        if (c.lookup_update(q, slow_get_page_int))
            hits += 1;
    }

    std::cout << hits << std::endl;
}

资料：

• LRU and LFU in C++