java HashSet vs. c++ unordered_set

感觉这两个应该是java和C++里最常用的hash table了。我的问题是为啥在c++里定义一个unordered_set<vector<int>>要报错。但是java 允许这个Set<List<Integer>>呢？
google了一下也找不到合适的答案。来地里求助下。谢谢了！

因为std::unordered_set的完全定义（ http://en.cppreference.com/w/cpp/container/unordered_set ）是：

1. template<
   
2.     class Key,
   
3.     class Hash = std::hash<Key>,
   
4.     class KeyEqual = std::equal_to<Key>,
   
5.     class Allocator = std::allocator<Key>
   
6. > class unordered_set;

复制代码

在不显式提供Hash算子的情况下，默认使用std::hash作为哈希函数。

而std::hash只实现了基础类型（ http://en.cppreference.com/w/cpp/utility/hash ）的特化，例如int、double、std::string之类的 —— 这方面的知识稍微有点复杂。

在不追求极限性能的情况下我们可以自己写一些std::hash对于复合数据结构的特化，例如std::pair、std::tuple和std::vector，参考实现如下：

1. #include <cstddef>
   
2. #include <iostream>
   
3. #include <tuple>
   
4. #include <type_traits>
   
5. #include <unordered_set>
   
6. #include <utility>
   
7. #include <vector>
   
8. 
   
9. namespace details {
   
10. 
    
11. inline std::size_t CombineHashes(const std::size_t first_hash,
    
12.                                  const std::size_t second_hash) {
    
13.   // C++ boost库里的组合hash方法
    
14.   // https://stackoverflow.com/questions/2590677/how-do-i-combine-hash-values-in-c0x
    
15.   return first_hash
    
16.       ^ (second_hash + 0x9e3779b9u + (first_hash << 6) + (first_hash >> 2));
    
17. }
    
18. 
    
19. }  // namespace project
    
20. 
    
21. namespace std {
    
22. 
    
23. template <typename FirstT, typename SecondT>
    
24. struct hash<pair<FirstT, SecondT>> {
    
25.   size_t operator()(const pair<FirstT, SecondT> &value) const {
    
26.     size_t first_hash = hash<FirstT>()(value.first);
    
27.     size_t second_hash = hash<SecondT>()(value.second);
    
28.     return details::CombineHashes(first_hash, second_hash);
    
29.   }
    
30. };
    
31. 
    
32. template <typename ...Ts>
    
33. struct hash<tuple<Ts...>> {
    
34.   size_t operator()(const tuple<Ts...> &value) const {
    
35.     return computeHash<sizeof...(Ts)>(value);
    
36.   }
    
37. 
    
38.   template <size_t idx>
    
39.   size_t computeHash(const tuple<Ts...> &value,
    
40.                      typename std::enable_if<idx == 0>::type * = 0) const {
    
41.     return 0;
    
42.   }
    
43. 
    
44.   template <size_t idx>
    
45.   size_t computeHash(const tuple<Ts...> &value,
    
46.                      typename std::enable_if<idx != 0>::type * = 0) const {
    
47.     using T = typename tuple_element<idx-1, tuple<Ts...>>::type;
    
48.     const auto &entry = std::get<idx-1>(value);
    
49.     return details::CombineHashes(hash<T>()(entry),
    
50.                                   computeHash<idx-1>(value));
    
51.   }
    
52. };
    
53. 
    
54. template <typename T>
    
55. struct hash<vector<T>> {
    
56.   size_t operator()(const vector<T> &value) const {
    
57.     size_t hash_value = 0;
    
58.     for (const auto &entry : value) {
    
59.       hash_value = details::CombineHashes(hash_value, hash<T>()(entry));
    
60.     }
    
61.     return hash_value;
    
62.   }
    
63. };
    
64. 
    
65. }  // namespace std
    
66. 
    
67. int main(int argc, char *argv[]) {
    
68.   std::unordered_set<std::vector<int>> data;
    
69. 
    
70.   data.emplace(std::vector<int>{1, 2, 3});
    
71.   data.emplace(std::vector<int>{4, 5});
    
72.   data.emplace(std::vector<int>{1, 2, 3});
    
73. 
    
74.   std::cout << "# entries = " << data.size() << "\n";
    
75.   // 输出
    
76.   // 2
    
77. 
    
78.   for (const auto &entry : data) {
    
79.     for (const auto &value : entry) {
    
80.       std::cout << value << " ";
    
81.     }
    
82.     std::cout << "\n";
    
83.   }
    
84.   // 输出（顺序不一定）：
    
85.   // 1 2 3
    
86.   // 4 5
    
87. 
    
88.   return 0;
    
89. }
    

