146. LRU 缓存

146. LRU 缓存 - 力扣（LeetCode）

class LRUCache {
  using KeyType = int;
  using ValueType = int;
  using ListType = list<pair<KeyType, ValueType>>;
  using MapType = unordered_map<KeyType, ListType::iterator>;

  MapType Map_;
  ListType List_;
  int Size_;
  int Capacity_;

public:
  LRUCache(int capacity) : Map_(), List_(), Capacity_(capacity),
                           Size_(0) {}

  int get(int key) {
    auto I = Map_.find(key);
    if (I == Map_.end())
      return -1;

    int Value = I->second->second;
    List_.erase(I->second);
    List_.push_front(make_pair(key, Value));
    Map_[key] = List_.begin();
    return Value;
  }

  void put(int key, int value) {
    auto I = Map_.find(key);
    if (I == Map_.end()) {
      if (Size_ == Capacity_) {
        int Key = List_.back().first;
        List_.pop_back();
        Map_.erase(Key);
      } else {
        ++Size_;
      }
    } else {
      List_.erase(I->second);
    }
    List_.push_front(make_pair(key, value));
    Map_[key] = List_.begin();
  }
};

这个没什么好说的，这是接近 boost::lru_cache 的标准实现，map 联系 key 和 list iterator 以及 value 构成的 pair，list 记录 key 用以实现 LRU 操作。

注意，我之前写了一个这样的版本：

class LRUCache {
  using KeyType = int;
  using ValueType = int;
  using ListType = list<pair<KeyType, ValueType>>;
  using MapType = unordered_map<KeyType, ListType::iterator>;
  // ...
};

这种写法的问题在于，list 创建对象的开销是比较大的，而 value 可能比较复杂，所以应该尽可能地把 value 存在 map 里面。详细参考这个回复。

二刷

class LRUCache {
  using KeyType = int;
  using ValueType = int;
  using ListType = std::list<KeyType>;
  using MapType = std::unordered_map<KeyType, std::pair<ListType::iterator, ValueType>>;

  int Size_{};
  int Capacity_{};
  ListType List_;
  MapType Map_;

public:
  LRUCache(int capacity) : Capacity_(capacity) {}
  
  int get(int key) {
    auto It = Map_.find(key);
    if (It == Map_.end())
      return -1;

    List_.erase(It->second.first);
    List_.push_front(key);
    auto Renewed = List_.begin();
    It->second.first = Renewed;
    return It->second.second;
  }

  void put(int key, int value) {
    auto It = Map_.find(key);
    if (It == Map_.end()) {
      if (Size_ == Capacity_) {
        // XXX end is PAST the real end element!!!
        // auto Victim = List_.end();
        int Key = List_.back();
        Map_.erase(Key);
        List_.pop_back();
      } else {
        ++Size_;
      }
    } else {
      List_.erase(It->second.first);
    }
    List_.push_front(key);
    Map_[key] = std::make_pair(List_.begin(), value);
  }
};

二刷的时候竟然写错了！千万要注意 end() 方法给出的迭代器是在元素之后的！所以在抛弃最久未使用元素的时候，就算真的要用迭代器，也应该用 rbegin()。但 erase() 实际上是不接受 rbegin() 的，所以这里也必须用到 pop_back() 来实现移除尾元素。

std::list::splice() 还是得关注一下，这个东西其实挺好玩的，主要就在于它可以替代各种 erase() 啊，push_front() 啊这种东西。并且有一点要注意的是：对 List 节点进行的 splice() 操作不会使得 Iterator 失效！所以我们完全不用再修改 Map_[key] 强行补写一句。

int get(int key) {
  auto It = Map_.find(key);
  if (It == Map_.end())
    return -1;

  List_.splice(List_.begin(), List_, It->second.first);
  // There's no need to renew the iterator. It won't change under splice().
  // It->second.first = Renewed;
  return It->second.second;
}

而 std::list::emplace() 呢，它的返回值就是一个迭代器，所以对 Map_ 进行更新的操作可以一行写完。

int put(int key, int value) {
  ...
  // Update the map in one single line.
  Map_[key] = make_pair(List_.emplace(List_.begin(), key), value);
}

三刷

class LRUCache {
  using KeyType = int;
  using ValueType = int;
  using Iterator = std::list<KeyType>::iterator;
  std::list<KeyType> History_;
  std::unordered_map<KeyType, std::pair<ValueType, Iterator>> Dict_;
  int Capacity_;
  int Size_;

public:
  LRUCache(int capacity) {
    Capacity_ = capacity;
    Size_ = 0;
  }

  int get(int key) {
    if (auto I = Dict_.find(key); I != Dict_.end()) {
      History_.splice(History_.begin(), History_, I->second.second);
      return I->second.first;
    } else {
      return -1;
    }
  }

  void put(int key, int value) {
    if (auto I = Dict_.find(key); I != Dict_.end()) {
      I->second.first = value;
      History_.erase(I->second.second);
    } else {
      if (Capacity_ == Size_) {
        int Eliminate = History_.back();
        Dict_.erase(Eliminate);
        History_.pop_back();
      } else {
        ++Size_;
      }
    }
    Dict_[key] = make_pair(value, History_.emplace(History_.begin(), key));
  }
};

这个写法可能还是最符合直觉。

对于History_的操作，list::splice()可以用在get()操作里面，反正是一行能解决的事情；但是如果要用到put()里面去的话，对控制流的结构就有要求了，所以put()里面还是乖乖用最直接的erase()、pop_back()等等，只在最后向Dict_里插入东西的时候用一下list::emplace()，这样可以直接得到迭代器。

此外要注意，put()操作无论如何必定会改变Dict_，所以我们更新Dict_的操作要放在整个控制流的最外层。