map可以动态进行插入删除等操作,但其常数太高了。
如果只用一个有序数组来存储的话,那么可以提供更好的查询复杂度的常数,同时在构建的时候由于不需要保存额外的信息所以非常节约内存:
struct my_map {
vector<pair<pii, int>> vec;
void clear() {
vec.clear();
}
int count (const pii & key) {
auto it = lower_bound (vec.begin(), vec.end(), make_pair (key, -INF));
return it == vec.end() ? 0 : it->first == key ? 1 : 0;
}
void init() {
sort (vec.begin(), vec.end());
vec.resize (unique (vec.begin(), vec.end()) - vec.begin());
}
void insert (const pii & key, int value) {
vec.push_back ({key, value});
}
int get (const pii & key) {
auto it = lower_bound (vec.begin(), vec.end(), make_pair (key, -INF));
return it ->second;
}
};
这里还需要研究一下方括号运算符、for-each使用的迭代器。等的写法,使其可以完全替代map。
TODO:无序的版本。