我正在尝试使用纯STL(不想使用Boost!)实现LFU(最近最少使用)缓存。
要求如下:
- 使用类似于
std::map
的Key
进行关联访问任何元素。 - 能够释放具有最低优先级(使用其
UsesCount
属性)的项目。 - 能够更新任何项目的优先级(
UsesCount
)。
问题如下:
- 如果我将
std::vector
用作项目(Key
,Value
,UsesCount
)的容器,将std::map
用作指向向量的迭代器的容器以进行关联访问,并将std::make_heap
,std::push_heap
和std::pop_heap
用作向量内的优先级队列实现,则堆操作后地图中的迭代器无效。 - 如果在上述配置中使用
std::list
(或std::map
)而不是std::vector
,则由于它们的迭代器不支持算术运算,无法编译std::make_heap
等操作。 - 如果我想使用
std::priority_queue
,则无法更新项目优先级。
问题如下:
- 我是否忽略了解决此问题的明显方法?
- 您能指向一些满足前面要求的LFU缓存的纯C++/STL实现作为示例吗?
感谢您的见解。
map
中,在即使插入/删除其他元素时也不会被移动。然后将映射迭代器放入您的向量中并构建一个堆。您可能仍然缺少高效更新项目优先级的能力,因此这不是一个答案。 - Steve Jessopstd::vector
的std::map
迭代器,我该如何定义它们的比较运算符,以便在插入项目或更新UsesCount
后查看指针对象内部的UsesCount
属性,以便能够使用std::make_heap
修复堆? - Blackhexbool operator()(MapIter a, MapIterB) { return a->second.UseCount < b->second.UseCount; }
- Useless