迭代器

迭代器概述

迭代器是一种抽象的设计概念，在设计模式中iterator模式被定义为：提供一种方法，可以按序访问某一聚合物（容器）所含元素，且不暴露该聚合物的内部表达方式。

在STL中，迭代器又起着将容器与算法联合到一起的作用。

#include <iostream>
#include <vector>
#include <list>
#include <deque>
#include <algorithm>
 
using namespace std;
 
int main()
{
	const int arr[7]{1, 2, 3, 4, 5, 6, 7};
 
	vector<int> varr(arr, arr + 7);
	list<int> larr(arr, arr + 7);
	deque<int> darr(arr, arr + 7);
 
	vector<int>::iterator it1 = find(varr.begin(), varr.end(), 3);
	list<int>::iterator it2 = find(larr.begin(), larr.end(), 4);
	deque<int>::iterator it2 = find(darr.begin(), darr.end(), 5);
 
	return 0;
}

上例用法就是常用的迭代器使用方式。find算法在查找时，与具体的数据结构无关，只要给出待查找数据集合的范围，find就可在该范围中查找，找到返回该元素在区间中的位置，否则返回end。

所示的迭代器都是依附于容器创建、使用的，除此之外其实也可以设计一种泛型的迭代器。

迭代器实现原理

迭代器是一种行为类似指针的对象，因此迭代器实现上首先需要对" * " 和 " -> "进行重载。

我们以list为对象，设计一个迭代器：

// list结构
template <typename T>
class List{
    void insert_front (T value);
    void insert_end (T value);
    void display (std::ostream &os = std::cout)const;
 
private:
    ListItem<T>* _end;
    ListItem<T>* _front;
    long _size;
};
 
tempalte <typename T>
class ListItem{
public:
    T value() const {return _value; }
    LsitItem* next()const {return _next; }
 
private:
    T _value;
    ListItem* _next;
}

list底层结构为带头结点的双向循环链表，迭代器在移动时，只能按照链表的结构前后依次移动，因此链表的迭代器需要对原生态的指针进行封装，因为当对迭代器++时，应该通过节点中的next指针域找到下一个节点。 

// 迭代器
template<class T, class Ref, class Ptr>
struct __list_iterator
{
	typedef __list_iterator<T, T&, T*> iterator;
	typedef __list_iterator<T, const T&, const T*> const_iterator;
	typedef __list_iterator<T, Ref, Ptr> self;
 
	typedef bidirectional_iterator_tag iterator_category;
	typedef T value_type;
	typedef Ptr pointer;
	typedef Ref reference;
	typedef ptrdiff_t difference_type;
 
	typedef ListItem<T>* link_type;
	typedef size_t size_type;
	link_type node;
	__list_iterator(link_type x)
		: node(x)
	{}
	__list_iterator()
	{}
	__list_iterator(const iterator& x)
		: node(x.node)
	{}
	bool operator==(const self& x) const
	{
		return node == x.node;
	}
	bool operator!=(const self& x) const
	{
		return node != x.node;
	}
	reference operator*() const
	{
		return (*node).data;
	}
	pointer operator->() const
	{
		return &(operator*());
	}
	self& operator++(){
		node = (link_type)((*node).next);
		return *this;
	}
 
	self operator++(int)
	{
		self tmp = *this;
		++*this;
		return tmp;
	}
	self& operator--()
	{
		node = (link_type)((*node).prev);
		return *this;
	}
	self operator--(int)
	{
		self tmp = *this;
		--*this;
		return tmp;
	}
};

 迭代器与类的融合

1. 定义迭代器类

           2. 在容器类中统一迭代器名字

// 如list：
template <class T, class Alloc = alloc>
class list
{
 
    typedef __list_iterator<T, T&, T*> iterator;
    // ...
};

3. 在容器类中添加获取迭代器范围的接口：

template <class T, class Alloc = alloc>
class list
{
 
    iterator begin()
    {
        return (link_type)((*node).next);
    }
    iterator end()
    {
        return node;
    }
    // ...
};

 

 

迭代器萃取参考：https://blog.csdn.net/LLZK_/article/details/53714015