Standard Template Library

Pour les articles homonymes, voir STL.

La Standard Template Library (STL) est une bibliothèque C++, normalisée par l'ISO (document ISO/CEI 14882) et mise en œuvre à l'aide des templates.

Cette bibliothèque fournit :

• un ensemble de classes conteneurs, telles que les vecteurs (vector), les tableaux associatifs (map), les listes chaînées (list), qui peuvent être utilisées pour contenir n'importe quel type de données à condition qu'il supporte certaines opérations comme la copie et l'assignation.
• une abstraction des pointeurs : les itérateurs. Ceux-ci fournissent un moyen simple et élégant de parcourir des séquences d'objets et permettent la description d'algorithmes indépendamment de toute structure de données.
• des algorithmes génériques tels que des algorithmes d'insertion/suppression, recherche et tri.
• une classe string permettant de gérer efficacement et de manière sûre les chaînes de caractères.

Historique

L'architecture de la bibliothèque STL a été créée en grande partie par une seule personne, Alexander Stepanov. En 1979, il commença à mettre en forme ses premières idées de programmation générique, une technique révolutionnaire dans le domaine du développement logiciel. Bien que Dave Musser ait formulé certains aspects de la programmation générique dès 1971, ceux-ci restaient limités, à l'époque, au champ très spécialisé de l'algèbre informatique.

Stepanov sut reconnaître le potentiel de la programmation générique et persuada ses collègues de General Electric (dont, initialement, Dave Musser et Deepak Kapur) de creuser le concept pour en faire l'une des bases du développement de logiciel. À cette époque, aucun langage de programmation ne proposait de réel support pour cette nouvelle méthode de programmation générique.

Ada fut le premier langage important à fournir ce support, avec son unité générique. Stepanov et Musser développèrent et publièrent une bibliothèque Ada, disponible dès 1987, dédiée aux calculs utilisant des listes. Celle-ci incluait une grande partie de leur recherche sur la programmation générique. Cependant, Ada ne parvint pas réellement à dépasser le cadre de l'industrie de défense, et C++, malgré son manque de maturité, se dégagea rapidement comme un langage à la fois adapté à la programmation générique et susceptible d'être diffusé plus largement. Un des autres avantages de C++ réside dans son modèle de calcul, qui permet un accès très souple à une zone de stockage mémoire, à travers les pointeurs. Cela permet d'obtenir du code très général sans perdre en efficacité.

De nombreuses recherches furent nécessaires pour développer, non pas des composants individuels, mais l'architecture d'une bibliothèque complète basée sur la programmation générique. D'abord aux Laboratoire AT&T de Bell, puis au Centre de Recherche Hewlett-Packard, Stepanov essaya différentes architectures et implémentations d'algorithmes, en C puis en C++. Musser participa à cette recherche, et en 1992, Meng Lee rejoignit le projet de Stepanov chez HP et devint l'un des principaux contributeurs.

Ce travail aurait probablement été poursuivi un certain temps comme un simple projet de recherche et aurait amené à une bibliothèque propriétaire HP, si Andrew Koenig, au courant du projet, n'avait pas demandé à Stepanov de présenter ses idées lors d'une conférence du comité ANSI/ISO, en novembre 1993. Le comité, qui s'était réuni pour normaliser C++, répondit très favorablement et demanda, par l'intermédiaire de Koenig, un avant-projet officiel pour la réunion de mars 1994. Malgré un délai extrêmement court, Stepanov et Lee réussirent à fournir une première proposition, qui reçut l'approbation préliminaire du comité lors de la réunion de mars.

Le comité demanda cependant plusieurs changements et extensions (dont certains importants), et un petit groupe de membres rencontra Stepanov et Lee pour les aider à détailler certaines caractéristiques. En particulier, il fallait montrer la cohérence de l'une des extensions les plus significatives (les conteneurs associatifs) en les implémentant entièrement, ce que Stepanov délégua à Musser. C'est sans doute l'une des phases du projet qui aurait pu facilement devenir incontrôlable, mais là encore, Stepanov releva le défi et fit une proposition complète, approuvée définitivement par le comité ANSI/ISO en juillet 1994. On trouvera des détails supplémentaires sur cette histoire dans un interview qu'Alexander Stepanov donna en mars 1995 dans le Dr. Dobb's Journal.

Le document 17 de Stepanov et Lee fut alors incorporé dans l'avant-projet de la norme ANSI/ISO C++ (1, une partie des articles 17 à 27). Cela influença d'autres parties de la bibliothèque standard C++, en particulier les fonctions de manipulation de chaînes (objet string de C++), et certains standards adoptés auparavant furent modifiés en conséquence.

Malgré le succès de la STL auprès du comité, il restait la question de sa diffusion et de son utilisation pratique. Les diffuseurs de compilateur et de bibliothèques logicielles indépendantes pouvaient bien sûr développer leur propre implémentation de la STL, en se basant sur l'avant-projet de norme désormais public, et vendre cette implémentation, soit comme produit à part entière, soit comme partie intégrante d'un de leur produit. Atul Saini fut l'un des premiers éditeurs à reconnaître le potentiel commercial de la STL. Il commença à l'étudier comme ligne de développement économique pour son entreprise Modena Software Incorporated avant même que la STL soit complètement acceptée par le comité.

Les perspectives de large diffusion de la STL augmentèrent considérablement lorsque Hewlett-Packard décida, en août 1994, de rendre disponible gratuitement sur Internet sa propre implémentation. Celle-ci, développée par Stepanov, Lee et Musser au cours de la normalisation avec l'ANSI/ISO, devint la base de toutes les implémentations proposées aujourd'hui par les diffuseurs de compilateurs et de bibliothèques logicielles.

