Tableau dynamique

Nous souhaitons implémenter un tableau dynamique à partir d'une application avec les caractéristiques suivantes.

#include <iostream>
#include <sstream>
#include <algorithm>

// on peut modéliser un tableau dynamique
// par sa donnée (data) et sa taille (n)
// de la manière suivante
template <typename T>
class dynamic_array
{
public:
    // on peut implémenter le constructeur par taille
    // d'un tableau dynamique de la manière suivante
    dynamic_array(size_t n)
    {
        this->n = n;
        data = new T[n];
    }

    // on peut implémenter le constructeur par copie
    // d'un tableau dynamique de la manière suivante
    dynamic_array(const dynamic_array<T> &other)
    {
        n = other.n;
        data = new T[n];
        for (int i = 0; i < n; i++)
            data[i] = other[i];
    }

    // on peut implémenter le destructeur
    // d'un tableau dynamique de la manière suivante
    ~dynamic_array()
    {
        delete[] data;
    }

    // on peut récupérer un élément à un indice donné
    // d'un tableau dynamique de la manière suivante
    T &operator[](int index)
    {
        return data[index];
    }

    // on peut récupérer un élément constant à un indice donné
    // d'un tableau dynamique de la manière suivante
    const T &operator[](int index) const
    {
        return data[index];
    }

    // on peut récupérer un élément à un indice donné
    // d'un tableau dynamique de la manière suivante
    T &at(int index)
    {
        if (index < n)
            return data[index];
        throw "Index out of range";
    }

    // on peut récupérer la taille
    // d'un tableau dynamique de la manière suivante
    size_t size() const
    {
        return n;
    }

    // on peut récupérer l'itérateur de début
    // d'un tableau dynamique de la manière suivante
    T *begin()
    {
        return data;
    }

    // on peut récupérer l'itérateur de début constant
    // d'un tableau dynamique de la manière suivante
    const T *begin() const
    {
        return data;
    }

    // on peut récupérer l'itérateur de fin
    // d'un tableau dynamique de la manière suivante
    T *end()
    {
        return data + n;
    }

    // on peut récupérer l'itérateur de fin constant
    // d'un tableau dynamique de la manière suivante
    const T *end() const
    {
        return data + n;
    }

    // on peut fusionner deux tableaux dynamiques
    // de la manière suivante
    friend dynamic_array<T> operator+(
        const dynamic_array<T> &arr1,
        const dynamic_array<T> &arr2)
    {
        dynamic_array<T> result(arr1.size() + arr2.size());
        std::copy(arr1.begin(), arr1.end(), result.begin());
        std::copy(arr2.begin(), arr2.end(), result.begin() + arr1.size());
        return result;
    }

    // on peut afficher un tableau dynamique
    // de la manière suivante
    friend std::ostream &operator<<(std::ostream &_out, const dynamic_array<T> &_arr)
    {
        _out << "{";
        bool isSep = false;
        for (const auto &item : _arr)
        {
            if (isSep)
            {
                _out << ", ";
            }
            _out << item;
            isSep = true;
        }
        _out << "}";
        return _out;
    }

private:
    T *data;
    size_t n;
};

// on peut modéliser un étudiant
// par son nom (name) et son niveau (standard)
// de la manière suivante
struct student
{
    std::string name;
    int standard;
};

// on peut afficher un étudiant
// de la manière suivante
std::ostream &operator<<(std::ostream &os, const student &s)
{
    return (os << "{" << s.name << ", " << s.standard << "}");
}

// on peut mettre en oeuvre un tableau dynamique
// de la manière suivante
int main(int argc, char **argv)
{
    // construction d'un tableau dynamique
    dynamic_array<student> class1(2);
    class1[0] = {"Pierre", 10};
    class1[1] = {"Paul", 20};
    std::cout << "(1): " << class1 << std::endl;
    // (1): {{Pierre, 10}, {Paul, 20}}

    // construction par copie d'un tableau dynamique
    auto class2 = class1;
    std::cout << "(2): " << class2 << std::endl;
    // (2): {{Pierre, 10}, {Paul, 20}}

    // fusion de deux tableaux dynamiques
    auto class3 = class1 + class2;
    std::cout << "(3): " << class3 << std::endl;
    // (3): {{Pierre, 10}, {Paul, 20}, {Pierre, 10}, {Paul, 20}}

    return 0;
}

Résultat des tests.

...
(1): {{Pierre, 10}, {Paul, 20}}
(2): {{Pierre, 10}, {Paul, 20}}
(3): {{Pierre, 10}, {Paul, 20}, {Pierre, 10}, {Paul, 20}}
...

Tableau polyvalent

Nous souhaitons implémenter un constructeur de tableau polyvalent à partir d'une application avec les caractéristiques suivantes.

#include <iostream>
#include <array>
#include <type_traits>

// on peut implémenter la construction
// d'un tableau polyvalent de la manière suivante
template <typename... Args>
auto build_array(Args &&...args)
    -> std::array<typename std::common_type<Args...>::type, sizeof...(args)>
{
    using commonType = typename std::common_type<Args...>::type;
    return {std::forward<commonType>((float)args)...};
}

// on peut afficher les éléments
// d'un tableau polyvalent de la manière suivante
template <size_t N>
std::ostream &operator<<(std::ostream &_out, const std::array<float, N> &_list)
{
    bool isSep = false;
    _out << "{";
    for (const auto &item : _list)
    {
        if (isSep)
        {
            _out << ", ";
        }
        _out << item;
        isSep = true;
    }
    _out << "}";
    return _out;
}

// on peut mettre en oeuvre la construction
// d'un tableau polyvalent de la manière suivante
int main(int argc, char **argv)
{
    // construction et affichage d'un tableau polyvalent
    auto data = build_array(10, 20u, 'a', 30.5f, false);
    std::cout << "(1): " << data << std::endl;
    auto data2 = build_array(11, 21u, 'b', 31.5f, true, 12, 22u, 'c');
    std::cout << "(2): " << data2 << std::endl;
    //(1): {10, 20, 97, 30.5, 0}
    //(2): {11, 21, 98, 31.5, 1, 12, 22, 99}

    // erreur à la compilation
    // lorsque tous les arguments du constructeur de tableau polyvalent
    // ne peuvent pas être convertis en un seul type
    // auto data3 = build_array(1, "String", 2.0);

    return 0;
}

