This is an old revision of the document!
Table of Contents
Partie I – Manipulations d’itérateurs
Question n°1
Nous nous intéressons typiquement à la fonction suivante définie sur un tableau dynamique :
#include <vector> // std::vector template <class T> int upper(std::vector<T> aVector, const T& theValue) { for (int i = 0; i < aVector.size(); i++) { if (aVector[i] > theValue) return i; } return -1; }
Cette fonction retourne l’indice du premier élément du tableau qui est plus grand que theValue.
Question n°1.1
Modifier cette fonction pour qu’elle fonctionne désormais avec des itérateurs et non plus un tableau.
Question n°1.2
Tester cette fonction avec le code suivant :
int testUpper() { int myints[] = { 10,20,30,30,20,10,10,20 }; std::vector<int> v(myints, myints + 8); std::vector<int>::iterator up = upper(v.begin(), v.end(), 20); std::cout << "first value greater than 20 at position " << (up - v.begin()) << '\n'; return 0; }
Le compilateur identifie int[] comme étant un int* qui se respecte les exigences définies par input iterator. Comme le tableau contient 8 éléments, myints+8 définit un pointeur qui pointe sur l'élément qui se trouverait à l'indice 8, soit myints[8]. Cependant, cet élément n'existe pas ! C'est bien un élément situé après le dernier élément dans le tableau myints qui est myints[8] et qui est référencé par le pointeur myints+7. En conséquence, myints+8 marque bien la fin de la séquence, puisque c'est l'itérateur qui suit le dernier itérateur valide de la séquence.
std::vector<int> v( /* pointeur sur le premier de la séquence */myints, /* pointeur sur l'élément qui serait situé après le dernier élément de la séquence */ myints + 8);
Donc nous initialisons ainsi un vecteur avec les valeurs provenant du tableau myints. Nous voyons aussi au passage que les pointeurs sont un cas particulier des itérateurs et que les itérateurs respectent les exigences définies par random access iterator.
Une fois ceci effectué, les lignes suivantes n'appellent pas de remarques particulières :
std::vector<int>::iterator up = upper(v.begin(), v.end(), 20); std::cout << "first value greater than 20 at position " << (up - v.begin()) << '\n';
à l'exception que l'itérateur up' ayant pour type std::vector<int>::iterator doit supporter l'opération - dite différence de position. Cette opération n'est pas disponible pour tous les types d'itérateurs . Elle n'est en fait que disponible pour les itérateurs qui respectent les exigences définies par random access iterator, ce qui est le cas pour l'itérateur de std::vector<int>::iterator défini dans std::vector.
Si nous souhaitons utiliser un autre containeur comme par exemple le containeur std::set, nous pouvons écrire le code suivant :
<code cpp>
std::set<int> intSet(v.begin(), v.end());
auto /* std::set<int>::iterator */upSet = upper(intSet.begin(), intSet.end(), 20);
</code>
Le mot-clé ''auto'' dit au compilateur d'inférer le type. Si nous ne mettons pas auto, nous aurions du écrire le type de l'itérateur qui est exposé par std::set, soit std::set<int>::iterator. Cependant, le compilateur n'est pas toujours en mesure d'inférer (de calculer) le type, dans ce cas, un message d'erreur sera généré et il vous appartiendra de soit fournir des informations complémentaires au compilateur permettant d'inférer le type ou au contraire de définir le type.
De plus, upSet est un itérateur de type bidirectional iterator. De fait upSet n'implante l'opération - dite distance qui n'est implanter que par les itérateurs étant des random access iterator.
Ceci fait que le code suivant :
<code cpp>
std::cout « “first value greater than 20 at position ”
« (setUp - intSet.begin()) « '\n';
</code>
ne compile pas puisque nous l'opération '-' n'est pas défini pour des objets de type std::set<int>::iterator.
Si nous souhaitons connaitre la position, il faudra compter le nombre de pas que nous devons effectuer en partant du premier élément contenu dans l'ensemble jusqu'à l'élément qui est référencé par l'itérateur setUp. Ce qui donne la boucle suivante :
<code cpp>
int position = 0; upSet - v.begin()
for(auto it = intSet.begin(); it != upSet; it++) { position ++; }
std::cout « “First value greater than 20 at position ”
« position « std::endl;
</code>
===== Question n°2 =====
Dans la STL, de nombreux algorithmes sont fournis dont notamment des algorithmes de tri. Ces algorithmes sont présents dans le fichier d’entête :
<code cpp>
#include <algorithm>
</code>
Nous trouvons par exemple l’algorithme de tri :
<code cpp>
template <class randomAccessIterator>
void sort(randomAccessIterator first, randomAccessIterator last);
</code>
ainsi que :
<code cpp>
template <class randomAccessIterator>
void sort_heap(randomAccessIterator first, randomAccessIterator last);
</code>
qui fournisse un tri rapide et tri sur le tas.
==== Question n°2.1 ====
Nous souhaitons déterminer la position du premier élément dans notre tableau qui est plus grand que 20 avec d’ordonner le tableau. Ceci correspond au code de la fonction définie à la question 1.2, et nous souhaitons ensuite déterminer la position du premier élément qui est plus grand que 20 après avoir ordonner le tableau.
Modifier le code de la fonction définie à la question 1.2 pour ajouter cette nouvelle opération en appelant soit la fonction sort soit la fonction sort_heap pour effectuer le tri de votre tableau.
<hidden Correction>
Les fonctions sort et sort_heap prennent en argument deux itérateurs dénotant une séquence, le premier itérateur faisant référence au premier élément de la séquence et le deuxième itérateur fait référence à l'itérateur correspondant au marqueur de fin de séquence.
Dans ce cas, l'appel pour un containeur standard que nous appelons sortcontainer sera :
<code cpp>
std::sort(container.begin(), container(end));
std::sort_heap(conta.begin(), container(end));
</code>
Pour chacune des fonctions, il est spécifié que l'itérateur doit être un randomIterator. En fait, plus spécifiquement, il doit respecter les deux contrats définis par random access iterator et par value is swappable.
Ceci signifie que l'itérateur peut fonctionner sur une structure de type std::vector qui expose bien un tel itérateur mais pas sur une structure de type std::set par exemple qui n'expose qu'un bidirectionnal iterator.
Pour un containeur de type std::vector, il est possible d'écrire le code suivant:
<code cpp>
#include<iostream>
#include“upper.h”
#include<vector>
#include<algorithm>
using namespace std;
int testSortAndUpper()
{
Appel de la fonction “upper' sur le vecteur en commençant par le premier élément
et en terminant avec le dernier.
std::vector<int>::iterator up = upper(v.begin(), v.end(), 20);
std::cout « “First value greater than 20 at position ”
« (up - v.begin()) « std::endl;
Appel de la fonction de tri
std::sort(v.begin(), v.end());
Appel ensuite de la fonction sort_heapupper sur le vecteur.
up = upper(v.begin(), v.end(), 20);
std::cout « “First value greater than 20 at position ”
« (up - v.begin()) « std::endl;
}
int testSortHeapAndUpper()
{
Appel de la fonction “upper' sur le vecteur en commençant par le premier élément
et en terminant avec le dernier.
std::vector<int>::iterator up = upper(v.begin(), v.end(), 20);
std::cout « “First value greater than 20 at position ”
« (up - v.begin()) « std::endl;
Appel de la fonction de tri
std::sort_heap(v.begin(), v.end());
Appel ensuite de la fonction upper sur le vecteur.
up = upper(v.begin(), v.end(), 20);
std::cout « “First value greater than 20 at position ”
« (up - v.begin()) « std::endl;
}
int main()
{
testSortAndUpper();
testSortHeapAndUpper();
return 0;
}
</code>
</hidden>
