Une carte STL donne-t-elle toujours le même ordre lors de l'itération de begin() à end()?

Il semble de mes tests simples, mais je me demande si cela est garanti?Une carte STL donne-t-elle toujours le même ordre lors de l'itération de begin() à end()?

Y a-t-il des conditions dans lesquelles la commande ne sera pas garantie?

Modifier: Le cas, je suis particulièrement intéressé est si je remplir une carte avec un grand nombre d'entrées, sera l'ordre du itertator soit le même sur plusieurs pistes de mon exécutable? Que faire si les entrées sont insérées dans un ordre différent?

Source

2009-06-11 Jamie Cook

Si vous avez besoin d'éléments commande garantie, ne devriez-vous pas utiliser une structure semblable à List? Une carte par définition n'a pas d'ordre puisque les valeurs sont placées aux emplacements déterminés en hachant leurs clés. – Gishu

Notez la différence entre la commande et la séquence. List, vector et dequeue sont des conteneurs de séquence. Set et carte sont des conteneurs commandés. – Flame

Oui, il maintient un ordre interne, donc l'itération sur un ensemble qui ne change pas devrait toujours être la même. De here:

En interne, les éléments de la carte sont triées de bas à clé valeur plus élevée suite à une faible stricte spécifique critère de commande mis sur la construction .

Source

2009-06-11 03:34:50

En glibc, c'est un arbre rouge-noir. Bien que la commande stricte ne soit pas dans la spécification STL, c'est la norme de facto. –

@Jeffamaphone Et si votre clé est un pointeur vers un objet, vous pouvez obtenir n'importe quel type de commande à travers plusieurs exécutions de votre programme .... eh bien cela explique cela alors :) –

@Jamie Cook: Techniquement, les pointeurs sont aren 't des clés valides (au moins avec le comparateur std :: less par défaut) car il n'y a pas d'opérateur

Une carte STL donnera-t-elle le même ordre avec begin/end si elle est inchangée? Oui. Si vous changez la carte, ne dépassez pas la commande restant la même.

Source

2009-06-11 03:32:24 JaredPar

... mais l'ordre des éléments inchangés reste le même - toutes les insertions ou suppressions seront reflétées à l'endroit approprié dans la séquence par la relation d'ordre définie. C'est-à-dire que les changements apportés à la carte modifieront l'ordre d'itération de manière entièrement prévisible. –

-2

Sur le même ensemble de données sous la même implémentation de STL, oui. Il n'est pas garanti d'être le même à travers différentes implémentations pour autant que je sache.

Source

2009-06-11 03:32:31

La garantie est la même pour toutes les implémentations, à condition que le comparateur fournisse un ordre faible strict valide - sinon tous les paris sont désactivés! –

Donc, c'est garanti à moins que ce ne soit pas? :) –

std::map est un récipient triés, donc, oui, l'ordre est garanti (identique à la commande que vous utilisez dans son constructeur implicitement ou explicitement). Ne pas compte sur ce pour le populaire (mais pas encore-stanard) hashmap si - il a de très nombreux avantages dans de nombreux cas par rapport à std::map, mais pas un ordre prévisible de l'itération!

Source

2009-06-11 03:37:36

En C++ 0x, la carte/l'ensemble basé sur le hachage est appelé unordered_map/unordered_set. Il est très clair de ne pas être commandé. – Flame

std :: carte est une collection triée
et vous devrez définir moins que l'opérateur
imagine m est une carte de type T:

assert(m.size() > 1); 
for (std::map<T>::const_iterator i = m.begin(); i != m.end(); ++i) { 
    std::map<T>::const_iterator j = i + 1; 
    while (j != m.end()) { 
     assert(*i < *j); 
     ++j; 
    } 
}

Source

2009-06-11 04:41:12

Une carte STL donne-t-elle toujours le même ordre lors de l'itération de begin() à end()?

Répondre

Questions connexes