固定容量unordered_map

Question

我需要一个容器，它的行为像一个unordered_map，但是有一个固定的容量，以及一个驱逐策略，其中最近插入的键值对是在容量执行时被驱逐的。

我通过创建一个容器来实现这一点，它将一个常规的unordered_map和一个迭代器队列(作为一个循环数组实现)结合在一起。插入新项时，队列末尾的迭代器将被擦除。

fixed_size_unordered_map

#include <array>
#include <unordered_map>

template<typename Key, typename U, std::size_t capacity>
class fixed_size_unordered_map {
    using iterator = typename std::unordered_map<Key, U>::iterator;
    using size_type = typename std::unordered_map<Key, U>::size_type;
    using value_type = typename std::unordered_map<Key, U>::value_type;

public:
    fixed_size_unordered_map() { iter_queue.fill(items.end()); }
    fixed_size_unordered_map(const fixed_size_unordered_map&) = default;
    fixed_size_unordered_map& operator=(const fixed_size_unordered_map&) = default;
    fixed_size_unordered_map(fixed_size_unordered_map&&) = default;
    fixed_size_unordered_map& operator=(fixed_size_unordered_map&&) = default;

    size_type count(const Key& key) const {
        return items.count(key);
    }

    const Key& at(const Key& key) const {
        return items.at(key);
    }

    std::pair<iterator, bool> insert(const value_type &v) {
        if(iter_queue[queue_idx] != items.end()){
            items.erase(iter_queue[queue_idx]);
        }
        const auto ret = items.insert(v);
        if(ret.second){
            iter_queue[queue_idx] = ret.first;
            queue_idx = (queue_idx + 1) % capacity;
        }
        return ret;
    }

    /* could implement more map<T, U> delegates as appropriate, the above are the ones
     * I actually need for my use case */

protected:
    std::unordered_map<Key, U> items;

    std::array<iterator, capacity> iter_queue;
    std::size_t queue_idx{0};
};

示例用法：

fixed_size_unordered_map<int, int, 10> m;
for(int i=0; i<=10; ++i){
    m.insert(std::make_pair(i, 2*i*i));
}
std::cout << m.at(10) << "\t" << m.at(1) << "\t" << m.count(0) << std::endl;

Answer 1

template<typename Key, typename U, std::size_t capacity>
class fixed_size_unordered_map {

底层映射允许对分配程序、键比较器和哈希进行策略自定义。您可能希望向用户提供这些自定义点。

    using iterator = typename std::unordered_map<Key, U>::iterator;
    using size_type = typename std::unordered_map<Key, U>::size_type;
    using value_type = typename std::unordered_map<Key, U>::value_type;

这些常见的类型定义是否打算是private？

    fixed_size_unordered_map(const fixed_size_unordered_map&) = default;
    fixed_size_unordered_map& operator=(const fixed_size_unordered_map&) = default;
    fixed_size_unordered_map(fixed_size_unordered_map&&) = default;
    fixed_size_unordered_map& operator=(fixed_size_unordered_map&&) = default;

如果显式定义了类的任何特殊成员函数，则必须全部定义它们。以下五个被认为是特殊的成员职能。(见零/3/5规则)

• 破坏者
• 复制构造器
• 复制分配
• 移动构造器
• 移动分配

要么显式提供缺少的析构函数(规则五)，要么不显式定义其中的任何一个(“零规则”)。

    if(iter_queue[queue_idx] != items.end()){
        items.erase(iter_queue[queue_idx]);
    }
    const auto ret = items.insert(v);
    if(ret.second){

这里没有明确的行为。如果iter_queue已满，则不管发生什么情况，都要擦除。如果插入成功，则迭代器将覆盖LRU中当前无效的迭代器。如果插入不成功，LRU就不会发生任何事情，并且当前的迭代器就是无效的。

擦除前检查一下。插入时擦除。确定希望LRU在插入失败时的行为方式。

考虑使用循环缓冲区或为某些缓冲区类型编写自己的LRU缓存适配器。通过将LRU功能解耦，该对象可以专注于将其接口调整到组合对象。它还消除了显式定义默认构造函数的需要(除非定义了转换ctor)。