LRU cache design

by

A linked list + hashtable of pointers to the linked list nodes is the usual way to implement LRU caches. This gives O(1) operations (assuming a decent hash). Advantage of this (being O(1)): you can do a multithreaded version by just locking the whole structure. You don’t have to worry about granular locking etc.

Briefly, the way it works:

On an access of a value, you move the corresponding node in the linked list to the head.

When you need to remove a value from the cache, you remove from the tail end.

When you add a value to cache, you just place it at the head of the linked list.

Thanks to doublep, here is site with a C++ implementation: Miscellaneous Container Templates.

More Related Contents:

  1. How to get the maximum number after erasing n digits from the number [closed]
  2. what is the difference between set and unordered_set in C++?
  3. TMP: how to generalize a Cartesian Product of Vectors?
  4. Why would anyone use set instead of unordered_set?
  5. Easiest way of using min priority queue with key update in C++
  6. LRU implementation in production code
  7. Order Statistic Tree in C++
  8. Insertion sort stops working after million input
  9. How to find out how many bits are set (equal 1) in the product of two integers [closed]
  10. How do I compare chars (or strings) using void functions, also comparing chars that were taken from a struct array
  11. C++ – Find numbers between first and last negative numbers in Array
  12. Image Processing: Algorithm Improvement for ‘Coca-Cola Can’ Recognition
  13. Rotating a point about another point (2D)
  14. Create Random Number Sequence with No Repeats
  15. Fast ceiling of an integer division in C / C++
  16. Algorithm for finding the smallest power of two that’s greater or equal to a given value [duplicate]
  17. How can I find the actual path found by BFS?
  18. Splitting a string by a character
  19. How can I sort a std::map first by value, then by key?
  20. C – How to implement Set data structure?
  21. Similar String algorithm
  22. Calculating the Amount of Combinations
  23. Efficiency of the STL priority_queue
  24. Better shading on BW display while rendering filled surfaces
  25. Algorithm to add or subtract days from a date?
  26. Creating N nested for-loops
  27. Is it possible to implement lock free map in C++
  28. What should the ‘pop()’ method return when the stack is empty? [duplicate]
  29. Calculate mean and standard deviation from a vector of samples in C++ using Boost
  30. Checking if all elements of a vector are equal in C++

Leave a Comment