leetcode

0 class LRUCache {

1 unordered_map<int, pair<int, int>> um;

2 queue<pair<int, int>> q;

3 int capacity;

4

5 public:

6 LRUCache(int capacity) : capacity(capacity) {}

7

8 int get(int key) {

9 auto it = um.find(key);

10 if (it == um.end()) return -1;

11 q.push({key, ++it->second.first});

12 return it->second.second;

13 }

14

15 void put(int key, int value) {

16 auto it = um.find(key);

17 if (it != um.end()) {

18 q.push({key, ++it->second.first});

19 it->second.second = value;

20 return;

21 }

22

23 if (um.size() == capacity) {

24 while (true) {

25 auto [key, time] = q.front();

26 q.pop();

27 if (um[key].first == time) {

28 um.erase(key);

29 break;

30 }

31 }

32 }

33 q.push({key, 0});

34 um[key] = {0, value};

35 }

36 };