Structures de données en C/C++

Le tableau dynamique et std::vector en C et C++

Dans cette leçon, vous allez implémenter en C un tableau dynamique qui s'agrandit tout seul quand on ajoute des éléments, puis le comparer à std::vector en C++.

Introduction

Un tableau dynamique (dynamic array) est un tableau qui peut grandir si nécessaire. Il distingue deux notions : le nombre d'éléments contenus (size) et la place allouée (capacity). Quand le tableau est plein, le programme alloue une zone plus grande, généralement le double, et y déplace les données.

Points importants

Définissez les conditions qui doivent toujours être vraies (invariants) avant d'écrire les opérations.
Traitez les cas de structure vide, pleine et d'échec d'allocation mémoire.
Évaluez ensemble la complexité et la gestion mémoire de chaque opération.

Voir comment ça marche

Appuyez plusieurs fois sur push_back. Quand le tableau est plein, il alloue un bloc deux fois plus grand et y copie tout.

Exemples de code C et C++

Exécuter →

main.c

#include <stdio.h>
#include <stdlib.h>

int main(void) {
    size_t size = 0, capacity = 2;
    int *values = malloc(capacity * sizeof *values);
    if (!values) return 1;
    for (int value = 1; value <= 5; ++value) {
        if (size == capacity) {
            capacity *= 2;
            int *grown = realloc(values, capacity * sizeof *values);
            if (!grown) {
                free(values);
                return 1;
            }
            values = grown;
        }
        values[size++] = value * value;
    }
    printf("size=%zu capacity=%zu last=%d\n",
           size, capacity, values[size - 1]);
    free(values);
}

Résultat de l’exécution

size=5 capacity=8 last=25

C++

Exécuter →

main.cpp

#include <iostream>
#include <vector>

int main() {
    std::vector<int> values;
    for (int value = 1; value <= 5; ++value) {
        values.push_back(value * value);
    }
    std::cout << "size=" << values.size()
              << " last=" << values.back() << '\n';
}

Résultat de l’exécution

size=5 last=25

Comparaison entre C et C++

Dans la version C, quand size atteint capacity, le programme double capacity et appelle realloc pour agrandir la mémoire. Le résultat de realloc est placé dans un pointeur temporaire, grown, pour que l'ancienne mémoire puisse encore être libérée si l'allocation échoue. std::vector en C++ encapsule exactement cette stratégie de croissance, et en plus libère lui-même la mémoire, prend en charge les itérateurs et reste sûr face aux exceptions.

Les données (struct) et les opérations sont séparées, et la mémoire est allouée et libérée à la main.

C++

Les classes et les conteneurs protègent la cohérence des données et gèrent eux-mêmes leurs ressources.

Exercices d'approfondissement

Exécutez les deux versions, puis modifiez le code pour observer la différence de sécurité qu'apporte chaque langage.

Ajoutez des tests pour l'état vide et pour le moment où la capacité maximale est atteinte.
Écrivez la libération de la mémoire et vérifiez qu'il n'y a pas de fuite.
Comparez la complexité avec celle du conteneur équivalent de la bibliothèque standard.

S'entraîner avec un défi

Utilisez le contenu de cette leçon pour résoudre un vrai problème. Chaque défi s'exécute dans le navigateur, avec des tests instantanés et une revue par l'IA.

Tous les défis