0

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?

Community
  • 1
  • 1
Joe C
  • 2,757
  • 2
  • 26
  • 46

1 Answers1

1

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?

Community
  • 1
  • 1
Ross Bencina
  • 3,822
  • 1
  • 19
  • 33