C++ Iterator 迭代器

迭代器简介

迭代器（Iterator）是一种抽象设计理念，通过迭代器可以在不了解容器内部原理的情况下遍历容器。迭代器的功能：访问容器对象的元素

STL中迭代器的一个重要作用就是作为容器与STL算法的连接，容器提供迭代器的接口，同一套算法代码可以用在不同的容器中。所有标准库容器都可以使用迭代器，部分支持使用下标运算符。（String对象不属于容器）

迭代器是指针的泛化，提供一种行为类似指针的类对非数组数据结构进行遍历，这允许程序员以相同的方式处理不同的数据结构（容器）

迭代器的类别

首先介绍五种迭代器类别：

它们的基础关系如下图所示：

迭代器的操作

每种迭代器均可进行包括表中前一种迭代器可进行的操作。（见参考资料[3]）

所有迭代器：

输入迭代器：

输出迭代器：

正向迭代器：

双向迭代器：

随机迭代器：

容器支持的迭代器

只有顺序容器和关联容器支持迭代器遍历，容器适配器不支持：

迭代器的基本使用

迭代器的类型

一般来说不需要知道迭代器的准确类型，标准库使用iterator来表示迭代器的类型（对象是常量只能用const前缀的，变量则都行）

迭代器按照定义方式分成以下四种：

1. 正向迭代器，定义方法如下：

容器类名::iterator 迭代器名;

2. 常量正向迭代器，定义方法如下：

容器类名::const_iterator 迭代器名;

3. 反向迭代器，定义方法如下：

容器类名::reverse_iterator 迭代器名;

4. 常量反向迭代器，定义方法如下：

容器类名::const_reverse_iterator 迭代器名;

begin和end方法

容器和string对象都有定义迭代器类型，同时拥有返回迭代器的成员函数。如：容器有成员函数begin和end：

• begin成员函数复制返回指向第一个元素的迭代器
• end成员函数返回指向容器尾元素的下一个位置的迭代器

对于常量对象，begin和end返回的是const_iterator，非常量返回iterator

为便于专门得到const_iterator类型，C++11提供了两个新函数：cbegin和cend

简单使用示例

正向反向遍历vector容器：

int main()
{
    std::vector<int> scores = { 1,2,3,4,5,6,7,8,9,10};

    // 正向遍历vector容器
    for (auto i = scores.begin(); i < scores.end(); i++)
    {
        std::cout << *i << " ";
    }
    std::cout << std::endl;
    // 1 2 3 4 5 6 7 8 9 10

    // 反向遍历vector容器
    for (auto i = scores.rbegin(); i < scores.rend(); i++)
    {
        std::cout << *i << " ";
    }
    std::cout << std::endl;
    // 10 9 8 7 6 5 4 3 2 1
    
    auto a = scores.begin();
    auto b = scores.rend();
    if (a == b.base()) {	// base方法用于将reverse_iterator转换成iterator
        std::cout << "begin == rend" << std::endl;
    }
    else {
        std::cout << "begin != rend" << std::endl;
    }
    return 0;
}

迭代器的辅助函数

STL有操作迭代器的三个函数模板：(均来自<algorithm>库)

• advance(p, n)：使迭代器 p 向前或向后移动 n 个元素。
• distance(p, q)：计算两个迭代器之间的距离，即迭代器 p 经过多少次 + + 操作后和迭代器 q 相等。如果调用时 p 已经指向 q 的后面，则这个函数会陷入死循环。
• iter_swap(p, q)：用于交换两个迭代器 p、q 指向的值。

使用案例

本段内容来自参考资料[5]

std::replace函数：

template <class _FwdIt, class _Ty>
_CONSTEXPR20 void replace(const _FwdIt _First, const _FwdIt _Last, const _Ty& _Oldval, const _Ty& _Newval) {
    // replace each matching _Oldval with _Newval
    _Adl_verify_range(_First, _Last);
    auto _UFirst      = _Get_unwrapped(_First);
    const auto _ULast = _Get_unwrapped(_Last);
    for (; _UFirst != _ULast; ++_UFirst) {
        if (*_UFirst == _Oldval) {
            *_UFirst = _Newval;
        }
    }
}

