Bài 13.2: Sử dụng Iterator với Vector trong C++

Chào mừng các bạn quay trở lại với series blog của FullhouseDev về lập trình C++! Trong các bài trước, chúng ta đã tìm hiểu về vector, một trong những container (kiểu dữ liệu chứa) phổ biến và mạnh mẽ nhất trong Thư viện Mẫu Chuẩn (STL) của C++. Chúng ta đã biết cách thêm, truy cập và xóa các phần tử bằng chỉ mục ([]) hoặc các phương thức như push_back, pop_back, v.v.

Tuy nhiên, khi làm việc với các container khác trong STL như list, set, hay map, việc truy cập bằng chỉ mục không phải lúc nào cũng khả dụng hoặc hiệu quả. Đây là lúc iterator phát huy sức mạnh của mình. Iterator cung cấp một cách thống nhất để truy cập và duyệt qua các phần tử trong bất kỳ container nào của STL.

Trong bài viết này, chúng ta sẽ tập trung tìm hiểu sâu hơn về cách sử dụng iterator đặc biệt với vector. Mặc dù vector có thể truy cập bằng chỉ mục, việc hiểu và sử dụng iterator sẽ mở ra cánh cửa để bạn làm việc hiệu quả hơn với các thuật toán của STL và các loại container khác sau này.

Hãy cùng đi sâu vào thế giới của iterator!

Iterator là gì? Tại sao lại dùng nó với Vector?

Hãy tưởng tượng iterator như một con trỏ thông minh hoặc một "con trỏ" ảo trỏ đến một phần tử cụ thể bên trong một container. Thay vì chỉ trỏ đến một địa chỉ bộ nhớ cố định như con trỏ thông thường, iterator hiểu cấu trúc của container mà nó đang làm việc.

Với vector, chúng ta có thể truy cập phần tử thứ i bằng vec[i]. Đây là cách nhanh chóng và đơn giản khi bạn biết chỉ mục. Nhưng iterator cung cấp một góc nhìn khác:

Tính tổng quát: Iterator hoạt động trên tất cả các container của STL theo cùng một cách cơ bản (duyệt, truy cập phần tử hiện tại, di chuyển đến phần tử tiếp theo). Điều này giúp bạn viết mã linh hoạt hơn, có thể chuyển đổi giữa các loại container dễ dàng hơn mà không cần thay đổi logic duyệt.
Tương thích với thuật toán STL: Hầu hết các thuật toán trong <algorithm> của STL (như sort, find, copy, v.v.) đều hoạt động dựa trên iterator. Bạn cung cấp cho chúng cặp iterator chỉ định phạm vi (từ đâu đến đâu) để thực hiện thuật toán.
Thao tác phức tạp: Đối với các thao tác như chèn (insert) hoặc xóa (erase) phần tử trong khi đang duyệt qua vector, việc sử dụng iterator là cách chính xác và an toàn (khi hiểu rõ quy tắc).

Mặc dù vector hỗ trợ truy cập ngẫu nhiên (như mảng), nó cũng cung cấp đầy đủ bộ iterator để bạn làm việc theo phong cách STL.

Bắt đầu với `begin()` và `end()`

Mỗi container trong STL, bao gồm cả vector, đều cung cấp các phương thức để lấy iterator đánh dấu các vị trí quan trọng:

vec.begin(): Trả về một iterator trỏ đến phần tử đầu tiên của vector.
vec.end(): Trả về một iterator trỏ đến vị trí ngay sau phần tử cuối cùng của vector.

Lưu ý quan trọng: end() không trỏ đến phần tử cuối cùng. Nó trỏ đến một vị trí "không tồn tại" ngay sau phần tử cuối. Đây là quy ước chuẩn trong STL để biểu thị điểm kết thúc của một phạm vi.

Hãy xem một ví dụ đơn giản:

#include <iostream>
#include <vector>
#include <string> // Để dùng string

