高效的ID管理,随机,删除方式

• 在测试时,需要随机生成很多key进行管理,还需要随机取出,删除
  • 最早使用rb_tree_map管理,但是性能不行,反倒是ID管理成为了瓶颈,无法测出程序真正的性能瓶颈
• 使用裸数组和hash_map,可以实现O(1)的随机,添加和删除也只是hash_map的复杂的,性能提高了很多

#pragma once
#include <cstdlib>
#include <map>
#include <unordered_map>
#include <vector>

#define RAND(begin, end) ((rand() % ((end) - (begin))) + (begin))

template<class KeyType>
class KeyHolder
{
private:
    KeyType *keys{};
    int point{0};
    const int MAX_SIZE;
    std::unordered_map<KeyType, int> keyMap{};

public:
    KeyHolder(KeyHolder &) = delete;
    KeyHolder(KeyHolder &&) = delete;

    KeyHolder(int maxSize) : MAX_SIZE(maxSize)
    {
        keys = new KeyType[maxSize];
    }
    ~KeyHolder()
    {
        if (keys != nullptr)
        {
            delete[] keys;
            keys = nullptr;
        }
    }
    int Add(const KeyType &key)
    {
        if (point >= MAX_SIZE)
        {
            return -2;
        }
        auto ret = keyMap.insert(std::make_pair(key, point));
        if (!ret.second)
        {
            return -1;
        }
        keys[point] = key;
        ++point;
        return 0;
    }
    int Rand(KeyType *outKey)
    {
        if (point == 0)
        {
            return 1;
        }
        int randNum = RAND(0, point);
        (*outKey) = keys[randNum];
        return 0;
    }
    int Remove(const KeyType &key)
    {
        auto it = keyMap.find(key);
        if (it == keyMap.end())
        {
            return -1;
        }
        int index = it->second;

        // 和最后一个交换位置
        keys[index] = keys[point - 1];
        keyMap[keys[index]] = index;
        --point;
        return 0;
    }
};