我可以依赖无序地图的顺序吗？

Question

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

#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 存储东西的顺序？如果没有，最好的选择是什么？

Answer 1

差不多。

[C++14: 24.2.5/6]: [..] In containers that support equivalent keys, elements with equivalent keys are adjacent to each other in the iteration order of the container. Thus, although the absolute order of elements in an unordered container is not specified, its elements are grouped into equivalent-key groups such that all elements of each group have equivalent keys. Mutating operations on unordered containers shall preserve the relative order of elements within each equivalent-key group unless otherwise specified.

[C++14: 24.2.5/9]: [..] For unordered_multiset and unordered_multimap, rehashing preserves the relative ordering of equivalent elements.

这是一种非常尴尬的措辞，但据我所知，一般的概念是等效键下元素的顺序是未指定的，尽管它至少在之后几乎保持不变。

所以：

您不能依赖广告订单，但如果您小心的话，您可以依赖稳定的订单。

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

[C++14: 23.2.4/4]: For multiset and multimap, insert, emplace, and erase preserve the relative ordering of equivalent elements.

Answer 2

std::unordered_multimap 既不是有序的（显然）也不是 稳定的 。因此，您将等效元素放入 std::unordered_multimap 的顺序绝不能保证符合标准。

我可以依赖无序地图的顺序吗？

Can I rely on the order of an unordered map?

c++

gcc

multimap

language-lawyer

c++11