数据结构知识总结（STL整理）

重要知识点

1.基础知识

#include<bits/stdc++.h> //万能头文件
#include< algorithm > //包含sort函数

运用sort实现多关键字排序

bool cmp(Element a,Element b){
    if(a.s1!=b.s1){
        return a.s1>b.s1;//根据关键字s1降序
    else
        //这里可以继续嵌套判断语句实现多关键字排序
        return a.s2<b.s2;//根据关键字s2升序
}
sort(list,list+n,cmp);

c++输出格式控制

#include<iomanip>
setbase(n)//设置整数为n进制(n=8,10,16)
setprecision(n)//设置浮点数的有效数字为n位
setw(n)//设置字段宽度为n位
setfill(n)//设置字符填充，c可以是字符常或字符变量
setiosflags(ios::fixed)//设置浮点数以固定的小数位数显示
setiosflags(ios::scientific)//设置浮点数以科学计数法表示
setiosflags(ios::left)//输出左对齐
setiosflags(ios::right)//输出右对齐
setiosflags(ios::skipws)//忽略前导空格

提高cin/cout效率（防止TLE）

ios::sync_with_stdio(false);//关闭与stdio的兼容
cin.tie(0);//cin与cout解除绑定
cout.tie(0);

2. STL相关

双端队列 deque

#include<deque>//双向队列

//初始化
deque<int> a; // 定义一个int类型的双端队列a
deque<int> a(10); // 定义一个int类型的双端队列a，并设置初始大小为10
deque<int> a(10, 1); // 定义一个int类型的双端队列a，并设置初始大小为10且初始值都为1
deque<int> b(a); // 定义并用双端队列a初始化双端队列b
deque<int> b(a.begin(), a.begin()+3); // 将双端队列a中从第0个到第2个(共3个)作为双端队列b的初始值

//容器属性
deq.size();//容器大小
deq.empty();//容器判空
deq.max_size();//容器最大容量
deq.resize();//更改容器大小

//插入
deq.push_front(const T& x);//头部添加元素
deq.push_back(const T& x);//末尾添加元素
deq.insert(iterator it, const T& x);//任意位置插入一个元素
deq.insert(iterator it, int n, const T& x);//任意位置插入 n 个相同元素
deq.insert(iterator it, iterator first, iterator last);
//插入另一个向量的 [forst,last] 间的数据

//删除
deq.pop_front();//头部删除元素
deq.pop_back();//末尾删除元素
deq.erase(iterator it);//任意位置删除一个元素
deq.erase(iterator first, iterator last);//删除 [first,last] 之间的元素
deq.clear();//清空所有元素

//访问
deq[1]; //下标访问（并不会检查是否越界）
deq.at(1); //at方法访问（以上两者的区别就是 at 会检查是否越界，是则抛出 out of range 异常）
deq.front();//访问第一个元素
deq.back();//访问最后一个元素

队列queue

#include<queue> //队列
q.push(x);//x入队尾
q.pop();//弹出队首的第一个元素（注意 并不会返回被弹出元素的值）
q.front();//访问队首元素
q.back();//访问队尾元素
q.empty();//判断队列空(当队列空时，返回true)
q.size();//返回队列内元素的大小

栈stack

#include<stack>//栈
t.empty();//如果栈为空返回true，否则返回false
t.size();//返回栈内元素的大小
t.pop();//从栈顶弹出一个成员
t.push();//向栈内压入一个成员
t.top()//返回栈顶，但不删除成员

求区间第k小nth_element();

#include<algorithm>
//求区间第k小(从1开始)
nth_element(a,a+k-1,a+n);//把下标k-1放在了正确的位置（此时a[k-1]为第k小）

//求区间第k大
//(1)为区间第n-k+1小时，即为区间第k大
nth_element(a,a+n-k,a+n);
//a[n-k]为区间第k大

//(2)把函数定义为求区间第k大
//a.自定义
bool cmp(int a, int b){
    return a > b;
}
nth_element(c,c+k-1,c+n,cmp);
//b.用greater
nth_element(c,c+k-1,c+n,greater<int>());
//a[k-1]为区间第k大

可重集合multiset与不可重复set

#include<set>
//set中元素不可重复，multiset元素可重复
multiset<int> t;//定义  
set<int> t;
//常用操作
t.insert(k);//插入元素k
t.count(k);//判断元素k在容器内出现的次数（为0表示不在容器中）
t.erase(k);//删除容器中所有元素k，若不存在则删除无效
t.clear();// 清空容器
t.size();//返回容器现有元素个数
t.empty();//判断容器是否为空

//想遍历set里的元素或进行进一步修改，必须定义对应迭代器，以下三种定义方法（迭代器类似于指针）
multiset<int>::iterator it;//定义正向迭代器
multiset<int>::reverse_iterator rit;//定义反向迭代器
auto it = t.begin();//因为t.begin()返回正向迭代器，所以it自动被定义为正向迭代器，可适应其他所有操作
for(multiset<int>::iterator it=q.begin();it!=q.end();it++){}

//以下需要迭代器的操作：
t.begin();//返回multiset中第一个元素，类型为正向迭代器
t.rbegin();//返回multiset中最后一个元素，类型为反向迭代器
t.end();//返回multiset中最后一个元素，类型为正向迭代器
t.rend();//返回multiset中第一个元素，类型为反向迭代器

t.find(k);//寻找k，若找到返回第一个k对应的迭代器，否则返回end()，所以可以用t.erase(t.find(k))的方法来删除容器中其中一个等于k的元素
t.insert(a, b);//插入指针[a, b)之间的元素
t.erase(it);//删除迭代器it对应的元素
t.erase(l, r);//删除迭代器[l, r)之间的元素
lower_bound(k);// 返回第一个大于等于k的元素的迭代器
upper_bound(k);//返回第一个大于k元素的迭代器

vector

#include<vector>
//vector是一个能够存放任意类型的动态数组
vector<int> list;
vector<int> num[100005];
list.push_back(a); 		//把a放进vector里
list[i].push_back(a); 

list.empty(); //判断a是否为空，空则返回ture,不空则返回false
list.size(); //返回a中元素的个数
list.erase(i);//删除迭代器指向的元素
for(vector<int>::iterator it=b.begin();it!=b.end();it++){}
//迭代器遍历
list.back(); //返回a的最后一个元素
list.front(); //返回a的第一个元素

map

#include<map>//map是根据关键字（第一个值）升序排列
map<int,string> person;//定义map
//插入数据
//（1）以数组形式插入
person[2]="TOM";
person[4]="Jack";
//（2）使用pair插入
person.insert(pair < int,string > (1,"Jim"));
//（3）使用value_type插入
person.insert(map<int,std::string>::value_type(2, "Tom"));

//遍历
//（1）迭代器遍历
map<int,string>::iterator it;//正向迭代器
map<int,string>::reverse_iterator iter;//反向迭代器 
for(it=person.begin();it!=person.end();it++){
	cout<<it->first<<' '<<it->second<<endl;  
	it++;
}
//删除
iterator erase(iterator it);//通过一个条目对象删除
iterator erase(iterator first，iterator last);//删除一个范围
size_type erase(const Key&key);	//通过关键字删除
clear()；//就相当于enumMap.erase(enumMap.begin(),enumMap.end());
//

优先队列priority_queue

#include<queue>
priority_queue<int> as;//对于基础类型 默认是大根堆
priority_queue <int,vector<int>,greater<int> > q;//小根堆
priority_queue <int,vector<int>,less<int> >q;//大根堆
//自定义比较（重写仿函数）
struct cmp{
	bool operator()(Node n1, Node n2){
		if (n1.a == n2.a) return n1.b > n2.b;
		return n1.a > n1.b;
	}//所以大于号是小顶堆 小于号是大顶堆
};
priority_queue<Node, vector<Node>, cmp> t;
//其余操作与队列基本一致