C++拓展：反向迭代器的思路与实现

_OP_CHEN

发布于 2026-01-14 10:24:04

670

文章被收录于专栏：C++C++

前言

在 C++ STL 的容器体系中，迭代器是连接容器与算法的核心桥梁，它封装了容器内部的数据访问逻辑，让开发者能够以统一的方式遍历不同结构的容器。正向迭代器（iterator）作为最常用的迭代器类型，实现了从容器起始位置到末尾位置的遍历，但在实际开发中，我们常常需要反向遍历容器（如从末尾元素向前输出、逆序处理数据等），这就需要反向迭代器（reverse_iterator）的支持。反向迭代器并非独立设计的迭代器类型，而是基于正向迭代器的适配器模式实现的 —— 它复用正向迭代器的核心能力，仅通过反转遍历方向，就能适配所有支持正向迭代器的容器（如 vector、list、string 等）。本文将结合 SGI-STL 3.0 版本的源码，从底层思路、核心实现、容器适配到实战测试，全方位拆解反向迭代器的设计哲学与编码实现，帮助开发者不仅 “会用”，更能 “懂原理、能手写”。

一、反向迭代器的核心设计思路

在深入代码实现之前，我们首先需要理清反向迭代器的核心设计逻辑。反向迭代器的本质是 “正向迭代器的反向封装”，其设计思路围绕以下三个核心问题展开：

1.1 核心定位：迭代器适配器

反向迭代器不是独立的迭代器实现，而是一个适配器（Adapter） —— 它接收一个已有的正向迭代器作为模板参数，通过重写迭代器的核心操作符（++、--、*、->等），将正向遍历逻辑反转，从而实现反向遍历。

这种设计的优势在于：

复用性强：无需为每个容器单独设计反向迭代器，只需传递该容器的正向迭代器即可适配。
一致性高：所有容器的反向迭代器遵循统一的接口规范，开发者使用方式完全一致。
维护成本低：正向迭代器的逻辑变更可直接同步到反向迭代器，无需额外修改。

例如，vector 的反向迭代器是基于 vector 的原生指针迭代器（T*）适配而来，list 的反向迭代器则是基于 list 的双向迭代器（__list_iterator）适配而来，二者的底层容器结构完全不同，但反向迭代器的适配逻辑保持统一。

1.2 关键矛盾：遍历方向与边界对齐

反向迭代器的核心矛盾的是 “反向遍历” 与 “容器边界统一” 的协调。在 STL 中，所有容器的迭代器都遵循 “左闭右开” 的区间规则：

正向迭代器：begin()指向第一个元素，end()指向最后一个元素的下一个位置（不存储有效数据）。
遍历区间：[begin(), end())，遍历终止条件为iterator == end()。

为了保证反向迭代器与正向迭代器的接口一致性，反向迭代器必须延续这一 “左闭右开” 规则，但需要将遍历方向反转。此时就产生了一个关键设计决策：反向迭代器的rbegin()和rend()应如何映射到正向迭代器的边界？

SGI-STL 给出的解决方案是：

反向迭代器的rbegin()：对应正向迭代器的end()（即指向最后一个元素的下一个位置）。
反向迭代器的rend()：对应正向迭代器的begin()（即指向第一个元素）。
反向遍历区间：[rbegin(), rend())，遍历终止条件为reverse_iterator == rend()。

这一设计的巧妙之处在于，它完全复用了正向迭代器的边界规则，同时通过 “反向解引用” 实现了反向遍历。例如，对于容器[1,2,3,4]：

正向迭代器区间：begin() -> 1，end() -> 4的下一个位置，遍历顺序为1→2→3→4。
反向迭代器区间：rbegin() -> end()，rend() -> begin()，遍历顺序为4→3→2→1。

1.3 核心操作的反向映射

反向迭代器的所有操作符都需要基于正向迭代器的操作进行 “反向映射”，这是实现反向遍历的关键。核心映射关系如下：

反向迭代器操作	正向迭代器对应操作	功能说明
operator++	operator--	反向迭代器自增（向后遍历）= 正向迭代器自减
operator--	operator++	反向迭代器自减（向前遍历）= 正向迭代器自增
operator*	*(current - 1)	解引用时访问正向迭代器当前位置的前一个元素
operator[]	*(rbegin() + n)	访问反向迭代器偏移 n 个位置的元素（本质是正向偏移的反向计算）

其中，operator*的实现是最容易让人困惑的地方 —— 为什么反向迭代器的解引用需要访问正向迭代器的前一个位置？这正是为了配合rbegin()和rend()的边界映射：

rbegin()对应正向迭代器的end()（无效位置），解引用时需要向前偏移 1 位，才能访问到最后一个有效元素。
rend()对应正向迭代器的begin()，当反向迭代器遍历到rend()时，停止遍历，避免访问无效数据。

举个直观的例子：容器元素：[1,2,3,4]正向迭代器：begin()→1，end()→无效位置反向迭代器：rbegin() = reverse_iterator(end())，解引用时*rbegin() = *(end() - 1) = 4当rbegin()自增（++rbegin()），正向迭代器end()自减为4的位置，解引用时*(4的位置 - 1) = 3，以此类推，直到反向迭代器到达rend()（对应begin()），遍历终止。

1.4 版本兼容：偏特化与非偏特化实现

在 SGI-STL 3.0 中，反向迭代器提供了两个版本的实现，通过条件编译__STL_CLASS_PARTIAL_SPECIALIZATION控制：

新版本（支持类模板偏特化）：template <class Iterator> class reverse_iterator
旧版本（不支持偏特化）：reverse_bidirectional_iterator（适配双向迭代器）和reverse_iterator（适配随机访问迭代器）

这两者的核心区别在于模板参数的设计：

