====== Partie I – Manipulations d’itérateurs======

[[in204:tds:sujets:td4|TD4]]

===== Question n°1 =====

Nous nous intéressons typiquement à la fonction suivante définie sur un tableau dynamique :

<code cpp>
#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;
}
</code>

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.

<hidden Correction>

Dans la fonction précédente, nous souhaitons remplacer le type ''std::vector<T>'' par des itérateurs délimitant la séquence d'éléments.

Dans ce cas, la fonction prendrait en arguments, trois arguments :

  - l'itérateur ''theBeginIterator'' faisant référence au premier élément de la séquence,
  - l'itérateur ''theEndIterator'' faisant référence à l'itérateur marquant la fin de la séquence (ie. l'itérateur correspondant à l'itérateur obtenue en appliquant l'opérateur ''++'' sur l'itérateur faisant référence au dernier élément de la séquence),
  - une valeur ''aValue'' de référence qui défénit la valeur pivot.

La fonction accède aux éléments stockés dans le containeur de manière linéaire, en commençant par le premier élément et en continuant avec le deuxième, puis le troisième et ainsi de suite jusqu'à atteindre le dernier élément de la séquence. 

De ce fait, l'itérateur est supposé respecter que le contrat dénomé [[https://en.cppreference.com/w/cpp/named_req/InputIterator|LegacyInputIterator]]. En fait, c'est le contrat définissant les exigences minimales et en conséquence si nous définissons un algorithme qui se contente de ces contraintes minimale, il est possible de l'utiliser avec l'ensemble des containeurs qui sont définis conformément aux exigences de la STL de C++.

Dans ce cas, nous avons deux paramètres de type pour la fonction:

  - le paramètre de type ''inputIterator'' correspondant au type des itérateurs ''theBeginIterator'' et ''theEndIterator'',
  - le paramètre de type ''T'' correspondant au type des valeurs pivots.