Résultat des tests.

...
(1): {10, 20, 97, 30.5, 0}
(2): {11, 21, 98, 31.5, 1, 12, 22, 99}
...

Suppression conditionnelle d'une liste d'objets

Nous souhaitons mettre en oeuvre la suppression conditionnelle d'un ensemble d'objets à partir d'une liste depuis une application avec les caractéristiques suivantes.

#include <iostream>
#include <forward_list>

// on peut modéliser un citoyen
// par nom (name) et son âge (age)
// de la manière suivante
struct citizen
{
    std::string name;
    int age;
};

// on peut afficher un citoyen
// de la manière suivante
std::ostream &operator<<(std::ostream &_out, const citizen &_citizen)
{
    return (_out << "{" << _citizen.name << ", " << _citizen.age << "}");
}

// on peut afficher une liste de citoyens
// de la manière suivante
template <typename T>
std::ostream &operator<<(std::ostream &_out, const std::forward_list<T> &_list)
{
    bool isSep = false;
    _out << "{";
    for (const auto &item : _list)
    {
        if (isSep)
        {
            _out << ", ";
        }
        _out << item;
        isSep = true;
    }
    _out << "}";
    return _out;
}

// on peut mettre en oeuvre la suppression des éléments d'une liste
// de la manière suivante
int main(int argc, char **argv)
{
    // création de la liste de citoyens
    std::forward_list<citizen> citizens =
        {
            {"Raj", 22},
            {"Rohit", 25},
            {"Rohan", 17},
            {"Sachin", 16},
        };
    std::cout << "(1): " << citizens << std::endl;
    // (1): {{Raj, 22}, {Rohit, 25}, {Rohan, 17}, {Sachin, 16}}

    // suppression de tous les citoyens tels que (age < 18)
    auto citizens_copy = citizens;
    citizens.remove_if(
        [](const citizen &c)
        {
            return (c.age < 18);
        });
    std::cout << "(2): " << citizens << std::endl;
    // (2): {{Raj, 22}, {Rohit, 25}}

    // suppression de tous les citoyens tels que (age != 17)
    citizens_copy.remove_if(
        [](const citizen &c)
        {
            return (c.age != 17);
        });
    std::cout << "(3): " << citizens_copy << std::endl;
    // (3): {{Rohan, 17}}

    return 0;
}

Résultat des tests.

...
(1): {{Raj, 22}, {Rohit, 25}, {Rohan, 17}, {Sachin, 16}}
(2): {{Raj, 22}, {Rohit, 25}}
(3): {{Rohan, 17}}
...

Itérateurs

#include <iostream>
#include <forward_list>
#include <vector>

// on peut afficher une liste (vector)
// de la manière suivante
std::ostream &operator<<(
    std::ostream &_out, const std::vector<std::string> &_list)
{
    bool isSep = false;
    _out << "{";
    for (const auto &item : _list)
    {
        if (isSep)
        {
            _out << ", ";
        }
        _out << item;
        isSep = true;
    }
    _out << "}";
    return _out;
}

// on peut afficher une liste (forward_list)
// de la manière suivante
std::ostream &operator<<(
    std::ostream &_out, const std::forward_list<std::string> &_list)
{
    bool isSep = false;
    _out << "{";
    for (const auto &song : _list)
    {
        if (isSep)
        {
            _out << ", ";
        }
        _out << song;
        isSep = true;
    }
    _out << "}";
    return _out;
}

// on peut mettre en oeuvre l'utilisation des itérateurs
// de la manière suivante
int main(int argc, char **argv)
{
    // création d'une liste (vector)
    std::vector<std::string> vec = {
        "Lewis Hamilton",
        "Lewis Hamilton",
        "Nico Roseberg ",
        "Sebastian Vettel",
        "Lewis Hamilton",
        "Sebastian Vettel",
        "Sebastian Vettel",
        "Sebastian Vettel",
        "Fernando Alonso",
    };
    std::cout << "(1): " << vec << std::endl;
    // (1): {Lewis Hamilton, Lewis Hamilton, Nico Roseberg ,
    //       Sebastian Vettel, Lewis Hamilton, Sebastian Vettel,
    //       Sebastian Vettel, Sebastian Vettel, Fernando Alonso}

    // récupération du premier élément d'une liste (vector)
    auto it = vec.begin(); // Temps constant
    std::cout << "(2): " << *it << std::endl;
    // (2): Lewis Hamilton

    // Auto-addion d'un itérateur d'une liste (vector)
    it += 8; // Temps constant
    std::cout << "(3): " << *it << std::endl;
    // (3): Fernando Alonso

    // déplacement en arrière d'un itérateur d'une liste (vector)
    advance(it, -3); // Temps constant
    std::cout << "(4): " << *it << std::endl;
    // (4): Sebastian Vettel

    // copie d'une liste (vector) vers une liste (forward_list)
    std::forward_list<std::string> fwd(vec.begin(), vec.end());
    std::cout << "(5): " << fwd << std::endl;
    // (5): {Lewis Hamilton, Lewis Hamilton, Nico Roseberg ,
    // Sebastian Vettel, Lewis Hamilton, Sebastian Vettel,
    // Sebastian Vettel, Sebastian Vettel, Fernando Alonso}

    // récupération du premier élément d'une liste (forward_list)
    auto it1 = fwd.begin();
    std::cout << "(6): " << *it << std::endl;
    // (6): Sebastian Vettel

    // déplacement en avant d'un itérateur d'une liste (forward_list)
    advance(it1, 5); // Temps proportionnel au nombre d'éléments
    std::cout << "(7): " << *it << std::endl;
    // (7): Sebastian Vettel

    // erreur à l'exécution
    // lors du déplacement en arrière d'un itérateur d'une liste (forward_list)
    // advance(it1, -2); // Runtime error

    // erreur à la compilation
    // lors de l'auto-addition d'un itérateur d'une liste (forward_list)
    // it1 += 2; // Compiler error

    return 0;
}

Résultat des tests.

...
(1): {Lewis Hamilton, Lewis Hamilton, Nico Roseberg , Sebastian Vettel, 
Lewis Hamilton, Sebastian Vettel, Sebastian Vettel, Sebastian Vettel, 
Fernando Alonso}
(2): Lewis Hamilton
(3): Fernando Alonso
(4): Sebastian Vettel
(5): {Lewis Hamilton, Lewis Hamilton, Nico Roseberg , Sebastian Vettel,
Lewis Hamilton, Sebastian Vettel, Sebastian Vettel, Sebastian Vettel, 
Fernando Alonso}
(6): Sebastian Vettel
(7): Sebastian Vettel
...

