迭代器模式
英文: 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;
}
执行结果:
可见实现了迭代器不仅能使遍历方法保持一致, 而且还能配合 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;
}
}
可以看出改算法根据迭代器的类型选择了合适的具体算法.