fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <chrono>
  5. #include <set>
  6. using namespace std;
  7.  
  8. struct Point { int x, y; };
  9. bool operator==(Point const& p1, Point const& p2)
  10. {
  11. 	return p1.x == p2.x && p1.y == p2.y;
  12. }
  13.  
  14. bool operator<(Point const& p1, Point const& p2)
  15. {
  16. 	return p1.x != p2.x ? p1.x < p2.x : p1.y < p2.y;
  17. }
  18.  
  19. void addToSortedVector(std::vector<Point>& v, const Point &p){
  20. 	auto it = std::lower_bound(v.begin(),v.end(),p);
  21. 	if(it == v.end() || !(*it == p)){
  22. 		v.insert(it,p);
  23. 	}
  24. }
  25.  
  26.  
  27. void __attribute__ ((noinline))test1(const std::vector<Point>& in,std::vector<int>& out){
  28. 	std::set<Point> points{};
  29. 	for(const auto&i:in){
  30. 		points.insert(i);
  31. 	}
  32. 	out.push_back(points.size());
  33. }
  34. void __attribute__ ((noinline))test2(const std::vector<Point>& in,std::vector<int>& out){
  35. 	std::vector<Point> points{};
  36. 	for(const auto&i:in){
  37. 		addToSortedVector(points,i);
  38. 	}
  39. 	out.push_back(points.size());
  40. }
  41.  
  42.  
  43.  
  44. int main() {
  45. 	const std::vector<Point> input{{{99,0},{98,0},{97,4},{96,4},{95,0},{94,3},{93,0},{92,0},{91,2},{90,0},{89,0},{88,0},{87,4},{4,4},{0,0},{0,3},{2,2},{0,9},{0,2},{1,0},{0,0},{0,0},{4,4},{4,4},{0,0},{0,3},{0,0},{0,0},{0,2},{1,0},{0,0},{0,0},{4,4},{4,4},{0,0},{0,3},{2,2},{3,9},{03,2},{1,3},{0,3},{3,0},{2,4},{3,4},{5,0},{05,3},{0,5},{5,0},{5,2},{1,5},{5,0},{6,0},{6,4},{7,4},{7,0},{7,3},{7,2},{7,9},{7,2},{1,7}}};
  46. 	std::vector<int> out;
  47.  
  48. 	std::chrono::nanoseconds time[2]{{},{}};
  49.  
  50. 	for(int i=0;i<100;i++){
  51. 		const auto t1 = std::chrono::high_resolution_clock::now();
  52. 		test1(input,out);
  53. 		const auto t2 = std::chrono::high_resolution_clock::now();
  54. 		time[0] += t2 - t1;
  55. 		const auto t3 = std::chrono::high_resolution_clock::now();
  56. 		test2(input,out);
  57. 		const auto t4 = std::chrono::high_resolution_clock::now();
  58. 		time[1] += t4 - t3;
  59. 	}
  60.  
  61. 	typedef std::chrono::nanoseconds output_time;
  62. 	const char* const out_unit = " ns";
  63.  
  64. 	std::cout << "1: " << std::chrono::duration_cast<output_time>(time[0]).count() << out_unit << "\n";
  65. 	std::cout << "2: " << std::chrono::duration_cast<output_time>(time[1]).count() << out_unit << "\n";
  66. 	cout << out.size(); //just to stop the optimizer from stomping on us
  67. 	return 0;
  68. }
Success #stdin #stdout 0s 3432KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1: 831853 ns
2: 589159 ns
200
https://ideone.com/E2gqOd
language:
C++14 (gcc 8.3)
created:
11 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!