unordered_set如何确定c++中的插入顺序？

Question

我知道人们在不关心集合中元素的顺序时会使用 unordered_set。但是，当我运行 C++ Shell

上的示例程序时

#include <iostream>
#include <unordered_set>
#include <string>

int main()

{
std::unordered_set<std::string> inputSet;
inputSet.insert("Hello world");
inputSet.insert("Abcdef");
inputSet.insert("This is the test string...");

for(const auto &val : inputSet)
  std::cout << val.c_str() << std::endl;

return 0;}

它给了我

This is the test string...
Abcdef
Hello world

我尝试运行它 3 或 4 次，它仍然给我相同的输出，这意味着有一种方法可以 unordered_set 确定插入顺序。

谁能解释一下unordered_set如何确定插入顺序？

对不起，如果之前有人问过，我在网上搜索了一段时间，我找不到这个问题的具体答案。提前致谢。

Answer 1

如此处所述http://en.cppreference.com/w/cpp/container/unordered_set

Internally, the elements are not sorted in any particular order, but organized into buckets. Which bucket an element is placed into depends entirely on the hash of its value. This allows fast access to individual elements, since once a hash is computed, it refers to the exact bucket the element is placed into.

因此它使用默认或用户提供的哈希算法来分类到哈希桶中。

Answer 2

std::unordered_set<T> 中的顺序是无序的。但是，假设使用确定性散列并且执行相同顺序的插入操作，则程序的不同运行将具有相同顺序的元素。使用为不同运行产生不同值的散列以不同顺序插入元素 and/or 将产生不同顺序的元素。

Answer 3

没有特定的顺序...它使用默认的 std::hash 来散列字符串。并且无论哈希值是多少，它都会在容器中转换为适当的桶索引..

我们说的哈希值可以得到：

auto hello = std::hash<std::string>()("Hello world");
auto abcd = std::hash<std::string>()("Abcdef");
auto test = std::hash<std::string>()("This is the test string...");

对于特定的 STL 实现，这解析为：

Hello maps to: 14420674105493498572
abcd maps to: 10830572898531769673
test maps to: 13068738153895491918

在 C++Shell

上观看直播

通常通过应用 % 运算符将值转换为适当的桶索引。同样，std::unordered_set 的迭代器并没有强制顺序地遍历所有的桶（碰撞呢？）。因此，您不应该依赖从程序运行之间的迭代器观察到的任何顺序。

从 C++14 开始，std::hash<> 被明确允许在不同的程序运行之间产生不同的结果。至 quote:

Hash functions are only required to produce the same result for the same input within a single execution of a program; this allows salted hashes that prevent collision DoS attacks.

unordered_set如何确定c++中的插入顺序？

How does unordered_set determine the inserting order in c++?

c++

unordered-set