Subj : Re: best data structure for LRU cache?
To   : alt.comp.lang.learn.c-c++,comp.programming
From : Roger Willcocks
Date : Sun Aug 07 2005 10:58 am

"Digital Puer" <digital_puer@hotmail.com> wrote in message 
news:1123382742.905087.69870@g44g2000cwa.googlegroups.com...
> Can someone recommend the best data structure to implement
> an LRU cache? I was thinking perhaps a priority queue,
> but that requires globally unique timestamps for
> each item that passes through the cache. I was thinking
> something simpler, as you would only need to know the
> ordering of items inside the cache, not globally.
>

Add previous and next pointers to your cache entries, use a doubly linked 
list and keep pointers to the head and the tail of the list. When an entry 
in the cache is used, unlink it from the queue (using the entry's previous 
and next pointers) and move it to the tail of the queue. When you need to 
reclaim space, eat from the head of the queue.

--
Roger

.