Est de l'ordre de l'itération sur les std::map connu (et garanti par la norme)?
Ce que je veux dire est - on sait que le 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 de std::map::begin()
à std::map::end()
à l'aide d'un for
, la norme 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 est-il de 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 parcourir tous les éléments, avec la clé, supérieure à celle d'un béton int
valeur. Yep, ça sonne comme std::vector
serait le meilleur choix, mais à mon avis "très rares sont les situations".
MODIFIER: je sais, que les éléments de 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.
- Dans le cas où vous ne le saviez pas: dans votre vie réelle utilisation vous pouvez utiliser
map::upper_bound
pour trouver le point de départ de l'itération. - Je le sais et je sais exactement où je l'avais commencer à répéter. J'ai juste erré si la commande est garantie.
- Un clairsemée vecteur ne serait pas raisonnable si vos clés (indices numériques) varient énormément à travers le conseil d'administration. Je suis à l'aide d'une solution similaire pour lequel l'index numérique représente un Cartésien coordonnée dans un espace à 3 dimensions. À l'aide d'un vecteur dans ce scénario permettrait d'augmenter ma mémoire, par gigaoctets. Donc, je ne pense pas que le vecteur est une panacée ici, loin de là.
- Je ne comprends pas la question, et je vais vous expliquer pourquoi, grâce à une pensée de l'expérience. Si vous savez déjà que les éléments sont ordonnés, comment pourrait-itération ne pas être? Que fait la commande de dire que, si elle ne s'applique pas à l'itération? Quels sont les autres cas, il a où l'importance de l'ordre, est détectable, etc.? (La réponse a été donnée par Konstantin.)
Vous devez vous connecter pour publier un commentaire.
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 clésa
etb
pour lesquels l'expression!compare(a,b) && !compare(b,a)
est vrai, sont considérées comme égales. Par défaut la fonction de comparaison eststd::less<K>
.La commande n'est pas une chance de bonus, mais plutôt, il est un aspect fondamental 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).
*begin()
et*rbegin()
.Cela est garanti par conteneur Associatif exigences de la norme C++. E. g. voir l'article 23.2.4/10 en C++11:
et 23.2.4/11
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 un triés conteneur associatifstd::unordered_map
est une table de hachage en fonction conteneur associatif introduit dans C++11Afin de clarifier les garanties sur la commande.
En C++03:
std::set
,std::multiset
,std::map
etstd::multimap
sont garantis pour être commandé en fonction de la clé (et le critère fourni)std::multiset
etstd::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
etstd::multimap
sont garantis pour être commandé en fonction de la clé (et le critère fourni)std::multiset
etstd::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_*
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).Lorsque la Norme dit que les éléments sont ordonnés dans un sens, cela signifie que:
J'espère que cela efface toute confusion.
Oui,
std::map
est une triés conteneur, commandé par leKey
à l'aide desComparator
. Donc, c'est garanti.C'est sûrement possible.
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'une
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 vosstd::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 unestd::map::find()
spécifique d'une paire clé/valeur dans la carte.begin() peut donner le plus petit élément. Mais elle est mise en œuvre dépendait. Est-il spécifié dans la norme C++? Si non, alors il est dangereux de faire cette supposition.