新版本利用 C++ 的迭代器萃取器（iterator_traits），通过正向迭代器Iterator自动推导数据类型（value_type、reference、pointer等），无需显式传递模板参数。
旧版本不支持迭代器萃取，需要显式传递T（数据类型）、Reference（引用类型）、Distance（距离类型）等模板参数，且需要针对不同迭代器类别（双向、随机访问）分别实现。

迭代器萃取器（iterator_traits）是 STL 的核心技术之一，它通过模板偏特化，从迭代器类型中提取关键信息（如迭代器类别、数据类型、引用类型等），让反向迭代器的实现更通用、更简洁。

二、SGI-STL 反向迭代器源码深度解析

为了更直观地理解反向迭代器的设计，我们先来剖析一下 SGI-STL 3.0 中反向迭代器的源码（来自stl_iterator.h、stl_vector.h、stl_list.h），大家可以重点关注类结构、核心操作符实现、容器适配逻辑等关键内容。

2.1 新版本反向迭代器（支持偏特化）

新版本反向迭代器的类模板定义如下（简化后的核心代码）：

template <class Iterator>
class reverse_iterator {
protected:
    Iterator current;  // 存储正向迭代器，核心适配对象
public:
    // 迭代器相关类型定义（通过iterator_traits萃取）
    typedef typename iterator_traits<Iterator>::iterator_category iterator_category;
    typedef typename iterator_traits<Iterator>::value_type value_type;
    typedef typename iterator_traits<Iterator>::difference_type difference_type;
    typedef typename iterator_traits<Iterator>::pointer pointer;
    typedef typename iterator_traits<Iterator>::reference reference;
    typedef Iterator iterator_type;  // 正向迭代器类型
    typedef reverse_iterator<Iterator> self;  // 反向迭代器自身类型

public:
    // 构造函数
    reverse_iterator() {}
    explicit reverse_iterator(iterator_type x) : current(x) {}  // 接收正向迭代器构造
    reverse_iterator(const self& x) : current(x.current) {}  // 拷贝构造

    // 模板构造函数，支持不同迭代器类型的反向迭代器拷贝（如const与非const）
    template <class Iter>
    reverse_iterator(const reverse_iterator<Iter>& x) : current(x.current) {}

    // 返回底层的正向迭代器（base()方法）
    iterator_type base() const { return current; }

    // 解引用操作符：访问current的前一个位置
    reference operator*() const {
        Iterator tmp = current;
        return *--tmp;  // 先自减，再解引用
    }

    // 箭头操作符：返回指向元素的指针
    #ifndef __SGI_STL_NO_ARROW_OPERATOR
    pointer operator->() const { return &(operator*()); }
    #endif

    // 前缀自增：反向迭代器++ = 正向迭代器--（向后移动）
    self& operator++() {
        --current;
        return *this;
    }

    // 后缀自增：返回自增前的副本
    self operator++(int) {
        self tmp = *this;
        --current;
        return tmp;
    }

    // 前缀自减：反向迭代器-- = 正向迭代器++（向前移动）
    self& operator--() {
        ++current;
        return *this;
    }

    // 后缀自减：返回自减前的副本
    self operator--(int) {
        self tmp = *this;
        ++current;
        return tmp;
    }

    // 加法操作：反向迭代器 + n = 正向迭代器 - n
    self operator+(difference_type n) const {
        return self(current - n);
    }

    // 加法赋值：反向迭代器 += n = 正向迭代器 -= n
    self& operator+=(difference_type n) {
        current -= n;
        return *this;
    }

    // 减法操作：反向迭代器 - n = 正向迭代器 + n
    self operator-(difference_type n) const {
        return self(current + n);
    }

    // 减法赋值：反向迭代器 -= n = 正向迭代器 += n
    self& operator-=(difference_type n) {
        current += n;
        return *this;
    }

    // 下标操作：反向迭代器[n] = *(反向迭代器 + n)
    reference operator[](difference_type n) const { return *(*this + n); }
};

// 比较运算符重载（基于正向迭代器的比较）
template <class Iterator>
inline bool operator==(const reverse_iterator<Iterator>& x, const reverse_iterator<Iterator>& y) {
    return x.base() == y.base();  // 比较底层正向迭代器
}

template <class Iterator>
inline bool operator<(const reverse_iterator<Iterator>& x, const reverse_iterator<Iterator>& y) {
    return y.base() < x.base();  // 反向比较，保持遍历逻辑一致
}

// 反向迭代器减法：返回两个反向迭代器之间的距离
template <class Iterator>
inline typename reverse_iterator<Iterator>::difference_type
operator-(const reverse_iterator<Iterator>& x, const reverse_iterator<Iterator>& y) {
    return y.base() - x.base();  // 基于正向迭代器的距离计算
}

// 全局加法：n + 反向迭代器 = 反向迭代器 + n
template <class Iterator>
inline reverse_iterator<Iterator>
operator+(typename reverse_iterator<Iterator>::difference_type n, const reverse_iterator<Iterator>& x) {
    return reverse_iterator<Iterator>(x.base() - n);
}

代码解析：

成员变量current：存储底层的正向迭代器，是反向迭代器的核心适配对象，所有操作最终都通过current映射到正向迭代器的操作。
类型萃取：通过iterator_traits<Iterator>自动提取正向迭代器的相关类型（如value_type、reference），避免显式传递模板参数，提高通用性。
解引用operator*：这是反向迭代器最关键的操作。由于current在rbegin()时指向end()（无效位置），因此需要先创建临时变量tmp并自减，再解引用，才能获取到有效的末尾元素。
自增 / 自减操作：反向迭代器的++对应正向迭代器的--（向后移动），--对应正向迭代器的++（向前移动），这是实现反向遍历的核心逻辑。
比较运算符：反向迭代器的比较本质是底层正向迭代器的比较，但operator<需要反向比较（y.base() < x.base()），以保证遍历顺序的一致性。