Liste chaînée

#include <iostream>
#include <algorithm>

// on peut modéliser un noeud d'une liste chaînée
// par sa donnée (data) et son pointeur de noeud suivant (next)
// de la manière suivante
struct singly_ll_node
{
    int data;
    singly_ll_node *next;
};

// on peut modéliser un itérateur d'une liste chaînée
// par son pointeur de noeud (ptr)
// de la manière suivante
class singly_ll_iterator
{
public:
    using node = singly_ll_node;
    using node_ptr = node *;

public:
    // on peut implémenter le constructeur par pointeur d'un itérateur
    // d'une liste chaînée de la manière suivante
    singly_ll_iterator(node_ptr p)
        : ptr(p)
    {
    }

    // on peut récupérer la donnée d'un itérateur
    // d'une liste chaînée de la manière suivante
    int &operator*()
    {
        return ptr->data;
    }

    // on peut récupérer le pointeur direct d'un itérateur
    // d'une liste chaînée de la manière suivante
    node_ptr get()
    {
        return ptr;
    }

    // on peut pré-incrémenter un itérateur
    // d'une liste chaînée de la manière suivante
    singly_ll_iterator &operator++()
    {
        ptr = ptr->next;
        return *this;
    }

    // on peut post-incrémenter un itérateur
    // d'une liste chaînée de la manière suivante
    singly_ll_iterator operator++(int)
    {
        singly_ll_iterator result = *this;
        ++(*this);
        return result;
    }

    // on peut comparer l'égalité entre deux itérateurs
    // d'une liste chaînée de la manière suivante
    friend bool operator==(
        const singly_ll_iterator &left,
        const singly_ll_iterator &right)
    {
        return left.ptr == right.ptr;
    }

    // on peut comparer la différence entre deux itérateurs
    // d'une liste chaînée de la manière suivante
    friend bool operator!=(
        const singly_ll_iterator &left,
        const singly_ll_iterator &right)
    {
        return left.ptr != right.ptr;
    }

private:
    node_ptr ptr;
};

// on peut modéliser une liste chaînée
// par son pointeur de noeud de départ (head)
// et son pointeur de noeud de fin (m_end)
// de la manière suivante
class singly_ll
{
public:
    using node = singly_ll_node;
    using node_ptr = node *;
    using iterator = singly_ll_iterator;

public:
    // on peut implémenter le constructeur par défaut
    // d'une liste chaînée de la manière suivante
    singly_ll()
    {
        head = new node{0, nullptr};
        m_end = head;
    }

    // on peut implémenter le constructeur par liste
    // d'une liste chaînée de la manière suivante
    singly_ll(const std::initializer_list<int> &ilist)
        : singly_ll()
    {
        for (auto it = std::rbegin(ilist); it != std::rend(ilist); it++)
            push_front(*it);
    }

    // on peut implémenter le constructeur par copie
    // d'une liste chaînée de la manière suivante
    singly_ll(const singly_ll &other)
        : singly_ll()
    {
        for (auto i : other)
        {
            m_end->data = i;
            m_end->next = new node{0, nullptr};
            m_end = m_end->next;
        }
    }

    // on peut implémenter le destructeur
    // d'une liste chaînée de la manière suivante
    ~singly_ll()
    {
        node_ptr node = head;
        while (node)
        {
            node_ptr cur = node;
            node = node->next;
            delete cur;
        }
    }

    // on peut ajouter un élément au début
    // d'une liste chaînée de la manière suivante
    void push_front(int val)
    {
        auto new_node = new node{val, nullptr};
        new_node->next = head;
        head = new_node;
    }

    // on peut supprimer un élément à la fin
    // d'une liste chaînée de la manière suivante
    void pop_front()
    {
        auto first = head;
        if (head->next)
        {
            head = head->next;
            delete first;
        }
        else
            throw "Empty list";
    }

    // on peut récupérer l'itérateur de début
    // d'une liste chaînée de la manière suivante
    singly_ll_iterator begin()
    {
        return singly_ll_iterator(head);
    }

    // on peut récupérer l'itérateur de fin
    // d'une liste chaînée de la manière suivante
    singly_ll_iterator end()
    {
        return singly_ll_iterator(m_end);
    }

    // on peut récupérer l'itérateur constant de début
    // d'une liste chaînée de la manière suivante
    singly_ll_iterator begin() const
    {
        return singly_ll_iterator(head);
    }

    // on peut récupérer l'itérateur constant de fin
    // d'une liste chaînée de la manière suivante
    singly_ll_iterator end() const
    {
        return singly_ll_iterator(m_end);
    }

    // on peut afficher les éléments
    // une liste chaînée de la manière suivante
    friend std::ostream &operator<<(std::ostream &_out, const singly_ll &_list)
    {
        bool isSep = false;
        _out << "{";
        for (const auto &item : _list)
        {
            if (isSep)
            {
                _out << ", ";
            }
            _out << item;
            isSep = true;
        }
        _out << "}";
        return _out;
    }

private:
    node_ptr head;
    node_ptr m_end;
};

// on peut mettre en oeuvre une liste chaînée
// de la manière suivante
int main(int argc, char **argv)
{
    // construction par défaut d'une liste chaînée
    singly_ll sll;

    // ajout de données au début d'une liste chaînée
    sll.push_front(10);
    sll.push_front(20);
    sll.push_front(30);
    sll.push_front(40);
    sll.push_front(50);
    std::cout << "(1): " << sll << std::endl;
    // (1): {50, 40, 30, 20, 10}

    // suppression de données au début d'une liste chaînée
    sll.pop_front();
    sll.pop_front();
    std::cout << "(2): " << sll << std::endl;
    // (2): {30, 20, 10}

    // construction par liste d'une liste chaînée
    singly_ll sll2 = {10, 20, 30, 40, 50};
    sll2.push_front(0);
    sll2.push_front(-10);
    std::cout << "(3): " << sll2 << std::endl;
    // (3): {-10, 0, 10, 20, 30, 40, 50}

    // construction par copie d'une liste chaînée
    auto sll3 = sll2;
    sll3.push_front(-20);
    sll3.push_front(-30);
    std::cout << "(4): " << sll3 << std::endl;
    // (4): {-30, -20, -10, 0, 10, 20, 30, 40, 50}

    // parcours par itération d'une liste chaînée
    std::cout << "(5): {";
    for (singly_ll::iterator it = sll3.begin(); it != sll3.end(); it++)
    {
        if (it != sll3.begin())
        {
            std::cout << ", ";
        }
        std::cout << *it;
    }
    std::cout << "}" << std::endl;
    // (5): {-30, -20, -10, 0, 10, 20, 30, 40, 50}

    return 0;
}

