|
STL 3个部分 1、序列容器：存放数据的顺序，与存放顺序有关，与数据值无关 array：数组的类模版（数组的爸爸） deque：双向队列（与队列没什么关系），两端可进可出 vector：可变数组，无限长 以上三个容器，都是物理连续存放的线性容器（可以使用下标） forward_list：单向链表（可以操作头插头删） list：双向链表（可以操作头插尾插，头删尾删） 以上两个容器，都是非物理连续存放的线性容器（不能使用下标） 容器的创建: 容器名<类型> 变量名; list<double> l; vector<long long> v; 容器的遍历 下标遍历：for(int i=0;i<v.size();i++) cout<<v[i]; 迭代器遍历：for(auto i=l.begin();i!=l.end();i++) cout<<*i; auto 自定类型，通过i赋予的值的类型，确定auto的实际类型 i 实际是一个迭代器（指针+方向） 实际类型是list<double>::iterator i++ 下一个位置 *i 将指针i指向的值解析出来 push 存放 pop 取出 back 后 front 前 vector : push_back pop_back deque : push_back push_front pop_back pop_front forward_list : push_front pop_front list : push_back push_front pop_back pop_front size 大小 empty 是否为空 clear 清空 insert 中间插入 2、关联容器：存放数据的顺序，与存放顺序无关，与数据值有关（自动有序） 非线性结构，树形结构（方便调整大致顺序） set : 集合（自动有序，从小到大，自动去重）1223412 -> 1234 map : 映射（自动有序，根据键从小到大，自动去重，根据键去重） map的数据是成对儿的，分别是（键-值） struct p{ type1 first;//键 type2 second;//值 }; 输入一组数据，自动去重并排序输出 set<int> s; int n,a; cin>>n; while(n--){ cin>>a; s.insert(a); } for(auto i=s.begin();i!=s.end();i++){ cout<<*i; } //map<string,int> m; //map<int,char> m; 输入一组数据，不去重并排序输出 map<int,int> m;//key代表数据，value代表数据出现的次数 int n,a; cin>>n; while(n--){ cin>>a; //因为map的成对儿存放数据的，因此，key还有下标功能 m[a]++;//a这个数据对应的value+1 } for(auto i=m.begin();i!=m.end();i++){ //cout<<*i;报错 int x=i->first; int y=i->second; while(y--) cout<<x; } m[5]=7; m[5]=8;//更新原来的数据 m.insert(map<int,int>::value_type({4,9}));//正常存储 m.insert(map<int,int>::value_type({4,3}));//跳过
multimap 可重复映射 multiset 可重复集合 非关联容器 unorder 无序 unordered_set 无序不重复集合 unordered_map 无序不重复映射 unordered_multiset 无序可重复集合 unordered_multimap 无序可重复映射 3、容器适配器：栈、队列、优先队列，存取数据的顺序，有自定规则 栈：先进后出，后进先出（不能修改中间，只能操作栈顶的数组） 队列：先进先出，后进后出（不能修改中间，只能操作头尾的数组） 优先队列：随便进，最大的先出（顶上总是放最大数据的树形（大顶堆）） 6 2 4 8 8 7 3 9 9 8 8 7 出队 stack 栈 存push 删pop 取栈顶top queue 队列 存push 删pop 取队头front 取队尾back priority_queue 优先队列 存push 删pop 取队顶top empty 判断是否为空 size大小 手搓栈： //创建栈 int num=0;//在数组中实际栈的开始 int sta[10000]={},t=num,b=num;//b永恒不变，t永远指向栈顶元素的下一个位置 //存 void push(int x){ sta[t]=x; t++; } //取 void pop(){ t--; } //获取栈顶 int top(){ return sta[t-1]; } //判断栈空 bool empty(){ return t==b;//是空返回true，非空返回false } //数据数量 int size(){ return t-b; } 手搓队列： //创建队列 int num=0;//在数组中实际队列的开始 int que[10000]={},f=num,b=num;//b永远指向队尾元素的下一个位置 int maxq=100;//设定队列能存放的具体大小 //存 void push(int x){ que[b]=x; b++; //循环队列：if(maxq==b) b=num; } //取 void pop(){ f++; //循环队列：if(maxq==f) f=num; } //获取队头 int front(){ return que[f]; } //获取队尾 int back(){ return que[b-1]; } //判断队空 bool empty(){ return f==b;//是空返回true，非空返回false } //获取数量 int size(){ return b-f; //循环队列：return b>f?b-f:b+maxq-f; } 对于链表来说，每个元素（节点）都包含数据域和指针域 数据域：当前空间需要存放的数据，数据数量类型数量不唯一 指针域：当前节点与其他节点进行连接的工具，单链表一个指针，双链表两个指针 struct node{ int a; node *nxt;//指向下一个节点 node *pre;//指向上一个节点 }; head 头节点：链表中的第一个节点，原则上不可以进行修改 struct node{ int a; node *nxt; node(int n){ a=n; nxt=nullptr; } }*head=nullptr; void push_front(int n){ if(head==nullptr) head=new node(n); else{ node *p=new node(n); p->nxt=head; head->nxt=p; } } void insert(int x,int n){ node *p=head; while(p->a!=x) p=p->nxt; node *q=new node(n); q->nxt=p->nxt; p->nxt=q; } void erase(int n){ node *p=head; if(p->a==n){ head=p->nxt; delete p;//删除p指向的空间，p变成野指针 p=nullptr; } while(p->nxt->a!=n) p=p->nxt; node *q=p->nxt; p->nxt=q->nxt; delete q; q=nullptr; } 栈：四种类型题 1、进制转换问题 2、括号匹配问题: 左入右出:1353,1354,1355 () 基本操作 []() 升级版：判断类型 <([{ plus版：判断类型判断优先级 3、车厢调度 4、后缀表达式计算 队列：约瑟夫问题1334，1418 队列部分最难的题是1333 基础算法：二三四章 (责任编辑：admin) |