Standard Template Library - Définition

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

Cette bibliothèque fournit :

• un ensemble de classes conteneurs, tel que les vecteurs, les tableaux associatifs, les listes chaînées, 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 iterators. 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 le 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 du 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 le 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 du 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 le 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.

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 90, 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, 10 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