STL在竞赛中的应用
STL在竞赛中的应用
概论
vector
vector 是不定长数组容器。其数组长度的扩增策略是每次乘 2
其操作方式如下：
list
链表容器
#include
#include
using namespace std;
struct point{
int x,y,z;
point(int a,int b,int c):x(a),y(b),z(c){ }
point():x(0),y(0),z(0){}
bool operator <(const point &temp)const{
if(x!=temp.x) return x(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);
}
void output()const{
cout< l1;
/*赋值 & 添加*/
point temp(1,2,3);
for(int i=1;i<=5;++i) l1.push_back(temp);
auto iter=l1.begin();
*iter=point(3,2,5);
/*遍历*/
for(auto iter=l1.begin();iter!=l1.end();++iter){
iter->output();
}
for(auto &i:l1){
i.output();
}
/*反转*/
l1.reverse();
}
string
queue & deque
stack
priority_queue
**优先队列，通过堆来实现，能够保证队首元素为最大（小）值，支持插入，删除操作（\(O(log(n))\)) ，也支持取队首元素、弹出队首元素（\(O(1)\)) **
使用方法如下：
#include
#include
using namespace std;
struct point{
int x,y,z;
bool operator <(const point &temp)const{
if(x!=temp.x) return x(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);
}
void output()const{
cout< pq_0;
/*大根堆构造*/
priority_queue,greater > pq_1;//小根堆，重载>方法
priority_queue,less> pq_2;//大根堆，重载<方法
/*访问*/
while(!pq_0.empty()){
point temp=pq_0.top();
pq_0.pop();
temp.output();
}
/*清空*/
while(!pq_0.empty()) pq_0.pop();
}
各种比较运算符重载方法（通过\(<\)延伸）：
bool operator <(const point &temp)const{
if(x!=temp.x) return x(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);
}