VC驿站

 找回密码
 加入驿站

QQ登录

只需一步,快速开始

搜索
查看: 2446|回复: 3

[交流] 最愛的boost容器之 unordered_map unordered_set

[复制链接]
74_avatar_middle
在线会员 发表于 2015-9-24 14:28:16 | 显示全部楼层 |阅读模式
本帖最后由 zuiwuchang 于 2015-9-24 14:32 编辑

在c++98中 提供了 兩個二叉排序樹 結構 分別是 std::set std::map
map是一個 key value的 鍵值對 set則 只有 key

set 更多用在 只需要驗證 存在性時 (比如 你發布了一個軟體 你只想知道用戶 是否已經 給過註冊 費用 而無需要 其他信息)
  1. #include <iostream>
  2. #include <set>

  3. int main()
  4. {
  5.     std::string user_code = "假裝這是一個 用戶註冊碼";

  6.     std::set<std::string> datas;

  7.     //false 此時還沒註冊
  8.     std::cout<<(datas.find(user_code) != datas.end())<<"\n";

  9.     //true 已經註冊
  10.     datas.insert(user_code);
  11.     std::cout<<(datas.find(user_code) != datas.end())<<"\n";

  12.     return 0;
  13. }
复制代码

map 則 是一個 key value 的鍵值對 其有更多 的 用處 (比如 lua 中 只有 這種 數據結構 其他 鍊錶 隊列 數組 .... 都由 key/value 模擬)
(js 中對象 也是 key/value 的 結構)
  1. #include <iostream>
  2. #include <map>
  3. typedef std::map<std::string,std::string> datas_t;

  4. void is_user(const datas_t& datas,const std::string& code)
  5. {
  6.     auto find = datas.find(code);
  7.     if(find == datas.end())
  8.     {
  9.         std::cout<<"not user\n";
  10.     }
  11.     else
  12.     {
  13.         std::cout<<find->second<<"\n";
  14.     }
  15. }
  16. int main()
  17. {
  18.     std::string user_code = "假裝這是一個 用戶註冊碼";
  19.     std::string user_name = "illusive man";

  20.     datas_t datas;

  21.     //false 此時還沒註冊
  22.     is_user(datas,user_code);

  23.     //true 已經註冊
  24.     datas[user_code] = user_name;
  25.     is_user(datas,user_code);

  26.     return 0;
  27. }
复制代码
其他 更加 詳細的 set map用法 見 c++標準庫
(C++ Primer 是本不錯的 書 而且 最新版 已經包括了 一些 c++11新增加的 內容
其中一些 有boost加入到 c++11的內容 這本書 也有介紹 記得有 shared_ptr tuple any bind ... 如果沒記錯的話)



