LRUCache

2024-11-08 18:54:52

LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最少使用的页面予以淘汰。

Cache的容量有限，因此当Cache的容量用完后，而又有新的内容需要添加进来时，就需要挑选并舍弃原有的部分内容，从而腾出空间来放新内容。LRU Cache 的替换原则就是将最近最少使用的内容替换掉。其实，LRU译成最久未使用会更形象，因为该算法每次替换掉的就是一段时间内最久没有使用过的内容。

list::splice

void splice (iterator position, list& x);
void splice (const_iterator position, list& x);
void splice (const_iterator position, list&& x);

void splice (iterator position, list& x, iterator i);
void splice (const_iterator position, list& x, const_iterator i);
void splice (const_iterator position, list&& x, const_iterator i);

void splice (iterator position, list& x, iterator first, iterator last);
void splice (const_iterator position, list& x, const_iterator first, const_iterator last);
void splice (const_iterator position, list&& x, const_iterator first, const_iterator last);

在C++的std::list容器中，splice函数用于将一个列表（list）中的元素移动到另一个列表的指定位置，而不复制它们。这是通过调整内部指针（或节点链接）来实现的，因此是一个高效的操作。以下是您提到的三个splice函数重载的简要说明：

void splice (iterator position, list& x);

此函数将整个列表x中的所有元素移动到当前列表的position位置。移动后，列表x将变为空，而当前列表将在position处包含原列表x的所有元素。如果position是当前列表的end()迭代器，则x的元素将被添加到当前列表的末尾。
void splice (iterator position, list& x, iterator i);

此函数将单个元素从列表x移动到当前列表的position位置。元素是由迭代器i指定的，它必须指向列表x中的一个有效元素。移动后，迭代器i将不再指向列表x中的任何元素（因为它现在属于当前列表）。
void splice (iterator position, list& x, iterator first, iterator last);

此函数将列表x中由迭代器范围[first, last)指定的元素移动到当前列表的position位置。这个范围包括first指向的元素，但不包括last指向的元素。移动后，这个范围内的元素将不再属于列表x，而是成为当前列表的一部分。如果first和last相等，则不移动任何元素。

需要注意的是，在所有这些情况下，splice操作都不会复制元素，而是通过重新链接节点来移动它们。因此，这是一个常数时间操作（O(1)），尽管遍历列表以找到迭代器所指向的元素可能需要线性时间（O(n)），但这与splice函数本身的效率无关。此外，splice函数要求所有涉及的迭代器都是有效的，并且属于指定的列表（在调用splice之前）。

146. LRU 缓存 - 力扣（LeetCode）

/**
 * Your LRUCache object will be instantiated and called as such: // 实例化和调用
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */
class LRUCache {
    typedef list<pair<int, int>>::iterator ListIt;
    int _capacity;
    unordered_map<int, ListIt> _hashmap;
    list<pair<int, int>> _LRUlist;

public:
    LRUCache(int capacity) : _capacity(capacity) {}

    int get(int key) {
        auto it = _hashmap.find(key);
        if (it != _hashmap.end()) {
            // 将该关键字移动到LRU队列头
            ListIt listit = it->second;
            _LRUlist.splice(_LRUlist.begin(), _LRUlist, listit);
            return listit->second;
        } else
            return -1;
    }

    void put(int key, int value) {
        auto it = _hashmap.find(key);
        if (it == _hashmap.end()) {
            // 判满，如果满了逐出最久未使用的关键字
            if (_hashmap.size() == _capacity) {
                pair<int, int> back = _LRUlist.back();
                _hashmap.erase(back.first);
                _LRUlist.pop_back();
            }
            // 将关键字插入到LRU队列头
            _LRUlist.push_front(make_pair(key, value));
            _hashmap.insert(make_pair(key, _LRUlist.begin()));

        } else {
            // 找到了更新其value值，并将该关键字移动到LRU队列头
            ListIt listit = it->second;
            listit->second = value;
            _LRUlist.splice(_LRUlist.begin(), _LRUlist, listit);
        }
    }
};

码农公寓

相关文章