Standard Template Library - Définition

Introduction

La Standard Template Library (STL) est une bibliothèque C++, normalisée par l'ISO (document ISO/CEI 14882) et mise en oeuvre à 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.