Should items with duplicate keys in unordered_multimap be kept in the order of their insertion?

Question

One book mentioned that for std::unordered_multimap:

The order of the elements is undefined. The only guarantee is that duplicates, which are possible because a multiset is used, are grouped together in the order of their insertion.

But from the output of the example below, we can see that the print order is reverse from their insertion.

#include <string>
#include <unordered_map>

int main()
{
    std::unordered_multimap<int, std::string> um;
    um.insert( {1,"hello1.1"} );
    um.insert( {1,"hello1.2"} );
    um.insert( {1,"hello1.3"} );

    for (auto &a: um){
        cout << a.first << '\t' << a.second << endl;
    }
}

Which when compiled and run produces this output (g++ 5.4.0):

1   hello1.3  
1   hello1.2  
1   hello1.1

updated: unordered_multiset has the same issue:

auto cmp = [](const pair<int,string> &p1, const pair<int,string> &p2)
            {return p1.first == p2.first;};
auto hs = [](const pair<int,string> &p1){return std::hash<int>()(p1.first);};

unordered_multiset<pair<int, string>, decltype(hs), decltype(cmp)> us(0, hs, cmp);
us.insert({1,"hello1.1"});
us.insert({1,"hello1.2"});
us.insert({1,"hello1.3"});

for(auto &a:us){
    cout<<a.first<<"\t"<<a.second<<endl;
}

output:

1   hello1.3
1   hello1.2
1   hello1.1

`The order of the elements is undefined.` I guess you need to realise what the Standard means when it says "undefined": anything can happen, but it doesn't matter what happens, and no one should rely on what _might_ happen, on a Tuesday, with the wind blowing East. Implementations can define an order if they want - probably as a side-effect of not being deliberately byzantine - but the Standard doesn't. That's all. Having said that, if you were to insert more elements, you'd probably find the 'predictable' order start to break down. But again, it doesn't matter at all. It's an `unordered_map`. — underscore_d, Jul 16 '16 at 21:55
@underscore_d: No, it's an `unordered_multimap`, of which the C++14 November 2014 draft (at least) requires that "elements with equivalent keys are adjacent to each other in the iteration order of the container" and that "rehashing preserves the relative ordering of equivalent elements" (23.2.5). I can't find anything about relative ordering being defined according to insertion order, but it is worth knowing. — Ry-, Jul 16 '16 at 22:13
@RyanO'Hara Thanks for the info. I didn't fully process that because the 1st line has the `multi` missing. Now we need to know which book says this, not that it's going to be more reliable than the Standard! — underscore_d, Jul 16 '16 at 22:33
@underscore_d The statement is from C++ standard library A tutorial and reference Chapter 6.2 containers, at the begining of page 183: Now,if we print all elements,the order might be different because the order is undefined. The only guarantee is that duplicates, which are possible because a multiset is used, are grouped together in the order of their insertion. — camino, Jul 17 '16 at 01:06
@camino Thanks for the citation and extra quote. I don't think its statement makes any sense. "The order is undefined" directly conflicts with "grouped together in the order of their insertion". They're **just** grouped together, in an undefined (albeit usually unchanging) order. — underscore_d, Jul 17 '16 at 07:29

eerorika · Accepted Answer · 2020-11-26T13:05:41.430

Here is what the standard says of the ordering [unord.req] / §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.

So, to answer the question:

Should items with duplicate keys in unordered_multimap be kept in the order of their insertion?

No, there is no such requirement, or guarantee. If the book makes such claim about the standard, then it is not correct. If the book describes a particular implementation of std::unordered_multimap, then the description could be true for that implementation.

The requirements of the standard make an implementation using open addressing impractical. Therefore, compliant implementations typically use separate chaining of hash collisions, see How does C++ STL unordered_map resolve collisions?

Because equivalent keys - which necessarily collide - are (in practice, not explicitly required to be) stored in a separate linked list, the most efficient way to insert them, is in order of insertion (push_back) or in reverse (push_front). Only the latter is efficient if the separate chain is singly linked.

The implementor is not obliged to persist that behavior across future versions of their library. — kfsone, Jul 17 '16 at 01:19

Should items with duplicate keys in unordered_multimap be kept in the order of their insertion?

1 Answers1