int main() {
    vector<string> fruits = {"Apple", "Banana", "Cherry"};

    // Lấy iterator trỏ đến phần tử đầu tiên
    vector<string>::iterator it_begin = fruits.begin();

    // Lấy iterator trỏ đến vị trí ngay sau phần tử cuối cùng
    vector<string>::iterator it_end = fruits.end();

    // Truy cập giá trị của phần tử đầu tiên sử dụng dereference operator (*)
    // Phải đảm bảo vector không rỗng trước khi dereference begin()
    if (!fruits.empty()) {
        cout << "Phan tu dau tien (qua iterator): " << *it_begin << endl;
    }

    // it_end khong duoc dereference vi no khong tro den mot phan tu hop le

    return 0;
}

Giải thích:

Chúng ta khai báo một vector chứa các chuỗi.
fruits.begin() trả về một iterator mà chúng ta lưu vào biến it_begin. Kiểu dữ liệu của iterator này được khai báo là vector<string>::iterator. Đây là kiểu chuẩn để khai báo iterator có thể đọc và ghi cho một vector chứa string.
fruits.end() trả về iterator kết thúc, lưu vào it_end.
*it_begin sử dụng toán tử dereference (*) để truy cập giá trị của phần tử mà it_begin đang trỏ tới (là chuỗi "Apple").
Chúng ta không thể sử dụng *it_end vì it_end không trỏ đến một phần tử hợp lệ trong vector.

Duyệt Vector bằng Iterator (Vòng lặp `while`)

Cách phổ biến để duyệt qua toàn bộ các phần tử của một container sử dụng iterator là bắt đầu từ begin() và dừng lại khi gặp end(). Ta có thể dùng vòng lặp while:

#include <iostream>
#include <vector>

int main() {
    vector<int> numbers = {10, 20, 30, 40, 50};

    // Khai báo và khởi tạo iterator tại vị trí bắt đầu
    vector<int>::iterator it = numbers.begin();

    cout << "Duyet vector bang while loop voi iterator:" << endl;
    // Vong lap tiep tuc cho den khi iterator dat den vi tri ket thuc (end())
    while (it != numbers.end()) {
        // Truy cap gia tri phan tu hien tai
        cout << *it << " ";

        // Di chuyen iterator sang phan tu tiep theo
        ++it; // Nen dung pre-increment (++it) vi thuong hieu qua hon post-increment (it++) voi iterator
    }
    cout << endl;

    return 0;
}

Giải thích:

Chúng ta khởi tạo it bằng numbers.begin().
Điều kiện lặp it != numbers.end() đảm bảo vòng lặp chạy cho đến khi it không còn trỏ tới một phần tử hợp lệ trong phạm vi [ begin(), end() ).
Trong mỗi lần lặp:
- *it truy cập giá trị của phần tử hiện tại.
- ++it di chuyển iterator it sang phần tử kế tiếp. Việc sử dụng ++it thay vì it++ thường được khuyến khích cho iterator vì nó có thể hiệu quả hơn trong một số trường hợp (mặc dù đối với iterator của vector, sự khác biệt thường không đáng kể).

Duyệt Vector bằng Iterator (Vòng lặp `for` truyền thống)

Vòng lặp for truyền thống là một cách viết gọn hơn cho vòng lặp while ở trên khi bạn biết rõ ba phần: khởi tạo, điều kiện dừng và bước di chuyển.

#include <iostream>
#include <vector>

