L'ordre d'itération dans std :: map est-il connu (et garanti par le standard)?

158

Ce que je veux dire, c'est - nous savons que les std::mapéléments de s sont triés en fonction des clés. Donc, disons que les clés sont des entiers. Si j'itère de std::map::begin()à en std::map::end()utilisant a for, la norme garantit-elle que je vais itérer en conséquence à travers les éléments avec des clés, triés par 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;
}

L'impression 234est-elle garantie ou est-ce une implémentation définie?


Raison réelle: j'ai une clé std::mapavec int. Dans de très rares situations, j'aimerais parcourir tous les éléments, avec une clé, supérieure à une intvaleur concrète . Oui, il semble que ce std::vectorserait le meilleur choix, mais remarquez mes "situations très rares".


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

Kiril Kirov
la source
6
Au cas où vous ne le sauriez pas: dans votre vie réelle, vous pouvez l'utiliser map::upper_boundpour trouver le point de départ de l'itération.
Steve Jessop
Je le sais et je connais l'endroit exact où je commencerais à itérer. J'ai juste erré si la commande est garantie.
Kiril Kirov
Un vecteur clairsemé ne serait pas judicieux si vos clés (indices numériques) varient énormément à travers le tableau. J'utilise une solution similaire pour laquelle l'index numérique représente une coordonnée y cartésienne dans un espace à 3 dimensions. L'utilisation d'un vecteur dans ce scénario augmenterait mon empreinte mémoire de gigaoctets. Je ne pense donc pas que le vecteur soit une panacée ici, loin de là.
Jonathan Neufeld
Je ne comprends pas la question et j'expliquerai pourquoi à travers une expérience de pensée. Si vous savez déjà que les éléments sont ordonnés, comment l'itération pourrait-elle ne pas être? Que signifie même la commande, si elle ne s'applique pas à l'itération? Quels sont les autres cas où l'ordre compte, est détectable, etc.? (La réponse a été donnée par Konstantin .)
underscore_d

Réponses:

176

Oui, c'est garanti. De plus, *begin()vous donne le plus petit et *rbegin()le plus grand élément, comme déterminé par l'opérateur de comparaison, et deux valeurs clés aet bpour lesquelles l'expression !compare(a,b) && !compare(b,a)est vraie sont considérées comme égales. La fonction de comparaison par défaut est std::less<K>.

L'ordre n'est pas un bonus chanceux, mais plutôt un aspect fondamental de la structure de données, car l'ordre est utilisé pour déterminer quand deux clés sont identiques (par la règle ci-dessus) et pour effectuer une recherche efficace (essentiellement un binaire recherche, qui a une complexité logarithmique dans le nombre d'éléments).

Kerrek SB
la source
std :: map est implémenté en utilisant des arbres binaires, donc techniquement aucune recherche binaire n'est effectuée.
jupp0r
11
@ jupp0r: Structurer une plage comme un arbre de recherche binaire est une méthode particulière pour implémenter une recherche binaire dans la plage. La "recherche binaire" est un concept abstrait plutôt qu'une implémentation particulière. Peu importe que vous sautiez par des décalages dans un tableau ou que vous suiviez des nœuds de liaison; ce ne sont que des moyens spécifiques de «diviser la fourchette en deux».
Kerrek SB
1
Je sais que c'est un ancien message, mais pour être clair, la "recherche efficace" est relative. Techniquement, le std::unordered_mapa un temps de recherche plus efficace de O (1). L'avantage de std::mapréside dans l'ordre des clés, mais pas dans la recherche.
Adam Johnston
42

Ceci est garanti par les exigences de conteneur associatif dans la norme C ++. Par exemple, voir 23.2.4 / 10 en C ++ 11:

La propriété fondamentale des itérateurs de conteneurs associatifs est qu'ils
parcourir les conteneurs dans l'ordre non décroissant des clés où
non descendant est défini par la comparaison qui a été utilisée pour les construire.
Pour deux itérateurs déréférençables 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 des clés uniques, la condition la plus forte est maintenue,
  value_comp (* i, * j)! = false.
Konstantin Oznobihin
la source
32

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

