STL 容器笔记

Shadow_T · 2023-06-01 19:39:40 · 算法·理论

前言

本博客的 stl 按作者自认为的实用度排序。

本博客适用于 C++ 萌新选手。

vector

实用度：10。

vector 是 C++ 中的一种容器（动态数组）。 它的特点在于定义时，不需要定义数组大小，而且还配有许多函数。

vector 的基本操作如下:

这里讲些 vector 神操作。

来看这道题目 https://www.luogu.com.cn/problem/P3369。

它会问你排名 x 的数，或者 x 的排名，那么我们要让其每次插入或删除都保证有序。

C++ 有个函数叫做 lower_bound，可以在有序的数组内找到小于等于 x 的最大位置。

那么每次操作要插入 x，我们可以找到 x 在序列中的位置，然后插入，就可以保证其有序了。

比如一开始有一个空的 vector v。

第 1 次插入 2，v=[2]。

第 2 次插入 3，v=[2,3]。

第 3 次插入 0，v=[0,2,3]。

第 4 次插入 2，v=[0,2,2,3]。

我们可以发现，每次插入在小于等于 x 的最大位置就可以保证有序。

一行代码：v.insert(lower_bound(v.begin(),v.end(),x),x);

对于删除操作就用 erase：

v.erase(lower_bound(v.begin(),v.end(),x));

其他操作也可以用 vector 库函数实现：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    vector<int> v;
    int n;
    cin>>n;
    while(n--)
    {
        int opt,x;
        scanf("%d%d",&opt,&x);
        switch(opt)
        {
            case 1:v.insert(lower_bound(v.begin(),v.end(),x),x);break;
            case 2:v.erase(lower_bound(v.begin(),v.end(),x));break;
            case 3:printf("%d\n",lower_bound(v.begin(),v.end(),x)-v.begin()+1);break;
            case 4:printf("%d\n",v[x-1]);break;
            case 5:printf("%d\n",v[lower_bound(v.begin(),v.end(),x)-v.begin()-1]);break;
            case 6:printf("%d\n",v[upper_bound(v.begin(),v.end(),x)-v.begin()]);break;
        }
    }
}

然后你发现一道蓝题就被 vector 板子虐了。

当要求有插入，有删除，要有序，可以访问位置 x 的元素是，就可以使用。但是这种方法常数较大，有被卡掉的可能性，所以谨慎使用。最劣复杂度可以到 O(n^2)，但是普遍较快。

这东西还有个用处，就是可以存图，在 u 和 v 中间连一条边权 w 的边：

vector<pair<int,int> > g[maxn];
int u,v;
cin>>u>>v;
g[u].push_back(v);

set&multiset

实用度：8。

set 的基本操作如下:

set 每次插入值后一直都是保持有序的。可以用迭代器线性遍历 set：

for(set<int>::iterator it=s.begin();it!=s.end();it++)
  cout<<*it<<" ";

它还有个兄弟 multiset，区别在于 set 自动去重，multiset 不去重。

它可以实现一个非常牛的东西：珂朵莉树（ODT）。

实现的是随机数据下区间赋值，区间加，单点排名等等，复杂度 O(n \log n)。

至于写法因为篇幅这里就不讲解，详见 This。

set 还可以实现 \operatorname{mex}，推荐看 This。

priority_queue

实用度：7。

priority_queue 的基本操作如下:

操作确实不多但巨好用，和 set 一样，每次 q 都是有序的，但是无法用迭代器遍历。

在很多地方都很好用，可以快速得出最大或最小的数。

priority_queue 默认大根堆，对于小根堆可以重载运算符或者这样定义：

priority_queue<int,vector<int>,greater<int> >pr;

有时候会出现这种情况，就是我们不光要插入还要删除，很明显优先队列无法直接完成，我们可以用 set，还可以懒标记，要用到下面的 map。

• 对于插入 x，直接在 q 里插进去。

• 对于删除 x，我们在 map m 里面标记一下 x 删除过一次。

• 对于访问，如果发现堆顶元素在 map 里有记载，那么出队，且在 map 里消除一次删除记录。

priority_queue<int> q;
map<int,int> m;
int op;
cin>>op;
if(op==1)
{
  int x;
  cin>>x;
  q.push(x);
}
if(op==2)
{
  int x;
  cin>>x;
  m[x]++;
}
if(op==3)
{
  while(m[q.top()])
  m[q.top()]--,q.pop();
  cout<<q.top()<<"\n";
}

（直接手搓的，没测试过）。

map&multimap&unordered_map

实用度：7。

基本操作就 clear()，别的都基本和数组一样。

它的好处是可以用任何值域，任何类型做下标，像 double，像 pair，甚至本身 map，都可以用来存储查询，复杂度为 O(\log n)。字符串基本就不用求哈希了。

它也可以用迭代器线性遍历，还会自动去重，用处很广泛。

multimap 和 map 的区别和 set 一样，就是去重没去重。有时候 map 会被卡常，可以用 unordered_map。map 复杂度稳定 O(\log n)，unordered_map 复杂度 O(1) 到 O(n) 不等。

bitset

实用度：7。

（其实本文作者不是很会用这东西）。

deque

实用度：6。

queue

实用度：6。

queue 的基本操作如下:

在 bfs 中很常用，可以实现队列结构。

pair

实用度：6。

list

实用度：5。

stack

实用度：5。

stack 的基本操作如下:

这个 STL 没有什么特殊用法，但是实现栈结构比较方便。

array

实用度：4。