迭代器剖析

标签：node typedef 迭代 iterator 剖析 type 指针

对于迭代器，我们要有以下两点认识：

迭代器可以理解为泛化的指针，可以执行 *iter（解引用）、iter++（正向迭代器）、iter--（双向迭代器）、iter+=i（随机访问迭代器）、iter->method() 等操作，这与指针的使用非常类似；
迭代器是容器与算法之间的桥梁，迭代器让算法忽略了容器底层的数据结构，使用迭代器可以获知容器元素的类型、完成对容器元素的访问与遍历。

从指针的角度理解迭代器

从底层结构上来看，所有容器的数据结构可以分为顺序表（连续内存）和链表（不连续内存），前者如 array、vector，而它们的迭代器本质上就是对其指针的一层封装；后者如 list、forward_list，它们的迭代器无法单单用指针完成，因而必须创建对应的迭代器类，并重载*、++、--、->等运算符。

因此，我们分别以 vector 和 list 为例介绍迭代器。

vector 的迭代器

vector 的实现仅需要三个指针：start、finish、end_of_storage，其中 start 指向 vector 的第一个元素，finish 指向已使用 vector 的最后一个元素的下一个位置，end_of_storage 指向 vector 容量的最后一个元素的下一个元素。因此，在 32 位平台上，对 vector 做 sizeof，无论 vector 内部存储什么类型的元素，无论 vector 内部存储几个元素，其结构都是 3×4=12 字节。

在 SGI-STL V3.3中，vector中相关实现如下：

template <class _Tp, class _Alloc> 
class _Vector_base {
public:
  // ...
  _Vector_base(const _Alloc&)						// 创建一个空的分配器
    : _M_start(0), _M_finish(0), _M_end_of_storage(0) {}
  _Vector_base(size_t __n, const _Alloc&)			// 创建一个含有n个字节的分配器
      												// 此处的__n不是元素个数，而是经过计算的需要分配的字节数
    : _M_start(0), _M_finish(0), _M_end_of_storage(0) 
  {
    _M_start = _M_allocate(__n);					// start指针指向分配空间的开始
    _M_finish = _M_start;
    _M_end_of_storage = _M_start + __n;				// end_of_storage指向分配空间末尾的下一个位置
  }

  ~_Vector_base() { _M_deallocate(_M_start, _M_end_of_storage - _M_start); }

protected:
  _Tp* _M_start;				// start 指针
  _Tp* _M_finish;				// finish 指针
  _Tp* _M_end_of_storage;		// end_of_storage 指针
    
  // ...
};

template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class vector : protected _Vector_base<_Tp, _Alloc> 
{
  // ...
public:
  typedef _Tp value_type;
  typedef value_type* iterator;					// iterator类型即_Tp*类型
  typedef value_type& reference;
  typedef size_t size_type;

public:
  iterator begin() { return _M_start; }			// begin()即返回start指针
  iterator end() { return _M_finish; }			// end()即返回finish指针

  size_type size() const						// 返回容器内元素个数
    { return size_type(end() - begin()); }
  size_type max_size() const					// 返回容器内所能存储的最大元素个数
    { return size_type(-1) / sizeof(_Tp); }
  size_type capacity() const					// 返回容器的容量
    { return size_type(_M_end_of_storage - begin()); }
  bool empty() const							// 容器是否未空
    { return begin() == end(); }

  reference operator[](size_type __n) { return *(begin() + __n); }
    											// 返回 vector[n]
  
  // ...
}

从上述代码可知，vector 的迭代器类型为 _Tp* ，即指针类型；begin()、end()、size()、capacity()、empty() 等仅需对指针进行简单运算即可，另外也不需要对 *、++、--、->等运算符函数进行重载，因为指针本就支持这些操作。

list 的迭代器

list 是双向链表，其底层实现为环状双向链表，由于链表中每个结点的存储空间并不连续，因此并不能直接使用指针实现迭代器的功能。

list 的底层实现

首先我们看一下 list 的底层实现（gcc 2.95版本）：

list 为一个环状双向链表，在链表尾部有一个空白结点，以实现STL的前闭后开区间特性，即迭代器end()指向这个空白结点（最后一个位置的下一个位置）。在 list 类中，唯一一个数据成员是一个指向结点的指针，这个指针（即下图中的 node）就指向链表尾部的空白结点。因此，list的大小在 32 为平台上为 4 字节。

在创建 list 时，list 的构建函数会创建这个空白结点，并让 node 指针指向空白结点，并使自身成为环状链表（没有任何元素）。当链表中含有元素时，node 指向的空白结点的 next 指针指向链表中的第一个元素。因此，list.end() 即返回 node，list.begin() 即返回 node.next 。

template <class _Tp>
struct _List_node {						// 链表结点
  typedef void* _Void_pointer;
  _Void_pointer _M_next;				// next指针
  _Void_pointer _M_prev;				// prev指针
  _Tp _M_data;							// data
};

template <class _Tp, class _Alloc>
class _List_base						// list 的基类
{
public:
  // ...
  _List_base(const allocator_type&) {
    _M_node = _M_get_node();			// 分配一个结点
    _M_node->_M_next = _M_node;
    _M_node->_M_prev = _M_node;
  }
protected:
  _List_node<_Tp>* _M_get_node() { return _Alloc_type::allocate(1); }
  _List_node<_Tp>* _M_node;				// 唯一数据成员-指针，其类型为指向链表结点_List_node的指针
};