这段是我从VS2022里复制出来的，模板参数里两个类模板，看名字不难猜到前者这个_FwdIt指的是ForwardIterator前向迭代器，replace函数的功能遍历迭代器区间将旧值替换成新值

std::merge函数：

代码我直接从参考资料那里复制吧，VS里提取出来的看着没这个清晰

// merge，将两个有序序列进行合并，返回结果序列最后一个元素的下一个位置
// 版本1，operator<
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
                     InputIterator2 first2, InputIterator2 last2,
                     OutputIterator result)  {
    while (first1 != last1 && first2 != last2) {	// 输入的两组迭代器区间不相同
        if (*first1 < *first2) {					// 如果1的值小
            *result = *first1;						// 就保存到输出序列中的第一个
            ++first1;								// 迭代器1往后挪
        }
        else {
            *result = *first2;
            ++first2;
        }
        ++result;
    }
    // 将两个序列中剩余的元素拷贝到result中
    return copy(first1, last1, copy(first2, last2, result));
}

5个参数，两对迭代器区间加一个输出迭代器参数，功能是把两个序列进行升序合并，可见对迭代器的操作就像用指针一样

std::reverse函数：

一样，从参考资料那里copy了：

// reverse，将序列反转
// 不同迭代器类型会影响性能，双向迭代器或者随机访问迭代器
// 因此需要设计两层函数，通过tag来区分不同的迭代器类型

// 底层函数，双向迭代器的版本，只能使用自增和自减
template <class BidirectionalIterator>
void __reverse(BidirectionalIterator first, BidirectionalIterator last, bidirectional_iterator_tag) {
    --last;
    while (first != last) {
        swap(*first, *last);
        if (++first == last)
            return;
        --last;
    }
}

// 底层函数，随机访问迭代器的版本
template <class RandomAccessIterator>
void __reverse(RandomAccessIterator first, RandomAccessIterator last, random_access_iterator_tag) {
    // 修正last
    --last;
    // 随机访问迭代器的好处就是可以直接比较大小
    while (first < last) {
        swap(*first, *last);
        ++first;
        --last;
    }
}

// reverse对外接口
template <class BidirectionalIterator>
void reverse(BidirectionalIterator first, BidirectionalIterator last) {
    // 萃取出迭代器的类型
    typedef typename iterator_traits<BidirectionalIterator>::iterator_category iterator_category;
    // 根据参数类型的不同调用不同版本的函数
    __reverse(first, last, iterator_category());
}

迭代器的实现

本段内容来自参考资料[5]

迭代器的实现

迭代器内部通过定义一个tag结构体来设定它的迭代器类别，同时在内部实现该迭代器支持的操作，在使用的时候通过iterator_traits萃取出迭代器内部定义的tag，来区分不同迭代器，调用不同迭代器版本的底层函数（就像上面的reverse函数）

五种迭代器对应的tag：

// 五种迭代器类别对应的tag
struct input_iterator_tag {};       // 只读迭代器
struct output_iterator_tag {};      // 只写迭代器
struct forward_iterator_tag : public input_iterator_tag {};     // 前向迭代器
struct bidirectional_iterator_tag : public forward_iterator_tag{};      // 双向迭代器
struct random_access_iterator_tag : public bidirectional_iterator_tag{};// 随机访问迭代器，支持指针的所有运算操作

按照STL架构，迭代器需要提供五种类型用于traits萃取

// 具体的某个迭代器实现
// 任何迭代器都应该提供五种类型，以利于traits萃取，否则便是自别于整个STL架构，可能无法与其他STL组件顺利搭配
// 所以STL提供了一个iterators class，如果每个新设计的迭代器都继承自它，则可保证符合STL所需之规范
// 因为主要是为了实现萃取五种类型的功能，所以迭代器中只有这几种类型的信息
// Category被定义为迭代器类型，实参应该为上面五个tag的其中一个
template <class Category, class T, class Distance = ptrdiff_t, class Pointer = T*, class Reference = T&>
struct iterator {
    typedef Category    iterator_category;
    typedef T           value_type;
    typedef Distance    difference_type;
    typedef Pointer     pointer;
    typedef Reference   reference;
};

