ランダム要素の参照・削除が定数時間 O(1) の std::set 拡張 (C++)

マラソンマッチとか連結グラフのランダム生成*1とかで使えそうなデータ構造 (名前ついてたら教えて)

set の要素を格納した vector を用意しておけば，erase を末尾要素との swap + pop_back で出来るという寸法

#include <bits/stdc++.h>
using namespace std;

template <typename _Ty> ostream& operator << (ostream& o, const unordered_set<_Ty>& s) { if (s.empty()) { o << "{ }"; return o; } o << "{" << *(s.begin()); for (auto itr = ++s.begin(); itr != s.end(); itr++) { o << ", " << *itr; } o << "}"; return o; }



class RandomSet {

    // xor shift
    struct Xor128 {
        unsigned x, y, z, w;
        Xor128(int _w) { x = 123456789; y = 362436069; z = 521288629; w = _w; }
        unsigned nextUInt() {
            unsigned t = (x ^ (x << 11));
            x = y; y = z; z = w;
            return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
        }
    } rnd;

    unordered_set<int> st;   // set 本体
    vector<int> v;           // set と同一の要素を格納した vector

public:

    RandomSet(unsigned seed = 88675123) : rnd(seed), st() {}

    // この辺は適当に増やして
    auto begin() { return st.begin(); }
    auto end() { return st.end(); }
    auto empty() { return st.empty(); }
    auto size() { return st.size(); }

    // 要素の挿入
    auto insert(int key) {
        // https://cpprefjp.github.io/reference/unordered_set/unordered_set/insert.html
        // pair<iterator, bool>(要素を指すイテレータ, 要素が追加されたかどうか)
        auto ret = st.insert(key);
        // 追加されたなら vector にも追加
        if (ret.second == true)
            v.push_back(key);
        return ret;
    }
    // ランダムな要素の参照
    auto random() {
        unsigned idx = rnd.nextUInt() % size();
        return v[idx];
    }
    // ランダムな要素の削除
    // 戻り値は削除した要素の key
    auto pop_random() {
        unsigned idx = rnd.nextUInt() % size();
        auto key = v[idx];
        swap(v[idx], v.back());
        st.erase(key);
        v.pop_back();
        return key;
    }

    friend ostream& operator<<(ostream& os, const RandomSet& obj) {
        os << obj.st;
        return os;
    }
};



int main() {

    clock_t elapses = clock();

    RandomSet rs;

    int N = 10;

    for (int i = 0; i < N; i++) {
        rs.insert(i);
        cout << "insert: " << i << endl;
        cout << "set: " << rs << endl;
    }

    for (int i = 0; i < N; i++) {
        int x = rs.pop_random();
        cout << "pop_random: " << x << endl;
        cout << "set: " << rs << endl;
    }

    elapses = clock() - elapses;
    cerr << (double(elapses) / CLOCKS_PER_SEC) << " sec." << endl;

    return 0;
}

ideone.com

*1:関連 :
chillbrains.hateblo.jp