現在回到 boost 的 unordered_map unordered_set
之所以 要先 說 map set  在於 如果 你會 用 map set 就可以 直接 使用 unordered_map unordered_set 了 它們用法 基本 一樣
只是 unordered_map unordered_set 使用 散列表 而 map set 使用 二叉排序樹
(這只是 實現上的 問題 對於 調用者來說 完全 透明)
現在 你可以 把上面 代碼中的 std::map std::set 替換為 boost::unordered_map boost::unordered_set 便可立刻 享用到 散列表 帶來的 好處
同include 要替換為 #include<boost/unordered_map.hpp> #include<boost/unordered_map.hpp>
(散列表的詳細介紹 見 https://zh.wikipedia.org/wiki/%E5%93%88%E5%B8%8C%E8%A1%A8)



因為 unordered_map unordered_set 用法 基本同 map set 下面 將 不再 提 unordered_map unordered_set 和map set 相同的 地方 詳細用法 參考 map set
只 提下 其 不同點


對於 散列表而言 需要 一個散列函數 對 其key  進行 散列 操作 對於 std 和 boost 中的 大部分 組件 而言 boost  已經 為其 進行了 特化 處理
如果 是自己 的 class  則需要 為其 特化 std::size_t hash_value(const T& )
同時 提供 operator== 的重載
  1. #include <iostream>
  2. #include <boost/unordered_set.hpp>

  3. class test_one
  4. {
  5. private:
  6.     std::string name;
  7. public:
  8.     test_one(const std::string& name)
  9.     {
  10.         this->name = name;
  11.     }
  12.     bool operator==(const test_one& right) const
  13.     {
  14.         return name == right.name;
  15.     }
  16.     friend std::size_t hash_value(const test_one& obj);

  17. };
  18. //特化 test_one
  19. std::size_t hash_value(const test_one& obj)
  20. {
  21.     return boost::hash<std::string>()(obj.name);
  22. }


  23. class test_two
  24. {
  25. private:
  26.     std::string name;
  27.     std::string company;
  28. public:
  29.     test_two(const std::string& name,const std::string& company)
  30.     {
  31.         this->name = name;
  32.         this->company = company;
  33.     }
  34.     bool operator==(const test_two& right) const
  35.     {
  36.         return name == right.name
  37.                && this->company == company;
  38.     }
  39.     friend std::size_t hash_value(const test_two& obj);

  40. };

  41. std::size_t hash_value(const test_two& obj)
  42. {
  43.     std::size_t hash        =        0;
  44.     boost::hash_combine(hash,obj.name);
  45.     boost::hash_combine(hash,obj.company);
  46.     //... 如果 還有 其他 影響 hash的 屬性 boost::hash_combine(hash,obj.XXX);
  47.     return hash;

  48. }
  49. int main()
  50. {
  51.     {
  52.         boost::unordered_set<test_one> one;
  53.         test_one key("illusive man");
  54.         std::cout<<(one.find(key) != one.end())<<"\n";

  55.         one.insert(key);
  56.         std::cout<<(one.find(key) != one.end())<<"\n";
  57.     }
  58.     {
  59.         boost::unordered_set<test_two> two;
  60.         test_two key("illusive man","Cerberus");
  61.         std::cout<<(two.find(key) != two.end())<<"\n";

  62.         two.insert(key);
  63.         std::cout<<(two.find(key) != two.end())<<"\n";
  64.     }

  65.     return 0;
  66. }
复制代码




另外 一個 unordered_map unordered_set 和 map set的 不同 在於 散列表 是無序的 而 二叉排序樹 時 有序的
故 若 你需要一個 有序的  結構 (比如 你要 保存 用戶名 並且  安 名字  排序 unordered_map unordered_set 無法 保證 順序 map set 則 使用 默認的 less 排序) 應該使用 map set
因為 unordered_map unordered_set 是 無須的 故 其 正向 和 逆向 遍歷 沒有什麼 差別 故 boost 只提供了其 正向的 迭代器 而 map set 同時 提供了 正向 逆向 迭代器

评分

参与人数 1威望 +2 驿站币 +3 热心值 +3 收起 理由
51_avatar_small Syc + 2 + 3 + 3 感谢分享!

查看全部评分





上一篇:树形控件基础操作,VC6运行
下一篇:hash 校驗工具
51_avatar_middle
online_admins 发表于 2015-9-27 20:10:30 | 显示全部楼层
感谢楼主分享这么好的东西,赞一个。。。
65_avatar_middle
在线会员 发表于 2015-10-2 21:38:35 | 显示全部楼层
其实说是无序 但是仍然是有序的吧 只是不是按规则排序。
74_avatar_middle
ico_lz  楼主| 发表于 2015-10-2 23:21:11 | 显示全部楼层
yaoyuanzhi 发表于 2015-10-2 21:38
其实说是无序 但是仍然是有序的吧 只是不是按规则排序。

所謂有序 就是指安一定規則
你都承認 不安規則 存放  又何來序
(好吧 這是個哲學問題 等我們有空時  到某個 哲學 bbs再研究吧)
您需要登录后才可以回帖 登录 | 加入驿站 qq_login

本版积分规则

关闭

站长提醒上一条 /2 下一条

QQ|小黑屋|手机版|VC驿站 ( 辽ICP备09019393号tongdun|网站地图wx_jqr

GMT+8, 2019-8-21 23:03

Powered by Discuz! X3.4

© 2009-2019 cctry.com

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