Licence CC 0

Progresser en C++

Quand on refait un exercice 4 ans plus tard

Publié :
Auteur :
Catégorie :
Temps de lecture estimé : 3 minutes

Aujourd’hui, j’ai recodé un code à moi vieux de quatre ans. C’était une version un peu modifiée de l’exercice zTri, où j’avais implémenté les tris à bulle, par insertion et rapide.

C’est amusant de voir que j’ai progressé et comment j’ai pu raccourcir le code et le rendre plus agréable à lire. Bien entendu, il y a de quoi améliorer. Mais c’est un exemple pour tout ceux qui débutent et peut-être se sentent découragés parce qu’ils ont l’impression de ne pas progresser.

Je mets mon nouveau code en spolier en-dessous. Voici le lien de la V1. Comparez et voyez. Si vous voulez me faire des remarques sur la V2, je les attends avec impatience. :)

#include <algorithm>
#include <functional>
#include <iostream>
#include <random>
#include <vector>

class ComparePolicyLess
{
protected:
    template <typename T>
    bool comparing(T const & left, T const & right)
    {
        return std::less<T>{} (left, right);
    }
};

class ComparePolicyGreat
{
protected:
    template <typename T>
    bool comparing(T const & left, T const & right)
    {
        return std::greater<T>{} (left, right);
    }
};

template <typename Container, typename SortPolicy>
class Sort : SortPolicy
{
    using SortPolicy::algorithm;

public:
    void sort(Container & container)
    {
        algorithm<Container>(container);
    }
};

template <typename ComparePolicy>
class SortPolicyBubble : private ComparePolicy
{
    using ComparePolicy::comparing;

protected:
    template <typename Container>
    void algorithm(Container & container)
    {
        auto it_begin = std::end(container); --it_begin;
        for (auto it = it_begin; it != std::begin(container); --it)
        {
            bool no_swap { true };
            for (auto jt = std::begin(container); jt != it; ++jt)
            {
                auto kt = jt; ++kt;
                if (comparing(*jt, *kt))
                {
                    using std::swap;
                    swap(*kt, *jt);
                    no_swap = false;
                }
            }

            if (no_swap)
            {
                break;
            }
        }
    }
};

template <typename ComparePolicy>
class SortPolicyInsertion : private ComparePolicy
{
    using ComparePolicy::comparing;

protected:
    template <typename Container>
    void algorithm(Container & container)
    {
        for (auto it = std::begin(container); it != std::end(container); ++it)
        {
            // https://stackoverflow.com/a/18454367/6060256
            std::rotate(std::upper_bound(std::begin(container), it, *it), it, std::next(it));
        }
    }
};

template <typename ComparePolicy>
class SortPolicyQuick : private ComparePolicy
{
    using ComparePolicy::comparing;

protected:
    template <typename Container>
    void algorithm(Container & container)
    {
        auto end = std::end(container); --end;
        quick_sort(container, std::begin(container), end);
    }

private:
    template <typename Iterator>
    Iterator pivot(Iterator first, Iterator last)
    {
        std::random_device rd {};
        std::default_random_engine engine { rd() };

        int const max { static_cast<int>(std::distance(first, last)) };
        std::uniform_int_distribution uniform_dist(0, max);

        Iterator temp { first };
        std::advance(temp, uniform_dist(engine));
        return temp;
    }

    template <typename Iterator>
    Iterator part(Iterator first, Iterator last)
    {
        auto pivot = this->pivot(first, last);
        auto const pivot_original_value { *pivot };

        using std::swap;
        swap(*pivot, *last);

        auto jt = first;
        for (auto it = first; it != last; ++it)
        {
            if (comparing(pivot_original_value, *it))
            {
                swap(*it, *jt);
                ++jt;
            }
        }

        std::swap(*last, *jt);
        return jt;
    }

    template <typename Container, typename Iterator>
    void quick_sort(Container & container, Iterator first, Iterator last)
    {
        if (std::distance(first, last) > 0)
        {
            Iterator pivot { part(first, last) };
            Iterator previous { pivot };
            Iterator next { pivot };

            // Protection because the pivot is random and can be the beginning or end of the container.
            if (pivot != std::begin(container)) { --previous; }
            quick_sort(container, first, previous);
            if (pivot != std::end(container)) { ++next; }
            quick_sort(container, next, last);
        }
    }
};

template <typename Container>
using BubbleSort = Sort<Container, SortPolicyBubble<ComparePolicyGreat>>;

template <typename Container>
using InsertionSort = Sort<Container, SortPolicyInsertion<ComparePolicyGreat>>;

template <typename Container>
using QuickSort = Sort<Container, SortPolicyQuick<ComparePolicyGreat>>;

int main()
{
    std::vector<int> v1 { 1, -8, 4, 48, -10, 700, 5, -7, 54545, -777 };

    QuickSort<decltype(v1)> qs;
    qs.sort(v1);

    for (auto i : v1)
    {
        std::cout << i << std::endl;
    }

    return 0;
}


