迭代器作用

  • 在设计模式中有一种模式叫迭代器模式，简单来说就是提供一种方法，在不需要暴露某个容器的内部表现形式情况下，使之能依次访问该容器中的各个元素，
  • 这种设计思维在STL中得到了广泛的应用，是STL的关键所在，通过迭代器，容器和算法可以有机的粘合在一起，只要对算法给予不同的迭代器，就可以对不同容器进行相同的操作。
  • 在这里提到了一个叫迭代器的东西，说得简单一点，就是一种指针，学习C和C++的同学肯定不会对指针感到陌生，这确实是个让我们又爱又恨的东西。
  • 以下以算法find为例，展示了容器、算法和迭代器如何合作：
template<typename InputIterator, typename T>
InputIterator find(InputIterator first, InputIterator last, const T &value)
{
    while (first != last && *frist != value)
        ++first;
    return first;
}

迭代器是一种智能指针

  • 它将指针进行了一层封装，既包含了原生指针的灵活和强大，也加上很多重要的特性，使其能发挥更大的作用以及能更好的使用。
  • 迭代器对指针的一些基本操作如*、->、++、==、!=、=进行了重载，使其具有了遍历复杂数据结构的能力，其遍历机制取决于所遍历的数据结构。
  • 下面上一段代码，了解一下迭代器的“智能”：

对于不同的数据容器，以上Iterator类中的成员函数operator++的实现会各不相同，

例如，对于数组的可能实现如下：

//对于数组的实现
template<typename T>
Iterator& operator++()
{ 
    ++m_ptr; 
    retrun *this;
}

对于链表，它会有一个类似于next的成员函数用于获取下一个结点，其可能实现如下：

//对于链表的实现
template<typename T>
Iterator& operator++()
{
    m_ptr = m_ptr->next();//next()用于获取链表的下一个节点 
    return *this;
}

不同的容器都有专属的迭代器

下面尝试实现一个自己的迭代器，由于迭代器的作用对象是容器，因此需要首先实现一个容器，下面代码展示了一个

单向链表的实现：


template<typename T>
class ListItem
{
public:
    ListItem() { m_pNext = 0;}
    ListItem(T v, ListItem *p = 0) { m_value = v; m_pNext = p;}
    T Value() const { return m_value;}
    ListItem* Next() const { return m_pNext;}
	
private:
    T m_value;	//存储的数据
    ListItem* m_pNext;	//指向下一个ListItem的指针
};
 
template<typename T>
class List
{
public:
    //从链表尾部插入元素
    void Push(T value)
    {
       m_pTail = new ListItem<T>(value);
       m_pTail = m_pTail->Next();
    }
	
    //打印链表元素
    void Print(std::ostream &os = std::cout) const
    {	
        for (ListItem<T> *ptr = m_pHead; ptr; ptr = ptr->Next())
        os<<ptr->Value<<" ";
        os<<endl;
    }
	
    //返回链表头部指针
    ListItem<T>* Begin() const { return m_pHead;}
 
    //返回链表尾部指针
    ListItem<T>* End() const { return 0;}
	
    //其它成员函数
 
private：
    ListItem<T> *m_pHead;    //指向链表头部的指针
    ListItem<T> *m_pTail;    //指向链表尾部的指针
    long m_nSize;    //链表长度
};

迭代器实现：

template<typename T>
class ListIter
{
public:
    ListIter(T *p = 0) : m_ptr(p){}
	
    //解引用，即dereference
    T& operator*() const { return *m_ptr;}
	
    //成员访问，即member access
    T* operator->() const { return m_ptr;}
	
    //前置++操作
    ListIter& operator++() 
    { 
        m_ptr = m_ptr->Next(); //暴露了ListItem的东西
        return *this;
    }
	
    //后置++操作
    ListIter operator++(int)
    {
        ListIter temp = *this;
        ++*this;
        return temp;
    }
	
    //判断两个ListIter是否指向相同的地址
    bool opeartor==(const ListIter &arg) const { return arg.m_ptr == m_ptr;}
	
    //判断两个ListIter是否指向不同的地址
    bool operator!=(const ListIter &arg) const { return arg.m_ptr != m_ptr;}
	
private:
    T *m_ptr;
};

测试代码：


int main(int argc, const char *argv[])
{
    List<int> mylist;
	
    for (int i = 0; i < 5; ++i)
    {
        mylist.push(i);
    }
    mylist.Print();	//0 1 2 3 4
	
    //暴露了ListItem
    ListIter<ListItem<int> > begin(mylist.Begin());
    ListIter<ListItem<int> > end(mylist.End());
    ListIter<ListItem<int> > iter;
	
    iter = find(begin, end, 3);//从链表中查找3
    if (iter != end)
        cout<<"found"<<endl;
    else
        cout<<"not found"<<endl;
}
  • 为了实现迭代器ListIter，我们在很多地方暴露了容器List的内部实现ListItem，这违背一开始说的迭代器模式中不暴露某个容器的内部表现形式情况下，使之能依次访问该容器中的各个元素的定义。
  • 为了解决这种问题，STL将迭代器的实现交给了容器，每种容器都会以嵌套的方式在内部定义专属的迭代器。
  • 各种迭代器的接口相同，内部实现却不相同，这也直接体现了泛型编程的概念。

迭代器的分类

在STL中，原生指针也是一种迭代器，除了原生指针以外，迭代器被分为五类：

  • Input Iterator

​ 此迭代器不允许修改所指的对象，即是只读的。支持==、!=、++、*、->等操作。

  • Output Iterator

​ 允许算法在这种迭代器所形成的区间上进行只写操作。支持++、*等操作。

  • Forward Iterator

​ 允许算法在这种迭代器所形成的区间上进行读写操作，但只能单向移动，每次只能移动一步。支持Input Iterator和Output Iterator的所有操作。

  • Bidirectional Iterator

​ 允许算法在这种迭代器所形成的区间上进行读写操作，可双向移动，每次只能移动一步。支持Forward Iterator的所有操作，并另外支持–操作。

  • Random Access Iterator

​ 包含指针的所有操作，可进行随机访问，随意移动指定的步数。支持前面四种Iterator的所有操作，并另外支持it + n、it - n、it += n、 it -= n、it1 - it2和it[n]等操作。