Subj : Re: best data structure for LRU cache?
To   : alt.comp.lang.learn.c-c++,comp.programming
From : Jon Harrop
Date : Sun Aug 07 2005 10:13 pm

Digital Puer wrote:
> 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.

I've never done this before, but in the simplest case I think you can just
use an int index into an array. The int points to the oldest entry. To
insert you overwrite the array entry at the int before incrementing it. To
search, consider each entry in turn.

In C, you probably want to use an array of pointers to your objects (NULL if
empty). In C++, you probably want an STL vector of smart pointers.

-- 
Dr Jon D Harrop, Flying Frog Consultancy
http://www.ffconsultancy.com

.