迭代器模式

英文: Iterator pattern.

描述

迭代器类似自定义的指针, 拥有和指针类似的使用方式, 但却允许不同数据结构以相同的方法进行遍历.

以数组和链表为例, 数组的元素在内存中是紧密相连的, 但链表在内存中不是紧密相连的, 因此两者获取下一个元素的方法不同. 迭代器则用于封装这部分代码, 使不同数据结构可以使用相同的方法进行遍历.

下面简单实现了一个数组并提供了迭代器. 由于此时迭代器的行为和指针最接近, 所以代码最简单易懂.

#include <cstddef>
#include <iostream>
#include <numeric>

// 堆上的数组
class Array {
public:
    using value_type = int;
    class iterator {
    public:
        using value_type = Array::value_type; // 提供类系信息, 供 STL 算法使用

        iterator(value_type* ptr) : ptr(ptr) {}

        // 模拟指针的(部分)操作
        bool        operator==(const iterator& rhs) const { return ptr == rhs.ptr; }
        bool        operator!=(const iterator& rhs) const { return !(*this == rhs); }
        iterator&   operator++() { ptr++; return *this; }
        iterator    operator++(int) { auto t = *this; ++(*this); return t; }
        value_type& operator*() { return *ptr; }

    private:
        value_type* ptr;
    };

    explicit Array(std::size_t size)
        : data(new value_type[size * sizeof(value_type)]), size(size)
    {}

    virtual ~Array() { delete[] data; }

    iterator begin() { return iterator(data); }
    iterator end() { return iterator(data + size); }

private:
    value_type* data;
    std::size_t size;
};

int main() {
    Array arr(5);

    std::iota(arr.begin(), arr.end(), 0); // 使用 C++ STL 算法

    // 当作指针使用
    for(auto it = arr.begin(); it != arr.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << '\n';

    // 使用 C++ for-each
    for(auto it : arr) {
        std::cout << it << " ";
    }
    std::cout << '\n';

    return 0;
}

执行结果:

0 1 2 3 4 
0 1 2 3 4

可见实现了迭代器不仅能使遍历方法保持一致, 而且还能配合 C++ 的 STL 和 for-each 使用.

上面容器使用的数据结构是数组, 但可以换成链表等其他数据结构.

STL 算法

但上方这种完全自定义的迭代器却不能很好的适应 STL 算法.
下面提供一种迭代器算法的简单实现:

template <typename Iter>
auto distance(Iter first, Iter last) {
    typename Iter::value_type result = 0;
    for(; first != last; ++first) {
        ++result;
    }
    return result;
}

上面的代码即适用于数组, 又适用于链表等其他数据结构实现的容器. 使用迭代器进行遍历时, STL 算法无需在意容器的内部实现.
但若用在数组等结构上会存在效率问题, 因为数组元素紧密相连的特点, 实现 distance 有更加简单/高效的算法. 可以根据数据结构的特性对其迭代器进行分类, 以便采用合适的算法.
下面是 std::distance 的一种实现:

template<std::input_or_output_iterator Iter>
constexpr std::iter_difference_t<Iter> distance(Iter first, Iter last) {
    if constexpr(std::random_access_iterator<Iter>) {
        return last - first;
    } else {
        std::iter_difference_t<Iter> result{};
        for (; first != last; ++first)
            ++result;
        return result;
    }
}

可以看出改算法根据迭代器的类型选择了合适的具体算法.

参见

• std::iterator is deprecated: Why, What It Was, and What to Use Instead - Fluent C++ (fluentcpp.com).

评论