常用数据结构总结（欢迎补充）

1.并查集

//初始化
for(int i=1;i<=n;++i)p[i]=i;
//寻找集合的编号
int find(int x)
{
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}
//合并集合
p[find(a)]=find(b);

2.树状数组

//下标从1开始
int tr[N];
memset(tr,0,sizeof tr);
//单点加
void add(int x,int c)
{
    for(int i=x;i<=n;i+=lowbit(i))tr[i]+=c;
}
//区间求和 1-x
int sum(int x)
{
    int res=0;
    for(int i=x;i;i-=lowbit(i))res+=tr[i];
    return res;
}

3.栈

stack<int> s;
s.push(1);
cout<<s.top()<<endl;
s.pop()

4.队列

queue<int> q;
q.push(1);
q.push(2);
cout<<q.front()<<endl;//1
q.pop();
cout<<q.front()<<endl;//2

5.优先队列

priority_queue<int> q;//大根堆
priority_queue<int,vector<int>,greater<int>> q1;//小根堆
q.push(1);q1.push(1);
q.push(2);q1.push(2);
q.push(3);q1.push(3);
cout<<q.top()<<endl;//3
cout<<q1.top()<<endl;//1

6.存图

//初始化
memset(h,-1,sizeof h);
//预定义
int h[N],e[N*2],ne[N*2],idx;
//增加边
void add(int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
//遍历
for(int i=h[u];i!=-1;i=ne[i]){
    int j=e[i];
}

7.string

string s;
cin>>s;//abcd
cout<<"字符串的长度："<<s.size()<<endl;
//find返回起始下标
cout<<s.find("b")<<endl;//1
cout<<s.find("cd",1)<<endl;//2
//删除
s.erase(s.find("cd"),1);//下标 个数
cout<<s<<endl;//abd

8.结构体

struct Node{
    int l,r,w;
    bool operator<(const Node& W)const
    {
        if(W.w!=w)return w<W.w;
        if(W.l!=l)return l<W.l;
        return r<W.r;
    }
}sum[N];

9.map

//增删改查基本是O(log N) 很快了
map<int,int> m;
m[1]=5;
m[2]=6;
m[3]++;
cout<<m[4]<<endl;//只要出现过就是被添加进去了
//蓝桥杯可以使用的遍历方式
for(map<int,int>::iterator it=m.begin();it!=m.end();it++)
{
    cout<<it->first<<" "<<it->second<<endl;
}