陌生的STL 和 pbds初步

发表于 更新于 分类于 阅读次数： 评论数：
本文字数： 1.8k 阅读时长 ≈ 6 分钟
本文记录了STL的学习

真的有很多人，他们的代码如诗一般。

有两个有趣的事情。 ①部分很多 $ACMer$ 对 $Vector$ 有这样的想法 : 这个东西是会带大常数的，可是现场赛没卡过，所以很喜欢用（外国选手也非常喜欢？）。 ②我们常常感觉 $stack$ 和 $queue$ 常数特别大，事实上，他的空间特别大， 比时间问题大多了。不信开个$queue\lt int\gt a[1000000]$ 试试呗😂。事实上，$std::queue $ 和 $std::stack$ 是默认基于 $std::deque$ 实现的。

起因是看到著名OI爷jiangly的代码，虎躯一震。他的代码风格真的好好啊！他对于stl的掌控，真的！！！%%%%%%%

回想自己，经常问队友什么什么怎么用，就很离谱。

像这种窒息的对话常常出现，就很无奈。。
遂学习一波

前言

不知道从什么地方开始写，就来碎碎念。

打过 $OI$ 的会感觉 $stl$ 在时间效率上比较低下。而在 $XCPC$ 中，是开$-O2$ 优化的。    当然，不要觉得，编译器什么都可以优化。

Part Ⅰ

指针

没系统的学过，之前看过但是都忘记了。除了字典树$(trie)$等几个算法或数据结构外,都用的不多把（包括trie也是可以用数组模拟的）？除此之外的地方，指针也基本上可以被引用代替。

引用

在扩展欧几里得算法中用到了实参引用。

1
2
3
4
5
6
7
8
9
10
11
12
//找出a,b最大公因数，且求出x，y满足ax+by =gcd(a,b)。
int ext_gcd(int a, int b, int &x,int &y){
	int d = a;
	if(b != 0){
		d = ext_gcd(b , a%b ,y , x);
		y -= (a / b) * x;
	}else {
		x = 1;
		y = 0;
	}
	return d;
}

和指针传参效果一样，但是相比于用指针传递参数而言要方便很多。在要传占用内存较大的变量或类时可以用指针传递来加快效率。

运算符重载

在结构体中，我们经常会用到运算符重载。旨在实现扩展c++自带的类型，或者达到自己的运算（或比较）目的。
比如在fft中重写Complex。

1
2
3
4
5
6
7
struct C {
    LD r, i;
    C(LD r = 0, LD i = 0) : r(r), i(i) {}
} A[MAXN], B[MAXN];
C operator+(const C& a, const C& b) { return C(a.r + b.r, a.i + b.i); }
C operator-(const C& a, const C& b) { return C(a.r - b.r, a.i - b.i); }
C operator*(const C& a, const C& b) { return C(a.r * b.r - a.i * b.i, a.r * b.i + a.i * b.r); }

auto关键字

$auto$ 关键字可以在声明变量的时候根据变量初始值的类型自动为此变量选择匹配的类型，配合同是 $C++ 11$标准加入的 $for$ 语句的新用法在有的时候可以加快代码的编写速度。

比如以前遍历 $set$ 的一般写法是:

1
2
3
4
set <int> iterator::itr;
for (itr = st.begin(); itr != st.end(); itr++){
    cout << *itr << endl;
}

比如遍历某容器时现可以写作:

1
2
3
for(auto it : st){
    cout << it << endl;
}

这种写法中，$for$ 循环会从头到尾遍历一遍 $st$ 容器，将其中的值取出。需要注意的是，如果要修改元素的值的话，应该声明成引用$auto\&\quad i$。

模板

$cf$ 上著名选手 tourist 的代码就有很多模板。然而我很多看不懂用不来。
卑微如我只能写个快读模板。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
template <typename T>
void read(T &x) {
    x = 0;
    int f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + (ch ^ 48);
        ch = getchar();
    }
    x *= f;
    return;
}
template <typename T>
void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
    return;
}

Part Ⅱ

vector

vector 的实现基于动态数组，结合倍增思想（空间开不下了就全部删掉再开 $2$ 倍）。单次操作复杂度基本都是均摊 $O(1)$ 的。

初始化

