【STL】迭代器

小灰灰 2022-07-13 00:59 317阅读 0赞

## 什么是迭代器 ##

迭代器是STL中行为类似指针的设计模式，它可以提供了一种对容器中的对象的访问方法；并且它没有暴露容器中内部的表述方式。  
例如STL中的map和set,它们的底层是一颗红黑树（一种平衡树）：

private:
      typedef rb_tree<key_type, value_type, 
                      select1st<value_type>, key_compare, Alloc> rep_type;
      rep_type t;  // red-black tree representing map

而当你用迭代器去对他们进行访问时：

map<string, size_t> mp;
        mp["a"]++;
        mp["a"]++;
        mp["b"]++;
        mp["b"]++;
        mp["c"]++;
        mp["d"]++;
        mp["e"]++;
        mp["f"]++;
        mp["g"]++;
        mp["a"]++;
        mp["b"]++;
        mp["f"]++;
        mp["a"]++;
        mp["b"]++;
    
    
        map<string, size_t>::iterator it = mp.begin();
        while (it != mp.end())
        {
            cout << (*it).first << " " << (*it).second << endl;
            it++;
        }

原本在红黑树中的二叉树结构却能转换成一种线性结构的访问方式，如上述例子。可见，迭代器既能对容器中的对象进行访问，又能将容器的结构隐藏起来，达到封装的效果。

今天，我们就来介绍一下迭代器

## STL中迭代器的特性 ##

迭代器的特性被称为迭代器的型别，那什么是迭代器的型别呢？

STL中必须包含以下五种内嵌型别的迭代器称为标准迭代器，它们分别是：

## 1.value type ##

value type 就是指迭代器所指对象的相类型，任何一个打算与STL算法有多联系的容器都应该定义自己value type的内嵌型别，例如STL的vector中：

typedef T value_type;   //T为模板参数

## 2.difference type ##

difference type被用来表示两个迭代器之间的距离，它在STL的vector中的定义如下

typedef ptrdiff_t difference_type;

ptrdiff\_t是C/C++标准库中定义的一个与机器相关的数据类型。ptrdiff\_t类型变量通常用来保存两个指针减法操作的结果。ptrdiff\_t定义在stddef.h（cstddef）这个文件内。ptrdiff\_t通常被定义为long int类型。

## 3.reference type ##

reference type为迭代器所指向的容器中对象的引用。在STL中定义如下：

typedef value_type& reference;

## 4.pointer type ##

pointer type为容器中迭代器所指向的对象的地址

typedef value_type* pointer;

## 5.iterator category ##

前面四个型别熟悉C++的人应该有所了解了，第五个型别我们可以理解为迭代器的分类，首先我们来看看迭代器有哪些类型？

源码中定义如下：

//该迭代器所指向的对象不能够被改变，被称为只读迭代器
    struct input_iterator_tag {};     
    //只许写入的迭代器，我们只能在该种迭代器类型的区间上进行写操作     
    struct output_iterator_tag {};
    ////允许写入的迭代器，我们可以在该种迭代器类型的区间上进行读写操作 
    struct forward_iterator_tag : public input_iterator_tag {};
    //可双向移动迭代器，也就是说该种迭代器可以进行 iterator++和--操作
    struct bidirectional_iterator_tag : public forward_iterator_tag {};
    //随机序列的迭代器，该种迭代器首先要要求容器中的地址必须是连续的，并且该容器涵盖了指针的所有运算操作
    struct random_access_iterator_tag : public bidirectional_iterator_tag {};

迭代器分类的从属关系：  
![这里写图片描述][SouthEast]

STL迭代器中实际的继承关系：  
![这里写图片描述][SouthEast 1]

[SouthEast]: /images/20220713/69c0082ab11442daa089ee04c2fef56e.png
[SouthEast 1]: /images/20220713/4bbab42eac9c4ae58c27346731585526.png