Czy mogę polegać na kolejności nieuporządkowanej mapy?

Question

Mam std::unordered_multimap i chcę uzyskać ostatni wstawiony element określonego klucza. Zauważyłem ten problem:

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

Ten kod wyjścia:

last 
3 

to przynajmniej na GCC, zachowanie chcę. Czy mogę na tym polegać? Czy standard mówi jednoznacznie o porządku przechowywania rzeczy? Jeśli nie, jaka byłaby najlepsza alternatywa?

Answer 1

Prawie.

[C++14: 24.2.5/6]:[..] W pojemnikach, które obsługują równoważne klawiszy, elementy równoważne z klawiszy sąsiadują ze sobą w celu iteracji pojemnika. Tak więc, mimo że , bezwzględna kolejność elementów w nieuporządkowanym pojemniku nie jest określona, jej elementy są pogrupowane w grupy równoważnego klucza, tak że wszystkie elementy każdej grupy mają równoważne klucze. Mutowanie operacji na nieuporządkowanych kontenerach zachowuje względną kolejność elementów w obrębie każdej równoważnej grupy kluczy, chyba że określono inaczej.

[C++14: 24.2.5/9]:[..]Na unordered_multiset i unordered_multimap, hashuje zachowuje względem uporządkowania równoważne elementy.

To dość niezręczne sformułowanie, ale z tego co mogę powiedzieć, ogólna idea jest taka, że ​​kolejność elementów równoważnych pod spodem klawiszy jest nieokreślona, ​​choć przynajmniej dość dużo pozostaje taka sama później.

Więc:

Nie można liczyć na zamówienia reklamowego, ale prawdopodobnie można polegać na stabilnym porządku, jeśli jesteś ostrożny.

to w kontraście z zamówionych kontenerów asocjacyjnych:

[C++14: 23.2.4/4]:Dla MultiSet i multimapy, INSERT, emplace i wymazać zachować względną kolejność równoważnych elementów.

Answer 2

std::unordered_multimap jest nie zamówił (oczywiście) ani stabilny. Dlatego kolejność umieszczania równoważnych elementów w std::unordered_multimap nie jest w żaden sposób gwarantowana jako zgodna ze standardem.