Implementing a cache

[pdpi]

On Jul 12, 2:01 pm, s... at pobox.com wrote:
>     Nikolaus> I want to implement a caching data structure in Python that
>     Nikolaus> allows me to:
>
>     Nikolaus>  1. Quickly look up objects using a key
>     Nikolaus>  2. Keep track of the order in which the objects are accessed
>     Nikolaus>     (most recently and least recently accessed one, not a
>     Nikolaus>     complete history)
>     Nikolaus>  3. Quickly retrieve and remove the least recently accessed
>     Nikolaus>     object.
>
> My Cache module does #1 and #3.  I'm not sure if you want #2 for internal
> cache maintenance or for as part of the API.
>
>    http://www.smontanaro.net/python/Cache.py
>
> Skip

I'm not sure whether #2 is doable at all, as written. You _need_ a
complete history (at least the full ordering of the items in the
cache) to be able to tell what the least recently used item is.