Puis-je me fier à l'ordre d'une carte non ordonnée?

Question

J'ai un std::unordered_multimap et je veux obtenir le dernier élément inséré d'une clé spécifique. J'ai observé ce comportement:

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

Ce sorties de code:

last 
3 

C'est, au moins, le CCG, le comportement que je veux. Puis-je compter sur cela? Est-ce que la norme dit quelque chose à propos de la commande les choses de magasin std::unordered_multimap? Sinon, quelle serait la meilleure alternative?

Answer 1

Presque.

[C++14: 24.2.5/6]:[..] en récipients qui prennent en charge les clés équivalentes, les éléments équivalents à clés sont adjacents les uns aux autres dans l'ordre de l'itération du récipient. Ainsi, bien que l'ordre absolu des éléments dans un conteneur non ordonné n'est pas spécifié, ses éléments sont groupés en groupes de clés équivalentes de sorte que tous les éléments de chaque groupe ont des clés équivalentes. Les opérations de mutations sur des conteneurs non ordonnés doivent préserver l'ordre relatif des éléments dans chaque groupe de clés équivalentes, sauf indication contraire.

[C++14: 24.2.5/9]:[..]Pour unordered_multiset et unordered_multimap, ressasser préserve l'ordre relatif des éléments équivalents.

Il est libellé assez maladroit, mais, de ce que je peux dire, la notion générale est que l'ordre des éléments clés équivalents en dessous est non précisé, mais au moins à peu près reste le même après.

Alors:

Vous ne pouvez pas compter sur ordre d'insertion, mais vous pouvez probablement compter sur un ordre stable si vous êtes prudent.

Ceci est en contraste avec les conteneurs associatifs ordonnés:

[C++14: 23.2.4/4]:Pour multiset et multimap, insérer, emplace et effacer préserver l'ordre relatif des éléments équivalents.

Answer 2

std::unordered_multimap est ni ordonné (évidemment), ni stable. Donc l'ordre dans lequel vous mettez des éléments équivalents dans le std::unordered_multimap n'est en aucun cas garanti d'être conforme à la norme.