不同标准库容器的iterator

• Array是连续空间，可以连续移动，类似指针。
  所以其迭代器是random_access_iterator_tag.
• vector也是连续空间，所以其迭代器也是random_access_iterator_tag.
• Deque虽然是假的连续空间，但是其迭代器也是random_access_iterator_tag.
• List，双向链表，可以往前往后，但是不支持随机访问，所以其迭代器是bidirectional_iterator_tag.
• Forward_List,单向链表，只能单方向的走，不能往后退，所以其迭代器是forward_iterator_tag.
• 红黑树所作出的容器set/map/Multiset/Multimap,根据红黑树的特性，所以其迭代器是bidirectional_iterator_tag.
• 哈希表所作出的容器，哈希容器，其迭代器的类型要根据list的类型来决定，看看list是单向的，还是双向的。

五种iterator_categor

struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag: public input_iterator_tag{}; //继承自input
struct bidirectional_iterator_tag :public forward_iterator_tag{};//继承自forward
struct random_access_iterator_tag:public bidirectional_iterator_tag{};

五种迭代器类型之间的关系

? ? ?? ?????

input iterator

?

input iterator 只能够与单遍算法一起使用，不能被赋值，是所有迭代器等级中最低的一个。当我们搜索范围内的元素时，每个位置最多只能被访问一次。可以将输入迭代器与另一个迭代器比较，因此只有两个迭代器指向相同位置时，这两个迭代器才相等。输入迭代器只能单向递增。¹

iterator_category对算法的影响

1. 举个例子：输入迭代器求取这两个位置之间的距离：

template<class InputIterator>
inline iterator_traits<InputIterator>::difference_type //返回类型应该用iterator_traitsqu
distance(InputIterator first, InputIterator last) {
    typedef typename iterator_traits<InputIterator>::iterator_category categor;
    return _distance(first,last,category);
}

_distance()是重载函数，根据category的类型分别重载为下面两个：

• 如果category()的类型是random_access_iterator_tag()，则两个迭代器可以通过相减获得距离：

template<class RandomAccessIterator>
inline iterator_traits<RandomAccessIterator>::difference_type
__distance(RandomAccessIterator first, RandomAccessIterator last,random_access_iteraotr_tag) {
    return last-first;
}

• 如果迭代器的类型不是random_access_iterator_tag()而是input_iterator_tag()，则函数重载为下述形式：

template<class InputIterator>
inline iterator_traits<InputIterator>::difference_type
__distance(InputIterator first, InputIterator last,input_iterator_tag) {
    iterator_traits<InputIterator>::difference_type n = 0;
    while(first != last) {
        ++first;
        ++n;
    }
    return n;
}

再举个例子：advance()

template<class InputIterator, class Distance>
inline void advance(InputIterator& i, Distance n) {
    __advance(i,n,iterator_category(i));
}

//其中iterator_category的作用是萃取出距离的类型：
template<class Iterator>
inline typename iterator_traits<Iterator>::iterator_category
iterator_category(const Iterator&) {
    typedef typename iterator_traits<Iterator>::iterator_category category;
    return category();
}

根据category()的类型对_advance()函数进行重载：

• 当迭代器类型是input_iterator_tag时：

template<class InputIterator, class Distance>
inline void _advance(InputIterator& i, Distance n, input_iterator_tag) {
    while(n--) ++i;
}

• 当迭代器类型是bidirectional_iterator_tag时：

template<class BidirectionalIterator,class Distance>
inline void _advance(BidirectionalIterator& i, Distance n, bidirectional_iterator_tag) {
    if(n >= 0) 
        while(n--) ++i;
    else 
        while(n++) --i;
}

• 当迭代器类型是random_access_iterator_tag:

template<class RandomAccessIterator,class Distance>
inline void _advance(RandomAccessIterator& i, Distance n, random_access_iterator_tag) {
    i+=n;
}

虽然重载的函数，有些并没有farwardIterator，但是它和inputIterator是继承关系，所以也是可以使用这个函数。