迭代器模式

英文: 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).

评论