11 commentaires

Salut,

C’est amusant de voir que j’ai progressé et comment j’ai pu raccourcir le code et le rendre plus agréable à lire.

Je ne voudrais pas jouer les rabats-joie, mais… je trouve le tout un peu long et complexe pour implémenter trois algorithmes de tri, plus précisémment ces trois là. Bon après c’est de la programmation générique, du coup c’est pas parfaitement comparable avec un équivalent en C.

+3 -0

J’ai pas précisé oui. Il faut un compilateur supportant C++17.

@Taurre : ça te parait sans doute plus complexe parce que tu fais du C. Mais déjà j’ai éliminé la redondance qu’il y avait avant entre les fonctions spécifiques aux tableaux C et celles pour les conteneurs STL. Maintenant les deux sont réunis au sein d’une même fonction.

J’aurai plutôt mis la dépendance au type du conteneur sur la fonction de sort au lieu de la classe qui contient sort, pour pouvoir passer l’algorithme et le réutiliser avec d’autres conteneurs/types.

Sinon c’est très fun comme implémentation, mais c’est vrai qu’avec trois algorithmes et comparés à du sort en C c’est beaucoup verbeux. Il faudrait comparer avec des sorts C++ plutôt !

+1 -0

J’aurai plutôt mis la dépendance au type du conteneur sur la fonction de sort au lieu de la classe qui contient sort, pour pouvoir passer l’algorithme et le réutiliser avec d’autres conteneurs/types.

Sinon c’est très fun comme implémentation, mais c’est vrai qu’avec trois algorithmes et comparés à du sort en C c’est beaucoup verbeux. Il faudrait comparer avec des sorts C++ plutôt !

unidan

Merci pour la suggestion, ça simplifie le code. :)

Pour la comparaison avec des algorithmes C++, faut en trouver qui utilise la STL ou qui essaye d’être génériques. La plupart des exemples, c’est std::vector avec les crochets, quand c’est pas un bête tableau C.

Le coup en lisibilité pour avoir de la généricité est énorme comparé à ce qui se fait dans un paradigme fonctionnel :

let rec qs_sort compare l =
  match l with
  | [] -> []
  | x::t ->
     let l = List.filter (fun y -> compare x y > 0)  t in
     let r = List.filter (fun y -> compare x y <= 0) t in
     (qs_sort compare l)@[x]@(qs_sort compare r)

let rec pp_list pp fmt = function
  | [] -> Format.fprintf fmt "]"
  | [x] -> Format.fprintf fmt "%a]" pp x
  | x::t ->  Format.fprintf fmt "%a;%a" pp x (pp_list pp) t

let pp_list pp fmt list =
  Format.fprintf fmt "[%a" (pp_list pp)  list

let pp_int fmt i = Format.fprintf fmt "%d" i

let pp_string fmt str = Format.fprintf fmt "%s" str

let _ =
  Format.printf "%a@." (pp_list pp_int)
    (qs_sort Pervasives.compare [1;-8;4;48;-10;700;5;-7;54545;-77]);
  Format.printf "%a@." (pp_list pp_string)
    (qs_sort Pervasives.compare ["aaa";"hello";"machine";"bidule"])

Tout ce qui rend le code générique est implicite ici grâce au système de type. Bien sûr, si on souhaite que ce code puisse être facilement utilisable, on peut rajouter des annotations de type.

Mon point ici, c’est juste que mon impression dans le code que tu présentes ici est qu’environ 33% du code est dédié à le rendre générique et n’ayant pu trop l’habitude de faire du C++, cela rend la lecture moins facile.

Avec l’arrivé du mot-clé auto, est-il prévu dans le futur de rendre le code dédié à la généricité un peu plus implicite en C++ ?

+0 -0

Oui, c’est vrai, j’avais zappé ce point. En Haskell, je pourrais le corriger facilement, en OCaml il faudrait passer par des modules je suppose.

Ce que tu dis la personne dans l’article est vrai, cependant j’ai l’impression qu’il repousse la faute sur le langage. Si tu généralises trop ton code, juste parce que tu as envie de le faire, c’est le problème de celui qui code, pas du langage. En général, les systèmes de type des langages fonctionnels incitent à être générique sur le type des éléments que l’on manipule, mais pas sur les structure de données. Quand je code en OCaml, en général, je sais toujours la structure de données que je vais utiliser, et il y en aura bien qu’une seule que je vais utiliser.

Si j’ai un même algorithme que je souhaite utiliser sur deux structures de données différentes, je me permettrai alors de faire de la duplication de code. Si je cherche des performances, c’est souhaitable. Sinon, je me débrouille très souvent pour utiliser qu’une seule structure de données et je ne paye pas le coup de passer de l’une à l’autre.

Je ne sais pas si en C++ par contre c’est le cas, et je serai curieux d’avoir des avis sur la question.

+0 -0

