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

Question

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

但是元素可以多次使用，并且在再次使用时应返回队列的顶部，以便缓存真正删除上一次使用的元素。

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

编辑：我不知道名字，但这或多或少是Least recently used algorithms。

Answer 1

看来这是一个简单的LRU缓存问题。这是一些有助于您的代码

class LRUCache { 
public:
LRUCache(const LRUCache& other) = delete;
LRUCache& operator=(LRUCache & other) = delete;       

LRUCache(int capacity) {   
    size = capacity;
}

int get(int key) {
    auto it = mp.find(key);
    if(it != mp.end())
    {
        int val = it->second.first;
        use(it);
        return val;
    }
    return -1;
}

void put(int key, int value) {
    auto it = mp.find(key);
    if(it != mp.end())
    {
        it->second.first = value;
        use(it);
        return;
    }

    if(mp.size() == size)
    {
        // evict
        mp.erase(lst.back());
        lst.pop_back();
    }
    // add new
    lst.push_front(key);
    mp[key] = {value,lst.begin()};  
}

private:
int size = 0;
unordered_map<int,pair<int,list<int>::iterator>> mp;
list<int> lst;

void use(unordered_map<int,pair<int,list<int>::iterator>>::iterator& it)
{
    lst.erase(it->second.second); // erase element from the list
    lst.push_front(it->first); // push key to front of the list
    it->second.second = lst.begin();
}
};

Answer 2

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

我找到了多集here的示例。 Multiset允许重复，而set不允许重复，因此这更适合您的账单。

基于相同的想法，您可以具有类似的结构-

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

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

Answer 3

我们可以通过映射和双向链接的组合来做到这一点。双链表将维护最后使用的ID。该映射消除了重复的唯一ID。如果缓存大小达到限制，则在双向链接列表中找到第一个元素，然后从映射中删除该唯一ID，并删除列表的head元素。如果使用唯一的ID，则在map中查找ID的值，然后将节点移至列表的开头。