迭代器iterator是什么?
对于迭代器的理解可以从以下两个角度去剖析
“指针”对全部c/c 的程序猿来说，一点都不陌生。
在接触到c语言中的malloc函数和c 中的new函数后。我们也知道这两个函数返回的都是一个指针。
该指针指向我们所申请的一个“堆”。提到“堆”。就不得不想到“栈”。
从c/c 程序设计的角度思考，“堆”和“栈”最大的差别是“栈”由系统自己主动分配而且自己主动回收，
而“堆”则是由程序猿手动申请。
而且显示释放。假设程序猿不显示释放“堆”。便会造成内存泄漏。
内存泄漏的危害大家知道，严重时会导致系统崩溃。
既然“指针”的使用者一不小心就可能导致内存泄漏，
那么我们怎样可以使得指针的使用变得更安全呢？
从c 面向对象的角度分析，
我们有没有可能将“指针”封装起来，
使得用户不直接接触指针，
而使用一个封装后的对象来替代指针的操作呢？
答案是显然的，“智能指针”(smart pointer)正解决这类问题，
尤其是在防止内存泄漏方面做得很突出。
c 标准库std中提供了一种“智能指针类”名为"auto_ptr"，先看以下的代码：
void f()
{
int *p=new int(42);
//此处发生异常//
delete p;
}
迭代器是一种智能指针
正如上面的代码所看到的。
假设在两条语句中间发生异常，会导致指针p所指的那块内存泄漏。
由于在执行delete之前发生异常，就不会自己主动释放堆。
然而。假设使用auto_ptr对象取代常规指针，将会自己主动释放内存，由于编译器可以保证提前执行其析构函数。
这样，我们就行将上述代码改为：
#include//auto_ptr的头文件
void f()
{
auto_ptrp(new int (42));
} 通过以上的分析。我们便对智能指针有了一定的了解。
迭代器iterator就是一种智能指针。它对原始指针进行了封装，
而且提供一些等价于原始指针的操作，做到既方便又安全。
迭代器是一种连接容器和算法的桥梁
为什么呢？我们举个样例来说明原因。
#include
#include//用到find函数
#include
using namespace std;
int main()
{
vectorvec;
int i;
for(i=0;i<10;i )
{
vec.push_back(i);
}
if(vec.end()!=find(vec.begin(),vec.end(),7))
{
cout<<"find!"<
上述代码中。值得注意的是用到的find函数，
find函数的函数原型为：template _init find(_init _first, _init _last, const _ty & _val),
从find函数原型能够看出find函数是一个函数模板，函数的形參中前两个參数为_init。
该參数是inputiterator的缩写。最后一个參数则是一个随意类型变量的引用。
而我们的程序在使用find函数实。传入的实參为find(vec.begin(),vec.end(),7)。
这样我们的形參迭代器就将算法find和容器vector联系起来了，
从这个角度我们能够非常easy理解为什么说迭代器是算法和容器的联系的桥梁了。
由于迭代器是一种行为类似指针的对象，也就说迭代器是一种广义指针，
即迭代器对解除引用操作（operator*）和访问成员操作（operator->）进行重载。
然而要对这两个操作符进行重载，对容器内部对象的数据类型和存储结构有所了解，
于是在 stl 中迭代器的最终实现都是由容器本身来实现的，每种容器都有自己的迭代器实现
迭代器iterator 提供了一种一般化的方法对顺序或关联容器类型中的每个元素进行连续访问
例如，假设iter为任意容器类型的一个iterator，则 iter 表示向前移动迭代器使其指向容器的下一个元素，
而*iter 返回iterator 指向元素的值，每种容器类型都提供一个begin()和一个end()成员函数。
begin()返回一个iterator 它指向容器的第一个元素
end()返回一个iterator 它指向容器的末元素的下一个位置
1.迭代器的分类
在stl中，迭代器主要分为5类。
各自是：输入迭代器、输出迭代器、前向迭代器、双向迭代器和随机訪问迭代器。
每种迭代器均可进行包括表中前一种迭代器可进行的操作。
输入迭代器和输出迭代器是最低级的迭代器。后三种迭代器都是对该迭代器的一种派生，
这五类迭代器的从属关系，如下图所示，
其中箭头a→b表示，a是b的强化类型，这也说明了如果一个算法要求b，那么a也可以应用于其中。
input（输入）迭代器
只能一次一个向前读取元素，按此顺序一个个传回元素值。表2.1列出了input迭代器的各种操作行为。input迭代器只能读取元素一次，如果你复制input迭代器，并使原input迭代器与新产生的副本都向前读取，可能会遍历到不同的值。纯粹input迭代器的一个典型例子就是“从标准输入装置（通常为键盘）读取数据”的迭代器。
表达式 功能表述
*iter 读取实际元素
iter->member 读取实际元素的成员（如果有的话）
iter 向前步进（传回新位置）
iter 向前步进（传回旧位置）
iter1 == iter2 判断两个迭代器是否相同
iter1 != iter2 判断两个迭代器是否不相等
type(iter) 复制迭代器（copy 构造函数）
output（输出）迭代器
output迭代器和input迭代器相反，其作用是将元素值一个个写入。表2.2列出output迭代器的有效操作。operator*只有在赋值语句的左手边才有效。output迭代器无需比较（comparison）操作。你无法检验output迭代器是否有效，或“写入动作”是否成功。你唯一可以做的就是写入、写入、再写入。
表达式 功能表述
*iter = value 将元素写入到迭代器所指位置
iter 向前步进（传回新位置）
iter 向前步进（传回旧位置）
type(iter) 复制迭代器（copy 构造函数）
forward（前向）迭代器
forward迭代器是input迭代器与output迭代器的结合，具有input迭代器的全部功能和output迭代器的大部分功能。表2.3总结了forward迭代器的所有操作。forward迭代器能多次指向同一群集中的同一元素，并能多次处理同一元素。
表达式 功能表述
*iter 存取实际元素
iter->member 存取实际元素的成员
iter 向前步进（传回新位置）
iter 向前步进（传回旧位置）
iter1 == iter2 判断两个迭代器是否相同
iter1 != iter2 判断两个迭代器是否不相等
type() 产生迭代器（default构造函数）
type(iter) 复制迭代器（copy构造函数）
iter1 == iter2 复制
bidirectional（双向）迭代器
bidirectional（双向）迭代器在forward迭代器的基础上增加了回头遍历的能力。
换言之，它支持递减操作符，用以一步一步的后退操作。
p 后置自增迭代器
p 前置自增迭代器
--p 前置自减迭代器
p-- 后置自减迭代器
random access（随机存取）迭代器
random access迭代器在bidirectional迭代器的基础上再增加随机存取能力。
因此它必须提供“迭代器算数运算”（和一般指针“指针算术运算”相当）。
也就是说，它能加减某个偏移量、能处理距离（differences）问题，并运用诸如<和>的相互关系操作符进行比较。
以下对象和型别支持random access迭代器：
- 可随机存取的容器（vector, deque）
-
strings（字符串，string，wstring）
-
一般array（指针）
p 后置自增迭代器
p 前置自增迭代器
p =i 将迭代器递增i位
p-=i 将迭代器递减i位
p i 在p位加i位后的迭代器
p-i 在p位减i位后的迭代器
p[i] 返回p位元素偏离i位的元素引用
p p<=p1 p的位置在p1的前面或同一位置时返回true，否则返回false
p>p1 如果迭代器p的位置在p1后，返回true，否则返回false
p>=p1 p的位置在p1的后面或同一位置时返回true，否则返回false
迭代器相关算法函数
- advance(p, n)：使迭代器 p 向前或向后移动 n 个元素。
- distance(p, q)：计算两个迭代器之间的距离，即迭代器 p 经过多少次 操作后和迭代器 q 相等。如果调用时 p 已经指向 q 的后面，则这个函数会陷入死循环。
- iter_swap(p, q)：用于交换两个迭代器 p、q 指向的值。
各个容器支持的迭代器
list提供的是bidirectionaliterator，
set和map提供的 iterators是 forwarditerator，
关于stl中iterator迭代器的操作如下：
只有顺序容器和关联容器支持迭代器遍历，各容器支持的迭代器的类别如下：
容器 支持的迭代器类别
vector 随机访问
deque 随机访问
set 双向
multimap 双向
multiset 双向
list 双向
map 双向
queue 不支持
stack 不支持
现在我们可以回答一个问题, 为什么上面的find函数形參是一个inputiterator，却可以接受实參vec.begin()
这是因为派生类对象能够作为实參传递给以基类类型作为形參的函数。
所以find函数中的vec.begin()作为实參，以输入迭代器类型作为形參，两者能够达到虚实相结合的目的而不会出错。
所以说。迭代器为各类算法和和各类容器提供了一个相互沟通的平台。
容器的迭代器都是定身制作的，什么意思呢？全部容器都内置一个迭代器。该内置迭代器由容器的设计者实现。
因为现有的容器比較多，不可能每种容器的迭代器都具体介绍下。
可是有一点能够确定的是，每一个容器相应的迭代器都是依据容器的特点来实现的，以求达到最高效率。
一个小问题
迭代器 it,it 哪个好，为什么
1)前置返回一个引用，后置返回一个对象
// i实现代码为：
int& operator ()
{
*this = 1;
return *this;
}
2)前置不会产生临时对象，后置必须产生临时对象，临时对象会导致效率降低
//i 实现代码为：
int operator (int)
{
int temp = *this;
*this;
return temp;
}
2.迭代器的失效
迭代器失效指的是迭代器原来所指向的元素不存在了或者发生了移动，此时假设不更新迭代器，将无法使用该过时的迭代器。
迭代器失效的根本原因是对容器的某些操作改动了容器的内存状态（如容器又一次载入到内存）或移动了容器内的某些元素。
使vector迭代器失效的操作
1.向vector容器内加入元素(push_back,insert)
向vector容器加入元素分下面两种情况：
1）若向vector加入元素后，整个vector又一次载入。即前后两次vector的capacity()的返回值不同一时候，此时该容器 内的全部元素相应的迭代器都将失效。
2）若该加入操作不会导致整个vector容器载入，则指向新插入元素后面的那些元素的迭代器都将失效。
2,删除操作(erase,pop_back,clear)
vector运行删除操作后，被删除元素相应的迭代器以及其后面元素相应的迭代器都将失效。
3.resize操作：调整当前容器的size
调整容器大小对迭代器的影响分例如以下情况讨论：
a.若调整后size>capacity，则会引起整个容器又一次载入，整个容器的迭代器都将失效。
b.若调整后size
b1.若调整后容器的size>调整前容器的size，则原来vector的全部迭代器都不会失效。
b2.若调整后容器的size<调整前容器的size，则容器中那些别切掉的元素相应的迭代器都将失效。
4.赋值操作(v1=v2 v1.assign(v2))
会导致左操作数v1的全部迭代器都失效，显然右操作数v2的迭代器都不会失效。
5.交换操作(v1.swap(v2))
因为在做交换操作时。v1,v2均不会删除或插入元素，所以容器内不会移动不论什么元素。故v1,v2的全部迭代器都不会失效。
使deque迭代器失效的操作
1.插入操作（push_front,push_back,insert)
deque的插入操作对迭代器的影响分两种情况：
a.在deque容器首部或尾部插入元素不会是不论什么迭代器失效；
b.在除去首尾的其它位置插入元素会使该容器的全部迭代器失效。
2.删除操作
a.在deque首、尾删除元素仅仅会使被删除元素相应的迭代器失效；
b.在其它不论什么位置的删除操作都会使得整个迭代器失效。
使list/map/set迭代器失效的操作
因为list/map/set容器内的元素都是通过指针连接的。list实现的数据结构是双向链表，而map/set实现的数据结构是红黑树，故这些容器的插入和删除操作都只需更改指针的指向，不会移动容器内的元素。故在容器内添加元素时，不会使不论什么迭代器失效，而在删除元素时，只会使得指向被删除的迭代器失效。
3.迭代器的设计
stl的设计原理核心是利用了c 的traits技术
traits比较晦涩不好懂,这里有几篇篇讲解比较好的博客
神奇的traits
了解了什么是traits之后,我们再来上源码,把讲解放在注释里
#include
#include//ptrdiff_t相应的头文件
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{};//随机訪问迭代器
//std::iterator,标准迭代器的类模板
template
struct iterator//迭代器包括五个经常使用属性
{
typedef category iterator_category;//迭代器的类型，五种之中的一个
typedef t value_type;//迭代器所指向的元素的类型
typedef distance difference_type;//两个迭代器的差值
typedef pointer pointer;//迭代器的原始指针
typedef reference reference;//迭代器所指向元素的引用
};
//定义iterator_traits，用于提取迭代器的属性,该类的对象不应该让用户看到
template
struct iterator_traits
{
//以下的操作相当于一个递归的操作。用于递归提取原始指针的相关值
typedef typename iterator::iterator_category iterator_category;
typedef typename iterator::value_type value_type;
typedef typename iterator::difference_type difference_type;
typedef typename iterator::pointer pointer;
typedef typename iterator::reference reference;
};
//针对原始指针的偏特化版本号
template
struct iterator_traits
{
//相当于递归终止条件
typedef random_access_iterator_tag iterator_category;
typedef t value_type;
typedef ptrdiff_t diffrence_type;
typedef t* pointer;
typedef t& reference;
};
//针对指向经常使用的原始指针设计的偏特化版本号
template
struct iterator_traits
{
typedef random_access_iterator_tag iterator_category;
typedef t value_type;
typedef ptrdiff_t diffrence_type;
typedef const t * pointer;//重点在这里
typedef const t & reference;//还有这里
};
//定义两个迭代器的差值类型的函数distance_type
template
inline typename iterator_traits::difference_type *
distance_type(const iterator&)
{
return static_cast::difference_type *>(0);
}
//获取迭代器的value_type函数
template
inline typename iterator_traits::value_type *
value_type(const iterator&)
{
return static_cast::value_type*>(0);
}
//求两个一般迭代器之间的距离的函数_distance,供distance函数分类调用
template
inline typename iterator_traits::difference_type
_distance(inputiterator first,inputiterator last,input_iterator_tag)
{
typename iterator_traits::difference_type n=0;
while(first!=last)
{
first;
n;
}
return n;
}
//求两个随机訪问迭代器之间的距离的函数_distance，供distance函数分类调用
template
inline typename iterator_traits::difference_type
_distance(randomaccessiterator first,randomaccessiterator last,
random_access_iterator_tag)
{
return last-first;
}
//自适应地调用distance函数
template
inline typename iterator_traits::difference_type
distance(inputiterator first,inputiterator last)
{
typedef typename iterator_traits::iterator_category category;
//从typename能够看出。category是一个类型
return _distance(first,last,category());//显示调用category类的构造函数，返回该类的一个对象
}
/*****以下的函数用于将指针移动n位的方法*/
//一般迭代器求向前移动的方法，与双向迭代器和随机反问迭代器不同
template
inline void _advance(inputiterator& i,distance n,input_iterator_tag)
{
while(n--)
{
i;
}
}
//针对双向迭代器移动的方法
template
inline void _advance(bidirectionaliterator &iter,distance n,
bidirectional_iterator_tag)
{
if(n>=0)//当n大于0时。向后移动
{
while(n--)
{
iter;
}
}
else//当n小于0时，向前移
{
while(n )
{
--iter;
}
}
}
//定义随机訪问迭代器移动的方法
template
inline void _advance(randomaccessiterator &iter,distance n,
random_access_iterator_tag)
{
iter =n;
}
//自适应的调用advance函数
template
inline void advance(inputiterator &iter,distance n)
{
_advance(i,n,iterator_catetory(iter));
}
从上面的代码中不难发现，实现一个迭代器。须要做一下工作：
1.定义5类迭代器的标志类，该标志类用于实现函数的差别调用（即重载），比如求两迭代器距离函数distance(iter1,iter2,tag)。移动函数advance(iter,n,tag)。这五个标志类分别为：input_iterator_tag，output_iterator_tag。forward_iterator_tag，bidirectional_iterator_tag，random_access_iterator_tag。
2.对于每个iterator类，都必须包括5个属性，分别为：iterator_category、value_type、difference_type、pointer、reference。
3.定义一个迭代器的“属性榨汁机”iterator_traits，用于获取iterator的5中属性值。
4.定义迭代器的操作。分别为：
1） 获取iterator的标志----->iterator_category(iter)。
2）获取两迭代器差值的类型----->distance_type(iter)。
3）获取迭代器的原始类型--------->value_type(iter)；
4）求两迭代器的距离---------------->distance(iter1,iter2,tag)；
5）将迭代器移动n位------------------>advance(iter,n,tag)。
下面针对不同的容器介绍了其相应迭代器的用法
1、vector
#include
#include
int main()
{
std::vector charvector;
intx;
for(x=0; x<10; x)
charvector.push_back(65 x);
intsize = charvector.size();
for(x=0; x::iterator start = charvector.begin();
charvector.erase(start);
std::vector::iterator iter;
for(iter = charvector.begin(); iter != charvector.end(); iter )
{
std::cout << *iter;
}
std::cout << std::endl;
}
return0;
}
2、deque
#include
#include
int main()
{
std::deque chardeque;
intx;
for(x=0; x<10; x)
chardeque.push_front(65 x);
intsize = chardeque.size();
for(x=0; x::iterator start = chardeque.begin();
chardeque.erase(start);
std::deque::iterator iter;
for(iter = chardeque.begin();iter != chardeque.end(); iter )
{
std::cout << *iter;
}
std::cout << std::endl;
}
return0;
}
3、list
#include
#include
int main()
{
// create and populate the list.
intx;
std::list charlist;
for(x=0; x<10; x)
charlist.push_front(65 x);
// display contents of list.
std::cout << "original list: ";
std::list::iterator iter;
for(iter = charlist.begin();iter != charlist.end(); iter )
{
std::cout << *iter;
//char ch = *iter;
//std::cout << ch;
}
std::cout << std::endl;
// insert five xs into the list.
std::list::iterator start = charlist.begin();
charlist.insert( start, 5, 'x');
// display the result.
std::cout << "resultant list: ";
for(iter = charlist.begin();
iter != charlist.end(); iter )
{
std::cout << *iter;
//char ch = *iter;
//std::cout << ch;
}
return0;
}
4、set
#include
#include
int main()
{
// create the set object.
std::set charset;
// populate the set with values.
charset.insert('e');
charset.insert('d');
charset.insert('c');
charset.insert('b');
charset.insert('a');
// display the contents of the set.
std::cout << "contents of set: " << std::endl;
std::set::iterator iter;
for(iter = charset.begin(); iter != charset.end(); iter )
std::cout << *iter << std::endl;
std::cout << std::endl;
// find the d.
iter = charset.find('d');
if(iter == charset.end())
std::cout << "element not found.";
else
std::cout << "element found: " << *iter;
return0;
}
5、multiset
#include
#include
int main()
{
// create the first set object.
std::multiset charmultiset1;
// populate the multiset with values.
charmultiset1.insert('e');
charmultiset1.insert('d');
charmultiset1.insert('c');
charmultiset1.insert('b');
charmultiset1.insert('a');
charmultiset1.insert('b');
charmultiset1.insert('d');
// display the contents of the first multiset.
std::cout << "contents of first multiset: " << std::endl;
std::multiset::iterator iter;
for(iter = charmultiset1.begin();iter != charmultiset1.end(); iter )
std::cout << *iter << std::endl;
std::cout << std::endl;
// create the second multiset object.
std::multiset charmultiset2;
// populate the multiset with values.
charmultiset2.insert('j');
charmultiset2.insert('i');
charmultiset2.insert('h');
charmultiset2.insert('g');
charmultiset2.insert('f');
charmultiset2.insert('g');
charmultiset2.insert('i');
// display the contents of the second multiset.
std::cout << "contents of second multiset: "
<< std::endl;
for(iter = charmultiset2.begin();
iter != charmultiset2.end(); iter )
std::cout << *iter << std::endl;
std::cout << std::endl;
// compare the sets.
if(charmultiset1 == charmultiset2)
std::cout << "set1 == set2";
elseif(charmultiset1 < charmultiset2)
std::cout << "set1 < set2";
elseif(charmultiset1 > charmultiset2)
std::cout << "set1 > set2";
return0;
}
6、map
#include
#include
7、multimap
#include
#include
8、stack
#include
#include
#include
int main()
{
std::stack > intstack;
int x;
std::cout << "values pushed onto stack:"<< std::endl;
for(x=1; x<11; x)
{
intstack.push(x*100);
std::cout << x*100 << std::endl;
}
std::cout << "values popped from stack:"
<< std::endl;
intsize = intstack.size();
for(x=0; x
9、queue
#include
#include
#include
int main()
{
std::queue > intqueue;
intx;
std::cout << "values pushed onto queue:"<< std::endl;
for(x=1; x<11; x)
{
intqueue.push(x*100);
std::cout << x*100 << std::endl;
}
std::cout << "values removed from queue:"<< std::endl;
intsize = intqueue.size();
for(x=0; x
10、priority_queue
#include
#include
#include
int main()
{
std::priority_queue,std::greater > intpqueue;
intx;
intpqueue.push(400);
intpqueue.push(100);
intpqueue.push(500);
intpqueue.push(300);
intpqueue.push(200);
std::cout << "values removed from priority queue:"<< std::endl;
intsize = intpqueue.size();
for(x=0; x
自己开发的容器，要有自己的迭代器，要继承有这五个部分的 typedef，才能是自己的定义与原来的一些算法更兼容。
另外，迭代器有五个类型：
inputiterator（输入迭代器）；
outputiterator（输出迭代器）；
forwarditerator（前向迭代器）；
bidirectionaliterator（双向迭代器）；
randomaccessiterator（随机迭代器）；
将迭代器分为几种类型是因为在算法中根据 traits 萃取出 的不同迭代器类型，内部可以写出更加高效合适的实现功能的代码。
iterator_traits 就像是一种萃取机，你想要什么东西，你丢给这个萃取机器，它返回给你想要的东西。萃取 iterator 的特性（为什么要这样设计？因为算法要知道，这是算法给 iterator 提出的问题！也就是说算法通过仿函数来处理容器里面的元素）