Les éléments d'une carte std :: map sont-ils garantis?

Question

Est-ce juste un effet secondaire de l'implémentation (arbre rouge-noir) ou la commande est-elle garantie par la norme C++?

Answer 1

L'itération ordonnée n'est pas un détail d'implémentation; il est garanti par la norme C++. Il est une propriété fondamentale de tous les conteneurs associatifs (C++ 03 §23.1.2/9):

La propriété fondamentale des itérateurs de conteneurs associatifs est qu'ils itérer à travers les conteneurs dans l'ordre non décroissant de clés où non-descendant est défini par la comparaison qui a été utilisée pour les construire. Pour toutes deux itérateurs dereferenceable i et j de telle sorte que la distance i-j est positif,

value_comp(*j, *i) == false 

value_comp est le comparateur avec lequel la carte a été construit (par défaut, il est std::less<T>).

Answer 2

C'est garanti par la norme C++.

Answer 3

Garanti. Si vous voulez quelque chose qui n'est pas contraint par cet essai boost: unordered_map <>

Answer 4

§23.1.2/2:

Chaque conteneur associatif est paramétré sur Key et une commande relation Compare qui induit une relation d'ordre strict faible (25.3) sur les éléments de Key. ... L'objet du type Compare est appelé l'objet de comparaison d'un conteneur . Cet objet de comparaison peut être un pointeur vers une fonction ou un objet d'un type avec un opérateur d'appel de fonction approprié.

L'objet Compare par défaut est la fonction inférieure à std::less<Key>.

La commande est une propriété de la fonction. C'est une exigence, pas un effet secondaire.

Le tri est un effet secondaire. 23.1.2/10 et 23.1.2/9 (cité par James) garantissent que map/set et multimap/multiset ont des clés croissantes/non décroissantes, respectivement, sur la séquence de begin à end.