int main() {
    vector<double> values = {1.1, 2.2, 3.3, 4.4};

    cout << "Duyet vector bang for loop truyen thong voi iterator:" << endl;
    // Khai bao | Dieu kien | Buoc nhay
    for (vector<double>::iterator it = values.begin(); it != values.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;

    return 0;
}

Giải thích:

Cú pháp của vòng lặp for gom ba phần:
- Khởi tạo: vector<double>::iterator it = values.begin();
- Điều kiện dừng: it != values.end();
- Bước nhảy: ++it;
Kết quả tương tự như vòng lặp while, chỉ là cú pháp khác.

(Lưu ý: Đối với việc chỉ duyệt đơn giản như thế này mà không cần thao tác phức tạp, vòng lặp for dựa trên phạm vi (range-based for loop) for (auto& element : vector) thường là cách đọc và viết ngắn gọn nhất.)

Các Phép Toán Cơ Bản với Iterator

Đối với vector, iterator của nó thuộc loại Random Access Iterator. Điều này có nghĩa là ngoài các phép toán cơ bản (*, ++, ==, !=), nó còn hỗ trợ các phép toán của con trỏ, cho phép di chuyển ngẫu nhiên và so sánh vị trí:

*it: Truy cập giá trị phần tử mà it trỏ tới.
++it: Di chuyển it tới phần tử kế tiếp.
--it: Di chuyển it tới phần tử đứng trước (chỉ cho Random Access Iterator trở lên).
it + n: Trả về một iterator mới trỏ tới phần tử cách it n vị trí về phía sau.
it - n: Trả về một iterator mới trỏ tới phần tử cách it n vị trí về phía trước.
it1 - it2: Trả về số lượng phần tử giữa it2 và it1 (chỉ cho Random Access Iterator).
it1 == it2: So sánh hai iterator có trỏ cùng một vị trí không.
it1 != it2: So sánh hai iterator có trỏ khác vị trí không.
it1 < it2, it1 <= it2, it1 > it2, it1 >= it2: So sánh vị trí tương đối (chỉ cho Random Access Iterator trở lên).

Ví dụ sử dụng các phép toán này:

#include <iostream>
#include <vector>

int main() {
    vector<char> letters = {'a', 'b', 'c', 'd', 'e'};

    auto it_first = letters.begin(); // iterator tro den 'a'
    auto it_third = letters.begin() + 2; // iterator tro den 'c' (tu 'a' di 2 buoc)
    auto it_last = letters.end() - 1; // iterator tro den 'e' (tu end() lui 1 buoc)

    cout << "Phan tu dau tien: " << *it_first << endl;
    cout << "Phan tu thu ba: " << *it_third << endl;
    cout << "Phan tu cuoi cung: " << *it_last << endl;

    // Di chuyen iterator hien tai
    auto it_current = letters.begin();
    ++it_current; // it_current bay gio tro den 'b'
    cout << "Sau khi ++it_current: " << *it_current << endl;
    --it_current; // it_current bay gio tro lai 'a'
    cout << "Sau khi --it_current: " << *it_current << endl;

    // So sanh iterator
    if (it_first == letters.begin()) {
        cout << "it_first tro cung vi tri voi begin()." << endl;
    }

    if (it_third > it_first) {
        cout << "it_third dung sau it_first trong vector." << endl;
    }

    // Tinh khoang cach (so phan tu)
    ptrdiff_t distance = it_last - it_first; // ptrdiff_t la kieu chuan cho ket qua phep tru iterator
    cout << "Khoang cach tu 'a' den 'e' la " << distance << " phan tu." << endl;


    return 0;
}

Giải thích:

auto được sử dụng để tự suy ra kiểu của iterator, giúp code gọn hơn. auto it_begin = letters.begin(); tương đương với vector<char>::iterator it_begin = letters.begin();.
Chúng ta có thể dùng + và - để di chuyển iterator một số bước nhất định.
Các phép toán so sánh (==, !=, <, >, v.v.) giúp kiểm tra vị trí tương đối của các iterator.
Phép trừ hai iterator trả về khoảng cách giữa chúng (số lượng phần tử). Kiểu trả về chuẩn là ptrdiff_t.

Iterator Đảo Ngược: `rbegin()` và `rend()`

STL cung cấp reverse iterator để duyệt ngược từ cuối lên đầu một cách tự nhiên.

vec.rbegin(): Trả về một reverse iterator trỏ đến phần tử cuối cùng của vector.
vec.rend(): Trả về một reverse iterator trỏ đến vị trí ngay trước phần tử đầu tiên của vector (tương đương với begin() khi nhìn từ đầu).

Khi bạn tăng (++) một reverse iterator, nó sẽ di chuyển về phía đầu của container.

#include <iostream>
#include <vector>

int main() {
    vector<int> scores = {90, 75, 88, 95, 80};

    cout << "Duyet nguoc vector bang reverse iterator:" << endl;
    // Kieu reverse iterator
    for (vector<int>::reverse_iterator rit = scores.rbegin(); rit != scores.rend(); ++rit) {
        cout << *rit << " ";
    }
    cout << endl;

    return 0;
}

Giải thích:

Chúng ta sử dụng kiểu vector<int>::reverse_iterator.
Vòng lặp bắt đầu từ scores.rbegin() (phần tử cuối cùng, 80) và kết thúc khi đạt đến scores.rend() (vị trí trước phần tử đầu tiên).
Toán tử ++rit di chuyển reverse iterator từ 80 -> 95 -> 88 -> 75 -> 90.

Tương tự, bạn có thể sử dụng rbegin() và rend() trong vòng lặp while.

Iterator Hằng: `cbegin()`, `cend()`, `crbegin()`, `crend()`

Đôi khi bạn chỉ muốn duyệt qua các phần tử của vector để đọc giá trị mà không muốn hoặc không được phép thay đổi chúng. Lúc này, bạn nên sử dụng constant iterator.

vec.cbegin(): Trả về constant iterator trỏ đến phần tử đầu tiên.
vec.cend(): Trả về constant iterator trỏ đến vị trí ngay sau phần tử cuối cùng.
vec.crbegin(): Trả về constant reverse iterator trỏ đến phần tử cuối cùng.
vec.crend(): Trả về constant reverse iterator trỏ đến vị trí ngay trước phần tử đầu tiên.

Điểm khác biệt chính là bạn không thể sử dụng toán tử * để gán giá trị mới cho phần tử mà constant iterator trỏ tới.

#include <iostream>
#include <vector>
#include <string>

int main() {
    const vector<string> colors = {"Red", "Green", "Blue"}; // Vector constant

    cout << "Duyet vector constant bang constant iterator:" << endl;
    // Kieu constant iterator
    for (vector<string>::const_iterator cit = colors.cbegin(); cit != colors.cend(); ++cit) {
        cout << *cit << " ";
        // *cit = "Yellow"; // <--- Dong nay se gay loi bien dich vi cit la constant iterator
    }
    cout << endl;

    // Voi vector khong constant, van co the dung cbegin/cend de chi doc
    vector<int> data = {1, 2, 3};
    cout << "Duyet vector khong constant chi doc bang constant iterator:" << endl;
    for (auto ccit = data.cbegin(); ccit != data.cend(); ++ccit) {
        cout << *ccit << " ";
        // *ccit = 10; // <--- Dong nay cung gay loi bien dich
    }
    cout << endl;

    return 0;
}

Giải thích:

Kiểu dữ liệu là vector<string>::const_iterator.
Khi làm việc với một vector được khai báo là const, bạn bắt buộc phải sử dụng các phương thức trả về constant iterator như cbegin() và cend().
Ngay cả với một vector không phải const, bạn vẫn có thể gọi cbegin() và cend() nếu chỉ muốn đọc dữ liệu. Điều này giúp thể hiện rõ ràng mục đích của bạn trong mã và ngăn chặn việc vô ý thay đổi dữ liệu.

Sửa Đổi Phần Tử bằng Iterator

Nếu bạn có một iterator thông thường (không phải constant iterator), bạn có thể sử dụng toán tử dereference (*) để truy cập và sửa đổi giá trị của phần tử mà nó trỏ tới.

#include <iostream>
#include <vector>

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

    cout << "Vector truoc khi sua doi: ";
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl;

    // Su dung iterator de nhan doi moi phan tu
    for (auto it = numbers.begin(); it != numbers.end(); ++it) {
        *it = *it * 2; // Su dung *it o ben trai phep gan de sua doi gia tri
    }

    cout << "Vector sau khi nhan doi: ";
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

Giải thích:

Chúng ta duyệt qua vector bằng iterator thông thường (auto it = numbers.begin()).
Bên trong vòng lặp, *it = *it * 2; truy cập giá trị hiện tại (*it ở bên phải phép gán), nhân đôi nó, và gán lại giá trị mới vào vị trí mà it đang trỏ tới (*it ở bên trái phép gán).

Chèn Phần Tử bằng Iterator (`insert`)

Phương thức insert() của vector cho phép bạn chèn một hoặc nhiều phần tử vào một vị trí cụ thể được chỉ định bởi một iterator.

Cú pháp cơ bản: vec.insert(position_iterator, value);

position_iterator: Một iterator trỏ đến vị trí mà bạn muốn chèn phần tử trước nó.
value: Giá trị của phần tử cần chèn.

Phương thức insert() trả về một iterator trỏ đến phần tử đầu tiên vừa được chèn vào. Điều quan trọng cần nhớ là insert() có thể làm mất hiệu lực (invalidate) các iterator hiện có trỏ đến vị trí chèn hoặc sau vị trí chèn (bao gồm cả end()).

#include <iostream>
#include <vector>
#include <string>

int main() {
    vector<string> words = {"apple", "banana", "date"};

    cout << "Vector truoc khi chen: ";
    for (const auto& word : words) {
        cout << word << " ";
    }
    cout << endl;

    // Chen "cherry" vao giua "banana" va "date"
    // Can tim iterator tro den "date"
    auto it_date = words.begin();
    while (it_date != words.end() && *it_date != "date") {
        ++it_date;
    }

    if (it_date != words.end()) {
        // it_date bay gio tro den "date", chung ta chen "cherry" TRUOC vi tri nay
        words.insert(it_date, "cherry");
        cout << "Vector sau khi chen 'cherry': ";
        for (const auto& word : words) {
            cout << word << " ";
        }
        cout << endl;
    }

    // Chen "apricot" vao dau vector
    words.insert(words.begin(), "apricot");
     cout << "Vector sau khi chen 'apricot' vao dau: ";
    for (const auto& word : words) {
        cout << word << " ";
    }
    cout << endl;

    // Chen "elderberry" vao cuoi vector (truoc end())
    words.insert(words.end(), "elderberry");
     cout << "Vector sau khi chen 'elderberry' vao cuoi: ";
    for (const auto& word : words) {
        cout << word << " ";
    }
    cout << endl;

    return 0;
}

Giải thích:

Chúng ta tìm iterator trỏ đến chuỗi "date" bằng một vòng lặp đơn giản.
words.insert(it_date, "cherry"); chèn chuỗi "cherry" vào vị trí mà it_date đang trỏ tới (trước "date").
words.insert(words.begin(), "apricot"); chèn "apricot" vào đầu vector.
words.insert(words.end(), "elderberry"); chèn "elderberry" vào cuối vector (trước vị trí kết thúc giả định).

Xóa Phần Tử bằng Iterator (`erase`)

Phương thức erase() của vector cho phép bạn xóa một hoặc một phạm vi các phần tử được chỉ định bởi iterator.

Cú pháp:

vec.erase(position_iterator); : Xóa phần tử tại vị trí được trỏ bởi iterator.
vec.erase(first_iterator, last_iterator); : Xóa các phần tử trong phạm vi [ first_iterator, last_iterator ).

Phương thức erase() trả về một iterator trỏ đến phần tử ngay sau phần tử (hoặc phạm vi) vừa bị xóa. Giống như insert(), erase() làm mất hiệu lực iterator bị xóa và tất cả các iterator trỏ đến vị trí sau vị trí xóa (bao gồm cả end()).

Điều này rất quan trọng khi xóa phần tử trong vòng lặp duyệt. Bạn phải sử dụng giá trị trả về của erase để có được iterator hợp lệ cho lần lặp kế tiếp.

#include <iostream>
#include <vector>
#include <algorithm> // Can cho remove

int main() {
    vector<int> nums = {10, 20, 30, 40, 50, 60};

    cout << "Vector ban dau: ";
    for (int n : nums) cout << n << " ";
    cout << endl;

    // Xoa phan tu thu 3 (gia tri 30)
    auto it_to_erase = nums.begin() + 2; // Iterator tro den 30
    cout << "Xoa phan tu: " << *it_to_erase << endl;
    nums.erase(it_to_erase);

    cout << "Vector sau khi xoa 30: ";
    for (int n : nums) cout << n << " ";
    cout << endl; // Vector: 10 20 40 50 60

    // Xoa mot pham vi phan tu (tu 40 den het tru 60)
    auto it_start_erase = nums.begin() + 2; // Bay gio tro den 40
    auto it_end_erase = nums.begin() + 4;   // Bay gio tro den 60 (se xoa truoc vi tri nay)
    cout << "Xoa pham vi tu " << *it_start_erase << " den truoc " << *it_end_erase << endl;
    nums.erase(it_start_erase, it_end_erase); // Xoa 40, 50

    cout << "Vector sau khi xoa pham vi: ";
    for (int n : nums) cout << n << " ";
    cout << endl; // Vector: 10 20 60

    // VÍ DỤ QUAN TRỌNG: Xóa trong vòng lặp
    vector<int> data = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    cout << "Vector du lieu goc: ";
    for (int n : data) cout << n << " ";
    cout << endl;

    // Xoa tat ca cac so chan
    auto it = data.begin();
    while (it != data.end()) {
        if (*it % 2 == 0) {
            // Xoa phan tu hien tai va cap nhat iterator bang gia tri tra ve cua erase
            it = data.erase(it);
            // it bay gio da tro den phan tu TIEP THEO hop le, khong can ++it o day
        } else {
            // Neu khong xoa, di chuyen den phan tu tiep theo nhu binh thuong
            ++it;
        }
    }

    cout << "Vector sau khi xoa so chan (trong loop): ";
    for (int n : data) cout << n << " ";
    cout << endl; // Vector: 1 3 5 7 9

    return 0;
}

Giải thích:

Ví dụ đầu tiên minh họa cách xóa một phần tử hoặc một phạm vi bằng cách sử dụng các iterator đã xác định trước.
Ví dụ thứ ba (VÍ DỤ QUAN TRỌNG) cho thấy cách xóa phần tử trong khi đang duyệt.
- Chúng ta dùng vòng lặp while hoặc for truyền thống.
- Khi tìm thấy phần tử cần xóa (*it % 2 == 0), chúng ta gọi data.erase(it).
- Giá trị trả về của erase(it) là iterator trỏ đến phần tử nằm ngay sau phần tử vừa bị xóa. Chúng ta gán lại giá trị này cho it (it = data.erase(it);). Điều này đảm bảo rằng trong lần lặp tiếp theo, it sẽ trỏ đến phần tử đúng, và vòng lặp while (it != data.end()) vẫn hoạt động chính xác với iterator mới.
- Nếu không xóa phần tử, chúng ta di chuyển iterator bằng ++it; như bình thường.
Nếu bạn không gán lại giá trị trả về của erase khi xóa trong vòng lặp, iterator it sẽ bị mất hiệu lực và việc sử dụng nó trong lần lặp kế tiếp (kể cả kiểm tra điều kiện it != data.end()) sẽ dẫn đến undefined behavior (lỗi không xác định, rất khó debug).

(Lưu ý: Với các tác vụ xóa theo điều kiện như ví dụ cuối cùng, thuật toán remove_if kết hợp với erase là cách làm idiomatic và thường hiệu quả hơn trong C++ hiện đại: data.erase(remove_if(data.begin(), data.end(), [](int n){ return n % 2 == 0; }), data.end());)

Iterator và Hiệu suất của Vector

Mặc dù iterator cung cấp tính tổng quát và cần thiết cho nhiều thuật toán/thao tác, điều quan trọng cần nhớ về vector là:

vector lưu trữ các phần tử liền kề trong bộ nhớ (giống như mảng).
Truy cập bằng chỉ mục ([]) là thao tác hằng số (O(1)) - rất nhanh.
Thêm/xóa ở cuối (push_back, pop_back) thường là thao tác hằng số trung bình (O(1) average), nhưng có thể là tuyến tính (O(n)) nếu cần cấp phát lại bộ nhớ.
Thêm/xóa ở giữa hoặc đầu bằng insert() hoặc erase() yêu cầu di chuyển tất cả các phần tử phía sau vị trí thao tác để duy trì tính liền kề. Đây là thao tác tuyến tính (O(n)).
Việc sử dụng iterator để duyệt không làm cho việc truy cập chậm hơn so với chỉ mục đối với vector. Thực tế, iterator của vector thường được triển khai đơn giản như các con trỏ.

Do đó, hãy chọn cách tiếp cận phù hợp nhất với tác vụ:

Duyệt đơn giản: Range-based for loop (for (auto& element : vector)) là ngắn gọn và rõ ràng nhất.
Truy cập theo chỉ mục: Dùng [] hoặc .at() khi bạn biết chỉ mục và muốn truy cập ngẫu nhiên.
Duyệt, sửa đổi tại chỗ, hoặc cần tương tác với thuật toán STL: Dùng iterator.
Chèn/xóa ở giữa/đầu: Dùng iterator với insert/erase. Cẩn thận với việc mất hiệu lực của iterator khi xóa trong vòng lặp.

Iterator Invalidation (Mất Hiệu Lực Iterator)

Đây là một điểm phức tạp và quan trọng khi sử dụng iterator với vector.

Khi bạn thay đổi kích thước hoặc cấu trúc bộ nhớ của vector (ví dụ: bằng insert(), erase(), push_back() khi dung lượng đầy, resize(), assign(), clear()), một số hoặc tất cả các iterator và reference (tham chiếu) mà bạn đang giữ có thể bị mất hiệu lực.

Khi chèn (insert): Tất cả các iterator và reference tại vị trí chèn và sau vị trí chèn bị mất hiệu lực. end() cũng bị mất hiệu lực.
Khi xóa (erase): Iterator và reference đến phần tử bị xóa bị mất hiệu lực. Tất cả các iterator và reference sau vị trí xóa cũng bị mất hiệu lực. end() cũng bị mất hiệu lực.
Khi push_back hoặc insert gây cấp phát lại bộ nhớ: Tất cả các iterator, reference và pointer trỏ vào các phần tử của vector đều bị mất hiệu lực.

Việc sử dụng một iterator đã bị mất hiệu lực sẽ dẫn đến undefined behavior – mã của bạn có thể crash, cho kết quả sai, hoặc có vẻ hoạt động đúng một cách ngẫu nhiên.

Cách xử lý phổ biến nhất, như đã thấy trong ví dụ xóa trong vòng lặp, là cập nhật iterator sau khi thực hiện thao tác có thể gây mất hiệu lực (như gán lại giá trị trả về của erase).

// Vi du don gian ve mat hieu luc
vector<int> numbers = {10, 20, 30, 40};
auto it = numbers.begin() + 1; // it tro den 20
cout << "Gia tri tai it: " << *it << endl; // OK

numbers.insert(numbers.begin(), 5); // Chen 5 vao dau

// Bây gio, 'it' tro den 20 TRUOC khi chen, vi tri cua 20 da thay doi
// su dung 'it' sau phep chen nay la KHONG AN TOAN
//cout << "Gia tri tai it sau khi chen: " << *it << endl; // <<< UNDEFINED BEHAVIOR!

// De an toan, can lay lai iterator sau khi chen/xoa neu can
// auto it_after_insert = numbers.begin() + 2; // 20 bay gio o chi muc 2
// cout << "Gia tri moi tai vi tri cu: " << *it_after_insert << endl; // OK

Việc hiểu rõ quy tắc mất hiệu lực của iterator là rất quan trọng khi thực hiện các thao tác thay đổi cấu trúc vector.

Tóm tắt

Trong bài viết này, chúng ta đã đi sâu vào cách sử dụng iterator với vector. Chúng ta đã học:

Iterator là gì và tại sao chúng là công cụ mạnh mẽ, đặc biệt trong STL.
Cách lấy iterator bắt đầu (begin()) và kết thúc (end()).
Cách duyệt vector bằng iterator sử dụng vòng lặp while và for.
Các phép toán cơ bản của iterator, đặc biệt là các phép toán của Random Access Iterator của vector.
Cách sử dụng reverse iterator (rbegin(), rend()) để duyệt ngược.
Cách sử dụng constant iterator (cbegin(), cend(), crbegin(), crend()) cho truy cập chỉ đọc.
Cách sửa đổi phần tử bằng cách dereference iterator.
Cách chèn (insert()) và xóa (erase()) phần tử sử dụng iterator.
Quy tắc quan trọng: Cách xử lý iterator bị mất hiệu lực sau khi chèn hoặc xóa, đặc biệt khi xóa trong vòng lặp.

Việc thành thạo iterator không chỉ giúp bạn làm việc hiệu quả hơn với vector trong các tình huống phức tạp mà còn là nền tảng vững chắc để bạn làm việc với các container khác của STL và sử dụng các thuật toán mạnh mẽ từ thư viện <algorithm>.

Hẹn gặp lại các bạn trong các bài tiếp theo!

Comments

There are no comments at the moment.