C/C++杂谈：迭代器小结

月踏

一、简介

迭代器又称Iterator，有时也叫Cursor，是设计模式的一种，在标准库中用的非常普遍，常见的容器都实现了相应的迭代器，在不需要暴露容器内部表示的情况下，它提供了一组统一的接口可以顺序访问一个容器中的各个元素。

这种设计模式的关键思想是把对容器的访问和遍历从容器中分离出来放入一个单独的Iterator类中，Iterator需要保证能够提供类似下面几个接口对应的功能：

First：获取第一个元素
CurrentItem：获取当前元素
Next：获取下一个元素
IsDone：判断是否遍历完容器中所有元素

使用Iterator的好处非常明显，它既可以统一不同类型容器的访问接口，例如标准库容器提供的begin/end接口，又可以方便的使用不同的遍历算法来遍历容器中的元素，例如树形数据结构的遍历，可以分别抽象出前序、中序、后序遍历的迭代器。

二、分析标准库vector的迭代器实现

下面这段代码相信大家都用过：

// v is a vector object
for(auto it=v.begin(); it!=v.end(); it++) { ... }

这里的begin和end都会返回一个迭代器，通过运算符的重载，就可以实现前面第一节提到的四个必须功能：

First：通过begin()来实现
CurrentItem：通过对当前的it解引用实现
Next：通过operator++这个运算符重载来实现
IsDone：通过operator!=这个运算符重载来实现

下面展示标准库中 vector的一部分begin和end的相关代码实现：

template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
class vector : protected _Vector_base<_Tp, _Alloc> {
public:
  typedef __gnu_cxx::__normal_iterator<pointer, vector> iterator;
  iterator begin() _GLIBCXX_NOEXCEPT { return iterator(this->_M_impl._M_start); }
  iterator end() _GLIBCXX_NOEXCEPT { return iterator(this->_M_impl._M_finish); }
};

vector继承自_Vector_base类，之所以用protected继承，应该是想表达has-a的语义，可以看到begin和end接口返回了一个iterator对象，它是__normal_iterator<pointer, vector>的别名，在深入看__normal_iterator之前，需要看一下vector的数据成员，因为iterator对象是通过vector的数据成员构造的。

上面代码中展示了两个vector的数据成员，即_M_start和_M_finish，其实总共有三个，定义在基类中，简化的基类代码如下：

