Iterators - Công cụ duyệt Container
📖 Giới thiệu
Iterators là đối tượng giống như con trỏ, cho phép duyệt qua các phần tử trong container. Chúng là cầu nối giữa containers và algorithms trong STL.
Ví dụ đơn giản đầu tiên
cpp
#include <iostream>
#include <vector>
#include <list>
using namespace std;
int main() {
vector<int> vec = {1, 2, 3, 4, 5};
// Iterator cơ bản
vector<int>::iterator it;
cout << "Vector: ";
for (it = vec.begin(); it != vec.end(); ++it) {
cout << *it << " ";
}
cout << endl;
// Range-based for (sử dụng iterator ngầm định)
cout << "Range-based: ";
for (int x : vec) {
cout << x << " ";
}
cout << endl;
return 0;
}🔧 Các loại Iterator
1. Input Iterator
cpp
// Chỉ đọc, di chuyển về phía trước
istream_iterator<int> input(cin);2. Output Iterator
cpp
// Chỉ ghi, di chuyển về phía trước
ostream_iterator<int> output(cout, " ");3. Forward Iterator
cpp
// Đọc/ghi, di chuyển về phía trước
forward_list<int>::iterator it;4. Bidirectional Iterator
cpp
// Đọc/ghi, di chuyển cả hai hướng
list<int>::iterator it;
set<int>::iterator it;5. Random Access Iterator
cpp
// Truy cập ngẫu nhiên, arithmetic operations
vector<int>::iterator it;
deque<int>::iterator it;💻 Ví dụ minh họa
Ví dụ 1: Iterator trong thực tế
cpp
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <iterator>
using namespace std;
class IteratorDemo {
public:
static void basic_iteration() {
cout << "=== BASIC ITERATION ===" << endl;
vector<string> cities = {"Hà Nội", "TP.HCM", "Đà Nẵng", "Hải Phòng", "Cần Thơ"};
cout << "1. Iterator thường:" << endl;
for (auto it = cities.begin(); it != cities.end(); ++it) {
cout << " " << *it << endl;
}
cout << "\n2. Const iterator:" << endl;
for (auto it = cities.cbegin(); it != cities.cend(); ++it) {
cout << " " << *it << " (read-only)" << endl;
}
cout << "\n3. Reverse iterator:" << endl;
for (auto it = cities.rbegin(); it != cities.rend(); ++it) {
cout << " " << *it << endl;
}
cout << "\n4. Range-based for:" << endl;
for (const auto& city : cities) {
cout << " " << city << endl;
}
}
static void iterator_arithmetic() {
cout << "\n=== ITERATOR ARITHMETIC ===" << endl;
vector<int> numbers = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
auto it = numbers.begin();
cout << "Đầu tiên: " << *it << endl;
// Di chuyển iterator
advance(it, 3); // Di chuyển 3 vị trí
cout << "Sau khi advance(3): " << *it << endl;
auto it2 = it + 2; // Random access iterator
cout << "it + 2: " << *it2 << endl;
auto it3 = prev(it2, 1); // Lùi 1 vị trí
cout << "prev(it2, 1): " << *it3 << endl;
auto it4 = next(it, 2); // Tiến 2 vị trí
cout << "next(it, 2): " << *it4 << endl;
// Khoảng cách giữa iterators
auto distance_val = distance(numbers.begin(), it);
cout << "Khoảng cách từ begin đến it: " << distance_val << endl;
}
static void iterator_with_algorithms() {
cout << "\n=== ITERATOR WITH ALGORITHMS ===" << endl;
vector<int> data = {5, 2, 8, 1, 9, 3, 7, 4, 6};
cout << "Dữ liệu gốc: ";
copy(data.begin(), data.end(), ostream_iterator<int>(cout, " "));
cout << endl;
// Tìm kiếm với iterator
auto found = find(data.begin(), data.end(), 8);
if (found != data.end()) {
cout << "Tìm thấy 8 tại vị trí: " << distance(data.begin(), found) << endl;
}
// Sắp xếp một phần
sort(data.begin(), data.begin() + 5);
cout << "Sau khi sort 5 phần tử đầu: ";
copy(data.begin(), data.end(), ostream_iterator<int>(cout, " "));
cout << endl;
// Xóa phần tử với iterator
auto to_remove = remove_if(data.begin(), data.end(),
[](int x) { return x > 7; });
data.erase(to_remove, data.end());
cout << "Sau khi xóa phần tử > 7: ";
copy(data.begin(), data.end(), ostream_iterator<int>(cout, " "));
cout << endl;
}
static void custom_iterator_operations() {
cout << "\n=== CUSTOM ITERATOR OPERATIONS ===" << endl;
list<string> words = {"apple", "banana", "cherry", "date", "elderberry"};
// Tìm phần tử và xóa
auto it = find(words.begin(), words.end(), "cherry");
if (it != words.end()) {
cout << "Xóa: " << *it << endl;
words.erase(it);
}
// Chèn vào vị trí cụ thể
auto insert_pos = find(words.begin(), words.end(), "date");
if (insert_pos != words.end()) {
words.insert(insert_pos, "coconut");
}
cout << "Sau khi thao tác: ";
for (const auto& word : words) {
cout << word << " ";
}
cout << endl;
// Chia list thành 2 phần
auto middle = words.begin();
advance(middle, words.size() / 2);
list<string> first_half(words.begin(), middle);
list<string> second_half(middle, words.end());
cout << "Nửa đầu: ";
for (const auto& word : first_half) {
cout << word << " ";
}
cout << endl;
cout << "Nửa sau: ";
for (const auto& word : second_half) {
cout << word << " ";
}
cout << endl;
}
static void iterator_categories_demo() {
cout << "\n=== ITERATOR CATEGORIES DEMO ===" << endl;
// Input Iterator với istream
cout << "Nhập 3 số (cách nhau bởi space): ";
istream_iterator<int> input_it(cin);
istream_iterator<int> end_of_input;
vector<int> input_numbers;
for (int i = 0; i < 3 && input_it != end_of_input; ++i, ++input_it) {
input_numbers.push_back(*input_it);
}
// Output Iterator với ostream
cout << "Số bạn đã nhập: ";
copy(input_numbers.begin(), input_numbers.end(),
ostream_iterator<int>(cout, " "));
cout << endl;
// Back insert iterator
vector<int> target;
copy(input_numbers.begin(), input_numbers.end(),
back_inserter(target));
cout << "Sao chép bằng back_inserter: ";
for (int x : target) {
cout << x << " ";
}
cout << endl;
}
static void iterator_invalidation_demo() {
cout << "\n=== ITERATOR INVALIDATION DEMO ===" << endl;
vector<int> vec = {1, 2, 3, 4, 5};
cout << "Vector ban đầu: ";
for (int x : vec) cout << x << " ";
cout << endl;
auto it = vec.begin() + 2; // Trỏ đến phần tử thứ 3 (giá trị 3)
cout << "Iterator trỏ đến: " << *it << endl;
// Thêm phần tử có thể invalidate iterator
vec.push_back(6); // Có thể gây reallocation
// KHÔNG an toàn - iterator có thể đã bị invalidated
// cout << "Sau push_back: " << *it << endl; // Nguy hiểm!
// An toàn - tạo iterator mới
auto safe_it = vec.begin() + 2;
cout << "Iterator mới trỏ đến: " << *safe_it << endl;
cout << "Vector sau push_back: ";
for (int x : vec) cout << x << " ";
cout << endl;
// Với list, iterator ít bị invalidated hơn
list<int> lst = {1, 2, 3, 4, 5};
auto list_it = lst.begin();
advance(list_it, 2);
cout << "List iterator trỏ đến: " << *list_it << endl;
lst.push_back(6); // Không invalidate iterator
lst.push_front(0); // Không invalidate iterator
cout << "Sau khi thêm vào list, iterator vẫn trỏ đến: " << *list_it << endl;
}
};
int main() {
cout << "=== STL ITERATORS COMPREHENSIVE DEMO ===" << endl;
IteratorDemo::basic_iteration();
IteratorDemo::iterator_arithmetic();
IteratorDemo::iterator_with_algorithms();
IteratorDemo::custom_iterator_operations();
// Uncomment để test input iterator
// IteratorDemo::iterator_categories_demo();
IteratorDemo::iterator_invalidation_demo();
return 0;
}🏋️ Thực hành
Bài tập 1: Custom Iterator
Tạo iterator cho custom container class
Bài tập 2: Iterator Adapter
Implement filtering iterator chỉ trả về phần tử thỏa điều kiện
Bài tập 3: Safe Iterator
Tạo iterator với bounds checking
📋 Tóm tắt
- Iterators: Abstraction for container traversal
- Categories: Input, Output, Forward, Bidirectional, Random Access
- Operations: ++, --, *, ->, ==, !=
- Benefits: Generic algorithms, consistent interface
- Caution: Iterator invalidation
Bài tiếp theo: File I/O - Chuyển sang advanced topics.