8. Classes et fonctions paramétrables, Librairie Standard du C++ (STL)

Question 1

Les templates

Answer 1

permettent de spécifier dans un seul bout de code un ensemble de fonctions ou de classes surchargées (par leur type).

Question 2

Processus pour obtenir une classe utilisable à partir d’une template

Answer 2

l’instanciation de la template.

Question 3

Les classes et fonctions paramétrables seront utiles pour

Answer 3

toutes les abstractions dont le comportement ne change pas en fonction du type.

Question 4

Les méthodes ne sont plus dans

Answer 4

un fichier .cpp mais dans le .h après la déclaration de la classe ou dans un .hpp inclut par le .h.

Question 5

Classes patron

Answer 5

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>

Question 6

Fonctions patron

comportement est similaire avec

Answer 6

les fonctions :
chaque appel d’un patron de fonction avec de nouveaux types d’arguments compile une nouvelle fonction patron.

Question 7

L’approche STL

Answer 7

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.

Question 8

Composantes principales de STL:

Answer 8

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.

Question 9

itérateurs

Answer 9

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.

Question 10

Comme avec les pointeurs sur un vecteur C++, l’itérateur peut être

Answer 10

incrémenté ou décrémenté pour parcourir le conteneur (iter++ ou iter–).

Question 11

Hiérarchie des itérateurs

Answer 11

accès aléatoire
bidirectionel
unidicrectionel avant
d’entrée(lecture)/de sortie(écriture)

Question 12

Itérateur inverse

Answer 12

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.

Question 13

adaptateurs

Answer 13

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.

Question 14

3 types d’itérateurs d’insertion:

Answer 14

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.

Question 15

STL

Answer 15

librairie standard de patrons

Question 16

vector

Answer 16

bloc de mémoire contigu
accès aléatoire aux éléments
insertions optimisées à la fin

Question 17

deque

Answer 17

«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

Question 18

list

Answer 18

liste doublement chaînée,
blocs de mémoire indépendants accès séquentielle aux éléments
insertions et retraits performants partout

Question 19

types de séquence

Answer 19

vector deque list

Question 20

type d’association

Answer 20

set multiset map multimap

Question 21

type d’adaptateur

Answer 21

stack queue priority queue

Question 22

set

Answer 22

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

Question 23

multiset

Answer 23

ensemble ordonné accepte le dédoublement d’éléments dans la collection.

Question 24

map

Answer 24

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

Question 25

multimap

Answer 25

dictionnaire
accepte le dédoublement des entrées dans la collection

Question 26

stack

Answer 26

implantation d’une pile utilisant une séquence (deque par défaut) insertions et retraits performants
insertions et retraits sur le dessus.

Question 27

queue

Answer 27

implantation d’une file utilisant une list ou deque
insertions et retraits performants
insertions derrière et retraits devant

Question 28

priority queue

Answer 28

implantation d’une file à priorité utilisant une deque
accès performants
retrait de la plus grande valeur

Question 29

Comment accéder les valeurs?

Answer 29

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é

Question 30

Ordre dans la collection important?

Answer 30

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.

Question 31

Dimension variable?

Answer 31

Si les dimensions varient beaucoup :
olist ou set

Si les dimensions demeurent relativement
fixes :
ovector et deque

Question 32

Estimer la dimension apriori?

Answer 32

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.

Question 33

Tester la présence d’un élément?

Answer 33

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…

Question 34

Collection indexée ou paire/valeur?

Answer 34

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.

Question 35

Position des insertions et des retraits

Answer 35

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

Question 36

Les algorithmes génériques

Answer 36

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.

Question 37

avantage

Answer 37

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…

Question 38

limite

Answer 38

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.