petit excercice piège vector et références

Version imprimable

Bonjour,

je suis tombé sur ce problème récemment, alors je vous le propose sous forme d'exercice. Je vous préviens, c'est tordu (en plus j'ai rajouté du bruit).

Q1: qu'affiche le programme suivant?
Q2: pourquoi?

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
 
#include <string>
#include <vector>
 
using namespace std;
 
struct Foo
{
	Foo( const string & name = "n/a" ) : name(name) {}
	string name;
};
 
 
int main() 
{ 
	vector<Foo> fooes;
	fooes.push_back( Foo( "first foo" ) );
	Foo & first_foo = fooes.back();
	Foo & second_foo = first_foo;
	fooes.emplace_back( Foo( "second foo" ) );
	second_foo = fooes.back();
 
	cout << "foo1: " << first_foo.name << endl;
	cout << "foo2: " << second_foo.name << endl;
 
	getchar();
	return 0; 
}

07/08/2013, 14h23
Médinoc

Ma réponse:

Les deux affichent "second foo", parce que les deux références pointent sur le même Foo (le premier), qui a été écrasé par le second à la ligne second_foo = fooes.back();.
07/08/2013, 14h39
r0d

Et non!
Mais ça prouve que tu as été honnête et que tu as essayé de trouver sans compiler/exécuter.
Je ne donne pas la réponse tout de suite, peut-être que d'autres ont envie de chercher :)
07/08/2013, 15h00
Ehonn

Comportement indéterminé ?
Le emplace_back peut provoquer une réallocation.
07/08/2013, 15h22
Astraya

Ca crash nan? emplace_back ne fait aucune copie si je crois me rappeler et la Foo exite uniquement à l'appel de emplace_back. Donc second_foo.name crashera ou vaudra tout et n'importe quoi. Ou alors emplace_back fait une copie mais je ne sais pas trop.

EDIT : Autant pour moi c'est du move -_-'
07/08/2013, 15h39
koala01

Salut,

Quand j'étudiais, j'avais un prof qui n'hésitait jamais à "jouer au compilateur"... je vais faire pareil ici:

Code:

fooes.push_back( Foo( "first foo" ) );

ajoutes à fooes un nouvel élément dont la chaine de caractères correspond à "first foo"

Code:

Foo & first_foo = fooes.back();

récupère une référence (!!!) sur le dernier élément du vecteur, à savoir, la structure pour laquelle la chaine est "first foo"

Code:

Foo & second_foo = first_foo;

crée simplement une autre variable, qui fait référence au même élément

Code:

fooes.emplace_back( Foo( "second foo" ) );

ajoute, en utilisant la sémantique de mouvement, un deuxième élément dont la chaine est "second foo".

A priori, cela ne pose pas de problème en soi, sauf que... C'est pour les éléments de fooes que la sémantique de mouvement est utilisée, ce qui, à mon sens, n'empêche en rien le vecteur d'augmenter sa capacité en cas de besoin.

Il est fort vraisemblable que les objets soient placé dans l'espace nouvellement créé par mouvement, mais, quoi qu'il en soit, je dirais que les deux références se réfèrent à des éléments invalides.

Code:

second_foo = fooes.back();

récupère le dernier élément de fooes (celle dont la ligne est "second foo").

second_foo fait bel et bien référence à cet objet (qui est tout à fait valide), mais l'opérateur d'affectation n'est pas récursif / transitif.

Pour moi, first_foo fait toujours référence à un objet invalide

Code:

cout << "foo1: " << first_foo.name << endl;

A priori, comportement indéterminé parce que first_foo fait référence à un objet invalide.

Code:

cout << "foo2: " << second_foo.name << endl;

affiche "second string", quoi qu'il advienne

La seule chose dont je ne sois pas tout à fait sur, c'est le comportement de first_foo dans l'histoire.

J'aurais tendance à dire que, l'objet d'origine ayant de toutes manières été déplacé (que ce soit en utilisant la sémantique de mouvement ne change rien à l'histoire), ou risquant de l'avoir été (tout dépend de la capacité maximale créée par défaut pour ton implémentation spécifique), on ne devrait plus tenter le moindre accès à first_foo car on ne peut pas garantir qu'il n'aura justement pas été déplacé et que la référence soit donc toujours valide.