template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class list : protected _List_base<_Tp, _Alloc> {	// list模板类
	// 无任何成员变量
public:
  typedef _List_iterator<_Tp,_Tp&,_Tp*> iterator;	// list 的迭代器类型
  iterator begin() { return (_Node*)(_M_node->_M_next); }
  iterator end() { return _M_node; }
  bool empty() const { return _M_node->_M_next == _M_node; }
}

list 迭代器的实现

list 使用类实现其迭代器，而这个类本质上也只是对指针的包装，并重载了对应的函数。

template<class _Tp, class _Tp&, class _Tp*>
struct _List_iterator {
  // ...
  typedef _List_iterator<_Tp,_Tp&,_Tp*>             iterator;
  typedef _List_iterator<_Tp,_Tp&,_Tp*>             _Self;
  typedef _Tp value_type;
  typedef _Tp& pointer;
  typedef _Tp* reference;
  typedef _List_node<_Tp> _Node;

  _Node* _M_node;						// 唯一的数据成员-指向链表结点的指针

  // 重载操作符函数
  bool operator==(const _Self& __x) const { return _M_node == __x._M_node; }
  bool operator!=(const _Self& __x) const { return _M_node != __x._M_node; }
  
  reference operator*() const { return (*_M_node)._M_data; }
  pointer operator->() const { return &(operator*()); }
  _Self& operator++() { 				// ++指针，即指向下一个结点
    _M_node = (_Node*)(_M_node->_M_next);
    return *this;
  }
  _Self operator++(int) { 				// 指针++
    _Self __tmp = *this;				// 调用拷贝构造函数
    ++*this;
    return __tmp;
  }
  // ...
};

在新版的GNU C++ 4.9 中 list 的实现有些许不同，但 iterator 的实现依旧是同样的逻辑，这里不再赘述。

从桥梁的角度理解迭代器

正如“从指针的角度理解迭代器”中介绍的那样，无论是顺序表的迭代器还是链表的迭代器，本质都是指针。在上一节中，指针被封装成迭代器，实现了 *、++、--、-> 等运算，但从算法的角度来说，算法不仅需要这些迭代器操作，算法还需要知道容器内存储的元素类型以及其他信息（这里同称为 associated types），而迭代器必须就这些问题给出回答。

迭代器必须提供以下五种 associated types（以 __list_iterator 为例）：

template<class _Tp, class _Ref, class _Ptr>
struct _List_iterator {
  // ...
  typedef bidirectional_iterator_tag iterator_category;	// 表示迭代器类型（正向、双向、随机）
  typedef _Tp value_type;								// 表示迭代器指向的元素类型
  typedef _Ptr pointer;									// 表示迭代器指向的元素的指针类型，即_Tp*
  typedef _Ref reference;								// 表示迭代器指向的元素的引用类型，即_Tp&
  typedef ptrdiff_t difference_type;					// 表示两个迭代器距离的类型，ptrdiff_t一般是unsigned(长)整型
  // ...
}

如果迭代器以类实现，那么算法只需使用域操作符即可获知对应的 associated type：

template <typename I>
void alogrithm(I iter) {
	// ...
	I::iterator_category
	I::value_type
	// ...
}

但如果迭代器是指针呢？如 vector 和 array，那么就无法通过上述方法获取对应的 associated type。

而这里，只需要加一个中间类 Iterator_traits，即可解决问题：

  template<typename _Iterator>		// class 类型的 iterator 实现
    struct __iterator_traits<_Iterator,
			     __void_t<typename _Iterator::iterator_category,
				      typename _Iterator::value_type,
				      typename _Iterator::difference_type,
				      typename _Iterator::pointer,
				      typename _Iterator::reference>>
    {
      typedef typename _Iterator::iterator_category iterator_category;
      typedef typename _Iterator::value_type        value_type;
      typedef typename _Iterator::difference_type   difference_type;
      typedef typename _Iterator::pointer           pointer;
      typedef typename _Iterator::reference         reference;
    };

  template<typename _Iterator>
    struct iterator_traits
    : public __iterator_traits<_Iterator> { };

对于指针类型的迭代器，只需对上述的类模板进行特化：

  /// Partial specialization for pointer types.
  template<typename _Tp>
    struct iterator_traits<_Tp*>
    {
      typedef random_access_iterator_tag iterator_category;
      typedef _Tp                         value_type;
      typedef ptrdiff_t                   difference_type;
      typedef _Tp*                        pointer;
      typedef _Tp&                        reference;
    };

  /// Partial specialization for const pointer types.
  template<typename _Tp>
    struct iterator_traits<const _Tp*>
    {
      typedef random_access_iterator_tag iterator_category;
      typedef _Tp                         value_type;
      typedef ptrdiff_t                   difference_type;
      typedef const _Tp*                  pointer;
      typedef const _Tp&                  reference;
    };

这样，无论是 class 类型的迭代器还是指针类型的迭代器，都可以通过 iterator_traits 获取对应的 associated types。

标签：node,typedef,迭代,iterator,剖析,type,指针
From： https://www.cnblogs.com/HOMEofLowell/p/17846542.html