A recent talk about unordered_map in C++ made me realize that I should use unordered_map for most cases where I used map before, because of the efficiency of lookup ( amortized O(1) vs. O(log n) ). Most times I use a map, I use either int or std::string as the key type; hence, I've got no problems with the definition of the hash function. The more I thought about it, the more I came to realize that I can't find any reason of using a std::map over a std::unordered_map in the case of keys with simple types -- I took a look at the interfaces, and didn't find any significant differences that would impact my code.
因此，问题是:是否有任何真正的理由使用std::map而不是std::unordered_map在简单类型的情况下，如int和std::string?
我是从严格的编程角度提出这个问题的——我知道它并不是完全标准的，而且它可能会给移植带来问题。
另外，我认为正确答案之一可能是“对于较小的数据集更有效”，因为开销更小(是真的吗?)——因此，我希望将这个问题限制在键数量非普通的情况下(>1 024)。
编辑:哦，我忘记了显而易见的(感谢GMan!)——是的，地图当然是有序的——我知道，我正在寻找其他原因。
I was intrigued by the answer from @Jerry Coffin, which suggested that the ordered map would exhibit performance increases on long strings, after some experimentation (which can be downloaded from pastebin), I've found that this seems to hold true only for collections of random strings, when the map is initialised with a sorted dictionary (which contain words with considerable amounts of prefix-overlap), this rule breaks down, presumably because of the increased tree depth necessary to retrieve value. The results are shown below, the 1st number column is insert time, 2nd is fetch time.
g++ -g -O3 --std=c++0x -c -o stdtests.o stdtests.cpp
g++ -o stdtests stdtests.o
gmurphy@interloper:HashTests$ ./stdtests
# 1st number column is insert time, 2nd is fetch time
** Integer Keys **
unordered: 137 15
ordered: 168 81
** Random String Keys **
unordered: 55 50
ordered: 33 31
** Real Words Keys **
unordered: 278 76
ordered: 516 298
I was intrigued by the answer from @Jerry Coffin, which suggested that the ordered map would exhibit performance increases on long strings, after some experimentation (which can be downloaded from pastebin), I've found that this seems to hold true only for collections of random strings, when the map is initialised with a sorted dictionary (which contain words with considerable amounts of prefix-overlap), this rule breaks down, presumably because of the increased tree depth necessary to retrieve value. The results are shown below, the 1st number column is insert time, 2nd is fetch time.
g++ -g -O3 --std=c++0x -c -o stdtests.o stdtests.cpp
g++ -o stdtests stdtests.o
gmurphy@interloper:HashTests$ ./stdtests
# 1st number column is insert time, 2nd is fetch time
** Integer Keys **
unordered: 137 15
ordered: 168 81
** Random String Keys **
unordered: 55 50
ordered: 33 31
** Real Words Keys **
unordered: 278 76
ordered: 516 298
我大致同意GMan的观点:根据使用类型的不同，std::map可以(而且通常)比std::tr1::unordered_map快(使用VS 2008 SP1中包含的实现)。
有几个复杂的因素需要记住。例如，在std::map中，您正在比较键，这意味着您只查看足够多的键的开头，以区分树的左右子分支。根据我的经验，几乎只有当你使用int这样可以在单个指令中进行比较的时候，你才会查看整个键。对于更典型的键类型，如std::string，通常只比较几个字符。
相比之下，一个像样的哈希函数总是查看整个键。IOW，即使查找表的复杂度是恒定的，哈希本身也具有大致的线性复杂度(尽管是键的长度，而不是项的数量)。使用长字符串作为键，std::map可能会在unordered_map开始搜索之前完成搜索。
其次，虽然有几种方法可以调整哈希表的大小，但大多数方法都非常慢——除非查找比插入和删除频繁得多，否则std::map通常会比std::unordered_map快。
当然，就像我在对你上一个问题的评论中提到的，你也可以使用树表。这既有优点也有缺点。一方面，它将最坏的情况限制在一棵树上。它还允许快速插入和删除，因为(至少当我这样做时)我使用了固定大小的表。消除所有的表大小调整可以让你的哈希表更简单，通常更快。
另一点:哈希和基于树的映射的需求是不同的。哈希显然需要一个哈希函数和一个相等比较，其中有序映射需要一个小于比较。当然，我提到的混合型需要两者兼备。当然，对于使用字符串作为键的常见情况，这并不是真正的问题，但某些类型的键比哈希更适合排序(反之亦然)。
我只是想指出……有很多种unordered_map。
在哈希图上查找维基百科文章。根据所使用的实现的不同，查找、插入和删除方面的特征可能有很大差异。
这是我最担心的添加unordered_map到STL:他们将不得不选择一个特定的实现，因为我怀疑他们会走政策的道路，所以我们将被困在一个实现的平均使用，而没有其他情况…
例如，一些哈希映射具有线性重新哈希，其中不是一次重新哈希整个哈希映射，而是在每次插入时重新哈希一部分，这有助于分摊成本。
另一个例子:一些哈希映射使用一个简单的节点列表作为bucket，其他使用map，其他不使用节点，但找到最近的槽，最后一些将使用节点列表，但重新排序，以便最后访问的元素位于前面(像缓存一样)。
因此，目前我倾向于std::map或loki::AssocVector(用于冻结数据集)。
不要误解我的意思，我希望使用std::unordered_map，将来也可能会使用，但是当您想到实现它的所有方法和由此产生的各种性能时，很难“信任”这样一个容器的可移植性。
