Posso fare affidamento sull'ordine di una mappa non ordinata?

Question

Ho un std::unordered_multimap e voglio ottenere l'ultimo elemento inserito di una chiave specifica. Ho osservato questo comportamento:

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

Questo uscite di codice:

last 
3 

Questo è, almeno, il GCC, il comportamento che voglio. Posso fare affidamento su questo? Lo standard dice simething sull'ordine che le cose del negozio std::unordered_multimap memorizzano? In caso contrario, quale sarebbe l'alternativa migliore?

Answer 1

Quasi.

[C++14: 24.2.5/6]:[..] In contenitori che supportano chiavi equivalenti, elementi con chiavi equivalenti sono adiacenti l'uno all'altro nell'ordine iterazione del contenitore. Pertanto, sebbene l'ordine assoluto di elementi in un contenitore non ordinato non sia specificato, i suoi elementi sono raggruppati in gruppi di chiavi equivalenti in modo tale che tutti gli elementi di ciascun gruppo abbiano chiavi equivalenti. Le operazioni di modifica su contenitori non ordinati devono conservare l'ordine relativo degli elementi all'interno di ciascun gruppo di chiavi equivalenti, salvo diversamente specificato.

[C++14: 24.2.5/9]:[..]Per unordered_multiset e unordered_multimap, rimaneggiamento preserva l'ordine relativo degli elementi equivalenti.

E 'formulazione abbastanza imbarazzante, ma, da quello che posso dire, l'idea generale è che l'ordine degli elementi sotto i tasti equivalenti non è specificato, anche se rimane almeno praticamente la stessa in seguito.

Quindi:

Non si può contare su ordine di inserimento, ma probabilmente si può fare affidamento su un ordine stabile se si sta attenti.

Ciò è in contrasto con i contenitori associativi ordinate:

[C++14: 23.2.4/4]:Per multinsieme e multimap, inserto, colloco, e cancellare preservare l'ordine relativo degli elementi equivalenti.

Answer 2

std::unordered_multimap è né ordinato (ovviamente) né stabile. Pertanto, l'ordine di inserimento di elementi equivalenti nello std::unordered_multimap non è in alcun modo garantito dalla coerenza dello standard.