s*****n
发帖数: 994 | 1 代码在此，哪位大牛帮忙瞄一眼错在哪儿
通过不了的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_;
}
}
}; |
f********4
发帖数: 988 | 2 我就扫了一眼，可能。。貌似。。你删除node的时候没有把那个node在你的map里删除
。。但我觉得好像还有别的问题吧。。 |
s*****n
发帖数: 994 | 3 那个deleteNode是在DoubleLinkedList里面删除，hashmap里删除在外面
这么做是因为get的时候也会update中间的node到head，但不在hash里删除
【在 f********4 的大作中提到】
: 我就扫了一眼，可能。。貌似。。你删除node的时候没有把那个node在你的map里删除
: 。。但我觉得好像还有别的问题吧。。
|
w**s
发帖数: 339 | 4 在超过capacity的情况下，你只是把尾指针的内容删除了，还应该调整尾指针的位置。 |
s*****n
发帖数: 994 | 5 在deleteNode里面有调整啊
if (tail_ == temp)
tail_ = tail_->prev_;
哎，这题真奇了
【在 w**s 的大作中提到】
: 在超过capacity的情况下，你只是把尾指针的内容删除了，还应该调整尾指针的位置。
|
w**s
发帖数: 339 | 6 那你岂不是先调整再删除了？删错位置了。
【在 s*****n 的大作中提到】
: 在deleteNode里面有调整啊
: if (tail_ == temp)
: tail_ = tail_->prev_;
: 哎，这题真奇了
|
s*****n
发帖数: 994 | 7 You are right.可是改完了还是fail在同一个test bench上了，我把code update了一下
C++指针操作真那么容易出bug吗。。
【在 w**s 的大作中提到】
: 那你岂不是先调整再删除了？删错位置了。
|
w**s
发帖数: 339 | 8 你删除hash table里面的成员应该是 hash_.erase(tail_->key_) 不应该hash_.erase(
tail_->value_) |
s********u
发帖数: 1109 | 9 其实我觉得，大家为什么不用stl的实现呢，那个list肯定是效率很高和bugfree的啊。
不喜欢用iterator？ |
G*****m
发帖数: 5395 | 10 DLL为啥不用std::list呢?
value)
【在 s*****n 的大作中提到】
: 代码在此，哪位大牛帮忙瞄一眼错在哪儿
: 通过不了的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){}
|
l*****3
发帖数: 32 | 11 这题建议先用stl里面的list, 过了以后再用自己的双向链表. 我开始用自己写的双向
链表也是总也过不了 |
s*****n
发帖数: 994 | 12 后来自己也发现了，但是改了还是不过，105cap的case在经过几百次get set后开始出
现wrong answer
erase(
【在 w**s 的大作中提到】
: 你删除hash table里面的成员应该是 hash_.erase(tail_->key_) 不应该hash_.erase(
: tail_->value_)
|
s*****n
发帖数: 994 | 13 有个担心是stl空间不够的时候会copy自己，那hash里面存的pointer就全失效了，以前
用vector碰到过，list应该不会
那我先试试stl的吧
【在 s********u 的大作中提到】
: 其实我觉得，大家为什么不用stl的实现呢，那个list肯定是效率很高和bugfree的啊。
: 不喜欢用iterator？
|