2.2 旧版本反向迭代器（不支持偏特化）

在不支持类模板偏特化的编译器环境中，SGI-STL 提供了两个旧版本的反向迭代器实现，分别适配双向迭代器和随机访问迭代器：

2.2.1 双向迭代器适配（reverse_bidirectional_iterator）

template <class BidirectionalIterator, class T, class Reference = T&, class Distance = ptrdiff_t>
class reverse_bidirectional_iterator {
    typedef reverse_bidirectional_iterator<BidirectionalIterator, T, Reference, Distance> self;
protected:
    BidirectionalIterator current;  // 底层双向正向迭代器
public:
    // 迭代器类型定义（显式指定）
    typedef bidirectional_iterator_tag iterator_category;
    typedef T value_type;
    typedef Distance difference_type;
    typedef T* pointer;
    typedef Reference reference;

public:
    reverse_bidirectional_iterator() {}
    explicit reverse_bidirectional_iterator(BidirectionalIterator x) : current(x) {}

    // 返回底层正向迭代器
    BidirectionalIterator base() const { return current; }

    // 解引用操作
    Reference operator*() const {
        BidirectionalIterator tmp = current;
        return *--tmp;
    }

    // 箭头操作符
    #ifndef __SGI_STL_NO_ARROW_OPERATOR
    pointer operator->() const { return &(operator*()); }
    #endif

    // 自增/自减操作（仅支持双向迭代器的核心操作）
    self& operator++() {
        --current;
        return *this;
    }
    self operator++(int) {
        self tmp = *this;
        --current;
        return tmp;
    }
    self& operator--() {
        ++current;
        return *this;
    }
    self operator--(int) {
        self tmp = *this;
        ++current;
        return tmp;
    }
};

2.2.2 随机访问迭代器适配（reverse_iterator）

template <class RandomAccessIterator, class T, class Reference = T&, class Distance = ptrdiff_t>
class reverse_iterator {
    typedef reverse_iterator<RandomAccessIterator, T, Reference, Distance> self;
protected:
    RandomAccessIterator current;  // 底层随机访问正向迭代器
public:
    // 迭代器类型定义
    typedef random_access_iterator_tag iterator_category;
    typedef T value_type;
    typedef Distance difference_type;
    typedef T* pointer;
    typedef Reference reference;

public:
    reverse_iterator() {}
    explicit reverse_iterator(RandomAccessIterator x) : current(x) {}

    RandomAccessIterator base() const { return current; }

    Reference operator*() const { return *(current - 1); }  // 随机访问迭代器支持直接减1

    #ifndef __SGI_STL_NO_ARROW_OPERATOR
    pointer operator->() const { return &(operator*()); }
    #endif

    // 自增/自减操作
    self& operator++() {
        --current;
        return *this;
    }
    self operator++(int) {
        self tmp = *this;
        --current;
        return tmp;
    }
    self& operator--() {
        ++current;
        return *this;
    }
    self operator--(int) {
        self tmp = *this;
        ++current;
        return tmp;
    }

    // 随机访问相关操作（仅随机访问迭代器支持）
    self operator+(Distance n) const { return self(current - n); }
    self& operator+=(Distance n) {
        current -= n;
        return *this;
    }
    self operator-(Distance n) const { return self(current + n); }
    self& operator-=(Distance n) {
        current += n;
        return *this;
    }
    Reference operator[](Distance n) const { return *(*this + n); }
};

新旧版本差异：

模板参数：旧版本需要显式传递T（数据类型）、Reference（引用类型）等，而新版本通过iterator_traits自动萃取。
迭代器类别适配：旧版本需要针对双向迭代器和随机访问迭代器分别实现，而新版本通过iterator_category自动适配不同迭代器类别的操作（如随机访问迭代器支持+、-操作，双向迭代器不支持）。
解引用实现：随机访问迭代器版本的operator*直接使用current - 1（因为随机访问迭代器支持算术运算），而双向迭代器版本需要通过--tmp实现（双向迭代器仅支持自增自减）。

2.3 容器中的反向迭代器适配

反向迭代器本身是通用的适配器，需要容器提供rbegin()和rend()方法，才能将反向迭代器与容器绑定。下面以 vector 和 list 为例，解析 SGI-STL 中容器如何适配反向迭代器：

2.3.1 vector 容器的反向迭代器适配（stl_vector.h）

template <class T, class Alloc = alloc>
class vector {
public:
    typedef T value_type;
    typedef value_type* iterator;  // vector的正向迭代器是原生指针
    typedef const T* const_iterator;

    // 反向迭代器类型定义（适配vector的正向迭代器）
    #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
    typedef reverse_iterator<const_iterator> const_reverse_iterator;
    typedef reverse_iterator<iterator> reverse_iterator;
    #else
    typedef reverse_iterator<const_iterator, value_type, const_reference, difference_type> const_reverse_iterator;
    typedef reverse_iterator<iterator, value_type, reference, difference_type> reverse_iterator;
    #endif

    // 正向迭代器接口
    iterator begin() { return start; }
    const_iterator begin() const { return start; }
    iterator end() { return finish; }
    const_iterator end() const { return finish; }

    // 反向迭代器接口：rbegin()绑定end()，rend()绑定begin()
    reverse_iterator rbegin() { return reverse_iterator(end()); }
    const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
    reverse_iterator rend() { return reverse_iterator(begin()); }
    const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }

private:
    iterator start;  // 容器起始位置
    iterator finish;  // 容器末尾位置（最后一个元素的下一个）
    iterator end_of_storage;  // 容器容量末尾位置
};

