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

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

Solution

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.