一亩三分地《新生手册+美国生活指南》下载

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
硅谷知名AI创业公司
图灵视频
招聘多个工程师职位
查看: 464|回复: 7
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
我的人缘0
ohshout 发表于 2018-4-22 11:09:59 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  87% (7)
 
 
12% (1)  踩

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

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

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

上一篇:每日刷题记录
下一篇:马上暑假了。刷题打卡。
我的人缘0
magicsets 发表于 2018-4-22 12:48:37 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  97% (235)
 
 
2% (6)  踩
本帖最后由 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;
复制代码
回复

使用道具 举报

全球28万学生4.7分推荐
我的人缘1
GoldenArcher 发表于 2018-4-22 12:51:58 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (311)
 
 
4% (15)  踩
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
回复

使用道具 举报

我的人缘0
 楼主| ohshout 发表于 2018-5-17 02:46:10 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  87% (7)
 
 
12% (1)  踩
magicsets 发表于 2018-4-22 12:48
因为std::unordered_set的完全定义( http://en.cppreference.com/w/cpp/container/unordered_set )是:在 ...

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

使用道具 举报

我的人缘0
 楼主| ohshout 发表于 2018-5-17 02:47:54 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  87% (7)
 
 
12% (1)  踩
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在这方面做得这么好

21.000+ students read the Road to learn React. The course weaves all the opinionated roadmaps into one roadmap to master React. It gives you all the fundamentals in React. You will build a Hacker News App along the way.

回复

使用道具 举报

我的人缘0
kungfu 发表于 2018-5-17 09:38:15 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  53% (35)
 
 
46% (30)  踩
讲效率还是Java牛逼 C++隐形的坑太多了
回复

使用道具 举报

我的人缘0
kungfu 发表于 2018-5-17 09:39:54 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  53% (35)
 
 
46% (30)  踩
kungfu 发表于 2018-5-17 09:38
讲效率还是Java牛逼 C++隐形的坑太多了

C++要求的确很高
回复

使用道具 举报

我的人缘0
magicsets 发表于 2018-5-17 11:59:59 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (235)
 
 
2% (6)  踩
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大米 +3 收起 理由
ohshout + 3 很有用的信息!

查看全部评分

With React+D3v4 you'll learn the basics of building fast data visualization components in about an hour.

回复

使用道具 举报

游客
请先登录

本版积分规则

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

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

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

GMT+8, 2018-8-22 05:57

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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