2.3.2 list 容器的反向迭代器适配（stl_list.h）

template <class T, class Alloc = alloc>
class list {
public:
    typedef __list_iterator<T, T&, T*> iterator;  // list的正向双向迭代器
    typedef __list_iterator<T, const T&, const T*> const_iterator;

    // 反向迭代器类型定义（适配list的正向迭代器）
    #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
    typedef reverse_iterator<const_iterator> const_reverse_iterator;
    typedef reverse_iterator<iterator> reverse_iterator;
    #else
    typedef reverse_bidirectional_iterator<const_iterator, value_type, const_reference, difference_type> const_reverse_iterator;
    typedef reverse_bidirectional_iterator<iterator, value_type, reference, difference_type> reverse_iterator;
    #endif

    // 正向迭代器接口（list是循环双向链表，_head是哨兵节点）
    iterator begin() { return (link_type)((*_head).next); }
    const_iterator begin() const { return (link_type)((*_head).next); }
    iterator end() { return _head; }  // end()指向哨兵节点（无效位置）
    const_iterator end() const { return _head; }

    // 反向迭代器接口：rbegin()绑定end()，rend()绑定begin()
    reverse_iterator rbegin() { return reverse_iterator(end()); }
    const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
    reverse_iterator rend() { return reverse_iterator(begin()); }
    const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }

private:
    link_type _head;  // 哨兵节点
    size_t _size;  // 元素个数
};

容器适配的核心逻辑：

反向迭代器类型定义：容器通过typedef定义自身的reverse_iterator和const_reverse_iterator，将通用反向迭代器与容器的正向迭代器绑定。
rbegin () 和 rend () 实现：所有容器的rbegin()都返回reverse_iterator(end())，rend()都返回reverse_iterator(begin())，这是反向迭代器与容器边界对齐的关键。
适配通用性：无论容器的底层结构是数组（vector）、链表（list）还是其他，只要提供begin()、end()和正向迭代器，就能通过相同的方式适配反向迭代器。

三、手写反向迭代器：从 0 到 1 实现

在理解了 SGI-STL 的源码思路后，我们将动手实现一个通用的反向迭代器适配器，并适配 vector 和 list 容器。为了降低理解门槛，我们采用 “显式传递模板参数” 的方式（类似 SGI-STL 的旧版本），后续再补充迭代器萃取器的优化方案。

3.1 通用反向迭代器实现（ReverseIterator.h）

我们实现的反向迭代器需要支持以下核心功能：

接收正向迭代器、引用类型、指针类型作为模板参数。
实现解引用（operator*）、箭头（operator->）操作。
实现自增（operator++）、自减（operator--）操作（支持前缀和后缀）。
实现比较运算符（operator==、operator!=）。
支持随机访问迭代器的算术操作（+、-、+=、-=、[]）。

代码实现如下：

#ifndef REVERSE_ITERATOR_H
#define REVERSE_ITERATOR_H

namespace bit {  // 自定义命名空间，避免与STL冲突

// 反向迭代器适配器：Iterator为正向迭代器类型，Ref为引用类型，Ptr为指针类型
template <class Iterator, class Ref, class Ptr>
struct ReverseIterator {
    typedef ReverseIterator<Iterator, Ref, Ptr> Self;  // 反向迭代器自身类型
    Iterator _it;  // 存储底层正向迭代器

    // 构造函数：接收正向迭代器初始化
    ReverseIterator(Iterator it) : _it(it) {}

    // 核心操作符重载

    // 1. 解引用操作符：访问正向迭代器的前一个位置
    Ref operator*() const {
        Iterator tmp = _it;
        return *--tmp;  // 先自减，再解引用（适配双向迭代器）
    }

    // 2. 箭头操作符：返回指向元素的指针
    Ptr operator->() const {
        return &(operator*());  // 复用解引用操作
    }

    // 3. 前缀自增：++rit 向后移动（反向遍历）
    Self& operator++() {
        --_it;  // 正向迭代器自减
        return *this;
    }

    // 4. 后缀自增：rit++ 向后移动，返回自增前的副本
    Self operator++(int) {
        Self tmp(*this);  // 保存当前状态
        --_it;            // 正向迭代器自减
        return tmp;       // 返回副本
    }

    // 5. 前缀自减：--rit 向前移动（反向遍历的反向）
    Self& operator--() {
        ++_it;  // 正向迭代器自增
        return *this;
    }

    // 6. 后缀自减：rit-- 向前移动，返回自减前的副本
    Self operator--(int) {
        Self tmp(*this);  // 保存当前状态
        ++_it;            // 正向迭代器自增
        return tmp;       // 返回副本
    }

    // 7. 比较运算符：== 和 !=
    bool operator==(const Self& s) const {
        return _it == s._it;  // 比较底层正向迭代器
    }

    bool operator!=(const Self& s) const {
        return _it != s._it;  // 比较底层正向迭代器
    }

    // 8. 随机访问相关操作（仅当Iterator为随机访问迭代器时可用）
    // 加法操作：rit + n
    Self operator+(size_t n) const {
        return Self(_it - n);  // 正向迭代器减n
    }

    // 加法赋值：rit += n
    Self& operator+=(size_t n) {
        _it -= n;
        return *this;
    }

    // 减法操作：rit - n
    Self operator-(size_t n) const {
        return Self(_it + n);  // 正向迭代器加n
    }

    // 减法赋值：rit -= n
    Self& operator-=(size_t n) {
        _it += n;
        return *this;
    }

    // 下标操作：rit[n]
    Ref operator[](size_t n) const {
        return *(*this + n);  // 复用加法和解引用操作
    }

    // 9. 返回底层正向迭代器（类似STL的base()方法）
    Iterator base() const {
        return _it;
    }
};

}  // namespace bit

