Au-delà des tableaux dynamiques : le Segment Array efficace et stable

Cet article présente le Segment Array, une structure de données performante combinant la flexibilité des tableaux dynamiques, les avantages des pointeurs stables et une excellente compatibilité avec les allocateurs d'arène. Contrairement aux tableaux dynamiques qui déplacent les éléments lors du redimensionnement, le Segment Array utilise des segments pré-alloués de tailles fixes, évitant la fragmentation de la mémoire et l'invalidation des pointeurs. Chaque segment a le double de la taille de son prédécesseur, avec de nouveaux segments alloués uniquement si nécessaire, atteignant une complexité temporelle moyenne de O(1). L'auteur fournit une implémentation en C et détaille son fonctionnement interne, y compris le calcul efficace des index et l'intégration avec les génériques. Le Segment Array est particulièrement utile dans les scénarios nécessitant une gestion efficace de la mémoire dynamique au sein d'un allocateur d'arène, comme dans un profileur de compilation.