OVH Cloud OVH Cloud

Contigüité des éléments d'un `std::vector´

167 réponses
Avatar
drkm
Je viens de tomber sur un message de Michel, d'il y a un mois, dont
voici un extrait :

> From: "Michel Michaud" <mm@gdzid.com>
> Subject: Re: buffer et std::vector<char> passage de l'un a l'autre
> Message-ID: <pQnHa.816$5d.225371@news20.bellglobal.com>
> Date: Mon, 16 Jun 2003 14:16:52 -0400

> Avec

> vector<char> v(taille);

> &v[0] est un char* qui peut être passé aux fonctions attendant un
> char[]/char*. La norme ne dit pas explicitement que les char sont
> contigus, mais c'est un fait et il y a une correction à la norme qui
> l'indique aussi.

J'avais toujours entendu dire que la contigüités des éléments d'un
vecteur était garantie. Apparemment non. Pour ce qui est de la
correction à la norme, je suppose que tu parlais d'un DR. En as-tu la
référence, stp ?

--drkm

10 réponses

Avatar
drkm
Gabriel Dos Reis writes:

drkm writes:

| Gabriel Dos Reis writes:

| > Fabien LE LEZ writes:

| > | Euh... j'ai très nettement l'impression que tu es d'accord
| > | avec moi, mais que ton subconscient refuse de l'admettre ;-)

| > À ta place, je me retiendrais de m'aventurer sur ce terrain
| > hasardeux.

| Quel terrain hasardeux ?

celui que tu es en train d'emprunter.


Ah, l'humour. C'est vrai que c'est un terrain hasardeux :-).

--drkm

Avatar
Gabriel Dos Reis
drkm writes:

| Gabriel Dos Reis writes:
|
| > drkm writes:
|
| > | Gabriel Dos Reis writes:
|
| > | > Fabien LE LEZ writes:
|
| > | > | Euh... j'ai très nettement l'impression que tu es d'accord
| > | > | avec moi, mais que ton subconscient refuse de l'admettre ;-)
|
| > | > À ta place, je me retiendrais de m'aventurer sur ce terrain
| > | > hasardeux.
|
| > | Quel terrain hasardeux ?
|
| > celui que tu es en train d'emprunter.
|
| Ah, l'humour.

ceux qui n'en ont pas s'exclament souvent « Ah, l'humour ».

-- Gaby
Avatar
Alain Naigeon
"Gabriel Dos Reis" a écrit dans le message
news:
(Arnaud Debaene) writes:

| > D'un autre côté je me demande moi-même comment
| > représenter une telle propriété... après tout, cela concerne
| > en premier lieu *l'implémentation* d'un itérateur sur cette
| > classe, mais à partir du moment où l'utilisateur peut avoir
| > accès au "prochain" élément, en quoi cela l'intéresse-t-il
| > de savoir où il se trouve par rapport au précédent ?
| Tout simplement parce qu'on peut vouloir accéder aux éléments du
| vector autrement que par un itérateur. L'interface de vector propose
| at et operator[].

Tout à fait exact. Et la question qui se posait était :

Si i et j sont des entiers dans les bornes d'un std::vector<> v,
l'égalité suivante a-t-elle lieu ?

&v[i] == &v[j] + (i - j) // ou &v.at(i) == &v.at(j) + (i - j)


D'accord, bien compris, mais : dès lors que tu exiges cette
propriété ex nihilo (= pas exprimée dans l'interface), tu
pourrais aussi bien l'exiger (la parachuter) pour tout autre
type de collection permettant un accès direct et renvoyant
une référence ?!

Exemple : j'ai un arbre binaire de recherche ; ses noeuds
stockent des objets munis d'une étiquette entière (en tout
cas munie des opérations + - et comparaison). Il y a une
fonction de l'arbre qui renvoie la référence à un objet si je
lui passe une étiquette.
Toutes les conditions sont donc réunies pour pouvoir exprimer,
éventuellement, la même égalité que ci-dessus. Et pourtant,
je parierais gros que tu n'aurais pas envie, cette fois-ci, de
sortir d'un chapeau l'idée qu'elle doit s'appliquer...
Conclusion : lorsqu'une classe est munie de tout ce qu'il faut
(cf ci-dessus), alors :
- ou bien elle s'appelle std::vector et l'égalité est vraie ;
- ou bien, pour une autre, on ne sait pas...

Hum, hum !? ;-)

