程序员应了解的那些事（5）C++迭代器之iterator_traits/iterator_category

<1>traits
所谓traits，可以理解为“萃取机”。作用就是：你丢给他什么东西，他会给你拿出你想要的特性。

迭代器的特性：iterator_traits<>

 <2>迭代器的属性
迭代器是沟通算法和容器的桥梁。一方面让算法知道所要处理的范围，另一方面可以取出容器中的数据。
以rotate算法为例，我们来看看算法需要迭代器的哪些属性。

1、iterator_category：根据调用关系，我们看出首先需要得到iterator_category，即迭代器的分类。
2、difference_type：回答两个iterator中间的距离需要用什么类型来表现。
3、value_type：需要回答容器中存的类型，即迭代器所指元素的类型。
综上，每一个算法需要迭代器回答这三个问题，（还有两个未出现过的reference和pointer）如下图所示。
 

<3>迭代器的traits
只有class才能typedef，而迭代器是泛化的指针。为了回答前一页的问题，traits就需要进行如下设计：

Traits要先区分是否为class的迭代器。如果是，则可以直接回答算法的问题，如果否，则应用traits作为中介，来回答这一问题。而这个中介以如下方式设计：

 <4>iterator_category
(4.1)种类
一共有5种iterator_category分别为：
1、input_iterator：istream独有的迭代器。
2、output_iterator：ostream独有的迭代器。
3、forward_iterator：继承自input_iterator，单向走的迭代器，只能走一个，不能跳。如forward_list、单向list的hashtable
4、bidirectional_iterator：继承自forward_iterator，双向走的迭代器，只能走一个，不能跳。如list、rb-tree、双向list的hashtable
5、random_access_iterator：继承自bidirectional_iterator，可以跳的迭代器。如array、vector、deque。

下例表现打印了每种类型容器的迭代器类型：

打印了每种类型容器iterator_category的typeid：

 

（4.2）对算法的影响。 算法的效率与迭代器的类型有巨大关系

①距离：distance

       先看distance函数，它要知道两个迭代器之间的距离。根据不同的迭代器种类调用两个不同（重载）的__distance函数。对于random_access_iterator，只有连续空间才有这种指针，故可以直接相减；但若是input_iterator版本，就从头一步步走到尾，看共走了多少步。返回类型为iterator_traits中的difference_type（就是表示距离）。
      如上distance，这种情况在算法的实现中非常多，如果只用一步步走的方式，复杂度极大。所以，迭代器种类对算法的影响是很深远的。

② 前进：advance
        同上例，这里出现三种分类：一步步走呢（input_iterator），往那边走呢（bidirectional_iterator），还是可以跳呢（random_access_iterator）。

 

        当没有特殊的版本时，如forward_iterator没有特定的类型时，由于继承了input_iterator，故is a input_iterator，所以调用input_iterator版本。

③复制：copy
       copy函数非常简单，只需要有copy来源端的首尾迭代器，再给出copy接收端的首迭代器，只要3个参数即可完成。但实际的实现非常麻烦，会分成非常多种情况，看copy的对象是否特属于某一种更为简便的情况，因此对应很多种实现来加快其速度。

       由以上内容我们可以感受到copy实现的精细程度。这里，“has trivial” 表示“不重要的”，如同复数类的拷贝构造和拷贝赋值，用默认的即可，并不重要。

④unique_copy
为了防止发生output和read之间的冲突，需要制造一个Output_Iterator专属版本避免这种情况。

（4.3）算法对迭代器种类的影响
   算法对迭代器种类没有要求，但由于算法是模板函数，所以对迭代器种类有所“暗示”。