Résultat des tests.

...
(1): {50, 40, 30, 20, 10}
(2): {30, 20, 10}
(3): {-10, 0, 10, 20, 30, 40, 50}
(4): {-30, -20, -10, 0, 10, 20, 30, 40, 50}
(5): {-30, -20, -10, 0, 10, 20, 30, 40, 50}
...

Tableau de type (std::list)

#include <iostream>
#include <list>
#include <vector>

// on peut afficher les éléments
// d'une liste (list) de la manière suivante
template <typename T>
std::ostream &operator<<(std::ostream &_out, std::list<T> _list)
{
    _out << "{";
    bool isSep = false;
    for (const auto &data : _list)
    {
        if (isSep)
        {
            _out << ", ";
        }
        _out << data;
        isSep = true;
    }
    _out << "}";

    return _out;
}

// on peut afficher les éléments
// d'une liste (vector) de la manière suivante
template <typename T>
std::ostream &operator<<(std::ostream &_out, std::vector<T> _list)
{
    _out << "{";
    bool isSep = false;
    for (const auto &data : _list)
    {
        if (isSep)
        {
            _out << ", ";
        }
        _out << data;
        isSep = true;
    }
    _out << "}";

    return _out;
}

// on peut mettre en oeuvre
// une liste (list) de la manière suivante
int main(int argc, char **argv)
{
    // construction par liste d'une liste (list)
    std::list<int> list1 = {1, 2, 3, 4, 5};
    std::cout << "(01): " << list1 << std::endl;
    // (01): {1, 2, 3, 4, 5}

    // ajout d'un élément à la fin d'une liste (list)
    list1.push_back(6);
    std::cout << "(02): " << list1 << std::endl;
    // (02): {1, 2, 3, 4, 5, 6}

    // insertion d'un élément après le premier élément d'une liste (list)
    list1.insert(next(list1.begin()), 0);
    std::cout << "(03): " << list1 << std::endl;
    // (03): {1, 0, 2, 3, 4, 5, 6}

    // insertion d'un élément à la fin d'une liste (list)
    list1.insert(list1.end(), 7);
    std::cout << "(04): " << list1 << std::endl;
    // (04): {1, 0, 2, 3, 4, 5, 6, 7}

    // suppression d'un élément à la fin d'une liste (list)
    list1.pop_back();
    std::cout << "(05): " << list1 << std::endl;
    // (05): {1, 0, 2, 3, 4, 5, 6}

    // construction par liste d'une liste (vector)
    std::vector<int> vec = {1, 2, 3, 4, 5};
    std::cout << "(06): " << vec << std::endl;
    // (06): {1, 2, 3, 4, 5}

    // accès à un élément à l'indice (4) d'une liste (vector)
    auto it4 = vec.begin() + 4;
    std::cout << "(07): " << *it4 << std::endl;
    // (07): 5

    // insertion d'un élément à l'indice (2) d'une liste (vector)
    vec.insert(vec.begin() + 2, 0);
    std::cout << "(08): " << vec << std::endl;
    // (08): {1, 2, 0, 3, 4, 5}

    // accès à un élément à l'indice (4) d'une liste (list)
    std::list<int> lst = {1, 2, 3, 4, 5};
    std::cout << "(09): " << lst << std::endl;
    auto l_it4 = next(lst.begin(), 4);
    std::cout << "(10): " << *l_it4 << std::endl;
    // (09): {1, 2, 3, 4, 5}
    // (10): 5

    // insertion à un élément à l'indice (2) d'une liste (list)
    lst.insert(next(lst.begin(), 2), 0);
    std::cout << "(11): " << lst << std::endl;
    // (11): {1, 2, 0, 3, 4, 5}

    return 0;
}

Résultat des tests.

...
(01): {1, 2, 3, 4, 5}
(02): {1, 2, 3, 4, 5, 6}
(03): {1, 0, 2, 3, 4, 5, 6}
(04): {1, 0, 2, 3, 4, 5, 6, 7}
(05): {1, 0, 2, 3, 4, 5, 6}
(06): {1, 2, 3, 4, 5}
(07): 5
(08): {1, 2, 0, 3, 4, 5}
(09): {1, 2, 3, 4, 5}
(10): 5
(11): {1, 2, 0, 3, 4, 5}
...

Liste doublement chaînée

#include <iostream>
#include <vector>
#include <array>
#include <sstream>
#include <algorithm>
#include <random>
#include <chrono>

// on peut modéliser un noeud d'une liste doublement chaînée
// par sa donnée (data), son pointeur de noeud suivant (next)
// et son pointeur de noeud précédent (prev)
// de la manière suivante
template <typename T>
struct cir_list_node
{
    ~cir_list_node()
    {
        delete data;
    }

    T *data;
    cir_list_node *next, *prev;
};

// on peut modéliser un itérateur d'une liste doublement chaînée
// par son pointeur de noeud (ptr)
// de la manière suivante
template <typename T>
struct cir_list_it
{
public:
    using node = cir_list_node<T>;
    using node_ptr = node *;

public:
    // on peut implémenter le constructeur par pointeur d'un itérateur
    // d'une liste doublement chaînée de la manière suivante
    cir_list_it(node_ptr p)
        : ptr(p)
    {
    }

    // on peut récupérer le contenu de la donnée d'un itérateur
    // d'une liste doublement chaînée de la manière suivante
    T &operator*()
    {
        return *(ptr->data);
    }

    // on peut récupérer le pointeur de noeud d'un itérateur
    // d'une liste doublement chaînée de la manière suivante
    node_ptr get()
    {
        return ptr;
    }

    // on peut pré-incrémenter un itérateur
    // d'une liste doublement chaînée de la manière suivante
    cir_list_it &operator++()
    {
        ptr = ptr->next;
        return *this;
    }

