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 :

1. l'itérateur theBeginIterator faisant référence au premier élément de la séquence,
2. 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),
3. 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é 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:

1. le paramètre de type inputIterator correspondant au type des itérateurs theBeginIterator et theEndIterator,
2. 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 :

template<class inputIterator, class T>
inputIterator upper(inputIterator theBeginIterator, inputIterator theEndIterator, const T& aValue)

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 :

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

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 container sera :

    std::sort(container.begin(), container(end));
    std::sort_heap(conta.begin(), container(end));

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:

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