LRU缓存算法的复杂度

Question

我面前有一个任务是实现LRU缓存。而系统中最长的操作应该需要O(log (n))。作为我的缓存，我使用 std :: MAP。我仍然需要第二个容器来存储密钥 + 创建时间 - 按时间排序。当我需要更新缓存地址时，它应该在某个地方：

年龄最大的成员必须自然居住在 container.begin()。

我只会用STL。

列表 - 不适合我。

list.find() - O (n)

优先队列 - 删除未实现的项目。

我认为它可以理想地存储在 std::set;

std::set<pair<KEY, TIME>>;

排序std::set:

struct compare
{
    bool operator ()(const pair<K, TIME> &a, const pair<K, TIME> &b)
    {
        return a.second < b.second;
    }
};

并在 std :: set 中找到一个键来编写查找对中第一个元素的函数 - std::set<pair<KEY, TIME>>;。

你怎么看？谁能告诉我这是否符合我指定的复杂性要求？

Answer 1

是的，您可以使用 map 加上 set 来获得 deleting/updating/inserting 的复杂度为 O( logn).

map 存储 key,value 对。
set 应该按此顺序存储 time,key（你做的相反）。当缓存已满并且您想删除一个键时，它将对应于 it = myset.begin() 指向的集合中的元素。

说过可以使用哈希+双链表提高性能。

The complexity of the LRU cache algorithm