Table of Contents

Partie II – Spécialisation par contraintes

TD6

Question n°1

Nous considérons toujours notre code affichant le contenu d'un conteneur tel que défini dans la première partie. 

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

Question n°1.1

Déterminer ce qui va caractériser un conteneur pouvant être pris comme argument par la fonction précédente ?

Correction

Correction

En fait, il est attendu que le conteneur fournisse deux méthodes :

  • `begin()`: retournant un itérateur marquant le début de la séquence,
  • `end()`: retournant un itérateur marquant le fin de la séquence.

L'itérateur qui est retourné doit supporter :

  • l'accès en lecture des données stockées dans le conteneur,
  • le parcours en avant.

Il n'a pas besoin de supporter le multipasse.

Question n°1.2

Implanter un concept qui permet de formaliser les exigences que vous venez de formuler ?

Correction

Correction 

template<typename T>
concept Browsable = requires (const T& a)
{
    { a.begin() } -> std::forward_iterator;
    { a.end() } -> std::forward_iterator;
};

Question n°1.3

Ajouter les contraintes à l'opérateur << qui a été défini pour un conteineur.

Correction

Correction 

template<typename containerT, typename charT, typename traits = std::char_traits<charT>>
requires Browsable<containerT>
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 << "}";
    return aStream;
}

Question n°1.4

Introduisez une implantation de l'opérateur `«` qui pour tout type affiche 'NONE'.

Correction

Correction 

template<typename T, typename charT, typename traits = std::char_traits<charT>>
std::basic_ostream<charT, traits>& operator << (std::basic_ostream<charT, traits>& aStream, const T& aContainer)
{
    std::cout << "NONE";
    return aStream;
}

Question n°2

Nous avons deux fonctions pour effectuer un tri, l'algorithme simple de tri que nous avons implanté et l'algorithme ``std::sort`` fourni par la STL.

Cependant notre algorithme fonctionne pour des itérateurs qui ne supportent pas l'accès indexé tandis que l'algorithme ``std::sort`` est un quicksort et nécessite un accès indexé mais qui est plus rapide.

Modifier le code de ``std::simple_sort`` pour appeller ``std::sort`` si jamais les itérateurs sont des itérateurs supportant l'accès direct (``std::random_access_iterator``).

Correction

Correction 

template<typename  iterator>
void simple_sort(iterator start, iterator end) 
    requires(std::forward_iterator<iterator> && ! std::random_access_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);
        }
    }
}
template<typename iterator>
void simple_sort(iterator start, iterator end) 
    requires(std::random_access_iterator<iterator> && std::input_or_output_iterator<iterator>)
{
    std::cout << "Quicksort\n";
    return std::sort(start, end);
}

Et nous exécutons le code suivant : 

{
    std::list<int> l = {1, 7, 3, 4, 9, 2, 5};
    std::vector<int> v(l.begin(), l.end());
    simple_sort(l.begin(), l.end());
    std::cout << l << std::endl;
    simple_sort(v.begin(), v.end());
    std::cout << v << std::endl;

qui génèrera la sortie suivante: 

Insertion Sort
{1, 2, 3, 4, 5, 7, 9}
Quicksort
{1, 2, 3, 4, 5, 7, 9}