C++ STL Fundamentals

🧭 Iterator và range-based for

Iterator là “con trỏ tổng quát” giúp duyệt các container STL theo cùng một cách. Range-based for cung cấp cú pháp ngắn gọn hơn, nhưng bản sao, tham chiếu và tham chiếu hằng tạo ra hành vi khác nhau.

begin / endPhạm vi nửa mở

*itĐọc phần tử hiện tại

++itDi chuyển iterator

auto&Sửa phần tử gốc

Mục tiêu Đặt vấn đề Iterator Mô phỏng Phân loại Range-for Copy/Reference Container Invalidation Phân tích Code mẫu Giải thích code Lỗi thường gặp Quiz

🎯 Mục tiêu bài học

Cần hiểu

Iterator là gì và vì sao STL dùng iterator.
Ý nghĩa của begin(), end(), *it, ++it.
Phân biệt iterator và chỉ số.
Khác nhau giữa auto x, auto& x, const auto& x.
Khái niệm iterator invalidation.

Cần làm được

Duyệt vector, set và map bằng iterator.
Duyệt bằng range-based for.
Sửa phần tử qua tham chiếu.
Dùng find, sort, reverse với phạm vi iterator.
Xóa phần tử an toàn khi đang duyệt.

1. Đặt vấn đề

Bài toán mở đầu.
Ta có nhiều container STL như vector, list, set, map. Cần viết thuật toán duyệt và tìm kiếm mà không phụ thuộc vào cách container lưu dữ liệu bên trong.

1.1. Vì sao chỉ số chưa đủ?

Vector có a[i], nhưng set và map không hỗ trợ truy cập bằng chỉ số. Nếu mỗi container dùng một cách duyệt riêng, các thuật toán STL không thể dùng chung.

1.2. Ý tưởng “vị trí đang đứng”

begin(): phần tử đầu tiên.
end(): vị trí ngay sau phần tử cuối.
*it: phần tử hiện tại.
++it: phần tử kế tiếp.

Duyệt phạm vi nửa mở [begin, end)

Kết luận: Iterator tạo ra giao diện duyệt chung cho container và thuật toán STL.

2. Iterator cơ bản

Khai báo đầy đủ

vector<int>::iterator it = a.begin();

while (it != a.end()) {
    cout << *it << ' ';
    ++it;
}

Dùng auto

for (auto it = a.begin();
     it != a.end();
     ++it) {
    cout << *it << ' ';
}

Biểu thức	Ý nghĩa	Lưu ý
`a.begin()`	Iterator tới phần tử đầu.	Container rỗng: begin == end.
`a.end()`	Ngay sau phần tử cuối.	Không được dereference.
`*it`	Lấy phần tử hiện tại.	Chỉ hợp lệ khi it != end.
`++it`	Đi tới phần tử kế tiếp.	Ưu tiên tiền tố.
`it->first`	Truy cập trường của pair/object.	Tương đương `(*it).first`.

3. Mô phỏng iterator trên vector

Vector

auto it = a.begin();
while (it != a.end()) {
    cout << *it;
    ++it;
}

4. Các nhóm iterator

Nhóm	Di chuyển	Container tiêu biểu	Thao tác
Forward	Tiến một chiều	`forward_list`, `unordered_set`	`++it`
Bidirectional	Tiến và lùi	`list`, `set`, `map`	`++it`, `--it`
Random Access	Nhảy tùy ý	`vector`, `deque`, `array`	`it+n`, `it2-it1`

Không phải iterator nào cũng cộng được số. it+3 dùng được với vector nhưng không dùng được với set/list.

5. Range-based for

for (khai_báo_phần_tử : container) { ... }

Bản sao

for (auto x : a) {
    x *= 2;
}

Không sửa vector.

Tham chiếu

for (auto& x : a) {
    x *= 2;
}

Sửa trực tiếp vector.

Tham chiếu hằng

for (const auto& x : a) {
    cout << x;
}

Không sao chép, không sửa.

Quy tắc: Chỉ đọc object lớn → const auto&; cần sửa → auto&; cần bản sao → auto.

6. Mô phỏng copy, reference và const reference

VectorChế độ

7. Duyệt các container

vector

for (auto it = a.begin();
     it != a.end(); ++it) {
    cout << *it;
}

set

for (const auto& x : s) {
    cout << x;
}

Không sửa phần tử set.

