关于用STL实现LRU cache# JobHunting - 待字闺中
h*o
1 楼
先前自己写的Double link list通过了。听说用STL的list<>简单， 实现了一下，怎么
就说超时那？ 请问把node移到头可以用： dll.remove(n); dll.push_
front(n)吧？ 我看很多例子用splice.不知道是否这个原因。 一下是我的代码：麻烦
哪位给指点一下：
class Node{
public:
Node(int key=-1, int val=-1):key(key), val(val){}
int key;
int val;
};
class LRUCache{
public:
LRUCache(int capacity) {
_capacity = capacity;
_entry = new Node[_capacity];
_pos = 0; //其实不需要
}
~LRUCache() {delete[] _entry; }
int get(int key) {
if (_m.find(key) != _m.end()) { //found
Node* n = _m[key];
dll.remove(n);
dll.push_front(n);
return n->val;
}
else return -1;
}
void set(int key, int value) {
if (_m.find(key) != _m.end()) { //found
Node* n = _m[key];
n->val = value;
dll.remove(n);
dll.push_front(n);
}
else{
if (_pos == _capacity){
Node* n = dll.back();
_m.erase(n->key);
n->val = value;
n->key = key;
_m[key] = n;
dll.pop_back();
dll.push_front(n);
}
else{
Node* n = _entry+_pos; _pos++;
n->key = key; n->val = value;
dll.push_front(n);
_m[key] = n;
}
}
}
private:
Node* _entry;
int _capacity;
int _pos;
unordered_map _m;
list dll;
};
就说超时那？ 请问把node移到头可以用： dll.remove(n); dll.push_
front(n)吧？ 我看很多例子用splice.不知道是否这个原因。 一下是我的代码：麻烦
哪位给指点一下：
class Node{
public:
Node(int key=-1, int val=-1):key(key), val(val){}
int key;
int val;
};
class LRUCache{
public:
LRUCache(int capacity) {
_capacity = capacity;
_entry = new Node[_capacity];
_pos = 0; //其实不需要
}
~LRUCache() {delete[] _entry; }
int get(int key) {
if (_m.find(key) != _m.end()) { //found
Node* n = _m[key];
dll.remove(n);
dll.push_front(n);
return n->val;
}
else return -1;
}
void set(int key, int value) {
if (_m.find(key) != _m.end()) { //found
Node* n = _m[key];
n->val = value;
dll.remove(n);
dll.push_front(n);
}
else{
if (_pos == _capacity){
Node* n = dll.back();
_m.erase(n->key);
n->val = value;
n->key = key;
_m[key] = n;
dll.pop_back();
dll.push_front(n);
}
else{
Node* n = _entry+_pos; _pos++;
n->key = key; n->val = value;
dll.push_front(n);
_m[key] = n;
}
}
}
private:
Node* _entry;
int _capacity;
int _pos;
unordered_map
list
};