fork download
copy 
  1. #include <iostream>
  2.  
  3. #include <list>
  4. #include <string>
  5. #include <unordered_map>
  6.  
  7. class Item {
  8. public:
  9.     Item(std::string new_value, std::list<std::string>::iterator new_iterator)
  10.             :value(new_value), iterator(new_iterator) {};
  11.     Item() {};
  12.     std::string value;
  13.     std::list<std::string>::iterator iterator;
  14. };
  15.  
  16.  
  17. class LruCache {
  18. public:
  19.     LruCache(size_t max_size) :capacity_(max_size){}
  20.  
  21.     void Set(const std::string& key, const std::string& value) {
  22.         auto item = cache_.find(key);
  23.         if (item == cache_.end()) {
  24.             CheckSize();
  25.             last_used_.push_front(key);
  26.             cache_[key] = Item(value, last_used_.begin());
  27.         } else {
  28.             PushFrontItem(item);
  29.             cache_[key].value = value;
  30.         }
  31.     }
  32.  
  33.     bool Get(const std::string& key, std::string* value) {
  34.         auto item = cache_.find(key);
  35.         if (item != cache_.end()) {
  36.             *value = item->second.value;
  37.             PushFrontItem(item);
  38.             return true;
  39.         }
  40.         return false;
  41.     }
  42.  
  43. private:
  44.     void CheckSize() {
  45.         if (last_used_.size() >= capacity_) {
  46.             RemoveLast();
  47.         }
  48.     }
  49.  
  50.     void RemoveLast () {
  51.         std::string last = last_used_.back();
  52.         last_used_.pop_back();
  53.         cache_.erase(last);
  54.     }
  55.  
  56.     void PushFrontItem(std::unordered_map<std::string, Item>::iterator item) {
  57.         last_used_.erase(item->second.iterator);
  58.         last_used_.push_front(item->first);
  59.         item->second.iterator = last_used_.begin();
  60.     }
  61.  
  62. private:
  63.     size_t capacity_;
  64.     std::unordered_map<std::string, Item> cache_;
  65.     std::list<std::string> last_used_;
  66. };
  67.  
  68.  
  69.  
  70. using namespace std;
  71.  
  72. #define REQUIRE(x) std::cout << x << std::endl;
  73.  
  74. void test()
  75. {
  76.     LruCache cache(2);
  77.     std::string value;
  78.  
  79.  
  80.     cache.Set("a", "1");
  81.     cache.Set("b", "2");
  82.     cache.Set("c", "3");
  83.  
  84.     REQUIRE(!cache.Get("a", &value));
  85.     REQUIRE(cache.Get("b", &value));
  86.     REQUIRE(cache.Get("c", &value));
  87.  
  88.     cache.Set("b", "4");
  89.     cache.Set("c", "5");
  90.     cache.Set("b", "6");
  91.  
  92.     cache.Set("e", "7");
  93.  
  94.     REQUIRE(!cache.Get("c", &value));
  95.     REQUIRE(cache.Get("b", &value));
  96.     REQUIRE(cache.Get("e", &value));
  97.  
  98.     cache.Get("b", &value);
  99.     cache.Set("f", "8");
  100.  
  101.     REQUIRE(!cache.Get("e", &value));
  102.     REQUIRE(cache.Get("b", &value));
  103.     REQUIRE(cache.Get("f", &value));
  104. }
  105.  
  106. int main() {
  107.     for (int i = 0; i < 5; ++i) {
  108.         test();
  109.     }
  110.     return 0;
  111. }
Success #stdin #stdout 0s 15248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
https://ideone.com/X7WiEx
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!