Skip to main content

Chapter 6: Iterator System

核心问题与阅读主线

本章导读6 个核心小节 · 附自检与总结

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> 时循环写法不变,内部状态从连续地址转为节点指针。

核心判断

阅读算法源码时,直接按循环体内的表达式反推最低能力要求:

  1. 仅出现 ++it、it != last、*it:只需输入遍历能力(单趟即可);
  2. 出现 --it:至少需要双向能力(bidirectional);
  3. 出现 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 iteratorstd::back_insert_iterator<std::vector<int>>写入、递增适合作为算法输出端,读取旧值无意义
input iteratorstd::istream_iterator<int>只读、递增、单趟遍历消费输入流或一次性序列
forward iteratorstd::forward_list<int>::iterator读取、递增、多趟遍历可保存位置并重复扫描同一区间
bidirectional iteratorstd::list<int>::iteratorforward 能力 + --it支持反向遍历与双向链表移动
random access iteratorstd::deque<int>::iteratorbidirectional 能力 + + n、- n、it[n]支持常数时间距离计算与按偏移跳转
contiguous iteratorstd::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 能力层级,按四问递进:

  1. 只能单向读、只能写,还是可读写?
  2. 递增后旧副本是否仍有效(单趟 input vs 多趟 forward)?
  3. 是否支持 --it 回退(bidirectional)与 + n 常数时间跳转(random access)?
  4. 相邻元素是否保证物理地址连续(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_categoryadvance_impl(it, n, category{})常见于旧标准库,不满足时多在模板体深处报错
C++20 conceptsstd::random_access_iterator 等概念约束template <std::random_access_iterator Iterator>约束前移至签名处,错误更早暴露

边界与误区

注意

iterator_category 是向算法发出的能力契约:自定义 iterator 缺少 difference_type 会导致距离与偏移算法实例化失败;若把仅能单步移动的 iterator 错标为 random access,算法将生成 it += n,轻则编译失败,重则产生错误语义。

排查顺序

阅读涉及 traits 的模板算法时,按四步追踪:

  1. 定位算法模板参数(如 Iterator);
  2. 查看 std::iterator_traits 提取了哪些关联类型;
  3. 核对分发依据是 category tag 重载还是 concept 约束;
  4. 将选中路径与复杂度承诺一一对应。

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)增删分段缓冲区与中控控制结构取决于是否重配控制结构与操作位置
哈希容器 rehashbucket 数组与节点分桶关系iterator 路径失效,需重新获取

边界与误区

注意

std::count_if 等算法不校验修改历史,并发修改、回调重入及循环复用旧 iterator 都是高发失效源;即使插入失败触发强异常回滚使容器恢复可用,已判失效的 iterator 也不会自动复活,“容器仍可用”与“旧 iterator 仍可用”必须分开判断。

排查顺序

判断旧 iterator 是否可继续使用,按五步核查:

  1. 确认 iterator 所属的容器实例与序列版本;
  2. 梳理获取到使用之间的全部容器修改(含回调与并发);
  3. 按存储形状判断是否发生元素搬迁、节点销毁或控制结构重建;
  4. 存在风险时重新获取 begin()、end() 或目标位置;
  5. 将算法调用限制在当前有效区间内。

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 源码或排查实现时,按四步切入:

  1. 查内部状态成员(指针、节点、分段块指针或 base);
  2. 查 iterator_traits 别名与 iterator_category / concept 声明;
  3. 查 operator*、operator++ 等位置运算的底层映射;
  4. 回到容器修改操作核对失效边界。

最小自检任务​

动手自检先独立判断

阅读下面代码,独立判断四个问题:

  1. std::copy 的输入端与输出端分别需要什么 iterator 能力?
  2. std::advance 在 std::vector<int> 与 std::list<int> 上的复杂度为何不同?
  3. r.base() 指向哪个正向位置,与 *r 有何关系?
  4. 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 严格一致。