Code

Solution of problem 146 is showed below. You can also find it here.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
static const int _ = []() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
return 0;
}();

class LRUCache {
public:
LRUCache(int capacity) {
cap = capacity;
}

int get(int key) {
if( !mp.count( key ) ) return -1;
lst.splice( lst.begin(), lst, mp[key] );
return mp[key]->second;
}

void put(int key, int value) {
if( mp.count( key ) ) {
mp[key]->second = value;
lst.splice( lst.begin(), lst, mp[key] );
} else {
lst.push_front( make_pair( key, value ) );
mp[key] = lst.begin();
if( lst.size() > cap ) {
mp.erase( lst.rbegin()->first );
lst.pop_back();
}
}
}

private:
int cap;
unordered_map<int, list<pair<int, int>>::iterator> mp;
list<pair<int, int>> lst;
};

/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/

Solution

To solve the problem, you need to build a list to store the order of “key”-“value” pair and to build a map to store “key”-“position in list” pair. Thus, when putting a “key”-“value” pair, you will easily know its position and update the order.

Valueable Function

The interesting part of this code is the function “splice” of list. It can be found on c++ reference.

1
void splice (iterator position, list& x, iterator i);

The function will transfer element “i” in list “x” to specific “position”.

Before using this funcition, I wrote a segment of code to implement the function by myself but it runs slower than the function. In this case, by using this function, I transfer the “mp[key]” in list “lst” to the front of the list “lst”.