By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
455,514 Members | 1,741 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 455,514 IT Pros & Developers. It's quick & easy.

Design Patterns for LRU Cache in C++

P: n/a
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.

May 29 '07 #1
Share this Question
Share on Google+
4 Replies


P: n/a
On 29 Maj, 06:01, Raja <rokkamr...@gmail.comwrote:
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.

--
Erik Wikström

May 29 '07 #2

P: n/a
On May 28, 9:01 pm, Raja <rokkamr...@gmail.comwrote:
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.

May 29 '07 #3

P: n/a
Naresh Rautela wrote:
On May 28, 9:01 pm, Raja <rokkamr...@gmail.comwrote:
>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.
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.
May 29 '07 #4

P: n/a
Erik Wikström wrote:
On 29 Maj, 06:01, Raja <rokkamr...@gmail.comwrote:
>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 .
You might want to look at std::priority_queue, sorted by time of use.
May 29 '07 #5

This discussion thread is closed

Replies have been disabled for this discussion.