Dans la plupart des langues, a mapest simplement un AssociativeContainer: il mappe une clé à une valeur. Dans les langues "plus récentes", ceci est généralement réalisé en utilisant une carte de hachage, donc aucun ordre n'est garanti.

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

  • std::mapest un conteneur associatif trié
  • std::unordered_map est un conteneur associatif basé sur une table de hachage introduit dans C ++ 11

Donc, afin de clarifier les garanties à la commande.

En C ++ 03:

  • std::set, std::multiset, std::mapEt std::multimapsont garantis d'être commandé en fonction des touches (et le critère fourni)
  • dans std::multisetet std::multimap, la norme n'impose aucune garantie d'ordre sur les éléments équivalents (c'est-à-dire ceux qui se comparent égaux)

En C ++ 11:

  • std::set, std::multiset, std::mapEt std::multimapsont garantis d'être commandé en fonction des touches (et le critère fourni)
  • dans std::multisetet std::multimap, la norme impose que les éléments équivalents (ceux qui se comparent égaux) soient ordonnés selon leur ordre d'insertion (insérés en premier)
  • std::unordered_*les conteneurs ne sont, comme leur nom l'indique, pas ordonnés. Plus particulièrement, l'ordre des éléments peut changer lorsque le conteneur est modifié (lors de l'insertion / suppression).

Lorsque la norme dit que les éléments sont ordonnés d'une certaine manière, cela signifie que:

  • lors de l'itération, vous voyez les éléments dans l'ordre défini
  • lors de l'itération en sens inverse, vous voyez les éléments dans l'ordre inverse

J'espère que cela dissipe toute confusion.

Matthieu M.
la source
Cela n'a rien à voir avec ma question, désolé :) Je sais lesquels sont commandés et lesquels - non. Et je demande l'ordre lorsque je parcours les éléments.
Kiril Kirov
10
@KirilKirov: eh bien, la définition d'un conteneur associatif ordonné est que lors de son itération, les éléments sont ordonnés.
Matthieu M.
Eh bien, je suppose que vous avez raison, mais je ne savais pas cela et c'est exactement ce que je demandais :)
Kiril Kirov
4

Est-ce que l'impression 234 est garantie ou son implémentation est-elle définie?

Oui, std::mapest un conteneur trié, commandé par le Keyavec le fourni Comparator. C'est donc garanti.

Je voudrais parcourir tous les éléments, avec une clé, supérieure à une valeur int concrète.

C'est sûrement possible.

jpalecek
la source
3

Oui ... les éléments de a std::mapont un ordre faible strict, ce qui signifie que les éléments seront composés d'un ensemble (c'est-à-dire qu'il n'y aura pas de répétition de clés "égales"), et l'égalité est déterminée en testant sur tout deux clés A et B, que si la clé A n'est pas inférieure à la clé B, et B n'est pas inférieure à A, alors la clé A est égale à la clé B.

Cela étant dit, vous ne pouvez pas trier correctement les éléments de a std::mapsi l'ordre faible pour ce type est ambigu (dans votre cas, où vous utilisez des entiers comme type de clé, ce n'est pas un problème). Vous devez être capable de définir une opération qui définit un ordre total sur le type que vous utilisez pour les clés de votre std::map, sinon vous n'aurez qu'un ordre partiel pour vos éléments, ou poset, qui a une propriété où A peut ne pas être comparable à B. Ce qui se passera généralement dans ce scénario, c'est que vous serez en mesure d'insérer les paires clé / valeur, mais vous risquez de vous retrouver avec des paires clé / valeur en double si vous parcourez toute la carte et / ou détectez «manquant» paires clé / valeur lorsque vous essayez d'effectuer une std::map::find()paire clé / valeur spécifique dans la carte.

Jason
la source
Comme les autres réponses, cela ne répond pas réellement à ma question, merci quand même.
Kiril Kirov
-3

begin () peut donner le plus petit élément. Mais c'est la mise en œuvre qui dépend. Est-il spécifié dans la norme C ++? Sinon, il est dangereux de faire cette hypothèse.

Pyang
la source