1
2
3
4
5
6
7
vector <int> a;//新建一个空的vector 
vector <int> b(5,3);//新建一个包含 5 个 3 的 vector
vector <int> c(5);// = vector <int> c(5,0);
vector <int> d(b.begin()+1,b.end()-1);// 用 [b.begin()+1,b.end()-1) 这一段构成的数组生成 vector 
vector <int> e(d);// 生成一个和 d 相同的 vector e
vector <int> v(n);
iota(v.begin(),v.end(),0); //在vector里创建一个0,1...n-1的数列

基本操作

  • back()  v.back() 返回 v 的最后一个元素的引用
  • front()  v.front() 返回 v 的第一个元素的引用
  • begin()  v.begin()返回一个迭代器，指向 v 的第一个元素。
  • end()  v.end()返回一个迭代器，指向 v 的最后一个元素的后一个位置。
  • clear()  v.clear() 表示将 v 清空（内存不释放）。 Complexity：与容器大小线性。
  • empty()  v.empty()返回一个布尔值，表示 v 是否为空。

  • erase 

    1
    2
    3
    4
    5
    6
    vector<int> v(10);
    iota(v.begin(), v.end(), 1);
    v.erase(v.begin() + 5);  //删除 v.begin()+5 这个位置的元素
    v.erase(v.begin(), v.begin() + 3);  //删除 [v.begin(),v.end()) 这个区间之间的所有元素
    for (auto i : v) cout << i << " ";
    //输出结果 4 5 7 8 9 10

  • insert

    1
    2
    3
    4
    5
    6
    vector <int> v(3,1);
    vector <int> :: iterator it=v.begin();
    it=v.insert(it,2);//在 it 处插入一个 2
    v.insert(it,2,3);//在 it 处插入 2 个 3 ，注意这个语句执行完之后 it 就失效了
    vector <int> u(3,1);
    u.insert(u.begin(),v.begin(),v.end());//在 u.begin() 处插入 [v.begin(),v.end()) 这个范围内的元素

  • resize
    这个聚好用！
    多组时候可以这样v.clear();v.resize(n);
    unique_sort时候可以这样 (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))好像有点长，有个很简短写法我忘记了。。 a.resize(unique(a.begin(),a.end())-a.begin());大概这样？

  • emplace_back()/push_back()  在 v 的最后插入一个元素。

  • pop_back() 弹出最后一个元素。

set

单次操作的复杂度基本都是 $O(log\ Size)$的。
一样的操作就省略了。

基本操作

  • count
    S.count(x)表示求 $S$ 中 $x$ 元素的出现次数。由于 $set$ 中各个元素互不相同，所以只会返回 $0$ 或 $1$ 。
    单次操作时间复杂度为 $O(log \ Size)$
    ​1000000 次 count 用时在 0.3s 到 1s 左右，取决于电脑运行效率。

  • erase
    用于删除元素

    1
    2
    3
    4
    S.erase(it);// 删除 set 迭代器 it 指向的元素。删除完之后这个迭代器就失效了。
    S.erase(x);// 删除元素 x 
    S.erase(it1,it2);// 删除 [it1,it2) 的所有元素 
    S.erase(it,S.end());// 上一种用法的一个实例

  • find
    S.find(x)返回一个迭代器，这个迭代器指向的元素值为 $x$。

  • insert
    S.insert(x) 表示在 S 中插入元素 $x$ ，并返回一个 pair :: iterator,bool> ，第一个元素表示插入元素 $x$ 之后 $x$ 的迭代器（如果原本就有 $x$ 就返回原来的 $x$ 的迭代器），第二个元素表示这次插入是否有效，如果 $x$ 原先不在 $S$ 中，那么返回 $true$，否则返回 $false$。
    ​S.insert(it1,it2) 表示在 S 中插入 $[it1,it2)$ 的所有元素。

  • swap 

    1
    S.swap(S1);//复杂度是常数

  • lower_bound/upper_bound
    返回的是迭代器。大于等于 / 大于

multiset

multiset 是可重集，也就是说容器内可以有多个相同元素。我以前很喜欢用。
大部分用法和 set 一样，这里讲不太一样的。
奥！！一定要说的一个点是 multiset 的常数比 set 的常数大若干倍！

较为不同的

  • count
    S.count(x)单次 count 复杂度在 $O(log\ Size + S.count(x))$
    实测 from others
  • erase
    S.erase(x)的作用是删除 S 中所有等于 x 的元素。
    删除一个的时候写成S.erase(S.find(x))

map

基于 rbtree。
一般用于离散化，单次操作的时间复杂度基本都是 $0(log \ Size)$

