fork(1) download
copy 
  1. #include <iostream>
  2. #include <set>
  3. #include <unordered_set>
  4. #include <vector>
  5. #include <ctime>
  6.  
  7. using namespace std;
  8.  
  9. // Boost hash function for arrays, it's pretty good
  10. template <class T>
  11. inline void hash_combine(std::size_t& seed, T const& v)
  12. {
  13.     seed ^= std::hash<T>()(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
  14. }
  15.  
  16. namespace std
  17. {
  18. template<typename T>
  19. struct hash<vector<T>>
  20. {
  21. typedef vector<T> argument_type;
  22. typedef std::size_t result_type;
  23.  
  24. result_type operator()(argument_type const& in) const
  25. {
  26. 	size_t size = in.size();
  27. 	size_t seed = 0;
  28. 	for (size_t i = 0; i < size; i++) {
  29. 		hash_combine(seed, in[i]);
  30. 	}
  31. 	return seed;
  32. }
  33. };
  34. }
  35. // End of boost hash function
  36.  
  37. const int VECTORS = 1000;
  38. const int LENGTH = 100 * 1000;
  39.  
  40. int main() {
  41. 	// Test sets
  42. 	set<vector<int>> s;
  43. 	unordered_set<vector<int>> hs;
  44. 	// All vectors
  45. 	vector<vector<int>> vectors;
  46. 	// Generation
  47. 	for (int i = 0; i < VECTORS; ++i) {
  48. 		vector<int> cur;
  49. 		for (int j = 0; j < LENGTH; ++j) {
  50. 			cur.push_back(rand());
  51. 		}
  52. 		vectors.emplace_back(std::move(cur));
  53. 	}
  54. 	// Tree set
  55. 	double start = clock();
  56. 	// for each vector
  57. 	for (auto& vec : vectors) {
  58. 		// if it's not present
  59. 		if (!s.count(vec)) {
  60. 			// insert it
  61. 			s.insert(vec);
  62. 		}
  63. 	}
  64. 	double finish = clock();
  65. 	cout << "Tree set: " << (finish - start) / CLOCKS_PER_SEC << " s" << endl;
  66. 	// Hash set
  67. 	start = clock();
  68. 	// for each vector
  69. 	for (auto& vec : vectors) {
  70. 		// if it's not present
  71. 		if (!hs.count(vec)) {
  72. 			// insert it
  73. 			hs.insert(vec);
  74. 		}
  75. 	}
  76. 	finish = clock();
  77. 	cout << "Hash set: " << (finish - start) / CLOCKS_PER_SEC << " s" << endl;
  78. 	return 0;
  79. }
Success #stdin #stdout 1.48s 1179204KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Tree set: 0.113923 s
Hash set: 0.357026 s
https://ideone.com/PnTGlq
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!