    // on peut post-incrémenter un itérateur
    // d'une liste doublement chaînée de la manière suivante
    cir_list_it operator++(int)
    {
        cir_list_it it = *this;
        ++(*this);
        return it;
    }

    // on peut pré-décrémenter un itérateur
    // d'une liste doublement chaînée de la manière suivante
    cir_list_it &operator--()
    {
        ptr = ptr->prev;
        return *this;
    }

    // on peut post-décrémenter un itérateur
    // d'une liste doublement chaînée de la manière suivante
    cir_list_it operator--(int)
    {
        cir_list_it it = *this;
        --(*this);
        return it;
    }

    // on peut comparer l'égalité entre deux itérateurs
    // d'une liste doublement chaînée de la manière suivante
    friend bool operator==(
        const cir_list_it &it1, const cir_list_it &it2)
    {
        return it1.ptr == it2.ptr;
    }

    // on peut comparer la différence entre deux itérateurs
    // d'une liste doublement chaînée de la manière suivante
    friend bool operator!=(
        const cir_list_it &it1, const cir_list_it &it2)
    {
        return it1.ptr != it2.ptr;
    }

private:
    node_ptr ptr;
};

// on peut modéliser une liste doublement chaînée
// par son noeud de départ (head) et sa taille (n)
// de la manière suivante
template <typename T>
class cir_list
{
public:
    using node = cir_list_node<T>;
    using node_ptr = node *;
    using iterator = cir_list_it<T>;

public:
    // on peut implémenter le constructeur par défaut
    // d'une liste doublement chaînée de la manière suivante
    cir_list()
        : n(0)
    {
        head = new node{nullptr, nullptr, nullptr};
        head->next = head;
        head->prev = head;
    }

    // on peut implémenter le constructeur par liste
    // d'une liste doublement chaînée de la manière suivante
    cir_list(const std::initializer_list<T> &il)
        : cir_list()
    {
        for (const auto &i : il)
            insert(i);
    }

    // on peut implémenter le constructeur par copie
    // d'une liste doublement chaînée de la manière suivante
    cir_list(const cir_list<T> &other)
        : cir_list()
    {
        for (const auto &i : other)
            insert(i);
    }

    // on peut implémenter le destructeur
    // d'une liste doublement chaînée de la manière suivante
    ~cir_list()
    {
        while (size())
        {
            erase(*(head->data));
        }
    }

    // on peut récupérer la taille
    // d'une liste doublement chaînée de la manière suivante
    size_t size() const
    {
        return n;
    }

    // on peut insérer un élément au début
    // d'une liste doublement chaînée de la manière suivante
    void insert(const T &value)
    {
        node_ptr newNode = new node{new T(value), nullptr, nullptr};
        n++;

        auto dummy = head->prev;
        dummy->next = newNode;
        newNode->prev = dummy;

        if (head == dummy)
        {
            dummy->prev = newNode;
            newNode->next = dummy;
            head = newNode;
            return;
        }

        newNode->next = head;
        head->prev = newNode;
        head = newNode;
    }

    // on peut supprimer un élément au début
    // d'une liste doublement chaînée de la manière suivante
    void erase(const T &value)
    {
        auto cur = head, dummy = head->prev;
        while (cur != dummy)
        {
            if (*(cur->data) == value)
            {
                cur->prev->next = cur->next;
                cur->next->prev = cur->prev;
                if (cur == head)
                {
                    head = head->next;
                }
                delete cur;
                n--;
                return;
            }
            cur = cur->next;
        }
    }

    // on peut récupérer l'itérateur de début
    // d'une liste doublement chaînée de la manière suivante
    cir_list_it<T> begin()
    {
        return cir_list_it<T>{head};
    }

    // on peut récupérer l'itérateur constant de début
    // d'une liste doublement chaînée de la manière suivante
    cir_list_it<T> begin() const
    {
        return cir_list_it<T>{head};
    }

    // on peut récupérer l'itérateur de fin
    // d'une liste doublement chaînée de la manière suivante
    cir_list_it<T> end()
    {
        return cir_list_it<T>{head->prev};
    }

    // on peut récupérer l'itérateur constant de fin
    // d'une liste doublement chaînée de la manière suivante
    cir_list_it<T> end() const
    {
        return cir_list_it<T>{head->prev};
    }

    // on peut afficher les éléments
    // une liste doublement chaînée de la manière suivante
    friend std::ostream &operator<<(std::ostream &_out, const cir_list<T> &_list)
    {
        bool isSep = false;
        _out << "{";
        for (const auto &song : _list)
        {
            if (isSep)
            {
                _out << ", ";
            }
            _out << song;
            isSep = true;
        }
        _out << "}";
        return _out;
    }

private:
    node_ptr head;
    size_t n;
};

// on peut mettre en oeuvre
// une liste doublement châinée de la manière suivante
int main(int argc, char **argv)
{
    // construction par défaut d'une liste doublement châinée
    cir_list<int> pl;

    // insertion des données au début d'une liste doublement châinée
    pl.insert(10);
    pl.insert(20);
    pl.insert(30);
    pl.insert(40);
    pl.insert(50);
    std::cout << "(1): " << pl << std::endl;
    // (1): {50, 40, 30, 20, 10}

    // suppression d'un élément d'une liste doublement châinée
    pl.erase(30);
    std::cout << "(2): " << pl << std::endl;
    // (2): {50, 40, 20, 10}

    // construction par liste d'une liste doublement châinée
    cir_list<int> pl2 = {11, 21, 31, 41, 51};
    std::cout << "(3): " << pl2 << std::endl;
    // (3): {51, 41, 31, 21, 11}

    // construction par copie d'une liste doublement châinée
    auto pl3 = pl2;
    std::cout << "(4): " << pl3 << std::endl;
    // (4): {51, 41, 31, 21, 11}

    // parcours par itération d'une liste doublement châinée
    std::cout << "(5): {";
    for (cir_list<int>::iterator it = pl3.begin();
         it != pl3.end(); ++it)
    {
        if (it != pl3.begin())
        {
            std::cout << ", ";
        }
        std::cout << *it;
    }
    std::cout << "}" << std::endl;
    // (5): {11, 21, 31, 41, 51}

    return 0;
}

Résultat des tests.

