Subj : Re: best data structure for LRU cache?
To   : comp.programming
From : Alex Fraser
Date : Mon Aug 08 2005 04:05 pm

"Jon Harrop" <usenet@jdh30.plus.com> wrote in message
news:42f66c04$0$24029$ed2619ec@ptn-nntp-reader01.plus.net...
> 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.

You are taking the piss, right?

Alex

.