C++中map/unodered_map选择和比较

在写LycorisNet的过程中，底层的数据结构大量使用了map，试图加快算法的运行速度。Lycoris初代的版本是采用Go语言开发的，Golang中“稀少”的数据结构让我最终不得不选择基于哈希的map。后期为了进一步加速，决定全部使用C++ 11进行重构。

然而框架搭建好了以后，发现C++ 11标准库中map默认为红黑树的实现，此外其还内置了基于哈希实现的unodered_map。出于极客对极致性能的追求，有必要对两种map进行比较和择优。

Map是STL的一个关联容器，它提供一对一（其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可能称为该关键字的值）的数据处理能力，由于这个特性，它完成有可能在我们处理一对一数据的时候，在编程上提供快速通道。这里说下map内部数据的组织，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()了。 

人们往往会更倾向于一个理论——在不需要排序的情况下尽量选择给予哈希的实现，但在真正实现中往往不是这样。至少在Lycoris中，unodered_map并不比map提高了性能，一方面是由于散列函数（哈希函数）选择不当（我尝试过大多数包括异或移位），另一方面可能由于map并不是算法的瓶颈。