Iterators: The STL Glue

Understand iterator categories, from input iterators to contiguous iterators. Learn iterator arithmetic, the begin/end convention, and how iterators connect containers to algorithms.

The Iterator Abstraction

Iterators are the glue between STL containers and algorithms. Instead of writing N algorithms for M containers (N*M implementations), the STL defines a common iterator interface. Each container provides iterators, and each algorithm operates on iterator ranges — giving N+M implementations that work together.

An iterator is an object that:
1. Points to an element in a sequence
2. Can be dereferenced (*it) to access the element
3. Can be incremented (++it) to move to the next element
4. Can be compared (it != end) to detect the end of the sequence

Different iterator categories support different sets of operations, forming a hierarchy from weakest to strongest.

Iterator Categories

The C++ iterator categories form a hierarchy (each level includes the capabilities of all levels below):

| Category | Operations | Example Containers |
|---|---|---|
| Input | Read, single-pass forward (++,*,==) |istream_iterator|
| Output | Write, single-pass forward (++,*=) |ostream_iterator,back_inserter|
| Forward | Read/write, multi-pass forward |forward_list,unordered_set|
| Bidirectional | Forward + backward (--) |list,set,map|
| Random Access | Bidirectional + jumps (+n,-n,[],<) |deque|
| Contiguous (C++17) | Random Access + elements are adjacent in memory |vector,array,string|

Algorithms declare the minimum category they require.std::sortneeds random access iterators, so it works withvectorbut notlist(which provides its ownsort()member function).

The begin/end Convention

Every STL container providesbegin()andend()— a half-open range[begin, end)whereendpoints one past the last element. Free functionsstd::begin()andstd::end()work with containers, C-arrays, and any type that provides member.begin()and.end().

begin_end.cpp

#include <vector>
#include <list>
#include <algorithm>
#include <iostream>
#include <iterator>

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

    // Member functions
    auto first = vec.begin();   // points to 5
    auto last  = vec.end();     // points past 2

    // Free functions — preferred for generic code
    auto first2 = std::begin(vec);
    auto last2  = std::end(vec);

    // Works with C-arrays too
    int arr[] = {10, 20, 30};
    std::sort(std::begin(arr), std::end(arr));

    // const iterators — read-only access
    auto cit = vec.cbegin();     // const_iterator
    // *cit = 99;                // ERROR: cannot modify through const_iterator

    // Reverse iterators — iterate backward
    for (auto rit = vec.rbegin(); rit != vec.rend(); ++rit) {
        std::cout << *rit << ' ';  // 2, 4, 1, 3, 5 (reversed, pre-sort was applied)
    }
    std::cout << '\n';
}

Iterator Utilities: next, prev, advance, distance

Theheader provides utility functions that work across all iterator categories, choosing the most efficient implementation automatically.

iterator_utils.cpp

#include <iterator>
#include <vector>
#include <list>
#include <iostream>

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

    // std::next — returns iterator n positions forward (default 1)
    auto it = std::next(vec.begin(), 2);   // points to 30
    std::cout << *it << '\n';              // 30

    // std::prev — returns iterator n positions backward
    auto it2 = std::prev(vec.end());       // points to 50
    std::cout << *it2 << '\n';             // 50

    // std::advance — modifies iterator in place (no return)
    auto it3 = vec.begin();
    std::advance(it3, 3);                  // now points to 40
    std::cout << *it3 << '\n';             // 40

    // std::distance — number of increments from first to last
    auto d = std::distance(vec.begin(), vec.end());  // 5
    std::cout << "Distance: " << d << '\n';

    // These work with non-random-access iterators too
    std::list<int> lst = {1, 2, 3, 4, 5};
    auto lit = std::next(lst.begin(), 2);  // O(n) for list, O(1) for vector
    std::cout << *lit << '\n';             // 3

    auto ld = std::distance(lst.begin(), lst.end());  // O(n) for list
    std::cout << "List distance: " << ld << '\n';     // 5
}

Insert Iterators and Stream Iterators

Insert iterators allow algorithms to insert into containers rather than overwriting existing elements. Stream iterators adapt I/O streams to the iterator interface.

insert_stream_iterators.cpp

#include <iterator>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>

int main() {
    std::vector<int> src = {1, 2, 3, 4, 5};
    std::vector<int> dst;

    // back_inserter — calls push_back on each assignment
    std::copy(src.begin(), src.end(), std::back_inserter(dst));
    // dst: {1, 2, 3, 4, 5}

    // front_inserter — calls push_front (works with deque, list)
    // inserter — calls insert at a given position

    // ostream_iterator — write to an output stream
    std::copy(dst.begin(), dst.end(),
              std::ostream_iterator<int>(std::cout, ", "));
    std::cout << '\n';  // 1, 2, 3, 4, 5,

    // istream_iterator — read from an input stream
    std::istringstream iss("10 20 30 40");
    std::vector<int> from_stream(
        std::istream_iterator<int>(iss),
        std::istream_iterator<int>()   // end-of-stream sentinel
    );
    // from_stream: {10, 20, 30, 40}
}

Lỗi thường gặp

Incrementing an iterator pastend()or decrementing pastbegin()is undefined behavior. The same applies to dereferencingend()— it is a sentinel, not a valid element.

A common mistake is writingit + 1without checking whetheritis already at or near the end:

auto it = vec.end();
++it;    // UB — past-the-end
*it;     // UB — dereferencing end()

Always check iterator validity before operations. Use std::next and std::prev with distance checks, or use range-based for loops that handle bounds automatically.

Thực hành tốt

Khi viết các hàm tổng quát hoạt động theo trình tự:

1. Chấp nhận cặp lặp (hoặc phạm vi trong C++20) thay vì các vùng chứa cụ thể
2. Sử dụngtypenamehoặcautocho loại vòng lặp
3. Sử dụngstd::distancethay vì phép trừ (yêu cầu truy cập ngẫu nhiên)
4. Sử dụngstd::next/std::prevthay vì số học+/-
5. Trong C++20, ưu tiên khái niệm để hạn chế các yêu cầu của trình vòng lặp:

template<std::forward_iterator Iter>
auto my_algorithm(Iter first, Iter last) { ... }

Điều này đảm bảo mã của bạn hoạt động với phạm vi vùng chứa rộng nhất.

Điểm chính

Trình vòng lặp tách các vùng chứa khỏi thuật toán - nguyên tắc thiết kế cốt lõi của STL
Có sáu loại vòng lặp: đầu vào, đầu ra, chuyển tiếp, hai chiều, truy cập ngẫu nhiên, liền kề
Sử dụng các hàm miễn phístd::begin()/std::end()cho mã chung hoạt động với vùng chứa và mảng C
std::next,std::prev,std::advance,std::distancework across all iterator categories
Chèn các trình vòng lặp (back_inserter,front_inserter,inserter) để thuật toán phát triển các vùng chứa
Không bao giờ hủy đăng kýend()hoặc tăng dần nó - cả hai đều là hành vi không xác định

Câu đố — Kiểm tra kiến thức

(15 XP)

1. `std::sort`yêu cầu danh mục trình vòng lặp nào?

2. `std::back_inserter(vec)`tạo ra cái gì?

3. Độ phức tạp về thời gian của`std::distance(first, last)`trên`std::list`là bao nhiêu?

Bộ điều hợp container & Container đặc biệt

Tiếp

STL Algorithms: The Power of <algorithm>