C++ 迭代器

1.用途：

像我们之前学习的容器map,vector等，如果需要遍历该怎么做呢？这些容器大部分对下标式遍历，无法像数组灵活使用，也包括增删改查，因为它们的特性，所以需要一种其他的方法。

那么迭代器就是一种很好的替代方法。

(注意有些也可使用下标的方法，因为重载了[]操作符，这里不做过多说明，建议用迭代器进行操作）

迭代器有一组通用的方法，以便它们能在不同的容器都能使用。

迭代器的本质是一个类，封装了元素的指针(也可以是引用等),可以看作是对指针的一种封装，然后在这个类里重载了* -> ++等指针相关的操作符，使其模仿指针的行为，表面上像指针一样使用。

如果有时候你不能理解某种情况，你可以试着把迭代器当成指针(仅为便于理解)

下面我们来看一下具体用法。

1.1访问元素

begin方法，返回容器中第一个元素的迭代器。

end方法，容器中最后一个元素的后一个迭代器（非最后一个元素的迭代器）

示例：

#include<iostream>
#include<vector>
using namespace std;
int main()
{vector<int> vec = { 1,2,3,4,5 };vector<int>::iterator it = vec.begin();for (; it != vec.end(); it++){cout << *it << " " ;}
}

结果：

迭代器的定义，每种类型都是不一样的，比如map的迭代器，需要指定类型，这个就跟指针一样的道理，char *p,int *p;这样，是不同的。

it++ 跟指针一样，移到下一个元素。迭代器指向下一个元素。

然后通过*it访问元素，就像指针取值一样。

1.2更改元素

#include<iostream>
#include<vector>
using namespace std;
int main()
{vector<int> vec = { 1,2,3,4,5 };vector<int>::iterator it = vec.begin();for (; it != vec.end(); it++){if (*it == 3)  //像指针的方式改值即可*it = 6;}cout << vec[2] << endl;
}

结果：

输出为6，说明正常改值。

1.3 auto

如果是map类型，使用迭代器，需要这样定义：(根据生成的类型指定)

#include<iostream>
#include<string>
#include<map>
using namespace std;
int main()
{map<int, string> mp = { {1,"one"},{2,"two"}, {3,"three"} };map<int, string>::iterator it = mp.begin();for (; it != mp.end(); it++){cout << it->first<< ":" << it->second << endl; //也可(*it).first访问，即分别是类指针 类对象访问成员的方式}}

map中每一个元素都是pair对象，pair是一个类或者结构体，里面有成员first存储键，second存储值。所以迭代器指向的是pair。

可以看到，定义迭代器时每次需要指定类型有些不便。

我们可以使用auto，类型推导关键字，即编译器会根据初始化变量，自动推导类型。

比如 auto c='b',c就是个char 变量。

这个auto当然也支持迭代器类型。如下更改即可:

	//map<int, string>::iterator it = mp.begin();auto it = mp.begin();

2.获取指针

前面说过了，迭代器是对底层是对指针的封装，我们可以获取到这个指针，以便在某些特定情况下使用。有两种常用方法：

第一种，通过*解引用，然后再&取地址。

第二种，容器的data方法，返回底层元素数组的首地址。

如下示例：

#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main()
{vector<int> vec = { 1, 2, 3, 4, 5 };//map<int, string>::iterator it = mp.begin();vector<int>::iterator it = vec.begin()+2;//获取第三个元素迭代器	int* p = &(*it); //解引用，再取地址，获取迭代器封装的指针cout << "解引用&获取方法:\n值:" << *p << "  地址:" << p << endl;int* p1 = vec.data()+2; //首地址+2,也是指向第三个元素的指针cout << "data获取方法:\n值:" << *p1 << "  地址:" << p1 << endl;}

结果：

可以看到，它们值和地址输出都一样，说明两种方法工作正常。

3.内存分配

像这些容器如vector,map等，它们的功能比数组强大的多(动态性方面)，说明它们内部不可能像数组一样。比如int a[100];这样静态分配内存在栈上。那将必然失去它们的灵活性。

所以vector map等都是动态分配内存，如使用new等分配在堆上，那么它们内部则需要一套管理内存的方法，手动分配和释放。

我们通过方法也可以参与这个过程，比如这样定义：

std::vector<int> vec(3);

容器初始化分配3个int内存空间。

通过capacity()方法，我们可以查看容器的分配的内存空间大小.

示例：

#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main()
{vector<int> vec(3);cout << vec.capacity() << endl;
}

结果：

说明这个容器，目前可以容纳三个元素。

如果此时我们调用push_back再新增一个元素，这会触发内存重新匹配，因为已经超出了容器的上限，这个会造成什么问题呢？之前的迭代器会失灵，因为封装的指针地址已经失效了，这个是需要注意的。

我们可以通过输出地址来观察这个现象：

#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main()
{vector<int> vec = { 1,2,3};auto it = vec.begin();int* p = &(*it);cout << "指针地址:" << p << "   迭代器取值:" << *it << endl;vec.push_back(4);//容器如果不够，此操作会触发内存重新分配以满足新的大小int* p1 = vec.data();//再取地址cout << "指针地址:" << p1 << endl;//此时再*it会报错，因为访问非法的内存。 需要重新获取迭代器}

结果：

两次地址不一样，说明已经重新分配。

如果要避免这种情况呢，该怎么做？提前分配好大小，如下：

#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main()
{vector<int> vec = { 1,2,3 }; //注意这种行为 看情况有些分配的空间不一定是三，而是大于三，本例仅在为三的情况下。vec.reserve(4); //通过reserve分配内存空间为4cout << "已使用内存:" << vec.size() << "   容器总内存:" << vec.capacity() << endl;auto it = vec.begin();int* p = &(*it);cout << "指针地址:" << p << "   迭代器取值:" << *it << endl;vec.push_back(4);//不会触发重新分配int* p1 = vec.data();//再取地址cout << "指针地址:" << p1 <<"   迭代器取值:" << *it << endl; //地址一样，之前迭代器也可用}

结果：