#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://c...content-available-to-author-only...b.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; }
Standard input is empty
insert: 0 set: {0} insert: 1 set: {1, 0} insert: 2 set: {2, 1, 0} insert: 3 set: {3, 2, 1, 0} insert: 4 set: {4, 0, 1, 2, 3} insert: 5 set: {5, 4, 0, 1, 2, 3} insert: 6 set: {6, 5, 4, 0, 1, 2, 3} insert: 7 set: {7, 6, 5, 4, 0, 1, 2, 3} insert: 8 set: {8, 7, 6, 5, 4, 0, 1, 2, 3} insert: 9 set: {9, 8, 7, 6, 5, 4, 0, 1, 2, 3} pop_random: 6 set: {9, 8, 7, 5, 4, 0, 1, 2, 3} pop_random: 3 set: {9, 8, 7, 5, 4, 0, 1, 2} pop_random: 2 set: {9, 8, 7, 5, 4, 0, 1} pop_random: 7 set: {9, 8, 5, 4, 0, 1} pop_random: 0 set: {9, 8, 5, 4, 1} pop_random: 4 set: {9, 8, 5, 1} pop_random: 8 set: {9, 5, 1} pop_random: 9 set: {5, 1} pop_random: 5 set: {1} pop_random: 1 set: { }
0.000179 sec.