map hash_map unordered_map 性能测试_C/C++_编程开发_程序员俱乐部

原文：http://blog.chinaunix.net/uid-20384806-id-3055333.html 测试条件： gcc version 4.2.1 20070719? [FreeBSD] FreeBSD ?7.2-RELEASE #0: Fri May? 1 07:18:07 UTC 2009???? root@driscoll.cse.buffalo.edu:/usr/obj/usr/src/sys/GENERIC? amd64
Intel(R) Xeon(R) CPU?????????? E5620? @ 2.40GHz 16核 ? 测试程序说明： 先准备好n个字符串随机的MD5字符串做为key，然后分别对3个容器进行插入、遍历、查找、caozuo.html" target="_blank">删除操作。 例如，n=100的时候，插入是指插入100个随机MD5 key；遍历是指对容器遍历一次；查找是指分别对这个100个随机的MD5 key做查找操作（即查找100次）；删除是指挨个删除这个100个随机MD5 key。 ? 测试数据如下表：
插入，单位us 100 1K 10K 100K 1M 10M std::map 241 2833 35888 381214 4439088 62233380 std::ext/hash_map 97 1667 16466 146025 1788446 18512639 std::tr1::unordered_map 77 772 8052 53094 658312 7429297 ?
遍历，单位us 100 1K 10K 100K 1M 10M std::map 11 76 842 11603 155700 1771906 std::ext/hash_map 47 430 4218 39880 470344 4781575 std::tr1::unordered_map 1 1 2 1 2 1 查找，单位us 100 1K 10K 100K 1M 10M std::map 156 2111 30456 258709 4100260 59064394 std::ext/hash_map 77 774 8056 56974 660231 7705527 std::tr1::unordered_map 77 772 8051 54456 659537 7600263 删除，单位us 100 1K 10K 100K 1M 10M std::map 291 3641 49584 472414 6675897 92491113 std::ext/hash_map 89 869 9068 86524 964767 10372650 std::tr1::unordered_map 49 480 4879 33087 395098 4369617 结论： 1. std::tr1::unordered_map 与?std::ext/hash_map? ? ? ?任何情况下，如果要在这两个容器之间选择的话，我们毫不犹豫应该选择 unordered_map。因为他的性能在上述4中操作中均优于 hash_map，甚至可以说远远优于 hash_map。 ? 2.?std::tr1::unordered_map 与?std::map? ? ? ?map的性能总体来说是最差的。但是，当我们需要一个有序的关联容器的时候，我们必须选择std::map，因为?unordered_map?内部元素不是有序的，这一点从名字都可以看出来。除此之外都应该选择?unordered_map?。 ? 3. 上述测试中，unordered_map?的遍历性能几乎是常数级别的，与常识不太相符，需要再研究研究。 ? 附录：贴上源代码 说明：与测试程序稍有区别，这里的源码里没有MD5相关的代码以确保其他人能比较方便的直接拿去编译运行。 ? 如有错误还请跟帖指出，非常感谢。 ? ?