...
(1): {50, 40, 30, 20, 10}
(2): {50, 40, 20, 10}
(3): {51, 41, 31, 21, 11}
(4): {11, 21, 31, 41, 51}
(5): {11, 21, 31, 41, 51}
...

Jeu de cartes

#include <iostream>
#include <vector>
#include <array>
#include <sstream>
#include <algorithm>
#include <random>
#include <chrono>

// on peut modéliser une carte d'un jeu de cartes
// par son numéro (number) et sa couleur (suit)
// de la manière suivante
struct card
{
    // on peut énumérer les couleurs d'une carte
    // d'un jeu de cartes de la manière suivante
    enum suit
    {
        HEART,  // coeur
        SPADE,  // pique
        CLUB,   // trèfle
        DIAMOND // carreau
    };

    // on peut afficher les informations sur une carte
    // d'un jeu de cartes de la manière suivante
    std::string to_string() const
    {
        std::ostringstream os;
        if (number > 0 && number <= 10)
            os << number;
        else
        {
            switch (number)
            {
            case 1:
                os << "Ace"; // As
                break;
            case 11:
                os << "Jack"; // Valet
                break;
            case 12:
                os << "Queen"; // Reine
                break;
            case 13:
                os << "King"; // Roi
                break;
            default:
                return "Invalid card"; // Carte invalide
            }
        }

        os << " of ";
        switch (suit)
        {
        case HEART:
            os << "hearts"; // coeurs
            break;
        case SPADE:
            os << "spades"; // piques
            break;
        case CLUB:
            os << "clubs"; // trèfles
            break;
        case DIAMOND:
            os << "diamonds"; // carreaux
            break;
        }

        return os.str();
    }

    int number;
    suit suit;
};

// on peut modéliser un jeu de cartes
// par des cartes (deck) et des joueurs (player1, player2, player3, player4)
// de la manière suivante
class game
{
public:
    // on peut construire les cartes
    // d'un jeu de cartes de la manière suivante
    void buildDeck()
    {
        for (int i = 0; i < 13; i++)
            deck[i + 0 * 13] = card{i + 1, card::HEART};
        for (int i = 0; i < 13; i++)
            deck[i + 1 * 13] = card{i + 1, card::SPADE};
        for (int i = 0; i < 13; i++)
            deck[i + 2 * 13] = card{i + 1, card::CLUB};
        for (int i = 0; i < 13; i++)
            deck[i + 3 * 13] = card{i + 1, card::DIAMOND};
    }

    // on peut distribuer les cartes aux joueurs
    // d'un jeu de cartes de la manière suivante
    void dealCards()
    {
        // mélange des cartes
        unsigned seed = (unsigned)std::chrono::system_clock::now()
                            .time_since_epoch()
                            .count();
        std::shuffle(deck.begin(), deck.end(), std::default_random_engine(seed));

        // distribution des cartes aux joueurs
        player1 = {deck.begin() + 0 * 13, deck.begin() + 1 * 13};
        player2 = {deck.begin() + 1 * 13, deck.begin() + 2 * 13};
        player3 = {deck.begin() + 2 * 13, deck.begin() + 3 * 13};
        player4 = {deck.begin() + 3 * 13, deck.end()};
    }

    // on peut démarrer un jeu de cartes
    // de la manière suivante
    void playGame()
    {
        while (!isGameComplete())
        {
            playOneRound();
        }
    }

    // on peut déterminer le vainqueur d'une partie
    // d'un jeu de cartes de la manière suivante
    int getWinner() const
    {
        if (player1.empty())
            return 1;
        if (player2.empty())
            return 2;
        if (player3.empty())
            return 3;
        if (player4.empty())
            return 4;
        return 0;
    }

private:
    // on peut déterminer la fin de la partie
    // d'un jeu de cartes de la manière suivante
    bool isGameComplete() const
    {
        return player1.empty() || player2.empty() ||
               player3.empty() || player4.empty();
    }

    // on peut jouer une partie
    // d'un jeu de cartes de la manière suivante
    void playOneRound()
    {
        // comparaison et suppression des cartes entre deux joueurs
        if (compareAndRemove(player1, player2))
        {
            compareAndRemove(player3, player4);
            return;
        }
        else if (compareAndRemove(player1, player3))
        {
            compareAndRemove(player2, player4);
            return;
        }
        else if (compareAndRemove(player1, player4))
        {
            compareAndRemove(player2, player3);
            return;
        }
        else if (compareAndRemove(player2, player3))
        {
            return;
        }
        else if (compareAndRemove(player2, player4))
        {
            return;
        }
        else if (compareAndRemove(player3, player4))
        {
            return;
        }

        // mélange des cartes des joueurs
        unsigned seed = (unsigned)std::chrono::system_clock::now()
                            .time_since_epoch()
                            .count();
        std::shuffle(player1.begin(), player1.end(), std::default_random_engine(seed));
        std::shuffle(player2.begin(), player2.end(), std::default_random_engine(seed));
        std::shuffle(player3.begin(), player3.end(), std::default_random_engine(seed));
        std::shuffle(player4.begin(), player4.end(), std::default_random_engine(seed));
    }

    // on peut comparer et supprimer les cartes de deux joueurs
    // d'un jeu de cartes de la manière suivante
    bool compareAndRemove(std::vector<card> &p1, std::vector<card> &p2)
    {
        // dernière cartes identiques
        if (p1.back().number == p2.back().number)
        {
            // suppression des cartes
            p1.pop_back();
            p2.pop_back();
            return true;
        }
        return false;
    }

private:
    std::array<card, 52> deck;
    std::vector<card> player1, player2, player3, player4;
};

// on peut mettre en oeuvre
// un jeu de cartes de la manière suivante
int main(int argc, char **argv)
{
    // construction du jeu de cartes
    game newGame;

    // construction des cartes
    newGame.buildDeck();
    newGame.dealCards();
    newGame.playGame();

    // affichage du vainqueur
    auto winner = newGame.getWinner();
    std::cout << "(1): Player " << winner << " won the game." << std::endl;
    // (1): Player N won the game.

    return 0;
}

Résultat des tests.

...
(1): Player 4 won the game.
...

File d'attente

#include <iostream>
#include <queue>