La fonction ''upper'' retournait la position de la première valeur qui est plus grande que la valeur ''aValue'' ou ''-1'' si toutes les valeurs sont plus petites. La généralisation à des itérateurs doit fournir les mêmes résultats. Pour la valeur la première valeur plus grande, il peut être retourné l'itérateur faisant référence à la première valeur la plus grande. Si aucune valeur n'est plus grande que la valeur ''aValue'', il faut effectivement retourner un itérateur qui soit ''invalide''. En fait, le seul itérateur qui ne désigne pas une valeur dans la séquence [''theBeginIterator'', ''theEndIterator''( est l'itérateur ''theEndIterator'' qui désigne l'itéarateur marquant la fin de la séquence, donc faisant référence à quelque chose qui n'est plus dans la séquence. 

Par similitude, la fonction ''upper'' retournera donc :
  * l'itérateur faisant référence à la première valeur qui est plus grande que la valeur ''aValue'',
  * l'itérateur ''theEndIterator'' si aucune valeur dans la séquence n'est plus grande que la valeur ''aValue''.

Ceci permet déslors de réécrire l'entête de la fonction comme suit :
<code cpp>
template<class inputIterator, class T>
inputIterator upper(inputIterator theBeginIterator, inputIterator theEndIterator, const T& aValue)
</code>

Dans le code, les éléments sont accèder de manière successive tant que l'itérateur ''theBeginIterator'' est différent de l'itérateur marquant la fin de la séquence. Ceci amène la reformulation du code de la fonction comme suit :

<code cpp>
template<class inputIterator, class T>
inputIterator upper(inputIterator theBeginIterator, inputIterator theEndIterator, const T& aValue)
{
    for(;theBeginIterator != theEndIterator; theBeginIterator ++)
    {
        if(*theBeginIterator > theValue)
            return theBeginIterator;
    }
    return theEndIterator;
}
</code>
</hidden>

==== Question n°1.2 ==== 
Tester cette fonction avec le code suivant :

<code cpp>
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;
}
</code>
<hidden Explication & correction>


<code cpp>
	int myints[] = { 10,20,30,30,20,10,10,20 };
</code>

déclare un tableau contenant 8 éléments. ''myints'' correspond à un pointeur pointant sur l'addresse du premier élément du tableau soit ''10''.

<code cpp>
	std::vector<int> v(myints, myints + 8);
</code>

construit un containeur de type [[https://en.cppreference.com/w/cpp/container/vector|std::vector]] à partir d'une séquence d'élément en appelant le constructeur suivant :
<code cpp>
template< class InputIt >
vector( InputIt first, InputIt last,
        const Allocator& alloc = Allocator() );
</code>

Le compilateur identifie ''int[]'' comme étant un ''int*'' qui se respecte les exigences définies par  [[https://en.cppreference.com/w/cpp/named_req/InputIterator|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.

<code cpp>
	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);
</code>

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 [[https://en.cppreference.com/w/cpp/named_req/RandomAccessIterator|random access iterator]].

Une fois ceci effectué, les lignes suivantes n'appellent pas de remarques particulières :
<code cpp>
	std::vector<int>::iterator up = upper(v.begin(), v.end(), 20); 
	std::cout << "first value greater than 20  at position " 
            << (up - v.begin()) << '\n';
</code>

à 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 [[https://en.cppreference.com/w/cpp/named_req/RandomAccessIterator|random access iterator]], ce qui est le cas pour l'itérateur de ''std::vector<int>::iterator'' défini dans [[https://en.cppreference.com/w/cpp/container/vector|std::vector]].

Si nous souhaitons utiliser un autre containeur comme par exemple le containeur [[https://en.cppreference.com/w/cpp/container/set|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é [[in204:cpp:syntax:type:inference|''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 [[https://en.cppreference.com/w/cpp/container/set|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 [[https://en.cppreference.com/w/cpp/named_req/BidirectionalIterator|bidirectional iterator]]. De fait ''upSet'' n'implante l'opération ''-'' dite distance qui n'est implanter que par les itérateurs étant des [[https://en.cppreference.com/w/cpp/named_req/RandomAccessIterator|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>

En fait, cette boucle peut-être effectuée par un appel à la fonction  [[https://en.cppreference.com/w/cpp/iterator/distance|std::distance]] définie dans le fichie d'entête [[https://en.cppreference.com/w/cpp/header/algorithm|<algorithm>]], ce qui réduit le code précédent à :
<code cpp>
	std::set<int> intSet(v.begin(), v.end());
	auto upSet = upper(intSet.begin(), intSet.end(), 20);
        std::cout << "First value greater than 20  at position "
                  << std::distance(v.begin(), upSet) << std::endl;
</code>

L'intérêt de faire appel à la fonction [[https://en.cppreference.com/w/cpp/iterator/distance|std::distance]] qui a pour protopye : 
<code cpp>
template<class inputIterator>
typename std::iterator_traits<inputIterator>::difference_type
    distance(inputIterator first, inputIterator last);
</code
est de laisser le compilateur sélectonner l'algorithme le plus efficace pour calculer le nombre d'itérations nécessaires pour aller du premier itérateur ''first'' au second itérateur ''last''. Si les itérateurs sont des itérateurs respectant les exigences relatives à un [[https://en.cppreference.com/w/cpp/named_req/RandomAccessIterator|random access iterator]], dans ce cas, le code exécuté sera équivalent à :
<code cpp>
    return last - first;
</code>

Par contre si l'itérateur n'est pas un [[https://en.cppreference.com/w/cpp/named_req/RandomAccessIterator|random access iterator]], l'itérateur est supposé être un [[https://en.cppreference.com/w/cpp/named_req/InputIterator|input iterator]] et en conséquence le code exécuté est similaire au suivant :

<code cpp>
    std::iterator_traits<inputIterator>::difference_type position = 0; //upSet - v.begin()
    for(auto it = intSet.begin(); it != upSet; it++) { position ++; }
    return position.
</code>

En fait, la classe [[https://en.cppreference.com/w/cpp/iterator/iterator_traits|std::iterator_traits]] permet d'accéder plus simplement et de manière homogène aux champs des itérateurs ou des éléments assimilés à des itérateurs comme les pointeurs. Cette classe expose plusieurs définitions de type et notamment la définition de type qui s'avère être ''iterator_category'' qui identifie le type de l'itérateur.

Ainsi le code de la fonction ''std::distance'' devient :

<code cpp>

namespace {    
    template<class inputIterator, class iteratorTag>
    typename std::iterator_traits<inputIterator>::difference_type
        distance(inputIterator first, inputIterator last, iteratorTag)
    {
        std::iterator_traits<inputIterator>::difference_type position = 0; //upSet - v.begin()
        for(auto it = intSet.begin(); it != upSet; it++) { position ++; }
        return position.
    }
    template<class inputIterator>
    typename std::iterator_traits<inputIterator>::difference_type
        distance(inputIterator first, inputIterator last, std::random_access_iterator_tag)
    {
        return last - first;
    }
}

template<class inputIterator>
typename std::iterator_traits<inputIterator>::difference_type
    distance(inputIterator first, inputIterator last)
{
    return distance(first, last, 
        std::iterator_traits<inputIterator>::iterator_category());
}

</code>

Quand on appelle la fonction ''distance'', elle appelle la fonction distance qui prend trois arguments, le dernier étant un objet ayant un type identifiant le type d'itérateur. Deux fonctions ''distances'' internes (ie. dans un espace de nom anoyme) sont définies: 
  * <code cpp>
    template<class inputIterator, class iteratorTag>
    typename std::iterator_traits<inputIterator>::difference_type
        distance(inputIterator first, inputIterator last, iteratorTag)
</code>Cette fonction est la fonction générique qui fonctionne pour l'intégralité des différents type d'itérateurs ''iteratorTag''.
  * <code cpp>
    template<class inputIterator>
    typename std::iterator_traits<inputIterator>::difference_type
        distance(inputIterator first, inputIterator last, std::random_access_iterator_tag)
</code>Cette fonction est la version spécialisée pour le type ''iteratorTag'' qui doit être égal à [[https://en.cppreference.com/w/cpp/iterator/iterator_tags|std::random_access_iterator_tag]].
 
Comme la version spécialisée est prioritaire sur la version générique, si l'itérateur définit ''iterator_category'' comme étant [[https://en.cppreference.com/w/cpp/iterator/iterator_tags|std::random_access_iterator_tag]], c'est la version spécialisée de la fonction qui sera appelé, sinon la version générique, ce qui permet d'avoir recours à la méthode optimale pour calculer la distance.

</hidden>

===== 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 [[https://en.cppreference.com/w/cpp/algorithm/sort|sort]] soit la fonction  [[https://en.cppreference.com/w/cpp/algorithm/sort_heap|sort_heap]] pour effectuer le tri de votre tableau.

<hidden Correction>

Les fonctions [[https://en.cppreference.com/w/cpp/algorithm/sort|sort]] et [[https://en.cppreference.com/w/cpp/algorithm/sort_heap|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 ''container'' 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 [[https://en.cppreference.com/w/cpp/named_req/RandomAccessIterator|random access iterator]] et par [[https://en.cppreference.com/w/cpp/named_req/ValueSwappable|value is swappable]]. 

Ceci signifie que l'itérateur peut fonctionner sur une structure de type [[https://en.cppreference.com/w/cpp/container/vector|std::vector]] qui expose bien un tel itérateur mais pas sur une structure de type [[https://en.cppreference.com/w/cpp/container/set|std::set]] par exemple qui n'expose qu'un [[https://en.cppreference.com/w/cpp/named_req/BidirectionalIterator|bidirectionnal iterator]].


Pour un containeur de type [[https://en.cppreference.com/w/cpp/container/vector|std::vector]], il est possible d'écrire le code suivant:

<code cpp>
#include<iostream>
#include"upper.h"
#include<vector>
#include<algorithm>

using namespace std;

void testSortAndUpper()
{
    std::vector<int> v{ 10, 20, 30, 30, 20, 10, 10, 20 };
    // 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 ''sort''
    std::sort(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;
}


void testSortHeapAndUpper()
{
    std::vector<int> v{ 10, 20, 30, 30, 20, 10, 10, 20 };
    std::make_heap(v.begin(), v.end());
    // 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 ''sort_heap''
    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>