c++ - 如何实现一个唯一ID队列，其中元素可以在C++中“碰撞”到顶部？

Question

我正在实现一个元素缓存（由唯一 ID 表示），并保留最大数量的元素。当我达到最大尺寸时删除最后使用的元素。所以它看起来像一个队列，但具有独特的元素，因为我不想多次添加相同的 id。

但是元素可以被多次使用，并且在再次使用时应该回到队列的顶部，以便缓存真正删除最后使用的元素。

我真的不知道该怎么做。我的第一个猜测是使用 std::list，因此手动管理元素的唯一性和“移至顶部”操作。
有没有更聪明的方法来实现这一目标？

编辑：我不知道名字，但这或多或少是最近最少使用的算法。

标签： c++c++11stllru

Answer 1

也许您正在寻找std::set带有自定义比较运算符的？

我在这里找到了一个 multiset 的例子。Multiset 允许重复，set 不允许，所以这更适合您的账单。

借鉴相同的想法，您可以拥有这样的结构 -

struct Elem
{
    std::string UID;
    std::chrono::time_point lastUsed;
}

lastUsed如果您重新使用缓存中的项目，请更改参数。