C++中的unordered_map和map

时间：2022-05-10 23:16:07

背景

很久以来，STL中都只提供<map>作为存放对应关系的容器，内部通常用红黑树实现，据说原因是二叉平衡树（如红黑树）的各种操作，插入、删除、查找等，都是稳定的时间复杂度，即O(log n)；但是对于hash表来说，由于无法避免re-hash所带来的性能问题，即使大多数情况下hash表的性能非常好，但是re-hash所带来的不稳定性在当时是不能容忍的。

在C++中最让我蛋疼的事情之一就是unordered_map千呼万唤才出来，在C++早期版本标准库里面只有map这个字典。 但是map的内部实现是采用的红黑树，众所周知，对于字典这类结构也可以用hash表来实现，也就是C++的标准库应该也要有hash_map这种数据结构。

  • 红黑树实现的map占用内存较小，但是查找效率不高，O(logn)的查找效率。
  • hash表实现的map占用内存较大，但是查找效率高，往往可以逼近O(1)的惊人查找效率。

在C++中关于map的hash表方法的实现是unordered_map这个数据结构，首次出现应该是在C++98那个年代的tr1这个命名空间里面出现。 使用方法写起来比较啰嗦。

#include <tr1/unordered_map> using std::tr1::unordered_map;

我认为像unordered_map这个数据结构差不多就是C++程序员的柴米油盐，生活必需品。 但是由于C++标准委员会的懒散，硬生生是拖到c++0x/c++11标准才把unordered_map纳入std标准。 也就是只有在支持-std=c++0x甚至-std=c++11的编译器里(对于g++来说大概是g++4.4这个版本以上的才开始支持)，才可以用如下代码使用unordered_map：

#include <unordered_map> using std::unordered_map;

假设如果全世界所有的g++都已经是4.4版本以上了，那使用unordered_map就不再有任何问题，但是现实是残酷的，总会在世界某些角落的服务器， 仍然在使用g++-4.1.x，而且对于这些服务器来说升级g++还麻烦得很。所有我们的程序就要考虑对于低级版本的兼容 。

解决方法

#if(__cplusplus == 201103L) #include <unordered_map> #include <unordered_set> #else #include <tr1/unordered_map> #include <tr1/unordered_set> namespace std { using std::tr1::unordered_map; using std::tr1::unordered_set; } #endif

这个解决方法主要是依靠__cplusplus这个宏在不同C++版本中的值不同。 对于(能够使用且)使用了-std=c++0x或者-std=c++11编译选项的编译过程，__cplusplus的值是201103L，否则则是其他值。

结论

上述方法最低大概只能支持到C++98这个标准了，因为到了C++98才开始有tr1/unordered_map，所以你的编译器如果连C++98都不支持的话，那就乖乖用远古时代流传至今的map吧。

参考资料

  • http://www.cplusplus.com/forum/general/90675/
  • http://*.com/questions/2324658/how-to-determine-the-version-of-the-c-standard-used-by-the-compiler
转自：http://ju.outofmemory.cn/entry/88618
标签：

相关文章