Can I rely on the order of an unordered map?

Question

I have an std::unordered_multimap and I want to get the last inserted element of a specific key. I observed this behaviour:

#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;
}

This code outputs:

last
3

This is, at least, on GCC, the behaviour I want. Can I rely on this? Does the standard say simething about the order the std::unordered_multimap store things? If not, what would be the best alternative?

Answer 1

Almost.

[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.

It's pretty awkward wording but, from what I can tell, the general notion is that the order of elements underneath equivalent keys is unspecified, though it at least pretty much stays the same afterwards.

So:

You can't rely on insertion order, but you can probably rely on a stable order if you're careful.

This is in contrast with the ordered associative containers:

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