San Jose各个房价 <1.5m 区域买房总结

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
把贵司招聘信息放这里
查看: 354|回复: 7
收起左侧

[学C/C++] java HashSet vs. c++ unordered_set

[复制链接] |试试Instant~ |关注本帖
ohshout 发表于 2018-4-22 11:09:59 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
感觉这两个应该是java和C++里最常用的hash table了。我的问题是为啥在c++里定义一个unordered_set<vector<int>>要报错。但是java 允许这个Set<List<Integer>>呢?
google了一下也找不到合适的答案。来地里求助下。谢谢了!
magicsets 发表于 2018-4-22 12:48:37 | 显示全部楼层
本帖最后由 magicsets 于 2018-4-22 12:54 编辑

因为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. namespace details {

  9. inline std::size_t CombineHashes(const std::size_t first_hash,
  10.                                  const std::size_t second_hash) {
  11.   // C++ boost库里的组合hash方法
  12.   // https://stackoverflow.com/questions/2590677/how-do-i-combine-hash-values-in-c0x
  13.   return first_hash
  14.       ^ (second_hash + 0x9e3779b9u + (first_hash << 6) + (first_hash >> 2));
  15. }

  16. }  // namespace project

  17. namespace std {

  18. template <typename FirstT, typename SecondT>
  19. struct hash<pair<FirstT, SecondT>> {
  20.   size_t operator()(const pair<FirstT, SecondT> &value) const {
  21.     size_t first_hash = hash<FirstT>()(value.first);
  22.     size_t second_hash = hash<SecondT>()(value.second);
  23.     return details::CombineHashes(first_hash, second_hash);
  24.   }
  25. };

  26. template <typename ...Ts>
  27. struct hash<tuple<Ts...>> {
  28.   size_t operator()(const tuple<Ts...> &value) const {
  29.     return computeHash<sizeof...(Ts)>(value);
  30.   }

  31.   template <size_t idx>
  32.   size_t computeHash(const tuple<Ts...> &value,
  33.                      typename std::enable_if<idx == 0>::type * = 0) const {
  34.     return 0;
  35.   }

  36.   template <size_t idx>
  37.   size_t computeHash(const tuple<Ts...> &value,
  38.                      typename std::enable_if<idx != 0>::type * = 0) const {
  39.     using T = typename tuple_element<idx-1, tuple<Ts...>>::type;
  40.     const auto &entry = std::get<idx-1>(value);
  41.     return details::CombineHashes(hash<T>()(entry),
  42.                                   computeHash<idx-1>(value));
  43.   }
  44. };

  45. template <typename T>
  46. struct hash<vector<T>> {
  47.   size_t operator()(const vector<T> &value) const {
  48.     size_t hash_value = 0;
  49.     for (const auto &entry : value) {
  50.       hash_value = details::CombineHashes(hash_value, hash<T>()(entry));
  51.     }
  52.     return hash_value;
  53.   }
  54. };

  55. }  // namespace std

  56. int main(int argc, char *argv[]) {
  57.   std::unordered_set<std::vector<int>> data;

  58.   data.emplace(std::vector<int>{1, 2, 3});
  59.   data.emplace(std::vector<int>{4, 5});
  60.   data.emplace(std::vector<int>{1, 2, 3});

  61.   std::cout << "# entries = " << data.size() << "\n";
  62.   // 输出
  63.   // 2

  64.   for (const auto &entry : data) {
  65.     for (const auto &value : entry) {
  66.       std::cout << value << " ";
  67.     }
  68.     std::cout << "\n";
  69.   }
  70.   // 输出(顺序不一定):
  71.   // 1 2 3
  72.   // 4 5

  73.   return 0;
  74. }
复制代码
你可以把上面代码中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;
复制代码
回复 支持 1 反对 0

使用道具 举报

全球28万学生4.7分推荐
GoldenArcher 发表于 2018-4-22 12:51:58 | 显示全部楼层
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
回复 支持 反对

使用道具 举报

 楼主| ohshout 发表于 2018-5-17 02:46:10 | 显示全部楼层
magicsets 发表于 2018-4-22 12:48
因为std::unordered_set的完全定义( http://en.cppreference.com/w/cpp/container/unordered_set )是:在 ...

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

使用道具 举报

 楼主| ohshout 发表于 2018-5-17 02:47:54 | 显示全部楼层
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在这方面做得这么好
回复 支持 反对

使用道具 举报

kungfu 发表于 2018-5-17 09:38:15 | 显示全部楼层
讲效率还是Java牛逼 C++隐形的坑太多了
回复 支持 反对

使用道具 举报

kungfu 发表于 2018-5-17 09:39:54 | 显示全部楼层
kungfu 发表于 2018-5-17 09:38
讲效率还是Java牛逼 C++隐形的坑太多了

C++要求的确很高
回复 支持 反对

使用道具 举报

magicsets 发表于 2018-5-17 11:59:59 | 显示全部楼层
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就是死猪不怕开水烫:我标准库性能就这样,爱用不用...

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-26 20:39

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表