Tableaux et stl

Si tu as un problème de ce type, il me semble que c'est a priori que tu
ferais mieux d'éviter std::vector et d'utiliser plutôt une std::list :
tu sous-entends qu'il est ici lourd et à éviter que de créer un
temporaire pour copie. Or le vecteur fait cela tout le temps dès que la
taille change, et le list permet de l'éviter.

Si on fait un resize avec une taille inférieure, il y a réallocation, ou
bien est-ce que cela garde la zone mémoire actuelle?

Alain Gaillard wrote on 18/09/2006 19:39:

(std::vector<>)

Comment ça, simple affectation de pointeur ?

parce que vector<> est resizable, il repose nécessairement sur un array
de pointeur sur la classe template. il ne s'agit pas d'hypothèses sur
une implémentation X ou Y de telle STL mais d'une nécessité.

dès lors le moyen d'insérer un nouvel item dans un vector<> (pas de
créer le vector initial avec une taille non nulle) est:

- de recevoir une référence ou un temporaire (la différence n'existant
que dans le contexte de l'appelant) pour en réaliser une copie dynamique
et stocker cette copie.

- de recevoir un pointeur sur une instance dynamique, dans ce cas ce
pointeur pourrait être directement affecté au nouvel emplacement créé
dans le vector ou irait en remplacement d'un item existant (idiome
setAt(..)).

si un objectif important des rédacteurs de vector<> est d'éviter toute
erreur sur les pointeurs, leur choix fait sens, on ne pourra pas écrire
par exemple:

T* t = new T(...);
v.push(t);
delete t;

qui planterait; son interface impose:

T* t = new T(...);
v.push(*t);
delete t;

qui, parce que "t" a été cloné, ne plantera pas.

ce qui me ""gène"" est le fait que cette interface résulte (un peu) de
choix non sémantiques et/ou rationnelles mais sur des hypothèses sur le
codeur distrait - soit, ils existent; soit le langage peut aider à
limiter la casse, ...

soit aussi, il "suffit" de créer un vector<T*> (et non vector<T>) si
l'on souhaite insérer des T*, mais je reboucle alors sur la réponse
faite à James, on peux souhaiter contrôler / réaliser l'instantiation
des items mais manipuler des références (et non des pointeurs) lors de
l'utilisation des opérateurs [] de vector<> et de ses itérateurs.

Sylvain.



Sylvain.

JM wrote on 18/09/2006 23:01:

Si on fait un resize avec une taille inférieure, il y a réallocation, ou
bien est-ce que cela garde la zone mémoire actuelle?

cela peut dépendre de l'implémentation, je pense que la réallocation
n'est pas garantie: le vector<> travaillant naturellement avec son
concept d'itérateur, il aura tendance à simplement ajuster ses bornes.

évidemment un resize(10% * size()) pose dès lors en problème en
l'absence d'une méthode pack() (compactant le vecteur a sa seule taille
nécessaire).

Sylvain.

soit aussi, il "suffit" de créer un vector<T*> (et non vector<T>) si
l'on souhaite insérer des T*, mais je reboucle alors sur la réponse
faite à James, on peux souhaiter contrôler / réaliser l'instantiation
des items mais manipuler des références (et non des pointeurs) lors de
l'utilisation des opérateurs [] de vector<> et de ses itérateurs.

J'ai un peu l'impression que ce que tu souhaites, c'est un adaptateur au
dessus de vector permettant de manipuler un vector<T*> comme s'il gérait
des T.

As-tu regardé boost::iterator, en particulier
http://www.boost.org/libs/iterator/doc/indirect_iterator.html ?

--
Loïc

Sylvain wrote:

kanze wrote on 18/09/2006 19:12:

ben parce que "cela créé un temporaire" !

C'est un peu la philosophie de base de C++. On a des
temporaires sur la pile, plutôt que seulement des objets
créés dynamiquement.

j'aime cette philosophie, la coexistence de variables statiques ET
dynamiques me va très bien également; non, je ne vois pas comment
efficacement sans passer.

c'est ici seulement l'interface de vector<> dont il est question.

Certes. Tout ce que je disais, c'est qu'elle est conforme avec
la reste du C++.

- on peux vouloir la "classe vectorisée" non copiable.

On ne peut pas. C'est contre la philosophie de base. (En fait,
je vois mal comment ça serait implémentable.)

je suis également d'accord avec les exigences du contrat de
vector<>, je soulignais le trait pour indiquer qu'il a *IMHO*
un caractère négatif.

