c++ - unordered_multimap 中具有重复键的项目是否应按插入顺序保存？

Question

一本书提到对于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.

但从下面示例的输出中，我们可以看到打印顺序与插入顺序相反。

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

编译和运行时产生这个输出(g++ 5.4.0):

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

更新: unordered_multiset 有同样的问题:

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

输出:

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

Answer 1

这是标准对顺序的描述 [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.

所以，回答这个问题:

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

不，没有这样的要求或保证。如果本书对标准做出这样的声明，那么它是不正确的。如果本书描述了 std::unordered_multimap 的特定实现，那么该描述可能适用于该实现。

---

标准的要求使得使用开放寻址的实现变得不切实际。因此，兼容的实现通常使用散列冲突的单独链接，请参阅 How does C++ STL unordered_map resolve collisions?

因为等效键——必然会发生冲突——被(在实践中，没有明确要求)存储在一个单独的链表中，插入它们的最有效方法是按插入顺序 (push_back) 或反向插入 (push_front) ).如果单独的链是单链接的，则只有后者是有效的。