LRU cache in C ++

Question

Possible duplicate:
LRU cache design

I got this question in a programming interview. Feel free to think about how you could answer it.

How would you implement the LRU cache (least recently updated) in C ++? Basically, a cache can contain up to N elements. If a new element is inserted and the number of elements in the cache is less than N , it is simply inserted. But if a new element is inserted and the number of elements in the cache is already N , the element that was recently used must be removed from the cache.

Think about how long it will take for each of your operations.

Answer 1

I would have a member of the cache that stores the last access time. When an element gets access (a member function is called), the access time member is updated. When the cache is full, the item with the least access time will be deleted.

Another option is to have cache elements in an obsessive list . When something is available and not on the list, it is on the list. When the cache is full, the bottom of the list is erased. More work on each access, but the victim is faster to find.

The main idea is not to have typical maps and lists for such tasks, they will fragment your memory. My algorithms constantly store the cache in one place.