// on peut modéliser une tâche d'une imprimante
// par son identifiant (id), l'auteur de la tâche (user),
// la date de la demande (time) et un compteur de tâches (count)
// de la manière suivante
class Job
{
public:
    // on peut implémenter un constructeur par nom et date
    // d'une tâche d'une imprimante de la manière suivante
    Job(const std::string &u, int t)
        : user(u),
          time(t),
          id(++count)
    {
    }

    // on peut afficher une tâche d'une imprimante
    // de la manière suivante
    friend std::ostream &operator<<(std::ostream &os, const Job &j)
    {
        os << "{" << j.id << ", " << j.user << ", " << j.time << "}";
        return os;
    }

private:
    int id;
    std::string user;
    int time;
    static int count;
};

int Job::count = 0;

// on peut modéliser une imprimante
// par ses tâches (jobs)
// de la manière suivante
template <size_t N>
class Printer
{
public:
    // on peut ajouter une tâche à la fin
    // de la file d'attente des tâches de l'imprimante
    // de la manière suivante
    bool addNewJob(const Job &job)
    {
        if (jobs.size() == N)
        {
            return false;
        }
        std::cout << "(1): adding: " << job << std::endl;
        jobs.push(job);
        return true;
    }

    // on peut supprimer une tâche au début
    // de la file d'attente des tâches de l'imprimante
    // de la manière suivante
    void startPrinting()
    {
        while (!jobs.empty())
        {
            std::cout << "(3): processing: " << jobs.front() << std::endl;
            jobs.pop();
        }
    }

private:
    std::queue<Job> jobs;
};

// on peut mettre en oeuvre une file d'attente
// d'une imprimante de la manière suivante
int main(int argc, char **argv)
{
    // construction d'une imprimante avec une capacité de cinq tâches
    Printer<5> printer;

    // construction par nom et date des tâches
    Job j1("John", 10);
    Job j2("Jerry", 4);
    Job j3("Jimmy", 5);
    Job j4("George", 7);
    Job j5("Bill", 8);
    Job j6("Kenny", 10);

    // ajout des tâches à la file d'attente des tâches de l'imprimante
    printer.addNewJob(j1);
    printer.addNewJob(j2);
    printer.addNewJob(j3);
    printer.addNewJob(j4);
    printer.addNewJob(j5);

    // message d'erreur lors de l'ajout d'une tâche à l'imprimante
    // au-delà de sa capacité maximale
    if (!printer.addNewJob(j6))
    {
        std::cout << "(2): Couldn't add 6th job" << std::endl;
    }

    // exécution des tâches de l'imprimante
    printer.startPrinting();

    // ajout et exécution de la sixième tâche de l'imprimante
    printer.addNewJob(j6);
    printer.startPrinting();
    return 0;
}

Résultat des tests.

...
(1): adding: {1, John, 10}
(1): adding: {2, Jerry, 4}
(1): adding: {3, Jimmy, 5}
(1): adding: {4, George, 7}
(1): adding: {5, Bill, 8}
(2): Couldn't add 6th job
(3): processing: {1, John, 10}
(3): processing: {2, Jerry, 4}
(3): processing: {3, Jimmy, 5}
(3): processing: {4, George, 7}
(3): processing: {5, Bill, 8}
(1): adding: {6, Kenny, 10}
(3): processing: {6, Kenny, 10}
...

Arbre binaire

#include <iostream>
#include <queue>

// on peut modéliser un noeud d'un arbre binaire
// par sa donnée (position),
// son pointeur de premier noeud (first),
// et son pointeur de deuxième noeud (second)
// de la manière suivante
struct node
{
    std::string position;
    node *first, *second;
};

// on peut modéliser un arbre binaire
// par son pointeur de noeud racine (root)
// de la manière suivante
class org_tree
{
public:
    // on peut implémenter un constructeur par donnée
    // d'un arbre binaire de la manière suivante
    org_tree(const std::string &pos)
    {
        root = new node{pos, nullptr, nullptr};
    }

    // on peut ajouter un subordonné
    // dans un arbre binaire de la manière suivante
    bool addSubordinate(const std::string &manager, const std::string &subordinate)
    {
        auto managerNode = org_tree::find(root, manager);
        if (!managerNode)
        {
            std::cout << "(01): No position named " << manager << std::endl;
            return false;
        }
        if (managerNode->first && managerNode->second)
        {
            std::cout << "(02): " << manager << " already has 2 subordinates." << std::endl;
            return false;
        }
        if (!managerNode->first)
            managerNode->first = new node{subordinate, nullptr, nullptr};
        else
            managerNode->second = new node{subordinate, nullptr, nullptr};
        return true;
    }

    // on peut afficher les éléments
    // d'un arbre binaire de la manière suivante
    friend std::ostream &operator<<(std::ostream &_out, const org_tree &_tree)
    {
        _out << "{";
        org_tree::levelOrder(_out, _tree.root);
        _out << "}";
        return _out;
    }

private:
    // on peut rechercher un noeud
    // dans un arbre binaire de la manière suivante
    static node *find(node *root, const std::string &value)
    {
        if (root == nullptr)
            return nullptr;
        if (root->position == value)
            return root;
        auto firstFound = org_tree::find(root->first, value);
        if (firstFound != nullptr)
            return firstFound;
        return org_tree::find(root->second, value);
    }

    // on peut parcourir les éléments
    // d'un arbre binaire de la manière suivante
    static void levelOrder(std::ostream &_out, node *start)
    {
        if (!start)
            return;

        std::queue<node *> q;
        q.push(start);

        while (!q.empty())
        {
            size_t size = q.size();
            for (size_t i = 0; i < size; i++)
            {
                auto current = q.front();
                q.pop();

                if (i != 0)
                {
                    _out << ", ";
                }

                _out << current->position;
                if (current->first)
                    q.push(current->first);
                if (current->second)
                    q.push(current->second);
            }

            if (!q.empty())
            {
                _out << ", " << std::endl;
            }
        }
    }

private:
    node *root;
};

