STL::unordered_map之無序map

class template

unordered_map 

template < class Key,                                     //unordered_map::key_type

           class T,                                                 //unordered_map::mapped_type

           class Hash = hash<Key>,                      // unordered_map::hasher

           class Pred =equal_to<Key>,                   //unordered_map::key_equal

           class Alloc = allocator<pair<const Key,T> >     // unordered_map::allocator_type

           > class unordered_map; 

Unordered Map

哈希map是一種關聯容器，通過鍵值和映射值存儲元素。允許根據鍵值快速檢索各個元素。

在unordered_map中，鍵值一般用來唯一辨別元素，而對應的值是一個對象關聯到這個鍵的内容。鍵映射值的類型可能會有所不同。

在内部unordered_map的元素不以鍵值或映射的元素作任何特定的順序排序，其存儲位置取決于哈希值允許直接通過其鍵值為快速通路單個元素（具有恒定平均的平均時間複雜度）。

unordered_map容器比map容器更快地通過鍵值通路他們的單個元素，雖然unordered_map一般都是比map通過其元素的一個子集範圍疊代效率低。

哈希map允許使用操作運算符（運算符[]）以其鍵值作為參數直接通路元素。

容器屬性

關聯

   在關聯容器的元素通過鍵值引用，而不是由他們在容器中的絕對位置。

無序

 無序容器通過哈希表組織其元素的使用，允許通過鍵值快速通路其對應元素。

映射

每個元素關聯到一鍵值對應一映射值：鍵值用于識别元素，其主要内容是鍵對應的值。

唯一鍵

在容器中沒有兩個元素可以有相同的鍵。

配置設定器的喚醒

容器使用一個配置設定器對象動态地處理其存儲需求。

模闆參數

Key

關鍵值的類型。一個unordered_map中的每個元素通過鍵值被唯一辨別。

T

映射值的類型。

一個unordered_map中的每個元素是用來存儲一些資料作為其映射值。别名為成員類型unordered_map:: mapped_type。請注意，這是和unordered_map:: value_type不同的（見下文）。

Hash

學習​​資料結構​​的時候 偶然得知有個unordered_map，以前沒有用過，查了查相關内容，據說效率比map高出很多，而且耗資源也少，研究一下

至于具體效率咋樣我就不去驗證了，網上太多了

​

關鍵是

unordered_map與map的差別

boost::unordered_map， 它與 stl::map的差別就是，stl::map是按照operator<比較判斷元素是否相同，以及比較元素的大小，然後選擇合适的位置插入到樹中。是以，如果對map進行周遊（中序周遊）的話，輸出的結果是有序的。順序就是按照operator< 定義的大小排序。

而boost::unordered_map是計算元素的Hash值，根據Hash值判斷元素是否相同。是以，對unordered_map進行周遊，結果是無序的。

用法的差別就是，stl::map 的key需要定義operator< 。 而boost::unordered_map需要定義hash_value函數并且重載operator==。對于内置類型，如string，這些都不用操心。對于自定義的類型做key，就需要自己重載operator== 或者hash_value()了。 

最後，說，當不需要結果排好序時，最好用unordered_map。

​​Linux​​下使用

普通的key就不說了和map一樣

看一下用sockaddr_in 作為key的方法

[cpp] 

​​view plain​​​

​​​copy​​​

​​​​​​

​​​​​

1. <span style="font-family:Microsoft YaHei;font-size:18px;">#ifndef CSESSION_H
2. #define CSESSION_H
3. #include <netinet/in.h>
4. #include <time.h>
5. #include <map>
6. #include <string.h>
7. #include <tr1/unordered_map>  //頭檔案
8. #include <iostream>
9. using namespace std;
10. using namespace std::tr1;
11. struct Terminal
12. {
13. int             nid ; //id  the key for terminal
14. //ip  the key for Client
15. time_t          tm;   //last alive time
16. //status
17. Terminal();
18. ~Terminal();
19. const Terminal& term);
20. };
21. struct hash_func  //hash 函數
22. {
23. size_t operator()(const sockaddr_in &addr) const
24. {
25. return addr.sin_port*9999 + addr.sin_addr.s_addr;
26. }
27. };
28. struct cmp_fun //比較函數 ==
29. {
30. bool operator()(const sockaddr_in &addr1, const sockaddr_in &addr2) const
31. {
32. return memcmp(&addr1, &addr2, sizeof(sockaddr_in)) == 0 ? true:false;
33. }
34. };
35. //typedef unordered_map<int,Terminal*> MapTerminal; // Terminal socket 作為key
36. //typedef unordered_map<int,Terminal*>::iterator MapTerminal_It; //
37. typedef unordered_map<sockaddr_in, Terminal*,hash_func, cmp_fun> MapClientSession; // sockaddr_in作為key
38. typedef unordered_map<sockaddr_in, Terminal*,hash_func, cmp_fun>::iterator MapClientSession_It; //
39. #endif // CSESSION_H</span>

operator== 有兩種方式

一種是

struct st

{

 bool operator==(const st &s) const

...

}；

另一種就是自定義函數體，代碼中

struct cmp_fun

{

bool operator()(...)

...

}

必須要自定義operator==和hash_value。 重載operator==是因為，如果兩個元素的hash_value的值相同，并不能斷定這兩個元素就相同，必須再調用operator==。 當然，如果hash_value的值不同，就不需要調用operator==了。