迭代器Iterator

迭代器是什么

迭代器是用来访问容器保存元素的数据结构中的元素也就是访问某种数据结构中的元素是一种检查容器内元素并遍历元素的数据类型。 Iterator模式是运用于聚合对象的一种模式通过运用该模式使得我们可以在不知道对象内部表示的情况下按照一定顺序由iterator提供的方法访问聚合对象中的各个元素。数组范围内的指针就是迭代器的一种。

指针针是C语言里面就有的东西而迭代器是C++里面才有的。
指针通常用来访问的是序列的元素但不是所有的容器都会在连续的内存空间上保存数据。所以对于这些容器我们不能单纯地使用指针作为迭代器而是针对每一种容器都会有专门配对的迭代器。

对于所有的迭代器它们的使用方法和指针一样比如自增++解引用*。除了数组以外在大部分的容器中都会提供成员函数beget在类中创建类是C++中对于C语言中的结构体的延伸用来获取容器开始位置的迭代器会提供成员函数end用来获取容器结束位置的迭代器。

什么是迭代器迭代器有什么作用

迭代器类型

Input Iterator只能单步向前迭代元素不允许修改由该类迭代器引用的元素。
Output Iterator该类迭代器和Input Iterator极其相似也只能单步向前迭代元素不同的是该类迭代器对元素只有写的权力。
Forward Iterator该类迭代器可以在一个正确的区间中进行读写操作它拥有Input Iterator的所有特性和Output Iterator的部分特性以及单步向前迭代元素的能力。
Bidirectional Iterator该类迭代器是在Forward Iterator的基础上提供了单步向后迭代元素的能力。
Random Access Iterator该类迭代器能完成上面所有迭代器的工作它自己独有的特性就是可以像指针那样进行算术计算而不是仅仅只有单步向前或向后迭代。
input output
\ /
forward
|
bidirectional
|
random access

vector 和deque提供的是RandomAccessIteratorlist提供的是BidirectionalIteratorset和map提供的 iterators是 ForwardIterator。
关于STL中iterator迭代器的操作如下
说明每种迭代器均可进行包括表中前一种迭代器可进行的操作。
迭代器操作 说明
(1)所有迭代器
p++ 后置自增迭代器
++p 前置自增迭代器
(2)输入迭代器
*p 复引用迭代器作为右值
p=p1 将一个迭代器赋给另一个迭代器
p==p1 比较迭代器的相等性
p!=p1 比较迭代器的不等性
(3)输出迭代器
*p 复引用迭代器作为左值
p=p1 将一个迭代器赋给另一个迭代器
(4)正向迭代器
提供输入输出迭代器的所有功能
(5)双向迭代器
–p 前置自减迭代器
p-- 后置自减迭代器
(6)随机迭代器
p+=i 将迭代器递增i位
p-=i 将迭代器递减i位
p+i 在p位加i位后的迭代器
p-i 在p位减i位后的迭代器
p[i] 返回p位元素偏离i位的元素引用
p<p1 如果迭代器p的位置在p1前返回true否则返回false
p<=p1 p的位置在p1的前面或同一位置时返回true否则返回false
p>p1 如果迭代器p的位置在p1后返回true否则返回false
p>=p1 p的位置在p1的后面或同一位置时返回true否则返回false
只有顺序容器和关联容器支持迭代器遍历各容器支持的迭代器的类别如下
容器 支持的迭代器类别 容器 支持的迭代器类别 容器 支持的迭代器类别
vector 随机访问 deque 随机访问 list 双向
set 双向 multiset 双向 map 双向
multimap 双向 stack 不支持 queue 不支持
priority_queue 不支持

Iterator模式有三个重要的作用
1迭代器支持以不同的方式遍历一个聚合.复杂的聚合可用多种方式进行遍历如二叉树的遍历可以采用前序、中序或后序遍历以不同的顺序遍历了二叉树中的所有元素。迭代器模式使得改变遍历算法变得很容易: 仅需用一个不同的迭代器的实例代替原先的实例即可你也可以自己定义迭代器的子类以支持新的遍历或者可以在遍历中增加一些逻辑如有条件的遍历等。
2迭代器简化了聚合的接口. 有了迭代器的遍历接口聚合本身就不再需要类似的遍历接口了这样就简化了聚合的接口。
3在同一个聚合上可以有多个遍历 每个迭代器保持它自己的遍历状态因此你可以同时进行多个遍历。
4此外Iterator模式可以为遍历不同的聚合结构需拥有相同的基类提供一个统一的接口即支持多态迭代。
c++迭代器iterator详解

迭代器的实现源码分析

 // 五种迭代器类型
    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 {};

从迭代器模版看迭代器的具体结构
利用内嵌类型申明typedef可以轻松实现隐藏所指对象类型

// iterator 模板
    template <class Category, class T, class Distance = ptrdiff_t, class Pointer = T*, class Reference = T&>
        struct iterator
    {
        typedef Category                             iterator_category;//迭代器类型
        typedef T                                    value_type;//迭代器指向的容器对象中存储的元素的类型
        typedef Pointer                              pointer;//指向迭代器所指向的元素的指针
        typedef Reference                            reference;//对迭代器所指向的元素的引用
        typedef Distance                             difference_type;//两个迭代器之间的距离
    };

C++从类模板 Iterator 中的模板参数来看迭代器

迭代器的萃取

