C++高手看下这个LC的LRU Cache的实现 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

C++高手看下这个LC的LRU Cache的实现

C++高手看下这个LC的LRU Cache的实现# JobHunting - 待字闺中

r*72015-05-15 07:05

1 楼

可以pass所有的test cases，不知道是不是显得比较初级，本人C++比较普通，谢谢指
教！
class LRUCache{
public:
typedef map::iterator> > KVType;
LRUCache(int capacity) {
mCapacity = capacity;
}

int get(int key) {
KVType::iterator it = mKeyValuePair.find(key);
if (it == mKeyValuePair.end()) {
return -1;
}
int result = it->second.first;
list::iterator keysIt = it->second.second;
mKeys.erase(keysIt);
mKeys.push_front(key);
mKeyValuePair[key] = make_pair(result, mKeys.begin());
return result;
}

void set(int key, int value) {
int result = get(key);
// already exists
if (result != -1) {
mKeyValuePair[key].first = value;
return;
}
// doesn't exists and not full
if (mKeys.size() != mCapacity) {
mKeys.push_front(key);
mKeyValuePair[key] = make_pair(value, mKeys.begin());
return;
}
// doesn't exists and full
mKeyValuePair.erase(mKeys.back());
mKeys.pop_back();
mKeys.push_front(key);
mKeyValuePair[key] = make_pair(value, mKeys.begin());
}
private:
list mKeys;
KVType mKeyValuePair;
int mCapacity;
};

a*u2015-05-15 07:05

2 楼

请问你的mKeys，pop_back()和push_front()的时间复杂度多少？如果不是O(1), 可以
考虑换成double linkedlist

a*u2015-05-15 07:05

3 楼

查了下，list的操作时间的确是O(1), 那整体设计没啥大问题。至于语言让懂c++的人
看吧

r*72015-05-15 07:05

4 楼

算法应该没啥问题，这个题也没啥算法吧，所以想让高手看看C++怎么写比较
sophisticated

【在 a*****u 的大作中提到】

: 查了下，list的操作时间的确是O(1), 那整体设计没啥大问题。至于语言让懂c++的人
: 看吧

e*i2015-05-15 07:05

5 楼

looks good! my 2cents in comments:
class LRUCache{ // maybe it's better to be templated key instead of 'int'?
public:
typedef map::iterator> > KVType; // map O(lgn)
vs unordered_map O(n) ??
LRUCache(int capacity) {
mCapacity = capacity;
}

int get(int key) {
KVType::iterator it = mKeyValuePair.find(key); //auto it = ...
if (it == mKeyValuePair.end()) {
return -1;
}
int result = it->second.first;
mKeys.erase(it->second.second); // keysIt used only once, combine
the line above
mKeys.push_front(key);
mKeyValuePair[key] = make_pair(result, mKeys.begin());
return result;
}

void set(int key, int value) {
int result = get(key); //to optimise, maybe copy the first 3 lines
in get() instead of calling get()
// since you're putting the kv on top (push_front) anyway later here.
// already exists
if (result != -1) {
mKeyValuePair[key].first = value;
return;
}
if (mKeys.size() == mCapacity) {
// doesn't exists and full
mKeyValuePair.erase(mKeys.back());
mKeys.pop_back();
}
// doesn't exists and not full
mKeys.push_front(key);
mKeyValuePair[key] = make_pair(value, mKeys.begin());
}
private:
list mKeys;
KVType mKeyValuePair;
int mCapacity; // make it const, and init with ctor; and, unsigned int
};

【在 r****7 的大作中提到】

: 可以pass所有的test cases，不知道是不是显得比较初级，本人C++比较普通，谢谢指
: 教！
: class LRUCache{
: public:
: typedef map::iterator> > KVType;
: LRUCache(int capacity) {
: mCapacity = capacity;
: }
:
: int get(int key) {