fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. 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; }
  5.  
  6.  
  7.  
  8. class RandomSet {
  9.  
  10. 	// xor shift
  11. 	struct Xor128 {
  12. 		unsigned x, y, z, w;
  13. 		Xor128(int _w) { x = 123456789; y = 362436069; z = 521288629; w = _w; }
  14. 		unsigned nextUInt() {
  15. 			unsigned t = (x ^ (x << 11));
  16. 			x = y; y = z; z = w;
  17. 			return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
  18. 		}
  19. 	} rnd;
  20.  
  21. 	unordered_set<int> st;	// set 本体
  22. 	vector<int> v;			// set と同一の要素を格納した vector
  23.  
  24. public:
  25.  
  26. 	RandomSet(unsigned seed = 88675123) : rnd(seed), st() {}
  27.  
  28. 	// この辺は適当に増やして
  29. 	auto begin() { return st.begin(); }
  30. 	auto end() { return st.end(); }
  31. 	auto empty() { return st.empty(); }
  32. 	auto size() { return st.size(); }
  33.  
  34. 	// 要素の挿入
  35. 	auto insert(int key) {
  36. 		// https://c...content-available-to-author-only...b.io/reference/unordered_set/unordered_set/insert.html
  37. 		// pair<iterator, bool>(要素を指すイテレータ, 要素が追加されたかどうか)
  38. 		auto ret = st.insert(key);
  39. 		// 追加されたなら vector にも追加
  40. 		if (ret.second == true)
  41. 			v.push_back(key);
  42. 		return ret;
  43. 	}
  44. 	// ランダムな要素の参照
  45. 	auto random() {
  46. 		unsigned idx = rnd.nextUInt() % size();
  47. 		return v[idx];
  48. 	}
  49. 	// ランダムな要素の削除
  50. 	// 戻り値は削除した要素の key
  51. 	auto pop_random() {
  52. 		unsigned idx = rnd.nextUInt() % size();
  53. 		auto key = v[idx];
  54. 		swap(v[idx], v.back());
  55. 		st.erase(key);
  56. 		v.pop_back();
  57. 		return key;
  58. 	}
  59.  
  60. 	friend ostream& operator<<(ostream& os, const RandomSet& obj) {
  61. 		os << obj.st;
  62. 		return os;
  63. 	}
  64. };
  65.  
  66.  
  67.  
  68. int main() {
  69.  
  70. 	clock_t elapses = clock();
  71.  
  72. 	RandomSet rs;
  73.  
  74. 	int N = 10;
  75.  
  76. 	for (int i = 0; i < N; i++) {
  77. 		rs.insert(i);
  78. 		cout << "insert: " << i << endl;
  79. 		cout << "set: " << rs << endl;
  80. 	}
  81.  
  82. 	for (int i = 0; i < N; i++) {
  83. 		int x = rs.pop_random();
  84. 		cout << "pop_random: " << x << endl;
  85. 		cout << "set: " << rs << endl;
  86. 	}
  87.  
  88. 	elapses = clock() - elapses;
  89. 	cerr << (double(elapses) / CLOCKS_PER_SEC) << " sec." << endl;
  90.  
  91. 	return 0;
  92. }
Success #stdin #stdout #stderr 0s 4392KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
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: { }
stderr
copy 
0.000179 sec.
https://ideone.com/ziuy0T
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!