daily pastebin goal
24%
SHARE
TWEET

Untitled

a guest Jan 21st, 2019 70 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class LRUCache {
  2. public:
  3.     LRUCache(int capacity) : capacity_(capacity) {}
  4.  
  5.     int get(int key) {
  6.         if (data_.count(key) == 0) return -1;
  7.         key_to_timestamp_[key] = ++timestamp_;
  8.         timestamp_to_key_pq_.push({ timestamp_, key });
  9.         return data_[key];
  10.     }
  11.  
  12.     void put(int key, int value) {
  13.         if (data_.count(key) == 0 && data_.size() == capacity_) {
  14.             if (timestamp_to_key_pq_.empty()) return;
  15.             auto to_delete = timestamp_to_key_pq_.top();
  16.             auto key_to_delete = std::get<1>(to_delete);
  17.             timestamp_to_key_pq_.pop();
  18.  
  19.             while (data_.count(key_to_delete) == 0 || key_to_timestamp_[key_to_delete] != std::get<0>(to_delete)) {
  20.                 to_delete = timestamp_to_key_pq_.top();
  21.                 key_to_delete = std::get<1>(to_delete);
  22.                 timestamp_to_key_pq_.pop();
  23.             }
  24.  
  25.             data_.erase(key_to_delete);
  26.             key_to_timestamp_.erase(key_to_delete);
  27.         }
  28.  
  29.         data_[key] = value;
  30.         key_to_timestamp_[key] = ++timestamp_;
  31.         timestamp_to_key_pq_.push({ timestamp_, key });
  32.     }
  33.  
  34. private:
  35.     int capacity_;
  36.     long long timestamp_{ numeric_limits<long long>::min() };
  37.     unordered_map<int, int> data_;
  38.     unordered_map<int, long long> key_to_timestamp_;
  39.  
  40.     using QueryData = tuple<long long, int>;
  41.     priority_queue<QueryData, vector<QueryData>, std::greater<QueryData>> timestamp_to_key_pq_;
  42. };
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top