Table of Contents

Partie I – Définitions des exigences

TD6

Question n°1

Créer un projet dans lequel vous intégrez le fichier “simple_sort.hpp” qui contient la fonction de comparaison suivante:

#pragma once
#include<algorithm>
 
template<typename  iterator>
void simple_sort(iterator start, iterator end)
{
    for(;start != end; start ++)
    {
        auto it = start; it++;
        for(;it != end; it ++)
        {
            // Compare si les deux elements sont dans le bon ordre.
            if (*start > *it)
                std::swap(*start, *it);
        }
    }
}

Question n°1.1

Déterminer quel type d'itérateur est requis pour effectuer les opérations ?

Correction

Correction

Il s'agit d'un itérateur:

  • devant offrir une itération croissante,
  • devant offrir la possibilité de reprendre l'itération à partir d'une position antérieurement stockée.

Si nous regardons les caractéristiques des itérateurs: Iterator library, nous constatons que:

  • LegacyInputIterator: ne supporte pas plusieurs passes et ne supporte pas l'écriture,
  • LegacyForwardIterator: supporte plusieurs passes mais ne supporte pas obligatoire l'écriture,
  • LegacyOuputIterator: supporte l'écriture.

De fait, nous devons garantir à la fois la lecture et l'écriture, ce qui signifie que nous devons nous assurer que l'itérateur respect les contracts requis pour un LegacyForwardIterator et un LegacyOuputIterator.

Question n°1.2

Ajouter une contrainte imposant que le type passé à la fonction correspond bien au type d'itérateur que vous avez identifié.

Correction

Correction

template<typename  iterator>
void simple_sort(iterator start, iterator end) 
    requires(std::forward_iterator<iterator> && std::input_or_output_iterator<iterator>)
{
    std::cout << "Insertion Sort\n";
    for(;start != end; start ++)
    {
        auto it = start; it++;
        for(;it != end; it ++)
        {
            // Compare si les deux elements sont dans le bon ordre.
            if (*start > *it)
                std::swap(*start, *it);
        }
    }
}

Question n°1.3

Nous souhaitons ajouter l'opérateur suivant qui liste l'ensemble des éléments d'un conteneur:

template<typename  containerT, typename charT, typename traits = std::char_traits<charT>>
std::basic_ostream<charT, traits>& operator << (std::basic_ostream<charT, traits>& aStream, const containerT& aContainer)
{
    aStream << "{";
    auto end = aContainer.end();
    for(auto it = aContainer.begin(); it != end;)
    {
        aStream << *it ++;
        if(it != end)
            aStream << ", ";
    }
    aStream << "}";
} 

Ajouter ce code à votre fichier 'simple_sort.hpp' et puis tester ensuite à la fois la précédente fonction et cette nouvelle fonction avec le code suivant :

#include<list>
#include"simple_sort.hpp"
 
int main() 
{
    std::list<int> v = {1, 7, 3, 4, 9, 2, 5};
    simple_sort(v.begin(), v.end());
    std::cout << v;
    return 0;
}

Question n°1.4

Dans la question précédente, nous avons défini une nouvelle surcharge de l'opérateur <<. En fait, cette surcharge n'est pas optimale, puisqu'il suffit que je définisse un type quelconque non supporté et cela ne fonctionne plus :

#include<list>
#include"sort.hpp"
 
struct Toto {};
int main() 
{
    std::list<int> v = {1, 7, 3, 4, 9, 2, 5};
    simple_sort(v.begin(), v.end());
    std::cout << v;
    std::cout << Toto() << std::endl;
    return 0;
}

Expliquer pourquoi le compilateur génére une erreur ?

Correction

Correction

En fait, il n'y a pas de surcharge de l'opérateur << pour le type `Toto`, en conséquence, le compilateur va rechercher dans les opérateurs qui n'ont pas de contraintes sur les types, vous vous souvenez qu'on essaye d'abord les opérateurs les plus généraux et ensuite les moins généraux. Il trouve donc dans l'espace de nom courant l'opérateur :

template<typename  containerT, typename charT, typename traits = std::char_traits<charT>>
std::basic_ostream<charT, traits>& operator << (std::basic_ostream<charT, traits>& aStream, const containerT& aContainer) {...}

et ne sait pas que cet opérateur n'est définit que pour les objets qui sont des conteneurs au sens de la STL. En conséquence de quoi, il génère une erreur puisqu'il essaye d'instancier un code qui ne supporte pas des objets de type `Toto`.

Partie 2