fork download
copy 
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <functional>
  4. #include <string>
  5. #include <unordered_map>
  6. #include <vector>
  7. using namespace std;
  8.  
  9. template<typename Hash, typename Iterator>
  10. size_t order_independent_hash(Iterator begin, Iterator end, Hash hasher)
  11. {
  12. 	std::vector<size_t> hashes;
  13. 	for (Iterator it = begin; it != end; ++it)
  14. 		hashes.push_back(hasher(*it));
  15. 	std::sort(hashes.begin(), hashes.end());
  16. 	size_t result = 0;
  17. 	for (auto it2 = hashes.begin(); it2 != hashes.end(); ++it2)
  18. 		result ^= *it2 + 0x9e3779b9 + (result<<6) + (result>>2);
  19. 	return result;
  20. }
  21.  
  22. namespace std
  23. {
  24. 	template<typename T1, typename T2>
  25. 	struct hash<std::pair<T1,T2> >
  26. 	{
  27.         typedef std::pair<T1,T2> argument_type;
  28.         typedef std::size_t result_type;
  29.  
  30.         result_type operator()(argument_type const& s) const
  31.         {
  32.             result_type const h1 ( std::hash<T1>()(s.first) );
  33.             result_type const h2 ( std::hash<T2>()(s.second) );
  34.             return h1 ^ (h2 + 0x9e3779b9 + (h1<<6) + (h1>>2));
  35.         }
  36. 	};
  37.  
  38. 	template<typename Key, typename T>
  39. 	struct hash<std::unordered_map<Key,T> >
  40. 	{
  41.         typedef std::unordered_map<Key,T> argument_type;
  42.         typedef std::size_t result_type;
  43.  
  44.         result_type operator()(argument_type const& s) const
  45.         {
  46.             return order_independent_hash(s.begin(), s.end(), std::hash<std::pair<Key,T> >());
  47.         }
  48. 	};
  49. }
  50.  
  51. int main() {
  52. 	unordered_map<int, string> tester;
  53. 	tester[1] = "one";
  54. 	tester[2] = "two";
  55. 	tester[3] = "three";
  56. 	tester[4] = "four";
  57. 	tester[5] = "five";
  58. 	cout << hash<unordered_map<int, string>>()(tester) << endl;
  59. 	return 0;
  60. }
Success #stdin #stdout 0s 3476KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1458597602
https://ideone.com/WOLFbc
language:
C++14 (gcc 8.3)
created:
9 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!