Skip to main content

Chapter 49: Mini Iterator

核心问题与阅读主线

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

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_typeIt::value_typestd::remove_cv_t<T>std::remove_cv_t<T>
difference_typeIt::difference_typestd::ptrdiff_tstd::ptrdiff_t
pointerIt::pointerT*const T*
referenceIt::referenceT&const T&
iterator_categoryIt::iterator_categorystd::random_access_iterator_tagstd::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 编译报错或算法分流异常时,按四步核对:

  1. 确认算法读取了哪些关联类型(如 difference_type、iterator_category);
  2. 检查自定义 iterator 类是否完整提供五个嵌套别名;
  3. 检查 T* 与 const T* 偏特化是否覆盖原始指针入口;
  4. 核对 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 扩展位(如附带所属容器地址与区间边界校验)。

关键事实

随机访问迭代器必须同时维持五条语义不变量:

  1. 偏移交换律:it + n 与 n + it 指向同一位置;
  2. 偏移互逆:(it + n) - it == n;
  3. 下标等价:it[n] 等价于 *(it + n);
  4. 同区间可比:<、<=、>、>= 与 - 仅在同一连续区间内有定义;
  5. 尾后边界: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 < rhsrhs.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_categorymini::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 dispatchC++20 concepts
分流机制通过 iterator_traits<It>::iterator_category 空标签触发重载决议直接在函数签名约束标准 concept(如 std::random_access_iterator)
报错定位能力与标签不匹配时,往往延迟至 *_impl 内部实例化处报错在调用点函数签名处立即暴露能力约束失败
工程角色展示传统 STL 源码实现结构适合编写现代接口约束与静态验收测试

核心判断

实现与验收 mini iterator 时建议遵循五步顺序:

  1. 固定状态模型(如 vector_iterator<T> 的单指针 current_);
  2. 补齐解引用、移动、算术与比较操作并守住各自不变量;
  3. 完整提供 iterator_traits 五个关联类型及 T* / const T* 偏特化;
  4. 用 tag dispatch 或 concepts 验证算法能选对复杂度路径;
  5. 结合容器内存变更(如 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 更早暴露接口能力缺失。