tomilov

LRU C++17

Aug 3rd, 2021
644
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class LRUCache {
  2. public:
  3.     LRUCache(int c)
  4.         : capacity{size_t(c)}
  5.     {}
  6.    
  7.     int get(int key) const
  8.     {
  9.         auto it = cache.find(key);
  10.         if (it == std::end(cache)) {
  11.             return -1;
  12.         }
  13.         lru.splice(std::cend(lru), lru, *it->second.lru);
  14.         return it->second.value;
  15.     }
  16.    
  17.     void put(int key, int value)
  18.     {
  19.         auto it = cache.find(key);
  20.         if (it == std::end(cache)) {
  21.             it = cache.insert(it, {key, Value{value, nullptr}});
  22.             if (cache.size() > capacity) {
  23.                 cache.erase(lru.front());
  24.                 lru.splice(std::cend(lru), lru, std::cbegin(lru));
  25.                 lru.back() = it;
  26.             } else {
  27.                 lru.push_back(it);
  28.             }
  29.             it->second.lru = std::make_unique<Iterator>(std::prev(std::end(lru)));
  30.         } else {
  31.             it->second.value = value;
  32.             lru.splice(std::cend(lru), lru, *it->second.lru);
  33.         }
  34.     }
  35. private:
  36.     struct Iterator;
  37.     struct Value
  38.     {
  39.         int value;
  40.         std::unique_ptr<Iterator> lru;
  41.     };
  42.     using Cache = std::unordered_map<int /* key */, Value>;
  43.     using LRU = std::list<typename Cache::iterator>;
  44.     struct Iterator : LRU::iterator
  45.     {
  46.         Iterator(LRU::iterator it)
  47.             : LRU::iterator{it}
  48.         {}
  49.     };
  50.    
  51.     const size_t capacity;
  52.     Cache cache;
  53.     mutable LRU lru;
  54. };
  55.  
  56.  
RAW Paste Data