用得好map真的很方便！ dqy 就比较会。

unordered_map

基于 hash 表。是map的弱化版，由于实现原理不同，map有的很多功能他都么得，但是他单次操作时间复杂度$O(1)$，但在 cf 上可以被卡。neal文章有写 Blowing up unordered_map, and how to stop getting hacked on it
​
需要 c++11 以上的编译器才可以使用。

priority_queue

优先队列，堆，完全可以用 set 代替，功能比 set 弱，单次操作 $O(log \ Size)$，没有迭代器，系统默认大根堆。

但他常数比set小，约为0.5倍。

定义一个 int 类型的大根堆 priority_queue q;

定义一个 char 类型的大根堆 priority_queue, greater > Q;

重载比较运算符：

1
2
3
4
5
6
struct cmp{
    bool operator () (int a,int b){
        //......
    }
};
priority_queue <int,vector <int>,cmp> Q3;

Part Ⅲ:pb_ds初步：

主要看的是于纪平《C++的pb_ds库在OI中的应用.pdf》

什么是__gnu_pbds?Policy based data structures！简称平板电视pbds。在使用pbds前，你需要：

1
2
3
4
5
6
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>//用tree
#include<ext/pb_ds/hash_policy.hpp>//用hash
#include<ext/pb_ds/trie_policy.hpp>//用trie
#include<ext/pb_ds/priority_queue.hpp>//用priority_queue
using namespace __gnu_pbds;

有没有形如#include<bits/stdc++.h>的写法呢？

答案是有的！

1
2
3
#include<bits/extc++.h>
using namespace __gnu_pbds;
//bits/extc++.h与bits/stdc++.h类似，bits/extc++.h是所有拓展库，bits/stdc++.h是所有标准库,然而在某些ide下会显示缺少东西。

hash

hash_table的用法与map类似，它是这么定义的：

1
2
cc_hash_table<int,bool> h;
gp_hash_table<int,bool> h;

其中cc开头为拉链法，gp开头为探测法，实测探测法稍微快一些。

用法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
gp_hash_table<string,int> h;
void judge(string s)
{
    if(h.find(s)!=h.end())
        cout<<"orz %%%";
    else
        cout<<"fuck";
    cout<<endl;
}
int main()
{
    h["aa"]=1;
    h.insert(make_pair("nn",1));
    string str;
    while(cin>>str)
        judge(str);
    return 0;
}

等一等？和map一样，那不如直接用 map 了。不不不，map 的总时间复杂度是 $O(nlog_n)$ 的，而hash_table的总时间复杂度仅为 $O(n)$

Tree

pbds里面的tree都是平衡树，其中有rb_tree,splay_tree,ov_tree（后两种都容易超时，所以请不要用它们）。

食用芝士：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#define pii pair<int,int>
#define mp(x,y) make_pair(x,y) 
tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update> tr;
pii //存储的类型
null_type //无映射(低版本g++为null_mapped_type)
less<pii> //从小到大排序
rb_tree_tag //红黑树
tree_order_statistics_node_update //更新方式 
tr.insert(mp(x,y)); //插入;
tr.erase(mp(x,y)); //删除;
tr.order_of_key(pii(x,y)); //求排名 
tr.find_by_order(x); //找k小值，返回迭代器 
tr.join(b); //将b并入tr，前提是两棵树类型一样且没有重复元素 
tr.split(v,b); //分裂，key小于等于v的元素属于tr，其余的属于b
tr.lower_bound(x); //返回第一个大于等于x的元素的迭代器
tr.upper_bound(x); //返回第一个大于x的元素的迭代器
//以上所有操作的时间复杂度均为O(logn)

对于洛谷P3369 普通平衡树，我们用此很容易解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#include<cstdio>
#include<iostream>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> bbt;
int n;ll k,ans;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
} 
int main(){
    n=read();
    for(int i=1,opt;i<=n;i++){
        opt=read();k=read();
        if(opt==1) bbt.insert((k<<20)+i);
        if(opt==2) bbt.erase(bbt.lower_bound(k<<20));
        if(opt==3) printf("%d\n",bbt.order_of_key(k<<20)+1);
        if(opt==4) ans=*bbt.find_by_order(k-1),printf("%lld\n",ans>>20);
        if(opt==5) ans=*--bbt.lower_bound(k<<20),printf("%lld\n",ans>>20);
        if(opt==6) ans=*bbt.upper_bound((k<<20)+n),printf("%lld\n",ans>>20);
    }
    return 0;
}

