Bonjour à tous,
Je cherche actuellement des informations tres précise sur le fonctionnement de la STL selon la norme. Je suis donc a la recherche du plus d´information possible. Je sais que la norme est payante, mais peut etre un draft est disponible.
Quelqu´un aurait ca (ou autre chose qui m´aiderait) en stock ?
Merci

Je m´appuie sur la norme de SGI (meme si la norme ne contient pas les hash, les slist, et autres conteneurs)
A part cela, cette doc m´a permis d´etre portable Windows/Linux.

http://www.sgi.com/tech/stl/table_of_contents.html

J´ai l´impression que SGI respecte la norme (sauf quand il le dit) mais produit des extensions a cette norme.
Par exemple au sujet de l´algorithme for_each, SGI stipule:
"Applications are performed in forward order, i.e. from first to last"
Pourtant for_each prends en parametre un InputIterator et non un ForwardIterator. J´ai l´impression que ce comportement n´est pas imposé par la norme.
De plus, le livre "STL tutorial and Reference guide", par Musser et Saini, ne précise pas l´ordre d´application.

J´aurai du dire que je cherchais à ré-écrire une partie de la STL et non pas à l´utiliser. C´est pourquoi, je m´attache a ce style de détail.

par la vraie norme, je suis loin d´etre incollable.
par contre, j´ai appris les fonctionnements internes des STL, je connais les algos internes utilisés, si tu as besoin...

En fait, il y a un draft du standard C++ sur le site de B. Stroustrup:
ftp://https://www.jeuxvideo.com//ftp.research.att.com/pub/c++std/WP/CD2/
Exactement ce qu´il me fallait!

Les informations suivante m´intéresseraient. pouvez vous répondre a ces quelques questions ?

dans les applications qui vous interesse quel algorithmes de la STL utilisez vous ?
De quelle taille sont les données manipulées (max et moyenne) ?
Combien de temps prennent vos opération élémentaires (max et moyenne) ?

merci!

(HS) Reecrire la STL est un bon exercice, mais en pratique je trouve ca pas tres utile, et ce pour plusieures raisons:
en pratique, l´utilisation de la STL ne devrait se faire que dans les parties "utilitaires" d´un code, ie la ou les performances ne jouent pas. En effet, si je prends l´exemple d´un jv, personne ne veut (en tout cas personne ne devrait vouloir) utiliser la stl pour qqchose de time critical: pas assez flexible pour la gestion de la memoire utilisee, il est souvent plus que tres judicieux d´integrer (par exemple) une liste chainee dans la classe utilisee plutot que d´avoir un objet externe, mauvaise gestion du cache, etc.

Donc pour en revenir a tes moutons, sachant que je n´utlise que la STL pour des operations non time critical, ou pour mes tools.

dans les applications qui vous interesse quel algorithmes de la STL utilisez vous ?

Deja les classes que j´utilise le plus: vector, list, map, string (meme si j´utilise bcp plus ma version custom)
Algo: find, for_each

De quelle taille sont les donnees manipulees (max et moyenne) ?

Ca depends vraiment.. Par exemple, creation d´une table d´index pour les objets, j´ai une grosse map (disons en 100k elements). Les outils offline de generation de qqchose utilisent aussi du custom code plutot que la stl..
Mais la plupart du temps je travail sur des vector/list de moins de 100 elements, voir meme tres souvent de l´ordre de 4-5 elt.

Combien de temps prennent vos operation elementaires (max et moyenne) ?

Si j´utilise la STL pour qq chose qui est appele "souvent", je m´arrange pour toujours avoir de l´O(1), donc je ne fait aucun sort ou autre.
Sinon, aucune idee

/kUfa

(réponse au HS)
Je ne suis pas completement d´accord avec ton:
"en pratique, l´utilisation de la STL ne devrait se faire que dans les parties "utilitaires" d´un code, ie la ou les performances ne jouent pas."

