Vector làm hỏng iterator khi resize

Vấn đề

std::vector lưu trữ dữ liệu trong một vùng nhớ liên tục. Khi vector cần tăng kích thước vượt quá dung lượng hiện có, nó phải cấp phát một vùng nhớ mới, lớn hơn và sao chép toàn bộ dữ liệu cũ sang đó - điều này khiến mọi iterator, con trỏ, và tham chiếu trỏ đến phần tử cũ trở thành không hợp lệ (invalidated).

#include <vector>
#include <iostream>

int main() {
    std::vector<int> numbers = {1, 2, 3};

    int* ptr = &numbers[0]; // Con trỏ đến phần tử đầu tiên
    std::cout << *ptr << std::endl; // 1 - vẫn ổn

    numbers.push_back(4); // Có thể khiến vector "reallocate" (cấp phát lại) sang vùng nhớ mới!

    std::cout << *ptr << std::endl; // NGUY HIỂM! ptr có thể đang trỏ đến vùng nhớ CŨ, đã không còn hợp lệ

    return 0;
}

Cạm bẫy phổ biến nhất: xóa phần tử khi đang duyệt vòng lặp

#include <vector>
#include <iostream>

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

    for (auto it = numbers.begin(); it != numbers.end(); ++it) {
        if (*it % 2 == 0) {
            numbers.erase(it); // erase() làm hỏng iterator NGAY LẬP TỨC
            // ++it (trong vòng lặp for) giờ thao tác trên iterator ĐÃ KHÔNG HỢP LỆ!
        }
    }
    // Undefined behavior - có thể crash, có thể bỏ sót phần tử, có thể chạy "đúng" một cách ngẫu nhiên

    return 0;
}

Giải pháp: dùng giá trị trả về của erase()

erase() trả về một iterator hợp lệ trỏ đến phần tử ngay sau phần tử vừa bị xóa - dùng giá trị này thay vì tự tăng iterator:

#include <vector>
#include <iostream>

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

    for (auto it = numbers.begin(); it != numbers.end(); ) {
        if (*it % 2 == 0) {
            it = numbers.erase(it); // Dùng iterator MỚI được trả về, không tự ++it
        } else {
            ++it;
        }
    }

    for (int n : numbers) std::cout << n << " "; // 1 3 5

    return 0;
}

Cách hiện đại: std::remove_if + erase (erase-remove idiom)

#include <vector>
#include <algorithm>
#include <iostream>

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

    numbers.erase(
        std::remove_if(numbers.begin(), numbers.end(), [](int n) { return n % 2 == 0; }),
        numbers.end()
    );

    for (int n : numbers) std::cout << n << " "; // 1 3 5

    return 0;
}

Cách tránh reallocate không cần thiết: .reserve()

Nếu biết trước số lượng phần tử tối đa, gọi .reserve() để cấp phát đủ chỗ ngay từ đầu, tránh việc reallocate nhiều lần trong khi thêm phần tử:

std::vector<int> numbers;
numbers.reserve(1000); // Cấp phát sẵn chỗ cho 1000 phần tử

for (int i = 0; i < 1000; i++) {
    numbers.push_back(i); // Không còn reallocate trong vòng lặp này
}

Tóm tắt

Thao tác làm thay đổi kích thước của vector (push_back gây reallocate, erase, insert…) có thể làm hỏng mọi iterator/con trỏ/tham chiếu đang trỏ đến phần tử của nó.

• Không dùng iterator sau khi gọi thao tác có thể làm hỏng nó, trừ khi đó là iterator được trả về từ chính thao tác đó
• Dùng erase-remove idiom (std::remove_if + erase) để xóa nhiều phần tử một cách an toàn
• Gọi .reserve() trước nếu biết trước số lượng phần tử, để tránh reallocate không cần thiết