Giao diện
🔄 Iterators — Duyệt Containers
Iterators là abstraction cho việc duyệt containers — traversing without knowing internal structure.
Iterator là gì?
Iterator là "con trỏ tổng quát" — nó trỏ đến element trong container và cho phép di chuyển qua các elements.
cpp
#include <vector>
#include <iostream>
int main() {
std::vector<int> v = {10, 20, 30, 40, 50};
// Iterator pointing to first element
std::vector<int>::iterator it = v.begin();
// Dereference như pointer
std::cout << *it << std::endl; // 10
// Move to next
++it;
std::cout << *it << std::endl; // 20
// Move to previous
--it;
std::cout << *it << std::endl; // 10
return 0;
}begin() và end()
┌─────────────────────────────────────────────────────────────────┐
│ begin() và end() │
├─────────────────────────────────────────────────────────────────┤
│ │
│ vector: [10] [20] [30] [40] [50] │
│ ▲ ▲ │
│ │ │ │
│ begin() end() │
│ (first element) (ONE PAST last element) │
│ │
│ ⚠️ end() KHÔNG trỏ vào phần tử cuối! │
│ Nó trỏ vào "past-the-end" position │
│ │
└─────────────────────────────────────────────────────────────────┘cpp
std::vector<int> v = {10, 20, 30};
// Classic iteration
for (auto it = v.begin(); it != v.end(); ++it) {
std::cout << *it << " ";
}
// Output: 10 20 30
// ⚠️ Đừng dereference end()!
// auto x = *v.end(); // ❌ Undefined behavior!Iterator Types
1. Input Iterator
- Read-only, single-pass (chỉ đọc 1 lần)
std::istream_iterator
2. Output Iterator
- Write-only, single-pass
std::ostream_iterator
3. Forward Iterator
- Read/write, multi-pass
std::forward_list::iterator
4. Bidirectional Iterator
- Forward + backward (
++,--) std::list::iterator,std::map::iterator
5. Random Access Iterator
- Bidirectional + jump to any position (
+,-,[]) std::vector::iterator,std::deque::iterator
┌─────────────────────────────────────────────────────────────────┐
│ ITERATOR HIERARCHY │
├─────────────────────────────────────────────────────────────────┤
│ │
│ Random Access ◄── most powerful │
│ ▲ │
│ │ │
│ Bidirectional ◄── can go backward │
│ ▲ │
│ │ │
│ Forward ◄── multi-pass │
│ ▲ │
│ │ │
│ Input / Output ◄── single-pass │
│ │
└─────────────────────────────────────────────────────────────────┘auto với Iterators
cpp
std::vector<int> v = {1, 2, 3};
std::map<std::string, int> m = {{"a", 1}, {"b", 2}};
// Verbose
std::vector<int>::iterator it1 = v.begin();
std::map<std::string, int>::iterator it2 = m.begin();
// ✅ Dùng auto (recommended)
auto it3 = v.begin();
auto it4 = m.begin();
// const_iterator (read-only)
auto cit = v.cbegin(); // const_iterator
// *cit = 10; // ❌ Error: cannot modify through const_iteratorReverse Iterators
cpp
std::vector<int> v = {1, 2, 3, 4, 5};
// Backward iteration
for (auto it = v.rbegin(); it != v.rend(); ++it) {
std::cout << *it << " ";
}
// Output: 5 4 3 2 1
// rbegin() points to last element
// rend() points to one-before-firstIterator Invalidation
⚠️ CRITICAL
Một số operations invalidate existing iterators!
vector
cpp
std::vector<int> v = {1, 2, 3};
auto it = v.begin();
v.push_back(4); // ⚠️ May invalidate all iterators (reallocation)
v.insert(v.end(), 5); // ⚠️ Same
// Sau push_back, 'it' có thể invalid!
// *it = 10; // ❌ Undefined behavior if reallocated!map/set
cpp
std::map<int, std::string> m = {{1, "a"}, {2, "b"}, {3, "c"}};
auto it = m.find(2);
m.erase(1); // ✅ Other iterators still valid
m.erase(2); // ❌ 'it' now invalid (erased element)
m.insert({4, "d"}); // ✅ Doesn't invalidate existing iteratorsInvalidation Rules
| Container | insert() | erase() | push_back() |
|---|---|---|---|
vector | ⚠️ All after point + reallocation | ⚠️ All after point | ⚠️ All if reallocated |
deque | ⚠️ All | ⚠️ All | ⚠️ All except front/back |
list | ✅ None | ⚠️ Only erased | ✅ None |
map/set | ✅ None | ⚠️ Only erased | N/A |
Algorithms với Iterators
Iterators là "glue" giữa containers và algorithms:
cpp
#include <vector>
#include <algorithm>
#include <numeric>
#include <iostream>
int main() {
std::vector<int> v = {5, 2, 8, 1, 9, 3};
// Sort
std::sort(v.begin(), v.end());
// Find
auto it = std::find(v.begin(), v.end(), 8);
if (it != v.end()) {
std::cout << "Found at index: " << (it - v.begin()) << std::endl;
}
// Accumulate
int sum = std::accumulate(v.begin(), v.end(), 0);
// Transform
std::transform(v.begin(), v.end(), v.begin(),
[](int x) { return x * 2; });
// Copy
std::vector<int> v2(v.size());
std::copy(v.begin(), v.end(), v2.begin());
// Fill
std::fill(v.begin(), v.end(), 0);
return 0;
}Range-based for Under the Hood
cpp
std::vector<int> v = {1, 2, 3};
// Range-based for
for (auto& x : v) {
// use x
}
// ≈ Compiler translates to:
for (auto it = v.begin(); it != v.end(); ++it) {
auto& x = *it;
// use x
}Custom Iterator (Advanced)
cpp
#include <iterator>
class Range {
int start_, end_;
public:
Range(int start, int end) : start_(start), end_(end) {}
// Nested iterator class
class Iterator {
int current_;
public:
using iterator_category = std::input_iterator_tag;
using value_type = int;
using difference_type = int;
using pointer = int*;
using reference = int&;
Iterator(int val) : current_(val) {}
int operator*() const { return current_; }
Iterator& operator++() { ++current_; return *this; }
bool operator!=(const Iterator& other) const {
return current_ != other.current_;
}
};
Iterator begin() { return Iterator(start_); }
Iterator end() { return Iterator(end_); }
};
int main() {
for (int x : Range(1, 5)) {
std::cout << x << " "; // 1 2 3 4
}
return 0;
}📚 Tổng kết
| Concept | Key Takeaway |
|---|---|
| Iterator | Generalized pointer to elements |
begin(), end() | First element, past-the-end |
cbegin(), cend() | Const iterators |
rbegin(), rend() | Reverse iterators |
| Invalidation | Watch out for modifications! |
auto | Always use for iterator types |
| Range-based for | Syntactic sugar over iterators |
➡️ Tiếp theo
Tiếp theo: Modern Arrays — Stop using C-arrays!