STL在竞赛中的应用
概论
vector
vector 是不定长数组容器。其数组长度的扩增策略是每次乘 2
其操作方式如下:
list
链表容器
string
queue & deque
stack
priority_queue
优先队列,通过堆来实现,能够保证队首元素为最大(小)值,支持插入,删除操作(\(O(log(n))\)) ,也支持取队首元素、弹出队首元素(\(O(1)\))
使用方法如下:
#include<queue>
#include<iostream>
using namespace std;
struct point{
int x,y,z;
const bool operator <(const point &temp)const{
if(x!=temp.x) return x<temp.x;
if(y!=temp.y) return y<temp.y;
if(z!=temp.z) return z<temp.z;
return false;
}
const bool operator >(const point &temp)const{
return temp<*this;
}
void output(){
cout<<x<<" "<<y<<" "<<z<<endl;
}
};
int main(){
/*声明*/
priority_queue<point> pq_0;
/*大根堆构造*/
priority_queue<point,vector<point>,greater<point>> pq_1;//小根堆,重载>方法
priority_queue<point,vector<point>,less<point>> pq_2;//大根堆,重载<方法
/*访问*/
if(!pq_0.empty()){
point temp=pq_0.top();
temp.output();
}
/*清空*/
while(pq_0.empty()) pq_0.empty();
}
各种比较运算符重载方法(通过\(<\)延伸):
bool operator <(const point &temp)const{
if(x!=temp.x) return x<temp.x;
if(y!=temp.y) return y<temp.y;
if(z!=temp.z) return z<temp.z;
return false;
}
bool operator >(const point &temp)const{
return temp<*this;
}
bool operator <=(const point &temp)const{
return !(temp>*this);
}
bool operator >=(const point &temp)const{
return !(*this<temp);
}
bool operator ==(const point &temp)const{
return (*this<=temp) && (*this>=temp);
}