C++最适合用于非常简单LRU缓存的容器

3
我需要实现一个非常简单的LRU缓存,用于存储内存地址。
  • 这些地址的数量在运行时是固定的。
  • 我只关心最近使用的地址(不关心其他元素的顺序)。
  • 每个地址都有相应的索引号(简单整数),并且不是唯一的,可能会改变。

实现需要尽可能地减少开销。除了每个地址外,还有一个相关的信息结构(包含索引)。

我的当前方法是使用std::list来存储地址/信息对,以及一个boost::unordered_multimap,它是索引和列表相关迭代器之间的映射。

以下示例与我的生产代码无关。请注意,这仅用于更好地理解。

struct address_info
{
    address_info() : i(-1) {}
    int i;
    // more ...
};


int main()
{
    int const MAX_ADDR_COUNT = 10,
              MAX_ADDR_SIZE  = 64;

    char** s           = new char*[MAX_ADDR_COUNT];
    address_info* info = new address_info[MAX_ADDR_COUNT]();

    for (int i = 0; i < MAX_ADDR_COUNT; ++i)
        s[i] = new char[MAX_ADDR_SIZE]();

    typedef boost::unordered_multimap<int, std::list<std::pair<address_info, char*>>::const_iterator> index_address_map;

    std::list<std::pair<address_info, char*>> list(MAX_ADDR_COUNT);
    index_address_map                  map;

    {
        int i = 0;
        for (std::list<std::pair<address_info, char*>>::iterator iter = list.begin(); i != MAX_ADDR_COUNT; ++i, ++iter)
            *iter = std::make_pair(info[i], s[i]);
    }

    // usage example:
    // try to find address_info 4
    index_address_map::const_iterator iter = map.find(4);
    if (iter == map.end())
    {
        std::pair<address_info, char*>& lru = list.back();

        if (lru.first.i != -1)
            map.erase(lru.first.i);
        lru.first.i = 4;

        list.splice(list.begin(), list, boost::prior(list.end()));
        map.insert(std::make_pair(4, list.begin()));
    }
    else
        list.splice(list.begin(), list, iter->second);

    for (int i = 0; i < MAX_ADDR_COUNT; ++i)
        delete[] s[i];

    delete[] info;
    delete[] s;

    return 0;
}

1
那里是否隐藏了一个问题?也许这应该移到代码评审。 - Kerrek SB
代码非常混乱,你应该使用适当的API重写示例,以便我们知道确切的要求。如果您只需要最近使用的地址,为什么还要存储其他内容? - Karoly Horvath
@yi_H:因为像任何队列一样,当你弹出LRU元素时,你需要“新”的LRU :) - Matthieu M.
好的,那是一个需求.. 你应该能够弹出。 - Karoly Horvath
1个回答

2

通常的建议是使用Boost.MultiIndex进行此任务:

  • 索引0:插入顺序
  • 索引1:元素的关键字(二分查找或哈希)

如果我没记错,甚至在Boost网站上也有演示。


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接