La norme C++11 exige-t-elle que deux itérations à travers un unordered_container constant visitent les éléments dans le même ordre ?

Question

for (auto&& i : unordered_container)
{ /* ... */ }

for (auto&& i : unordered_container)
{ /* .. */ }

La norme exige-t-elle que ces deux boucles visitent les éléments dans le même ordre (en supposant que le conteneur n'est pas modifié) ?

---

Mon analyse de cette question...

J'ai lu la norme et, d'après ce que je sais, la réponse est "non"...

Puisque les itérateurs de conteneurs sont en avant, il y a un langage qui exige que a==b impliquent que ++a==++b pour les itérateurs avant. Cela signifie que deux itérations passeront par le même chemin SI elles commencent toutes deux au même endroit. Cela réduit la question à une question différente, à savoir si la norme exige que container.begin() == container.begin() . Je n'ai pas trouvé de langue qui l'exige.

Answer 1

Les conteneurs doivent mettre en œuvre operator==() . C'est ce que nous pouvons faire :

container c;
c == c;

Cette relation doit fonctionner de la même manière que :

std::distance(a.begin(), a.end()) == std::distance(b.begin(), b.end()) &&
std::equal(a.begin(), a.end(), b.begin());

La partie importante ici est l'appel à std::equal() . Cet appel nécessite que deux appels indépendants à container.begin() produira la même séquence de valeurs. Si ce n'est pas le cas, alors c == c serait faux, et cela n'a aucun sens car == est une relation d'équivalence.

Par conséquent, ma réponse est que nous peut prétend que la norme exige que deux passages de tout doit aboutir à la même commande. Évidemment, cette exigence est rompue si vous faites quoi que ce soit qui modifie le conteneur ou invalide les itérateurs.

Citations :

• C++ 2011 Tableau 96 - Exigences en matière de conteneurs

Answer 2

Je pense que la conclusion de @Sharth est correcte, mais (pour quiconque se soucie de normes plus récentes) est déjà obsolète (et peut ne jamais avoir reflété la réalité - voir ci-dessous).

Des versions plus récentes de la norme (par exemple, n3797) ont modifié les exigences, apparemment de manière intentionnelle. enlever l'obligation de passer commande. Plus précisément, il est dit (§23.2.5/12) :

Deux conteneurs non ordonnés a y b comparez, égalisez si a.size() == b.size() et, pour tout groupe à clé équivalente [ Ea1 , Ea2 ) obtenu à partir de a.equal_range(Ea1) il existe un groupe de clés équivalentes [ Eb1 , Eb2 ) obtenu à partir de b.equal_range(Ea1) de telle sorte que distance(Ea1, Ea2) == distance(Eb1, Eb2) y is_permutation(Ea1, Ea2, Eb1) retourne vrai.

J'ai également une confiance relativement faible dans le fait que les implémentations répondent réellement aux exigences de la norme 2011. En particulier, les conteneurs non ordonnés sont normalement implémentés comme des tables de hachage avec des listes liées pour la résolution des collisions. Comme ces listes liées sont censées être courtes, elles ne sont pas nécessairement triées (d'autant plus que les éléments stockés dans des conteneurs non ordonnés ne sont pas tenus de définir les opérations à utiliser pour le tri, telles que operator< ). Dans ce cas, il est assez courant que les listes liées contiennent les mêmes éléments, mais dans un ordre qui dépend de l'ordre dans lequel ils ont été insérés.

Dans ce cas, il serait assez courant que deux tables de hachage contenant les mêmes éléments qui ont été insérés dans des ordres différents, itèrent sur ces éléments dans des ordres différents.

En théorie, une telle mise en œuvre n'est pas conforme à la norme C++11 - mais je suppose que le changement cité ci-dessus a été effectué en grande partie parce que cette exigence ne pouvait pas être satisfaite en pratique (parce que, comme indiqué ci-dessus, le conteneur n'avait aucun moyen de faire respecter l'ordre).

Donc, tant que vous traitez avec le même conteneur, inchangé, dépendre de l'itération dans le même ordre peut être sûr. Cependant, deux conteneurs ayant le même contenu peuvent ne pas fonctionner aussi bien (et même dans ce qui prétend être une implémentation C++11, vous ne pouvez probablement pas vous attendre à ce qu'elle réponde à des exigences plus strictes que celles contenues dans les nouvelles versions).

Answer 3

Selon ma lecture de la norme, cela n'est pas garanti. L'article 23.2.5, paragraphe 6, stipule que :

Ainsi, bien que l'ordre absolu des éléments dans un ordre non ordonné ne soit pas spécifié, ses éléments sont groupés en groupes de clés équivalentes de telle sorte que tous les éléments de chaque groupe ont clés équivalentes. Les opérations de mutation sur des conteneurs non ordonnés doivent préserver l'ordre relatif des éléments à l'intérieur de chaque groupe de clés équivalentes. sauf indication contraire.

Supprimons la garantie assez claire que les éléments qui sont hachés sur la même clé verront leur ordre relatif préservé quoi qu'il arrive. Cela semble assez clair. De plus, excluons toute modification du conteneur. Dans la portée restante :

Bien que cela ne définisse pas explicitement que l'ordre d'itération, en l'absence de modifications du conteneur, est instable, j'interprète la déclaration "l'ordre absolu des éléments dans un conteneur non ordonné n'est pas spécifié" à sa valeur littérale. Si l'ordre d'itération n'est pas défini, alors il est indéfini, et il n'est pas garanti qu'il soit le même à chaque fois.

Je pense que tout se résume à savoir si, dans l'extrait cité, "n'est pas spécifié" doit être interprété comme "cela pourrait être n'importe quoi" ou "cela pourrait être n'importe quoi, à n'importe quel moment".

Je pense que l'on peut argumenter dans les deux sens. J'interpréterais "n'est pas spécifié" dans l'interprétation la plus stricte et la plus littérale de la seconde, mais je n'objecterais pas trop si quelqu'un argumentait en faveur de la première.

Answer 4

Les conteneurs non ordonnés renvoient des itérateurs de type "forward" (qui sont définis dans le § 24.2.5) et ceux-ci ont cette propriété : a == b implies ++a == ++b . Cela semble impliquer que si longtemps que unordered_container.begin() == unordered_container.begin() est vrai, que l'ordre de traversée sera le même.

Je n'ai pas trouvé de langue qui exige unordered_container.begin() == unordered_container.begin() ce qui m'a conduit à une réponse provisoire de "non", l'ordre de traversée n'a pas besoin d'être le même.