当前位置：首页 > news >正文

LeetCode 146 LRU Cache

news 来源：原创 2024/5/3 14:10:12

本文记录本人在解决 LeetCode 第146题 LRU Cache 过程中的收获。主要是增加了对 C++ STL list 容器的了解。点击该链接可跳转到 LeetCode 此题目处。本文借鉴了花花酱的个人网站的讲解和代码。本文相当于对花花酱的代码的注释。
需要解决的题目属于模拟题，即模拟出 Least Recently Used Cache 的运行机制。由于题目对 get（）、put（）函数时间复杂度都做了常数级的限制。所故题目的难点主要落在用什么数据结构上。在这里直接给出结论，使用一个 list 存储 items（需要从 Cache 中存取的），这使得 put（）函数可以满足常数级的时间复杂度；再用一个 unordered_map（hash table的实现）存储指向 items 的迭代器，这是使得 get（）函数可以满足常数级的时间复杂度。而且，unordered_map与 list 中都存储了 items 的 key，这有点冗余处理（空间）使得算法满足一些要求（换时间）的味道。 下面提出 6 个疑惑：

疑惑1：为什么将最近存取的 item 移动到 list 的头部，但是 unordered_map 中指向 item 的迭代器没有做修改。
疑惑2：list 容器 splice 方法的使用。
疑惑3：为什么list 容器的变量 cahe_ 要存 pair<int,int> 的元素，而不是直接存 int？
疑惑4： const auto & node = cache_.back（）为什么要用引用？
疑惑5： list 容器 erase、insert、emplace_front、pop_back、back 的使用。
疑惑6：unorder_map 容器 erase 的使用

需要提前强调说明的是，本文使用到了两种抽象的数据结构：双向链表和hash table。因为对双向链表的插入、删除和 hash table 的查找的时间复杂度都是常数级。前者在 C++ STL 中的具体实现是 list，后者是 unordered_map。而在代码中，list 的变量名是 cache_, unordered_map的变量名是 m_。下文中大部分出现的词是 cache_ 和 unordered_map。

接下来给出代码1——花花酱的解题代码：

// Author: Huahua
class LRUCache {
public:
    LRUCache(int capacity) {
        capacity_ = capacity;
    }
    
    int get(int key) {
        const auto it = m_.find(key);
        // If key does not exist
        if (it == m_.cend()) return -1;
 
        // Move this key to the front of the cache
        cache_.splice(cache_.begin(), cache_, it->second);
        return it->second->second;
    }
    
    void put(int key, int value) {        
        const auto it = m_.find(key);
        
        // Key already exists
        if (it != m_.cend()) {
            // Update the value
            it->second->second = value;
            // Move this entry to the front of the cache
            cache_.splice(cache_.begin(), cache_, it->second);
            return;
        }
        
        // Reached the capacity, remove the oldest entry
        if (cache_.size() == capacity_) {
            const auto& node = cache_.back();
            m_.erase(node.first);
            cache_.pop_back();
        }
        
        // Insert the entry to the front of the cache and update mapping.
        cache_.emplace_front(key, value);
        m_[key] = cache_.begin();
    }
private:
    int capacity_;
    list<pair<int,int>> cache_;
    unordered_map<int, list<pair<int,int>>::iterator> m_;
};
 
/**
 * 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);
 */

代码1 下文开始解惑：

解惑1

在代码1中，一条关键代码是

cache_.splice(cache_.begin(), cache_, it->second);

读者可能对 list 容器的 splice 方法不了解，没关系，下文会介绍。但是在这里，本文先介绍一下这条代码的含义。这条代码的意思是把访问到的 item 移动到 list 的头部。其中，it->second 是访问到的 item 的迭代器。这符合 LRU 机制。
那么问题来了：在 list 容器 cache_ 中移动了 it->second 对应的 item，为什么不在 unordered_map 中修改相应的指向这条 item 的迭代器内容？
回答：因为 splice 方法移动后，容器元素的迭代器仍然有效，仍然指向使用 splice 前的元素，所以不需要修改。

No elements are copied or moved, only the internal pointers of the list nodes are re-pointed.

更准确的解释请见cppreference网站。
方便读者理解，在这里举一个代码2 小例子加以说明：

#include<list>
#include<iostream>

using namespace std;

