image.png

    前两点一个unordered_set就可以完成，最后一点要求随机访问，unordered_set不支持随机访问，如果参照水塘抽样算法，可以等概率获得一个随机结果，但水塘抽样的时间复杂度是O(N)，所以不行。 这里采用的是哈希表的方式，每个Key都附着一个时间戳(可以是size++)，建立key和index之间的双向映射关系，于是可以根据等概率随机的index(小于等于size)找出对应的key。 需要特别设计的是delete时，如何防止移除了indexKey哈希表中这一元素带来的Index随机访问的空洞问题。

    1.         template<typename T>
    2.         class RandomPool {
    3.         public:
    4.             void insert(T k) {
    5.                 if (keyIndexMap_.find(k) == keyIndexMap_.end()) {
    6.                     keyIndexMap_.insert(make_pair(k, size));
    7.                     indexKeyMap_.insert(make_pair(size++, k));
    8.                 }
    9.             }
    10.             void deleteKey(T k) {
    11.                 if (keyIndexMap_.find(k) == keyIndexMap_.end())
    12.                     return;
    13.                 //处理删除后的下标空洞问题，因为size是连续的
    14.                 int deleteIndex = keyIndexMap_[k];
    15.                 T lastKey = indexKeyMap_[size];
    16.                 keyIndexMap_.insert(make_pair(lastKey, deleteIndex));
    17.                 indexKeyMap_.insert(make_pair(deleteIndex, lastKey));
    18.                 keyIndexMap_.erase(k);
    19.                 indexKeyMap_.erase(size);
    20.                 size--;
    21.             }
    22.             //等概率随机返回。
    23.             T getRamdomKey() {
    24.                 if (size == 0) return T();
    25.                 int random = rand() % size;
    26.                 return indexKeyMap_[random];
    27.             }
    28.         private:
    29.             int size_ = 0;//简易时间戳
    30.             //创建双向映射
    31.             unordered_map<T, int> keyIndexMap_;
    32.             unordered_map<int, T> indexKeyMap_;
    33.         };