STL迭代器在工作中使用的频次很高，最近在回顾 «STL源码剖析» 的过程中，再次熟悉一下迭代器的实现原理，并且记录一下

• 1.迭代器
  • 1.1 迭代器作用
  • 1.2 迭代器相应类型(associated types)
• 2. Traits 编程技术
• 3. 总结

以下内容主要摘抄自«STL源码剖析»的书籍中，以及下面的博客链接: https://github.com/steveLauwh/SGI-STL/tree/master/The%20Annotated%20STL%20Sources%20V3.3/iterator

1.迭代器

1.1 迭代器作用

迭代器是一种抽象，用于”黏合”容器和算法。
这句话怎么理解，试想如果想做一个容器进行遍历等，如果没有迭代器，则需要清楚的知道每个容器内部是怎么实现的，举个例子:

如果没有迭代器，那么遍历vector，list则可能会是下面的方法遍历

//eg1. 遍历vector
vector<int> v ;
for (size_t index = 0; index != v.size(); ++ index)
{
    do_something(v[index]); //因为我们知道vector的[]和size方法
}

//eg2. 遍历list
list<int> l;
struct<xxxx>* cur_ptr = l.m_cur;
while(cur_ptr != NULL)
{
    do_something(cur_ptr->data); 
    cur_ptr = cur_ptr->next; //可能是链表的下一个节点
}

意味着开发者需要每个容器内部的实现方式，针对不容的容器，不同方法进行遍历；

迭代器是一种行为类似指针的对象，而指针的各种行为中最常见的用途是 dereference 和 member access。迭代器最重要的就是对 operator* 和 operator->进行重载工作。

为什么每一种 STL 容器都提供有专属迭代器的缘故。
主要是暴露太多细节，所以把迭代器的开发工作交给容器去完成，这样所有实现细节可以得到封装，不被使用者看到。

有了迭代器之后，那么遍历容器就可以使用迭代器来实现

vector<int> v;
for (vector<int>::iterator it = v.begin(); it != v.end(); ++it)
{
	cout << *it << endl;
}

list<int> l;
for (list<int>::iterator it = l.begin(); it != l.end(); ++it)
{
	cout << *it << endl;
}

1.2 迭代器相应类型(associated types)

迭代器所指对象的类型。

利用 function template 的参数推导机制，只能推导出参数的类型，无法推导出函数返回值类型。

迭代器相应类型有五种：

• value type
• difference type
• pointer
• reference
• iterator category

2. Traits 编程技术

traits 意为 “特性”，扮演 “特性萃取机” 角色，萃取各个迭代器的特性(相应类型)。

template partial specialization 模板偏特化：针对 template 参数更进一步的条件限制所设计出来的一个特化版本，本身仍然是 template。

tempalte<typename I>
struct iterator_traits
{
    typedef typename I::iterator_category  iterator_category;
    typedef typename I::value_type  value_type;
    typedef typename I::difference_type  difference_type;
    typedef typename I::pointer  pointer;
    typedef typename I::reference  reference;
};

• 迭代器相应类型之一：value type

value type 就是迭代器所指对象的类型。

template <class T>
typename iterator_traits<I>::value_type func(I ite)
{
    return *ite;
}

• 迭代器相应类型之二：difference type

difference type 用来表示两个迭代器之间的距离。

template <class I, class T>
typename iterator_traits<I>::difference_type cout(I first, I last, const T& value)
{
    typename iterator_traits<I>::difference_type n = 0;
    for (; first != last; ++first)
    {
        ++n;
    }
    
    return n;
}

• 迭代器相应类型之三：reference type

在 c++ 中，函数如果要传回左值，都是以 by reference 的方式进行，所以如果 p 是一个迭代器，它的 value type 是 T ，那么*p 应该是T& (即reference type)

• 迭代器相应类型之四：pointer type

• 迭代器相应类型之五：iterator_category

  • 输入迭代器 (InputIterator) 是能从所指向元素读取的迭代器 (Iterator) 。输入迭代器 (InputIterator) 仅保证单趟算法的合法性。
  • 输出迭代器 (OutputIterator) 是能写入所指元素的迭代器 (Iterator) 。
  • 向前迭代器 (ForwardIterator) 是一种能从所指向元素读取数据的迭代器 (Iterator) 。
  • 双向迭代器 (BidirectionalIterator) 是能双向移动（即自增与自减）的向前迭代器 (ForwardIterator) 。
  • 随机访问迭代器 (RandomAccessIterator) 是能在常数时间内移动到指向任何元素的双向迭代器 (BidirectionalIterator) 。

3. 总结

traits 本质是什么？

多一层间接性，换来灵活性。

iterator_traits 负责萃取迭代器的特性，__type_traits 负责萃取类型的特性。