j'ai quelque expérience en C++ et avec les templates mais n'ai
jamais utilisé la STL et, ayant un projet en vue, je
m'interresse à l'intérêt que peux m'apporter cette
bibliothèque. J'ai donc récupéré une implémentation libre de
cette dernière afin de comprendre ce qui se passait en
coulisse. Il m'est alors venu une série de questions que je
vous soumets :
j'ai tout d'abord inspecté rapidement le modèle "vector" :
corrigez moi si je me trompe.
il semble que l'ajout (push_back) d'un objet provoque une
réallocation de l'ensemble du tableau. Dispendieux au niveau
temps ?
il est possible de réserver à l'avance un espace pour eviter
cet inconvénient, mais la aussi cela implique d'initialiser
cet espace (encore dispendieux).
je pense alors que pour avoir des conteneurs efficaces, il est
nécessaire au moins de dériver ces conteneurs de base. Mais
la aussi je me heurte à quelques problèmes : supposons tout
simplement que je veuille créer un conteneur tableau trié
d'objets (et qui le restent lors d'ajouts). une insertion
efficace se fait via une recherche dichotomique : j'ai trouvé
binary_search mais celui ci ne renvoie pas d'iterateur (?). la
methode "find" quant à elle ne peut pas faire une recherche
dichotomique étant donné que le tableau n'est pas sensé être
trié (??)
j'ai entendu dire également que cette bibliothèque était
"thread-safe" or je n'ai vu aucun code de synchronisation dans
le source de la bibliothèque récupéré (??)
je me suis posé également la question de création de
conteneurs indirects par ex un conteneur de pointeurs
d'objets : lors de la suppression par "erase", la suppression
ne doit effacer que le pointeur et non l'objet sur lequel il
pointe,
d'ou la neccessité de créer une fonction dérivée afin
de réaliser les choses correctement, n'est-ce pas ?
bref je me pose la question de l'utilité de cette bibliothèque
dans le cadre d'un développement dont le temps de traitement
est un facteur déterminant.
j'ai quelque expérience en C++ et avec les templates mais n'ai
jamais utilisé la STL et, ayant un projet en vue, je
m'interresse à l'intérêt que peux m'apporter cette
bibliothèque. J'ai donc récupéré une implémentation libre de
cette dernière afin de comprendre ce qui se passait en
coulisse. Il m'est alors venu une série de questions que je
vous soumets :
j'ai tout d'abord inspecté rapidement le modèle "vector" :
corrigez moi si je me trompe.
il semble que l'ajout (push_back) d'un objet provoque une
réallocation de l'ensemble du tableau. Dispendieux au niveau
temps ?
il est possible de réserver à l'avance un espace pour eviter
cet inconvénient, mais la aussi cela implique d'initialiser
cet espace (encore dispendieux).
je pense alors que pour avoir des conteneurs efficaces, il est
nécessaire au moins de dériver ces conteneurs de base. Mais
la aussi je me heurte à quelques problèmes : supposons tout
simplement que je veuille créer un conteneur tableau trié
d'objets (et qui le restent lors d'ajouts). une insertion
efficace se fait via une recherche dichotomique : j'ai trouvé
binary_search mais celui ci ne renvoie pas d'iterateur (?). la
methode "find" quant à elle ne peut pas faire une recherche
dichotomique étant donné que le tableau n'est pas sensé être
trié (??)
j'ai entendu dire également que cette bibliothèque était
"thread-safe" or je n'ai vu aucun code de synchronisation dans
le source de la bibliothèque récupéré (??)
je me suis posé également la question de création de
conteneurs indirects par ex un conteneur de pointeurs
d'objets : lors de la suppression par "erase", la suppression
ne doit effacer que le pointeur et non l'objet sur lequel il
pointe,
d'ou la neccessité de créer une fonction dérivée afin
de réaliser les choses correctement, n'est-ce pas ?
bref je me pose la question de l'utilité de cette bibliothèque
dans le cadre d'un développement dont le temps de traitement
est un facteur déterminant.
j'ai quelque expérience en C++ et avec les templates mais n'ai
jamais utilisé la STL et, ayant un projet en vue, je
m'interresse à l'intérêt que peux m'apporter cette
bibliothèque. J'ai donc récupéré une implémentation libre de
cette dernière afin de comprendre ce qui se passait en
coulisse. Il m'est alors venu une série de questions que je
vous soumets :
j'ai tout d'abord inspecté rapidement le modèle "vector" :
corrigez moi si je me trompe.
il semble que l'ajout (push_back) d'un objet provoque une
réallocation de l'ensemble du tableau. Dispendieux au niveau
temps ?
il est possible de réserver à l'avance un espace pour eviter
cet inconvénient, mais la aussi cela implique d'initialiser
cet espace (encore dispendieux).
je pense alors que pour avoir des conteneurs efficaces, il est
nécessaire au moins de dériver ces conteneurs de base. Mais
la aussi je me heurte à quelques problèmes : supposons tout
simplement que je veuille créer un conteneur tableau trié
d'objets (et qui le restent lors d'ajouts). une insertion
efficace se fait via une recherche dichotomique : j'ai trouvé
binary_search mais celui ci ne renvoie pas d'iterateur (?). la
methode "find" quant à elle ne peut pas faire une recherche
dichotomique étant donné que le tableau n'est pas sensé être
trié (??)
j'ai entendu dire également que cette bibliothèque était
"thread-safe" or je n'ai vu aucun code de synchronisation dans
le source de la bibliothèque récupéré (??)
je me suis posé également la question de création de
conteneurs indirects par ex un conteneur de pointeurs
d'objets : lors de la suppression par "erase", la suppression
ne doit effacer que le pointeur et non l'objet sur lequel il
pointe,
d'ou la neccessité de créer une fonction dérivée afin
de réaliser les choses correctement, n'est-ce pas ?
bref je me pose la question de l'utilité de cette bibliothèque
dans le cadre d'un développement dont le temps de traitement
est un facteur déterminant.
Gabriel Dos Reis writes:
> | bref je me pose la question de l'utilité de cette
> bibliothèque dans le cadre | d'un développement dont le
> temps de traitement est un facteur déterminant.
> la bibliothèque standard fait partie intégrante de C++ et tu
> ne devrais pas hésiter à l'apprendre et à t'en servir.
> Chercher à la contourner ne sera en général que
> contre-productif et une perte de temps.
Sans présumer de l'intérêt de la STL (j'ai mon avis là
dessus), le fait qu'elle fasse partie intégrante de C++ ne
présage rien de bon.
Les array ou les pointeurs font aussi partie intégrante de
C++, et pourtant on fait tout ce qu'on peut pour les éviter et
utiliser plutôt des classes vecteur ou smart pointer.
Gabriel Dos Reis <g...@cs.tamu.edu> writes:
> | bref je me pose la question de l'utilité de cette
> bibliothèque dans le cadre | d'un développement dont le
> temps de traitement est un facteur déterminant.
> la bibliothèque standard fait partie intégrante de C++ et tu
> ne devrais pas hésiter à l'apprendre et à t'en servir.
> Chercher à la contourner ne sera en général que
> contre-productif et une perte de temps.
Sans présumer de l'intérêt de la STL (j'ai mon avis là
dessus), le fait qu'elle fasse partie intégrante de C++ ne
présage rien de bon.
Les array ou les pointeurs font aussi partie intégrante de
C++, et pourtant on fait tout ce qu'on peut pour les éviter et
utiliser plutôt des classes vecteur ou smart pointer.
Gabriel Dos Reis writes:
> | bref je me pose la question de l'utilité de cette
> bibliothèque dans le cadre | d'un développement dont le
> temps de traitement est un facteur déterminant.
> la bibliothèque standard fait partie intégrante de C++ et tu
> ne devrais pas hésiter à l'apprendre et à t'en servir.
> Chercher à la contourner ne sera en général que
> contre-productif et une perte de temps.
Sans présumer de l'intérêt de la STL (j'ai mon avis là
dessus), le fait qu'elle fasse partie intégrante de C++ ne
présage rien de bon.
Les array ou les pointeurs font aussi partie intégrante de
C++, et pourtant on fait tout ce qu'on peut pour les éviter et
utiliser plutôt des classes vecteur ou smart pointer.
In article ,
Pascal J. Bourguignon wrote:
Les cas ou ne pas utiliser vector ?
- si on ne sait pas bien s'en servir, il vaut mieux apprendre.
Comprendre capacity, comprendre resize, connaitre les idiomes
courants (et surtout swap, par exemple).
- si ca n'est vraiment pas adapte, pour les quelques cas ou sa
complexite algorithmique est mauvaise (heureusement, il y a
d'autres structures de donnees dans la STL, et celle-ci est
meme concue pour qu'on puisse reutiliser ce qui est utilisable
avec ses propres structures de donnees !)
- si on a vraiment des contraintes de cout fortes qui font que
les betes tableaux du C sont plus adaptes.
C'est pareil pour les pointeurs et smart pointers...
In article <7ceittn4m1....@pbourguignon.anevia.com>,
Pascal J. Bourguignon <p...@informatimago.com> wrote:
Les cas ou ne pas utiliser vector ?
- si on ne sait pas bien s'en servir, il vaut mieux apprendre.
Comprendre capacity, comprendre resize, connaitre les idiomes
courants (et surtout swap, par exemple).
- si ca n'est vraiment pas adapte, pour les quelques cas ou sa
complexite algorithmique est mauvaise (heureusement, il y a
d'autres structures de donnees dans la STL, et celle-ci est
meme concue pour qu'on puisse reutiliser ce qui est utilisable
avec ses propres structures de donnees !)
- si on a vraiment des contraintes de cout fortes qui font que
les betes tableaux du C sont plus adaptes.
C'est pareil pour les pointeurs et smart pointers...
In article ,
Pascal J. Bourguignon wrote:
Les cas ou ne pas utiliser vector ?
- si on ne sait pas bien s'en servir, il vaut mieux apprendre.
Comprendre capacity, comprendre resize, connaitre les idiomes
courants (et surtout swap, par exemple).
- si ca n'est vraiment pas adapte, pour les quelques cas ou sa
complexite algorithmique est mauvaise (heureusement, il y a
d'autres structures de donnees dans la STL, et celle-ci est
meme concue pour qu'on puisse reutiliser ce qui est utilisable
avec ses propres structures de donnees !)
- si on a vraiment des contraintes de cout fortes qui font que
les betes tableaux du C sont plus adaptes.
C'est pareil pour les pointeurs et smart pointers...
On 9 juin, 11:22, (Pascal J. Bourguignon)
wrote:
La seule chose qu'on peut regretter, c'est les statut des
tableaux (mais on peut utiliser std::tr1::array a la place).
On 9 juin, 11:22, p...@informatimago.com (Pascal J. Bourguignon)
wrote:
La seule chose qu'on peut regretter, c'est les statut des
tableaux (mais on peut utiliser std::tr1::array a la place).
On 9 juin, 11:22, (Pascal J. Bourguignon)
wrote:
La seule chose qu'on peut regretter, c'est les statut des
tableaux (mais on peut utiliser std::tr1::array a la place).
On 2009-06-08, Christian PANEL wrote:bonjour,
j'ai quelque expérience en C++ et avec les templates mais n'ai jamais
utilisé la STL et, ayant un projet en vue, je m'interresse à l'intérêt
que
peux m'apporter cette bibliothèque. J'ai donc récupéré une implémentation
libre de cette dernière afin de comprendre ce qui se passait en coulisse.
Bizarre comme façon de procéder. J'ai plutôt tendance à lire les
docs des logiciels que j'utilise avant leur source.
Il m'est alors venu une série de questions que je vous soumets :
j'ai tout d'abord inspecté rapidement le modèle "vector" : corrigez moi
si
je me trompe.
il semble que l'ajout (push_back) d'un objet provoque une réallocation de
l'ensemble du tableau. Dispendieux au niveau temps ?
il est possible de réserver à l'avance un espace pour eviter cet
inconvénient, mais la aussi cela implique d'initialiser cet espace
(encore
dispendieux).
Ben, vector est un espace contigu de données: cela a des avantages
(accès en O(1) par exemple), mais quand on ajoute des données, il n'y a
pas
pleins de façon de faire: il faut agrandir ou pré-réserver.je pense alors que pour avoir des conteneurs efficaces, il est nécessaire
au
moins de dériver ces conteneurs de base.
Ces conteneurs n'ont pas été conçus pour que l'on en hérite il me semble.j'ai entendu dire également que cette bibliothèque était "thread-safe" or
je
n'ai vu aucun code de synchronisation dans le source de la bibliothèque
récupéré (??)
De mémoire, le C++ tel que décrit par la norme ne connait pas la
notion de thread, et la STL en faisant partie, pas plus.
Après, les fournisseurs d'implantation de la STL peuvent prendre
cette contrainte en compte. Celle que tu as récupéré ne le fait
visiblement
pas.je me suis posé également la question de création de conteneurs indirects
par ex un conteneur de pointeurs d'objets : lors de la suppression par
"erase", la suppression ne doit effacer que le pointeur et non l'objet
sur
lequel il pointe, d'ou la neccessité de créer une fonction dérivée afin
de
réaliser les choses correctement, n'est-ce pas ?
Heuh ? Un vector<int*> ne manipulera que des int*, et erase ne fera que
détruire le "int*" sans toucher à ce qui est pointé derrière.
bref je me pose la question de l'utilité de cette bibliothèque dans le
cadre
d'un développement dont le temps de traitement est un facteur
déterminant.
La STL est la bibliothèque générique fournie avec un compilo C++. Elle
doit
donc etre le meilleur compromis pour tout, donc potentiellement moins
bonne
pour des problèmes donnés. Ceci dit, un grand nombre d'implantations
sérieuses
existent, et peuvent de révéller meilleures que ce qui peut être fait en
un temps limité par un programmeur seul.
Après, le travers du développeur, c'est de rechigner à lire une doc de
200p,
et de commencer à écrire lui même le code dont il a besoin. Si c'est
raisonnable pour un code qui doit être écrit à la fin de la semaine,
ça l'est moins pour un contexte plus vaste.
Marc Boyer
--
Au XXIème siècle, notre projet de société s'est réduit
à un projet économique...
On 2009-06-08, Christian PANEL <c.panel@free.fr> wrote:
bonjour,
j'ai quelque expérience en C++ et avec les templates mais n'ai jamais
utilisé la STL et, ayant un projet en vue, je m'interresse à l'intérêt
que
peux m'apporter cette bibliothèque. J'ai donc récupéré une implémentation
libre de cette dernière afin de comprendre ce qui se passait en coulisse.
Bizarre comme façon de procéder. J'ai plutôt tendance à lire les
docs des logiciels que j'utilise avant leur source.
Il m'est alors venu une série de questions que je vous soumets :
j'ai tout d'abord inspecté rapidement le modèle "vector" : corrigez moi
si
je me trompe.
il semble que l'ajout (push_back) d'un objet provoque une réallocation de
l'ensemble du tableau. Dispendieux au niveau temps ?
il est possible de réserver à l'avance un espace pour eviter cet
inconvénient, mais la aussi cela implique d'initialiser cet espace
(encore
dispendieux).
Ben, vector est un espace contigu de données: cela a des avantages
(accès en O(1) par exemple), mais quand on ajoute des données, il n'y a
pas
pleins de façon de faire: il faut agrandir ou pré-réserver.
je pense alors que pour avoir des conteneurs efficaces, il est nécessaire
au
moins de dériver ces conteneurs de base.
Ces conteneurs n'ont pas été conçus pour que l'on en hérite il me semble.
j'ai entendu dire également que cette bibliothèque était "thread-safe" or
je
n'ai vu aucun code de synchronisation dans le source de la bibliothèque
récupéré (??)
De mémoire, le C++ tel que décrit par la norme ne connait pas la
notion de thread, et la STL en faisant partie, pas plus.
Après, les fournisseurs d'implantation de la STL peuvent prendre
cette contrainte en compte. Celle que tu as récupéré ne le fait
visiblement
pas.
je me suis posé également la question de création de conteneurs indirects
par ex un conteneur de pointeurs d'objets : lors de la suppression par
"erase", la suppression ne doit effacer que le pointeur et non l'objet
sur
lequel il pointe, d'ou la neccessité de créer une fonction dérivée afin
de
réaliser les choses correctement, n'est-ce pas ?
Heuh ? Un vector<int*> ne manipulera que des int*, et erase ne fera que
détruire le "int*" sans toucher à ce qui est pointé derrière.
bref je me pose la question de l'utilité de cette bibliothèque dans le
cadre
d'un développement dont le temps de traitement est un facteur
déterminant.
La STL est la bibliothèque générique fournie avec un compilo C++. Elle
doit
donc etre le meilleur compromis pour tout, donc potentiellement moins
bonne
pour des problèmes donnés. Ceci dit, un grand nombre d'implantations
sérieuses
existent, et peuvent de révéller meilleures que ce qui peut être fait en
un temps limité par un programmeur seul.
Après, le travers du développeur, c'est de rechigner à lire une doc de
200p,
et de commencer à écrire lui même le code dont il a besoin. Si c'est
raisonnable pour un code qui doit être écrit à la fin de la semaine,
ça l'est moins pour un contexte plus vaste.
Marc Boyer
--
Au XXIème siècle, notre projet de société s'est réduit
à un projet économique...
On 2009-06-08, Christian PANEL wrote:bonjour,
j'ai quelque expérience en C++ et avec les templates mais n'ai jamais
utilisé la STL et, ayant un projet en vue, je m'interresse à l'intérêt
que
peux m'apporter cette bibliothèque. J'ai donc récupéré une implémentation
libre de cette dernière afin de comprendre ce qui se passait en coulisse.
Bizarre comme façon de procéder. J'ai plutôt tendance à lire les
docs des logiciels que j'utilise avant leur source.
Il m'est alors venu une série de questions que je vous soumets :
j'ai tout d'abord inspecté rapidement le modèle "vector" : corrigez moi
si
je me trompe.
il semble que l'ajout (push_back) d'un objet provoque une réallocation de
l'ensemble du tableau. Dispendieux au niveau temps ?
il est possible de réserver à l'avance un espace pour eviter cet
inconvénient, mais la aussi cela implique d'initialiser cet espace
(encore
dispendieux).
Ben, vector est un espace contigu de données: cela a des avantages
(accès en O(1) par exemple), mais quand on ajoute des données, il n'y a
pas
pleins de façon de faire: il faut agrandir ou pré-réserver.je pense alors que pour avoir des conteneurs efficaces, il est nécessaire
au
moins de dériver ces conteneurs de base.
Ces conteneurs n'ont pas été conçus pour que l'on en hérite il me semble.j'ai entendu dire également que cette bibliothèque était "thread-safe" or
je
n'ai vu aucun code de synchronisation dans le source de la bibliothèque
récupéré (??)
De mémoire, le C++ tel que décrit par la norme ne connait pas la
notion de thread, et la STL en faisant partie, pas plus.
Après, les fournisseurs d'implantation de la STL peuvent prendre
cette contrainte en compte. Celle que tu as récupéré ne le fait
visiblement
pas.je me suis posé également la question de création de conteneurs indirects
par ex un conteneur de pointeurs d'objets : lors de la suppression par
"erase", la suppression ne doit effacer que le pointeur et non l'objet
sur
lequel il pointe, d'ou la neccessité de créer une fonction dérivée afin
de
réaliser les choses correctement, n'est-ce pas ?
Heuh ? Un vector<int*> ne manipulera que des int*, et erase ne fera que
détruire le "int*" sans toucher à ce qui est pointé derrière.
bref je me pose la question de l'utilité de cette bibliothèque dans le
cadre
d'un développement dont le temps de traitement est un facteur
déterminant.
La STL est la bibliothèque générique fournie avec un compilo C++. Elle
doit
donc etre le meilleur compromis pour tout, donc potentiellement moins
bonne
pour des problèmes donnés. Ceci dit, un grand nombre d'implantations
sérieuses
existent, et peuvent de révéller meilleures que ce qui peut être fait en
un temps limité par un programmeur seul.
Après, le travers du développeur, c'est de rechigner à lire une doc de
200p,
et de commencer à écrire lui même le code dont il a besoin. Si c'est
raisonnable pour un code qui doit être écrit à la fin de la semaine,
ça l'est moins pour un contexte plus vaste.
Marc Boyer
--
Au XXIème siècle, notre projet de société s'est réduit
à un projet économique...
Christian PANEL a écrit :
il semble que l'ajout (push_back) d'un objet provoque une réallocation de
l'ensemble du tableau. Dispendieux au niveau temps ?
la réallocation n'est pas systématique (stratégie d'allocation
déjà expliquée) par contre la copie est systématique.
ce qui est copié dépend bien sur du type paramètre, si c'est un
vector<foo> la classe foo doit être copiable et chaque insertion
utilisera l'opérateur de copie (implicite ou fourni par vous).
si c'est un vector<foo*>, le pointeur sera copié.Mais la aussi je me heurte à quelques problèmes : supposons tout
simplement que je veuille créer un conteneur tableau trié d'objets (et
qui le restent lors d'ajouts).
ce point me surprend, un tableau (basé sur vector ou pas) est "par
essence" un container utilisant l'accès indexé, a contrario un
"associative array" se moque des index mais présuppose une clé
pour réaliser le tri, ici vous voulez trier mais vous ne parlez
pas de clé, ce n'est pas le bon terme ou il manque une donnée.
si par tri vous pensez à une insertion à un index donné du tableau
(du vector) il est possible d'utiliser insert(iterator, foo) en lieu
et place de push_back, cela insérera à la position donnée en décalant
les éléments suivants, le calcul par vous de la position étant un
prérequis, par exemple:
std::vector<foo>::iterator i = b.begin();
i += /rang connu/;
si par contre vous pensez à une insertion ordonnée sans que vous
ayez à connaître a priori cette position, je choisirais plutôt à
arbre binaire auto balancé (type Adelson-Velskii et Landis), là vous
ne gérerez pas d'index et aurez un arbre systématiquement trié.
je me suis posé également la question de création de conteneurs indirects
par ex un conteneur de pointeurs d'objets : lors de la suppression par
"erase", la suppression ne doit effacer que le pointeur et non l'objet
sur lequel il pointe, d'ou la neccessité de créer une fonction dérivée
afin de réaliser les choses correctement, n'est-ce pas ?
si c'est un vector<foo>, chaque push_back(foo(?)) a créé une copie
de foo(?) et la destruction du vector détruira toutes les instances
contenues en propre.
si c'est un vector<foo*>, chaque push_back(new foo(?)) duplique un
pointeur et la destruction du vector détruira seulement le tableau
de pointeur.
donc si votre besoin est de désallouer ces instances lors de la
destructeur du vector, celui-ci ne répond pas, en effet, à votre
attente.
bref je me pose la question de l'utilité de cette bibliothèque dans le
cadre
d'un développement dont le temps de traitement est un facteur
déterminant.
aucune. cela n'engage que moi évidemment.merci de vos éclaircissements et de me faire partager votre expérience
sur
cette bibliothèque.
les contraintes listées (et d'autres) font que je n'utilise jamais
std::vector, mais la "non-expérience" de cette classe est quand
même une expérience d'usage.
Sylvain.
Christian PANEL a écrit :
il semble que l'ajout (push_back) d'un objet provoque une réallocation de
l'ensemble du tableau. Dispendieux au niveau temps ?
la réallocation n'est pas systématique (stratégie d'allocation
déjà expliquée) par contre la copie est systématique.
ce qui est copié dépend bien sur du type paramètre, si c'est un
vector<foo> la classe foo doit être copiable et chaque insertion
utilisera l'opérateur de copie (implicite ou fourni par vous).
si c'est un vector<foo*>, le pointeur sera copié.
Mais la aussi je me heurte à quelques problèmes : supposons tout
simplement que je veuille créer un conteneur tableau trié d'objets (et
qui le restent lors d'ajouts).
ce point me surprend, un tableau (basé sur vector ou pas) est "par
essence" un container utilisant l'accès indexé, a contrario un
"associative array" se moque des index mais présuppose une clé
pour réaliser le tri, ici vous voulez trier mais vous ne parlez
pas de clé, ce n'est pas le bon terme ou il manque une donnée.
si par tri vous pensez à une insertion à un index donné du tableau
(du vector) il est possible d'utiliser insert(iterator, foo) en lieu
et place de push_back, cela insérera à la position donnée en décalant
les éléments suivants, le calcul par vous de la position étant un
prérequis, par exemple:
std::vector<foo>::iterator i = b.begin();
i += /rang connu/;
si par contre vous pensez à une insertion ordonnée sans que vous
ayez à connaître a priori cette position, je choisirais plutôt à
arbre binaire auto balancé (type Adelson-Velskii et Landis), là vous
ne gérerez pas d'index et aurez un arbre systématiquement trié.
je me suis posé également la question de création de conteneurs indirects
par ex un conteneur de pointeurs d'objets : lors de la suppression par
"erase", la suppression ne doit effacer que le pointeur et non l'objet
sur lequel il pointe, d'ou la neccessité de créer une fonction dérivée
afin de réaliser les choses correctement, n'est-ce pas ?
si c'est un vector<foo>, chaque push_back(foo(?)) a créé une copie
de foo(?) et la destruction du vector détruira toutes les instances
contenues en propre.
si c'est un vector<foo*>, chaque push_back(new foo(?)) duplique un
pointeur et la destruction du vector détruira seulement le tableau
de pointeur.
donc si votre besoin est de désallouer ces instances lors de la
destructeur du vector, celui-ci ne répond pas, en effet, à votre
attente.
bref je me pose la question de l'utilité de cette bibliothèque dans le
cadre
d'un développement dont le temps de traitement est un facteur
déterminant.
aucune. cela n'engage que moi évidemment.
merci de vos éclaircissements et de me faire partager votre expérience
sur
cette bibliothèque.
les contraintes listées (et d'autres) font que je n'utilise jamais
std::vector, mais la "non-expérience" de cette classe est quand
même une expérience d'usage.
Sylvain.
Christian PANEL a écrit :
il semble que l'ajout (push_back) d'un objet provoque une réallocation de
l'ensemble du tableau. Dispendieux au niveau temps ?
la réallocation n'est pas systématique (stratégie d'allocation
déjà expliquée) par contre la copie est systématique.
ce qui est copié dépend bien sur du type paramètre, si c'est un
vector<foo> la classe foo doit être copiable et chaque insertion
utilisera l'opérateur de copie (implicite ou fourni par vous).
si c'est un vector<foo*>, le pointeur sera copié.Mais la aussi je me heurte à quelques problèmes : supposons tout
simplement que je veuille créer un conteneur tableau trié d'objets (et
qui le restent lors d'ajouts).
ce point me surprend, un tableau (basé sur vector ou pas) est "par
essence" un container utilisant l'accès indexé, a contrario un
"associative array" se moque des index mais présuppose une clé
pour réaliser le tri, ici vous voulez trier mais vous ne parlez
pas de clé, ce n'est pas le bon terme ou il manque une donnée.
si par tri vous pensez à une insertion à un index donné du tableau
(du vector) il est possible d'utiliser insert(iterator, foo) en lieu
et place de push_back, cela insérera à la position donnée en décalant
les éléments suivants, le calcul par vous de la position étant un
prérequis, par exemple:
std::vector<foo>::iterator i = b.begin();
i += /rang connu/;
si par contre vous pensez à une insertion ordonnée sans que vous
ayez à connaître a priori cette position, je choisirais plutôt à
arbre binaire auto balancé (type Adelson-Velskii et Landis), là vous
ne gérerez pas d'index et aurez un arbre systématiquement trié.
je me suis posé également la question de création de conteneurs indirects
par ex un conteneur de pointeurs d'objets : lors de la suppression par
"erase", la suppression ne doit effacer que le pointeur et non l'objet
sur lequel il pointe, d'ou la neccessité de créer une fonction dérivée
afin de réaliser les choses correctement, n'est-ce pas ?
si c'est un vector<foo>, chaque push_back(foo(?)) a créé une copie
de foo(?) et la destruction du vector détruira toutes les instances
contenues en propre.
si c'est un vector<foo*>, chaque push_back(new foo(?)) duplique un
pointeur et la destruction du vector détruira seulement le tableau
de pointeur.
donc si votre besoin est de désallouer ces instances lors de la
destructeur du vector, celui-ci ne répond pas, en effet, à votre
attente.
bref je me pose la question de l'utilité de cette bibliothèque dans le
cadre
d'un développement dont le temps de traitement est un facteur
déterminant.
aucune. cela n'engage que moi évidemment.merci de vos éclaircissements et de me faire partager votre expérience
sur
cette bibliothèque.
les contraintes listées (et d'autres) font que je n'utilise jamais
std::vector, mais la "non-expérience" de cette classe est quand
même une expérience d'usage.
Sylvain.
>"James Kanze" a écrit dans le message de news:
8da6d7eb-7431-4c59-bec0->
On Jun 8, 4:47 pm, "Christian PANEL" wrote:j'ai quelque expérience en C++ et avec les templates mais n'ai
jamais utilisé la STL et, ayant un projet en vue, je
m'interresse à l'intérêt que peux m'apporter cette
bibliothèque. J'ai donc récupéré une implémentation libre de
cette dernière afin de comprendre ce qui se passait en
coulisse. Il m'est alors venu une série de questions que je
vous soumets :j'ai tout d'abord inspecté rapidement le modèle "vector" :
corrigez moi si je me trompe.
Je ne sais pas si l'inspection des sources d'une implémentation
particulière est une bonne façon d'apprendre quoique ce soit sur
la STL.
il semble que l'ajout (push_back) d'un objet provoque une
réallocation de l'ensemble du tableau. Dispendieux au niveau
temps ?
Si chaque ajoute provoque une réallocation, l'implémentation
n'est pas conforme. La norme exige que push_back ait une
complexité « constante amortie » ; c-à-d en gros que la majorité
des push_back ne provoque pas de réallocation, et que le nombre
de push_back qui provoquent une réallocation diminue avec le
nombre d'éléments dans le vector. Une politique de croissance
exponentielle, donc ; s'il faut réallouer, on multiplie la place
par une facteur constante, typiquement 1,5 ou 2.
il est possible de réserver à l'avance un espace pour eviter
cet inconvénient, mais la aussi cela implique d'initialiser
cet espace (encore dispendieux).
Pas du tout. La fonction reserve n'initialise rien ; elle
alloue de la place, c'est tout.
je pense alors que pour avoir des conteneurs efficaces, il est
nécessaire au moins de dériver ces conteneurs de base. Mais
la aussi je me heurte à quelques problèmes : supposons tout
simplement que je veuille créer un conteneur tableau trié
d'objets (et qui le restent lors d'ajouts). une insertion
efficace se fait via une recherche dichotomique : j'ai trouvé
binary_search mais celui ci ne renvoie pas d'iterateur (?). la
methode "find" quant à elle ne peut pas faire une recherche
dichotomique étant donné que le tableau n'est pas sensé être
trié (??)
La fonction binary_search renvoie une paire d'itérateurs, de
façon à permettre l'itération sur tous les éléments égaux. Pour
trouver où insérer, il faut soit lower_bound, soit upper_bound,
selon où on veut insérer les égaux.
j'ai entendu dire également que cette bibliothèque était
"thread-safe" or je n'ai vu aucun code de synchronisation dans
le source de la bibliothèque récupéré (??)
La norme ne reconnaît pas (encore) des threads, mais la plupart
des implémentations fournissent la même garantie que SGI, voir :
http://www.sgi.com/tech/stl/thread_safety.html. Ce qui est à peu
près la seule qui a un sens. Et les seules synchronisations
nécessaires se trouvent dans des couches plus bas (souvent,
carrément dans malloc).je me suis posé également la question de création de
conteneurs indirects par ex un conteneur de pointeurs
d'objets : lors de la suppression par "erase", la suppression
ne doit effacer que le pointeur et non l'objet sur lequel il
pointe,
Heureusement. Je n'aimerais pas que les collections se mettent à
détruire mes objets.d'ou la neccessité de créer une fonction dérivée afin
de réaliser les choses correctement, n'est-ce pas ?
D'abord, il ne convient prèsque jamais de dériver de
std::vector. Et en fait, std::vector fait les choses
correctement (au moins à cet égard).
bref je me pose la question de l'utilité de cette bibliothèque
dans le cadre d'un développement dont le temps de traitement
est un facteur déterminant.
Par rapport à quoi ? Dans la pratique, je ne suis pas sûr que tu
trouveras une solution plus rapide que std::vector, sauf
peut-être pour des cas particuliers. (Si tu veux représenter un
point 3D par un tableau de double, plutôt que par trois double
distincts, et que ton application a des millions de points 3D,
que tu copies partout, std::vector ferait probablement bien un
problème de performance.)
>"James Kanze" <james.kanze@gmail.com> a écrit dans le message de news:
8da6d7eb-7431-4c59-bec0->f75c8fc5f0c0@x3g2000yqa.googlegroups.com...
On Jun 8, 4:47 pm, "Christian PANEL" <c.pa...@free.fr> wrote:
j'ai quelque expérience en C++ et avec les templates mais n'ai
jamais utilisé la STL et, ayant un projet en vue, je
m'interresse à l'intérêt que peux m'apporter cette
bibliothèque. J'ai donc récupéré une implémentation libre de
cette dernière afin de comprendre ce qui se passait en
coulisse. Il m'est alors venu une série de questions que je
vous soumets :
j'ai tout d'abord inspecté rapidement le modèle "vector" :
corrigez moi si je me trompe.
Je ne sais pas si l'inspection des sources d'une implémentation
particulière est une bonne façon d'apprendre quoique ce soit sur
la STL.
il semble que l'ajout (push_back) d'un objet provoque une
réallocation de l'ensemble du tableau. Dispendieux au niveau
temps ?
Si chaque ajoute provoque une réallocation, l'implémentation
n'est pas conforme. La norme exige que push_back ait une
complexité « constante amortie » ; c-à-d en gros que la majorité
des push_back ne provoque pas de réallocation, et que le nombre
de push_back qui provoquent une réallocation diminue avec le
nombre d'éléments dans le vector. Une politique de croissance
exponentielle, donc ; s'il faut réallouer, on multiplie la place
par une facteur constante, typiquement 1,5 ou 2.
il est possible de réserver à l'avance un espace pour eviter
cet inconvénient, mais la aussi cela implique d'initialiser
cet espace (encore dispendieux).
Pas du tout. La fonction reserve n'initialise rien ; elle
alloue de la place, c'est tout.
je pense alors que pour avoir des conteneurs efficaces, il est
nécessaire au moins de dériver ces conteneurs de base. Mais
la aussi je me heurte à quelques problèmes : supposons tout
simplement que je veuille créer un conteneur tableau trié
d'objets (et qui le restent lors d'ajouts). une insertion
efficace se fait via une recherche dichotomique : j'ai trouvé
binary_search mais celui ci ne renvoie pas d'iterateur (?). la
methode "find" quant à elle ne peut pas faire une recherche
dichotomique étant donné que le tableau n'est pas sensé être
trié (??)
La fonction binary_search renvoie une paire d'itérateurs, de
façon à permettre l'itération sur tous les éléments égaux. Pour
trouver où insérer, il faut soit lower_bound, soit upper_bound,
selon où on veut insérer les égaux.
j'ai entendu dire également que cette bibliothèque était
"thread-safe" or je n'ai vu aucun code de synchronisation dans
le source de la bibliothèque récupéré (??)
La norme ne reconnaît pas (encore) des threads, mais la plupart
des implémentations fournissent la même garantie que SGI, voir :
http://www.sgi.com/tech/stl/thread_safety.html. Ce qui est à peu
près la seule qui a un sens. Et les seules synchronisations
nécessaires se trouvent dans des couches plus bas (souvent,
carrément dans malloc).
je me suis posé également la question de création de
conteneurs indirects par ex un conteneur de pointeurs
d'objets : lors de la suppression par "erase", la suppression
ne doit effacer que le pointeur et non l'objet sur lequel il
pointe,
Heureusement. Je n'aimerais pas que les collections se mettent à
détruire mes objets.
d'ou la neccessité de créer une fonction dérivée afin
de réaliser les choses correctement, n'est-ce pas ?
D'abord, il ne convient prèsque jamais de dériver de
std::vector. Et en fait, std::vector fait les choses
correctement (au moins à cet égard).
bref je me pose la question de l'utilité de cette bibliothèque
dans le cadre d'un développement dont le temps de traitement
est un facteur déterminant.
Par rapport à quoi ? Dans la pratique, je ne suis pas sûr que tu
trouveras une solution plus rapide que std::vector, sauf
peut-être pour des cas particuliers. (Si tu veux représenter un
point 3D par un tableau de double, plutôt que par trois double
distincts, et que ton application a des millions de points 3D,
que tu copies partout, std::vector ferait probablement bien un
problème de performance.)
>"James Kanze" a écrit dans le message de news:
8da6d7eb-7431-4c59-bec0->
On Jun 8, 4:47 pm, "Christian PANEL" wrote:j'ai quelque expérience en C++ et avec les templates mais n'ai
jamais utilisé la STL et, ayant un projet en vue, je
m'interresse à l'intérêt que peux m'apporter cette
bibliothèque. J'ai donc récupéré une implémentation libre de
cette dernière afin de comprendre ce qui se passait en
coulisse. Il m'est alors venu une série de questions que je
vous soumets :j'ai tout d'abord inspecté rapidement le modèle "vector" :
corrigez moi si je me trompe.
Je ne sais pas si l'inspection des sources d'une implémentation
particulière est une bonne façon d'apprendre quoique ce soit sur
la STL.
il semble que l'ajout (push_back) d'un objet provoque une
réallocation de l'ensemble du tableau. Dispendieux au niveau
temps ?
Si chaque ajoute provoque une réallocation, l'implémentation
n'est pas conforme. La norme exige que push_back ait une
complexité « constante amortie » ; c-à-d en gros que la majorité
des push_back ne provoque pas de réallocation, et que le nombre
de push_back qui provoquent une réallocation diminue avec le
nombre d'éléments dans le vector. Une politique de croissance
exponentielle, donc ; s'il faut réallouer, on multiplie la place
par une facteur constante, typiquement 1,5 ou 2.
il est possible de réserver à l'avance un espace pour eviter
cet inconvénient, mais la aussi cela implique d'initialiser
cet espace (encore dispendieux).
Pas du tout. La fonction reserve n'initialise rien ; elle
alloue de la place, c'est tout.
je pense alors que pour avoir des conteneurs efficaces, il est
nécessaire au moins de dériver ces conteneurs de base. Mais
la aussi je me heurte à quelques problèmes : supposons tout
simplement que je veuille créer un conteneur tableau trié
d'objets (et qui le restent lors d'ajouts). une insertion
efficace se fait via une recherche dichotomique : j'ai trouvé
binary_search mais celui ci ne renvoie pas d'iterateur (?). la
methode "find" quant à elle ne peut pas faire une recherche
dichotomique étant donné que le tableau n'est pas sensé être
trié (??)
La fonction binary_search renvoie une paire d'itérateurs, de
façon à permettre l'itération sur tous les éléments égaux. Pour
trouver où insérer, il faut soit lower_bound, soit upper_bound,
selon où on veut insérer les égaux.
j'ai entendu dire également que cette bibliothèque était
"thread-safe" or je n'ai vu aucun code de synchronisation dans
le source de la bibliothèque récupéré (??)
La norme ne reconnaît pas (encore) des threads, mais la plupart
des implémentations fournissent la même garantie que SGI, voir :
http://www.sgi.com/tech/stl/thread_safety.html. Ce qui est à peu
près la seule qui a un sens. Et les seules synchronisations
nécessaires se trouvent dans des couches plus bas (souvent,
carrément dans malloc).je me suis posé également la question de création de
conteneurs indirects par ex un conteneur de pointeurs
d'objets : lors de la suppression par "erase", la suppression
ne doit effacer que le pointeur et non l'objet sur lequel il
pointe,
Heureusement. Je n'aimerais pas que les collections se mettent à
détruire mes objets.d'ou la neccessité de créer une fonction dérivée afin
de réaliser les choses correctement, n'est-ce pas ?
D'abord, il ne convient prèsque jamais de dériver de
std::vector. Et en fait, std::vector fait les choses
correctement (au moins à cet égard).
bref je me pose la question de l'utilité de cette bibliothèque
dans le cadre d'un développement dont le temps de traitement
est un facteur déterminant.
Par rapport à quoi ? Dans la pratique, je ne suis pas sûr que tu
trouveras une solution plus rapide que std::vector, sauf
peut-être pour des cas particuliers. (Si tu veux représenter un
point 3D par un tableau de double, plutôt que par trois double
distincts, et que ton application a des millions de points 3D,
que tu copies partout, std::vector ferait probablement bien un
problème de performance.)
"Marc Boyer" a écrit dans le message de
news:On 2009-06-08, Christian PANEL wrote:bonjour,
j'ai quelque expérience en C++ et avec les templates mais n'ai jamais
utilisé la STL et, ayant un projet en vue, je m'interresse à l'intérêt
que
peux m'apporter cette bibliothèque. J'ai donc récupéré une implémentation
libre de cette dernière afin de comprendre ce qui se passait en coulisse.
Bizarre comme façon de procéder. J'ai plutôt tendance à lire les
docs des logiciels que j'utilise avant leur source.
les versions d'essai style VC 2008 express, & co n'indique absolument rien
dans la manière dont sont implémentées les différentes fonctions (c'est un
peu comme si on vous proposait un produit sans vous démontrer son
efficacité)
De mémoire, le C++ tel que décrit par la norme ne connait pas la
notion de thread, et la STL en faisant partie, pas plus.
oui et c'est bien quand même domage quand on veut faire un code portable.
Heuh ? Un vector<int*> ne manipulera que des int*, et erase ne fera que
détruire le "int*" sans toucher à ce qui est pointé derrière.
oui, c'est bien ce que j'avais compris, d'où l'utilité de rajouter du code
si on veut omplémenter ce type de conteneur
Après, le travers du développeur, c'est de rechigner à lire une doc de
200p,
et de commencer à écrire lui même le code dont il a besoin. Si c'est
raisonnable pour un code qui doit être écrit à la fin de la semaine,
ça l'est moins pour un contexte plus vaste.
le tout est de calculer si par ex implémenter un tableau indirect d'objets
triés en C n'est pas plus rapide à faire que de lire une doc de 200 p et de
coder par dessus (avec en plus pas la certitude que ce soit plus efficace)
"Marc Boyer" <Marc.Boyer@cert.onera.fr.invalid> a écrit dans le message de
news: slrnh2qb25.3a0.Marc.Boyer@gavarnie.cert.fr...
On 2009-06-08, Christian PANEL <c.panel@free.fr> wrote:
bonjour,
j'ai quelque expérience en C++ et avec les templates mais n'ai jamais
utilisé la STL et, ayant un projet en vue, je m'interresse à l'intérêt
que
peux m'apporter cette bibliothèque. J'ai donc récupéré une implémentation
libre de cette dernière afin de comprendre ce qui se passait en coulisse.
Bizarre comme façon de procéder. J'ai plutôt tendance à lire les
docs des logiciels que j'utilise avant leur source.
les versions d'essai style VC 2008 express, & co n'indique absolument rien
dans la manière dont sont implémentées les différentes fonctions (c'est un
peu comme si on vous proposait un produit sans vous démontrer son
efficacité)
De mémoire, le C++ tel que décrit par la norme ne connait pas la
notion de thread, et la STL en faisant partie, pas plus.
oui et c'est bien quand même domage quand on veut faire un code portable.
Heuh ? Un vector<int*> ne manipulera que des int*, et erase ne fera que
détruire le "int*" sans toucher à ce qui est pointé derrière.
oui, c'est bien ce que j'avais compris, d'où l'utilité de rajouter du code
si on veut omplémenter ce type de conteneur
Après, le travers du développeur, c'est de rechigner à lire une doc de
200p,
et de commencer à écrire lui même le code dont il a besoin. Si c'est
raisonnable pour un code qui doit être écrit à la fin de la semaine,
ça l'est moins pour un contexte plus vaste.
le tout est de calculer si par ex implémenter un tableau indirect d'objets
triés en C n'est pas plus rapide à faire que de lire une doc de 200 p et de
coder par dessus (avec en plus pas la certitude que ce soit plus efficace)
"Marc Boyer" a écrit dans le message de
news:On 2009-06-08, Christian PANEL wrote:bonjour,
j'ai quelque expérience en C++ et avec les templates mais n'ai jamais
utilisé la STL et, ayant un projet en vue, je m'interresse à l'intérêt
que
peux m'apporter cette bibliothèque. J'ai donc récupéré une implémentation
libre de cette dernière afin de comprendre ce qui se passait en coulisse.
Bizarre comme façon de procéder. J'ai plutôt tendance à lire les
docs des logiciels que j'utilise avant leur source.
les versions d'essai style VC 2008 express, & co n'indique absolument rien
dans la manière dont sont implémentées les différentes fonctions (c'est un
peu comme si on vous proposait un produit sans vous démontrer son
efficacité)
De mémoire, le C++ tel que décrit par la norme ne connait pas la
notion de thread, et la STL en faisant partie, pas plus.
oui et c'est bien quand même domage quand on veut faire un code portable.
Heuh ? Un vector<int*> ne manipulera que des int*, et erase ne fera que
détruire le "int*" sans toucher à ce qui est pointé derrière.
oui, c'est bien ce que j'avais compris, d'où l'utilité de rajouter du code
si on veut omplémenter ce type de conteneur
Après, le travers du développeur, c'est de rechigner à lire une doc de
200p,
et de commencer à écrire lui même le code dont il a besoin. Si c'est
raisonnable pour un code qui doit être écrit à la fin de la semaine,
ça l'est moins pour un contexte plus vaste.
le tout est de calculer si par ex implémenter un tableau indirect d'objets
triés en C n'est pas plus rapide à faire que de lire une doc de 200 p et de
coder par dessus (avec en plus pas la certitude que ce soit plus efficace)
oui bien sur, il y a toujours des solutions auxquelles je ne pensais pas à
priori.
mais peut être ai-je loupé quelque chose : une structure d'arbre binaire
n'est pas implémenté dans la STL, non ?
oui bien sur, il y a toujours des solutions auxquelles je ne pensais pas à
priori.
mais peut être ai-je loupé quelque chose : une structure d'arbre binaire
n'est pas implémenté dans la STL, non ?
oui bien sur, il y a toujours des solutions auxquelles je ne pensais pas à
priori.
mais peut être ai-je loupé quelque chose : une structure d'arbre binaire
n'est pas implémenté dans la STL, non ?