Implémentation actuelle

La bibliothèque STL est principalement un ensemble d'objets et de méthodes standards pour C++. La norme ANSI/ISO précise les fonctionnalités de ces différents objets, mais pas la façon concrète dont ceux-ci doivent être implémentés. Pour cette raison, il existe de nombreuses bibliothèques STL différentes. Elles fournissent toutes un support des objets et algorithmes définis comme standards, et apportent pour la plupart un certain nombre d'extensions qui ne sont, à l'heure actuelle, pas reconnus comme standards par la norme. Cette multiplicité d'implémentations est similaire à celle qui existe au niveau des compilateurs.

Du point de vue des licences, la norme elle-même n'est soumise à aucun copyright, et tout le monde est donc libre de développer sa propre implémentation de la bibliothèque STL. Par contre, l'implémentation elle-même de la bibliothèque peut être ou non soumise à une licence, éventuellement propriétaire.

L'une des implémentations les plus diffusées de la bibliothèque STL a été développée historiquement par Hewlett-Packard, puis par Silicon Graphics. Cette implémentation est « libre de droit », sous copyright, c'est-à-dire que l'on peut la copier, la distribuer et la modifier, mais que l'on ne peut pas se réclamer en être l'auteur.

Il existe aussi une implémentation de la STL en licence GNU. Dans les différentes distributions Linux, elle est incluse dans le paquet libstdc++.

Performances

La question des performances nécessite de définir avant tout ce que l'on entend par programme performant en informatique. En effet, la seule rapidité du code compilé résultant n'est plus un critère absolu pour évaluer un programme. Il est nécessaire de prendre également en compte la qualité du code C++, c'est-à-dire sa facilité de compréhension, de maintenance et de réutilisation, ainsi que la compatibilité du code avec les différents compilateurs disponibles.

Qualité du code

Le principal apport de la STL, c'est un code C++ normalisé pour certains objets classiques, garantissant ainsi un code source lisible, facilement réutilisable.

Parallélisation

Les algorithmes présentés par les STL ne spécifient pas explicitement un ordre d'exécution. La tentation est donc grande de les exécuter de façon parallèle. Par exemple, la norme, à propos de std::for_each, ne précise pas si les éléments doivent être traités en ordre séquentiel. Un autre cas évident est le tri (std::sort) à la complexité de O(n.log(n)), donc très consommateur de temps CPU.

Bien que le problème soit complexe comme tout ce qui touche au parallélisme, il y a actuellement plusieurs approches distinctes:

• STAPL propose des conteneurs distribués, adaptés au traitement parallèle (évitant les phénomènes d'effondrement), tout en étant utilisable dans un contexte séquentiel.
• Multi Processing Template Library (MPTL) s'appuie en revanche davantage sur le code existant.
• Architecture Objet Evolutive pour le Calcul Parallèle sur les Tableaux, et notamment le projet Paradeis, « une extension de la STL pour le calcul parallèle creux ».
• Range Partition Adaptors (RPA), inspiré d'une note de Alexander Stepanov et Matthew Austen pousse encore plus loin cette démarche de réutilisation des programmes séquentiels et composants existants (conteneurs, algorithmes séquentiels optimisés et spécialisations de templates, optimisations dépendantes du système d'exploitation, etc.) intégrés dans un framework multitâche.
• Threading Building Blocks (TBB), bibliothèque de Intel, propose plusieurs algorithmes intrinsèquement parallèles (parallel_for, parallel_while, parallel_reduce) ainsi que des conteneurs destinés au traitement parallèle (concurrent_queue), dans une certaine mesure compatible avec la STL.
• Gnu g++ libstdc++ parallel mode: Une implémentation des STL utilisant OpenMP. De nombreux algorithmes en lecture seule (count), ou bien ne modifiant pas l'ordre des séquences (transform, replace), sont proposés. Cette bibliothèque souffre toutefois des limites d'OpenMP, à savoir une restriction aux itérateurs random_access.

Le problème devenant plus sensible compte tenu de l'apparition de microprocesseur multi cœur, et de la stagnation de leur fréquence d'horloge (« The free lunch is over », interview de Herb Sutter), ces solutions sont en évolution constante. On remarquera dans les évolutions possible du standard de C++ : A Proposal to Add Parallel Iteration to the Standard Library

Compatibilité avec les compilateurs existants

La bibliothèque STL utilise massivement l'ensemble des possibilités du langage C++, en particulier les modèles de classes (template). Dans les années 1990, lors des premières diffusions de la STL, la prise en charge par les compilateurs souffrait de problèmes de compatibilités diverses et il n'était pas rare que la compilation d'un code valide échoue. Cependant, dix ans plus tard, on peut considérer que les diverses implémentations de la STL sont d'excellente qualité, entièrement compatibles avec les compilateurs existants.

L'utilisation des templates entraîne cependant des temps de compilation importants. Bien qu'en constante amélioration, cette limitation est l'une des seules réserves actuellement formulée contre la STL.

Exemples de programme

// Met dans le vecteur v1 la seconde moitié du vecteur v2
v1.assign(v2.begin() + v2.size() / 2, v2.end());
 
// Applique la fonction test à chaque membre de v1
for_each(v1.begin(), v1.end(), test);

Diagramme des conteneurs

Voir aussi

Article connexe

• C++
• Oracle Template Library, une bibliothèque logicielle de manipulation de Base de données relationnelle basée sur le style de programmation de la STL.
• Boost.

Liens externes

• (en) Référence de la STL
• (en) Catégorie STL de l’annuaire dmoz