class="dp-css" style="margin-right: 1px; margin-bottom: 0px; margin-left: 1px; color: #5c5c5c; line-height: 1.3;">
1. #include?<iostream>
2. #include?<string>
3. #include?<sstream>
4. #include?<list>
5. #include?<map>
6. #include?<sys/time.h>
7. #include?<ext/hash_map>
8. #include?<tr1/unordered_map>
10. namespace zl
11. {?//{{{
12. ????struct equal_to
13. ????{
14. ????????bool operator()(const?char*?s1,?const?char*?s2)?const
15. ????????{
16. ????????????return strcmp(s1,?s2)?==?0;
17. ????????}
18. ????};
19. ?
20. ????struct hash_string
21. ????????:?public?std::unary_function<std::string,?std::size_t>
22. ????????{
23. ????????????std::size_t
24. ????????????????operator()(const?std::string&?__s)?const
25. #ifdef __linux__
26. ????????????????{?return std::tr1::Fnv_hash<>::hash(__s.data(),?__s.length());?}
27. #else
28. ????????????????{?return std::tr1::_Fnv_hash<>::hash(__s.data(),?__s.length());?}
29. #endif
30. ????????};
32. ????
33. ????struct hash_charptr
34. ????????:?public?std::unary_function<const?char*,?std::size_t>
35. ????????{
36. ????????????std::size_t
37. ????????????????operator()(const?char*?__s)?const
38. #ifdef __linux__
39. ????????????????{?return std::tr1::Fnv_hash<>::hash(__s,?strlen(__s));?}
40. #else
41. ????????????????{?return std::tr1::_Fnv_hash<>::hash(__s,?strlen(__s));?}
42. #endif
43. ????????};
44. }//}}}
46. typedef std::list<std::string>?string_list;
47. typedef std::map<std::string,?int>?string_map;
48. typedef __gnu_cxx::hash_map<std::string,?int,?zl::hash_string>?string_hash_map;
49. typedef std::tr1::unordered_map<std::string,?int>?string_unordered_map;
51. void fill_list(string_list&?slist,?size_t count);
52. uint64_t current_usec();
54. int?main(?int?argc,?char*?argv[]?)
55. {
56. ????if?(argc?!=?2?&&?argc?!=?3)
57. ????{
58. ????????fprintf(stderr,?"Usage:%s test_count rehash\n",?argv[0]);
59. ????????fprintf(stderr,?"For example:%s 10000 rehash\n",?argv[0]);
60. ????????return?-1;
61. ????}
63. ????size_t count?=?atoi(argv[1]);
64. ????bool rehash?=?false;
65. ????if?(argc?==?3)
66. ????{
67. ????????rehash?=?true;
68. ????}
70. ????string_map smap;
71. ????string_hash_map shash_map;
72. ????string_unordered_map sunordered_map;
74. ????if?(rehash)
75. ????{
76. ????????sunordered_map.rehash(count);
77. ????}
79. ????string_list slist;
80. ????fill_list(slist,?count);
82. ????uint64_t start?=?0;
83. ????uint64_t?end?=?0;
85. ????uint64_t map_insert_us?=?0;
86. ????uint64_t hash_map_insert_us?=?0;
87. ????uint64_t unordered_map_insert_us?=?0;
89. ????uint64_t map_traverse_us?=?0;
90. ????uint64_t hash_map_traverse_us?=?0;
91. ????uint64_t unordered_map_traverse_us?=?0;
93. ????uint64_t map_find_us?=?0;
94. ????uint64_t hash_map_find_us?=?0;
95. ????uint64_t unordered_map_find_us?=?0;
97. ????uint64_t map_delete_us?=?0;
98. ????uint64_t hash_map_delete_us?=?0;
99. ????uint64_t unordered_map_delete_us?=?0;
103. ????//?Insert test
104. ????{//{{{
105. ????????string_list::iterator it(slist.begin());
106. ????????string_list::iterator ite(slist.end());
108. ????????//map insert
109. ????????start?=?current_usec();
110. ????????for?(int?i?=?0;?it?!=?ite;?++it,?++i)
111. ????????{
112. ????????????smap[*it]?=?i;
113. ????????}
114. ????????end?=?current_usec();
115. ????????map_insert_us?=?end?-?start;
117. ????????//hash_map insert
118. ????????it?=?slist.begin();
119. ????????start?=?current_usec();
120. ????????for?(int?i?=?0;?it?!=?ite;?++it,?++i)
121. ????????{
122. ????????????shash_map[*it]?=?i;
123. ????????}
124. ????????end?=?current_usec();
125. ????????hash_map_insert_us?=?end?-?start;
127. ????????//unordered_map insert
128. ????????it?=?slist.begin();
129. ????????start?=?current_usec();
130. ????????for?(int?i?=?0;?it?!=?ite;?++it,?++i)
131. ????????{
132. ????????????shash_map[*it]?=?i;
133. ????????}
134. ????????end?=?current_usec();
135. ????????unordered_map_insert_us?=?end?-?start;
136. ????}//}}}
138. ????//?Traverse test
139. ????{//{{{
140. ????????//map traverse?
141. ????????{
142. ????????????string_map::iterator it(smap.begin());
143. ????????????string_map::iterator ite(smap.end());
144. ????????????start?=?current_usec();
145. ????????????for?(int?i?=?0;?it?!=?ite;?++it)
146. ????????????{
147. ????????????????i++;
148. ????????????}
149. ????????????end?=?current_usec();
150. ????????????map_traverse_us?=?end?-?start;
151. ????????}
153. ????????//hash_map traverse?
154. ????????{
155. ????????????string_hash_map::iterator it(shash_map.begin());
156. ????????????string_hash_map::iterator ite(shash_map.end());
157. ????????????start?=?current_usec();
158. ????????????for?(int?i?=?0;?it?!=?ite;?++it)
159. ????????????{
160. ????????????????i++;
161. ????????????}
162. ????????????end?=?current_usec();
163. ????????????hash_map_traverse_us?=?end?-?start;
164. ????????}
166. ????????//unordered_map traverse?
167. ????????{
168. ????????????string_unordered_map::iterator it(sunordered_map.begin());
169. ????????????string_unordered_map::iterator ite(sunordered_map.end());
170. ????????????start?=?current_usec();
171. ????????????for?(int?i?=?0;?it?!=?ite;?++it)
172. ????????????{
173. ????????????????i++;
174. ????????????}
175. ????????????end?=?current_usec();
176. ????????????unordered_map_traverse_us?=?end?-?start;
177. ????????}
178. ????}//}}}
180. ????//?Find test
181. ????{//{{{
182. ????????string_list::iterator it(slist.begin());
183. ????????string_list::iterator ite(slist.end());
185. ????????//map find
186. ????????start?=?current_usec();
187. ????????for?(int?i?=?0;?it?!=?ite;?++it,?++i)
188. ????????{
189. ????????????smap[*it]?=?i;
190. ????????}
191. ????????end?=?current_usec();
192. ????????map_find_us?=?end?-?start;
194. ????????//hash_map find
195. ????????it?=?slist.begin();
196. ????????start?=?current_usec();
197. ????????for?(int?i?=?0;?it?!=?ite;?++it,?++i)
198. ????????{
199. ????????????shash_map[*it]?=?i;
200. ????????}
201. ????????end?=?current_usec();
202. ????????hash_map_find_us?=?end?-?start;
204. ????????//unordered_map find
205. ????????it?=?slist.begin();
206. ????????start?=?current_usec();
207. ????????for?(int?i?=?0;?it?!=?ite;?++it,?++i)
208. ????????{
209. ????????????shash_map[*it]?=?i;
210. ????????}
211. ????????end?=?current_usec();
212. ????????unordered_map_find_us?=?end?-?start;
213. ????}//}}}
215. ????//?Delete test
216. ????{//{{{
217. ????????string_list::iterator it(slist.begin());
218. ????????string_list::iterator ite(slist.end());
220. ????????//map delete
221. ????????start?=?current_usec();
222. ????????for?(int?i?=?0;?it?!=?ite;?++it,?++i)
223. ????????{
224. ????????????smap.erase(*it);
225. ????????}
226. ????????end?=?current_usec();
227. ????????map_delete_us?=?end?-?start;
229. ????????//hash_map delete
230. ????????it?=?slist.begin();
231. ????????start?=?current_usec();
232. ????????for?(int?i?=?0;?it?!=?ite;?++it,?++i)
233. ????????{
234. ????????????shash_map.erase(*it);
235. ????????}
236. ????????end?=?current_usec();
237. ????????hash_map_delete_us?=?end?-?start;
239. ????????//unordered_map delete
240. ????????it?=?slist.begin();
241. ????????start?=?current_usec();
242. ????????for?(int?i?=?0;?it?!=?ite;?++it,?++i)
243. ????????{
244. ????????????shash_map.erase(*it);
245. ????????}
246. ????????end?=?current_usec();
247. ????????unordered_map_delete_us?=?end?-?start;
248. ????}//}}}
250. ????//stat output
251. ????std::cout?<<?" insert, count "?<<?count?<<?std::endl;
252. ????std::cout?<<?" std::map "?<<?map_insert_us?<<?" us\n";
253. ????std::cout?<<?" std::ext/hash_map "?<<?hash_map_insert_us?<<?" us\n";
254. ????std::cout?<<?"std::tr1::unordered_map "?<<?unordered_map_insert_us?<<?" us\n";
256. ????std::cout?<<?"\n";
257. ????std::cout?<<?" traverse, count "?<<?count?<<?std::endl;
258. ????std::cout?<<?" std::map "?<<?map_traverse_us?<<?" us\n";
259. ????std::cout?<<?" std::ext/hash_map "?<<?hash_map_traverse_us?<<?" us\n";
260. ????std::cout?<<?"std::tr1::unordered_map "?<<?unordered_map_traverse_us?<<?" us\n";
262. ????std::cout?<<?"\n";
263. ????std::cout?<<?" find, count "?<<?count?<<?std::endl;
264. ????std::cout?<<?" std::map "?<<?map_find_us?<<?" us\n";
265. ????std::cout?<<?" std::ext/hash_map "?<<?hash_map_find_us?<<?" us\n";
266. ????std::cout?<<?"std::tr1::unordered_map "?<<?unordered_map_find_us?<<?" us\n";
268. ????std::cout?<<?"\n";
269. ????std::cout?<<?" delete, count "?<<?count?<<?std::endl;
270. ????std::cout?<<?" std::map "?<<?map_delete_us?<<?" us\n";
271. ????std::cout?<<?" std::ext/hash_map "?<<?hash_map_delete_us?<<?" us\n";
272. ????std::cout?<<?"std::tr1::unordered_map "?<<?unordered_map_delete_us?<<?" us\n";
274. ?????
275. ????return 0;
276. }
278. void fill_list(string_list&?slist,?size_t count)
279. {
280. ????for?(size_t i?=?0;?i?<?count;?++i)
281. ????{
282. ????????std::ostringstream oss;
283. ????????oss?<<?i;
284. ????????//slist.push_back(MD5::getHexMD5(oss.str().c_str(),?oss.str().length()));
285. ????????slist.push_back(oss.str());
286. ????}
287. }
290. uint64_t current_usec()
291. {
292. ????struct timeval tv;
293. ????gettimeofday(?&tv,?NULL?);
294. ????return tv.tv_sec?*?1000?*?1000?+?tv.tv_usec;
295. }