我能信赖无序映射的顺序吗？

Question

我能信赖无序映射的顺序吗？

9

我有一个std::unordered_multimap，我想获取特定key的最后插入的元素。我观察到以下行为：

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

int main() {
    unordered_multimap<string, string> mmap;

    mmap.emplace("a", "first");
    mmap.emplace("a", "second");
    mmap.emplace("a", "last");
    mmap.emplace("b", "1");
    mmap.emplace("b", "2");
    mmap.emplace("b", "3");

    auto last_a = mmap.equal_range("a").first;
    auto last_b = mmap.equal_range("b").first;

    cout << last_a->second << endl;
    cout << last_b->second << endl;

    return 0;
}

这段代码输出：

last
3

在GCC上，至少我想要的是这种行为。我能依赖它吗？标准是否对std::unordered_multimap存储元素的顺序有规定？如果没有，最好的替代方案是什么？

- Guillaume Racicot

你可以使用libc++获取first 1。 - T.C.

2个回答

1

std::unordered_multimap既不是有序的（显然），也不是稳定的。因此，您将等效元素放入std::unordered_multimap中的顺序在标准中无法保证一致。

- Paul Evans

措辞表明了很强的稳定性。 - Lightness Races in Orbit

@LightnessRacesinOrbit 等价元素仅保证在迭代顺序的连续子范围内。 - Paul Evans

@PaulEvans 我知道。 - Lightness Races in Orbit

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Lightness Races in Orbit · Accepted Answer

几乎。

[C++14: 24.2.5/6]: [..] 在支持等效键的容器中，具有等效键的元素在容器的迭代顺序中相邻。因此，尽管未指定无序容器中元素的绝对顺序，但其元素被分组为等效键组，使得每个组的所有元素具有等效键。除非另有规定，否则对无序容器的变异操作应保留每个等效键组内元素的相对顺序。

[C++14: 24.2.5/9]: [..] 对于unordered_multiset和unordered_multimap，重新哈希保留等效元素的相对顺序。

这是一种笨拙的措辞，但从我所了解的情况来看，总体概念是等效键下方的元素顺序未指定，但至少在之后它基本上保持不变。

所以：

您不能依赖插入顺序，但如果小心的话，您可能可以依赖稳定的顺序。

这与有序关联式容器形成对比：

[C++14: 23.2.4/4]: 对于multiset和multimap，insert、emplace和erase保留等效元素的相对顺序。