C++STL迭代器(iterator)_c++ stl 迭代器

@TOC

       

目录

一.迭代器类别

（1）前向迭代器（forward iterator）

（2）双向迭代器（bidirectional iterator）

  (3)随机访问迭代器（random access iterator）

二. 迭代器的定义方式

---

       我们知道STL有六大组成：容器，算法，迭代器，函数对象，适配器，内存分配器，其中容器是一些封装数据结构的模板类，例如string,vector,stack,queue,不管是哪一种容器，最常做的操作都i是遍历容器中存储的元素。而要实现此操作，多数情况会选用“迭代器（iterator）” 来实现。

       我们知道，各个容器尽管内部结构各异，但是他们本质都是用来存储大量数据，为了让我们不至于换一个容器就得换个遍历方式，迭代器就此产生， 它可以处理不同的容器，依然统一的界面向算法传输数据 。

       迭代器可以是需要的任何类型，通过迭代器可以指向容器中的某个元素，还可以对该函数进行读和写的操作。

一.迭代器类别

       STL标准库为每一个标准容器定义了一种迭代器类型，这意味着，不同容器的迭代器也不同，其功能强弱也有所不同。

       容器的迭代器功能强弱，决定了该容器是否支持STL中的某个算法。

       常用的迭代器按功能强弱分为输入迭代器，输出迭代器，前向迭代器，双向迭代器，随机访问迭代器5种。因为输入和输出迭代器比较特殊，他不是把容器当作操作对象，而是把输入流和输出流作为操作对象，这个在I/O流后面慢慢提到，这一部分我们主要讲后面3种迭代器。

（1）前向迭代器（forward iterator）

       假设iterator是一个前向迭代器，则iterator支持 ++iterator , iterator++ , *iterator 操作，可以用==和!=运算符进行比较，此外两个正向迭代器可以互相赋值。

（2）双向迭代器（bidirectional iterator）

          双向迭代器具有正向迭代器的全部功能，除此之外，假设 iterator 是一个双向迭代器，则还可以进行 --iterator 或者 iterator-- 操作（即一次向后移动一个位置）。

  (3)随机访问迭代器（random access iterator）

        随机访问迭代器具有双向迭代器的全部功能。除此之外，假设 iterator 是一个随机访问迭代器，i 是一个整型变量或常量，则 iterator 还支持以下操作：

• iterator += i：使得 iterator 往后移动 i 个元素。
• iterator -= i：使得 iterator 往前移动 i 个元素。
• iterator+i：返回 iterator 后面第 i 个元素的迭代器。
• iterator-i：返回 iterator 前面第 i 个元素的迭代器。
• iterator[i]：返回 iterator 后面第 i 个元素的引用。

      此外，两个随机访问迭代器 iterator1、iterator2 还可以用 <、>、<=、>= 运算符进行比较。另外，表达式 iterator2-iterator1 也是有定义的，其返回值表示 iterator2 所指向元素和 iterator1 所指向元素的序号之差（也可以说是 iterator2 和 iterator1 之间的元素个数减一）。

    下表是C++11中不同容器指定使用的迭代器类型。

         注：容器适配器stack和queue没有迭代器，它们包含有一些成员函数，可以用来对元素进行访问。

二. 迭代器的定义方式

          尽管不同容器对应不同类型的迭代器，但这些迭代器有着较为统一的定义方式，具体分为4种。

       通过定义以上几种迭代器，就可以读取它指向的元素，*（迭代器名）就表示迭代器指向的元素。其中，常量迭代器和非常量迭代器的分别在于，通过非常量迭代器还能修改其指向的元素。另外，反向迭代器和正向迭代器的区别在于：

• 对正向迭代器进行 ++ 操作时，迭代器会指向容器中的后一个元素；
• 而对反向迭代器进行 ++ 操作时，迭代器会指向容器中的前一个元素。

        以上4种定义迭代器的方式，并不是每个容器都适用，有一部分容器是同时支持好几种迭代器的，但有些只能支持一种迭代器，比如：forward_list就只支持定义正向迭代器，不支持定义反向迭代器。

    下面，我简单使用迭代器进行示范：

#include<iostream>
#include <vector>
#include <iterator>
#include<typeinfo>
using namespace std;
 
int main()
{
	vector<int> v = { 1,2,3,4,5,6,7,8,9 };
	auto i = v.begin();
	const type_info& d = typeid(i);
	cout << d.name() << endl;
	for (i = v.begin(); i < v.end(); i++)
	{
		cout << *i << endl;
	}
	return 0;
}

运行结果：

  vector和array的迭代器作用很像，都是在同一块连续的区间内进行遍历，但是list是在一块不连续的位置上进行遍历。

#include<iostream>
#include <list>
#include <iterator>
#include<typeinfo>
using namespace std;
 
int main()
{
	list<int> head;
	head.push_back(1);
	head.push_back(2);
	head.push_back(3);
	head.push_back(4);
	list<int>::iterator iterator = head.begin();
	while (iterator != head.end())
	{
		cout << *iterator << endl;
		iterator++;
	}
	return 0;
}

       你会发现，明明是不连续的空间，但是仍然可以使用 迭代器++ 的方式进行遍历，这就是迭代器的好处。让代码更加统一。

下面是我自己实现的list_iterator代码：

 
namespace sslx
{
	// 像指针一样的对象
	template<class T, class Ref, class Ptr>
	struct __list_iterator
	{
		typedef list_node<T> Node;
		typedef __list_iterator<T, Ref, Ptr> iterator;
 
		typedef bidirectional_iterator_tag iterator_category;
		typedef T value_type;
		typedef Ptr pointer;
		typedef Ref reference;
		typedef ptrdiff_t difference_type;
 
 
		Node* _node;
		__list_iterator(Node* node)
			:_node(node)
		{}
 
		bool operator!=(const iterator& it) const
		{
			return _node != it._node;
		}
 
		bool operator==(const iterator& it) const
		{
			return _node == it._node;
		}
 
		// *it  it.operator*()
		// const T& operator*()
		// T& operator*()
		Ref operator*()
		{
			return _node->_data;
		}
		//T* operator->() 
		Ptr operator->()
		{
			return &(operator*());
		}
 
		// ++it
		iterator& operator++()
		{
			_node = _node->_next;
			return *this;
		}
 
		// it++
		iterator operator++(int)
		{
			iterator tmp(*this);
			_node = _node->_next;
			return tmp;
		}
 
		// --it
		iterator& operator--()
		{
			_node = _node->_prev;
			return *this;
		}
 
		// it--
		iterator operator--(int)
		{
			iterator tmp(*this);
			_node = _node->_prev;
			return tmp;
		}
	};
}