Pour l'arbre on n'a pas envie d'exiger que l'égalité soit
vérifiée. Mais au moins, comme aucune promesse de sa
vérité n'apparaît dans l'interface, personne n'est fondé
à supposer qu'elle est vraie, et donc la morale (la logique)
est sauve.
Pour vector c'est bien différent : il faut, sans raison *apparente*,
"oser" la supposition que la relation est vraie... ; on peut appeler
cela de la programmation objet courageuse ? ;-)
Je persiste à trouver ça bizare, tout de même (faut-il que je
m'habitue à remplacer "bizare" par "sémantique" ?)
Evidemment "bizare" peut aussi, quelquefois, se dire "stimulant",
mais j'ai du mal à voir, pour l'instant.

--

Français *==> "Musique renaissance" <==* English
midi - facsimiles - ligatures - mensuration
http://anaigeon.free.fr | http://www.medieval.org/emfaq/anaigeon/
Alain Naigeon - - Strasbourg, France

Avatar
Alain Naigeon
"Gabriel Dos Reis" a écrit dans le message
news:
"Alain Naigeon" writes:

| > Beaucoup de gens considèrent en effet qu'il s'agit d'une entorse à
| > l'abstraction de type et à la modélisation objet (y'a qu'à voir le
| > troll que cette question vient - une fois de plus - de déclencher). On
| > peut considérer cela comme une concession à la pratique existante et à
| > l'utilisabilité de vector, personnellement ce ne me choque pas du
| > tout.
|
| Je respecte ton choix, entre le pour et le contre !
| Pour moi C++ serait bien plus séduisant et sûr s'il
| larguait ce boulet de compatibilité avec cet espèce
| d'assembleur amélioré qu'on appelle C.

Pour quoi faire après ?


Une première tentative de programmation objet ?
Je commence à comprendre, par ailleurs, ton insistance
sur la sémantique. Mais est-ce une raison pour ne pas nettoyer
de la syntaxe des outils permettant de faire des choses coupables ?
Moi je n'attends pas d'un langage qu'il se complique à l'infini en
ajoutant des couches successives, comme les règlements d'une
administration. Si on me déconseille vivement l'usage d'une tournure,
d'un type, etc, j'ai envie que le langage m'interdise, à terme, de les
utiliser - et ceci d'autant plus que les auteurs de l'interdiction ont plus
de bon sens ;-) Je comprends mal une exigence de compatibilité avec
un existant jugé mauvais. C'est un argument que j'ai rencontré il y a
longtemps chez les Fortranphiles pour refuser le passage à C puis
à C++ (aujourd'hui je crois que, tout de même, bien des choses ont
évolué, mais il doit bien trainer encore quelques if ... 23, 24, 25 dans
certaines chaumières)

--

Français *==> "Musique renaissance" <==* English
midi - facsimiles - ligatures - mensuration
http://anaigeon.free.fr | http://www.medieval.org/emfaq/anaigeon/
Alain Naigeon - - Strasbourg, France

Avatar
Gabriel Dos Reis
"Alain Naigeon" writes:

| "Gabriel Dos Reis" a écrit dans le message
| news:
| > "Alain Naigeon" writes:
| >
| > | > Beaucoup de gens considèrent en effet qu'il s'agit d'une entorse à
| > | > l'abstraction de type et à la modélisation objet (y'a qu'à voir le
| > | > troll que cette question vient - une fois de plus - de déclencher). On
| > | > peut considérer cela comme une concession à la pratique existante et à
| > | > l'utilisabilité de vector, personnellement ce ne me choque pas du
| > | > tout.
| > |
| > | Je respecte ton choix, entre le pour et le contre !
| > | Pour moi C++ serait bien plus séduisant et sûr s'il
| > | larguait ce boulet de compatibilité avec cet espèce
| > | d'assembleur amélioré qu'on appelle C.
| >
| > Pour quoi faire après ?
|
| Une première tentative de programmation objet ?

Le contre-argument principal est que C++ n'est pas un langage orienté
objet, mais un langage qui supporte plusieurs paradigmes. Il est
important que C++ continue à supporter plusieurs paradigmes parce
qu'il n'y a pas qu'Une Seule Vraie Manière de programmer.
Contrairement à ce que tu aurais pu entendre ailleurs, le monde n'est
pas orienté objet.

| Je commence à comprendre, par ailleurs, ton insistance
| sur la sémantique. Mais est-ce une raison pour ne pas nettoyer
| de la syntaxe des outils permettant de faire des choses coupables ?

