fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <bits/extc++.h>
  3.  
  4. int main() {
  5. 	using namespace std;
  6. 	using namespace chrono;
  7. 	using namespace __gnu_pbds;
  8. 	using clock = high_resolution_clock;
  9. 	const int M = 2, N = 2e4;
  10. 	using ivec = array<int,N>;
  11. 	using imat = array<ivec,M>;
  12. 	using iset = set<int>;
  13. 	mt19937 random(clock::now().time_since_epoch().count());
  14. 	set<int> s; 
  15. 	tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> t;
  16. 	const function<int(int)> tester[] = {
  17. 		[&](int x){ return int(distance(s.begin(),s.find(x))); },
  18. 		[&](int x){ return int(t.order_of_key(x)); } };
  19. 	int v[N], result[M][N];
  20. 	const auto test_set = [&](const string& prompt, int i) {
  21. 		const auto t0 = clock::now();
  22. 		const auto& f = tester[i];
  23. 		for (int j = 0; j < N; ++j)
  24. 			result[i][j] = f(v[j]);
  25. 		const auto t1 = clock::now();
  26. 		const auto time = duration_cast<milliseconds>(t1-t0).count();
  27. 		cout << prompt << ": elapsed time = " << time << " msec." << endl; };
  28. 	for (int x, size = 0; size < N; )
  29. 		if (x = random(), s.find(x) == s.end())
  30. 			s.insert(x), t.insert(x), v[size++] = x;
  31. 	shuffle(v,v+N,random), test_set("iset",0), test_set("oset",1);
  32. 	for (int j = 0; j < N; ++j)
  33. 		if (result[0][j] != result[1][j])
  34. 			cout << "Failed.", exit(0);
  35. 	cout << "Passed"; }
  36.  
Success #stdin #stdout 2.84s 5700KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
iset: elapsed time = 2834 msec.
oset: elapsed time = 2 msec.
Passed
https://ideone.com/j0jt0Q
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

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!