LRU Cache
==========================

The LRU caching scheme is to evict the least recently used item when the cache is full. Since it is a cache or a key value store, the basic data structure should be a `map`. To maintain the `insertion order`, we need to use a `list` to store the ordered items.

|:feet:| When getting an item from LRU cache, the item will be refreshed.


.. literalinclude:: lru.h
  :language: c++
  :linenos:
  :lines: 5-37

LRU-Customized Eviction Scheme
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

.. literalinclude:: lru_customized_eviction.h
  :language: c++
  :linenos:
  :lines: 66-158

How to promote an item in a list to the front:

.. code-block:: c++

  [cling]$ list<int> l={2,4,1,3,6,5}
  (std::list<int> &) { 2, 4, 1, 3, 6, 5 }
  [cling]$ auto it = next(next(l.begin()));
  [cling]$ l.splice(l.begin(), l, it, next(it))
  [cling]$ l
  (std::list<int> &) { 1, 2, 4, 3, 6, 5 }

LFU
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^