一、迭代器iterator
迭代器是容器的一种遍历方式,每种容器都定义了自己的迭代器类型
声明一个迭代器:
容器名称<数据类型>::iterator 迭代器名称
vector<int>::iterator it;
map<int,int>::iterator it;
set<int>::iterator it;
.......
使用:
for(it=vec.begin();it!=vec.end();it++)
cout<<*it;
二、vector
1、常用操作
empty():判断向量是否为空,为空返回真,否则为假
begin():返回向量(数组)的首元素地址
end(): 返回向量(数组)的末元素的下一个元素的地址
clear():清空向量
front():返回得到向量的第一个元素的数据
back():返回得到向量的最后一个元素的数据
size():返回得到向量中元素的个数
push_back(数据):将数据插入到向量的尾部
pop_back():删除向量尾部的数据
.....
2、遍历方式
vector向量支持两种方式遍历,因为可以认为vector是一种动态数组,所以可以使用数组下标的方式,也可以使用迭代器
3、二维动态数组
4、vector与结构体的使用
struct node { int id; int g[4]; int rank[4]; }; int x;//对第几门学科进行排序 bool cmp(node a,node b) { return a.g[x]>b.g[x]; } vector<node>v(n);//注意是括号,n是容器大小--结构体数组 sort(v.begin(),v.end(),cmp);//按照第x门学科的成绩对每个人排序
#include <iostream> #include <vector> #include <list> #include <map> using namespace std; int main(void) { vector<int> vec; vec.push_back(1); vec.push_back(2); vec.push_back(3); vec.push_back(4); vec.push_back(5); cout << "向量的大小:" << vec.size() << endl; // 数组下标方式遍历vector for (int i = 0; i < vec.size(); i++) cout << vec[i] << " "; cout << endl; // 迭代器方式遍历vector vector<int>::iterator itor = vec.begin(); for (; itor != vec.end(); itor++) cout << *itor << " "; cout << endl; return 0; }
三、map
map是STL 的一个关联容器,它提供一对一的数据处理能力(键-值:其中第一个可以称为关键字(first) ,每个关键字只能在map中出现一次,第二个可能称为该关键字的值(second) ),由于这个特性,它完成有可能在我们处理一对一数据的时候,在编程上提供快速通道。
map会根据键值自动按字典序排序
1、常用操作
2、遍历方式
map支持数组下标和迭代器两种遍历方式
1、数组 用一个for循环遍历map,遍历的时候要注意键和值的数据类型 2、迭代器 map<int,string>::iterator it; for(it=m.begin();it!=m.end();it++) { //first-键 second-值 cout<<it->first<<‘ ‘<<it->second;
提示:map映射的建可以是string类型,map<string ,int>m是合法的。eg:string s="ABC", m[s]=1;
四、set集合
集合(set)是一个容器,它其中所包含的元素的值是唯一的,会把存入的元素自动排序和去重
头文件 #include<set>
声明一个set集合: set<数据类型>名字 可以开成数组使用
1、基本操作
注意:这里的p.begin()和p.rbegin()可以直接当指针来用
#include<iostream> #include<set> using namespace std; set<int>p; int main() { for(int i=0;i<5;i++) p.insert(i); //输出set的第一个值和最后一个值 cout<<*p.begin()<<endl; cout<<*p.rbegin()<<endl; //删除set的第一个值和最后一个值 set<int>::iterator it=p.end(); p.erase(p.begin()); p.erase(--it); cout<<*p.begin()<<endl; cout<<*p.rbegin()<<endl; return 0; }
2、遍历方式
set不支持下标操作,只能用迭代器遍历
五、multiset
操作和set一样,功能上有所不同,multiset会对数据自动排序,但是不会去重
六、pair
pair是将2个数据组合成一组数据,当需要这样的需求时就可以使用pair,如stl中的map就是将key和value放在一起来保存。区别在pair不会对数据自动排序。另一个应用是,当一个函数需要返回2个数据的时候,可以选择pair。 pair的实现是一个结构体,主要的两个成员变量是first和 second
头文件:#include<utility>
声明:
pair<数据类型,数据类型> 名字 可以开成数组
功能:
pair将一对值(T1和T2)组合成一个值,
这一对值可以具有不同的数据类型(T1和T2),
两个值可以分别用pair的两个公有函数first和second访问。
使用方法和结构体一样,可以直接赋值
pair<int,int>p[200005]; p[0].first=1; p[0].second=2; ......
在vector中使用pair
#include<iostream> #include<vector> #include<utility> using namespace std; vector<pair<int,int>>v;//其实和直接开成数组形式一样 pair<int,int>p[205]; int main() { int n; scanf("%d",&n); for(int i=0;i<n;i++) { int x,y; scanf("%d%d",&x,&y); v.push_back(make_pair(x,y)); } vector<pair<int,int>>::iterator it; for(it=v.begin();it!=v.end();it++) cout<<it->first<<' '<<it->second<<endl; return 0; }
七、unordered_map
unordered_map是无序的map,它的底层实现是哈希表,把键经过哈希处理作为索引,构建的一个数组+链表的结构,map插入和查询的时间复杂度为O(lgn)
unordered_map的插入和查找的时间复杂度为O(1)
头文件是#include<unordered_map>
使用和map基本一致
#include <iostream> #include<unordered_map> using namespace std; unordered_map<string, string>mp; int main() { mp["123"] = "abs"; mp["456"] = "dfg"; mp["789"] = "ert"; cout << mp.size() << endl; cout << mp.count("123") << endl; unordered_map<string, string>::iterator iter; for (iter = mp.begin(); iter != mp.end(); iter++) cout << iter->first << " " << iter->second << endl; return 0; }
八、list
List是STL中常用的容器之一,List将元素按顺序储存到链表中,在快速删除和快速插入方面比vector高出许多。STL中的list是一双向链表,具有指向前一节点和后一节点的指针。
#include<iostream> #include<list> using namespace std; int main() { list<int>p; //在链表前面添加元素 p.push_front(1); p.push_front(2); //在链表后面添加元素 p.push_back(0); p.push_back(0); //返回最后一个元素 cout << p.back() << endl; //返回第一个元素 cout << p.front() << endl; //删除最后一个元素 p.pop_back(); //删除第一个元素 p.pop_front(); //返回list中元素的个数 cout << p.size() << endl; //返回list的容量大小 cout << p.max_size() << endl; //迭代器遍历元素 { list<int>::iterator iter; for (iter = p.begin(); iter != p.end(); iter++) cout << *iter << endl; } { //在list的某个位置插入 p.insert(p.begin(), 9); list<int>::iterator iter2; for (iter2 = p.begin(); iter2 != p.end(); iter2++) cout << *iter2 << endl; } { //在list的某个位置删除元素 p.erase(p.begin()); list<int>::iterator iter3; for (iter3 = p.begin(); iter3 != p.end(); iter3++) cout << *iter3 << endl; } return 0; }