c++ - 如何在C++中实现一个唯一id的队列，其中元素可以是 "bumped"到顶部？

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();
}
};