STL源码剖析（六）迭代器

╰+攻爆jí腚メ 2023-10-10 10:04 38阅读 0赞

# STL源码剖析（六）迭代器 #

### 文章目录 ###

*  STL源码剖析（六）迭代器
 *   *  一、什么是迭代器？
     *  二、实现一个简单的容器
     *  三、实现容器的迭代器
     *  四、STL迭代器的规范
     *   *  4.1 STL迭代器的规范
         *  4.2 STL迭代器的分类

本文将带你学习什么是迭代器，以及STL的迭代器规范

## 一、什么是迭代器？ ##

迭代器是一种有指针行为（->，\*，++）的东西，它可以是`原生指针`，也可以是重载了\`\`operator->`、`operator\*`、`operator++`等运算符的`对象\`

对于原生指针就很清楚了，因为本身就具备指针的功能

对于迭代器是一个对象，你可能就有点不清楚了，别急，下面我使用一个非常简单的例子，来告诉你

## 二、实现一个简单的容器 ##

首先我们实现了非常非常简单的容器（容器是一个存储数据的对象）

template <class T>
    class MVector
    {
    public:
        MVector()
        {
            mStart = (T*)malloc(1024*1024);
            mEnd = mStart;
        }
    
        ~MVector()
        {
            free(mStart);
        }
    
        void push(const T& value)
        {
            *mEnd = value;
            ++mEnd;
        }
    
    private:
        T* mStart;
        T* mEnd;
    };

这实现了一个非常简单的容器，容器内部可以看是一个数组，`mStart`指向数组开头，`mEnd`指向数组最后一个元素的下一个位置，此容器只提供一个方法，那就是通过`push`添加元素

可以通过以下代码使用这个容器

#include <iostream>
    #include <stdlib.h>
    
    int main(int argc, char* argv[])
    {
        MVector<int> mVt;
    
        for(int i = 0; i < 10; ++i)
            mVt.push(i);
    
    	return 0;
    }

上述程序是简单的往容器中添加数据

想一下，我们现在如果要遍历容器内的所有元素，我们需要怎么做？

对于这个容器，我们当然可以通过某种方法，获取`mStart`和`mEnd`指针，然后通过它们来遍历所有的数组元素。

但在某些更加复杂的容器中（底层是链表或者红黑树）,在这些容器中，我们无法简单的通过指针来遍历所有元素，但是我们却想通过和指针一样的方式来访问容器中的元素，这时候就需要设计对象迭代器，然后重载运算符，将复杂的动作进行封装，提供和指针一样的功能

所以在STL中，大多数容器都提供了其对应的迭代器，下面我们就来为这个容器设计一个迭代器

## 三、实现容器的迭代器 ##

首先说明一下，对于上述这个容器，其实它的迭代器只要是`T*`原生指针就行，但是为了演示复杂的迭代器是怎么设计的，这里将实现一个对象迭代器，如下

template <class T>
    class Iterator
    {
    public:
        Iterator(T* data) : mData(data)
        {}
    
        Iterator& operator++()
        {
            ++mData;
            return *this;
        }
    
        T operator*()
        {
            return *mData;
        }
    
        bool operator!=(const Iterator& it)
        {
            return mData != it.mData;
        }
    
    private:
        T* mData;
    };

此迭代器内含一个对象指针，然后重载了`operator++`、`operator*`、`operator!=`运算符，这样子它就具有了指针的部分性质

有了迭代器之后，我们重新设计我们的容器，如下

template <class T>
    class MVector
    {
    public:
        /* add */
        typedef Iterator<T> iterator;
    
        MVector()
        {
            mStart = (T*)malloc(1024*1024);
            mEnd = mStart;
        }
    
        ~MVector()
        {
            free(mStart);
        }
    
        void push(const T& value)
        {
            *mEnd = value;
            ++mEnd;
        }
    
        /* add */
        iterator begin()
        {
            return iterator(mStart);
        }
    
        /* add */
        iterator end()
        {
            return iterator(mEnd);
        }s
        
    private:
        T* mStart;
        T* mEnd;
    };

我们使用`typedef Iterator<T> iterator`对外提供了该容器的迭代器类型，然后提供了`begin()`和`end()`来获取首尾迭代器

有了这些，我们就可以遍历容器的元素了，如下

int main(int argc, char* argv[])
    {
        MVector<int> mVt;
    
        /* 添加元素 */
        for(int i = 0; i < 10; ++i)
            mVt.push(i);
    
        /* 遍历容器 */
        for(MVector<int>::iterator it = mVt.begin(); it != mVt.end(); ++it)
            std::cout<<*it<<" "; //访问元素
        
        std::cout<<std::endl;
    
        return 0;
    }

**完整代码**

#include <iostream>
    #include <stdlib.h>
    
    template <class T>
    class Iterator
    {
    public:
        Iterator(T* data) : mData(data)
        {}
    
        Iterator& operator++()
        {
            ++mData;
            return *this;
        }
    
        T operator*()
        {
            return *mData;
        }
    
        bool operator!=(const Iterator& it)
        {
            return mData != it.mData;
        }
    
    private:
        T* mData;
    };
    
    template <class T>
    class MVector
    {
    public:
        typedef Iterator<T> iterator;
    
        MVector()
        {
            mStart = (T*)malloc(1024*1024);
            mEnd = mStart;
        }
    
        ~MVector()
        {
            free(mStart);
        }
    
        iterator begin()
        {
            return iterator(mStart);
        }
    
        iterator end()
        {
            return iterator(mEnd);
        }
    
        void push(const T& value)
        {
            *mEnd = value;
            ++mEnd;
        }
    
    private:
        T* mStart;
        T* mEnd;
    };
    
    int main(int argc, char* argv[])
    {
        MVector<int> mVt;
    
        for(int i = 0; i < 10; ++i)
            mVt.push(i);
    
        /* 遍历容器 */
        for(MVector<int>::iterator it = mVt.begin(); it != mVt.end(); ++it)
            std::cout<<*it<<" ";
        std::cout<<std::endl;
    
        return 0;
    }

## 四、STL迭代器的规范 ##

经过上述的讲解，想必你已经知道什么是迭代器了，但是我们上述实现的迭代器不符合STL的规范，所以对于STL的许多算法，我们并无法使用，下面来看一看STL中迭代器的设计规范

在`stl_iterator.h`文件中，定义了许多与迭代器相关的东西

### 4.1 STL迭代器的规范 ###

首先我们来看一下，STL对迭代器的要求，STL要求迭代器至少需要能提供上述的5种类型，如下

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 Distance  difference_type; //两个迭代器之间的距离描述
      typedef Pointer   pointer; //迭代器所指的类型的指针类型
      typedef Reference reference; //迭代器所指类型的引用类型
    };

为什么需要提供这些信息？

因为在STL的算法中，通常需要这些信息来定义相应的类型，或者根据这些信息来采取不同的措施，如果你设计的迭代器不满足这些要求，那么你在使用STL的算法的时候，非常有可能编译失败

关于其它字段，这里不做讨论了，下面好好讨论一个迭代器分类`iterator_category`

### 4.2 STL迭代器的分类 ###

STL对迭代器分为5类，其定义如下

/* 输入式迭代器 */
    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 {};

它们的关系如下

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70]

单向迭代器：表示往一个方向一格一格移动（单向链表）

双向迭代器：表示往前后方向一格一格移动（双向链表）

随机访问迭代器：可以随机访问（数组）

**为什么需要迭代器分类？**

主要目的是为了让算法可以采用不同的策略，下面举一个例子

在stl的算法中，有一个叫`advance`的算法，其作用是移动迭代器的指向，定义如下

inline void advance(InputIterator& i, Distance n)

设想一下，如果现在迭代器对应的容器底部是一个数组，那么移动5格，只需要+5就行，如果是链表的话，就需要一格一格地移动，很明显，这两者地效率差别是相当大

STL的实现如下

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

根据迭代器的`iterator_category`调用相应的`__advance`函数

对于随机访问的迭代器（random\_access\_iterator\_tag）

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

对于双向迭代器

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;
    }

对于普通的迭代器

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

本文到此也就结束了

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190924202631483.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg==,size_16,color_FFFFFF,t_70