Design Patterns for LRU Cache in C++

[Raja]

Hi,
I am trying to do a simple design of an LRU Cache . Can anyone
please guide me in this regard. I have a basic idea ADT to be used
using linked list and reference counted array. But I want to know the
best method to design , the classes , interfaces etc required .

Thank You,
Raja.

 

[=?iso-8859-1?q?Erik_Wikstr=F6m?=]

Hi,
I am trying to do a simple design of an LRU Cache . Can anyone
please guide me in this regard. I have a basic idea ADT to be used
using linked list and reference counted array. But I want to know the
best method to design , the classes , interfaces etc required .

Depends on your needs and constraints. A simple version would be to
use a vector to store a struct describing whatever it is that you
cache, and each time you access one of them you update a time-stamp.
When you need to replace one of them you can either sort the vector on
the time-stamp, or, if you need the order unchanged, make a copy and
sort the copy.

For more efficient implementations you might want to get a book on
operating systems, or google, or check wikipedia.

 

[Naresh Rautela]

Hi,
I am trying to do a simple design of an LRU Cache . Can anyone
please guide me in this regard. I have a basic idea ADT to be used
using linked list and reference counted array. But I want to know the
best method to design , the classes , interfaces etc required .

Thank You,
Raja.

Another simple implentation would be to use a list. Each time you get
a cached element append it to the end of the list. The head of the
list indicates the least recently used item. When a cached element is
used again move it to the end of the list. When a new element needs
to be cached delete the one at the front of the list and append the
new one at the end of the list.

Hope this helps.

 

[Tsung-hsien Chen]

Another simple implentation would be to use a list. Each time you get
a cached element append it to the end of the list. The head of the
list indicates the least recently used item. When a cached element is
used again move it to the end of the list. When a new element needs
to be cached delete the one at the front of the list and append the
new one at the end of the list.

Hope this helps.

How about using a set to store the structure of cache data and make it
sorted by timestamp. Put the least recently used entry at the head of
the set, then it can be deleted easily and quickly when necessary.
Whenever a cache entry is accessed, change its timestamp and remove its
original copy from the set and then put the new copy into the set. Since
the set is sorted by timestamp, the new copy will be put at the
appropriate position automatically.

Just my 2 cents.

 

[red floyd]

You might want to look at std:riority_queue, sorted by time of use.