Trie

trie即为字典树，我们先看如何定义一个trie与它的操作：

1
2
3
4
5
6
7
8
9
10
typedef trie<string,null_type,trie_string_access_traits<>,pat_trie_tag,trie_prefix_search_node_update> tr;
//第一个参数必须为字符串类型，tag也有别的tag，但pat最快，与tree相同，node_update支持自定义
tr.insert(s); //插入s 
tr.erase(s); //删除s 
tr.join(b); //将b并入tr 
pair//pair的使用如下：
pair<tr::iterator,tr::iterator> range=base.prefix_range(x);
for(tr::iterator it=range.first;it!=range.second;it++)
    cout<<*it<<' '<<endl;
//pair中第一个是起始迭代器，第二个是终止迭代器，遍历过去就可以找到所有字符串了。

priority_queue

priority_queue为优先队列，用堆实现，priority_queue的定义与操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
priority_queue<int,greater<int>,TAG> Q;//小根堆，大根堆写less<int>
/*其中的TAG为类型，有以下几种：
pairing_heap_tag 默认是pairing_heap_tag 
thin_heap_tag
binomial_heap_tag
rc_binomial_heap_tag 
binary_heap_tag
其中pairing_help_tag最快*/
Q.push(x);
Q.pop();
Q.top();
Q.join(b);
Q.empty();
Q.size(); 
Q.modify(it,6);
Q.erase(it);

堆优化dijkstra

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include<bits/stdc++.h>
#include<ext/pb_ds/priority_queue.hpp>
#define Rep(i,a,b) for(register int i=(a),i##end=(b);i<=i##end;++i)
#define Repe(i,a,b) for(register int i=(a),i##end=(b);i>=i##end;--i)
#define For(i,a,b) for(i=(a),i<=(b);++i)
#define Forward(i,a,b) for(i=(a),i>=(b);--i)
#define Chkmax(a,b) a=a>b?a:b
template<typename T>inline void read(T &x)
{
    T f=1;x=0;char c;
    for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-1;
    for(;isdigit(c);c=getchar())x=x*10+(c^48);
    x*=f;
}

inline void write(int x)
{
    if(!x){putchar(48);putchar('\n');return;}
    static int sta[45],tp;
    for(tp=0;x;x/=10)sta[++tp]=x%10;
    for(;tp;putchar(sta[tp--]^48));
    putchar('\n');
}

using namespace std;
void file()
{
#ifndef ONLINE_JUDGE
    freopen("water.in","r",stdin);
    freopen("water.out","w",stdout);
#endif
}

const int MAXN=1e5+7,MAXM=4e5+7;

static int n,m;

static struct edg
{
    int u,v,w,h;
    friend bool operator<(edg a,edg b){return a.h>b.h;}
}EDG[MAXM];

static struct edge
{
    int v,w,nxt;
}P[MAXM<<1];

static int head[MAXN],e;

inline void add(int u,int v,int w)
{P[++e]=(edge){v,w,head[u]};head[u]=e;}

__gnu_pbds::priority_queue<pair<int,int>,greater<pair<int,int> > >G;

__gnu_pbds::priority_queue<pair<int,int>,greater<pair<int,int> > >::point_iterator its[MAXN];

static int dis[MAXN];

const int INF=2e9+7;

inline void dijkst(int s)
{
    G.clear();
    its[s]=G.push(make_pair(0,s));dis[s]=0;
    Rep(i,2,n)dis[i]=INF,its[i]=G.push(make_pair(INF,i));
    static int u;
    while(!G.empty())
    {
        u=G.top().second;G.pop();
        for(register int v=head[u];v;v=P[v].nxt)
            if(dis[P[v].v]>dis[u]+P[v].w)
            {
                dis[P[v].v]=dis[u]+P[v].w;
                G.modify(its[P[v].v],make_pair(dis[u]+P[v].w,P[v].v));
            }
    }
}

static int s;

inline void init()
{
    read(n);read(m);read(s);
    static int u,v,w;
    Rep(i,1,m)read(u),read(v),read(w),add(u,v,w);
}

inline void solve()
{
    dijkst(s);
    Rep(i,1,n)printf("%d ",dis[i]);
    puts("");

}

int main()
{
    file();
    init();
    solve();
    return 0;
}

-------------本文结束感谢您的阅读-------------