我可以依賴無序映射的順序嗎？

我有一個std::unordered_multimap，我想獲得特定鍵的最後插入的元素。我觀察到了這種現象：我可以依賴無序映射的順序嗎？

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

此代碼輸出：

last 
3

這是，至少，在海灣合作委員會的行爲我想。我可以依靠這個嗎？這個標準是否會說明有關std::unordered_multimap商店的訂單？如果不是，那麼最好的選擇是什麼？

來源

2016-01-03 Guillaume Racicot

您將獲得'first 1'[libC++]（http://coliru.stacked-crooked.com/a/f8f56abb25674bbe）。 –

差不多。

[C++14: 24.2.5/6]:[..]在支持等價密鑰的容器，具有等價密鑰元件在所述容器的迭代順序彼此相鄰。因此，儘管無序容器中的元素的絕對順序未被指定，但其元素被分組爲等價鍵組，使得每個組的所有元素都具有相同的鍵。 無序容器上的變異操作應保留每個等價鍵組中元素的相對順序，除非另有說明。

[C++14: 24.2.5/9]:[..]對於unordered_multiset和unordered_multimap，重散列保持等同的元件的相對順序。

這是非常尷尬的字眼，但是，從我所知道的，一般概念是等同鍵下方元素的順序是不確定的，但它至少幾乎保持不變之後。

所以：

你不能依靠插入順序，但你也許可以依靠穩定的秩序，如果你細心的話。

這與有序關聯容器對比：

[C++14: 23.2.4/4]:對於多集和multimap，插入，佈設和擦除保護等同元素的相對順序。

來源

2016-01-03 23:08:38

但是沒有指定插入新元素的位置。如果在等效鍵組中有'a，b，c'，並插入'd'，則'a'，'b'和'c'的相對順序不會改變，但是您可以將'd '四個地方中的任何一個。 –

@ T.C。其中可能會或可能不會確定 –

std::unordered_multimap既不是有序的（明顯），也不穩定。因此，您將相同元素放入std::unordered_multimap的訂單無法保證與標準保持一致。

來源

2016-01-03 23:11:10

措辭表明穩定性很強。 –

@LightnessRacesinOrbit等價元素只能保證處於迭代次序的連續子範圍內。 –

@P aulEvans我知道。 –

我可以依賴無序映射的順序嗎？

回答

相關問題