PENALGO

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_iterator

Reverse 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-first

Iterator 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 iterators

Invalidation Rules ​

Containerinsert()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 erasedN/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 ​

ConceptKey Takeaway
IteratorGeneralized pointer to elements
begin(), end()First element, past-the-end
cbegin(), cend()Const iterators
rbegin(), rend()Reverse iterators
InvalidationWatch out for modifications!
autoAlways use for iterator types
Range-based forSyntactic sugar over iterators

➡️ Tiếp theo ​

Tiếp theo: Modern Arrays — Stop using C-arrays!

🧠 Quiz

Câu 1: v.end() trỏ tới đâu trong vector v = {10, 20, 30}? ​

  • [ ] A) Phần tử cuối cùng (30)
  • [x] B) Vị trí sau phần tử cuối cùng (past-the-end)
  • [ ] C) Phần tử đầu tiên (10)
  • [ ] D) nullptr

💡 Giải thích: end() trả về iterator trỏ tới vị trí one-past-the-end — không phải phần tử cuối. Đây là convention của STL để tạo half-open range [begin, end). Dereference *v.end() là Undefined Behavior. Muốn truy cập phần tử cuối, dùng v.back() hoặc *(v.end() - 1).

Câu 2: std::vector::iterator thuộc loại iterator nào? ​

  • [ ] A) Forward Iterator
  • [ ] B) Bidirectional Iterator
  • [x] C) Random Access Iterator
  • [ ] D) Input Iterator

💡 Giải thích: Vector iterator là Random Access Iterator — loại mạnh nhất. Nó hỗ trợ ++, -- (bidirectional), và cả +n, -n, [] (random jump). Điều này cho phép std::sort hoạt động trên vector (sort yêu cầu random access). std::list::iterator chỉ là Bidirectional, nên không dùng được std::sort.

Câu 3: Điều gì xảy ra với đoạn code này? ​

cpp
std::vector<int> v = {1, 2, 3};
auto it = v.begin();
v.push_back(4);
std::cout << *it;
  • [ ] A) In ra 1 bình thường
  • [ ] B) In ra 4
  • [x] C) Undefined Behavior vì iterator bị invalidated
  • [ ] D) Compilation error

💡 Giải thích: push_back có thể trigger reallocation khi size vượt capacity. Khi reallocation xảy ra, tất cả iterators, pointers và references tới vector đều bị invalidated. Sử dụng iterator đã invalid là Undefined Behavior. Luôn lấy iterator mới sau khi modify vector.

Professional Engineering Standards | © 2025 HPN Corporation