Chapter 12 Iterators¶

What Is an Iterator

迭代器（Iterator）：提供按顺序访问容器元素的方法，不暴露底层容器实现细节，是对指针的一般化
迭代器把容器和算法连接起来，若没有迭代器，\(N\) 个算法配 \(M\) 种数据结构通常要写 \(N*M\) 套实现
GoF 对 iterator 的定义：在不暴露聚合对象内部表示的前提下，顺序访问其元素。

1 Generic Algorithms with Iterators¶

泛型 find

template <class InputIterator, class T>
InputIterator find(InputIterator first,
                   InputIterator last,
                   const T& value) {
    while (first != last && *first != value) {
        ++first;
    }
    return first;
}

可同时用于不同容器

vector<int> vecTemp;
list<double> listTemp;

if (find(vecTemp.begin(), vecTemp.end(), 3) == vecTemp.end())
    cout << "3 not found in vecTemp" << endl;

if (find(listTemp.begin(), listTemp.end(), 4) == listTemp.end())
    cout << "4 not found in listTemp" << endl;

迭代器是 C++ STL 中容器与算法之间的统一接口，支持以下运算符：

++：实现顺序遍历，从当前元素移动到下一个
*：解引用，获取迭代器指向的元素内容
通常还会配合 ->

重载 * 和 ->：类似 auto_ptr 的写法

// 用模板支持托管任意类型的指针
template<class T>
class auto_ptr {
private:
    T* pointee;
public:
    // 重载 *：返回托管对象的引用，实现和普通指针一样的 *ptr 用法
    T& operator*()  { return *pointee; }
    // 重载 ->：返回托管对象的指针，实现和普通指针一样的 ptr->成员 用法
    T* operator->() { return pointee; }
};

2 Custom Iterator Example¶

链表节点与迭代器

定义链表节点类 ListItem（存储数据 + 指向下一个节点）

template<class T>
class ListItem {
public:
    // 成员函数：返回节点存储数据的引用（外部读写数据）
    T& val() { return _value; }
    // 成员函数：返回当前节点的下一个节点指针
    ListItem* next() { return _next; }
private:
    T _value;           // 私有成员：存储T类型的实际数据
    ListItem<T>* _next; // 私有成员：指针，指向链表中的下一个节点
};

定义链表迭代器类 ListIter（专门遍历链表的迭代器）

template<class T>
class ListIter {
    ListItem<T>* ptr; // 私有成员：迭代器核心，指向当前链表节点的指针
public:
    // 构造函数：传入节点指针初始化迭代器，默认值为空指针
    ListIter(ListItem<T>* p = 0) : ptr(p) {}

    // 重载 前置自增运算符 ++it（迭代器核心：移动到下一个元素）
    ListIter<T>& operator++() {
        ptr = ptr->next();
        return *this;
    }

    // 重载 == 运算符：判断两个迭代器是否相等（比较指向的节点地址）
    bool operator==(const ListIter& i) const {
        return ptr == i.ptr;
    }

    // 重载 解引用运算符 *（迭代器核心：获取当前指向的元素）
    T& operator*() { return ptr->val(); }

    // 重载 箭头运算符 ->（迭代器类指针用法：访问元素成员）
    T* operator->() { return &(**this); }
};

使用自定义迭代器

List<int> myList;
// ... insert elements

ListIter<int> begin = myList.begin();
ListIter<int> end = myList.end();

ListIter<int> iter = find(begin, end, 3);
if (iter == end) {
    cout << "not found" << endl;
}

3 Associated Types¶

有时算法除了需要 *iter 的值，还需要知道更多与迭代器关联的类型信息，例如值类型、差值类型、迭代器类别等。

通过包装函数推导类型

template <class I, class T>
void func_impl(I iter, T& v) {
    T tmp;
    tmp = *iter;
}

template <class I>
void func(I iter) {
    func_impl(iter, *iter);
}

在迭代器里嵌入类型别名

template <class T>
struct myIter {
    typedef T value_type;
    T* ptr;
    myIter(T* p = 0) : ptr(p) {}
    T& operator*() { return *ptr; }
};

通过 typename I::value_type 取出关联类型

template <class I>
typename I::value_type func(I iter) {
    return *iter;
}

4 `iterator_traits`¶

typedef 对自定义迭代器可行，但对原生指针迭代器（如 int*、double*）无能为力，而原生指针又恰好是 STL 中最常见的一类随机访问迭代器，因此引入 iterator_traits。

示例

