Chapter 6: Iterator System
核心问题与阅读主线
STL 的 iterator system 将容器存储解耦为算法可统一驱动的位置接口。面对连续数组、链式节点、裸指针与流适配器,它依靠能力分层、iterator_traits 编译期分发与容器失效契约,在保持通用接口的同时选出正确的底层访问路径。
全章共用代码样本(下文各节持续拆解)
本章贯穿同一组基础操作:在 std::vector<int> 上做区间统计、插入复制与反向访问,并对照 std::list<int>、裸指针与输出适配器上的差异,拆解区间边界、能力分层、编译期分发与失效规则。
#include <algorithm>
#include <iterator>
#include <list>
#include <vector>
int main() {
std::vector<int> numbers{1, 2, 3, 4};
std::vector<int> copied;
auto first = numbers.begin();
auto last = numbers.end();
auto even_count = std::count_if(first, last, [](int value) {
return value % 2 == 0;
});
std::copy(first, last, std::back_inserter(copied));
auto rfirst = std::make_reverse_iterator(last);
auto rlast = std::make_reverse_iterator(first);
auto first_from_back = *rfirst;
(void)even_count;
(void)first_from_back;
}
样本覆盖顺序读取(std::count_if)、插入适配(std::back_inserter)与反向适配(std::make_reverse_iterator)。分析主线只有三条:算法可见哪些表达式、容器保证哪些位置有效、traits 与 adapter 如何衔接。
6.1 iterator 作为 range cursor
iterator 是表示序列位置的值对象,算法仅通过复制、比较、递增与解引用访问元素:
std::vector<int>::iterator:近似裸指针,保存连续元素地址。std::list<int>::iterator:保存节点指针,沿链表移动。std::istream_iterator<int>:封装输入流当前读取状态。
STL 算法通常接收半开区间 [first, last):空区间写作 [first, first),尾后位置 last 仅用于终止比较,不可解引用。
template <class Iterator, class Predicate>
int count_matches(Iterator first, Iterator last, Predicate pred) {
int count = 0;
for (; first != last; ++first) {
if (pred(*first)) {
++count;
}
}
return count;
}
count_matches 暴露了“有效区间”的运行时前提:first != last 可比、++first 与 *first 合法,且 first 经有限次递增可达 last。跨容器混用或不可达边界无法在算法内纠错。
| cursor 状态 | 关联有效序列 | 常见合法操作 | 工程边界 |
|---|---|---|---|
| 可解引用位置 | 是(指向真实元素) | *it、++it、比较 | 仅能与同一容器的位置比较 |
尾后位置(end()) | 是(末尾边界哨兵) | 比较、--it(若双向) | 禁止解引用 *it |
| singular / 失效位置 | 否(默认构造未赋值或已失效) | 仅可重新赋值或销毁 | 视同失效,禁止读写或比较 |
算法不拥有容器,也不感知内部是连续内存、链表节点还是流缓冲;只要 numbers 未触发失效,贯穿样本的 [first, last) 即保持有效。换成 std::list<int> 时循环写法不变,内部状态从连续地址转为节点指针。
核心判断
阅读算法源码时,直接按循环体内的表达式反推最低能力要求:
- 仅出现
++it、it != last、*it:只需输入遍历能力(单趟即可); - 出现
--it:至少需要双向能力(bidirectional); - 出现
it + n、last - first、it[n]:进入随机访问路径(random access)。
6.2 pointer、iterator category 与能力分层
普通指针是 iterator system 的参照原型:int* 原生支持解引用、递增、比较、做差与下标访问,因此能与 std::vector<int>::iterator 共用同一套泛型算法,并把这套位置表达式推广到链表、流与适配器。
iterator category 描述操作能力与语义承诺:旧式 STL 用 tag 类型表达,C++20 起可用 iterator concepts 在签名处直接约束;现代源码中旧算法查 iterator_category,ranges 算法查 concept。
| 能力层级 | 典型对象 | 核心操作与语义 | 工程含义 |
|---|---|---|---|
| output iterator | std::back_insert_iterator<std::vector<int>> | 写入、递增 | 适合作为算法输出端,读取旧值无意义 |
| input iterator | std::istream_iterator<int> | 只读、递增、单趟遍历 | 消费输入流或一次性序列 |
| forward iterator | std::forward_list<int>::iterator | 读取、递增、多趟遍历 | 可保存位置并重复扫描同一区间 |
| bidirectional iterator | std::list<int>::iterator | forward 能力 + --it | 支持反向遍历与双向链表移动 |
| random access iterator | std::deque<int>::iterator | bidirectional 能力 + + n、- n、it[n] | 支持常数时间距离计算与按偏移跳转 |
| contiguous iterator | std::vector<int>::iterator、int* | random access 能力 + 物理地址连续 | 支持按连续缓冲地址对接底层接口 |
能力层级直接决定算法归属:std::sort 需要随机访问跳转,std::list<int> 仅具备双向能力,因而只能通过成员函数 list::sort() 重连节点排序。
贯穿样本中的 numbers.begin() 来自 std::vector<int>,满足随机访问与连续存储承诺:
std::vector<int> numbers{1, 2, 3, 4};
auto it = numbers.begin();
int third = it[2];
auto distance = numbers.end() - numbers.begin();
换作 std::list<int> 时节点分散在内存中,it[2] 与 end() - begin() 均不可用;链表 iterator 只能沿 next / prev 指针逐跳前进。
关键事实
random access 不等于 contiguous:std::deque<int> 支持 it[n] 与 end() - begin(),但分段缓冲区跨块需经控制结构定位,不保证相邻元素物理地址连续;仅 std::vector<int>、std::array<int, N> 与 C 数组指针提供连续地址承诺。
输出 iterator 方向相反,std::back_inserter(copied) 的职责是承接赋值:
std::vector<int> copied;
auto out = std::back_inserter(copied);
*out = 42;
++out;
*out = 43;
out 的 operator* 返回自身,operator= 转调 copied.push_back,并未指向既有元素。读源码见输出 iterator 时,优先核对赋值触发的底层写入动作。
核心判断
判定 iterator 能力层级,按四问递进:
- 只能单向读、只能写,还是可读写?
- 递增后旧副本是否仍有效(单趟
inputvs 多趟forward)? - 是否支持
--it回退(bidirectional)与+ n常数时间跳转(random access)? - 相邻元素是否保证物理地址连续(
contiguous)?
6.3 iterator_traits 与 tag dispatch
泛型算法通过 std::iterator_traits<Iterator> 统一查询 value_type、difference_type、reference、pointer 与 iterator_category:
- 类类型 iterator:traits 默认读取其内部嵌套别名。
- 裸指针(如
int*):标准库提供指针偏特化,使其直接接入同一套算法路径。
下面代码演示 std::iterator_traits<int*> 如何让普通指针接入类型查询:
#include <iterator>
#include <type_traits>
template <class Iterator>
using iter_value_type = typename std::iterator_traits<Iterator>::value_type;
template <class Iterator>
iter_value_type<Iterator> read_first(Iterator first) {
return *first;
}
static_assert(std::is_same_v<iter_value_type<int*>, int>);
read_first<int*> 依赖 std::iterator_traits<int*> 的指针偏特化才能过编。见到 typename iterator_traits<_Iter>::value_type,应理解为向 iterator 查询元素值类型,而非容器暴露成员类型。
旧式 STL 用 tag dispatch 做编译期分流:算法先经 iterator_traits 取 category tag,再将空对象 category{} 传给重载函数(如 std::advance 对输入、双向、随机访问路径的分流):
#include <iterator>
template <class Iterator, class Distance>
void advance_impl(Iterator& it, Distance n, std::input_iterator_tag) {
while (n > 0) {
--n;
++it;
}
}
template <class Iterator, class Distance>
void advance_impl(Iterator& it, Distance n, std::bidirectional_iterator_tag) {
if (n >= 0) {
while (n > 0) {
--n;
++it;
}
} else {
while (n < 0) {
++n;
--it;
}
}
}
template <class Iterator, class Distance>
void advance_impl(Iterator& it, Distance n, std::random_access_iterator_tag) {
it += n;
}
template <class Iterator, class Distance>
void mini_advance(Iterator& it, Distance n) {
using category = typename std::iterator_traits<Iterator>::iterator_category;
advance_impl(it, n, category{});
}
同名 mini_advance 对 std::vector<int>::iterator 直接 it += n,对 std::list<int>::iterator 则逐步移动。C++20 concepts 正将这类隐式重载转为签名约束:
| 编译期分发机制 | 能力判定依据 | 典型写法 | 诊断与适用场景 |
|---|---|---|---|
| tag dispatch(传统 STL) | iterator_traits<Iterator>::iterator_category | advance_impl(it, n, category{}) | 常见于旧标准库,不满足时多在模板体深处报错 |
| C++20 concepts | std::random_access_iterator 等概念约束 | template <std::random_access_iterator Iterator> | 约束前移至签名处,错误更早暴露 |
边界与误区
iterator_category 是向算法发出的能力契约:自定义 iterator 缺少 difference_type 会导致距离与偏移算法实例化失败;若把仅能单步移动的 iterator 错标为 random access,算法将生成 it += n,轻则编译失败,重则产生错误语义。
排查顺序
阅读涉及 traits 的模板算法时,按四步追踪:
- 定位算法模板参数(如
Iterator); - 查看
std::iterator_traits提取了哪些关联类型; - 核对分发依据是 category tag 重载还是 concept 约束;
- 将选中路径与复杂度承诺一一对应。
6.4 标准 iterator adapter
iterator adapter 保留 iterator 接口而不拥有元素,它包装底层 iterator、容器或流,将 *it、++it、*out = v 转译为反向遍历、容器插入或流读写。
| 适配器 | 包装对象 | 关键表达式映射 | 前提约束 |
|---|---|---|---|
std::reverse_iterator | 正向 iterator base | ++r 执行 --base;*r 读 base 前驱元素 | 底层至少为 bidirectional iterator |
std::back_inserter(std::back_insert_iterator) | 目标容器 | *out = v 转调 push_back(v) | 容器须支持 push_back |
std::front_inserter | 目标容器 | *out = v 转调 push_front(v) | 容器须支持 push_front |
std::inserter | 容器与位置 pos | *out = v 转调 insert(pos, v) 并更新位置 | 容器须支持 insert(pos, v) |
std::istream_iterator<T> | 输入流对象 | ++it 从流格式化读取下一元素 | 依赖流状态,仅单趟读取 |
std::ostream_iterator<T> | 输出流对象 | *out = v 将值写入输出流 | 依赖流可用状态,仅只写输出 |
std::reverse_iterator 通过内部 base 构造反向半开区间 [make_reverse_iterator(end), make_reverse_iterator(begin)):
std::vector<int> numbers{1, 2, 3, 4};
auto rfirst = std::make_reverse_iterator(numbers.end());
auto rlast = std::make_reverse_iterator(numbers.begin());
int value = *rfirst; // 4
auto base = rfirst.base(); // numbers.end()
边界与误区
r.base() 与 *r 存在 off-by-one 偏移:rfirst.base() 返回正向尾后位置 numbers.end(),而 *rfirst 读取的是其前驱元素 4。这保证了正反向半开区间的边界对称;调试或转换区间时误把 base() 当作当前元素会导致错位。
插入 adapter 将“覆写已有元素”转为“容器扩容插入”:直接传 target.begin() 需预留足够元素,改用 std::back_inserter(target) 则通过 push_back 建立元素生命周期:
std::vector<int> source{1, 2, 3};
std::vector<int> target;
std::copy(source.begin(), source.end(), std::back_inserter(target));
stream adapter 将流接上算法,std::ostream_iterator<int> 把每次赋值转成向 std::cout 写入整数与空格:
#include <iostream>
#include <iterator>
#include <vector>
void print_numbers(const std::vector<int>& numbers) {
std::copy(numbers.begin(), numbers.end(), std::ostream_iterator<int>(std::cout, " "));
}
读 adapter 源码时紧盯两点:内部包装了谁,以及 operator*、operator++、operator= 映射到哪条底层动作。
6.5 iterator 失效与算法解耦
iterator 失效指容器修改后旧 iterator 不再合法指向原位置。STL 的解耦边界在此划定:算法只按区间推进、不校验修改历史,位置安全性由调用者按容器规则维护。
贯穿样本的 first、last 依赖 numbers 当前缓冲区;一旦 push_back 扩容,旧位置便指向已释放内存:
std::vector<int> numbers{1, 2, 3, 4};
auto first = numbers.begin();
auto last = numbers.end();
numbers.push_back(5); // 可能触发重新分配
// 此处继续使用 first 或 last 需要先根据 vector 的容量变化判断有效性。
std::vector 由连续缓冲、size 与 capacity 组成:未超容时 push_back 仅尾部构造,旧地址不变;触发扩容则重分配、迁移元素并释放旧块,旧 iterator、指针与引用全数失效。
容器存储形状决定失效边界,关键看修改是否搬迁元素、销毁节点或重建控制结构:
| 修改场景 | 依赖的底层状态 | 典型失效后果 |
|---|---|---|
| 连续容器扩容重分配 | 连续存储基址、容量边界 | 旧 iterator、引用与指针全部失效 |
| 连续容器中间插入或删除 | 操作点后的元素顺序与地址 | 插入/删除点及之后的位置失效 |
链表(std::list)插入新节点 | 独立节点地址与链接关系 | 指向既有节点的 iterator 保持有效 |
链表(std::list)删除节点 | 被删除节点本身 | 指向被删节点的 iterator 失效 |
分段容器(std::deque)增删 | 分段缓冲区与中控控制结构 | 取决于是否重配控制结构与操作位置 |
| 哈希容器 rehash | bucket 数组与节点分桶关系 | iterator 路径失效,需重新获取 |
边界与误区
std::count_if 等算法不校验修改历史,并发修改、回调重入及循环复用旧 iterator 都是高发失效源;即使插入失败触发强异常回滚使容器恢复可用,已判失效的 iterator 也不会自动复活,“容器仍可用”与“旧 iterator 仍可用”必须分开判断。
排查顺序
判断旧 iterator 是否可继续使用,按五步核查:
- 确认 iterator 所属的容器实例与序列版本;
- 梳理获取到使用之间的全部容器修改(含回调与并发);
- 按存储形状判断是否发生元素搬迁、节点销毁或控制结构重建;
- 存在风险时重新获取
begin()、end()或目标位置; - 将算法调用限制在当前有效区间内。
6.6 mini iterator 与 mini reverse_iterator 实现路径
动手实现最小 iterator 可将抽象压回成员状态、嵌套别名与运算符边界。下面以裸指针 T* 构建最小随机访问 iterator:
#include <cstddef>
#include <iterator>
template <class T>
class MiniVectorIterator {
public:
using iterator_category = std::random_access_iterator_tag;
using value_type = T;
using difference_type = std::ptrdiff_t;
using pointer = T*;
using reference = T&;
MiniVectorIterator() = default;
explicit MiniVectorIterator(T* current) : current_(current) {}
reference operator*() const { return *current_; }
pointer operator->() const { return current_; }
MiniVectorIterator& operator++() {
++current_;
return *this;
}
MiniVectorIterator operator++(int) {
MiniVectorIterator old = *this;
++(*this);
return old;
}
MiniVectorIterator& operator--() {
--current_;
return *this;
}
MiniVectorIterator& operator+=(difference_type offset) {
current_ += offset;
return *this;
}
MiniVectorIterator operator+(difference_type offset) const {
MiniVectorIterator copy = *this;
copy += offset;
return copy;
}
difference_type operator-(MiniVectorIterator other) const {
return current_ - other.current_;
}
reference operator[](difference_type offset) const {
return current_[offset];
}
friend bool operator==(MiniVectorIterator left, MiniVectorIterator right) {
return left.current_ == right.current_;
}
friend bool operator!=(MiniVectorIterator left, MiniVectorIterator right) {
return !(left == right);
}
private:
T* current_ = nullptr;
};
MiniVectorIterator 仅封装 current_,五个 using 别名向 std::iterator_traits 暴露属性;因底层是连续指针,才能声明 std::random_access_iterator_tag 并常数时间执行 += 与 -。
若改写链表 iterator(operator++ 走 node->next,operator-- 走 node->prev),则只能声明 bidirectional 能力,确保声明与运行时复杂度一致。
下面实现最小双向 MiniReverseIterator,演示封装 base_ 与前驱解引用语义:
#include <iterator>
template <class Iterator>
class MiniReverseIterator {
public:
using iterator_type = Iterator;
using traits = std::iterator_traits<Iterator>;
using value_type = typename traits::value_type;
using difference_type = typename traits::difference_type;
using pointer = typename traits::pointer;
using reference = typename traits::reference;
MiniReverseIterator() = default;
explicit MiniReverseIterator(Iterator base) : base_(base) {}
Iterator base() const { return base_; }
reference operator*() const {
Iterator copy = base_;
--copy;
return *copy;
}
MiniReverseIterator& operator++() {
--base_;
return *this;
}
MiniReverseIterator& operator--() {
++base_;
return *this;
}
friend bool operator==(MiniReverseIterator left, MiniReverseIterator right) {
return left.base_ == right.base_;
}
private:
Iterator base_{};
};
MiniReverseIterator::operator++ 执行 --base_,operator* 复制 base_ 回退后解引用,既读前驱又维持 base() 的半开语义;因依赖 --,无法包装 input 或 forward iterator。
接回容器视角时,视图或容器只需将内部边界包装为 [begin(), end()):
template <class T>
class MiniArrayView {
public:
using iterator = MiniVectorIterator<T>;
MiniArrayView(T* data, std::size_t size) : data_(data), size_(size) {}
iterator begin() { return iterator(data_); }
iterator end() { return iterator(data_ + size_); }
private:
T* data_ = nullptr;
std::size_t size_ = 0;
};
MiniArrayView 不管分配与生命周期,仅将 (data_, size_) 映射为 [begin, end);对象生命周期、容量、异常安全与失效规则归容器本体。
核心判断
阅读标准库容器 iterator 源码或排查实现时,按四步切入:
- 查内部状态成员(指针、节点、分段块指针或
base); - 查
iterator_traits别名与iterator_category/ concept 声明; - 查
operator*、operator++等位置运算的底层映射; - 回到容器修改操作核对失效边界。
最小自检任务
阅读下面代码,独立判断四个问题:
std::copy的输入端与输出端分别需要什么 iterator 能力?std::advance在std::vector<int>与std::list<int>上的复杂度为何不同?r.base()指向哪个正向位置,与*r有何关系?source.push_back(4)之后,saved能否继续解引用应如何判断?
#include <algorithm>
#include <iterator>
#include <list>
#include <vector>
int main() {
std::vector<int> source{1, 2, 3};
std::vector<int> target;
auto saved = source.begin();
auto r = std::make_reverse_iterator(source.end());
std::copy(source.begin(), source.end(), std::back_inserter(target));
std::advance(saved, 2);
source.push_back(4);
std::list<int> nodes{1, 2, 3};
auto node_it = nodes.begin();
std::advance(node_it, 2);
(void)r;
}
本章知识点总结
- 位置接口与半开区间
iterator 将异构存储统一为位置值对象,算法沿
[first, last)推进,尾后位置last仅可比较、严禁解引用。 - 能力分层
output、input、forward、bidirectional、random access、contiguous逐级增强语义承诺,直接约束算法选择(如std::sort与list::sort())。 - 随机访问与连续边界
std::deque支持随机访问表达式但不保证地址连续,仅std::vector、std::array与原生指针具备contiguous承诺。 - traits 与编译期分发
std::iterator_traits为类类型 iterator 与裸指针提供统一查询入口,配合 tag dispatch 或 C++20 concepts 在编译期分流最优路径。 - adapter 映射
reverse_iterator(++对应--base,*r读base前驱)、插入器与流适配器不拥有元素,只通过重映射读写表达式改写底层动作。 - 失效与解耦边界
算法不校验容器修改历史,有效性由存储模型(重分配、节点销毁、rehash)决定,且异常回滚不会复活已失效的旧 iterator。
- 最小实现契约
自定义 iterator 必须保证内部状态、五个 traits 别名、位置运算复杂度与声明的
iterator_category严格一致。