map

for (const auto& [key, value] : mp) {
    cout << key << value;
}

Map: key không được sửa; value có thể sửa nếu dùng iterator/tham chiếu không const.

8. Iterator invalidation

Một số thao tác thay đổi cấu trúc container khiến iterator cũ không còn hợp lệ.

Vector mẫu

Thao tác	Iterator bị ảnh hưởng
`vector::push_back` có tái cấp phát	Tất cả iterator/reference cũ.
`vector::erase(pos)`	Từ pos trở về sau.
`list/set/map::erase(pos)`	Chỉ iterator tới phần tử bị xóa.

Không dereference iterator đã bị vô hiệu hóa. Đây là hành vi không xác định.

9. Phân tích và lựa chọn

Nhu cầu	Cách dùng	Lý do
Chỉ đọc số nhỏ	`for (int x : a)`	Sao chép rẻ.
Chỉ đọc object lớn	`for (const auto& x : a)`	Không sao chép.
Cần sửa	`for (auto& x : a)`	x là bí danh phần tử.
Cần vị trí	Iterator hoặc chỉ số	Range-for không cho chỉ số trực tiếp.
Cần xóa khi duyệt	`it = c.erase(it)`	Nhận iterator kế tiếp hợp lệ.

10. Code mẫu

#include <bits/stdc++.h>
using namespace std;

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

    for (auto it = a.begin();
         it != a.end(); ++it) {
        cout << *it << ' ';
    }

    auto it = find(a.begin(), a.end(), 30);
    if (it != a.end()) {
        cout << "\nVi tri: " << it - a.begin();
    }
}

vector<int> a = {1, 2, 3, 4};

for (auto x : a) {
    x *= 10;          // Không sửa a
}

for (auto& x : a) {
    x *= 10;          // Sửa trực tiếp a
}

for (const auto& x : a) {
    cout << x << ' ';
}

map<string,int> frequency = {
    {"apple", 2}, {"banana", 3}
};

for (auto& [word, count] : frequency) {
    count++;
}

for (const auto& [word, count] : frequency) {
    cout << word << ' ' << count << '\n';
}

vector<int> a = {1, 2, 3, 4, 5, 6};

for (auto it = a.begin(); it != a.end(); ) {
    if (*it % 2 == 0) {
        it = a.erase(it);
    } else {
        ++it;
    }
}

vector<int> a = {5, 2, 9, 2, 7};

sort(a.begin(), a.end());
reverse(a.begin(), a.end());
auto it = find(a.begin(), a.end(), 2);
int cnt = count(a.begin(), a.end(), 2);
long long sum = accumulate(a.begin(), a.end(), 0LL);

11. Giải thích code

11.1. Vì sao dùng it != end()?

end() nằm sau phần tử cuối; khi đạt end thì không được dùng *it.

11.2. Vì sao ưu tiên ++it?

Hậu tố có thể cần tạo bản sao iterator cũ; tiền tố không cần.

11.3. Vì sao auto x không sửa phần tử gốc?

x là bản sao cục bộ.

11.4. auto& và const auto&

auto& sửa được; const auto& không sao chép và không sửa.

11.5. Vì sao erase trả về iterator?

Iterator cũ có thể mất hiệu lực; giá trị trả về là iterator kế tiếp hợp lệ.

11.6. Vì sao không sửa phần tử set?

Thứ tự cây phụ thuộc vào key; sửa trực tiếp có thể phá cấu trúc.

12. Lỗi thường gặp

Dereference end().
Dùng iterator sau khi bị invalidation.
Dùng auto x rồi tưởng sửa được phần tử gốc.
Xóa rồi vẫn ++it không đúng cách.
Dùng it+n với set/list.
Tính vị trí bằng it-a.begin() cho container không random access.
Thay đổi kích thước container trong range-for mà không hiểu invalidation.
Sửa key của map hoặc phần tử set.

13. Quiz và bài tập

Câu 1. end() trỏ tới đâu?

Câu 2. Muốn sửa trực tiếp phần tử trong range-for?

Câu 3. Xóa an toàn khi đang duyệt?

Cơ bản

Duyệt vector bằng iterator.
In set theo thứ tự.
Duyệt map bằng structured binding.

Trung bình

Nhân đôi phần tử bằng auto&.
Xóa số chẵn khi duyệt.
Tìm vị trí bằng iterator.