template<typename _Tp, typename _Alloc>
struct _Vector_base {
  typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template rebind<_Tp>::other _Tp_alloc_type;
  typedef typename __gnu_cxx::__alloc_traits<_Tp_alloc_type>::pointer pointer;
  struct _Vector_impl_data {
    pointer _M_start;
    pointer _M_finish;
    pointer _M_end_of_storage;
  struct _Vector_impl : public _Tp_alloc_type, public _Vector_impl_data {};
  _Vector_impl _M_impl;
};

_Vector_base 中有很多内部类，数据成员主要包在_Vector_impl_data中，具体的实现都封装在_Vector_impl中，本文只关注迭代器，这里大家对vector的实现有个大概的印象就好，就不细看具体的内容了。

了解了vector的主要数据成员后，继续看 __normal_iterator ，下面是标准库中具体的实现，只把迭代器中最主要的接口列了出来：

template<typename _Iterator, typename _Container>
class __normal_iterator {
protected:
  _Iterator _M_current;
  typedef std::iterator_traits<_Iterator> __traits_type;
public:
  typedef _Iterator iterator_type;
  typedef typename __traits_type::reference reference;
  explicit __normal_iterator(const _Iterator& __i) : _M_current(__i) { }
  reference operator*() const { return *_M_current; }
  pointer operator->() const { return _M_current; }
  __normal_iterator& operator++() {
    ++_M_current;
    return *this;
  __normal_iterator operator++(int) { return __normal_iterator(_M_current++); }
  __normal_iterator& operator--() {
    --_M_current;
    return *this;
  __normal_iterator operator--(int) { return __normal_iterator(_M_current--); }
  __normal_iterator& operator+=(difference_type __n) { _M_current += __n; return *this; }
  __normal_iterator& operator-=(difference_type __n) { _M_current -= __n; return *this; }
};

从上面可以看出，__normal_iterator的主要数据成员_M_current，在vector的实例中，它是一个指针，初始值可能来自vector中的_M_start和_M_finish，它提供的接口支持指针自加、自减、解引用等。

这里还有一点需要注意的是，因为vector是一种随机访问容器，所以相应的迭代器中需要提供operator+=(int n)和operator-=(int 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 { };

从名字基本就能看到这些迭代器的用途，其中最强大的是随机访问迭代器，它用于vector、string、array等随机访问容器中。

三、动手写一个简单vector和相应迭代器

分析了迭代器的用途以及标准库vector的实现，自己来动手做一个乞丐版的vector和相应的iterator，其中vector的实现重点如下：

内存分配器使用标准库的std::allocator，这是标准库中容器的默认内存分配器，功能很强大，以后有时间专门来总结一下
使用三个指针类型的数据成员start_、finish_、end_of_storage_来分别指向vector的第一个元素、最后一个元素的下一个元素、vector存储空间的结尾
仅仅提供push_back和pop_back来向vector中放入元素和删除元素
提供empty/size/capacity/at/operator[]等基本接口来操作vector
提供begin和end两个迭代器接口来访问vector元素

有一个地方需要特别注意，在向vector中push_back元素的时候，如果存储空间不够，需要使用std::allocator来分配空间，下面是vector的主要实现：

#include "vector_iterator.hpp"
template <typename T, typename Alloc = std::allocator<T>>
class SimpleVector {
 public:
  SimpleVector(const Alloc& alloc = Alloc())
      : start_(nullptr),
        finish_(nullptr),
        end_of_storage_(nullptr),
        allocator_(alloc) {}
  ~SimpleVector() = default;
  void push_back(T&& value) {
    if (end_of_storage_ == nullptr || finish_ == end_of_storage_) {
      resize();
    allocator_.construct(finish_, std::forward<T>(value));
    finish_++;
  void pop_back() {
    if (empty()) return;
    finish_--;
    allocator_.destroy(finish_);
  bool empty() const { return start_ == finish_; }
  int size() const { return finish_ - start_; }
  int capacity() const { return end_of_storage_ - start_; }
  T& operator[](int idx) { return start_[idx]; }
  const T& operator[](int idx) const { return start_[idx]; }
  T& at(int idx) {
    CHECK(idx < size());
    return start_[idx];
  const T& at(int idx) const {
    CHECK(idx < size());
    return start_[idx];
  VectorIterator<T> begin() { return VectorIterator<T>(start_); }
  VectorIterator<T> end() { return VectorIterator<T>(finish_); }
  ConstVectorIterator<T> begin() const {
    return ConstVectorIterator<T>(start_);
  ConstVectorIterator<T> end() const { return ConstVectorIterator<T>(finish_); }
 private:
  void resize() {
    if (start_ == nullptr) {
      start_ = allocator_.allocate(8);
      finish_ = start_;
      end_of_storage_ = start_ + 8;
    } else {
      auto n = size();
      T* ptmp = allocator_.allocate(2 * n);
      for (auto i = 0; i < n; ++i) {
        allocator_.construct(ptmp + i, start_[i]);
        allocator_.destroy(start_ + i);
      allocator_.deallocate(start_, n);
      start_ = ptmp;
      finish_ = ptmp + n;
      end_of_storage_ = ptmp + 2 * n;
 private:
  T* start_;
  T* finish_;
  T* end_of_storage_;
  Alloc allocator_;
};

再看对应的迭代器的实现，实现了最基本的自加、自减、解引用、判等的功能，其中通过实际的代码还可以看到左侧自加和右侧自加的实际区别：

template <typename T>
class VectorIterator {
 public:
  VectorIterator(T* ptr) : ptr_(ptr) {}
  VectorIterator& operator++() {
    ptr_++;
    return *this;
  VectorIterator operator++(int) {
    VectorIterator tmp(ptr_);
    ptr_++;
    return tmp;
  VectorIterator& operator--() {
    ptr_--;
    return *this;
  VectorIterator operator--(int) {
    VectorIterator tmp(ptr_);
    ptr_--;
    return tmp;
  bool operator==(const VectorIterator& it) { return ptr_ == it.ptr_; }
  bool operator!=(const VectorIterator& it) { return !operator==(it); }
  T& operator*() { return *ptr_; }