int main()
{
	list<int> List1 = {11,33,55,77,99};
	list<int> List2 = {0,22,44,66,88};
	
	cout <<"List1: "; 
	for (auto it = List1.begin(); it != List1.end(); ++it)
		cout << *it <<"  ";
	cout <<endl;
	
	cout <<"List2: "; 
	for (auto it = List2.begin(); it != List2.end(); ++it)
		cout << *it <<"  ";
	cout <<endl;
	
	auto iter1 = List1.begin();
	auto iter2 = List2.begin();
	
	std::advance(iter2,3);
	cout <<"*iter1: "<<*iter1<<",    &(*iter1): "<<&(*iter1)<<endl;
	cout <<"*iter2: "<<*iter2<<",    &(*iter2): "<<&(*iter2)<<endl;
	
	List1.splice(iter1,List2,iter2);
	
	cout <<endl<<"After Splice: "<<endl; 
	cout <<"List1: ";
	for (auto it = List1.begin(); it != List1.end(); ++it)
		cout << *it <<"  ";
	cout <<endl;
	
	cout <<"List2: "; 
	for (auto it = List2.begin(); it != List2.end(); ++it)
		cout << *it <<"  ";
	cout <<endl;

	cout <<"*iter1: "<<*iter1<<",     &(*iter1): "<<&(*iter1)<<endl;
	cout <<"*iter2: "<<*iter2<<",    &(*iter2): "<<&(*iter2)<<endl;
	return 0;
}

代码2 代码 2 的输出如图 1 所示。可以看到在使用 splice 方法后，迭代器 iter1、iter2 对应的内容保持不变，内容的地址也保持不变。

在这里插入图片描述

图1 如果我们不用 slice 方法实现将最近访问的 item 移动到 cache_ 头部位置。我们也可以采用这样的策略：先从 cache_ 中移除该item，然后将该 item 插入到 cache_ 的头部。具体实现上，先用 erase 方法清除，再用 insert 或者 emplace_front 方法插入。使用这种策略，就需要修改 unordered_map m_ 中指向该 item 的迭代器，令其指向 item 的新的位置。使用这种策略的代码如代码 3 所示：

class LRUCache {
public:
    LRUCache(int capacity) {
        capacity_ = capacity;
    }
    
    int get(int key) {
        const auto it = m_.find(key);
        if (it == m_.cend())
            return -1;
    	  	
        pair<int,int> ele = *(it->second);
        cache_.erase(it->second);
        cache_.emplace_front(ele);
        m_[key] = cache_.begin();
        //cache_.splice(cache_.begin(), cache_, it->second);
        return cache_.begin()->second;
    }
    
    void put(int key, int value) {
        const auto it = m_.find(key);
        if (it != m_.cend()){
            it->second->second = value;
            //cache_.splice(cache_.begin(), cache_, it->second);
	        pair<int,int> ele = *(it->second);
	        cache_.erase(it->second);
	        cache_.emplace_front(ele);
	        m_[key] = cache_.begin();
        }          
        else{
            if (capacity_ == cache_.size()){
                const auto& node = cache_.back();
                m_.erase(node.first);
                cache_.pop_back();
            }
            cache_.emplace_front(key,value);
            m_[key] = cache_.begin();
        }

    }
private:
    int capacity_;
    unordered_map<int, list<pair<int,int>>::iterator> m_;
    list<pair<int,int>> cache_;
};

/**
 * 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);
 */

代码2

pair<int,int> ele = *(it->second);
        cache_.erase(it->second);
        cache_.emplace_front(ele);
        m_[key] = cache_.begin();

取代了原先的

cache_.splice(cache_.begin(), cache_, it->second);

其中

m_[key] = cache_.begin();

是修改 unorder_map m_ 中指向 item 的迭代器内容。

解惑2： list 容器 splice 方法的使用

该方法可以实现一个 list 的一部分元素插入到另外一个 list 上。当然，可以是前者的全部元素。这两个 list 也可以是同一个 list。在代码 1 中就是同一个 list，一个元素插入的情况。而且该方法不会让 list 的迭代器失效。
更严谨的解释和例子请见 cppreference 网站。

解惑3：为什么list 容器的变量 cahe_ 要存 pair<int,int> 的元素，而不是直接存 int？（即同时在 cache_ 存储 item 的key 和value而不是只存储 item 的 value，因为考虑到在 unordered_map 中已经存储了 item 的 key）

在cache_ 同时存储 item 的 key 和 value 是必须的。
因为在使用 put（）函数时，会碰到缓存已满的情况，那么这个时候就需要删除掉 cache_ 最后一条 item。如果在 chche_ 中不存储 item 的 key，那么此时就无法找到在 unordered_map 中对应需要删除的。