我什么时候应该使用unordered_map而不是std :: map

Question

我想知道在哪种情况下我应该使用unordered_map而不是std :: map.

每次我不注意地图中元素的顺序时,我必须使用unorderd_map吗？

Answer 1

map

1. 通常使用红黑树实现.
2. 元素已排序.
3. 内存使用量相对较小(哈希表不需要额外的内存).
4. 相对快速的查找:O(log N).

unordered_map

1. 通常使用哈希表实现.
2. 元素未排序.
3. 需要额外的内存来保留哈希表.
4. 快速查找O(1),但是恒定时间取决于可能相对较慢的哈希函数.还要记住,你可以遇到生日问题.

Answer 2

map允许以排序的方式迭代元素，但unordered_map事实并非如此。
因此，std::map当您需要按排序顺序迭代映射中的项目时，请使用 。