#endif  // REVERSE_ITERATOR_H

代码说明：

模板参数：Iterator是底层正向迭代器类型（如 vector 的T*、list 的ListIterator），Ref是元素的引用类型（如T&、const T&），Ptr是元素的指针类型（如T*、const T*）。
解引用operator*：采用Iterator tmp = _it; return *--tmp;的实现，适配双向迭代器（如 list 的迭代器），因为双向迭代器不支持算术运算（-1），只能通过自减操作移动。
随机访问操作：operator+、operator-等操作仅当Iterator是随机访问迭代器（如 vector 的T*）时可用，若用于双向迭代器（如 list 的迭代器），编译器会报错（因为双向迭代器不支持算术运算），这符合 STL 的设计规范。
命名空间：使用自定义命名空间bit，避免与 STL 的reverse_iterator冲突，方便测试。

3.2 适配 vector 容器

vector 是基于动态数组实现的容器，其正向迭代器是原生指针（T*），支持随机访问。下面实现支持反向迭代器的 vector 容器：

#ifndef VECTOR_H
#define VECTOR_H

#include <algorithm>  // 用于copy、fill等算法
#include "ReverseIterator.h"  // 包含反向迭代器头文件

namespace bit {

template <class T>
class vector {
public:
    // 正向迭代器类型定义
    typedef T* iterator;
    typedef const T* const_iterator;

    // 反向迭代器类型定义：适配正向迭代器
    typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
    typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;

    // 构造函数
    vector() : _start(nullptr), _finish(nullptr), _end_of_storage(nullptr) {}

    // 带初始化列表的构造函数（C++11及以上）
    vector(std::initializer_list<T> il) 
        : _start(nullptr), _finish(nullptr), _end_of_storage(nullptr) {
        reserve(il.size());  // 预留空间
        for (const auto& val : il) {
            push_back(val);  // 插入元素
        }
    }

    // 拷贝构造函数
    vector(const vector<T>& v) 
        : _start(nullptr), _finish(nullptr), _end_of_storage(nullptr) {
        reserve(v.capacity());  // 预留与v相同的容量
        iterator it = begin();
        const_iterator vit = v.begin();
        while (vit != v.end()) {
            *it = *vit;
            ++it;
            ++vit;
        }
        _finish = _start + v.size();
    }

    // 赋值运算符重载
    vector<T>& operator=(const vector<T>& v) {
        if (this != &v) {
            // 销毁当前资源
            delete[] _start;
            _start = _finish = _end_of_storage = nullptr;

            // 拷贝v的资源
            reserve(v.capacity());
            std::copy(v.begin(), v.end(), begin());
            _finish = _start + v.size();
        }
        return *this;
    }

    // 析构函数
    ~vector() {
        delete[] _start;
        _start = _finish = _end_of_storage = nullptr;
    }

    // 正向迭代器接口
    iterator begin() { return _start; }
    const_iterator begin() const { return _start; }
    iterator end() { return _finish; }
    const_iterator end() const { return _finish; }

    // 反向迭代器接口：核心适配逻辑
    reverse_iterator rbegin() { return reverse_iterator(end()); }  // 绑定end()
    const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
    reverse_iterator rend() { return reverse_iterator(begin()); }  // 绑定begin()
    const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }

    // 容量相关接口
    size_t size() const { return _finish - _start; }
    size_t capacity() const { return _end_of_storage - _start; }
    bool empty() const { return _start == _finish; }

    // 预留空间
    void reserve(size_t n) {
        if (n > capacity()) {
            size_t old_size = size();
            // 开辟新空间
            T* new_start = new T[n];
            // 拷贝旧数据（若存在）
            if (_start) {
                // 对于自定义类型，需要调用拷贝构造函数，此处简化为赋值
                std::copy(_start, _finish, new_start);
                delete[] _start;  // 释放旧空间
            }
            // 更新指针
            _start = new_start;
            _finish = _start + old_size;
            _end_of_storage = _start + n;
        }
    }

    // 调整大小
    void resize(size_t n, const T& val = T()) {
        if (n > capacity()) {
            reserve(n);  // 若n超过容量，先扩容
        }
        if (n > size()) {
            // 填充新元素
            std::fill(_finish, _start + n, val);
        }
        _finish = _start + n;  // 更新_finish
    }

    // 元素访问接口
    T& operator[](size_t pos) {
        // 断言pos合法（实际开发中可添加assert）
        return _start[pos];
    }
    const T& operator[](size_t pos) const {
        return _start[pos];
    }

    T& front() { return *_start; }
    const T& front() const { return *_start; }
    T& back() { return *(_finish - 1); }
    const T& back() const { return *(_finish - 1); }

    // 插入元素
    void push_back(const T& val) {
        if (_finish == _end_of_storage) {
            // 扩容：默认扩容为2倍，若初始容量为0则扩容为1
            size_t new_cap = capacity() == 0 ? 1 : capacity() * 2;
            reserve(new_cap);
        }
        *_finish = val;
        ++_finish;
    }

    // 删除末尾元素
    void pop_back() {
        if (!empty()) {
            --_finish;
        }
    }

    // 在pos位置插入元素
    iterator insert(iterator pos, const T& val) {
        // 断言pos合法
        if (_finish == _end_of_storage) {
            // 扩容
            size_t new_cap = capacity() == 0 ? 1 : capacity() * 2;
            // 计算pos在扩容后的新位置
            size_t pos_idx = pos - _start;
            reserve(new_cap);
            pos = _start + pos_idx;  // 扩容后_start可能变化，更新pos
        }
        // 移动元素
        iterator it = _finish;
        while (it > pos) {
            *it = *(it - 1);
            --it;
        }
        *pos = val;
        ++_finish;
        return pos;
    }