判断有无迭代器类型

 template <class T>
    struct has_iterator_cat//判断是否有迭代器类别iterator_category
    {
    private:
        struct two { char a; char b; };
        template <class U> static two test(...);//没有类别返回结构体two
        template <class U> static char test(typename U::iterator_category* = 0);//有类别返回char
        //通过传入的模板类型有无typename U::iterator_category来返回two 还是char
    public:
        static const bool value = sizeof(test<T>(0)) == sizeof(char);//有类别返回true
    };

有类型就继承iterator_traits_impl

template <class Iterator, bool>
    struct iterator_traits_impl {};

    template <class Iterator>
    struct iterator_traits_impl<Iterator, true>
    {
        typedef typename Iterator::iterator_category iterator_category;
        typedef typename Iterator::value_type        value_type;
        typedef typename Iterator::pointer           pointer;
        typedef typename Iterator::reference         reference;
        typedef typename Iterator::difference_type   difference_type;
    };

判断Iterator::iterator_category是否可以隐式转换为输入迭代器或输入迭代器如果不能隐式转换也就没必要萃取了如果能转换就得到所有迭代器信息。

template <class Iterator, bool>
    struct iterator_traits_helper {};

    template <class Iterator>
    struct iterator_traits_helper<Iterator, true>
        : public iterator_traits_impl<Iterator,
        std::is_convertible<typename Iterator::iterator_category, input_iterator_tag>::value ||
        std::is_convertible<typename Iterator::iterator_category, output_iterator_tag>::value>
        //判断Iterator::iterator_category是否可以隐式转换为输入迭代器或输入迭代器
    {
    };

判断迭代器具体类型

 //T类型迭代器能隐式转换为U类型迭代器
    template <class T, class U, bool = has_iterator_cat<iterator_traits<T>>::value>
    struct has_iterator_cat_of
        : public m_bool_constant<std::is_convertible<
        typename iterator_traits<T>::iterator_category, U>::value>//判断T类型迭代器能隐式转换为U类型迭代器
    {
    };
    //T类型迭代器无法隐式转换为U类型迭代器 
    template <class T, class U>
    struct has_iterator_cat_of<T, U, false> : public m_false_type {};
    //判断是否为input_iterator_tag类别迭代器
    template <class Iter>
    struct is_input_iterator : public has_iterator_cat_of<Iter, input_iterator_tag> {};
    //判断是否为output_iterator_tag类别迭代器
    template <class Iter>
    struct is_output_iterator : public has_iterator_cat_of<Iter, output_iterator_tag> {};
    //判断是否为forward_iterator_tag类别迭代器
    template <class Iter>
    struct is_forward_iterator : public has_iterator_cat_of<Iter, forward_iterator_tag> {};
    //判断是否为bidirectional_iterator_tag类别迭代器
    template <class Iter>
    struct is_bidirectional_iterator : public has_iterator_cat_of<Iter, bidirectional_iterator_tag> {};
    //判断是否为random_access_iterator_tag类别迭代器
    template <class Iter>
    struct is_random_access_iterator : public has_iterator_cat_of<Iter, random_access_iterator_tag> {};
    //判断是否为迭代器所有迭代器都是从input_iterator_tag 和 output_iterator_tag派生来的 ,所以只要判断是否是input_iterator_tag 或 output_iterator_tag
    template <class Iterator>
    struct is_iterator :
        public m_bool_constant<is_input_iterator<Iterator>::value ||
        is_output_iterator<Iterator>::value>
    {
    };

泛型算法得到某个迭代器某个特性的类型
C++类型萃取(traits)技术

C++ 模板类型萃取技术 traits

// 萃取某个迭代器的 category返回的就是结构体中的类型
    template <class Iterator>
    typename iterator_traits<Iterator>::iterator_category
        iterator_category(const Iterator&)
    {
        typedef typename iterator_traits<Iterator>::iterator_category Category;//把iterator_traits<Iterator>::iterator_category类型命名为Category
        return Category();
    }

    // 萃取某个迭代器的 distance_type
    template <class Iterator>
    typename iterator_traits<Iterator>::difference_type*
        distance_type(const Iterator&)// 在开头的迭代器结构体中定义过typename iterator_traits<Iterator>::difference_type*就是迭代器之间的距离距离
    {
        return static_cast<typename iterator_traits<Iterator>::difference_type*>(0);
    }

    // 萃取某个迭代器的 value_type
    template <class Iterator>
    typename iterator_traits<Iterator>::value_type*
        value_type(const Iterator&)
    {
        return static_cast<typename iterator_traits<Iterator>::value_type*>(0);
    

MyTinySTL阅读笔记—迭代器

通过迭代器类型的应用计算距离、移动迭代器

template
typename iterator_traits::difference_type distance(InputIterator first, InputIterator last)
{
// 按照迭代器种类分类处理
return distance_dispatch(first, last, iterator_category(first));
}

/*! 计算first迭代器和last迭代器之间的距离 input_iterator_tag版本 按照链表的方式计算 */
template
typename iterator_traits::difference_type distance_dispatch(InputIterator first, InputIterator last, input_iterator_tag)
{
typename iterator_traits::difference_type n = 0;
while (first != last)
{
++first;
++n;
}
return n;
}

/*! 计算first迭代器和last迭代器之间的距离 random_access_iterator_tag版本 按照指针的方式计算 */
template
typename iterator_traits::difference_type distance_dispatch(RandomIter first, RandomIter last, random_access_iterator_tag)
{
return last - first;
}