LRU缓存的实现

Question

您认为这种LRU缓存的实现如何？我正在尝试迁移到现代C++，所以如果您能在这里给我任何提示，那就太棒了。我听说它不想使用原始指针，对吗？那么，就像在这个例子中一样，仅限于内部呢？

而且，由于我不能在nullptr方法中返回一个get()值，那么最好的替代方法是什么？默认值，如示例中所示？

#ifndef __LRU_HPP__
#define __LRU_HPP__
#include <map>
#include<iostream>
#include<assert.h>

template<class T>
struct Default {
  T value;
  Default():value(){}
};

template<class K, class V>
struct node {
  K key;
  V value;
  node<K,V>* next;
  node<K,V>* prev;
  explicit node(K key, V value);
};

template<class K, class V>
class lru {
private:
  node<K,V>* head;
  node<K,V>* tail;
  std::map<K,node<K,V>*> map;
  std::size_t capacity;
  void replace(node<K,V>*);
public:
  explicit lru(std::size_t);
  void put(K key, V value);
  V get(K key);
};

template<class K, class V>
inline node<K,V>::node(K key, V value) {
  this->key = key;
  this->value = value;
}

template<class K, class V>
inline lru<K,V>::lru(std::size_t capacity) {
  assert(capacity > 1);
  this->capacity = capacity;
  this->head = tail = nullptr;
}

template<class K, class V>
void lru<K,V>::put(K key, V value) {
  auto it = map.find(key);
  if (it != map.end()) {
    node<K,V>* temp = it->second;
    temp->value = value;
    replace(temp);
    return;
  }
  if(capacity == map.size()) {
    tail->prev->next = tail->next;
    node<K,V>* target = tail;
    map.erase(target->key);
    tail = tail->prev;
    delete tail;
  }
  node<K,V>* temp = new node<K,V>(key, value);
  temp->prev = nullptr;
  temp->next = head;
  if(head != nullptr)
    head->prev = temp;
  else
    tail = temp;
  head = temp;
  map.insert(std::pair<K,node<K,V>*> {key, temp});
}

template<class K, class V>
V lru<K,V>::get(K key) {
  auto it = map.find(key);
  if(it != map.end()) {
    replace(it->second);
    return it->second->value;
  }
  return Default<V>().value;
}

template<class K, class V>
void lru<K,V>::replace(node<K,V>* temp) {
  if (temp->prev != nullptr)
    temp->prev->next = temp->next;
  if (temp->next != nullptr)
    temp->next->prev = temp->prev;
  if (tail == temp)
    tail = temp->prev != nullptr ? temp->prev : temp;
  if (head != temp) {
    head->prev = temp;
    temp->next = head;
    head = temp;
  }
}
#endif

Answer 1

名称空间使用

我会将所有这些放在某个名称空间中，这样它就不会意外地与它定义的名称的其他用法发生冲突。

为了隐藏node和Default模板，我可能也会更加努力地工作。例如，node不需要对外部世界可见，所以在lru中定义它可能会更好。

喜欢初始化而不是赋值

像这样的构造函数：

template<class K, class V>
inline node<K, V>::node(K key, V value) {
    this->key = key;
    this->value = value;
}

...is通常更好地编写类似这样的东西：

template <class K, class V>
inline node<K, V>::node(K key, V value)
    : key(key)
    , value(value)
{}

在某些情况下，您必须初始化(像这样)而不是赋值。在这种情况下，这不是强制性的，但我仍然认为它更可取。

考虑通过引用传递

按价值传递您的keys和values通常需要复制。您可能需要考虑是否值得通过引用进行传递。如果传递的类型是“小”的，则通常只完成很少(或什么也不完成)，但是如果类型很大，则可以大大提高速度。

将类型内部的知识封装在该类型的

中

现在，您的lru类“知道”(取决于) node类的内部。我通常更希望node知道它的内部结构。作为一种可能，您可以将一个next和prev传递给ctor，并让它将这些值放入node本身：

template <class K, class V>
inline node<K, V>::node(K key, V value, node *prev = nullptr, node *next = nullptr)
    : key(key)
    , value(value)
    , prev(prev)
    , next(next)
{}

在这种情况下，您的代码如下：

node<K, V>* temp = new node<K, V>(key, value);
temp->prev = nullptr;
temp->next = head;

...would变成了这样的东西：

node<K, V> *temp = new node<K, V>(key, value, nullptr, head);

考虑了其他数据结构

虽然双链接列表确实适用于手头的任务，但它通常相当浪费，除了实际关心存储的数据外，每个节点使用几个指针。

我会考虑使用单链列表来代替。虽然很显然，这并不是你能立即做到的，但我相当肯定你能做到。

考虑预先分配存储

考虑到在创建缓存时总对象的最大数量是固定的，在创建缓存时，我还会考虑为对象和链接列表节点预先分配存储空间。为固定大小的一组固定大小的块分配一个分配器可能非常简单，这可以大大提高速度，通过在空闲存储上为缓存中插入的每一项使用两次分配。

Answer 2

头保护

代码包含未定义的行为，因为下划线是为实现保留的：

17.6.4.3保留名称reserved.names C++标准库保留以下类型的名称：

• 宏
• 全局名称
• 具有外部链接的名称

如果程序在保留名称的上下文中声明或定义名称，而非本条款显式允许的名称，则其行为未定义。… 17.6.4.3.2全局名称global.names某些名称和函数签名始终保留在实现中：

• 每个包含双下划线__或以下划线开头由大写字母(2.12)开头的名称都保留给实现，供任何使用。
• 以下划线开头的每个名称都保留给实现，以便作为全局命名空间中的名称使用。

因此，将__LRU_HPP__重命名为LEAST_RECENTLY_USED_HPP或类似的。

Default

而不是

return Default<V>().value;

使用

return V{};

除非您希望使用Default<V>来提供专门化。

可能的bug

我很确定你是指delete target，而不是delete tail。

  if(capacity == map.size()) {
    tail->prev->next = tail->next;
    node<K,V>* target = tail;
    map.erase(target->key);
    tail = tail->prev;
    delete tail;                     // << ?
  }

否则，您将得到一个已删除但不为空的tail。

Call-by-reference

如果以后不打算更改参数，则使用const &作为参数。

Answer 3

• node没有理由知道密钥。
• 节点构造函数将创建一个完全创建的节点，即prev和next字段也应该初始化(到nullptr)。
• 成员初始化程序列表比构造函数体更可取。例如，lru::lru(std::size_t容量)：容量(容量)，prev(nullptr)，next(nullptr) {assert(容量> 1)；}
• 返回一个Default<V>.value()不符合目的。至少这意味着客户端不能put这样的值。一种惯用的方法(即STL)是让get返回迭代器，并通过返回end迭代器发出失败信号。
• put中的序列: tail->prev->next = tail->next；.尾=尾->prev；删除尾；是一个明确的错误，并有许多严重的后果。考虑重写：.尾=尾->prev；删除尾->下一步；尾->next= nullptr；
• 审阅者立即注意到put中的另一个" bug“--即头部没有更新--并且需要时间和精神集中来回忆capacity > 1断言，这使得bug变得无关紧要。我强烈建议将尾部移除作为反映这一事实的名称的函数。我建议pop_back_unguarded或类似的东西。
• 我不认为replace反映了这个函数的实际功能。也许是bump_up？