Tu n'aimes pas les citations des gens célèbres, mais la meilleure
réponse que je peux te donner c'est de regarder « the Design and
Evolution of C++ », chapitre 3 (si j'ai bonne mémoire) vers la fin,
sur la syntaxe et le résultat de diverses tentatives.

Cela étant dit, les gens n'ont pas baissé les bras. Il est possible
que la prochaine révision de C++ contiennent des simplifications de
syntaxe (cela ne veut pas dire que les anciennes seront bannies).
Des gens y travaillent.

| Moi je n'attends pas d'un langage qu'il se complique à l'infini en
| ajoutant des couches successives, comme les règlements d'une
| administration.

et pourtant c'est le sort des langages évolutifs. À moins bien sûr de
décider à chaque révision de faire table rase du passé. C'est possible
mais le résultat est souvent désastreux.

| Si on me déconseille vivement l'usage d'une tournure,
| d'un type, etc, j'ai envie que le langage m'interdise, à terme, de les
| utiliser - et ceci d'autant plus que les auteurs de l'interdiction ont plus
| de bon sens ;-) Je comprends mal une exigence de compatibilité avec
| un existant jugé mauvais.

Attention : je n'ai jamais entendu les acteurs actifs de l'évolution
de C++ dire que C est mauvais. Au contraire, j'ai souvent vu que la
question de compatibilité avec le C a toujours été prise très au sérieux.

| C'est un argument que j'ai rencontré il y a
| longtemps chez les Fortranphiles pour refuser le passage à C puis
| à C++ (aujourd'hui je crois que, tout de même, bien des choses ont
| évolué, mais il doit bien trainer encore quelques if ... 23, 24, 25 dans
| certaines chaumières)

Je comprends. Mais personnellement, je ne pretends pas que le C est
mauvais. Pour accepter une incompatibilité, il me faut des arguments,
disons, plus raisonnés ;-)

-- Gaby
Avatar
Arnaud Meurgues
Alain Naigeon wrote:

Juste ceci : le procès d'intention peut se produire quand on entend
les propos de l'autre à la lumière de ses propres idées, sans pouvoir
s'en abstraire.


Le procès d'intention, c'est juger des intentions de quelqu'un, lui
prêter des desseins. Ça peut être à partir de propos, mais aussi d'actes.

C'est une faute intellectuelle (encourue par chacun
de nous). La diffamation c'est une intention de nuire, c'est très
différent !


Si ça n'avait pas été différent, je ne les aurais pas considérés comme
une alternative.

Arnaud

Avatar
adebaene
"Alain Naigeon" wrote in message news:<3f145a08$0$26591$...
"Arnaud Debaene" a écrit dans le message news:


"Alain Naigeon" wrote in message
news:<3f107896$0$10882$...


De mon point de vue, la compatibilité de std::vector avec des
interfaces "C" du type read (Posix) est une justification suffisante.


Cela dépend du prix à payer...
??? Quel "prix"? En quoi cette obligation de continuité de pénalise

t'elle dans ton abstraction si tu n'en tiens pas compte?
Au passage, utiliser une implémentation contigue est à ma connaissance
la seule façon de garantir les "requirements" (traduction?) de vector
en ce qui concerne les performances, à savoir accès en temps constant,
recherche en O(N), ....

Beaucoup de gens considèrent en effet qu'il s'agit d'une entorse à
l'abstraction de type et à la modélisation objet (y'a qu'à voir le
troll que cette question vient - une fois de plus - de déclencher). On
peut considérer cela comme une concession à la pratique existante et à
l'utilisabilité de vector, personnellement ce ne me choque pas du
tout.


Je respecte ton choix, entre le pour et le contre !
Pour moi C++ serait bien plus séduisant et sûr s'il
larguait ce boulet de compatibilité avec cet espèce
d'assembleur amélioré qu'on appelle C.


Ca c'est ton point de vue de programmeur objet dans un monde idéal et
parfait. Dans la réalité, il est certain que C++ ne connaitrait pas le
succès qu'il a aujourd'hui sans la compatibilité avec le C.
C'est justement la force du C++ d'être multi-paradigme et de permettre
aussi bien de faire des abstractions objet de haut-niveau que de
s'interfacer nativement avec le système ou de bidouiller des registres
hardware à la main.


D'un autre côté je me demande moi-même comment
représenter une telle propriété... après tout, cela concerne
en premier lieu *l'implémentation* d'un itérateur sur cette
classe, mais à partir du moment où l'utilisateur peut avoir
accès au "prochain" élément, en quoi cela l'intéresse-t-il
de savoir où il se trouve par rapport au précédent ?
Tout simplement parce qu'on peut vouloir accéder aux éléments du