Les autres types de collections n'auraient sans doute pas posé ce genre de problème car elles sont (en théorie du moins) basées sur des pointeurs permettant de mettre les différents éléments en relation les uns avec les autres, mais std::vector devant de toutes manières assurer la contiguité des données, il est toujours susceptible de devoir (au mieux) déplacer les éléments qu'il contient
07/08/2013, 16h04
r0d

En effet vous avez raison, bien joué! :D
On a bien un comportement indéterminé sur le premier cout, mais en fait, j'ai bien testé avant de poster, et moi j'obtiens toujours un crash, même en release. Le 2eme cout c'est le même problème puisque la référence est la même.

Ici en fait, le emplace_back ne change rien à l'affaire, c'était juste pour brouiller les pistes. On aurait pu avoir un push_back c'était pareil.
De même que la deuxième variable qui référence la première, c'est juste pour brouiller les pistes.
En fait, c'est l'algorithme de gestion de la mémoire de la classe vector qui crée le problème ici (allocation dynamique + contigüité des éléments), et le fait qu'on déclare une/des nouvelle(s) variable(s) entre les deux push_back, ce qui implique le déplacement en mémoire du vector entier, et donc les références ne sont plus valides.

J'ai rencontré ça dans un code récemment, et j'ai eu un mal fou à trouver le problème, car ça peut crasher à n'importe quel moment (quand on utilise la variable), et quand c'est noyé dans du code complexe et fourni, c'est l'enfer.
J'hésite de rajouter cet exercice dans notre test d'embauche. C'est peut-être un peu fourbe quand-même.
07/08/2013, 16h07
r0d

Citation:

Envoyé par koala01

Les autres types de collections n'auraient sans doute pas posé ce genre de problème car elles sont (en théorie du moins) basées sur des pointeurs permettant de mettre les différents éléments en relation les uns avec les autres, mais std::vector devant de toutes manières assurer la contiguité des données, il est toujours susceptible de devoir (au mieux) déplacer les éléments qu'il contient

En effet, avec les listes et les heaps, on n'aurait pas eu le problème.
En revanche, avec les maps et les sets, qui sont des tree (red-black tree pour être précis), la gestion de la mémoire est complexe et je serais étonné que ce genre de choses se passent bien.
07/08/2013, 16h25
Médinoc

@koala01: Ton raisonnement implique de modifier une référence.

@Tous: Je pense que le comportement observé (puisqu'il n'est pas défini) doit dépendre de la stratégie d'allocation du vector: Une classe vector qui pré-alloue la taille pour deux éléments ou plus (soit lors de sa construction, soit lors de l'ajout du premier élément) aura le comportement que j'avais décrit. Tout autre implémentation peut causer un crash, écraser une zone mémoire toujours accessible mais non-utilisée, ou invoquer les démons nasaux.
07/08/2013, 16h26
koala01

Citation:

Envoyé par r0d

En effet vous avez raison, bien joué! :D

Merci (je le prend pour moi, je peux :question: :D)

Citation:

On a bien un comportement indéterminé sur le premier cout, mais en fait, j'ai bien testé avant de poster, et moi j'obtiens toujours un crash, même en release. Le 2eme cout c'est le même problème puisque la référence est la même.

Le pire de l'histoire, c'est que ca risque d'être très fortement dépendant de l'implémentation :aie:

Je m'explique: A priori, tout pourrait parfaitement se passer s'il n'y avait pas besoin de faire un resize() pour rajouter le deuxième élément.

Comme il me semble que la capacité de départ est laissée à l'appréciation de l'implémentation, nous pourrions donc parfaitement trouver une implémentation spécifique de std::vector prévoyant d'emblée 5, 10 ou 15 éléments ce qui retarderait le moment du resize() d'autant, un peu à l'instar de ce que l'on aurait si on avait fait appel à reserve().

Quoi qu'il en soit, dés le moment où un resize() sera nécessaire, toutes les références déclarées avant qu'il ne le soit seront invalidées ;)

Citation:

Ici en fait, le emplace_back ne change rien à l'affaire, c'était juste pour brouiller les pistes. On aurait pu avoir un push_back c'était pareil.
De même que la deuxième variable qui référence la première, c'est juste pour brouiller les pistes.

Je m'en étais douté :D

Citation:

En fait, c'est l'algorithme de gestion de la mémoire de la classe vector qui crée le problème ici (allocation dynamique + contigüité des éléments), et le fait qu'on déclare une/des nouvelle(s) variable(s) entre les deux push_back, ce qui implique le déplacement en mémoire du vector entier, et donc les références ne sont plus valides.

