Gestionnaire de mémoire : L'Allocateur

L'allocateur est le composant fondamental chargé de l'allocation et de la libération de la mémoire brute, ainsi que de la gestion du cycle de vie des objets (construction et destruction). Il implémente le paradigme RAII, permettant aux conteneurs comme std::vector de gérer les ressources sans intervention manuelle de l'utilisateur.

Modèles de classes et Généricité

Grâce aux modèles (templates), un allocateur peut manipuler n'est importe quel type de donnée sans duplication de code. La spécialisation se produit lors de l'instanciation.

template <typename T>
class CustomAllocator {
public:
   using value_type = T;

   T* allocate(std::size_t n) {
       if (n == 0) return nullptr;
       return static_cast<T*>(::operator new(n * sizeof(T)));
   }

   void deallocate(T* ptr) {
       if (ptr) ::operator delete(ptr);
   }
};

Variadic Templates et Forwarding Parfait

Pour construire des objets efficacement, les allocateurs modernes utilisent des modèles à paramètres variables. Cela permet de transmettre n'importe quel nombre d'arguments au constructeur de l'objet cible tout en préservant leur catégorie de valeur (lvalue ou rvalue) via std::forward.

template <typename T>
template <typename... Params>
void construct(T* address, Params&&... params) {
   ::new ((void*)address) T(std::forward<Params>(params)...);
}

Dichotomie entre Allocation et Construction

La sépartaion de l'allocation mémoire et de la construction d'objets offre plusieurs avantages techniques :

• Construction différée : On peut réserver un bloc mémoire massif et n'initialiser les objets qu'au moment opportun.
• Performance : L'allocation système est coûteuse ; en réutilisant un bloc déjà alloué pour plusieurs objets successifs, on réduit la surcharge logicielle.
• Optimisation de la destruction : Pour les types dits "triviaux" (comme int ou double), l'étape de destruction peut être totalement ignorée par le compilateur, accélérant ainsi la libération des ressources.

Les Itérateurs : Pont entre Algorithmes et Données

L'itérateur agit comme une abstraction du pointeur, permettant aux algorithmes de parcourir différentes structures de données (listes, vecteurs, arbres) via une interface uniforme.

Catégories d'itérateurs

La STL définit cinq catégories principales selon les capacités de déplacement et d'accès :

1. Input/Output : Lecture ou écriture unique, progression unidirectionnelle.
2. Forward : Lecture/écriture multiple, progression unidirectionnelle.
3. Bidirectional : Permet de reculer (--it).
4. Random Access : Accès direct par indexation et arithmétique de pointeurs.

Extraction de types (Traits)

La structure iterator_traits est cruciale pour le polymorphisme statique. Elle permet de déterminer à la compilation les propriétés d'un itérateur pour choisir l'implémentation algorithmique la plus performante.

template <typename Iterator>
void process_range(Iterator start, Iterator end) {
   using Category = typename std::iterator_traits<Iterator>::iterator_category;
   optimize_by_category(start, end, Category{});
}

Analyse des Conteneurs Séquentiels et Associatifs

Le cas du Vector

Le vector gère trois pointeurs internes : l'origine des données (start), la fin des éléments actifs (finish) et la limite de la mémoire réservée (end_of_storage).

• Stratégie d'extension : Lors d'un dépassement de capacité, le conteneur alloue généralement 1,5 ou 2 fois la taille actuelle, déplace les anciens éléments et libère l'ancien bloc.
• Réserve (Reserve vs Resize) : reserve modifie la capacité physique sans créer d'objets, tandis que resize altère le nombre d'éléments logiques.

Structures Associatives

• Map : Repose généralement sur un arbre bicloore (Red-Black Tree), garantissant une complexité logarithmique pour l'insertion et la recherche.
• Unoredred Map : Utilise une table de hachage. Elle offre une complexité moyenne constante, mais dépend fortement de la qualité de la fonction de hachage.

Adaptateurs de Conteneurs

Ces composants ne sont pas des structures de données autonomes mais des interfaces restreignant l'accès à un conteneur sous-jacent :

• Stack : Interface LIFO (Last-In, First-Out), s'appuie souvent sur deque.
• Queue : Interface FIFO (First-In, First-Out), utilise par défaut deque.
• Priority Queue : File de priorité utilisant un tas (heap) implémenté sur un vector.