    // 删除pos位置的元素
    iterator erase(iterator pos) {
        // 断言pos合法且容器非空
        iterator it = pos + 1;
        while (it != _finish) {
            *(it - 1) = *it;
            ++it;
        }
        --_finish;
        return pos;
    }

    // 清空容器
    void clear() {
        _finish = _start;
    }

private:
    iterator _start;         // 指向数组起始位置
    iterator _finish;        // 指向数组末尾（最后一个元素的下一个位置）
    iterator _end_of_storage;// 指向数组容量末尾位置
};

}  // namespace bit

#endif  // VECTOR_H

核心适配点：

反向迭代器类型定义：通过typedef ReverseIterator<iterator, T&, T*> reverse_iterator将通用反向迭代器与 vector 的正向迭代器（T*）绑定，同时定义const版本的反向迭代器。
rbegin () 和 rend () 实现：rbegin()返回reverse_iterator(end())，rend()返回reverse_iterator(begin())，完全遵循 STL 的边界映射规则。
兼容性：vector 的正向迭代器是随机访问迭代器，因此反向迭代器的所有操作（包括+、-、[]）都能正常使用。

3.3 适配 list 容器

list 是基于双向循环链表实现的容器，其正向迭代器是双向迭代器（不支持随机访问，仅支持自增自减）。下面实现支持反向迭代器的 list 容器：

3.3.1 链表节点定义（ListNode.h）

#ifndef LIST_NODE_H
#define LIST_NODE_H

namespace bit {

// 链表节点结构
template <class T>
struct ListNode {
    ListNode<T>* _prev;  // 前驱指针
    ListNode<T>* _next;  // 后继指针
    T _data;             // 节点数据

    // 构造函数
    ListNode(const T& data = T()) 
        : _prev(nullptr), _next(nullptr), _data(data) {}
};

}  // namespace bit

#endif  // LIST_NODE_H

3.3.2 list 正向迭代器实现（ListIterator.h）

list 的正向迭代器需要实现双向迭代器的核心操作（++、--、*、->），代码如下：

#ifndef LIST_ITERATOR_H
#define LIST_ITERATOR_H

#include "ListNode.h"

namespace bit {

// list正向迭代器：双向迭代器
template <class T, class Ref, class Ptr>
struct ListIterator {
    typedef ListNode<T> Node;
    typedef ListIterator<T, Ref, Ptr> Self;

    Node* _node;  // 指向链表节点

    // 构造函数
    ListIterator(Node* node) : _node(node) {}

    // 解引用操作符
    Ref operator*() const {
        return _node->_data;
    }

    // 箭头操作符
    Ptr operator->() const {
        return &(_node->_data);
    }

    // 前缀自增：++it
    Self& operator++() {
        _node = _node->_next;
        return *this;
    }

    // 后缀自增：it++
    Self operator++(int) {
        Self tmp(*this);
        _node = _node->_next;
        return tmp;
    }

    // 前缀自减：--it
    Self& operator--() {
        _node = _node->_prev;
        return *this;
    }

    // 后缀自减：it--
    Self operator--(int) {
        Self tmp(*this);
        _node = _node->_prev;
        return tmp;
    }

    // 比较运算符
    bool operator==(const Self& s) const {
        return _node == s._node;
    }

    bool operator!=(const Self& s) const {
        return _node != s._node;
    }
};

}  // namespace bit

#endif  // LIST_ITERATOR_H

3.3.3 list 容器实现（List.h）

#ifndef LIST_H
#define LIST_H

#include "ListNode.h"
#include "ListIterator.h"
#include "ReverseIterator.h"  // 包含反向迭代器头文件

namespace bit {

template <class T>
class list {
public:
    typedef ListNode<T> Node;
    // 正向迭代器类型定义
    typedef ListIterator<T, T&, T*> iterator;
    typedef ListIterator<T, const T&, const T*> const_iterator;

    // 反向迭代器类型定义：适配list的正向迭代器（双向迭代器）
    typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
    typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;

    // 构造函数：创建哨兵节点（循环双向链表）
    list() {
        _head = new Node();  // 哨兵节点，不存储有效数据
        _head->_prev = _head;
        _head->_next = _head;
        _size = 0;
    }

    // 带初始化列表的构造函数
    list(std::initializer_list<T> il) : list() {
        for (const auto& val : il) {
            push_back(val);
        }
    }

    // 拷贝构造函数
    list(const list<T>& lt) : list() {
        for (const auto& val : lt) {
            push_back(val);
        }
    }

    // 赋值运算符重载
    list<T>& operator=(const list<T>& lt) {
        if (this != &lt) {
            // 清空当前链表
            clear();
            // 拷贝lt的元素
            for (const auto& val : lt) {
                push_back(val);
            }
        }
        return *this;
    }

    // 析构函数
    ~list() {
        clear();  // 销毁所有有效节点
        delete _head;  // 销毁哨兵节点
        _head = nullptr;
        _size = 0;
    }

    // 正向迭代器接口
    iterator begin() {
        return iterator(_head->_next);  // 指向第一个有效节点
    }
    const_iterator begin() const {
        return const_iterator(_head->_next);
    }
    iterator end() {
        return iterator(_head);  // 指向哨兵节点（无效位置）
    }
    const_iterator end() const {
        return const_iterator(_head);
    }

    // 反向迭代器接口：核心适配逻辑
    reverse_iterator rbegin() {
        return reverse_iterator(end());  // 绑定end()（哨兵节点）
    }
    const_reverse_iterator rbegin() const {
        return const_reverse_iterator(end());
    }
    reverse_iterator rend() {
        return reverse_iterator(begin());  // 绑定begin()（第一个有效节点）
    }
    const_reverse_iterator rend() const {
        return const_reverse_iterator(begin());
    }

