Programmation C++/La librairie standard
Un livre de Wikibooks.
[modifier] La STL
La STL (Standard Template Library) a été mise au point par Alexander Stepanov et Meng Lee. La STL a été proposée au comité ISO de standardisation du C++ qui l'a acceptée en juillet 1994. Les résultats des travaux de recherche ont été publiés officiellement dans un rapport technique en novembre 1995. Ces travaux de recherche ont été une avancée majeure pour le C++, qui était aussi à l'époque le seul langage capable d'offrir les mécanismes de programmation générique nécessaires à la mise au point de cette bibliothèque. Elle a d'ailleurs influencé les autres parties de la future bibliothèque du C++ (notamment la future classe string) et aussi l'évolution du langage.
La STL est axée autour de trois grands thèmes:
- Les conteneurs: ce sont les structures de données classiques de l'algorithmique, à savoir les tableaux à accès direct, les listes chaînées, les piles, les files, les ensembles, les dictionaires. Dans sa version initiale, elle ne contiennent pas les tables de hachage, qui ne seront d'ailleurs pas présents dans ISO C++98.
- Les algorithmes: ce sont les algorithmes classiques de l'algorithmique, essentiellement les algorithmes de tri et de recherche
- Les itérateurs: c'est une généralisation du concept de pointeur. D'ailleurs un pointeur est un itérateur particulier. Les itérateurs ont l'avantage de pouvoir parcourir un conteneur sans que ce parcours ne fasse partie de l'état interne du conteneur.
La force de la STL réside dans le fait de pouvoir offrir des conteneurs pouvant accueillir n'importe quel type moyennant quelques contraintes sémantiques qui peuvent varier selon le type conteneur et surtout dans le fait que les algorithmes sont complètement découplés des conteneurs (même si certains conteneurs offrent parfois leur propre algorithme pour des besoins d'optimisation et de performances. Par exemple, le conteneur list a une méthode sort).
[modifier] Les conteneurs
En c++, les conteneurs sont des classes offrant au programmeur une implémentation permettant de gérer des collections dynamiques d'objets du même type (on parle de conteneurs homogènes), c'est à dire pour lesquels le nombre d'objets contenus peut varier à l'exécution. Les conteneurs sont implémentés dans la bibliothèque standard en tant que modèles de classe (templates), ce qui permet de les utiliser avec n'importe quel type d'objets, standard ou défini par le programmeur (à l'exception de bitset).
De plus les conteneurs sont conçus de manière à être compatible avec les algorithmes de la bibliothèque standard.
Comme toute classe standard, il faut les inclure avec un en-tête (header) spécifique, qui est souvent le nom de la classe avec des < > autour. Exemple : pour utiliser la classe vector il faut préciser dans le programme un #include <vector> .
Pour leur présentation il est d'usage de les séparer en trois catégories :
[modifier] Les conteneurs séquentiels
Ils offrent des fonctionnalités suffisantes de base pour gérer simplement des collections d'objets. Tous permettent une insertion et un accès à tous les éléments par des itérateurs.
Il s'agit de vector, deque, list et bitset.
vector est un tableau dynamique où il est particulièrement aisé d'accéder directement aux divers éléments par un index, et d'en ajouter ou en retirer à la fin. A la manière des tableaux de type C, l'espace mémoire alloué pour un objet de type vector est toujours continu, ce qui permet des algorithmes rapides d'accès aux divers éléments. A noter qu'il existe une version spéciale de vector, vector<bool>, spécialement conçue pour économiser de la mémoire
deque (de "Double ended queue", file à double entrée) ressemble beaucoup à vector, mis à part qu'il est tout aussi efficace d'y insérer ou de supprimer des éléments au début de la liste. De plus, les éléments contenus ne sont pas forcément stockés de manière contigüe en mémoire, ce qui permet d'éviter de lourdes réallocations lors de changements importants dans le conteneur s'il est grand.
list est une liste doublement chainée. L'insertion et la suppression d'élément ou de groupes continus d'éléments y est efficace partout dans la liste, mais il n'est pas possible d'accéder directement (par un index) aux différents éléments. On est forcé de les parcourir avec les itérateurs. De la meme manière que deque, une liste chaînée ne voit pas ses differents éléments stockés en mémoire continument.
bitset est un cas particulier de conteneur. On peut l'assimiler à un tableau classique de bool. Le chiffre binaire étant la plus petite unité de mémoire possible, alors que le type de base du c++ le plus petit (char) est de taille 8 bits (habituellement), ces tableaux sont donc particulièrement optimisés pour stocker et manipuler une grande quantité d'informations qui peuvent être traduites par 1 ou quelques bits seulement.
[modifier] Les conteneurs associatifs
Les conteneurs associatifs supposent l'utilisation d'une "clé de recherche" (un numéro d'identification, ou des chaines classées par ordre alphabétique par exemple) et implémentent des fonctions efficaces de tri et de recherche. Ils sont habituellement triés continuellement (lors de chaque insertion d'éléments).
Il s'agit de set, multiset, map, multimap
set ne contient que des objets du type clé de recherche tandis que map contient des clés associées avec un autre objet de type différent (exemple : Les numéros de téléphone dans un annuaire sont triés selon le nom de l'abonné correspondant au numéro). Toutes les clés sont supposées uniques.
Les conteneurs multiset et multimap sont les versions correspondantes qui autorisent la présence de plusieurs clés identiques (avec des algorithmes correspondants nécessairement un peu moins performants).
[modifier] Les adaptateurs de conteneurs
Les adaptateurs de conteneurs ne s'utilisent qu'en complément à un des conteneurs précédents, afin de lui ajouter des fonctionnalités plus précises.
Il s'agit de stack, queue, priority_queue
stack implémente une interface de pile (LIFO, Last In First Out : dernier arrivé, premier sorti).
queue implémente un interface de file d'attente (FIFO, First In First Out : premier arrivé premier sorti).
priority_queue implémente un interface de file d'attente où les éléments peuvent être comparés entre eux (par niveau de priorité), et sont classés dans la file suivant l'ordre spécifié. Ainsi elle permettent de traiter des données suivant des niveaux de priorité de manière efficace.
[modifier] Les algorithmes
[modifier] Les algorithmes de séquences non modifiants
- for_each
- find
- find_if
- find_end
- find_first_of
- adjacent_find
- count
- count_if
- mismatch
- equal
- search
- search_n
[modifier] Les algorithmes de séquences modifiants
[modifier] copies
- copy
- copy_backward
[modifier] échanges
- swap
- swap_ranges
- iter_swap
[modifier] transformations
- transform
[modifier] remplacements
- replace
- replace_if
- replace_copy
- replace_copy_if
[modifier] remplissages
- fill
- fill_n
[modifier] générations
- generate
- generate_n
[modifier] suppressions
- remove
- remove_if
- remove_copy
- remove_copy_if
[modifier] éléments uniques
- unique
- unique_copy
[modifier] ordre inverse
- reverse
- reverse_copy
[modifier] rotations
- rotate
- rotate_copy
[modifier] permutations aléatoires
- random_shuffle
[modifier] répartitions
- partition
- stable_partition
[modifier] Les algorithmes de tri et les opérations apparentées
[modifier] tris
- sort
- stable_sort
- partial_sort
- partial_sort_copy
- nth_element
[modifier] recherches dichotomiques
- lower_bound
- upper_bound
- equal_range
- binary_search
[modifier] fusions
- merge
- inplace_merge
[modifier] opérations d'ensemble
- includes
- set_union
- set_intersection
- set_difference
- set_symmetric_difference
[modifier] opérations de tas
- push_heap
- pop_heap
- maxmake_heap
- sort_heap
[modifier] minimum et maximum
- min
- max
- min_element
- max_element
- lexicographical_compare
[modifier] permutations
- next_permutation
- prev_permutation
[modifier] Les chaînes de caractères
[modifier] La classe string
[modifier] Les chaînes de caractères de type C
Le header cstring défini un certain nombre de fonction permettant la manipulation de chaînes de caractères de type C.
[modifier] memcpy
[modifier] memmove
[modifier] strcpy
[modifier] strncpy
[modifier] strcat
[modifier] strncat
[modifier] memcmp
[modifier] strcmp
[modifier] strcoll
[modifier] strncmp
[modifier] strxfrm
[modifier] strcspn
[modifier] strspn
[modifier] strtok
[modifier] memset
[modifier] strerror
[modifier] strlen
int strlen(char *str) { int i; i = 0; while(str[i] != '\0') i++; return (i); }
[modifier] memchr
char *pch; int pospex;
pch = (char*) memchr (Trame, '!', strlen(Trame)); if(pch!=NULL) {
pospex = pch - Trame;
}
[modifier] memchr(void* p, int c, size_t n)
memchr scrute les n premiers octets de p à la recherche du caractère c.
- Valeur renvoyée :
si succès, renvoie un pointeur sur la première occurrence de c dans p, sinon, renvoie NULL.
