C++最简单的LRU缓存容器

我需要实现一个真正简单的LRU缓存来存储内存地址。C++最简单的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; 
}

来源

2011-07-04 0xbadf00d

有没有隐藏在那里的问题？也许这应该转移到codereview。 –

“问题”在标题 –

中，代码非常混乱，您应该使用适合您的LRU的API重写您的示例，以便我们知道具体要求是什么。问：如果您只需要最近使用过的地址，为什么要存储其他内容？ –

通常的建议是挖Boost.MultiIndex的该任务：

指数0：插入的顺序
索引1：的元素的键（二进制搜索或散列）

如果我记得正确的话，它甚至在Boost站点上演示过。

来源

2011-07-04 12:40:53

C++最简单的LRU缓存容器

回答

相关问题