学习map和hash

学习map和hash_map

练习代码：

 1 #include <stdlib.h>
 2 #include <hash_map>
 3 #include <map>
 4 #include <string>
 5 using namespace std;
 6 
 7 struct cmp
 8 {
 9     // 重载operator()
10     // 注意：compare函数的参数必须写成const类型，否则无法编译通过
11     // 这里是有意使string按字典序的反序排列
12     bool operator()(const string& str1, const string& str2)
13     {
14         return str1>str2;
15     }
16 };
17 
18 
19 int main()
20 {
21     printf(">> map:
");
22     // 基于RB-Tree的map
23     // 能自动排序，快速检索、删除、插入
24     map<string, int, cmp> m;
25     m.insert(make_pair(string("Clark"), 12));
26     m.insert(make_pair(string("Jone"), 8));
27     m.insert(make_pair(string("Ada"), 1));
28     m.insert(make_pair(string("Lee"), 5));
29     m[string("Jack")]++;
30     m[string("Sam")] = m[string("Mike")] + 2;
31 
32     // 重复插入无效
33     m.insert(make_pair(string("Lee"), 8));
34 
35     map<string, int, cmp>::iterator iter;
36 
37     // map的检索时间复杂度为O(lnN)
38     iter = m.find(string("Mike"));
39     if (iter != m.end())
40     {
41         printf("Found Mike !
");
42         m.erase(string("Mike"));
43         printf("Deleted Mike !
");
44     }
45 
46     printf(">> One by one :
");
47     for (iter = m.begin(); iter != m.end(); iter++)
48         printf("Key=%s, Value=%d
", iter->first.c_str(), iter->second);
49     
50     printf(">> hash_map:
");
51     // 基于hash_table的hash_map
52     // 能快速减速、删除、插入，不能排序
53     hash_map<string, int> h_m;
54     h_m.insert(make_pair(string("Clark"), 12));
55     h_m.insert(make_pair(string("Jone"), 8));
56     h_m.insert(make_pair(string("Ada"), 1));
57     h_m.insert(make_pair(string("Lee"), 5));
58     h_m[string("Jack")]++;
59     h_m[string("Sam")] = h_m[string("Mike")] + 2;
60 
61     // 重复插入无效
62     h_m.insert(make_pair(string("Lee"), 8));
63     
64     hash_map<string, int>::iterator h_iter;
65 
66     // hash_map的检索时间复杂度为O(1)，优于RB-Tree的map
67     h_iter = h_m.find("Mike");
68     if (h_iter != h_m.end())
69     {
70         printf("Found Mike !
");
71         h_m.erase(string("Mike"));
72         printf("Deleted Mike !
");
73     }
74 
75     printf(">> One by one :
");
76     for (h_iter = h_m.begin(); h_iter != h_m.end(); h_iter++)
77         printf("Key=%s, Value=%d
", h_iter->first.c_str(), h_iter->second);
78 
79     system("pause");
80     return 0;
81 }

输出结果：

>> map:
Found Mike !
Deleted Mike !
>> One by one :
Key=Sam, Value=2
Key=Lee, Value=5
Key=Jone, Value=8
Key=Jack, Value=1
Key=Clark, Value=12
Key=Ada, Value=1
>> hash_map:
Found Mike !
Deleted Mike !
>> One by one :
Key=Clark, Value=12
Key=Sam, Value=2
Key=Jone, Value=8
Key=Lee, Value=5
Key=Ada, Value=1
Key=Jack, Value=1
请按任意键继续. . .