TD4

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.

Modifier cette fonction pour qu’elle fonctionne désormais avec des itérateurs et non plus un tableau.

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;
}

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 :

#include <algorithm>

Nous trouvons par exemple l’algorithme de tri :

template <class randomAccessIterator>
void sort(randomAccessIterator first, randomAccessIterator last);

ainsi que :

template <class randomAccessIterator>
void sort_heap(randomAccessIterator first, randomAccessIterator last);

qui fournisse un tri rapide et tri sur le tas.

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.