迭代器是STL的核心组件之一，是连接容器和算法的桥梁，通过提供统一的接口屏蔽不同容器底层数据结构的差异，使得算法能够独立于具体容器类型工作。

其实迭代器就是一种指针，模拟了指针的一些行为，可以解引用或者++移动，同时适用于各类容器。

迭代器的核心作用

迭代器的最主要的作用有三个,分别是：

1、统一接口：

不管底层的容器是数组、链表还是树等，迭代器提供的是统一的一种遍历方式，不会根据底层容器的不同而发生变化。

2、支持算法泛化：

STL提供的一些算法，比如std::sort,std::find通过迭代器去操作底层容器中的元素，而不需要关心容器的具体类型

3、隔离底层容器的细节：

在使用算法时不需要了解底层容器的实现细节，只要迭代器可以访问元素即可

迭代器的分类

迭代器根据功能从弱到强一共分为5类，具体如下表所示：

迭代器类型	核心操作	对应的容器
输入迭代器	单向移动，只能++；可以== !=比较；支持解引用 *it（只读访问）	istream_iterator（输入流迭代器）
输出迭代器	单向移动，只能写（*it = val赋值）；元素只能被写入一次	ostream_iterator（输出流迭代器）
前向迭代器	支持读写访问，单向访问，可重复遍历	forward_list、unordered_set/map
双向迭代器	支持读写访问；双向移动（++it/--it），可以重复遍历	list、set/map、multiset/multimap
随机访问迭代器	读写访问；支持双向迭代器所有操作 + 随机访问（it + n/it - n）、下标访问（it[n]）、大小比较（</>/<=/>=）。	vector、deque、array、原生数组指针

这里类型越强的迭代器可以兼容弱类型的迭代器操作。

迭代器的基本操作和接口

迭代器都支持的基础操作如下表：

操作	含义	支持的迭代器类型
*it	解引用，获取迭代器指向的元素	除了输出迭代器都支持读，输出迭代器支持写
it->xxxmember	访问元素的成员，等价于(*it).member	所有读写迭代器都支持
++it	前置递增	所有迭代器
it++	后置递增	所有迭代器
--it	前置递减	双向及以上的迭代器支持
it--	后置递减	双向及以上的迭代器支持
it1 == it2	判断两个迭代器是否指向同一位置	所有迭代器
it1 != it2	判断两个迭代器是否指向不同位置	所有迭代器

其中随机访问迭代器作为类型最高的迭代器，还额外支持了

• it + n / it - n，向前或者向后移动n个元素，
• it += n/it -= n：移动 n 个位置并赋值
• it[n]：访问迭代器后第 n 个元素（等价于*(it + n)）
• it1 - it2：计算两个迭代器之间的元素个数（返回difference_type）
• it1 < it2/it1 > it2等：比较位置先后

首迭代器 begin():指向容器的第一个元素的迭代器

尾迭代器end():指向容器的最后一个元素的下一个位置的迭代器，一般都不指向任何元素，标记范围结束

反向迭代器rbegin()/rend():逆向遍历容器中的元素

迭代器失效问题

当迭代器底层的容器的数据结构被破坏，常见的有插入、删除元素时，可能导致迭代器失效，这里的失效指的是这个迭代器指向了错误的位置或者已经被释放的空间，造成未定义行为等。

所以不同类型的容器迭代器失效问题的分析其实原理都是一样的，这里就不一一列举了，核心要点有：

• 插入时如果触发扩容，则全部迭代器失效（因为都是指向旧内存空间，现在扩容有了新的空间）
• 删除时，一般来说删除位置之后的元素迭代器会失效

当然我们还是应该具体问题具体分析，这里不做过多的探讨。

部分实现

1、istream_iterator

istream_iterator是输入迭代器中的一种，用于从输入流中读取数据。

成员变量

template<typename T, typename Distance = ptrdiff_t>
class istream_iterator {
    public:
    
    private:
        std::istream* stream_;
        T value_;
}

迭代器的类型定义

using iterator_category = input_iterator_tag;       // 标记为输入迭代器
using value_type = T;                               // 元素类型
using difference_type = Distance;                   
using pointer = const T*;                           // 常量指针
using reference = const T&;                         // 常量引用

构造函数

istream_iterator() : stream_(nullptr){}         // 默认构造函数：创建“尾后迭代器”（代表输入结束）
// 从输入流构造：绑定流并读取第一个元素
istream_iterator(std::istream& is) : stream_(&is){ ++*this;}

解引用

reference operator*() const {
    return value_;
}
​
pointer operator->() const {
    return &value_;
}

前置递增和后置递增

istream_iterator &operator++() {
    if (stream_ && !(*stream_ >> value_)) {
        stream_ = nullptr;
    }
    return *this;
}
​
istream_iterator operator++(int) {
    istream_iterator tmp = *this;
    ++*this;
    return tmp;
}

比较操作

friend bool operator==(const istream_iterator& lhs, const istream_iterator& rhs) {
    return lhs.stream_ == rhs.stream_;
}
​
friend bool operator!=(const istream_iterator &lhs, const istream_iterator &rhs) {
    return !(lhs == rhs);
}

2、ostream_iterator

ostream_iterator是输出迭代器的一种，以下是实现过程

template<typename T, typename charT = char, typename Traits = std::char_traits<charT>>
class ostream_iterator {
public:
    using iterator_category = output_iterator_tag;
    using value_type = void;
    using difference_type = ptrdiff_t;
    using pointer = void;
    using reference = void;
​
    ostream_iterator(std::ostream &os) : stream_(&os), delimiter_(nullptr) {}
​
    ostream_iterator(std::ostream &os, const charT *delimiter) : stream_(&os), delimiter_(delimiter) {}
​
    /// 进行输入
    ostream_iterator &operator=(const T &value) {
        *stream_ << value;
        if (delimiter_) {
            *stream_ << delimiter_;
        }
        return *this;
    }
​
    ostream_iterator &operator*() { return *this; }
​
    ostream_iterator &operator++() { return *this; }
​
    ostream_iterator &operator++(int) { return *this; }
​
​
private:
    std::ostream *stream_;     /// 输出流
    const charT *delimiter_;    /// 输出内容
};

3、advance_

根据迭代器的类型（如input、bidirectional、random access）对迭代器进行“前进”或“后退”的操作

如果是 input_iterator_tag 类型的迭代器（单向，只支持 ++），就只能通过不断地 ++it 来前进

template<typename InputIterator>
inline void advance_(InputIterator& it, iterator_difference_t<InputIterator> n, input_iterator_tag) {
    while (n--) {
        ++it;
    }
}
​

如果是BidirectionalIterator实现,支持前进（++）和后退（–）的迭代器

template<typename BidirectionIterator>
inline void advance_(BidirectionIterator& it, iterator_difference_t<BidirectionIterator> n, bidirectional_iterator_tag) {
    if (n > 0) {
        while (n--) {
            ++it;
        }
    } else {
        while (n++)  {
            --it;
        }
    }
}

如果是随机访问迭代器，支持 it += n 运算，这种操作效率远高于多次++ 或 --

template<typename RandomAccessIterator>
inline void advance_(RandomAccessIterator& it, iterator_difference_t<RandomAccessIterator> n, random_access_iterator_tag) {
    it += n;
}

调用以上标签的主函数,通过terator_catorgory_t<Iter> 来获取对应的标签类型

template<typename InputIterator>
inline void advance(InputIterator& it, iterator_difference_t<InputIterator> n) {
    advance_(it, n, iterator_category_t<InputIterator>());
}