STL在竞赛中的应用

STL在竞赛中的应用

概论

vector

vector 是不定长数组容器。其数组长度的扩增策略是每次乘 2

其操作方式如下:


list

链表容器

#include <list>
#include <iostream>
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<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);
    }
    void output()const{
        cout<<x<<" "<<y<<" "<<z<<endl;
    }
};
int main(){
    /*声明*/
    list<point> 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<queue>
#include<iostream>
using namespace std;

struct point{
    int x,y,z;
    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);
    }
    void output()const{
        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;//大根堆,重载<方法

    /*访问*/
    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<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);
    }

Lambda

algorithm

map

set

multimap/multiset

unodered_map/set

STL在竞赛中的应用

上一篇:Go map初始化和读取


下一篇:知识图谱环境搭建过程