traits萃取迭代器中的类型信息：

// traits相当于萃取机，通过traits可以获得迭代器中的五种类型
// 一般类型的traits，获取迭代器中的类型信息
template <class Iterator>
struct iterator_traits {
    typedef typename Iterator::iterator_category iterator_category;     // 普通类型的迭代器类型，类型值为五个迭代器tag结构体类型的其中一个
    typedef typename Iterator::value_type        value_type;            // 普通类型的类型
    typedef typename Iterator::difference_type   difference_type;       // 普通类型的迭代器中的指针差值类型
    typedef typename Iterator::pointer           pointer;               // 普通类型的迭代器中的指针类型
    typedef typename Iterator::reference         reference;             // 普通类型的迭代器中的引用类型
};

特化traits：

// 针对原生指针类型设计的traits偏特例化版本（特殊化）
// 原生指针也算是迭代器的一种
// 通过将模板参数设定为T*来进行模板参数特例化
// 表明只有模板参数为原生指针类型时，才会使用这个模板类
// 相当于将模板参数定为原生指针类型，所以五种类型不需根据迭代器中的信息就可以提前知道
// 也就是当T为原生指针类型时的五种类型
template <class T>
struct iterator_traits<T*> {
    typedef random_access_iterator_tag  iterator_category;	// 原生指针应该是支持随机访问的，所以tag是随机访问的tag
    typedef T                           value_type;
    typedef ptrdiff_t                   difference_type;
    typedef T*                          pointer;
    typedef T&                          reference;
};

list迭代器

下面是一个list迭代器，是一个双向迭代器，内部重载双向迭代器支持的运算符

template <class T, class Ref, class Ptr>
struct __list_iterator {
    typedef __list_iterator<T, T&, T*>      iterator;   // 迭代器类型
    typedef __list_iterator<T, Ref, Ptr>    self;       //

    typedef bidirectional_iterator_tag iterator_category;   // 迭代器的类型为双向迭代器。tag用于在调用一些底层函数时识别这个迭代器的类型
    typedef T value_type;               // 元素的类型
    typedef Ptr pointer;                // 元素的指针类型
    typedef Ref reference;              // 元素的引用类型
    typedef __list_node<T>* link_type;  // 指向节点的指针类型
    typedef size_t size_type;           // 元素数目的类型
    typedef ptrdiff_t difference_type;  // 迭代器差值的类型

    link_type node;     // 迭代器内部的指向节点的指针

    // 构造函数
    __list_iterator() = default;
    __list_iterator(link_type x) : node(x) {}
    __list_iterator(const iterator& x) : node(x.node) {}

    // 接着重载运算符
    bool operator==(const self& x) const { return node == x.node; }
    bool operator!=(const self& x) const { return node != x.node; }

    // 解引用，取数据值
    reference operator*() const { return node->data; }
    // 成员存取运算子的标准做法
    pointer operator->() const { return &(operator*()); }

    // 最后是自增自减
    // 前缀自增
    // 返回的是当前对象(*this)，所以可以返回引用
    self& operator++() {
        // node指向下一个节点
        node = (link_type)(node->next);
        return *this;
    }
    // 后缀自增
    // 返回的是临时对象，所以不能返回引用
    self operator++(int) {
        self tmp = *this;
//        this->node = (link_type)(node->next);
        ++*this;
        return tmp;

    }

    // 前缀自减
    self& operator--() {
        node = (link_type)(node->prev);
        return *this;
    }

    // 后缀自减
    self operator--(int) {
        self tmp = *this;
        --*this;
        return tmp;
    }
};

参考资料

• [1] C++标准模板库(STL)迭代器的原理与实现_wutao02的博客-CSDN博客_stl迭代器
• [2] C++：迭代器 - 知乎 (zhihu.com)
• [3] 【C++】：STL迭代器使用详解，很好很详细_seen_in_hw的博客-CSDN博客_c++ stl 迭代器
• [4] C++迭代器（STL迭代器）iterator详解 (biancheng.net)
• [5] C++ STL 迭代器Iterator、五种迭代器类别_Johnsonjjj的博客-CSDN博客_bidirectional_iterator