    // 容量相关接口
    size_t size() const { return _size; }
    bool empty() const { return _size == 0; }

    // 元素访问接口
    T& front() {
        return _head->_next->_data;  // 第一个有效节点的数据
    }
    const T& front() const {
        return _head->_next->_data;
    }
    T& back() {
        return _head->_prev->_data;  // 最后一个有效节点的数据
    }
    const T& back() const {
        return _head->_prev->_data;
    }

    // 插入元素
    void push_back(const T& val) {
        insert(end(), val);
    }

    void push_front(const T& val) {
        insert(begin(), val);
    }

    // 在pos位置插入元素
    iterator insert(iterator pos, const T& val) {
        Node* new_node = new Node(val);  // 创建新节点
        Node* cur = pos._node;           // pos指向的节点
        Node* prev = cur->_prev;         // pos的前驱节点

        // 调整指针关系
        prev->_next = new_node;
        new_node->_prev = prev;
        new_node->_next = cur;
        cur->_prev = new_node;

        ++_size;  // 更新元素个数
        return iterator(new_node);  // 返回指向新节点的迭代器
    }

    // 删除元素
    void pop_back() {
        erase(--end());
    }

    void pop_front() {
        erase(begin());
    }

    // 删除pos位置的元素
    iterator erase(iterator pos) {
        // 断言pos不是end()（哨兵节点）且容器非空
        Node* cur = pos._node;
        Node* prev = cur->_prev;
        Node* next = cur->_next;

        // 调整指针关系
        prev->_next = next;
        next->_prev = prev;

        delete cur;  // 释放节点
        --_size;     // 更新元素个数

        return iterator(next);  // 返回pos的下一个迭代器
    }

    // 清空容器（保留哨兵节点）
    void clear() {
        iterator it = begin();
        while (it != end()) {
            it = erase(it);  // 逐个删除节点
        }
        _size = 0;
    }

private:
    Node* _head;  // 哨兵节点
    size_t _size; // 元素个数
};

}  // namespace bit

#endif  // LIST_H

核心适配点：

反向迭代器类型定义：通过typedef ReverseIterator<iterator, T&, T*> reverse_iterator将通用反向迭代器与 list 的正向迭代器（ListIterator）绑定。
rbegin () 和 rend () 实现：rbegin()绑定end()（哨兵节点），rend()绑定begin()（第一个有效节点），与 vector 的适配逻辑完全一致。
双向迭代器兼容性：list 的正向迭代器是双向迭代器，不支持算术运算（+、-），因此反向迭代器的operator+、operator-等随机访问操作无法使用（编译器会报错），这符合双向迭代器的特性。

四、反向迭代器测试

为了验证我们实现的反向迭代器是否正确，我们编写测试代码，分别测试 vector 和 list 的反向遍历功能，包括基本遍历、元素修改、边界条件、随机访问（仅 vector）等场景。

4.1 测试代码（test.cpp）

#include <iostream>
#include "vector.h"
#include "list.h"

using namespace std;
using namespace bit;  // 使用自定义命名空间

// 测试vector的反向迭代器
void test_vector_reverse_iterator() {
    cout << "===================== 测试vector反向迭代器 =====================" << endl;

    // 1. 基本反向遍历
    vector<int> v = {1, 2, 3, 4, 5};
    cout << "vector原始数据：";
    for (auto val : v) {
        cout << val << " ";
    }
    cout << endl;

    cout << "vector反向遍历（rbegin() -> rend()）：";
    vector<int>::reverse_iterator rit = v.rbegin();
    while (rit != v.rend()) {
        cout << *rit << " ";  // 预期输出：5 4 3 2 1
        ++rit;
    }
    cout << endl;

    // 2. 反向迭代器修改元素
    cout << "反向迭代器修改元素（所有元素+10）：";
    rit = v.rbegin();
    while (rit != v.rend()) {
        *rit += 10;  // 反向遍历并修改
        ++rit;
    }
    for (auto val : v) {
        cout << val << " ";  // 预期输出：11 12 13 14 15
    }
    cout << endl;

    // 3. const反向迭代器
    const vector<int> cv = {10, 20, 30, 40, 50};
    cout << "const vector反向遍历：";
    vector<int>::const_reverse_iterator crit = cv.rbegin();
    while (crit != cv.rend()) {
        cout << *crit << " ";  // 预期输出：50 40 30 20 10
        ++crit;
    }
    cout << endl;

    // 4. 随机访问操作（vector支持）
    cout << "反向迭代器随机访问：";
    rit = v.rbegin();
    cout << "rit[0] = " << rit[0] << " ";  // 预期：15
    cout << "rit[2] = " << rit[2] << " ";  // 预期：13
    cout << "rit + 3 = " << *(rit + 3) << " ";  // 预期：12
    rit += 2;
    cout << "rit += 2 后：" << *rit << " ";  // 预期：13
    cout << endl;

    // 5. 边界条件测试
    vector<int> empty_v;
    cout << "空vector反向遍历：";
    rit = empty_v.rbegin();
    while (rit != empty_v.rend()) {
        cout << *rit << " ";  // 无输出
        ++rit;
    }
    cout << "（无元素）" << endl;

    cout << "===============================================================" << endl << endl;
}

