CODEWITHSUNDEEP
c++liststdlru
Joe C
Joe C

Reputation: 2827

How to use std::list to implement LRU

Using a list and a hash-map, we can implement LRU in Java.

How would you implement an LRU cache in Java?

In C++, does std::list allow us to implement this?

For each element in cache, we need to know its position in the list. However, after removing a position, does list ensure that the positions (list::iterator) after this one will not be changed?

Upvotes: 0

Views: 638

Answers (1)

Ross Bencina
Ross Bencina

Reputation: 4173

Yes, you can implement LRU using std::list and std::map.

std::list iterators referencing retained elements are unaffected by insertions and erasures of other elements. See this answer: Iterator invalidation rules

The same is true for std::map. See this answer: Does insertion to STL map invalidate other existing iterator?

Upvotes: 1

Related Questions