|
|---|
|
|
|
|
|
|
r*******a
发帖数: 7 | 1 原题：
设计一个Map，满足下面的复杂度。
add: O(1) deletion: O(1) lookup: O(1) clear:O(1) iterate: O(number of
elements)。
请问是不是map 加上一个version number?
typedef struct elem {
int val;
int version;
} elem_t;
class map {
unordered_map T;
int cur_version;
void add (int key, int val) {
elem_t e;
e.val = val;
e.version = cur_version;
T[key] = e;
}
void clear() {
cur_version++;
}
bool lookup(int key) {
if (T.find(key) != T.end()) {
if (T[key].version == cur_version) {
return true;
} else {
return false;
}
} else {
return false;
}
}
}; | r*******a
发帖数: 7 | | A*******e
发帖数: 2419 | 3 用版本加散列可行。但是空间永远只增不减，没问题吗？
代码有点罗嗦，而且漏了access modifier。
【在 r*******a 的大作中提到】
: 原题：
: 设计一个Map，满足下面的复杂度。
: add: O(1) deletion: O(1) lookup: O(1) clear:O(1) iterate: O(number of
: elements)。
: 请问是不是map 加上一个version number?
: typedef struct elem {
: int val;
: int version;
: } elem_t;
: class map {
|
|
|
|
|
|
|