// on peut mettre en oeuvre un arbre binaire
// de la manière suivante
int main(int argc, char **argv)
{
    // construction par nom d'un arbre binaire
    org_tree tree("CEO");

    // ajout des données à un arbre binaire
    if (tree.addSubordinate("CEO", "Deputy Director"))
        std::cout << "(03): Added Deputy Director in the tree." << std::endl;
    else
        std::cout << "(04): Couldn't add Deputy Director in the tree" << std::endl;
    // (03): Added Deputy Director in the tree.

    if (tree.addSubordinate("Deputy Director", "IT Head"))
        std::cout << "(05): Added IT Head in the tree." << std::endl;
    else
        std::cout << "(06): Couldn't add IT Head in the tree" << std::endl;
    // (05): Added IT Head in the tree.

    if (tree.addSubordinate("Deputy Director", "Marketing Head"))
        std::cout << "(07): Added Marketing Head in the tree." << std::endl;
    else
        std::cout << "(08): Couldn't add Marketing Head in the tree" << std::endl;
    // (07): Added Marketing Head in the tree.

    if (tree.addSubordinate("IT Head", "Security Head"))
        std::cout << "(09): Added Security Head in the tree." << std::endl;
    else
        std::cout << "(10): Couldn't add Security Head in the tree" << std::endl;
    // (09): Added Security Head in the tree.

    if (tree.addSubordinate("IT Head", "App Development Head"))
        std::cout << "(11): Added App Development Head in the tree." << std::endl;
    else
        std::cout << "(12): Couldn't add App Development Head in the tree" << std::endl;
    //(11): Added App Development Head in the tree.

    if (tree.addSubordinate("Marketing Head", "Logistics Head"))
        std::cout << "(13): Added Logistics Head in the tree." << std::endl;
    else
        std::cout << "(14): Couldn't add Logistics Head in the tree" << std::endl;
    //(13): Added Logistics Head in the tree.

    if (tree.addSubordinate("Marketing Head", "Public Relations Head"))
        std::cout << "(15): Added Public Relations Head in the tree." << std::endl;
    else
        std::cout << "(16): Couldn't add Public Relations Head in the tree" << std::endl;
    // (15): Added Public Relations Head in the tree.

    if (tree.addSubordinate("Deputy Director", "Finance Head"))
        std::cout << "(17): Added Finance Head in the tree." << std::endl;
    else
        std::cout << "(18): Couldn't add Finance Head in the tree" << std::endl;
    // (02): Deputy Director already has 2 subordinates.
    // (18): Couldn't add Finance Head in the tree

    // affichage d'un arbre binaire
    std::cout << "(19): " << tree << std::endl;
    // (19): {CEO,
    // Deputy Director,
    // IT Head, Marketing Head,
    // Security Head, App Development Head, Logistics Head, Public Relations Head}

    return 0;
}

Résultat des tests.

...
(03): Added Deputy Director in the tree.
(05): Added IT Head in the tree.
(07): Added Marketing Head in the tree.
(09): Added Security Head in the tree.
(11): Added App Development Head in the tree.
(13): Added Logistics Head in the tree.
(15): Added Public Relations Head in the tree.
(02): Deputy Director already has 2 subordinates.
(18): Couldn't add Finance Head in the tree
(19): {CEO, 
Deputy Director, 
IT Head, Marketing Head, 
Security Head, App Development Head, Logistics Head, Public Relations Head}
...

Arbre de recherche binaire

Résultat des tests.

...
(1): Inorder: {2, 4, 8, 10, 11, 12, 15, 20, 28}
(2): Inorder after deleting 12: {2, 4, 8, 10, 11, 15, 20, 28}
(4): Going left from 15, (5): Going right from 10, (5): Going right from 11, 
(7): Element 12 is NOT present in the tree
(8): {28, 20, 15, 11, 10, 8, 4, 2}
...

Tas de recherche de médiane

Résultat des tests.

...
(01): Median after insert 1: 1
(02): {{1}, {}}
(03): Median after insert 5: 3
(04): {{1}, {5}}
(05): Median after insert 2: 2
(06): {{2, 1}, {5}}
(07): Median after insert 10: 3.5
(08): {{2, 1}, {5, 10}}
(09): Median after insert 40: 5
(10): {{2, 1}, {5, 10, 40}}
...

Graphe de réseau de villes

Résultat des tests.

...
(1): {{-1, -1, -1, -1, -1, -1, -1}, {-1, -1, -1, -1, -1, -1, -1}, {-1, -1, -
1, -1, -1, -1, -1}, {-1, -1, -1, -1, -1, -1, -1}, {-1, -1, -1, -1, -1, -1, -
1}, {-1, -1, -1, -1, -1, -1, -1}, {-1, -1, -1, -1, -1, -1, -1}}
(2): ADD: LONDON-MOSCOW=900
(2): ADD: LONDON-ISTANBUL=500
(2): ADD: LONDON-DUBAI=1000
(2): ADD: ISTANBUL-MOSCOW=1000
(2): ADD: ISTANBUL-DUBAI=500
(2): ADD: DUBAI-MUMBAI=200
(2): ADD: ISTANBUL-SEATTLE=1500
(2): ADD: DUBAI-SINGAPORE=500
(2): ADD: MOSCOW-SEATTLE=1000
(2): ADD: MUMBAI-SINGAPORE=300
(2): ADD: SEATTLE-SINGAPORE=700
(3): {{-1, 900, 500, 1000, -1, -1, -1}, {900, -1, 1000, -1, -1, 1000, -1}, 
{500, 1000, -1, 500, -1, 1500, -1}, {1000, -1, 500, -1, 200, -1, 500}, {-1, 
-1, -1, 200, -1, -1, 300}, {-1, 1000, 1500, -1, -1, -1, 700}, {-1, -1, -1, 
500, 300, 700, -1}}
(2): ADD: SEATTLE-LONDON=1800
(4): {{-1, 900, 500, 1000, -1, 1800, -1}, {900, -1, 1000, -1, -1, 1000, -1}, 
{500, 1000, -1, 500, -1, 1500, -1}, {1000, -1, 500, -1, 200, -1, 500}, {-1, 
-1, -1, 200, -1, -1, 300}, {1800, 1000, 1500, -1, -1, -1, 700}, {-1, -1, -1, 
500, 300, 700, -1}}
(7): REMOVE: SEATTLE-LONDON
(5): {{-1, 900, 500, 1000, -1, -1, -1}, {900, -1, 1000, -1, -1, 1000, -1}, 
{500, 1000, -1, 500, -1, 1500, -1}, {1000, -1, 500, -1, 200, -1, 500}, {-1, 
-1, -1, 200, -1, -1, 300}, {-1, 1000, 1500, -1, -1, -1, 700}, {-1, -1, -1, 
500, 300, 700, -1}}
...

Arbre-n-aire de système de fichiers

Résultat des tests.