vector autrement que par un itérateur. L'interface de vector propose
at et operator[].


Ben oui mais si on parle d'interface et non d'implémentation,
ni at ni operateur[] ne représentent une contiguïté, qui ne peut
de toute façon être exprimée avec un seul indice.


Voir la remarque de Gaby : int toto[5]; Rien n'indique la contiguité,
pourtant tu pars bien du principe qu'elle existe.

Arnaud



Avatar
Arnaud Meurgues
Alain Naigeon wrote:

Une première tentative de programmation objet ?


Pourquoi alors être parti du C (with classes) ? Il y a smalltalk pour
ça, non ?

administration. Si on me déconseille vivement l'usage d'une tournure,
d'un type, etc, j'ai envie que le langage m'interdise, à terme, de les
utiliser - et ceci d'autant plus que les auteurs de l'interdiction ont plus
de bon sens ;-)


Et l'on se rapproche du Pascal qui interdit ce qui est jugé mauvais par
le concepteur du langage.

Je comprends mal une exigence de compatibilité avec
un existant jugé mauvais.


Outre le fait que C n'est pas aussi mauvais qu'on le dit (sinon, il
deviendrait difficile d'expliquer son succès), il ne faut pas perdre de
vue que les considérations de Stroustrup sont éminemment pragmatiques.
Il n'est pas partie de zéro. Il n'a pas fait Eiffel ou Smalltalk. Il est
parti de C car il lui reconnaissait des qualités (notamment sa notoriété).
Cet héritage pèse fortement sur l'évolution du C++ mais ne l'handicape
pas autant que tu sembles le penser. C'est aussi grâce à lui que le C++
a connu l'essort qu'on lui connaît et que des langages peut-être plus
cohérents et "purs" comme Ada ou Eiffel n'ont pu égaler (et Ada a
pourtant été promu par le Dod).

Tu sembles considérer qu'il est maintenant temps de couper le cordon. Ce
n'est pas forcément une décision pragmatique car les intéractions C/C++
sont encore fréquentes et le C est loin d'être mort.

Arnaud

Avatar
kanze
Arnaud Meurgues wrote in message
news:<3f1420b2$0$25195$...
Gabriel Dos Reis wrote:

Et puis, de toute façon quelque source qu'on puisse citer, James
niera.


Puisque j'essaye de suivre le débat, puis-je exposer la compréhension
que j'en ai afin d'être certain de n'avoir rien raté ?

Selon James, personne n'a pensé explicitement, avant l'adoption
définitive de la norme, que la mémoire d'un std::vector devait être
contigüe et pas autrement.


Plus exactement, que personne n'a pensé explicitement que la contiguïté
fasse partie de l'interface contractuelle. Les implémentations d'avant
la norme était bien contiguë.

C'est en tout cas une façon d'interprêter ses propos. Si c'est bien
ça qu'il veut dire, effectivement, c'est de la diffamation ou, en tout
cas, du procès d'intention (au sens propre). C'est je crois ce qui est
choquant dans les propos de James.


Et moi, je ne vois pas ce qu'il y a de diffamant à dire qu'on n'y avait
pas pensé. C'est tout. On ne pense jamais à tout.