复制代码

你可以把上面代码中main函数前面的代码做成一个头文件"hash.h"，然后每次include这个头文件就可以使用vector、pair、tuple的任意组合了，比如：

1.   std::unordered_set<std::vector<std::pair<std::vector<std::string>, std::tuple<float, float, float>>>> data;
   

复制代码

C++ unordered_set of vectors

You'll have to come up with a hash though, since the default one (std::hash<std::vector<int>>) will not be implemented.

http://www.cplusplus.com/reference/functional/hash/

Template里面没有vector<int>只有vector<bool>，我觉得这就是为什么会报错的原因吧……找不到合适的template

magicsets 发表于 2018-4-22 12:48
因为std::unordered_set的完全定义（ http://en.cppreference.com/w/cpp/container/unordered_set ）是：在 ...

我去竟然之前没看到。这么好的回答，实在感谢！
所以就是说Java内部已经实现了你这些代码，对吗？我试了python的set也不支持hash list。有点吃惊java在这方面做得这么好

GoldenArcher 发表于 2018-4-22 12:51
C++ unordered_set of vectors

You'll have to come up with a hash though, since the default one (st ...

所以就是说Java Set内部是实现了的，对吗？我试了python的set也不支持hash list。有点吃惊java在这方面做得这么好

讲效率还是Java牛逼 C++隐形的坑太多了

kungfu 发表于 2018-5-17 09:38
讲效率还是Java牛逼 C++隐形的坑太多了

C++要求的确很高

ohshout 发表于 2018-5-17 02:46
我去竟然之前没看到。这么好的回答，实在感谢！
所以就是说Java内部已经实现了你这些代码，对吗？我试了 ...

是的，Java有List的hashCode()以及equals()的默认实现：

1.     /**
   
2.      * Returns the hash code value for this list.  The hash code of a list
   
3.      * is defined to be the result of the following calculation:
   
4.      * <pre>{@code
   
5.      *     int hashCode = 1;
   
6.      *     for (E e : list)
   
7.      *         hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
   
8.      * }</pre>
   
9.      * This ensures that <tt>list1.equals(list2)</tt> implies that
   
10.      * <tt>list1.hashCode()==list2.hashCode()</tt> for any two lists,
    
11.      * <tt>list1</tt> and <tt>list2</tt>, as required by the general
    
12.      * contract of {[url=home.php?mod=space&uid=60079]@link[/url] Object#hashCode}.
    
13.      *
    
14.      * [url=home.php?mod=space&uid=160137]@return[/url] the hash code value for this list
    
15.      * @see Object#equals(Object)
    
16.      * @see #equals(Object)
    
17.      */
    
18.     int hashCode();

复制代码

1.     /**
   
2.      * Compares the specified object with this list for equality.  Returns
   
3.      * <tt>true</tt> if and only if the specified object is also a list, both
   
4.      * lists have the same size, and all corresponding pairs of elements in
   
5.      * the two lists are <i>equal</i>.  (Two elements <tt>e1</tt> and
   
6.      * <tt>e2</tt> are <i>equal</i> if <tt>(e1==null ? e2==null :
   
7.      * e1.equals(e2))</tt>.)  In other words, two lists are defined to be
   
8.      * equal if they contain the same elements in the same order.  This
   
9.      * definition ensures that the equals method works properly across
   
10.      * different implementations of the <tt>List</tt> interface.
    
11.      *
    
12.      * @param o the object to be compared for equality with this list
    
13.      * @return <tt>true</tt> if the specified object is equal to this list
    
14.      */
    
15.     boolean equals(Object o);

复制代码

其实C++也可以添加类似支持，就一点点代码，但是naive的实现性能可能不好，随意添加的话就有违STL的设计哲学... 或者是标准化委员会行动慢之类的原因，总之就是没有

相比之下Java就是死猪不怕开水烫：我标准库性能就这样，爱用不用...