Utilisation de std::vector en C++

std::vector est le conteneur séquentiel le plus utilisé en C++. Il fournit un tableau dynamique stocké en mémoire contiguë : accès aléatoire O(1), push_back amorti O(1), et généralement O(n) pour les insertions ou suppressions au milieu (déplacement des éléments). Cet article couvre la gestion de capacité (size/capacity), la croissance, reserve/resize, push_back vs emplace_back, l’invalidation des itérateurs, la disposition mémoire (data()), shrink_to_fit et divers conseils de performance.

1) Utilisation de base

#include <vector>
#include <iostream>
using namespace std;

int main() {
    vector<int> v;                // vide
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);

    cout << "size=" << v.size()
         << " capacity=" << v.capacity() << "\n";

    cout << v[1] << " " << v.at(2) << "\n"; // [] non vérifié, at() vérifié

    for (int x : v) cout << x << " ";
}

size indique le nombre d’éléments, tandis que capacity indique la quantité d’éléments pouvant être stockés avant réallocation.

2) Mémoire contiguë et data()

Un vector stocke ses éléments dans une mémoire contiguë, ce qui permet son utilisation directe dans des APIs C.

#include <cstring>  // memcpy
#include <vector>

int main() {
    vector<char> buf(8, 0);
    const char* msg = "C++";
    memcpy(buf.data(), msg, 3);
}

Cette disposition est avantageuse pour l’E/S, le SIMD, les graphiques, les buffers réseau et l’interfaçage avec C.

3) Stratégie de croissance, reserve et resize

• reserve(n) : augmente la capacité à au moins n sans changer la taille.
• resize(n) : modifie la taille en l’ajustant à n.

#include <vector>
#include <iostream>
using namespace std;

int main() {
    vector<int> v;

    v.reserve(1000);          
    for (int i=0; i<1000; i++)
        v.push_back(i);

    v.resize(1200, -1);       

    cout << v.size() << " " << v.capacity() << "\n";
}

Le facteur de croissance varie selon l’implémentation (~1,5–2× généralement). reserve améliore fortement les performances lorsque la taille finale est connue.

4) Insertion et suppression : push_back vs emplace_back, insert/erase

• push_back(x) : copie ou déplace l’objet.
• emplace_back(args...) : construit l’objet directement en place.
• insert/erase : déplace des éléments → souvent O(n).

#include <string>
#include <vector>
using namespace std;

struct Book {
    string title;
    double price;
    int pages;
    Book(string t, double p, int s)
        : title(t), price(p), pages(s) {}
};

int main() {
    vector<Book> books;
    books.emplace_back("C++ Primer", 180.0, 950);
    books.push_back(Book{"Effective C++", 150.0, 320});
    books.insert(books.begin(), {"Clean Code", 175.0, 464});
    books.erase(books.begin() + 1);
}

emplace_back est idéal pour les objets coûteux à copier. Pour de nombreuses insertions au milieu, envisagez deque ou list.

5) Invalidation des itérateurs

Les réallocations et les déplacements d’éléments peuvent invalider itérateurs, pointeurs et références.

• Réallocation : invalide tous les itérateurs/références.
• insert/erase : invalide à partir de la position modifiée.

#include <vector>
using namespace std;

int main() {
    vector<int> v{1,2,3};
    auto it = v.begin();
    v.push_back(4);   // peut réallouer
    // 'it' peut maintenant être invalide
}

Utilisez reserve pour éviter les réallocations ; regénérez vos itérateurs après les opérations à risque.

6) Conseils de performance

• Utilisez reserve si vous connaissez la taille finale.
• Utilisez emplace_back pour une construction directe.
• Privilégiez les mouvements (move semantics).
• Insérer au milieu coûte : préférez la fin du vector.
• clear() ne réduit pas la capacité.
• shrink_to_fit() est non garanti.

7) assign, swap, shrink_to_fit

#include <vector>
using namespace std;

int main() {
    vector<int> v{1,2,3,4,5};

    v.assign(3, 9);              // {9, 9, 9}

    vector<int>(v).swap(v);      // technique de réduction (shrink idiom)
    v.shrink_to_fit();           
}

La technique dite “shrink idiom” est souvent plus efficace que shrink_to_fit().

8) Tri, recherche et algorithmes

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int main() {
    vector<int> a{5,1,4,2,3};

    sort(a.begin(), a.end());                // 1 2 3 4 5
    bool found4 = binary_search(a.begin(), a.end(), 4);
    auto pos = lower_bound(a.begin(), a.end(), 3);

    cout << found4 << " @" << (pos - a.begin()) << "\n";
}

Avec C++20, std::ranges offre des pipelines plus clairs.

9) Concepts avancés : Allocateurs, vector<bool>, petits objets

• Allocateurs personnalisés : pools mémoire, traces, alignement…
• vector<bool> : spécialisation compactée en bits ; prudence avec les références proxy.
• Optimisation petits objets : concerne std::string, pas vector.

10) Exemple : Liste de livres

#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

struct Book {
    string title;
    double price;
    int pages;
    Book(string t, double p, int s)
        : title(move(t)), price(p), pages(s) {}
};

int main() {
    vector<Book> books;
    books.reserve(4);

    books.emplace_back("C++ Primer", 180.0, 950);
    books.emplace_back("Effective C++", 150.0, 320);
    books.emplace_back("Clean Code", 175.0, 464);

    sort(books.begin(), books.end(),
         [](const Book& a, const Book& b){
             return a.price < b.price;
         });

    auto it = find_if(books.begin(), books.end(),
        [](const Book& b){ return b.price >= 160.0; });

    if (it != books.end())
        cout << it->title << " " << it->price << "\n";
}

11) Erreurs fréquentes

• Utiliser vector pour beaucoup d’insertions au milieu → préférer deque ou list.
• Utiliser des itérateurs invalidés après réallocation.
• Effectuer des copies inutiles au lieu de mouvements ou d’emplacements.
• Ne pas utiliser reserve quand la taille est connue.
• Supposer que vector<bool> fonctionne comme un vector normal.

12) TL;DR

Articles connexes