template <class I>
// 迭代器萃取器，用于提取迭代器的关联类型）
struct iterator_traits {
    typedef typename I::value_type value_type;
};

template <class I>
typename iterator_traits<I>::value_type func(I iter) {
    // 解引用迭代器，返回指向的元素值
    return *iter;
}

Template Specialization

Primary template

// 模板的通用基础版本，定义了模板的原始形式
template<class T1, class T2, int I>
class A { ... };

Explicit (full) template specialization

// 为模板的所有参数都指定具体值，提供专属实现
template<>
class A<int, double, 5> { ... };

Partial template specialization

// 仅指定部分模板参数，剩余参数仍为泛型，提供部分场景的专属实现
template<class T2>
class A<int, T2, 3> { ... };

iterator_traits with Specialization

通用版本

template <class I>
class iterator_traits {
public:
    typedef typename I::value_type value_type;
    typedef typename I::pointer_type pointer_type;
    // ...
};

对原生指针的偏特化

// 只匹配 T* 类型（原生指针）
template <class T>
class iterator_traits<T*> {
public:
    typedef T value_type;
    typedef T* pointer_type;
    // ...
};

// 只匹配 const T* 类型（常量指针）
template <class T>
class iterator_traits<const T*> {
public:
    typedef T value_type;
    typedef const T* pointer_type;
    // ...
};

The standard traits technique in STL

template<class I>
class iterator_traits
{
public:
    // 萃取迭代器的5个标准关联类型
    typedef typename I::iterator_category iterator_category;
    typedef typename I::value_type value_type;
    typedef typename I::difference_type difference_type;
    typedef typename I::pointer pointer;
    typedef typename I::reference reference;
    ......
};

5 Tag Dispatch for `advance`¶

Iterator Categories

ForwardIterator 比 InputIterator 能力更强
BidirectionalIterator 支持双向移动
RandomAccessIterator 支持跳跃访问和算术运算

不同类别对应不同实现

输入迭代器 InputIterator 专用 advance

template <class InputIterator, class Distance>
void advance_II(InputIterator& i, Distance n) {
    // 循环 n 次：每次迭代器自增，只能向前移动，不支持后退
    while (n--) ++i;
}

双向迭代器 BidirectionalIterator 专用 advance

template <class BidirectionalIterator, class Distance>
void advance_BI(BidirectionalIterator& i, Distance n) {
    // 步数 n 为正向前移动，为负向后移动
    if (n >= 0) while (n--) ++i;
    else while (n++) --i;
}

随机访问迭代器 RandomAccessIterator 专用 advance

template <class RandomAccessIterator, class Distance>
void advance_RAI(RandomAccessIterator& i, Distance n) {
    // 直接 += 步数，一步到位，无需循环，时间复杂度 O(1)
    i += n;
}

标签类型

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 {};

内部调度

template <class InputIterator, class Distance>
inline void __advance(InputIterator& i, Distance n, input_iterator_tag) {
    while (n--) ++i;
}

template <class BidirectionalIterator, class Distance>
inline void __advance(BidirectionalIterator& i, Distance n, bidirectional_iterator_tag) {
    if (n >= 0) while (n--) ++i;
    else while (n++) --i;
}

template <class RandomAccessIterator, class Distance>
inline void __advance(RandomAccessIterator& i, Distance n, random_access_iterator_tag) {
    i += n;
}

对外统一接口

template <class Iterator, class Distance>
inline void advance(Iterator& i, Distance n) {
    __advance(i, n, typename iterator_traits<Iterator>::iterator_category());
}

对原生指针做 iterator_traits<T*> 特化后，可以自动归类为 random_access_iterator_tag
forward_iterator_tag 可通过继承链隐式转换到 input_iterator_tag

6 `distance`¶

输入迭代器版本

template <class InputIterator>
inline typename iterator_traits<InputIterator>::difference_type
__distance(InputIterator first, InputIterator last, input_iterator_tag) {
    typename iterator_traits<InputIterator>::difference_type n = 0;
    while (first != last) {
        ++first;
        ++n;
    }
    return n;
}

随机访问版本

template <class RandomAccessIterator>
inline typename iterator_traits<RandomAccessIterator>::difference_type
__distance(RandomAccessIterator first, RandomAccessIterator last, random_access_iterator_tag) {
    return last - first;
}

统一封装

template <class Iterator>
inline typename iterator_traits<Iterator>::difference_type
distance(Iterator first, Iterator last) {
    return __distance(first, last,
        typename iterator_traits<Iterator>::iterator_category());
}