C'est ce que j'ai expliqué :D

Citation:

J'ai rencontré ça dans un code récemment, et j'ai eu un mal fou à trouver le problème, car ça peut crasher à n'importe quel moment (quand on utilise la variable), et quand c'est noyé dans du code complexe et fourni, c'est l'enfer.

Je n'en doute pas un seul instant :D

Citation:

J'hésite de rajouter cet exercice dans notre test d'embauche. C'est peut-être un peu fourbe quand-même.

Je crois au contraire que celui qui apporte la bonne réponse à ce genre de question montre de manière manifeste qu'il est capable de réfléchir par lui-même :D

Citation:

Envoyé par r0d

En effet, avec les listes et les heaps, on n'aurait pas eu le problème.
En revanche, avec les maps et les sets, qui sont des tree (red-black tree pour être précis), la gestion de la mémoire est complexe et je serais étonné que ce genre de choses se passent bien.

Hé bien, je ne crois pas.

Oui, bien sur, la gestion de la mémoire est complexe, mais nous restons quand même dans le cadre ou la relation entre les différents éléments est représentée par des pointeurs.

Le fait qu'il y en ait deux et que l'on s'amuse peut être à "balancer" l'arbre à coup de rotations ne changera pas grand chose (ou du moins ne devrait pas changer grand chose): une fois qu'un élément a été ajouté, il ne sera plus ni copié ni déplacé. Seules les relations gauche / droite (rouge/noir ... less/more) qui le composent et qui composent les autres éléments seront modifiée afin de le placer "au bon endroit" dans l'arbre.

Je serais surpris (quoi que... sait on jamais :question:) qu'un set (ou une map) n'en vienne à réorganiser la mémoire de son propre chef, histoire d'éviter (par exemple) les cach misses éventuels dus à la fragmentation des positions des différents éléments en mémoire ;)
07/08/2013, 16h40
koala01

Citation:

Envoyé par Médinoc

@koala01: Ton raisonnement implique de modifier une référence.

Non, tu assignes une nouvelle valeur à une référence

Tant que l'objet que tu essayes d'assigner à la référence existe, il n'y a pas de problème ;)

Mon raisonnement pointait surtout le resize() du doigt (même si je ne l'ai pas cité explicitement dans ma première intervention) et le fait que, lorsque le resize est effectué, vector n'a pas d'autre choix que de copier / déplacer les éléments qu'il contient déjà vers l'espace mémoire nouvellement alloué.

A partir de là, tout ce qui fait référence, d'une manière ou d'une autre, à l'espace mémoire qui était alloué avant le resize "pointe" purement et simplement dans "les limbes" et ne pourra plus faire qu'une chose: provoquer un comportement indéfini.

Citation:

@Tous: Je pense que le comportement observé (puisqu'il n'est pas défini) doit dépendre de la stratégie d'allocation du vector: Une classe vector qui pré-alloue la taille pour deux éléments ou plus (soit lors de sa construction, soit lors de l'ajout du premier élément) aura le comportement que j'avais décrit.

C'est, en gros, ce que j'expliquais dans mon intervention suivante (je te jure, j'étais occupé à l'écrire avant de t'avoir lu :D), mais c'est très dépendant de l'implémentation.

Quoi qu'il en soit, comme je le disais (aussi ;)) dans mon intervention précédente, le problème arrivera, quoi qu'il arrive, au premier resize() du seul fait de la garantie de contiguïté des éléments imposée à la classe vector ;)

Citation:

Tout autre implémentation peut causer un crash, écraser une zone mémoire toujours accessible mais non-utilisée, ou invoquer les démons nasaux.

C'est le propre des comportements indéfinis :D
07/08/2013, 17h07
Médinoc

Citation:

Envoyé par koala01

Code:

second_foo = fooes.back();

récupère le dernier élément de fooes (celle dont la ligne est "second foo").

second_foo fait bel et bien référence à cet objet (qui est tout à fait valide), mais l'opérateur d'affectation n'est pas récursif / transitif.

Pour moi, first_foo fait toujours référence à un objet invalide

Code:

cout << "foo1: " << first_foo.name << endl;

A priori, comportement indéterminé parce que first_foo fait référence à un objet invalide.

Code:

cout << "foo2: " << second_foo.name << endl;

