代码在此,哪位大牛帮忙瞄一眼错在哪儿
通过不了的bench不小,转到自己程序里debug不容易
class DLL{
public:
int key_;
int value_;
DLL* prev_;
DLL* next_;
DLL (int key, int value, DLL* prev, DLL* next): key_(key), value_(value)
, prev_(prev), next_(next){}
};
class LRUCache{
public:
int capacity_;
DLL* head_;
DLL* tail_;
unordered_map hash_;
LRUCache(int capacity):capacity_(capacity), head_(NULL),tail_(NULL){
}
void insertHead (DLL* temp){
temp->next_ = head_;
if (head_)
head_->prev_ = temp;
head_ = temp;
if (tail_ == NULL)
tail_ = temp;
}
void deleteNode (DLL* temp){
if (temp->prev_){
temp->prev_->next_ = temp->next_;
}
if (temp->next_){
temp->next_->prev_ = temp->prev_;
}
if (tail_ == temp)
tail_ = tail_->prev_;
if (head_ == temp)
head_ = head_->next_;
}
int get(int key) {
if (hash_.find(key) == hash_.end()){
return -1;
}
DLL* temp = hash_[key];
deleteNode (temp);
insertHead (temp);
return hash_[key]->value_;
}
void set(int key, int value) {
if (hash_.find(key) != hash_.end()){
hash_[key]->value_ = value;
DLL* temp = hash_[key];
deleteNode (temp);
insertHead (temp);
}else{
if (hash_.size() >= capacity_){
hash_.erase(tail_->value_);
deleteNode(tail_);
delete tail_;
}
DLL* temp = new DLL(key, value, NULL, head_);
insertHead (temp);
hash_[key] = head_;
}
}
};