Anatomie interne du conteneur vector

Un std::vector gère une zone de mémoire contiguë via trois pointeurs internes : un pointant vers le début des données, un autre vers la position juste après le dernier élément valide, et un troisième marquant la fin de l'espace mémoire alloué. Cette conception permet un accès aléatoire en temps constant.

Stratégie de réallocation

Lorsque la capacité est dépassée (par exemple, lors d'un push_back), le vector :

1. Alloue un nouveau bloc mémoire plus grand (souvent 1.5x ou 2x l'ancienne capacité).
2. Transfère les éléments existants vers le nouveau bloc (par déplacement ou copie).
3. Détruit les objets dans l'ancien bloc.
4. Libère l'ancienne allocation mémoire.
5. Met à jour ses pointeurs internes.

Le facteur de croissance varie selon les implémentations de la STL. Observez ce comportement :

#include <iostream>
#include <vector>

int main() {
    std::vector<int> data;
    std::size_t previous_cap = 0;

    for (int idx = 0; idx < 64; ++idx) {
        data.push_back(idx * 10);
        const std::size_t current_cap = data.capacity();
        if (current_cap != previous_cap) {
            double growth_factor = previous_cap == 0 ? 1.0 
                : static_cast<double>(current_cap) / previous_cap;
            std::cout << "Capacité : " << current_cap
                      << " (facteur: " << growth_factor << ")\n";
            previous_cap = current_cap;
        }
    }
}

Libération de la mémoire

Les opérations influençant la mémoire :

• clear() : supprime les éléments mais conserve l'allocation.
• shrink_to_fit() : tente de réduire la capacité à la taille actuelle.
• swap() avec un vector vide : technique pour forcer la libération (précédemment).

std::vector<double> measurements(500, 0.0);
measurements.clear();  // Capacité inchangée
std::cout << "Après clear : " << measurements.capacity() << "\n";
measurements.shrink_to_fit();
std::cout << "Après shrink_to_fit : " << measurements.capacity() << "\n";

Comparaison avec d'autres conteneurs de la STL

Choisir un vector quand l'accès aléatoire fréquent et les opérations en fin de séquence dominent. Préférer deque pour des insertions/suppressions efficaces aux extrémités. Opter pour list lorsque les modifications fréquentes au sein de la séquence sont primordiales.

Techniques d'optimisation

Pré-allocation mémoire

Éviter les réallocations multiples :

// Approche non optimale
std::vector<int> slow;
for (int i = 0; i < 10000; ++i) {
    slow.push_back(i);  // Réallouations potentielles
}

// Approche optimisée avec reserve
std::vector<int> fast;
fast.reserve(10000);
for (int i = 0; i < 10000; ++i) {
    fast.push_back(i);  // Pas de réallocation
}

// Alternative avec construction directe
std::vector<int> direct(10000);
for (int i = 0; i < 10000; ++i) {
    direct[i] = i;  // Utilisation de l'opérateur []
}

Construction en place avec emplace_back

Évite la création d'objets temporaires :

struct SensorReading {
    std::string device_id;
    double value;
    unsigned long timestamp;

    SensorReading(std::string id, double val, unsigned long ts) 
        : device_id(std::move(id)), value(val), timestamp(ts) {}
};

std::vector<SensorReading> log;

// Méthode traditionnelle (copie potentielle)
log.push_back(SensorReading("TEMP_01", 23.5, 1234567890));

// Méthode optimale (construction directe)
log.emplace_back("TEMP_01", 23.5, 1234567890);

Suppression efficace d'éléments

Plusieurs stratégies selon le besoin :

std::vector<int> numbers = {1, 2, 5, 3, 5, 4, 5, 6};

// 1. Supprimer toutes les occurrences d'une valeur (erase-remove)
numbers.erase(
    std::remove(numbers.begin(), numbers.end(), 5),
    numbers.end()
);

// 2. Suppression conditionnelle préservant l'ordre
auto new_end = std::remove_if(numbers.begin(), numbers.end(),
    [](int n) { return n % 2 == 0; }); // Supprimer les nombres pairs
numbers.erase(new_end, numbers.end());

// 3. Suppression rapide ne préservant pas l'ordre
for (auto it = numbers.begin(); it != numbers.end(); ) {
    if (*it == 3) {
        *it = numbers.back();
        numbers.pop_back();
    } else {
        ++it;
    }
}

Applications pratiques

Gestion de données spatiales

#include <vector>
#include <cmath>

struct Point2D {
    float x, y;
    
    float distance_to(const Point2D& other) const {
        float dx = x - other.x;
        float dy = y - other.y;
        return std::sqrt(dx*dx + dy*dy);
    }
};

class PointCloud {
    std::vector<Point2D> points;
    
public:
    void add_point(float x, float y) {
        points.emplace_back(x, y);
    }
    
    std::vector<Point2D> neighbors_within_radius(const Point2D& center, 
                                                 float radius) const {
        std::vector<Point2D> result;
        for (const auto& pt : points) {
            if (center.distance_to(pt) <= radius) {
                result.push_back(pt);
            }
        }
        return result;
    }
    
    void compress_by_removing_duplicates(float tolerance) {
        // Implémentation simplifiée
        for (size_t i = 0; i < points.size(); ++i) {
            for (size_t j = i + 1; j < points.size(); ) {
                if (points[i].distance_to(points[j]) < tolerance) {
                    points[j] = points.back();
                    points.pop_back();
                } else {
                    ++j;
                }
            }
        }
    }
};

Traitement de séries temporelles

#include <vector>
#include <numeric>
#include <algorithm>

template<typename T>
class TimeSeries {
    std::vector<T> values;
    std::vector<unsigned long> timestamps;
    
public:
    void record(T value, unsigned long ts) {
        values.push_back(value);
        timestamps.push_back(ts);
    }
    
    double moving_average(std::size_t window_size, std::size_t end_index) const {
        if (end_index < window_size - 1) return 0.0;
        
        auto start_it = values.begin() + (end_index - window_size + 1);
        auto end_it = values.begin() + end_index + 1;
        
        T sum = std::accumulate(start_it, end_it, T(0));
        return static_cast<double>(sum) / window_size;
    }
    
    void resample(unsigned long new_interval) {
        // Implémentation d'un rééchantillonnage simplifié
        std::vector<T> new_values;
        std::vector<unsigned long> new_timestamps;
        
        unsigned long last_ts = 0;
        for (size_t i = 0; i < values.size(); ++i) {
            if (timestamps[i] - last_ts >= new_interval) {
                new_values.push_back(values[i]);
                new_timestamps.push_back(timestamps[i]);
                last_ts = timestamps[i];
            }
        }
        
        values = std::move(new_values);
        timestamps = std::move(new_timestamps);
    }
};

Aspects techniques avencés

Itérateurs et invalidation

Les itérateurs de vector peuvent être invalidés lors :

• D'une réallocation (appel à reserve, resize ou push_back causant une allocation).
• D'une insertion avant la position pointée par l'itérateur.
• D'une suppression à la position ou avant la position de l'itérateur.

Complexité amortie

La complexité en temps de push_back est :

• Cas meilleur : O(1) quand de l'espace est disponible.
• Cas pire : O(n) lors d'une réallocation avec copie de tous les éléments.
• Complexité amortie : O(1) sur une séquence d'opérations.

Bonnes pratiques

• Pré-allouer avec reserve lorsque la taille finale est connue ou estimable.
• Privilégier emplace_back pour construire des objets directement dans le conteneur.
• Éviter les insertions/suppressions au milieu si des opérations fréquentes sont nécessaires.
• Utiliser les algorithmes de la STL (std::sort, std::find, std::remove_if) pour des opérations optimisées.
• Surveiller la mémoire dans les applications critiques, utiliser shrink_to_fit si nécessaire.
• Considérer la localité spatiale pour l'accès aux données : parcours séquentiels sont plus efficaces.