affiche "second string", quoi qu'il advienne

Ces paroles impliquent que dans ton raisonnement la référence second_foo a été modifiée et les deux références ne pointent plus vers le même objet (ce qui est impossible).
07/08/2013, 17h21
Bysbobo

Citation:

Envoyé par r0d

J'hésite de rajouter cet exercice dans notre test d'embauche. C'est peut-être un peu fourbe quand-même.

C'est quand les sessions de recrutement? ;)
07/08/2013, 17h27
koala01

Citation:

Envoyé par Médinoc

Ces paroles impliquent que dans ton raisonnement la référence second_foo a été modifiée et les deux références ne pointent plus vers le même objet (ce qui est impossible).

Juste au temps pour moi...

J'avais temporairement oublié qu'il est impossible de modifié l'objet référencé par une référence :aie: Merci de la piqure de rappel :D
07/08/2013, 17h30
Médinoc

[pédanterie]Si, l'objet référencé est modifiable, c'est la référence elle-même qui ne l'est pas.

second_foo = fooes.back(); modifie justement l'objet référencé, l'écrasant avec le contenu du dernier élément du vecteur.[/pédanterie]
Enfin, ça dépend de ce qu'on entend par "modifier l'objet référencé par une référence".
07/08/2013, 17h49
r0d

Citation:

Envoyé par Bysbobo

C'est quand les sessions de recrutement? ;)

On recrute déjà.
Seulement pour l'instant nous n'avons pas de quoi rémunérer correctement un dev alors on ne prend que des stagiaires :/
Mais très sincèrement, nous aurons bientôt de quoi embaucher, et le plus vite sera le mieux parce que sur mon projet nous sommes complètement débordés.
07/08/2013, 18h22
koala01

Citation:

Envoyé par Médinoc

[pédanterie]Si, l'objet référencé est modifiable, c'est la référence elle-même qui ne l'est pas.

second_foo = fooes.back(); modifie justement l'objet référencé, l'écrasant avec le contenu du dernier élément du vecteur.[/pédanterie]
Enfin, ça dépend de ce qu'on entend par "modifier l'objet référencé par une référence".

Pour continuer dans la pédanterie, l'objet référencé à ce moment là est, de toutes manières, devenu invalide suite au resize (ou doit du moins être considéré comme tel) occasionné par le emplace_back (push_back ou toute autre fonction d'ajout et d'insertion d'élément dans le tableau :D).

Le comportement indéfini apparait donc (ou, du moins, risque fort d'apparaitre, selon l'implémentation) déjà à cette ligne ;)
02/09/2013, 15h05
jblecanard

Salut

J'arrive trop tard pour le prouver mais j'avais bien trouvé la réponse :)

Citation:

Envoyé par koala01

Le pire de l'histoire, c'est que ca risque d'être très fortement dépendant de l'implémentation

Je m'explique: A priori, tout pourrait parfaitement se passer s'il n'y avait pas besoin de faire un resize() pour rajouter le deuxième élément.

Comme il me semble que la capacité de départ est laissée à l'appréciation de l'implémentation, nous pourrions donc parfaitement trouver une implémentation spécifique de std::vector prévoyant d'emblée 5, 10 ou 15 éléments ce qui retarderait le moment du resize() d'autant, un peu à l'instar de ce que l'on aurait si on avait fait appel à reserve().

Attention à ne pas confondre resize() et reserve() qui font deux choses très différentes ! Ici, c'est bien l'ajout d'un reserve() qui peut rendre le comportement bien défini sans changer le sens du code.
02/09/2013, 18h16
koala01

Citation:

Envoyé par jblecanard

Salut

J'arrive trop tard pour le prouver mais j'avais bien trouvé la réponse :)

Attention à ne pas confondre resize() et reserve() qui font deux choses très différentes ! Ici, c'est bien l'ajout d'un reserve() qui peut rendre le comportement bien défini sans changer le sens du code.

Pour autant que je ne fasse pas erreur, il y en a d'office un qui appelle l'autre (je pencherais sur resize() qui appelle reserve() dans certaines circonstances), reserve() ayant comme finalité de prévoir un espace suffisant pour représenter le nombre d'éléments indiqué, resize() ayant pour finalité de modifier effectivement la taille renvoyée par size(), c'est à dire le nombre d'élément effectivement contenus (et donc représentables) à un instant T.

