下面粗体的句子，在 Nicolai Josuttis 的书 "The Standard Library" 中，我不清楚

Question

我正在阅读 "The Standard Library"，第二版，作者 Nicolai Josuttis。在其第 183 页中，我们有：

Examples of Using Unordered Maps and Multimaps

The example presented for multimaps on page 179 also works for an unordered multimap if you replace map by unordered_map in the include directive and multimap by unordered_multimap in the declaration of the container:
#include <unordered_map>
...
unordered_multimap<int,string> coll;
...
The only difference is that the order of the elements is undefined. However, on most platforms, the elements will still be sorted because as a default hash function, the modulo operator is used.

我把我不清楚的地方加粗了。当我读到这篇文章时，我的第一印象是作者说这两个程序（第 179 页中的程序，见下文）和上面的程序）应该在大多数平台上以相同的顺序打印城市名称。但这在 clang 和 GCC 中不会发生。请参阅 GCC 中 map and unordered_map 的实时示例。在clang中得到同样的结果

想了一会儿后，我将作者的解释解释为几乎所有平台的城市名称都以相同的顺序打印，当使用 unordered_map 处理时，输出似乎证实了这一点.但即便如此，我也很难接受这种解释，因为不同的实现可能会使用不同的哈希函数！

在下面，您将找到上面提到的第 179 页中的示例：

#include <map>
#include <string>
#include <iostream>
using namespace std;
int main()
{
    multimap<int,string> coll; // container for int/string values
    // insert some elements in arbitrary order
    // - a value with key 1 gets inserted twice
    coll = { {5,"tagged"},
             {2,"a"},
             {1,"this"},
             {4,"of"},
             {6,"strings"},
             {1,"is"},
             {3,"multimap"} };
    // print all element values
    // - element member second is the value
    for (auto elem : coll) {
        cout << elem.second << ’ ’;
    }
    cout << endl;
}

Answer 1

我认为混淆是因为我们在谈论 2 个哈希函数。

第一个是从密钥中获取数字的函数。默认为 std::hash，但也可以作为参数提供给 std::unorderded_map。

另一个函数是接受这个数字和 returns 桶索引的函数，即接受这个数字和 returns 0 - bucket_count() - 1 范围内的一个数字。这是实现定义的，但它几乎总是取模 % 因为它是最简单的并且如果原始散列函数是均匀分布的并且用户定义 std::hash 则不会产生负面影响应该是。

Answer 2

我认为这充其量是没有帮助的。

int 的常见默认哈希函数是使用 int 本身而无需更改。因此，如果 hash-table 的桶数多于最大整数，并且重复项以相同的顺序添加，大多数实现将（意外地）按排序顺序输出对。

然而，一般来说，对于具有某种顺序的对象，如果 A < B，则 H(A) < H(B) 并非如此。H(.) 是散列函数。通常情况下 MAX(H(X)) <= 存储桶计数也不是这样。

所以这本书实际上是在指出一个相当人为的特例的特征。为什么我认为这没有帮助？呈现人为特例的偶然属性可能会意外地让读者认为它们是某些更广泛特征的示例。

哈希映射中的条目不会以任何有用的顺序返回。它们不会按插入顺序返回。它们不会以相反的插入顺序返回。他们不会按排序顺序返回。他们不会以任何顺序回来。 [我是山姆]。

如果一个例子是值得的，那就是他们没有订购回来的例子。

Answer 3

这种说法是胡说八道。在某些平台上，在特定情况下，a（通常很小）unordered_multimap 中的元素顺序将与 multimap 中的元素顺序相同。然而，真正对程序员有用的是保证，比如"This container is sorted"。 unordered_(multi)map 和 unordered_(multi)set 都不能保证这一点。支持等效键（使用标准中的术语）的无序关联容器的一个实际有用的排序保证是具有等效键的条目总是相邻的，例如AACBBBD 或 BBBAADC 是有效订单，但 ABACBBD 不是。这就是这些容器像排序表亲一样支持 equal_range 操作的原因。即使这样（在 C++11 中），multimap 对这些条目也有更强的保证，因为它们不仅相邻，而且按插入顺序出现，而 unordered_multimap 可能并非如此。事实上，出于性能原因，它们可能以插入的相反顺序出现。但也不要依赖它……

下面粗体的句子，在 Nicolai Josuttis 的书 "The Standard Library" 中，我不清楚

The sentence in bold below, in the book "The Standard Library" by Nocolai Josuttis, is not clear to me

c++

standard-library

c++11