Chapter 49: Mini Iterator
核心问题与阅读主线
Mini STL 引入 iterator,旨在把“元素如何存储”与“算法如何遍历”解耦为统一的位置接口:它必须同时交付当前位置状态、操作集合与供算法读取的类型信息。
全章共用场景样本
本章贯穿实现 mini_vector<T> 的指针式随机访问迭代器 vector_iterator<T>、反向迭代器 reverse_iterator<It> 与最小算法分发(distance、advance)。后续容器只需暴露 begin()、end()、rbegin()、rend(),算法即可遍历元素而无需读取内部指针。
关键事实
本章以 C++17 iterator_category 与 tag dispatch 为主线,并在 49.4 节对照 C++20 concepts;真实 STL 的 proxy reference、sentinel、contiguous iterator、iter_move、iter_swap、const 转换与 debug iterator 本章暂不展开。
49.1 实现 iterator traits
iterator_traits<It> 为算法提供统一的编译期元信息入口,将“读取类型信息”与“iterator 执行移动”拆开,从而同时接管裸指针、容器迭代器与适配器。
下面的最小 traits 由主模板与指针偏特化组成:主模板读取自定义类内的五个嵌套别名,偏特化则将 T* 与 const T* 接入同一套入口:
#include <cstddef>
#include <iterator>
#include <type_traits>
namespace mini {
template<class It>
struct iterator_traits {
using value_type = typename It::value_type;
using difference_type = typename It::difference_type;
using pointer = typename It::pointer;
using reference = typename It::reference;
using iterator_category = typename It::iterator_category;
};
template<class T>
struct iterator_traits<T*> {
using value_type = std::remove_cv_t<T>;
using difference_type = std::ptrdiff_t;
using pointer = T*;
using reference = T&;
using iterator_category = std::random_access_iterator_tag;
};
template<class T>
struct iterator_traits<const T*> {
using value_type = std::remove_cv_t<T>;
using difference_type = std::ptrdiff_t;
using pointer = const T*;
using reference = const T&;
using iterator_category = std::random_access_iterator_tag;
};
} // namespace mini
主模板与指针偏特化在五个关联类型上的映射如下:
| 关联类型 | 主模板 iterator_traits<It> | 偏特化 iterator_traits<T*> | 偏特化 iterator_traits<const T*> |
|---|---|---|---|
value_type | It::value_type | std::remove_cv_t<T> | std::remove_cv_t<T> |
difference_type | It::difference_type | std::ptrdiff_t | std::ptrdiff_t |
pointer | It::pointer | T* | const T* |
reference | It::reference | T& | const T& |
iterator_category | It::iterator_category | std::random_access_iterator_tag | std::random_access_iterator_tag |
以 mini_distance(It first, It last) 读取 mini::iterator_traits<It>::difference_type 为例,三种实参走不同模板路径:
int*:主模板找不到int*::difference_type,改由T*偏特化接管;const int*:const T*偏特化通过std::remove_cv_t<T>保留value_type为int,仅对pointer与reference保留const;mini_vector<int>::iterator:直接命中主模板读取类内嵌套别名。
只提供 ++it、*it 而缺失 traits 别名的类型,无法被 C++17 算法识别能力边界。C++20 虽新增 iter_value_t、iter_reference_t 与 iterator_concept,但 traits 暴露元信息、iterator 负责移动的分工不变。
排查顺序
定位 traits 编译报错或算法分流异常时,按四步核对:
- 确认算法读取了哪些关联类型(如
difference_type、iterator_category); - 检查自定义 iterator 类是否完整提供五个嵌套别名;
- 检查
T*与const T*偏特化是否覆盖原始指针入口; - 核对
iterator_category与实际操作一致——若只支持++it却标为std::random_access_iterator_tag,将在算法实例化it + n或last - first时报错。
49.2 实现 random access iterator
连续存储上的随机访问迭代器只需保存单个 T* 指针:begin() 指向首元素,end() 指向尾后位置,递增、下标与测距均直接落到指针运算。
以下最小实现暂不含 debug 边界检查;调用者须保证迭代器同属一个连续区间,且仅在有效范围内解引用:
namespace mini {
template<class T>
class vector_iterator {
public:
using value_type = std::remove_cv_t<T>;
using difference_type = std::ptrdiff_t;
using pointer = T*;
using reference = T&;
using iterator_category = std::random_access_iterator_tag;
vector_iterator() = default;
explicit vector_iterator(pointer current) : current_(current) {}
reference operator*() const { return *current_; }
pointer operator->() const { return current_; }
reference operator[](difference_type n) const { return *(current_ + n); }
vector_iterator& operator++() {
++current_;
return *this;
}
vector_iterator operator++(int) {
vector_iterator old(*this);
++(*this);
return old;
}
vector_iterator& operator--() {
--current_;
return *this;
}
vector_iterator operator--(int) {
vector_iterator old(*this);
--(*this);
return old;
}
vector_iterator& operator+=(difference_type n) {
current_ += n;
return *this;
}
vector_iterator& operator-=(difference_type n) {
current_ -= n;
return *this;
}
friend vector_iterator operator+(vector_iterator it, difference_type n) {
it += n;
return it;
}
friend vector_iterator operator+(difference_type n, vector_iterator it) {
it += n;
return it;
}
friend vector_iterator operator-(vector_iterator it, difference_type n) {
it -= n;
return it;
}
friend difference_type operator-(vector_iterator lhs, vector_iterator rhs) {
return lhs.current_ - rhs.current_;
}
friend bool operator==(vector_iterator lhs, vector_iterator rhs) {
return lhs.current_ == rhs.current_;
}
friend bool operator!=(vector_iterator lhs, vector_iterator rhs) {
return !(lhs == rhs);
}
friend bool operator<(vector_iterator lhs, vector_iterator rhs) {
return lhs.current_ < rhs.current_;
}
friend bool operator>(vector_iterator lhs, vector_iterator rhs) {
return rhs < lhs;
}
friend bool operator<=(vector_iterator lhs, vector_iterator rhs) {
return !(rhs < lhs);
}
friend bool operator>=(vector_iterator lhs, vector_iterator rhs) {
return !(lhs < rhs);
}
pointer base() const { return current_; }
private:
pointer current_ = nullptr;
};
} // namespace mini
相比裸指针 T*,vector_iterator<T> 作为 mini_vector<T> 的公开位置类型建立了清晰边界,并预留了 debug 扩展位(如附带所属容器地址与区间边界校验)。
关键事实
随机访问迭代器必须同时维持五条语义不变量:
- 偏移交换律:
it + n与n + it指向同一位置; - 偏移互逆:
(it + n) - it == n; - 下标等价:
it[n]等价于*(it + n); - 同区间可比:
<、<=、>、>=与-仅在同一连续区间内有定义; - 尾后边界:
end()可比较、相减及递减回退到末元素,但本身不可解引用。
下面的最小示例验证了位置跳转、距离计算与全序比较如何一起落到底层指针运算上:
int data[] = {10, 20, 30, 40};
mini::vector_iterator<int> first(data);
mini::vector_iterator<int> last(data + 4);
auto third = first + 2;
int value = *third; // 30
auto count = last - first; // 4
bool ordered = first < last;
运行时运算全部落到 current_ 指针算术,编译期则由 iterator_category 声明能力,二者必须匹配。
边界与误区
vector_iterator<T> 的有效性绑定在底层存储地址上。只要 mini_vector 未重新分配内存,现有元素迭代器持续有效;一旦触发 reallocate 搬迁存储,旧迭代器虽仍存有非空地址,但已脱离容器当前对象状态,继续解引用属于悬垂访问。
49.3 实现 reverse iterator
reverse_iterator<It> 是不拥有元素的适配器,仅保存底层位置 current_ 并反转移动与解引用偏移:可解引用时 *r 对应 *(i - 1),因此 rbegin() 由 end() 构造,rend() 由 begin() 构造。
namespace mini {
template<class It>
class reverse_iterator {
public:
using iterator_type = It;
using traits = mini::iterator_traits<It>;
using value_type = typename traits::value_type;
using difference_type = typename traits::difference_type;
using pointer = typename traits::pointer;
using reference = typename traits::reference;
using iterator_category = typename traits::iterator_category;
reverse_iterator() = default;
explicit reverse_iterator(It current) : current_(current) {}
It base() const { return current_; }
reference operator*() const {
It tmp = current_;
--tmp;
return *tmp;
}
pointer operator->() const {
return &operator*();
}
reverse_iterator& operator++() {
--current_;
return *this;
}
reverse_iterator operator++(int) {
reverse_iterator old(*this);
++(*this);
return old;
}
reverse_iterator& operator--() {
++current_;
return *this;
}
reverse_iterator operator--(int) {
reverse_iterator old(*this);
--(*this);
return old;
}
reverse_iterator& operator+=(difference_type n) {
current_ -= n;
return *this;
}
reverse_iterator& operator-=(difference_type n) {
current_ += n;
return *this;
}
reference operator[](difference_type n) const {
return *(*this + n);
}
friend reverse_iterator operator+(reverse_iterator it, difference_type n) {
it += n;
return it;
}
friend reverse_iterator operator-(reverse_iterator it, difference_type n) {
it -= n;
return it;
}
friend difference_type operator-(reverse_iterator lhs, reverse_iterator rhs) {
return rhs.current_ - lhs.current_;
}
friend bool operator==(reverse_iterator lhs, reverse_iterator rhs) {
return lhs.current_ == rhs.current_;
}
friend bool operator!=(reverse_iterator lhs, reverse_iterator rhs) {
return !(lhs == rhs);
}
friend bool operator<(reverse_iterator lhs, reverse_iterator rhs) {
return rhs.current_ < lhs.current_;
}
private:
It current_{};
};
} // namespace mini
包装层在完全复用底层类型信息与状态的前提下,将外部操作映射到底层反向动作:
| 反向操作 | 底层 current_ 对应行为 | 语义说明 |
|---|---|---|
rbegin() / rend() | reverse_iterator(end()) / reverse_iterator(begin()) | 维持半开区间 [rbegin, rend) |
*rit / rit->m | 复制 current_ 后执行 --tmp; *tmp | 跳过 end() 哨兵,读取 base() 前一格 |
rit.base() | 直接返回 current_ | 指向 *rit 在正向顺序中的后一位置 |
++rit / rit += n | --current_ / current_ -= n | 反向逻辑前进等价于底层向低地址回退 |
--rit / rit -= n | ++current_ / current_ += n | 反向逻辑后退等价于底层向高地址前进 |
lhs - rhs / lhs < rhs | rhs.current_ - lhs.current_ / rhs.current_ < lhs.current_ | 距离与偏序关系同步反转 |
用同一数组验证 base() 与 *rfirst 的一格偏移关系:
int data[] = {10, 20, 30, 40};
using It = mini::vector_iterator<int>;
It first(data);
It last(data + 4);
mini::reverse_iterator<It> rfirst(last);
int value = *rfirst; // 40
It underlying = rfirst.base();
bool points_to_end = underlying == last;
边界与误区
rfirst.base() 等于 last,而 *rfirst 读出末元素 40,两者始终相差一格。在容器上根据反向迭代器删除元素时切忌直接写 erase(rit.base()),因为 rit.base() 指向 *rit 后方位置;删除 *rit 对应元素应先回退一格(如传入 std::prev(rit.base()) 对应的正向位置)。
反向迭代器的能力上限取决于底层 It:底层仅双向时只支持 ++ / --,底层为随机访问时才支持 + n、- n、[] 与 -。若适配 mini_list,需按 iterator_category 或 concepts 约束这些操作。
49.4 实现 iterator category 分发
category 分发使同一算法按迭代器能力选择不同复杂度路径。C++17 tag dispatch 分为两层:公开函数读取 iterator_category 并传递空标签 category{},由编译期重载决议选定 *_impl。
以 mini::distance 为例:
namespace mini {
template<class It>
auto distance_impl(It first, It last, std::input_iterator_tag)
-> typename mini::iterator_traits<It>::difference_type {
typename mini::iterator_traits<It>::difference_type n = 0;
for (; first != last; ++first) {
++n;
}
return n;
}
template<class It>
auto distance_impl(It first, It last, std::random_access_iterator_tag)
-> typename mini::iterator_traits<It>::difference_type {
return last - first;
}
template<class It>
auto distance(It first, It last)
-> typename mini::iterator_traits<It>::difference_type {
using category = typename mini::iterator_traits<It>::iterator_category;
return distance_impl(first, last, category{});
}
} // namespace mini
分发利用标准标签继承链:std::random_access_iterator_tag → std::bidirectional_iterator_tag → std::forward_iterator_tag → std::input_iterator_tag。存在精确重载时走最优路径,否则隐式向上转型回退到更弱通用路径。
mini::advance 进一步体现能力边界:输入迭代器只能向前推,双向迭代器支持正负方向移动,随机访问迭代器则一步跳转 it += n。
namespace mini {
template<class It, class Distance>
void advance_impl(It& it, Distance n, std::input_iterator_tag) {
while (n > 0) {
++it;
--n;
}
}
template<class It, class Distance>
void advance_impl(It& it, Distance n, std::bidirectional_iterator_tag) {
if (n >= 0) {
while (n > 0) {
++it;
--n;
}
} else {
while (n < 0) {
--it;
++n;
}
}
}
template<class It, class Distance>
void advance_impl(It& it, Distance n, std::random_access_iterator_tag) {
it += n;
}
template<class It, class Distance>
void advance(It& it, Distance n) {
using category = typename mini::iterator_traits<It>::iterator_category;
advance_impl(it, n, category{});
}
} // namespace mini
两类算法在不同 iterator_category 下的分发路径与复杂度承诺如下:
iterator_category | mini::distance(first, last) | mini::advance(it, n) | 复杂度承诺 |
|---|---|---|---|
std::input_iterator_tag(及 forward 回退) | 循环 ++first 计数 | 仅处理 n >= 0,循环 ++it | 线性 O(n) |
std::bidirectional_iterator_tag | 回退至 input_iterator_tag 重载 | 按 n >= 0 / n < 0 循环 ++it 或 --it | 线性 `O( |
std::random_access_iterator_tag | 直接返回 last - first | 直接执行 it += n | 常数 O(1) |
C++20 concepts 直接在函数签名约束操作集合(如 std::input_iterator、std::random_access_iterator),省去中间标签转发:
#include <concepts>
#include <iterator>
namespace mini {
template<std::input_iterator It>
auto concept_distance(It first, It last) {
typename std::iterator_traits<It>::difference_type n = 0;
for (; first != last; ++first) {
++n;
}
return n;
}
template<std::random_access_iterator It>
auto concept_distance(It first, It last) {
return last - first;
}
} // namespace mini
tag dispatch 与 concepts 均将算法分支建立在迭代器能力之上,工程取舍集中在表达与诊断位置:
| 对比维度 | C++17 tag dispatch | C++20 concepts |
|---|---|---|
| 分流机制 | 通过 iterator_traits<It>::iterator_category 空标签触发重载决议 | 直接在函数签名约束标准 concept(如 std::random_access_iterator) |
| 报错定位 | 能力与标签不匹配时,往往延迟至 *_impl 内部实例化处报错 | 在调用点函数签名处立即暴露能力约束失败 |
| 工程角色 | 展示传统 STL 源码实现结构 | 适合编写现代接口约束与静态验收测试 |
核心判断
实现与验收 mini iterator 时建议遵循五步顺序:
- 固定状态模型(如
vector_iterator<T>的单指针current_); - 补齐解引用、移动、算术与比较操作并守住各自不变量;
- 完整提供
iterator_traits五个关联类型及T*/const T*偏特化; - 用 tag dispatch 或 concepts 验证算法能选对复杂度路径;
- 结合容器内存变更(如
reallocate)界定失效边界。
最小自检任务
阅读下面代码,独立判断 forward_count、reverse_count、first_reverse_value 与 base_of_rfirst 的结果关系,并解释 reverse_iterator::operator++ 为何向底层反方向移动:
int data[] = {1, 2, 3, 4, 5};
using It = mini::vector_iterator<int>;
It first(data);
It last(data + 5);
mini::reverse_iterator<It> rfirst(last);
mini::reverse_iterator<It> rlast(first);
auto forward_count = mini::distance(first, last);
auto reverse_count = mini::distance(rfirst, rlast);
int first_reverse_value = *rfirst;
It base_of_rfirst = rfirst.base();
本章知识点总结
- traits 统一入口
iterator_traits<It>集中暴露value_type、difference_type、pointer、reference与iterator_category,并通过T*/const T*偏特化让原始指针共享同一套算法接口。 - 状态与能力一致
vector_iterator<T>以单个current_指针承载位置状态,实际操作集合必须与声明的iterator_category严格匹配,避免算法实例化报错。 - 尾后边界与存储失效
end()可比较、相减及递减回退,严禁解引用;容器reallocate搬迁内存后,旧 iterator 虽仍存非空地址但已悬垂失效。 - 反向偏移与方向反转
reverse_iterator(i)可解引用时访问*(i - 1),而base()返回原始i(两者差一格),++、+=、-与<均将底层方向反转。 - adapter 能力上限
reverse_iterator不拥有元素且复用底层 iterator 的状态与 traits,可用操作受底层 iterator 能力限制。 - tag dispatch 编译期分流
distance与advance借标准标签继承链完成重载决议,使线性扫描路径与常数跳转路径共用同一对外接口。 - C++20 concepts 对照
concepts 将能力约束前置到函数签名,比内部
*_impl延迟报错的 tag dispatch 更早暴露接口能力缺失。