Resize() aura donc, a priori, le même résultat dés le moment où il aura, d'une manière ou d'une autre, manipulé le pointeur vers le premier élément que std::vector manipule en interne.

Elle peut le faire aussi bien pour rajouter des éléments quand l'espace alloué au pointeur interne devient trop petit, mais elle peut également le faire lorsqu'on supprime des éléments, dans l'idée de ne garder qu'un pointeur sur un espace "strictement nécessaire" à la représentation de tous les éléments à représenter.

Les deux comportements auront donc, a priori, pour résultat de provoquer un comportement indéfini ;)
02/09/2013, 20h10
jblecanard

Citation:

Envoyé par koala01

Pour autant que je ne fasse pas erreur, il y en a d'office un qui appelle l'autre (je pencherais sur resize() qui appelle reserve() dans certaines circonstances), reserve() ayant comme finalité de prévoir un espace suffisant pour représenter le nombre d'éléments indiqué, resize() ayant pour finalité de modifier effectivement la taille renvoyée par size(), c'est à dire le nombre d'élément effectivement contenus (et donc représentables) à un instant T.

C'est tout à fait exact. Mais si tu utilises resize, par exemple pour agrandir, tu vas créer de nouveaux éléments, size() n'aura plus la même valeur et emplace_back tout comme push_back auront toujours pour effet d'ajouter encore un nouvel élément, au risque de provoquer une invalidation des références.

Si on fait un reserve(2) au début du code montré avant l'ajout du premier élément, il n'y aura pas de problème car on sait que l'ajout du deuxième ne nécessitera pas de redimensionnement. La mémoire du vector n'est redimensionnée que lorsque la mémoire additionnelle est consommée. Si on se réserve assez de mémoire additionnelle, on est tranquille :).
02/09/2013, 20h52
koala01

Citation:

Envoyé par jblecanard

C'est tout à fait exact. Mais si tu utilises resize, par exemple pour agrandir, tu vas créer de nouveaux éléments, size() n'aura plus la même valeur et emplace_back tout comme push_back auront toujours pour effet d'ajouter encore un nouvel élément, au risque de provoquer une invalidation des références.

Si on fait un reserve(2) au début du code montré avant l'ajout du premier élément, il n'y aura pas de problème car on sait que l'ajout du deuxième ne nécessitera pas de redimensionnement. La mémoire du vector n'est redimensionnée que lorsque la mémoire additionnelle est consommée. Si on se réserve assez de mémoire additionnelle, on est tranquille :).

Mais n'est ce pas exactement le sens de ce que j'avais écrit :question:

Je me cite:

Citation:

Envoyé par koala01

Le pire de l'histoire, c'est que ca risque d'être très fortement dépendant de l'implémentation :aie:

Je m'explique: A priori, tout pourrait parfaitement se passer s'il n'y avait pas besoin de faire un resize() pour rajouter le deuxième élément.

C'est bel et bien un resize() qui est nécessaire lorsqu'on a attient la limite

Citation:

Comme il me semble que la capacité de départ est laissée à l'appréciation de l'implémentation, nous pourrions donc parfaitement trouver une implémentation spécifique de std::vector prévoyant d'emblée 5, 10 ou 15 éléments ce qui retarderait le moment du resize() d'autant, un peu à l'instar de ce que l'on aurait si on avait fait appel à reserve().

Autrement dit : L'implémentation va fournir de base un conteneur permettant d'introduire 5, 10 ou 15 éléments, exactement comme si tu avais utilisé toi même reserve(5), reserve(10) ou reserve(15).

Toujours est il que, si tu te retrouves avec 6, 11 ou 16 éléments à placer dans ton vecteur, resize() sera appelé et donc:

Citation:

Quoi qu'il en soit, dés le moment où un resize() sera nécessaire, toutes les références déclarées avant qu'il ne le soit seront invalidées ;)

sont-ce les mots "à l'instar de" qui t'ont empêché de comprendre ce que j'ai pourtant écrit dans un français plus que correct :question:
02/09/2013, 23h23
jblecanard

Hou je te sens vexé :mrgreen:

C'est juste que je trouve que les explications (pas forcément les tiennes) parfois longues dans les posts pour des sujets qui ne sont pas super compliqués non plus. L'invalidation ou non des références en fonction des différentes opérations effectuées sur une collection donnée sont des choses bien documentées, et tout dev C++ est rapidement amené à les comprendre.