Mais j'ai l'impression qu'il y a une autre interprétation, peut-être
plus proche de ce qu'il veut dire, mais moins choquante. C'est de
comprendre que le comité, en tant que groupe d'humain, a eu
l'intention que la mémoire des std::vector soit contigüe. En ce cas,
celà signifierait que cette intention devait êtret connue et partagée
de tous les membres du comité, ce qui n'est évidemment pas vrai (James
étant un contre-exemple). Mais James semble tout de même dénier les
intentions explicites si celles-ci n'ont pas eu de manifestation
publique (et il est vrai que si personne d'exprime ses intentions, on
ne peut prouver qu'elles ont existé).


Je n'ai jusqu'ici aucune raison à croire que qui que ce soit ait
réelement eu une « intention » explicite. Même dans les propos de
Stroustrup que j'ai lu, à l'époque, il disait plutôt quelque chose du
genre « il ne m'était pas venu à l'ésprit que la mémoire pouvait ne pas
être contiguë », ou quelque chose du genre. Enfin, d'après mes
souvenirs. Parce que je n'y ai pas prété beaucoup d'attention -- ce
qu'il a pu pensé avant n'avait pas vraiment d'importance, dans la mésure
qu'il ne l'a pas dit ou écrit quelque part.

Et je continue à penser que c'est le cas. Je ne comprends pas toute
cette histoire de « diffamation ». On n'y a pas pensé. Ou au moins, si
on y avait pensé, on n'en a pas laissé des traces, ce qui revient au
fond au même. Et c'est tout. Où en est la honte ?

Par la suite, il s'avérait qu'on aurait dû y penser. Ce sont des choses
qui arrivent. On l'a donc fait la correction. Et pour faire bien, on en
a couché la motivation en termes pour faire plaisir à ISO. Chose qui me
semble aussi tout à fait normale.

--
James Kanze GABI Software mailto:
Conseils en informatique orientée objet/ http://www.gabi-soft.fr
Beratung in objektorientierter Datenverarbeitung
11 rue de Rambouillet, 78460 Chevreuse, France, +33 (0)1 30 23 45 16


Avatar
Julien Blanc
Arnaud Debaene wrote:
"Alain Naigeon" wrote in message news:<3f145a08$0$26591$...

"Arnaud Debaene" a écrit dans le message news:



"Alain Naigeon" wrote in message


news:<3f107896$0$10882$...

De mon point de vue, la compatibilité de std::vector avec des
interfaces "C" du type read (Posix) est une justification suffisante.


Cela dépend du prix à payer...


??? Quel "prix"? En quoi cette obligation de continuité de pénalise
t'elle dans ton abstraction si tu n'en tiens pas compte?
Au passage, utiliser une implémentation contigue est à ma connaissance
la seule façon de garantir les "requirements" (traduction?) de vector
en ce qui concerne les performances, à savoir accès en temps constant,
recherche en O(N), ....


ça c'est faux, il suffit d'avoir ce qu'on pourrait appeler une
"pseudo-contiguité" (ie il existe une fonction f(i) de complexité
constante qui pour l'indice i renvoie l'adresse de la cellule, et une
fonction g(i) qui renvoie l'adresse du successeur de la cellule d'indice
i). C'est assez facile à faire avec par exemple une représentation de ce
type :

X.X.X.X.X.X.

au lieu de

XXXXXX......

La première n'est pas contigüe, mais peut satisfaire aux contraintes de
performance de vector au même titre que la deuxième (même si son intérêt
est plus que douteux pour un container généraliste).

Je respecte ton choix, entre le pour et le contre !
Pour moi C++ serait bien plus séduisant et sûr s'il
larguait ce boulet de compatibilité avec cet espèce
d'assembleur amélioré qu'on appelle C.



Ca c'est ton point de vue de programmeur objet dans un monde idéal et
parfait. Dans la réalité, il est certain que C++ ne connaitrait pas le
succès qu'il a aujourd'hui sans la compatibilité avec le C.
C'est justement la force du C++ d'être multi-paradigme et de permettre
aussi bien de faire des abstractions objet de haut-niveau que de
s'interfacer nativement avec le système ou de bidouiller des registres
hardware à la main.


ça c'est un autre débat :). Ceci dit, je pense que si on n'a pas besoin
de la compatibilité C, alors on a tout intérêt à utiliser autre chose
que C++.

Ben oui mais si on parle d'interface et non d'implémentation,
ni at ni operateur[] ne représentent une contiguïté, qui ne peut
de toute façon être exprimée avec un seul indice.


Voir la remarque de Gaby : int toto[5]; Rien n'indique la contiguité,
pourtant tu pars bien du principe qu'elle existe.


la contiguité est indiquée par la sémantique de ton opérateur []. Et ça,
c'est dans la norme C et aussi celle de C++, ou alors il faut jeter tous
les bouquins que j'ai lu sur les deux langages. Visiblement, elle l'est
aussi pour vector<T>, mais là, ce n'était pas dans la spécification
*initiale* de vector.

Si j'ai bien suivi ce qu'ont dit Gaby et James, on a :

- Gaby qui dit que il était évident pour tous les membres du comité que
vector devait avoir une représentation contigüe
- James qui soutient qu'il n'était pas *au départ* évident pour tout le
monde que seule une représentation contigüe pouvait convenir pour vector
et qu'il faille bannir toute autre, même si cette position s'est ensuite
imposée au vu de l'existant.

La querelle pour savoir lequel des deux a raison ne m'intéresse guère,
la seule chose qui m'intéresse effectivement, c'est de savoir si :

- il est établi dans la norme *actuelle* que vector *doit* utiliser une
représentation contigüe (il semblerait que ce soit oui)
- cela est le cas dans toutes les implémentations (là aussi, il
semblerait que ce soit oui)

--
Julien Blanc. Equipe cadp. VERIMAG. Grenoble. France.