J´ai tendance a l´utiliser pour a peu pres tout parceque je ne cherche pas (basiquement) de performance. donc ca peut m´arriver de faire des sort de paquets d´un million d´element. Certes, ce n´est généralement pas ce qui prends le plus de temps de mon appli, mais ca peut en prendre une portion non négligeable.

Après, c´est sur que j´écris beaucoup de code expérimental et tres peu (pas du tout en fait) de code destiné à la production.

en passant, par:
"Combien de temps prennent vos operation elementaires (max et moyenne) ?"

Je veux dire, ce sont des comparaison d´entiers, de flottant, de chaine de caractere ?
Dans le cas des tris, merges et cie, il y a aussi des affectations, est ce que ce sont des opérations lentes ?

J´ai tendance a l´utiliser pour a peu pres tout parceque je ne cherche pas (basiquement) de performance.

Tu sous-entends donc que si tu cherchais a ameliorer tes performances tu utiliserais donc autre chose? (ce que je ferais perso) Mais bon reecrire la STL pour ameliorer les performances d´un code pour lequel tu ne cherches pas a avoir de bonnes performances n´est pas le plus utile *imo*, tu auras tjs moins de performances que si tu optimisais l´algo en question, et surtout c´est long de reecrire la stl.

Par contre je suis tout a fait d´accord sur le fait d´utiliser la STL pour le code experimental, c´est tres pratique, mais ca tombait dans ma categorie de code "utilitaire" (mon contexte etant l´optim de code que tu qualifie de "destine a la production").

Pour revenir a ta question initiale, mes principales comparaisons se font avec des int ou des chaines de caracteres. Un de nos algo au taf les plus lent car tres mal designe est la creation de notre arbre des noms de fichiers, qui inclut de nombreux tests avec des chaines de caracteres et de tres nombreuses affectations et allocations memoire..

(HS, 36 15 mylife)

Pour eclaircir les choses, quand je dis que le code n´est pas destiné a la production, je veux dire qu´il ne tournera que pendant un temps relativment cours. Cela ne voulant pas dire qu´il consommera peu de temps CPU. Je parles ici de milliers d´heures CPU (ce qui représente en temps réel pour moi, moins de 3 jours).

Par contre, je passes assez peu de temps a les écrire. Donc je n´ai pas vraiment le temps de me pencher sur l´optimisation du code a proprement parler, une fois que le code fonctionne et s´exécute en temps acceptable, je le laisse tourner et je fais autre chose.

Merci pour les précisions.

j´utilise rarement la STL, j´aurais plutôt tendance à recoder systématiquement mes algo même si ce n´est pas le plus productif.

Quand je m´en sers, c´est dans des programmes plutôt "scientifique" dont je veux qu´ils tournent le plus vite possible, je veux dire que les parties mécaniques du code ne doivent pas être le gros de travail, donc je préfère me reposer sur des algo déjà écrit (et sans bogue) que sur mon code.

Dans ce cas là, je me sers surtout des structures de données type set, list ou map etc. Pour y stocker des structures perso (pour des tailles typiques de quelques dizaine d´octets, avec quelques millier ou dizaine de millier d´élément). Et là soit j´utilise juste les iterateur pour les parcourir, et alors des recherches d´éléments (mais rarement autre chose).

Globalement, même si j´utilise la STL dans des zone "critique", le temps de calcul est toujours largement dominé par les calculs que je mène sur mes données, donc la STL elle même ne me parait pas trop critique.

Personnellement, j´utilise (quasiment) systématiquement la STL.
J´ai déja recodé tous les algos dans les TP a la fac, mais personnellement, je ne pense pas avoir optimisé ça a mort (surtout les rééquilibrages d´arbres binaires, et autres algos du genre tres puissants, utilisés et optimisés par la STL)

Apres, de temps en temps, je me fais un semblant de liste chainée quand j´ai besoin (un pointeur next dans une structure...)

Mais c´est vrai que je suis "pro-STL"

je contribue avec mon point de vue, mais pour eviter les redites, je me contenterai d´aller dans le sens de Kufa ; meme approche de mon cote : STL pour les protos/outils/etc. , mais implementations persos pour le code de production d´appli time-critical