2

一本书提到std::unordered_multimap：

元素的顺序是未定义的。唯一的保证是由于使用了多重集而可能出现的重复项按照它们的插入顺序分组在一起。

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

#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
4

1 回答 1

2

以下是标准对排序[unord.req] / §6的说明：

...在支持等效键的容器中，具有等效键的元素在容器的迭代顺序中彼此相邻。因此，尽管未指定无序容器中元素的绝对顺序，但它的元素被分组到等效键组中，这样每个组的所有元素都具有等效键。除非另有说明，无序容器上的变异操作应保持每个等效键组内元素的相对顺序。

所以，回答这个问题：

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

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

该标准的要求使得使用开放寻址的实现变得不切实际。因此，兼容的实现通常使用单独的哈希冲突链接，请参阅C++ STL unordered_map 如何解决冲突？

因为等价键 - 必然会发生冲突 - （实际上，没有明确要求）存储在单独的链表中，所以插入它们的最有效方法是按插入顺序（push_back）或反向（push_front）。如果单独的链是单独链接的，则只有后者是有效的。

于 2016-07-17T00:56:55.897 回答