// 测试list的反向迭代器
void test_list_reverse_iterator() {
    cout << "===================== 测试list反向迭代器 ======================" << endl;

    // 1. 基本反向遍历
    list<int> lt = {10, 20, 30, 40, 50};
    cout << "list原始数据：";
    for (auto val : lt) {
        cout << val << " ";
    }
    cout << endl;

    cout << "list反向遍历（rbegin() -> rend()）：";
    list<int>::reverse_iterator rit = lt.rbegin();
    while (rit != lt.rend()) {
        cout << *rit << " ";  // 预期输出：50 40 30 20 10
        ++rit;
    }
    cout << endl;

    // 2. 反向迭代器修改元素
    cout << "反向迭代器修改元素（所有元素*2）：";
    rit = lt.rbegin();
    while (rit != lt.rend()) {
        *rit *= 2;  // 反向遍历并修改
        ++rit;
    }
    for (auto val : lt) {
        cout << val << " ";  // 预期输出：20 40 60 80 100
    }
    cout << endl;

    // 3. const反向迭代器
    const list<int> clt = {100, 200, 300, 400, 500};
    cout << "const list反向遍历：";
    list<int>::const_reverse_iterator crit = clt.rbegin();
    while (crit != clt.rend()) {
        cout << *crit << " ";  // 预期输出：500 400 300 200 100
        ++crit;
    }
    cout << endl;

    // 4. 双向迭代器特性测试（不支持随机访问）
    cout << "list反向迭代器（双向迭代器，不支持+/-操作）：";
    rit = lt.rbegin();
    ++rit;  // 支持自增
    --rit;  // 支持自减
    cout << *rit << " ";  // 预期：100
    cout << endl;

    // 5. 边界条件测试
    list<int> empty_lt;
    cout << "空list反向遍历：";
    rit = empty_lt.rbegin();
    while (rit != empty_lt.rend()) {
        cout << *rit << " ";  // 无输出
        ++rit;
    }
    cout << "（无元素）" << endl;

    cout << "===============================================================" << endl << endl;
}

int main() {
    test_vector_reverse_iterator();
    test_list_reverse_iterator();
    return 0;
}

4.2 测试结果与分析

编译并运行测试代码，输出如下：

===================== 测试vector反向迭代器 =====================
vector原始数据：1 2 3 4 5 
vector反向遍历（rbegin() -> rend()）：5 4 3 2 1 
反向迭代器修改元素（所有元素+10）：11 12 13 14 15 
const vector反向遍历：50 40 30 20 10 
反向迭代器随机访问：rit[0] = 15 rit[2] = 13 rit + 3 = 12 rit += 2 后：13 
空vector反向遍历：（无元素）
===============================================================

===================== 测试list反向迭代器 ======================
list原始数据：10 20 30 40 50 
list反向遍历（rbegin() -> rend()）：50 40 30 20 10 
反向迭代器修改元素（所有元素*2）：20 40 60 80 100 
const list反向遍历：500 400 300 200 100 
list反向迭代器（双向迭代器，不支持+/-操作）：100 
空list反向遍历：（无元素）
===============================================================

五、常见问题与注意事项

在使用和实现反向迭代器时，容易遇到以下问题，需要特别注意：

5.1 解引用操作的逻辑误区

反向迭代器的operator*访问的是current的前一个位置，这是最容易误解的点。如果直接返回*_it，会导致rbegin()访问end()（无效位置），从而触发未定义行为。

错误实现：

Ref operator*() const {
    return *_it;  // 错误：rbegin()的_it是end()，访问无效
}

正确实现：

Ref operator*() const {
    Iterator tmp = _it;
    return *--tmp;  // 先自减，再解引用
}

5.2 迭代器类别适配问题

反向迭代器的操作依赖于底层正向迭代器的类别：

随机访问迭代器（如 vector 的T*）：支持所有操作（+、-、[]等）。
双向迭代器（如 list 的ListIterator）：仅支持++、--、*、->，不支持算术运算。
前向迭代器 / 输入迭代器：不支持反向迭代器（因为反向迭代器需要--操作）。

如果将反向迭代器用于前向迭代器（如 forward_list 的迭代器），会导致编译错误，因为前向迭代器没有--操作。

5.3 const 与非 const 反向迭代器的转换

非 const 反向迭代器可以隐式转换为 const 反向迭代器，但 const 反向迭代器不能转换为非 const 反向迭代器。这与正向迭代器的 const 转换规则一致。

示例如下：

vector<int> v = {1,2,3};
vector<int>::reverse_iterator rit = v.rbegin();
vector<int>::const_reverse_iterator crit = rit;  // 允许：非const→const
// rit = crit;  // 错误：const→非const不允许

5.4 base () 方法的返回值

反向迭代器的base()方法返回底层的正向迭代器，但其返回的迭代器位置与反向迭代器的当前位置并非直接对应：

对于反向迭代器rit，rit.base()指向的是*rit的下一个位置。
例如，rbegin().base() == end()，*rbegin() == *(end() - 1)。

示例如下：

vector<int> v = {1,2,3,4};
vector<int>::reverse_iterator rit = v.rbegin();  // rit.base() = v.end()
cout << *rit << endl;  // 输出4，对应v[3]
cout << *(rit.base() - 1) << endl;  // 输出4，与*rit等价

5.5 与 STL 标准的兼容性

我们实现的反向迭代器完全遵循 STL 标准，因此可以与 STL 的算法配合使用。例如，使用std::reverse算法反转容器，或使用std::for_each遍历反向迭代器区间：

#include <algorithm>

vector<int> v = {1,2,3,4,5};
// 使用std::for_each遍历反向迭代器区间
std::for_each(v.rbegin(), v.rend(), [](int val) {
    cout << val << " ";  // 输出：5 4 3 2 1
});

总结

未来，我们可以进一步扩展反向迭代器的功能，例如支持迭代器的距离计算（operator-）、比较运算符（operator<、operator<=等），或实现更复杂的迭代器适配器（如插入迭代器、流迭代器）。深入理解迭代器的设计与实现，是提升 C++ 编程能力的重要途径，也是通往 STL 底层源码的关键一步。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-11-03，如有侵权请联系 cloudcommunity@tencent.com 删除

遍历