|
这章部分内容之前学过了就不重复去记了。
加粗的部分是用的比较频繁的几种东西。
VECTOR
（动态数组)
用法
初始化方面：
类型1：vector<data_type> name(size)
类型2：vector<data_type> name(size,value)
类型3：vector<data_type> name
类型4：vector<data_type> name(name2)/定义/
类型5：vector<data_type> name(name2.begin(),name2.end())/复制/
访问方面：
关键字：
push_back(value)/末尾插入/
size()/返回大小/
empty()
insert(a.begin()+i,number,value)/第i元素前插入number个value/
reverse（a.begin()+i,a.begin()+j）/反转数组区间 i 到 j，隶属于algorithm,调用时注意/
a.clear()
a.erase(a,begin()+i,a.begin()+j)/删除i到j-1的元素/
a.erase(a.begin()+i)/删除第i+1个元素/
注意点：
1.初始化规定的大小如果是够用的，那么vector可以使用与普通array的操作，一旦超出了界限那么就要用push_back(value)来进行压入元素。
2.没有一开始在初始化规定好的空间为空但是不为0，一开始规定好的空间内部默认value为0
3.在使用有下标定位的关键字时可见，除了insert这个操作是对下标i-1进行的操作，其余的所有都是对着下标i进行的操作，这一点要注意。
4.动态数组要从第一个开始赋值
实际应用/书中原题/
解题 hdu4841 圆桌问题
简述：
一个圆桌2n个人围坐，n好人，n坏人。
目标：赶走全部坏人。
赶走方式：从第一个人开始数到第m个赶走，在数到第m个再赶走。
输入:n m的数值
输出：好人（G）坏人（B）的排列方式。
简析：
题目类型：模拟+vector
解题方法
#include <iostream>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
int main()
{
vector <int> a;
int n,m,pos=0;
cin>>n>>m;
for(int i=0;i<2*n;i++)
{
a.push_back(i);
}
for(int i=0;i<n;i++)
{
pos=(pos+m-1)%(a.size());
a.erase(a.begin()+pos);
}
pos=0;
for(int i=0;i<2*n;i++)
{
if(a[pos]==i&&pos<a.size())
{
pos++;
cout<<"G"<<endl;
}
else
{
cout<<"B"<<endl;
}
}
}
Q：为何适用动态数组？
A：可见我们每一次赶走坏人都会让圆桌的大小-1，那么我们开的数组大小始终在变化，而在数1到m赶人的过程又是取决于m和圆桌的大小的所以采用动态数组比较方便。
Q：pos为何是从0开始？
A：pos的作用是记录下标，间接决定是那个被赶走（清除），动态数组的下标是从0开始。
Q：为什么取模的时候用的是a.size()而不是2*n。
A：取余是模拟圆桌赶人的过程，圆桌大小在变，取余就相当于走了圆桌一圈，大小变了肯定取余的a.size()也要变化。
STACK（单开口容器）
用法
初始化方面：
类型1：stack<data_type>s
访问方面：
关键字：
push(value)
top()/返回顶端值/
pop()/删除顶端值/
size()
empty()
QUEUE（双开口容器）
用法
初始化方面：
queue <data_type> name
访问方面：
关键字：
push（value）
front()/类比STACK的top/
pop()/类比STACK的pop/
back()/返回队尾元素/
size()
empty()
priority_queue（优先队列）
与queue不同的方面：
1.访问上原本queue的关键front用于返回队首/第一个进入的/现在用top返回队顶元素/根据优先排出的顶部元素/
2.pop原本是删除队首元素，现在删除的是根据优先排出的顶部元素
注：不难看出优先队列就是把最优先元素放到了队首的特殊队列，假如习大大去排队，大家都愿意让他先办事以免耽误他的时间去处理更重要的事，那么他自然就是队首了。
3.实现方式是二插堆/时间复杂度log2n/
实例：
之前的一个题：
1.n个物体两两碰撞后变为一个物体，碰撞后质量按规则改变.
2.规则是质量变为sqrt（m1*m2）
3.求怎样碰撞让最终的物体质量最大
解题：每次让质量最大的两个碰撞就好
特点：动态变化，每次“质量最大的两个物体”不确定
核心代码
#include <stack>
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main()
{
priority_queue<int> q;
int max1,max2;
while(q.size()>=2)
{
max1=q.top();
q.pop();
max2=q.top();
q.pop();
q.push(sqrt(max2*max1));
if(q.size()==1)
{
cout<<q.top()<<endl;
break;
}
}
return 0;
}
LIST（空间上不连续分布的数组）
初始化上可以类比vector
使用上用指针来访问内部元素
list <data_type> l :: iterator name
与vector的不同：
1.从使用上看vector作为连续空间不希望频繁的插入insert和删除eraser，但是可以高效率的进行元素查看和获取，而list作为不连续空间，可以很好的处理insert和eraser，但由于是通过指针来访问内部元素所以不能精准的进行随机访问。
MAP
这是个非常常用也很实用的东西
一.关于map的性质
map是Stl的一个容器，他有两个性质：
1.可以提供任意类型下表（key）对应任意类型值（value）的关联。
关于第一个性质
类比数组，数组是一个整数下标对应一个任意类型的值，而map就是一个任意类型的下标对应了一个任意类型的值。
2.key是唯一的不可重复（这是为map的不可重复性）
关于第二个性质
这个要记住，你已经插入的key不可以通过insert的方式来覆盖更新这个key对应的值（insert后面说）。
二.关于map的遍历操作
关于 map<int,任意类型>maps这种以int为key，任意值为value的可以正常遍历
当key值变化为其他类型呢？
你是无法，，至少不方便去写个循环来遍历整个map容器，这个时候就需要我们的救星—— 迭代器
#include<bits/stdc++.h>
using namespace std;
int main()
{
map<string,int>maps;
int n;
for(cin>>n;n;n--)
{
string s;
cin>>s;
maps[s]++;
}
for(map<string,int>::iterator iter=maps.begin();iter!=maps.end();iter++)
{
cout<<iter->first<<" "<<iter->second<<endl;
}
}
next_permutation()（按字典序对原序列进行全排列）
用的比较多
语法：
next_permutation(begin,last)
注意：
1.操作范围是【begin，last)
2.操作范围内应该最初是字典序最小序列
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t,m,n;
vector<int>a;
for(cin>>t;t;t--)
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
a.push_back(i);
}
int con=1;
do
{
if(con==m)
{
break;
}
con++;
}
while(next_permutation(a.begin(),a.end()));
for(int i=0;i<a.size();i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
}
return 0;
}
最后说一下这个初始状态是字典序最小
1.当然初始状态可以不是，它会自动产生下一个排列，但是大多数时候你并不知道至少没法一眼看出这个是第几大字典序排列，所以初始状态是字典序最小的话一个方便了后期操作，另一个也方便观察。
2.可以用sort来达到字典序最小的目的
|