我需要实现一个非常简单的 LRU 缓存来存储内存地址。
- 这些地址的数量是固定的(在运行时)。
- 我只对最近使用的地址感兴趣(我不关心其他元素的顺序)。
- 每个地址都有一个对应的索引号(简单整数),它不是唯一的并且可以更改。
实现需要以尽可能少的开销运行。除了每个地址之外,还有一个相关的信息结构(包含索引)。
我目前的方法是使用 astd::list
来存储地址/信息对,而 aboost::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;
}