C'est là où je ne suis pas. Pour dire qu'il a un caractère
négatif, il faut bien présenter une alternative qui ne l'a pas.
Or, je crois que cette caractèristique est implicite dans
l'orientation valeur ; tu ne peux pas faire une collection à
orientation valeur sans l'avoir.

On peut discuter sur les convenances des choix de base ; selon
l'application et le style de programmation, différents choix
pourraient avoir des avantages. Mais je vois mal, une fois le
choix de base fait pour la sémantique de valeur, comment se
passer des temporaires et des copies. J'ai plutôt l'impression
qu'ils sont implicits dans le choix de base.

il reste toutefois des cas où on a bien affaire à des
instances qui doivent être non copiables (wrapper de resources
physiques par exemple, ou gestionnaire d'accès à une source
non multi-entrante, etc); de tels gestionnaires ne peuvent pas
être regroupés / utilisés via un vector<>.

Tout à fait d'accord. Aucun choix de base ne convient pour tout,
et il s'agit ici des éléments pour lesquels le choix de base
sémantique de valeur ne convient.

Le C++ a fait un choix, dès le départ, de se baser sur une
sémantique de valeur, avec des pointeurs et l'allocation
dynamique pour implémenter d'autres sémantiques dans les cas où
elles conviennent. Des classes de la STL suivent ce choix, et on
est bien amené dans certains cas de faire des collections des
pointeurs, de même que si je veux renvoyer un tel objet d'une
fonction, je me sers d'un pointeur.

- on peux, en effet, trouver étonnant le fait de transmettre
un truc ne servant qu'à être jeté (création tempo,
instantiation ptr, recopie, destruction; tout ça à la place
d'une simple affectation de pointeur ne parait pas très
vertueux).

Et quelle est l'alternative ? Crée tout dynamiquement, et ne
travailler qu'avec des pointeurs ?

une alternative simple serait de pouvoir transmettre un T* (et
même tout pointeur sur une classe assimilable à un T (T et ses
sous classes)).

Chose que rien ne t'empèche à faire. std::vector<T*> marche très
bien.

Évidemment, dans de tels cas, une allocation dynamique avec une
gestion explicite de la durée de vie de l'objet (et de la
mémoire, si tu n'utilises pas de glaneur de cellules) s'impose.

