前两点一个unordered_set就可以完成,最后一点要求随机访问,unordered_set不支持随机访问,如果参照水塘抽样算法,可以等概率获得一个随机结果,但水塘抽样的时间复杂度是O(N),所以不行。 这里采用的是哈希表的方式,每个Key都附着一个时间戳(可以是size++),建立key和index之间的双向映射关系,于是可以根据等概率随机的index(小于等于size)找出对应的key。 需要特别设计的是delete时,如何防止移除了indexKey哈希表中这一元素带来的Index随机访问的空洞问题。
template<typename T>
class RandomPool {
public:
void insert(T k) {
if (keyIndexMap_.find(k) == keyIndexMap_.end()) {
keyIndexMap_.insert(make_pair(k, size));
indexKeyMap_.insert(make_pair(size++, k));
}
}
void deleteKey(T k) {
if (keyIndexMap_.find(k) == keyIndexMap_.end())
return;
//处理删除后的下标空洞问题,因为size是连续的
int deleteIndex = keyIndexMap_[k];
T lastKey = indexKeyMap_[size];
keyIndexMap_.insert(make_pair(lastKey, deleteIndex));
indexKeyMap_.insert(make_pair(deleteIndex, lastKey));
keyIndexMap_.erase(k);
indexKeyMap_.erase(size);
size--;
}
//等概率随机返回。
T getRamdomKey() {
if (size == 0) return T();
int random = rand() % size;
return indexKeyMap_[random];
}
private:
int size_ = 0;//简易时间戳
//创建双向映射
unordered_map<T, int> keyIndexMap_;
unordered_map<int, T> indexKeyMap_;
};