c++ stl 容器 迭代器 stl用法示例

1.基本概念

1.1容器概述

顺序容器 vector, deque,list关联容器 set, multiset, map, multimap容器适配器 stack, queue, priority_queue

1.1.1迭代器

用于指向顺序容器和关联容器中的元素迭代器用法和指针类似 有const 和非 const两种通过迭代器可以读取它指向的元素通过非const迭代器还能修改其指向的元素

1.1.2顺序容器:

容器并非排序的，元素的插入位置同元素的值无关。

1.1.3关联容器:

元素是排序的插入任何元素，都按相应的排序规则来确定其位置在查找时具有非常好的性能 通常以平衡二叉树方式实现，插入和检索的时间都是 O(log(N))相互关系：map与set的不同在于map中存放的元素有且仅有两个成员变量，一个 名为first,另一个名为second, map根据first值对元素进行从小到大排序， 并可快速地根据first来检索元素

map同multimap的不同在于是否允许相同first值的元素

set 即集合。set中不允许相同元素，multiset中允许存在相同的元素。

1.1.4顺序容器和关联容器中都有的成员函数

begin返回指向容器中第一个元素的迭代器end返回指向容器中最后一个元素后面的位置的迭代器rbegin返回指向容器中最后一个元素的迭代器rend返回指向容器中第一个元素前面的位置的迭代器erase从容器中删除一个或几个元素clear从容器中删除所有元素front:返回容器中第一个元素的引用back: 返回容器中最后一个元素的引用push_back: 在容器末尾增加新元素pop_back: 删除容器末尾的元素erase:删除迭代器指向的元素(可能会使该迭代器失效），或删 除一个区间，返回被删除元素后面的那个元素的迭代器

1.2为什么定义迭代器？

迭代器上可以执行 ++ 操作, 以使其指向容器中的下一个元素。如果迭代器到达了容器中的最后一个元素的后面，此时再使用它，就会出错，类似于使用NULL或未初始化的指针一样。

1.3怎么定义并使用迭代器？

定义一个容器类的迭代器的方法可以是：

容器类名::iterator 变量名;

或： 容器类名::const_iterator 变量名;

访问一个迭代器指向的元素： * 迭代器变量名

#include<iostream>#include<vector>using namespace std;int main(){vector<int> t;for(int i=1;i<10;++i){t.push_back(i);} vector<int>::const_iterator i;for( i=t.begin();i!=t.end();++i){cout<<*i;//输出123456789 }}

1.4容器上的迭代器类别

vector 随机访问deque 随机访问list 双向set/multiset 双向map/multimap 双向stack 不支持迭代器queue 不支持迭代器priority_queue 不支持迭代器

不同类别有区别？

有

1.4.1双向迭代器

若p和p1都是双向迭代器，则可对p、p1可进行以下操作：

++p, p++ 使p指向容器中下一个元素–p, p-- 使p指向容器中上一个元素*p 取p指向的元素p == p1 , p!= p1 判断是否相等、不等（list的一种遍历方法）

1.4.2随机访问迭代器

若p和p1都是随机访问迭代器，则可对p、p1可进行以下操作：

双向迭代器的所有操作

p += i 将p向后移动i个元素p -= i 将p向向前移动i个元素p + i 值为: 指向 p 后面的第i个元素的迭代器p - i 值为: 指向 p 前面的第i个元素的迭代器p[i] 值为:p后面的第i个元素的引用p < p1, p <= p1, p > p1, p>= p1 （多种遍历方法！！）p – p1 : p1和p之间的元素个数

2.stl用法

stl有什么用？

有了STL，不必再写大多的标准数据结构和算法，并且可获得非常高的性能。

STL中提供能在各种容器中通用的算法，比如查找，排序等算法通过迭代器来操纵容器中的元素。许多算法可以对容器中的一个 局部区间进行操作，因此需要两个参数，一个是起始元素的迭代器， 一个是终止元素的后面一个元素的迭代器。比如，排序和查找有的算法返回一个迭代器。比如 find() 算法，在容器中查找一个元素， 并返回一个指向该元素的迭代器

2.1算法示例：find()

template< class InIt, class T>

InIt find(InIt first, InIt last, const T& val);

find在[first,last)查找等于val的元素

用 == 运算符判断相等

函数返回值是一个迭代器。如果找到，则该迭代器指向被找到的元素。 如果找不到，则该迭代器等于last

#include<iostream>#include<vector>#include<algorithm>using namespace std;int main(){int array[101],a;vector<int> v;vector<int>::iterator p;cin>>a;for(int i=0;i<a;++i){cin>>array[i];} int *pp=find(array,array+a,20);if(pp!=array+a)cout<<*pp<<endl;else cout<<"not found"<<endl;for(int i=0;i<a;++i){v.push_back(array[i]);}p=find(v.begin(),v.end(),20);if(p!=v.end())cout<<*p<<endl;else cout<<"not found"<<endl;}

用数组都能写啊，何必用容器呢？

当你想要从某个位置插入或删除一个数的时候，用数组就很麻烦，但是用vector就很方便了，而且他是可变长的，那也就不用考虑越界的问题了。

2.2vector用法实例：

#include<iostream>#include<vector>#include<algorithm>using namespace std;template<class T>void printvector(T s,T e){for(; s!=e ;++s)cout<<*s<<" ";cout<<endl;}int main(){vector<int>::iterator p;int a[101],n,b;cin>>n;for(int i=0;i<n;++i){cin>>a[i]; }vector<int> v(a,a+n);cout<<v.end()-v.begin()<<endl;//1.求容器里有多少个数 v.insert(v.begin()+2,100);//2.在v.begin()+2这个位置插入一个数 printvector(v.begin(),v.end());v.erase(v.begin()+2);//3.删除v.begin()+2这个位置的数 printvector(v.begin(),v.end());vector<int>v2(5,1000);//4.建立一个由五个1000组成的容器 printvector(v2.begin(),v2.end());v2.insert(v2.begin(),v.begin()+1,v.begin()+3);//5.将v.begin()+1到v.begin()+3的数插入到v2.begin()这个位置上 // 输出时输出所有v2，只不过开头增加了一段数。 printvector(v2.begin(),v2.end());v.erase(v.begin() + 1, v.begin() + 3); //6.删除一段区间 printvector(v.begin(),v.end());} //输入： //5//1 2 3 4 5//输出： //5//1 2 100 3 4 5//1 2 3 4 5//1000 1000 1000 1000 1000//2 3 1000 1000 1000 1000 1000//1 4 5

所有适用于 vector的操作都适用于 deque。

deque还有 push_front（将元素插入到前面） 和 pop_front(删除最前面的元素）操作，复杂度是O(1)