l'organisation interne de vector<> passe nécessairement par
des pointeurs de la classe template, n'imposer que des
références à l'insertion ne me parait pas si indispensable.
(ok, tu vas me répondre que je n'ai pas le droit de lire la
définition du template ou d'en tirer des conclusions).

Non, mais je n'y vois pas tellement d'utilisation des pointeurs
à des T. Il n'y a certainement pas un pointeur par élément.

Je ne suis pas sûr de t'avoir bien compris, d'ailleurs. Dans la
pratique, quand il s'agit d'un paramètre d'une fonction, une
référence et un pointeur sont plus ou moins la même chose. À
part la syntaxe, la seule véritable différence, c'est que tu
peux passer un temporaire à une référence à const, mais non à un
pointeur à const. La question intéressante me semble bien plus,
est-ce que le vector stocke une copie de l'objet qu'on lui
fournit, ou est-ce qu'il stocke l'objet même ? S'il stocke une
copie, il faut bien que l'objet supporte la copie, et
évidemment, il y aurait des copies chaque fois qu'on insère un
objet, et je vois mal comment on pourrait éviter la construction
du temporaire, puis sa copie. Si on stocke l'objet même, on
évite la copie, mais la gestion de la durée de vie de l'objet
reste à charge de l'utilisateur -- dans la pratique, ça veut
dire que l'objet doit être alloué dynamiquement la plupart du
temps.

Dans les fait, la STL supporte les deux. La copie, tu l'as par
défaut, avec std::vector<T>. Sinon, tu fais un std::vector<T*>,
et tu as l'autre sémantique.

si la question était ouverte ("si" parce que heureusement 99%
des utilisateurs se foutent de l'avis qui suit), le mérite de
vector<> est son mécanisme allocator customisable (justement
pour traiter les références) et son redimensionnement, dans un
second temps ses itérateurs.

Je ne vois pas trop le rapport entre l'allocator et les
références ici. Je sais que l'allocator déclare le type
reference, mais je crois que par ailleurs, il y a assez de
contraints sur ce type pour qu'il ne peut être qu'une vraie
référence. Historiquement, Stepanov a conçu des allocator pour
gérer un peu les modèles de compilation des Intel 16 bits : on
pouvait avoir un vector avec plus de 64 Ko même en compilant
avec modèle small, à condition d'utiliser un allocator où
reference et pointer avaient des attributes FAR. Quelque part
pendant la normalisation, cette motivation a disparue, mais le
typedef pour reference a resté ; dans la pratique, si ce n'est
pas une vraie référence C++, il doit être un type d'extension
fourni le compilateur et qui se comporte à tout égards comme une
vrai référence. Aujourd'hui, sur un système généraliste (Windows
ou Unix), à peu près la seule utilisation des allocator sur
mesure que je connais, c'est de mettre une collection dans la
mémoire partagée.

les 2 premiers points garantissent de travailler avec des
références (T&), c'est comme cela que je travaille dès que
possible donc il ne s'agirait pas de "travailler avec des
pointeurs", surtout pas; par contre je ne trouverais pas
gênant de faire un push(new T(...)).

Chose qui marche parfaitement bien avec un std::vector<T*>. Ce
que tu gagnes d'une côté (pas de copie), tu perds de l'autre
(allocation dynamique, nécessité d'une gestion explicite de la
durée de vie de l'objet). Parfois, c'est un qui convient,
parfois l'autre.

--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

Sylvain <noSpam@mail.net> writes:

Alain Gaillard wrote on 18/09/2006 19:39:

(std::vector<>)
Comment ça, simple affectation de pointeur ?

parce que vector<> est resizable, il repose nécessairement sur un array
de pointeur sur la classe template. il ne s'agit pas d'hypothèses sur une
implémentation X ou Y de telle STL mais d'une nécessité.

Les std::vector sont nécessairement stockés de façon contigue:
http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#69
Ça fait partie des précisions publiées dans C++2003.

A+

--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org

Sylvain wrote:

Alain Gaillard wrote on 18/09/2006 19:39:

(std::vector<>)

Comment ça, simple affectation de pointeur ?

parce que vector<> est resizable, il repose nécessairement sur
un array de pointeur sur la classe template. il ne s'agit pas
d'hypothèses sur une implémentation X ou Y de telle STL mais
d'une nécessité.

Sauf que je ne connais aucune implémentation qui marche comme
ça. C'est même intérdite par la norme (version 2003).

dès lors le moyen d'insérer un nouvel item dans un vector<>
(pas de créer le vector initial avec une taille non nulle)
est:

- de recevoir une référence ou un temporaire (la différence
n'existant que dans le contexte de l'appelant) pour en
réaliser une copie dynamique et stocker cette copie.

Sauf que la mémoire où est fait cette copie dynamique vient de
std::vector lui-même. Ultérieurement, oui, c'est de la mémoire
dynamique, mais (dans std::vector, au moins), c'est un seul bloc
de mémoire dynamique pour tous les éléments (ce qui est même
exigé de la norme actuelle, de façon à ce que tu peux utiliser
&v[0] comme paramètre à une fonction ancienne qui s'attend à un
T[], converti en pointeur).

[...]

ce qui me ""gène"" est le fait que cette interface résulte (un
peu) de choix non sémantiques et/ou rationnelles mais sur des
hypothèses sur le codeur distrait - soit, ils existent; soit
le langage peut aider à limiter la casse, ...

Stepanov n'a jamais pris en compte le « codeur distrait ».
Ici, il a simplement été cohérent avec la philosophie de C++,
qui utilise une sémantique de valeur par défaut.

--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

JM wrote:

Si tu as un problème de ce type, il me semble que c'est a
priori que tu ferais mieux d'éviter std::vector et
d'utiliser plutôt une std::list : tu sous-entends qu'il est
ici lourd et à éviter que de créer un temporaire pour copie.
Or le vecteur fait cela tout le temps dès que la taille
change, et le list permet de l'éviter.

Si on fait un resize avec une taille inférieure, il y a
réallocation, ou bien est-ce que cela garde la zone mémoire
actuelle?

La seule fonction qui peut réduire la taille du bloc de mémoire
allouée, c'est swap. Les contraites sur la complexité et la
validité des itérateurs, et les restrinctions sur les exceptions
font qu'aucune autre fonction qui reduit la taille du vector ne
peut pas déplacer le bloc de mémoire, ni même réduire la
capacité du vecteur.

--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

Sylvain wrote:

JM wrote on 18/09/2006 23:01:

Si on fait un resize avec une taille inférieure, il y a
réallocation, ou bien est-ce que cela garde la zone mémoire
actuelle?

cela peut dépendre de l'implémentation,

Pas vraiment. La norme spécifie beaucoup en ce qui concerne
std::vector, et ces spécifications ont dans la pratique l'effet
d'imposer une seule implémentation.

je pense que la réallocation n'est pas garantie:

C'est même garantie qu'elle n'aurait pas lieu.

le vector<> travaillant naturellement avec son concept
d'itérateur, il aura tendance à simplement ajuster ses bornes.

évidemment un resize(10% * size()) pose dès lors en problème
en l'absence d'une méthode pack() (compactant le vecteur a sa
seule taille nécessaire).

Quel problème ? Dans beaucoup d'utilisations, il fait
exactement ce qu'on veut :

std::vector< int > v ;
while ( ... ) {
v.clear() ;
// un packet de v.push_back()
// puis le traitement...
}

Ici, v atteindra rapidement sa taille maximum, et il n'y aura
plus d'allocations dynamique. Si ce n'est pas ce que je veux,
je déclare v dans la boucle, et j'ai une nouvelle instance
chaque fois.

Si je veux réelement réduire la taille utilisée à la taille
minimum :

std::vector<T>( v ).swap( v ) ;

fait l'affaire. (Je ne prétends pas que ce soit une façon
intuitive de le faire. C'est néaumoins l'idiome consacré, bien
connu entretemps à tous les utilisateurs de la STL. Et la STL
n'a jamais cherché à être simple à utiliser.)

--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

j'aime cette philosophie, la coexistence de variables statiques ET
dynamiques me va très bien également; non, je ne vois pas comment
efficacement sans passer.

Ben justement, il ne devrait pas y avoir coexistance.
Si tu veux du code de qualité, c'est-à-dire du code exception-safe,
toute donnée allouée dynamiquement est stockée dans un conteneur qui
gère sa durée de vie et qui répond à des sémantiques de valeur.
Donc le dynamique c'est uniquement dans des couches plus basses.

je suis également d'accord avec les exigences du contrat de vector<>, je
soulignais le trait pour indiquer qu'il a *IMHO* un caractère négatif.

Il n'y a pas de caractère négatif, c'est juste qu'on peut pas faire
autrement pour stocker des valeurs.

il reste toutefois des cas où on a bien affaire à des instances qui
doivent être non copiables (wrapper de resources physiques par exemple,
ou gestionnaire d'accès à une source non multi-entrante, etc); de tels
gestionnaires ne peuvent pas être regroupés / utilisés via un vector<>.

Normal, c'est physiquement impossible.
Tout ce que tu peux c'est centraliser les références à ces ressources et
la gestion de leur durée de vie.

une alternative simple serait de pouvoir transmettre un T* (et même tout
pointeur sur une classe assimilable à un T (T et ses sous classes)).

Ce qui ne change rien vu qu'on stocke des T, pas des T*.
Il faudra quand même une recopie.

l'organisation interne de vector<> passe nécessairement par des
pointeurs de la classe template

Non.
Comme il a déjà été dit, on stocke des T, pas des T*.
Je sais pas d'où te vient l'idée qu'on stocke des pointeurs des données
et pas les données elles-mêmes.

Tu aurais pourtant du, dans ton apprentissage du C++, réecrire un truc
semblable à std::vector.

si la question était ouverte ("si" parce que heureusement 99% des
utilisateurs se foutent de l'avis qui suit), le mérite de vector<> est
son mécanisme allocator customisable

Oui enfin, ça sert uniquement à utiliser des mécanismes comme le
pooling, ce qui est plus le travail du système d'exploitation et de
l'environnement.

(justement pour traiter les
références)

Mais quel rapport ?

et son redimensionnement, dans un second temps ses itérateurs.

Bon à la limite le redimensionnement d'accord (quoique y'a rien à
customiser, si on peut agrandir le segment on le fait et sinon on
recopie dans un endroit plus grand), mais les itérateurs !??
C'est du contigu donc de l'arithmétique de pointeurs de base.

les 2 premiers points garantissent de travailler avec des références
(T&), c'est comme cela que je travaille dès que possible donc il ne
s'agirait pas de "travailler avec des pointeurs", surtout pas;

Le principe de base quand même des conteneurs, c'est qu'ils contiennent
des trucs.
On pourrait effectivement faire fonctionner std::vector avec des
références (en spécialisant en utilisant des pointeurs pour
l'implémentation) mais cela n'aurait aucun intérêt.
Une référence, ça ne fait que référencer, ce n'est pas la chose en question.

par
contre je ne trouverais pas gênant de faire un push(new T(...)).

Ce que tu peux très bien faire avec un conteneur de T*.
Ce qui néanmoins pose des problèmes d'exception safety pour la
libération des éléments contenus.

Ce que tu veux, en fait, c'est des conteneurs avec des sémantiques de
pointeurs accessoirement polymorphiques.
Pour ça, y'a les conteneurs de pointeurs de boost.