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.
merci de vos éclaircissements et de me faire partager votre expérience sur
cette bibliothèque.
"Pascal J. Bourguignon" a écrit dans le message de news:
"Christian PANEL" writes:
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 ?
std::map.
En fait, c'est une des raisons de bien étudier la _documentation_ de STL : des contraintes de complexité algorithmique sont indiquées pour les fonctions cruciales, ce qui implique en pratique une catégorie d'implémentations.
Maintenant, rien ne dit que std::map ne puisse pas utiliser un arbre ternaire ou un arbre plus large encore (ça répondrait toujours aux contraintes asymptotiques). Mais le plus probable reste que ce soit une sorte d'arbre binaire équilibré.
-- __Pascal Bourguignon__
oh oui, j'ai vraiment suvolé et avait pensé à tout autre chose en voyant ce conteneur, on peut évidemment difficilement appréhender la STL en 1 heure. merci, je vais m'y interresser de plus près.
"Pascal J. Bourguignon" <pjb@informatimago.com> a écrit dans le message de
news: 7chbyp60h2.fsf@pbourguignon.anevia.com...
"Christian PANEL" <c.panel@free.fr> writes:
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 ?
std::map.
En fait, c'est une des raisons de bien étudier la _documentation_ de
STL : des contraintes de complexité algorithmique sont indiquées pour
les fonctions cruciales, ce qui implique en pratique une catégorie
d'implémentations.
Maintenant, rien ne dit que std::map ne puisse pas utiliser un arbre
ternaire ou un arbre plus large encore (ça répondrait toujours aux
contraintes asymptotiques). Mais le plus probable reste que ce soit
une sorte d'arbre binaire équilibré.
--
__Pascal Bourguignon__
oh oui, j'ai vraiment suvolé et avait pensé à tout autre chose en voyant ce
conteneur, on peut évidemment difficilement appréhender la STL en 1 heure.
merci, je vais m'y interresser de plus près.
"Pascal J. Bourguignon" a écrit dans le message de news:
"Christian PANEL" writes:
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 ?
std::map.
En fait, c'est une des raisons de bien étudier la _documentation_ de STL : des contraintes de complexité algorithmique sont indiquées pour les fonctions cruciales, ce qui implique en pratique une catégorie d'implémentations.
Maintenant, rien ne dit que std::map ne puisse pas utiliser un arbre ternaire ou un arbre plus large encore (ça répondrait toujours aux contraintes asymptotiques). Mais le plus probable reste que ce soit une sorte d'arbre binaire équilibré.
-- __Pascal Bourguignon__
oh oui, j'ai vraiment suvolé et avait pensé à tout autre chose en voyant ce conteneur, on peut évidemment difficilement appréhender la STL en 1 heure. merci, je vais m'y interresser de plus près.
James Kanze
On Jun 9, 2:19 pm, "Christian PANEL" wrote:
>"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.
hum! difficile de savoir ce qu'il se passe sans cela, à moins d'avoir une doc digne de ce nom (ce que je n'ai pas)
Mais une source ne te dit que ce que fait une implémentation, non ce qui est garanti et ce qui ne l'est pas.
>> 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.
bon à savoir mais cela ne semble pas être le cas dans le source que j'ai examiné (d'ou l'utilité quelquefois de consulter le source si on veut controler l'efficacité du code généré)
Dans ce cas-là, ce n'est pas une source de std::vector. Je ne sais pas ce que tu régardes, mais l'exigence d'une croissance exponentielle était présente dès le début, bien avant que le comité de normalisation a adopté la STL dans C++. Et toutes les implémentations que je connais (g++, Dinkumware, STLport et Rogue Wave) le respectent.
[...]
>> 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.
Erreur de ma part ; c'est la fonction equal_range qui renvoie la paire d'itérateurs.
-- James Kanze (GABI Software) email: 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
On Jun 9, 2:19 pm, "Christian PANEL" <c.pa...@free.fr> wrote:
>"James Kanze" <james.ka...@gmail.com> a écrit dans le message de news:
>8da6d7eb-7431-4c59-bec0->f75c8fc5f...@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.
hum! difficile de savoir ce qu'il se passe sans cela, à moins
d'avoir une doc digne de ce nom (ce que je n'ai pas)
Mais une source ne te dit que ce que fait une implémentation,
non ce qui est garanti et ce qui ne l'est pas.
>> 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.
bon à savoir mais cela ne semble pas être le cas dans le
source que j'ai examiné (d'ou l'utilité quelquefois de
consulter le source si on veut controler l'efficacité du code
généré)
Dans ce cas-là, ce n'est pas une source de std::vector. Je ne
sais pas ce que tu régardes, mais l'exigence d'une croissance
exponentielle était présente dès le début, bien avant que le
comité de normalisation a adopté la STL dans C++. Et toutes les
implémentations que je connais (g++, Dinkumware, STLport et
Rogue Wave) le respectent.
[...]
>> 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.
Erreur de ma part ; c'est la fonction equal_range qui renvoie la
paire d'itérateurs.
--
James Kanze (GABI Software) email:james.kanze@gmail.com
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
>"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.
hum! difficile de savoir ce qu'il se passe sans cela, à moins d'avoir une doc digne de ce nom (ce que je n'ai pas)
Mais une source ne te dit que ce que fait une implémentation, non ce qui est garanti et ce qui ne l'est pas.
>> 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.
bon à savoir mais cela ne semble pas être le cas dans le source que j'ai examiné (d'ou l'utilité quelquefois de consulter le source si on veut controler l'efficacité du code généré)
Dans ce cas-là, ce n'est pas une source de std::vector. Je ne sais pas ce que tu régardes, mais l'exigence d'une croissance exponentielle était présente dès le début, bien avant que le comité de normalisation a adopté la STL dans C++. Et toutes les implémentations que je connais (g++, Dinkumware, STLport et Rogue Wave) le respectent.
[...]
>> 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.
Erreur de ma part ; c'est la fonction equal_range qui renvoie la paire d'itérateurs.
-- James Kanze (GABI Software) email: 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
La seule chose qu'on peut regretter, c'est les statut des tableaux (mais on peut utiliser std::tr1::array a la place).
| Qui devient std::array dans la prochaine version de la norme. | Mais qui ne permet toujours pas de choses comme: | | std::array< int > const a[] = { 1, 1, 2, 3, 5, 8 } ; ^^
| On Jun 9, 12:22 pm, Michael Doubez <michael.dou...@free.fr> wrote:
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).
| Qui devient std::array dans la prochaine version de la norme.
| Mais qui ne permet toujours pas de choses comme:
|
| std::array< int > const a[] = { 1, 1, 2, 3, 5, 8 } ;
^^
La seule chose qu'on peut regretter, c'est les statut des tableaux (mais on peut utiliser std::tr1::array a la place).
| Qui devient std::array dans la prochaine version de la norme. | Mais qui ne permet toujours pas de choses comme: | | std::array< int > const a[] = { 1, 1, 2, 3, 5, 8 } ; ^^
| 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.
Ce serait une lourde erreur de prétendre le contraire.
| 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.
i.e. la STL.
Pas forcément. C'est le coeur de mon argument.
| D'ailleurs, c'est le premier reproche que l'on peut faire à C++, que
si c'est le premier reproche que tu peux faire à C++, tu n'as pas regarder suffisamment.
| pour bien l'utiliser, il faut éviter d'utiliser plein d'éléments de ce | langage, ce que notent bien tous les guides de style...
je vois que tu peux jeter la première pierre.
| Alors il n'y a pas de raison de supposer que la STL ne fasse pas | partie des choses à éviter, au moins dans certains contextes.
Bonne chance.
Honêtement, jusqu'à ce qu'un client me demande d'utiliser la STL, dans tous mes développement C++, je ne l'ai jamais utilisé (d'abord, elle n'existait pas, ensuite j'avais développé ma propre bibliothèque). De nos jours, si je voulais réaliser un développement en C++, je n'utiliserais pas la STL, mais je développerais aussi ma propre bibliothèque, sur d'autre fondements que ceux de la STL ou de boost. (eg. pas de smart pointeur, mais un vrai garbage collecteur, une approche plus fonctionnelle que procédurale, etc).
-- __Pascal Bourguignon__
Gabriel Dos Reis <gdr@cse.tamu.edu> writes:
pjb@informatimago.com (Pascal J. Bourguignon) writes:
| Gabriel Dos Reis <gdr@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.
Ce serait une lourde erreur de prétendre le contraire.
| 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.
i.e. la STL.
Pas forcément. C'est le coeur de mon argument.
| D'ailleurs, c'est le premier reproche que l'on peut faire à C++, que
si c'est le premier reproche que tu peux faire à C++, tu n'as pas
regarder suffisamment.
| pour bien l'utiliser, il faut éviter d'utiliser plein d'éléments de ce
| langage, ce que notent bien tous les guides de style...
je vois que tu peux jeter la première pierre.
| Alors il n'y a pas de raison de supposer que la STL ne fasse pas
| partie des choses à éviter, au moins dans certains contextes.
Bonne chance.
Honêtement, jusqu'à ce qu'un client me demande d'utiliser la STL, dans
tous mes développement C++, je ne l'ai jamais utilisé (d'abord, elle
n'existait pas, ensuite j'avais développé ma propre bibliothèque). De
nos jours, si je voulais réaliser un développement en C++, je
n'utiliserais pas la STL, mais je développerais aussi ma propre
bibliothèque, sur d'autre fondements que ceux de la STL ou de
boost. (eg. pas de smart pointeur, mais un vrai garbage collecteur, une
approche plus fonctionnelle que procédurale, etc).
| 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.
Ce serait une lourde erreur de prétendre le contraire.
| 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.
i.e. la STL.
Pas forcément. C'est le coeur de mon argument.
| D'ailleurs, c'est le premier reproche que l'on peut faire à C++, que
si c'est le premier reproche que tu peux faire à C++, tu n'as pas regarder suffisamment.
| pour bien l'utiliser, il faut éviter d'utiliser plein d'éléments de ce | langage, ce que notent bien tous les guides de style...
je vois que tu peux jeter la première pierre.
| Alors il n'y a pas de raison de supposer que la STL ne fasse pas | partie des choses à éviter, au moins dans certains contextes.
Bonne chance.
Honêtement, jusqu'à ce qu'un client me demande d'utiliser la STL, dans tous mes développement C++, je ne l'ai jamais utilisé (d'abord, elle n'existait pas, ensuite j'avais développé ma propre bibliothèque). De nos jours, si je voulais réaliser un développement en C++, je n'utiliserais pas la STL, mais je développerais aussi ma propre bibliothèque, sur d'autre fondements que ceux de la STL ou de boost. (eg. pas de smart pointeur, mais un vrai garbage collecteur, une approche plus fonctionnelle que procédurale, etc).
-- __Pascal Bourguignon__
Fabien LE LEZ
On Wed, 10 Jun 2009 05:12:44 -0500, Gabriel Dos Reis :
Mais, lequel Lisp ?
COW[*].
[*] can of worms.
On Wed, 10 Jun 2009 05:12:44 -0500, Gabriel Dos Reis
<gdr@cse.tamu.edu>:
