suite au post de JM, je voulais savoir si vector *doit* faire
le cycle copie/destruction en cas de déplacement de la zone
mémoire suite à un agrandissement.
D'après le code expérimenté par JM, c'est le cas. Mais je
voudrais savoir si (et pourquoi) le vector ne peut pas
simplement faire un (pseudo) realloc, ie demander
de la mémoire brute, plus grande, et faire une copie
bit à bit des objets dejà stockés ?
suite au post de JM, je voulais savoir si vector *doit* faire
le cycle copie/destruction en cas de déplacement de la zone
mémoire suite à un agrandissement.
D'après le code expérimenté par JM, c'est le cas. Mais je
voudrais savoir si (et pourquoi) le vector ne peut pas
simplement faire un (pseudo) realloc, ie demander
de la mémoire brute, plus grande, et faire une copie
bit à bit des objets dejà stockés ?
suite au post de JM, je voulais savoir si vector *doit* faire
le cycle copie/destruction en cas de déplacement de la zone
mémoire suite à un agrandissement.
D'après le code expérimenté par JM, c'est le cas. Mais je
voudrais savoir si (et pourquoi) le vector ne peut pas
simplement faire un (pseudo) realloc, ie demander
de la mémoire brute, plus grande, et faire une copie
bit à bit des objets dejà stockés ?
suite au post de JM, je voulais savoir si vector *doit* faire
le cycle copie/destruction en cas de déplacement de la zone
mémoire suite à un agrandissement.
suite au post de JM, je voulais savoir si vector *doit* faire
le cycle copie/destruction en cas de déplacement de la zone
mémoire suite à un agrandissement.
suite au post de JM, je voulais savoir si vector *doit* faire
le cycle copie/destruction en cas de déplacement de la zone
mémoire suite à un agrandissement.
je voulais savoir si vector *doit* faire
le cycle copie/destruction en cas de déplacement de la zone
mémoire suite à un agrandissement.
je voulais savoir si vector *doit* faire
le cycle copie/destruction en cas de déplacement de la zone
mémoire suite à un agrandissement.
je voulais savoir si vector *doit* faire
le cycle copie/destruction en cas de déplacement de la zone
mémoire suite à un agrandissement.
suite au post de JM, je voulais savoir si vector *doit* faire
le cycle copie/destruction en cas de déplacement de la zone
mémoire suite à un agrandissement.
Il doit le faire chaque fois qu'il a besoin d'agrandir la
capacité. Ce qui ne peut pas être à chaque push_back ; la norme
dit que push_back a une complexité amortie constante, ce qui
impose un algorithme exponentiel de croissance. (Selon
l'implémentation, typiquement, chaque fois que la capacité ne
suffit pas, il va la multiplier par 1,5 ou par 2 -- si je ne me
trompe pas, Stepanov utilisait 2, mais Andy Koenig a démontré
qu'avec un multiplicateur supérieur à sqrt(2), on ne pouvvait
jamais réutiliser la mémoire libérée.)
Si on connaît la taille finale, évidemment, rien n'empèche de
fair un coup de reserve au préalable, pour être sûr qu'il n'y a
pas de réallocation (avec les copies supplémentaires que cela
implique). Ça a aussi l'avantage que les insertions n'invalident
pas des itérateurs.
D'après le code expérimenté par JM, c'est le cas. Mais je
voudrais savoir si (et pourquoi) le vector ne peut pas
simplement faire un (pseudo) realloc, ie demander
de la mémoire brute, plus grande, et faire une copie
bit à bit des objets dejà stockés ?
D'abord, c'est intérdit avec l'allocator standard ; la norme
dit que cet allocator utilise la fonction ::operator new pour
obtenir de la mémoire (et si je remplace cette fonction, c'est
bien visible s'il le fait ou non).
Mais plus fondamentalement, le problème, c'est comment ? Il ne
peut pas faire un realloc tout court, parce que si realloc
déplace le bloc (chose qu'il fait souvent), on se retrouve
éventuellement avec des objets invalids.
suite au post de JM, je voulais savoir si vector *doit* faire
le cycle copie/destruction en cas de déplacement de la zone
mémoire suite à un agrandissement.
Il doit le faire chaque fois qu'il a besoin d'agrandir la
capacité. Ce qui ne peut pas être à chaque push_back ; la norme
dit que push_back a une complexité amortie constante, ce qui
impose un algorithme exponentiel de croissance. (Selon
l'implémentation, typiquement, chaque fois que la capacité ne
suffit pas, il va la multiplier par 1,5 ou par 2 -- si je ne me
trompe pas, Stepanov utilisait 2, mais Andy Koenig a démontré
qu'avec un multiplicateur supérieur à sqrt(2), on ne pouvvait
jamais réutiliser la mémoire libérée.)
Si on connaît la taille finale, évidemment, rien n'empèche de
fair un coup de reserve au préalable, pour être sûr qu'il n'y a
pas de réallocation (avec les copies supplémentaires que cela
implique). Ça a aussi l'avantage que les insertions n'invalident
pas des itérateurs.
D'après le code expérimenté par JM, c'est le cas. Mais je
voudrais savoir si (et pourquoi) le vector ne peut pas
simplement faire un (pseudo) realloc, ie demander
de la mémoire brute, plus grande, et faire une copie
bit à bit des objets dejà stockés ?
D'abord, c'est intérdit avec l'allocator standard ; la norme
dit que cet allocator utilise la fonction ::operator new pour
obtenir de la mémoire (et si je remplace cette fonction, c'est
bien visible s'il le fait ou non).
Mais plus fondamentalement, le problème, c'est comment ? Il ne
peut pas faire un realloc tout court, parce que si realloc
déplace le bloc (chose qu'il fait souvent), on se retrouve
éventuellement avec des objets invalids.
suite au post de JM, je voulais savoir si vector *doit* faire
le cycle copie/destruction en cas de déplacement de la zone
mémoire suite à un agrandissement.
Il doit le faire chaque fois qu'il a besoin d'agrandir la
capacité. Ce qui ne peut pas être à chaque push_back ; la norme
dit que push_back a une complexité amortie constante, ce qui
impose un algorithme exponentiel de croissance. (Selon
l'implémentation, typiquement, chaque fois que la capacité ne
suffit pas, il va la multiplier par 1,5 ou par 2 -- si je ne me
trompe pas, Stepanov utilisait 2, mais Andy Koenig a démontré
qu'avec un multiplicateur supérieur à sqrt(2), on ne pouvvait
jamais réutiliser la mémoire libérée.)
Si on connaît la taille finale, évidemment, rien n'empèche de
fair un coup de reserve au préalable, pour être sûr qu'il n'y a
pas de réallocation (avec les copies supplémentaires que cela
implique). Ça a aussi l'avantage que les insertions n'invalident
pas des itérateurs.
D'après le code expérimenté par JM, c'est le cas. Mais je
voudrais savoir si (et pourquoi) le vector ne peut pas
simplement faire un (pseudo) realloc, ie demander
de la mémoire brute, plus grande, et faire une copie
bit à bit des objets dejà stockés ?
D'abord, c'est intérdit avec l'allocator standard ; la norme
dit que cet allocator utilise la fonction ::operator new pour
obtenir de la mémoire (et si je remplace cette fonction, c'est
bien visible s'il le fait ou non).
Mais plus fondamentalement, le problème, c'est comment ? Il ne
peut pas faire un realloc tout court, parce que si realloc
déplace le bloc (chose qu'il fait souvent), on se retrouve
éventuellement avec des objets invalids.
On Wed, 20 Sep 2006 08:01:59 +0000 (UTC), Marc Boyer :je voulais savoir si vector *doit* faire
le cycle copie/destruction en cas de déplacement de la zone
mémoire suite à un agrandissement.
Ben oui, faut bien, car vector<> ne connaît pas le contenu de la
classe.
struct C
{
int x;
int *ptr;
C() : ptr (&x) {}
};
On Wed, 20 Sep 2006 08:01:59 +0000 (UTC), Marc Boyer :
je voulais savoir si vector *doit* faire
le cycle copie/destruction en cas de déplacement de la zone
mémoire suite à un agrandissement.
Ben oui, faut bien, car vector<> ne connaît pas le contenu de la
classe.
struct C
{
int x;
int *ptr;
C() : ptr (&x) {}
};
On Wed, 20 Sep 2006 08:01:59 +0000 (UTC), Marc Boyer :je voulais savoir si vector *doit* faire
le cycle copie/destruction en cas de déplacement de la zone
mémoire suite à un agrandissement.
Ben oui, faut bien, car vector<> ne connaît pas le contenu de la
classe.
struct C
{
int x;
int *ptr;
C() : ptr (&x) {}
};
Tu as une ref sous la main pour le coup du coef supérieur
à sqrt(2) ? (sinon, je vais chercher tout seul).
Mais pourquoi un objet peut-il devenir invalide en étant déplacé ?
S'il possède des pointeurs sur lui même ?
Tu as une ref sous la main pour le coup du coef supérieur
à sqrt(2) ? (sinon, je vais chercher tout seul).
Mais pourquoi un objet peut-il devenir invalide en étant déplacé ?
S'il possède des pointeurs sur lui même ?
Tu as une ref sous la main pour le coup du coef supérieur
à sqrt(2) ? (sinon, je vais chercher tout seul).
Mais pourquoi un objet peut-il devenir invalide en étant déplacé ?
S'il possède des pointeurs sur lui même ?
Oui, une classe qui pointe sur/dans elle même.
Je ne vois pas trop l'intérêt
Oui, une classe qui pointe sur/dans elle même.
Je ne vois pas trop l'intérêt
Oui, une classe qui pointe sur/dans elle même.
Je ne vois pas trop l'intérêt
suite au post de JM, je voulais savoir si vector *doit* faire
le cycle copie/destruction en cas de déplacement de la zone
mémoire suite à un agrandissement.
Il doit le faire chaque fois qu'il a besoin d'agrandir la
capacité. Ce qui ne peut pas être à chaque push_back ; la norme
dit que push_back a une complexité amortie constante, ce qui
impose un algorithme exponentiel de croissance. (Selon
l'implémentation, typiquement, chaque fois que la capacité ne
suffit pas, il va la multiplier par 1,5 ou par 2 -- si je ne me
trompe pas, Stepanov utilisait 2, mais Andy Koenig a démontré
qu'avec un multiplicateur supérieur à sqrt(2), on ne pouvvait
jamais réutiliser la mémoire libérée.)
Tu as une ref sous la main pour le coup du coef supérieur
à sqrt(2) ? (sinon, je vais chercher tout seul).
Si on connaît la taille finale, évidemment, rien n'empèche de
fair un coup de reserve au préalable, pour être sûr qu'il n'y a
pas de réallocation (avec les copies supplémentaires que cela
implique). Ça a aussi l'avantage que les insertions n'invalident
pas des itérateurs.
ouiD'après le code expérimenté par JM, c'est le cas. Mais je
voudrais savoir si (et pourquoi) le vector ne peut pas
simplement faire un (pseudo) realloc, ie demander
de la mémoire brute, plus grande, et faire une copie
bit à bit des objets dejà stockés ?
D'abord, c'est intérdit avec l'allocator standard ; la norme
dit que cet allocator utilise la fonction ::operator new pour
obtenir de la mémoire (et si je remplace cette fonction, c'est
bien visible s'il le fait ou non).
Mais plus fondamentalement, le problème, c'est comment ? Il ne
peut pas faire un realloc tout court, parce que si realloc
déplace le bloc (chose qu'il fait souvent), on se retrouve
éventuellement avec des objets invalids.
Mais pourquoi un objet peut-il devenir invalide en
étant déplacé ? S'il possède des pointeurs sur lui même ?
suite au post de JM, je voulais savoir si vector *doit* faire
le cycle copie/destruction en cas de déplacement de la zone
mémoire suite à un agrandissement.
Il doit le faire chaque fois qu'il a besoin d'agrandir la
capacité. Ce qui ne peut pas être à chaque push_back ; la norme
dit que push_back a une complexité amortie constante, ce qui
impose un algorithme exponentiel de croissance. (Selon
l'implémentation, typiquement, chaque fois que la capacité ne
suffit pas, il va la multiplier par 1,5 ou par 2 -- si je ne me
trompe pas, Stepanov utilisait 2, mais Andy Koenig a démontré
qu'avec un multiplicateur supérieur à sqrt(2), on ne pouvvait
jamais réutiliser la mémoire libérée.)
Tu as une ref sous la main pour le coup du coef supérieur
à sqrt(2) ? (sinon, je vais chercher tout seul).
Si on connaît la taille finale, évidemment, rien n'empèche de
fair un coup de reserve au préalable, pour être sûr qu'il n'y a
pas de réallocation (avec les copies supplémentaires que cela
implique). Ça a aussi l'avantage que les insertions n'invalident
pas des itérateurs.
oui
D'après le code expérimenté par JM, c'est le cas. Mais je
voudrais savoir si (et pourquoi) le vector ne peut pas
simplement faire un (pseudo) realloc, ie demander
de la mémoire brute, plus grande, et faire une copie
bit à bit des objets dejà stockés ?
D'abord, c'est intérdit avec l'allocator standard ; la norme
dit que cet allocator utilise la fonction ::operator new pour
obtenir de la mémoire (et si je remplace cette fonction, c'est
bien visible s'il le fait ou non).
Mais plus fondamentalement, le problème, c'est comment ? Il ne
peut pas faire un realloc tout court, parce que si realloc
déplace le bloc (chose qu'il fait souvent), on se retrouve
éventuellement avec des objets invalids.
Mais pourquoi un objet peut-il devenir invalide en
étant déplacé ? S'il possède des pointeurs sur lui même ?
suite au post de JM, je voulais savoir si vector *doit* faire
le cycle copie/destruction en cas de déplacement de la zone
mémoire suite à un agrandissement.
Il doit le faire chaque fois qu'il a besoin d'agrandir la
capacité. Ce qui ne peut pas être à chaque push_back ; la norme
dit que push_back a une complexité amortie constante, ce qui
impose un algorithme exponentiel de croissance. (Selon
l'implémentation, typiquement, chaque fois que la capacité ne
suffit pas, il va la multiplier par 1,5 ou par 2 -- si je ne me
trompe pas, Stepanov utilisait 2, mais Andy Koenig a démontré
qu'avec un multiplicateur supérieur à sqrt(2), on ne pouvvait
jamais réutiliser la mémoire libérée.)
Tu as une ref sous la main pour le coup du coef supérieur
à sqrt(2) ? (sinon, je vais chercher tout seul).
Si on connaît la taille finale, évidemment, rien n'empèche de
fair un coup de reserve au préalable, pour être sûr qu'il n'y a
pas de réallocation (avec les copies supplémentaires que cela
implique). Ça a aussi l'avantage que les insertions n'invalident
pas des itérateurs.
ouiD'après le code expérimenté par JM, c'est le cas. Mais je
voudrais savoir si (et pourquoi) le vector ne peut pas
simplement faire un (pseudo) realloc, ie demander
de la mémoire brute, plus grande, et faire une copie
bit à bit des objets dejà stockés ?
D'abord, c'est intérdit avec l'allocator standard ; la norme
dit que cet allocator utilise la fonction ::operator new pour
obtenir de la mémoire (et si je remplace cette fonction, c'est
bien visible s'il le fait ou non).
Mais plus fondamentalement, le problème, c'est comment ? Il ne
peut pas faire un realloc tout court, parce que si realloc
déplace le bloc (chose qu'il fait souvent), on se retrouve
éventuellement avec des objets invalids.
Mais pourquoi un objet peut-il devenir invalide en
étant déplacé ? S'il possède des pointeurs sur lui même ?
Marc Boyer writes:Tu as une ref sous la main pour le coup du coef supérieur
à sqrt(2) ? (sinon, je vais chercher tout seul).
J'avais en mémoire le nombre d'or. Il faut que ce qui a été
libéré est supérieur en taille à ce qu'il faut allouer. Donc
sum_{i=0}^{N} x^i > x^{N+2}
over{x^{N+1}-1}{x-1} > x^{N+2}
x^{N+1}-1 > x^{N+3} - x^{N+2}
x^{N+2}+x^{N+1} > x^{N+3}-1
Vu la forme (ça fait penser à la suite de Fibonacci et la
limite de 2 termes successifs de cette suite, c'est le nombre
d'or), le nombre d'or me semble un meilleur candidat que
racine de 2, mais je ne vois plus comment conclure
formellement.
Mais pourquoi un objet peut-il devenir invalide en étant déplac é ?
S'il possède des pointeurs sur lui même ?
Par exemple, ou s'il est enregistré quelque part.
Marc Boyer <Marc.Boyer@enseeiht.yahoo.fr.invalid> writes:
Tu as une ref sous la main pour le coup du coef supérieur
à sqrt(2) ? (sinon, je vais chercher tout seul).
J'avais en mémoire le nombre d'or. Il faut que ce qui a été
libéré est supérieur en taille à ce qu'il faut allouer. Donc
sum_{i=0}^{N} x^i > x^{N+2}
over{x^{N+1}-1}{x-1} > x^{N+2}
x^{N+1}-1 > x^{N+3} - x^{N+2}
x^{N+2}+x^{N+1} > x^{N+3}-1
Vu la forme (ça fait penser à la suite de Fibonacci et la
limite de 2 termes successifs de cette suite, c'est le nombre
d'or), le nombre d'or me semble un meilleur candidat que
racine de 2, mais je ne vois plus comment conclure
formellement.
Mais pourquoi un objet peut-il devenir invalide en étant déplac é ?
S'il possède des pointeurs sur lui même ?
Par exemple, ou s'il est enregistré quelque part.
Marc Boyer writes:Tu as une ref sous la main pour le coup du coef supérieur
à sqrt(2) ? (sinon, je vais chercher tout seul).
J'avais en mémoire le nombre d'or. Il faut que ce qui a été
libéré est supérieur en taille à ce qu'il faut allouer. Donc
sum_{i=0}^{N} x^i > x^{N+2}
over{x^{N+1}-1}{x-1} > x^{N+2}
x^{N+1}-1 > x^{N+3} - x^{N+2}
x^{N+2}+x^{N+1} > x^{N+3}-1
Vu la forme (ça fait penser à la suite de Fibonacci et la
limite de 2 termes successifs de cette suite, c'est le nombre
d'or), le nombre d'or me semble un meilleur candidat que
racine de 2, mais je ne vois plus comment conclure
formellement.
Mais pourquoi un objet peut-il devenir invalide en étant déplac é ?
S'il possède des pointeurs sur lui même ?
Par exemple, ou s'il est enregistré quelque part.
On Wed, 20 Sep 2006 08:01:59 +0000 (UTC), Marc Boyer :je voulais savoir si vector *doit* faire
le cycle copie/destruction en cas de déplacement de la zone
mémoire suite à un agrandissement.
Ben oui, faut bien, car vector<> ne connaît pas le contenu de la
classe.
struct C
{
int x;
int *ptr;
C() : ptr (&x) {}
};
Oui, une classe qui pointe sur/dans elle même.
Je ne vois pas trop l'intérêt, mais il faut le
permettre.
On Wed, 20 Sep 2006 08:01:59 +0000 (UTC), Marc Boyer :
je voulais savoir si vector *doit* faire
le cycle copie/destruction en cas de déplacement de la zone
mémoire suite à un agrandissement.
Ben oui, faut bien, car vector<> ne connaît pas le contenu de la
classe.
struct C
{
int x;
int *ptr;
C() : ptr (&x) {}
};
Oui, une classe qui pointe sur/dans elle même.
Je ne vois pas trop l'intérêt, mais il faut le
permettre.
On Wed, 20 Sep 2006 08:01:59 +0000 (UTC), Marc Boyer :je voulais savoir si vector *doit* faire
le cycle copie/destruction en cas de déplacement de la zone
mémoire suite à un agrandissement.
Ben oui, faut bien, car vector<> ne connaît pas le contenu de la
classe.
struct C
{
int x;
int *ptr;
C() : ptr (&x) {}
};
Oui, une classe qui pointe sur/dans elle même.
Je ne vois pas trop l'intérêt, mais il faut le
permettre.