最近最近使用的缓存使用C ++ [英] Least Recently Used cache using C++

问题描述

我正在尝试使用C ++实现LRU Cache。我想知道实现它们的最佳设计是什么。我知道LRU应该提供find（），添加一个元素并删除一个元素。删除应删除LRU元素。实现这个
的最好的ADT是例如：如果我使用带有元素的地图作为值和时间计数器作为键，我可以在O（logn）时间内搜索，插入是O（n），删除是O（ logn）。

解决方案

LRU缓存的一个主要问题是几乎没有const操作，大多数将更改底层表示（如果只是因为它们碰到访问的元素）。

这当然是非常不方便的，因为这意味着它不是一个传统的STL容器，因此任何展示迭代器的想法相当复杂：当迭代器被解引用时，这是一个访问，它应该修改我们正在迭代的列表...哦，我的。$ /

还有表演考虑无论是在速度和内存消耗方面。

这是不幸的，但你需要一些方法来组织你的数据在队列（LRU）（有可能从中间移除元素），这意味着您的元素他们将彼此独立。当然，一个 std :: list 适合，但它比你需要的更多。单独链接的列表在这里是足够的，因为您不需要向后迭代列表（您只需要一个队列，毕竟）。

然而，一个主要的缺点那些是他们穷人的参考，如果你需要更多的速度，你需要为节点提供自己的定制（池？）分配器，以便它们尽可能地保持在一起。这也将有助于缓解堆碎片。

接下来，您显然需要一个索引结构（对于缓存位）。最自然的是转向哈希图。 std :: tr1 :: unordered_map ， std :: unordered_map 或 boost :: unordered_map 通常质量很好，有些应该可以使用。他们还为哈希冲突处理分配了额外的节点，您可能更喜欢其他类型的哈希映射，请查看维基百科的文章< a>关于这个问题，并阅读各种实现技术的特点。

继续，有（明显的）线程支持。如果你不需要线程支持，那么这很好，如果你这样做的话，这会更复杂一些：

• 正如我所说，在这样一个结构上没有什么 const 操作，因此你不需要区分读/写访问


• 内部锁定好的，但是你可能会发现它不能很好的用于你的使用。内部锁定的问题是它不支持事务的概念，因为它放弃了每次调用之间的锁定。如果是这种情况，将对象转换为互斥体，并提供一个 std :: unique_ptr< Lock> lock（）方法（在调试中，您可以在每个方法的入口处使用锁定）


• 有（在锁定策略中）重新启动的问题，即从同一个线程重新锁定互斥体的能力，请检查Boost.Thread以获取有关可用的各种锁和互斥体的更多信息。

最后，有错误报告的问题。由于预期缓存可能无法检索您输入的数据，所以我会考虑使用异常味道差。考虑两个指针（ Value * ）或 Boost.Optional （ boost :: optional< Value&> ）。我喜欢Boost.Optional，因为它的语义很清楚。

I am trying to implement LRU Cache using C++ . I would like to know what is the best design for implementing them. I know LRU should provide find(), add an element and remove an element. The remove should remove the LRU element. what is the best ADTs to implement this For ex: If I use a map with element as value and time counter as key I can search in O(logn) time, Inserting is O(n), deleting is O(logn).

解决方案

One major issue with LRU caches is that there is little "const" operations, most will change the underlying representation (if only because they bump the element accessed).

This is of course very inconvenient, because it means it's not a traditional STL container, and therefore any idea of exhibiting iterators is quite complicated: when the iterator is dereferenced this is an access, which should modify the list we are iterating on... oh my.

And there are the performances consideration, both in term of speed and memory consumption.

It is unfortunate, but you'll need some way to organize your data in a queue (LRU) (with the possibility to remove elements from the middle) and this means your elements will have to be independant from one another. A std::list fits, of course, but it's more than you need. A singly-linked list is sufficient here, since you don't need to iterate the list backward (you just want a queue, after all).

However one major drawback of those is their poor locality of reference, if you need more speed you'll need to provide your own custom (pool ?) allocator for the nodes, so that they are kept as close together as possible. This will also alleviate heap fragmentation somewhat.

Next, you obviously need an index structure (for the cache bit). The most natural is to turn toward a hash map. std::tr1::unordered_map, std::unordered_map or boost::unordered_map are normally good quality implementation, some should be available to you. They also allocate extra nodes for hash collision handling, you might prefer other kinds of hash maps, check out Wikipedia's article on the subject and read about the characteristics of the various implementation technics.

Continuing, there is the (obvious) threading support. If you don't need thread support, then it's fine, if you do however, it's a bit more complicated:

• As I said, there is little const operation on such a structure, thus you don't really need to differentiate Read/Write accesses
• Internal locking is fine, but you might find that it doesn't play nice with your uses. The issue with internal locking is that it doesn't support the concept of "transaction" since it relinquish the lock between each call. If this is your case, transform your object into a mutex and provide a std::unique_ptr<Lock> lock() method (in debug, you can assert than the lock is taken at the entry point of each method)
• There is (in locking strategies) the issue of reentrance, ie the ability to "relock" the mutex from within the same thread, check Boost.Thread for more information about the various locks and mutexes available

Finally, there is the issue of error reporting. Since it is expected that a cache may not be able to retrieve the data you put in, I would consider using an exception "poor taste". Consider either pointers (Value*) or Boost.Optional (boost::optional<Value&>). I would prefer Boost.Optional because its semantic is clear.

这篇关于最近最近使用的缓存使用C ++的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！