Est de l'ordre de l'itération sur les std::map connu (et garanti par la norme)?

Question

Ce que je veux dire est - nous savons que l' std::map's éléments sont triés en fonction de clés. Donc, disons que les clés sont des nombres entiers. Si je itération à partir d' std::map::begin() de std::map::end() à l'aide d'un for, le standard garantie que je vais effectuer une itération, par conséquent, à travers les éléments avec des touches, triés dans l'ordre croissant?

---

Exemple:

std::map<int, int> map_;
map_[1] = 2;
map_[2] = 3;
map_[3] = 4;
for( std::map<int, int>::iterator iter = map_.begin();
     iter != map_.end();
     ++iter )
{
    std::cout << iter->second;
}

Est-ce garanti pour imprimer 234 ou c'est la mise en œuvre définies?

---

La vie réelle raison: j'ai un std::map avec int clés. Dans de très rares situations, j'aimerais aller parcourir tous les éléments, avec la clé, plus de de béton int de la valeur. Yep, ça sonne comme std::vector serait le meilleur choix, mais à mon avis "très rares sont les situations".

---

EDIT: je sais, que les éléments d' std::map sont triés.. pas besoin de le signaler (pour la plupart des réponses ici). J'ai même écrit dans ma question.
Je posais des questions sur les itérateurs et l'ordre quand je suis itération dans un récipient. Merci @Kerrek SB pour la réponse.

Answer 1

Oui, c'est garanti. En outre, *begin() vous donne le plus petit et le *rbegin() le plus grand élément, tel que déterminé par l'opérateur de comparaison, et deux valeurs essentielles a et b pour qui l'expression !compare(a,b) && !compare(b,a) est vrai, sont considérées comme égales. Par défaut la fonction de comparaison est - std::less<K>.

La commande n'est pas une chance de bonus, mais plutôt, c'est un regards croisés aspect de la structure de données, comme la commande est utilisée pour déterminer quand les deux touches sont les mêmes (par la règle ci-dessus) et efficace de recherche (essentiellement binaire de recherche, qui a logarithmique de la complexité dans le nombre d'éléments).

Answer 2

Cela est garanti par conteneur Associatif exigences de la norme C++. E. g. voir l'article 23.2.4/10 en C++11:

La propriété fondamentale des itérateurs de conteneurs associatifs, c'est qu'ils
itérer sur les récipients dans le non-ordre décroissant des touches où
non-descendant est définie par la comparaison qui a été utilisé pour les construire.
Pour toutes les deux dereferenceable itérateurs i et j tels que la distance de i à j est
positif,
 value_comp(*j, *i) == false

et 23.2.4/11

Pour les conteneurs associatifs avec les clés uniques, la condition plus forte détient,
 value_comp(*i, *j) != faux.

Answer 3

Je pense qu'il y a une confusion dans les structures de données.

Dans la plupart des langues, un map est tout simplement un AssociativeContainer: il mappe une clé à une valeur. Dans les "nouvelles" langues, ce qui est généralement réalisé en utilisant une table de hachage de la carte, donc pas de commande est garanti.

En C++, cependant, ce n'est pas:

• std::map est une triés conteneur associatif
• std::unordered_map est une table de hachage en fonction conteneur associatif introduit dans C++11

Ainsi, afin de clarifier les garanties sur la commande.

En C++03:

• std::set, std::multiset, std::map et std::multimap sont garantis pour être commandé en fonction de la clé (et le critère fourni)
• en std::multiset et std::multimap, la norme n'impose aucune garantie sur les éléments équivalents (c'est à dire, ceux qui comparent l'égalité)

En C++11:

• std::set, std::multiset, std::map et std::multimap sont garantis pour être commandé en fonction de la clé (et le critère fourni)
• en std::multiset et std::multimap, la Norme impose que les éléments équivalents (ceux qui comparent l'égalité) sont classés en fonction de leur ordre d'insertion (insertion de la première)
• std::unordered_* des conteneurs sont, comme le nom l'implique, n'est pas ordonné. Plus particulièrement, l'ordre des éléments peut changer lorsque le conteneur est modifié (lors de l'insertion/délétion).

J'espère que cela efface toute confusion.

Answer 4

Est-ce garanti pour imprimer 234 ou c'est la mise en œuvre définies?

Oui, std::map est une triés conteneur, commandé par l' Key avec le fournis Comparator. Donc, c'est garanti.

J'aimerais aller parcourir tous les éléments, avec la clé, supérieure à celle d'un béton de type int valeur.

C'est sûrement possible.

Answer 5

Oui ... les éléments dans un std::map ont un faible stricte-commande, ce qui signifie que les éléments sont composés d'un ensemble (c'est à dire, il n'y aura pas de répétitions de touches qui sont "égaux"), et l'égalité est déterminée par des essais sur les deux touches A et B, que si la clé n'est pas moins de la touche B, et B n'est pas inférieur à Un, puis la touche A est égal à clé B.

Cela étant dit, vous ne pouvez pas trier correctement les éléments d'un std::map si la faiblesse de la commande pour que le type est ambigu (dans votre cas, si vous utilisez des nombres entiers comme la clé-type, qui n'est pas un problème). Vous devez être en mesure de définir une opération qui définit un ordre total sur le type que vous utilisez pour vos clés dans vos std::map, sinon vous n'aurez qu'une commande partielle de vos éléments, ou poset, qui a la propriété où l'Un peut ne pas être comparable à B. Ce qui est en général le cas dans ce scénario est que vous serez en mesure d'insérer les paires clé/valeur, mais vous pouvez vous retrouver avec des doublons de paires clé/valeur si vous parcourir l'ensemble de la carte, et/ou de détecter les "disparus" de paires clé/valeur lorsque vous essayez d'effectuer une std::map::find() spécifique d'une paire clé/valeur dans la carte.