@Saroupille : on est d’accord qu’en tant qu’utilisateur, on a souvent conscience du type qu’on va utiliser.

Là, je me place plutôt en concepteur de bibliothèque. Je ne sais pas si mon code sera potentiellement utilisé par un vector, ou une liste, ou même un tableau C. Du coup, je dois être générique tant sur les éléments du conteneur que sur le conteneur lui-même.

@Saroupille : on est d’accord qu’en tant qu’utilisateur, on a souvent conscience du type qu’on va utiliser.

Là, je me place plutôt en concepteur de bibliothèque. Je ne sais pas si mon code sera potentiellement utilisé par un vector, ou une liste, ou même un tableau C. Du coup, je dois être générique tant sur les éléments du conteneur que sur le conteneur lui-même.

informaticienzero

Après ce problème là a déjà été résolu en C++ via les itérateurs. Ton code serait probablement plus court et aurait plus de fonctionnalité en se basant plus sur ceux-ci et en utilisant moins le système de type pour arriver à tes fins. Mais c’est moins fun comme construction.

+0 -0

@Taurre : ça te parait sans doute plus complexe parce que tu fais du C. Mais déjà j’ai éliminé la redondance qu’il y avait avant entre les fonctions spécifiques aux tableaux C et celles pour les conteneurs STL. Maintenant les deux sont réunis au sein d’une même fonction.

informaticienzero

Oui, venant du C cela à l’air terriblement verbeux en fait et cela rebute du coup au premier coup d’oeil. ^^
Côté C on obtient plutôt quelque chose comme ceci, qui est certes pas non plus forcément évident à cause de la manipulation des pointeurs génériques et du fait qu’on s’amuse avec l’arithmétique des pointeurs, mais quand même, cela a ma préférence. :D

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>


void swap(void *a, void *b, size_t size)
{
    uint8_t tmp[size];

    memcpy(tmp, a, size);
    memcpy(a, b, size);
    memcpy(b, tmp, size);
}


void sort_bubble(void *data, size_t n, size_t size, int (*cmp)(void *, void *))
{
    bool changed;

    do {
        uint8_t *p = (uint8_t *)data;
        changed = false;

        for (size_t i = 0; i < n - 1; ++i) {
            if (cmp(p, p + size) < 0) {
                swap(p, p + size, size);
                changed = true;
            }

            p += size;
        }
    } while (changed);
}


void sort_insert(void *data, size_t n, size_t size, int (*cmp)(void *, void *))
{
    uint8_t * const end = (uint8_t *)data + size * n;

    for (uint8_t *p = (uint8_t *)data + size; p < end; p += size)
        for (uint8_t *q = p; (void *)q > data && cmp(q - size, q) < 0; q -= size)
            swap(q - size, q, size);
}


uint8_t *partition(uint8_t *first, uint8_t *last, size_t size, int (*cmp)(void *, void *))
{
    uint8_t *lesser = first;

    for (uint8_t *p = first; p < last; p += size)
        if (cmp(p, last) > 0) {
            swap(lesser, p, size);
            lesser += size;
        }

    swap(lesser, last, size);
    return lesser;
}


void sort_quick_recursive(uint8_t *first, uint8_t *last, size_t size, int (*cmp)(void *, void *))
{
    if (first < last) {
        uint8_t *pivot = partition(first, last, size, cmp);
        sort_quick_recursive(first, pivot - size, size, cmp);
        sort_quick_recursive(pivot + size, last, size, cmp);
    }
}


void sort_quick(void *data, size_t n, size_t size, int (*cmp)(void *, void *))
{
    sort_quick_recursive(data, (uint8_t *)data + size * (n - 1), size, cmp);
}


int
cmp_int(void *a, void *b)
{
    if (*(int *)a < *(int *)b)
        return 1;
    else if (*(int *)a > *(int *)b)
        return -1;
    else
        return 0;
}


int
cmp_double(void *a, void *b)
{
    if (*(double *)a < *(double *)b)
        return 1;
    else if (*(double *)a > *(double *)b)
        return -1;
    else
        return 0;
}


int
main(void)
{
    int t1[] = { 5, 1, 6, 4, 2, 78 };
    double t2[] = { 6.4, -2.3, 0.01, 567.89, 66.9, 1.2 };

    sort_insert(t1, sizeof t1 / sizeof *t1, sizeof *t1, &cmp_int);
    sort_quick(t2, sizeof t2 / sizeof *t2, sizeof *t2, &cmp_double);

    for (size_t i = 0; i < sizeof t1 / sizeof *t1; ++i)
        printf("t1[%zu] = %d\n", i, t1[i]);
    for (size_t i = 0; i < sizeof t2 / sizeof *t2; ++i)
        printf("t2[%zu] = %f\n", i, t2[i]);

    return 0;
}

Après c’est clairement globalement moins générique qu’en C++ puisqu’il faut créer les fonctions de comparaisons qui vont bien et que cela ne fonctionne qu’avec des tableaux.

Édité par Taurre

+2 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte