8. Classes et fonctions paramétrables, Librairie Standard du C++ (STL) Flashcards
Les templates
permettent de spécifier dans un seul bout de code un ensemble de fonctions ou de classes surchargées (par leur type).
Processus pour obtenir une classe utilisable à partir d’une template
l’instanciation de la template.
Les classes et fonctions paramétrables seront utiles pour
toutes les abstractions dont le comportement ne change pas en fonction du type.
Les méthodes ne sont plus dans
un fichier .cpp mais dans le .h après la déclaration de la classe ou dans un .hpp inclut par le .h.
Classes patron
patron de classe utilisé avec de nouveaux arguments nouvelle classe patron compilée.
déclaration d’un objet de type std::vector<int> et d'un autre de type std::vector<double>
Instanciation de deux classes différentes.
Les objets seront de types différents,
Aucun lien entre les deux (pas même une conversion).</double></int>
Fonctions patron
comportement est similaire avec
les fonctions :
chaque appel d’un patron de fonction avec de nouveaux types d’arguments compile une nouvelle fonction patron.
L’approche STL
Indépendance des algorithmes envers les conteneurs.
Beaucoup d’algorithmes ne dépendent pas d’une implémentation particulière d’une structure de données.
Propriétés fondamentales communes à plusieurs structures de données:
opasser d’un élément à l’autre du début à la fin du conteneur.
Composantes principales de STL:
Algorithmes: définir des procédures de
traitement.
Conteneurs: gérer un ensemble d’espaces
mémoire selon les structures de données.
Itérateurs: procurer à un algorithme une façon
de traverser un conteneur.
itérateurs
Un intervalle spécifié ne contient jamais la borne supérieure:
Ex.: [x, x+10] où x+10 désigne l’endroit passé la fin de l’intervalle.
Les conteneurs définissent un itérateur spécial pour désigner «passé-la- fin» du conteneur.
end() retourne un itérateur pointant à «passé-la-fin» du conteneur.
begin() retourne l’élément de début du conteneur.
Comme avec les pointeurs sur un vecteur C++, l’itérateur peut être
incrémenté ou décrémenté pour parcourir le conteneur (iter++ ou iter–).
Hiérarchie des itérateurs
accès aléatoire
bidirectionel
unidicrectionel avant
d’entrée(lecture)/de sortie(écriture)
Itérateur inverse
parcours des éléments dans l’ordre inverse.
rbegin() et rend() retournent des itérateurs inverses.
o Le premier élément de la séquence sera le dernier et le dernier sera le premier.
Incrémenter fait avancer à rebours dans la séquence.
adaptateurs
permet de transformer un itérateur de sortie en itérateur qui insère des éléments au lieu d’écraser les éléments existants dans un contenant.
3 types d’itérateurs d’insertion:
ol’itérateur front_inserter
insère un élément au début d’un contenant.
ol’itérateur back_inserter
insère un élément à la fin d’un contenant.
ol’itérateur inserter
insère dans un contenant à l’endroit désigné par l’itérateur
passé en argument.
STL
librairie standard de patrons
vector
bloc de mémoire contigu
accès aléatoire aux éléments
insertions optimisées à la fin
deque
«double end queue» prononcé «deck» blocs de mémoire contigus
accès aléatoire aux éléments
insertions optimisées au début ou à la fin
list
liste doublement chaînée,
blocs de mémoire indépendants accès séquentielle aux éléments
insertions et retraits performants partout
types de séquence
vector deque list
type d’association
set multiset map multimap
type d’adaptateur
stack queue priority queue
set
ensemble ordonné
tous les éléments doivent être différents test d’inclusion très performant insertions et retraits performants
possibilité de parcourir séquentiel
multiset
ensemble ordonné accepte le dédoublement d’éléments dans la collection.
map
dictionnaire associant des couples clé/définition toutes les entrées doivent être différentes
test d’inclusion très performant
insertions et retraits performants
possibilité de parcourt séquentiel
multimap
dictionnaire
accepte le dédoublement des entrées dans la collection
stack
implantation d’une pile utilisant une séquence (deque par défaut) insertions et retraits performants
insertions et retraits sur le dessus.
queue
implantation d’une file utilisant une list ou deque
insertions et retraits performants
insertions derrière et retraits devant
priority queue
implantation d’une file à priorité utilisant une deque
accès performants
retrait de la plus grande valeur
Comment accéder les valeurs?
Si l’accès aléatoire est important
vector ou deque
Si l’accès séquentiel est suffisant
un des autres conteneurs peut être adapté
Ordre dans la collection important?
Le conteneur set maintient l’ordre des éléments dans la collection en tout temps.
Appliquer un algorithme de tri après l’insertion en utilisant un vector ou une list pour ordre à un moment donné.
Si l’ordre dans la collection est lié à l’ordre d’insertion,
bons choix : conteneur list ou un adapteur stack, queue.
Dimension variable?
Si les dimensions varient beaucoup :
olist ou set
Si les dimensions demeurent relativement
fixes :
ovector et deque
Estimer la dimension apriori?
Si on connaît la dimension qu’atteindra un
contenant,
seul le vector permet une pré-allocation d’un
bloc de mémoire de la bonne dimension.
Tester la présence d’un élément?
Si on doit fréquemment tester la présence d’un
élément dans la collection,
bons choix : set ou map
La recherche sur ces conteneurs est très efficace alors que sur un vector par exemple, la recherche peut signifier comparer tous les éléments de la collection…
Collection indexée ou paire/valeur?
Si les clés sont un nombre entre 0 et une
borne supérieure,
utiliser un vector ou un deque.
Dans le cas où la clé est autre chose (caractère, chaîne, type quelconque),
utiliser un map.
Position des insertions et des retraits
Si les valeurs doivent être insérées et retirées dans le milieu de la collection,
meilleur choix : list
Si les valeurs sont insérées au début,
deque ou list
Si les ajouts et les retraits sont faits à la fin,
bon choix : vector ou l’adapteur stack
Les algorithmes génériques
Les algorithmes fournis avec STL sont découplés du
conteneur sur lequel ils agissent
o
utilisation des itérateurs.
Tous les conteneurs dans la même catégorie peuvent
utiliser les mêmes algorithmes.
avantage
La librairie STL est extensible:
oles algorithmes existants fonctionneront sur les nouveaux conteneurs à venir.
oles conteneurs existants supporteront les
nouveaux algorithmes écrits par l’usager.
ode nouveaux algorithmes pourront être écrits et fonctionner sur tous les conteneurs présents et à venir…
limite
Important : connaître et comprendre les exigences et les
limites de composants de la librairie.
ointervalles spécifiés par deux itérateurs de source différente.
oitérateurs invalidés par une insertion ou un retrait dans le
conteneur.
