Set

class TSampleSet {
    std::vector<int> values;
    std::unordered_map<int, size_t> valueToIndex;

    void insert(int x) {
        if (valueToIndex.count(x)) {
            return;
        }
        valueToIndex[x] = std::size(values);
        values.push_back(x);
    }

    void remove(int x) {
        if (!valueToIndex.count(x)) {
            return;
        }
        auto it = valueToIndex.find(x);
        size_t currentIndex = it->second;
        valueToIndex.remove(it);
        if (currentIndex + 1 == std::size(values)) {
            values.pop_back();
            return;
        }

        std::swap(values.back(), values[currentIndex]);
        valueToIndex[values[currentIndex]] = currentIndex;

        values.pop_back();
    }

    bool contains(int x) const {
        return valueToIndex.count(x) > 0;
    }

    int sample() {
        return values[rand() % std::size(values)];
    }

};