questions sur la STL

"Christian PANEL" <c.panel@free.fr> writes:

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. 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 ?

Pas forcément: si on double la capacité du vecteur à chaque fois qu'il
faut le réallouer, alors le nombre total de copie sera en O(n).

1->2 1 copie
2->4 1+2 copies
4->8 3+4 copies
8->16 7+8 copies
n->2n n-1+n = 2n-1 copies


Donc, ajouter un élément, ça prend une copie plus un assignement.
Seulement la copie n'est pas faite au même moment que l'assignement,
en général.

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).

Oui.

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é (??)

Oui, la STL n'est pas forcement ce qu'il y a de mieux si on veut en
faire des sous-classes.

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é (??)

Ça doit surement dépendre des implémentations.

Mais en général le niveau de sécurité par rapport aux threads est
forcément assez limité: il faut tenir compte de la sémantique de
l'application pour pouvoir appliquer les verrous adéquats.

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 on veut supprimer l'objet lorsque le dernier pointeur sur lui est
supprimé, en effet. On peut le faire avec des "smart pointers".

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.

Disons que c'est une bibliothèque de bas niveau (assez efficace)
donnant des structures de données essentielles (que l'on retrouverait
comme type de base dans n'importe quel language de haut niveau), et
qu'elle est souvent requise par les "clients". À ce titre, il
convient de savoir s'en servir.

Maintenant, si j'avais à développer n'importe quel type de programme
non-trivial sans avoir comme contrainte externe STL, je n'utiliserai
pas STL. (Mais je n'utiliserai pas non plus C++).

merci de vos éclaircissements et de me faire partager votre expérience sur
cette bibliothèque.

--
__Pascal Bourguignon__

"Christian PANEL" <c.panel@free.fr> writes:

| bonjour,
|
| j'ai quelque expérience en C++ et avec les templates mais n'ai jamai s
| 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 coul isse. 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" : corr igez moi si
| je me trompe.
| il semble que l'ajout (push_back) d'un objet provoque une réallocati on de
| l'ensemble du tableau. Dispendieux au niveau temps ?

La réallocation a lieu uniquement s'il n'y a pas assez d'espace pour
stocker le nouvel élément. Cependant, la spécification est t elle que tu
as un coût amorti constant (ce qui implique qu'en moyenne tu N'as PAS une
réallocation à chaque push_back).

| il est possible de réserver à l'avance un espace pour eviter ce t
| inconvénient, mais la aussi cela implique d'initialiser cet espace ( encore
| dispendieux).

Non. v.reserve(n) n'initialize pas les données. Cette action alloue j ust
de la mémoire suffisante pour n push_back successifs sans réallou er.


| je pense alors que pour avoir des conteneurs efficaces, il est néces saire au
| moins de dériver ces conteneurs de base.

Ce n'est pas une bonne idée en général. Les structures de do nnées de la
STL sont générales et assez efficaces. Il y a de fortes chances q ue tu
ne fasses pas mieux.

| Mais la aussi je me heurte à quelques problèmes : supposons tou t simplement
| que je veuille créer un conteneur tableau trié d'objets (et qui le restent
| lors d'ajouts).

Si les objets ne sont jamais modifiés, tu peux aussi considérer s td::set.

| une insertion efficace se fait via une recherche dichotomique : j'ai trou vé
| 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é (??)

binary_search, comme son nom ne l'indique pas, ne fait pas de recherche
binaire (comme on l'aurait supposé). binary_search détermine si une
valeur donnée se trouve dans un suite triée. Pour faire de la re cherche
binaire, tu as de la combinaison de std::equal_range, std::lower_bound
et std::upper_bound.

| 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é (??)

C++03 ne sait pas ce que c'est que « thread ». Donc quand quelqu 'un te dit
« thread safe » il faut demander plus de précision.
De manière générale, les implémentations vont faire en sorte que leurs
utilisations internes de données ne posent pas de problèmes. Mai s c'est
la responsabilité de l'utilisateur de prendre des locks à grande échelle.

|
| je me suis posé également la question de création de conte neurs 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 su r
| 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 ?

stocker des pointeurs marche très bien dans ce cas.

|
| 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 d evrais
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.

|
| merci de vos éclaircissements et de me faire partager votre expà ©rience sur
| cette bibliothèque.

Deux sources :

(1) The C++ Programming Language, special edition
(2) Generic Programming and the STL

-- Gaby

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...

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.

On 8 juin, 16:47, "Christian PANEL" <c.pa...@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 couliss e.

[snip: répondu dans d'autres messages]

Une référence uqi date un peu mais que je trouve efficae est
"The C++ Standard Library - A Tutorial and Reference"
par M Josuttis
http://www.josuttis.com/libbook/

bref je me pose la question de l'utilité de cette bibliothèque dans l e cadre
d'un développement dont le temps de traitement est un facteur détermi nant.

Les fonctions garantissent une complexité et les fournisseurs passent
un certain temps à implémenter correctement leur STL (encore qu'il y
ait des disparités, notamment au niveau des strings) donc c'est assez
transparent.

Les problèmes de perf viennent souvent (toujours?) d'un mauvais choix
de structure de données ou d'algo.

--
Michael

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.

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.

D'ailleurs, c'est le premier reproche que l'on peut faire à C++, que
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...

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.

--
__Pascal Bourguignon__

In article <7ceittn4m1.fsf@pbourguignon.anevia.com>,
Pascal J. Bourguignon <pjb@informatimago.com> wrote:

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.

D'ailleurs, c'est le premier reproche que l'on peut faire à C++, que
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...

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.

Superbe lapalissade.
Tout fait partie des choses a eviter, au moins dans certains contextes...

C'est ca l'inconvenient d'un langage generaliste, qui permet de faire a
peu pres tout...

Les vector sont un excellent remplacant des tableaux du C dans la plupart
des contextes. Ils ont evidemment un cout, qui est faible, a compenser
par la tonne d'avantages qui va avec, entre le changement de taille
automatique (et efficace), la structure qui trimballe sa propre taille,
et la possibilite de faire du code exception-safe.

Lorsque je fais du C, c'est fou le nombre de fois ou je refais des vector.
La technique capacity/size est certes excessivement cretine, mais
redoutablement efficace dans un nombre affolant de cas pratiques... en
particulier, ca torsche les listes cote efficacite dans un nombre tres,
tres, tres important de cas.

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, p...@informatimago.com (Pascal J. Bourguignon)
wrote:

Gabriel Dos Reis <g...@cs.tamu.edu> writes:

> | bref je me pose la question de l'utilité de cette bibliothèque da ns le cadre
> | d'un développement dont le temps de traitement est un facteur dét erminant.

> la bibliothèque standard fait partie intégrante de C++ et tu ne dev rais
> pas hésiter à l'apprendre et à t'en servir.  Chercher à la co ntourner 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), l e
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.

On peut aussi faire la distinction entre ne pas utiliser et utiliser
avec distinction.
Les smart pointer ou les structures qui gèrent leur mémoire répondent
à certains besoins mais pas à tous.

La seule chose qu'on peut regretter, c'est les statut des tableaux
(mais on peut utiliser std::tr1::array a la place).

D'ailleurs, c'est le premier reproche que l'on peut faire à C++, que
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...

Dans ma boite à outils, il y a pleins d'outils que j'évite d'utiliser
quand je bricole (comme un burin) mais qui sont parfois indispensable.

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.

Tentative de syllogisme ?

--
Michael

On Tue, 09 Jun 2009 11:22:46 +0200, pjb@informatimago.com (Pascal J.
Bourguignon):

D'ailleurs, c'est le premier reproche que l'on peut faire à C++

Non, le principal reproche qu'on peut faire à C++, comme à beaucoup de
langages, c'est de n'être pas Lisp.

In article <vges259darguv7vv75lpv9l1csqv7j8lja@4ax.com>,
Fabien LE LEZ <usenet18@x.edulang.com> wrote:

On Tue, 09 Jun 2009 11:22:46 +0200, pjb@informatimago.com (Pascal J.
Bourguignon):

D'ailleurs, c'est le premier reproche que l'on peut faire à C++

Non, le principal reproche qu'on peut faire à C++, comme à beaucoup de
langages, c'est de n'être pas Lisp.

Fabien, c'est pas gentil de te moquer de ton petit camarade.