• Utilisation de std::list
• splice(itérateur, conteneur): Déplace tous les éléments d'un conteneur à la position spécifiée par l'itérateur

std::list<int> liste1;
std::list<int> liste2;
for (size_t i = 0; i < 3; i++)
{
    liste1.push_back(i); // 0 1 2
    liste2.push_back(i+10); // 10 11 12
}    
liste1.splice(liste2.begin(), liste1);
// liste1.splice(liste2.begin(), liste1, ++liste1.begin()); // Déplace l'élément 1 au début de liste2
// À ce stade, liste2 contient 0 1 2 10 11 12 et liste1 est vide
for(auto element:liste2)
{
    std::cout << element << std::endl; // 0 1 2 10 11 12
}

• unique: Supprime les éléments adjacents en double liste1.unique();
• Principe de fonctionnement de std::sort

Principe: Principalement basé sur le tri rapide (quicksort). Cependant, si le pivot n'est pas bien choisi, cela peut entraîner une profondeur de récursion importante. Pour éviter ce problème, lorsque la profondeur de récursion atteint un certain seuil, l'algorithme passe au tri par tas (heapsort). Lorsque le nombre d'éléments est inférieur ou égal à 16, le tri par insertoin est utilisé à la place du tri rapide. Implémentation: La fonction std::sort prend deux itérateurs (intervalle fermé à gauche, ouvert à droite) et une fonction de comparaison (ordre croissant par défaut). Elle appelle d'abord la fonction de tri mixte __introsort_loop(__first, __last, profondeur_de_pile, __comp). Cette fonction contient une boucle qui ne se termine que lorsque le nombre d'éléments est inférieur ou égal à 16. Enfin, elle appelle la fonction de tri par insertion. Comme std::sort nécessite que le conteneur supporte les itérateurs à accès aléatoire (RandomAccessIterator), et que les itérateurs de list ne supportent que l'accès bidirectionnel, on ne peut pas utiliser std::sort pour trier une liste. Il faut plutôt utiliser la méthode de tri propre au conteneur.

• Performance de list::push_back par rapport à vector

Chaque nœud d'une liste est alloué sur le tas. À chaque ajout d'un élément, un malloc est effectué pour le nœud, et les pointeurs gauche et droit sont initialisés.

• Allocation mémoire personnalisée pour les conteneurs: Préallocation d'un bloc mémoire comme tampon pour éviter les allocations multiples

#include <iostream>
#include <list>
static char tampon_global[65535*120];

// Structure dédiée pour stocker les données allouées en tant que tampon
struct gestionnaire_memoire_personnel
{
    char *m_tampon = tampon_global;
    size_t m_marque_eau = 0; // Enregistre la taille mémoire déjà allouée
    char* allouer(size_t n) // Fonction d'allocation dans la structure plutôt que dans l'allocateur
    {
        char *p = m_tampon + m_marque_eau;
        m_marque_eau += n;
        return p;
    }
};

// Allocateur personnalisé pour les conteneurs
template<class T>
struct allocateur_personnalise{
    gestionnaire_memoire_personnel *m_gestionnaire{};
    using value_type = T;
    // Constructeur: initialisation du tampon
    allocateur_personnalise(gestionnaire_memoire_personnel * gestionnaire):m_gestionnaire(gestionnaire){};
    T *allouer(size_t n)
    {
        char *p = m_gestionnaire->allouer(n*sizeof(T), alignof(T)); // L'alignement est crucial pour éviter un comportement indéfini
        return (T*)p;
    }
    void desallouer(T *p, size_t n)
    {
        // Rien à faire
    }
    allocateur_personnalise() = default;
    template<class U>
    constexpr allocateur_personnalise(allocateur_personnalise<U> const &autre) noexcept:m_gestionnaire(autre.m_gestionnaire){
    }
    constexpr bool operator==(allocateur_personnalise const &autre) const noexcept{
        return m_gestionnaire == autre.m_gestionnaire;
    }
};

int main() {
    gestionnaire_memoire_personnel memoire;
    std::list<char, allocateur_personnalise<char>> a(12, allocateur_personnalise<char>(&memoire));
    for (int i = 0; i < 65535; i++)
    {
        a.push_back(12);
    }
    return 0;
}

• C++17 fournit une version polymorphe de l'allocateur (implémentée avec des fonctions virtuelles)

Allocateur: std::pmr::polymorphic_allocator****Tampon mémoire: memory_resource est une classe abstraite avec des implémentations concrètes. Il ne faut pas l'utiliser directement. Les implémentations disponibles sont: monotonic_buffer_resource, qui ne peut être utilisée que comme variable locale (sinon la mémoire ne serait pas libérée), ou unsynchronized_pool_resource et synchronized_pool_resource pour une utilisation globale (la différence étant que ce dernier peut être utilisé en multithreading)

#include <iostream>
#include <list>
#include <memory_resource>
int main() {
    std::pmr::monotonic_buffer_resource gestionnaire_memoire;
    std::list<char, std::pmr::polymorphic_allocator<char>> a(12, &gestionnaire_memoire); // Conversion implicite de type
    // Peut aussi être écrit simplement: std::pmr::list<char> a(&gestionnaire_memoire);
    for (int i = 0; i < 65535; i++)
    {
        a.push_back(12);
    }
    return 0;
}