STL讲义

DEAD
,

(Flu给没空调队(Air_conditioning = nullptr)的STL讲义)

我们当中,有人不会STL.
— Flu

函数类

排序,去重,查找

STL的区间一直都是 $[l,r)$ .

1
2
3
4
5
6
7
8
9
10
11
12
sort(dat+l,dat+r+1,cmp);    //这是闭区间[l,r]的写法

int m=unique(dat+l,dat+r+1)-dat-l;    //现在的m是数列还剩多少个元素
                                    //这是去重的写法,和排序一样
//注意1 返回的是一个指针,表示还剩多少个元素,返回的是 r) 的指针,也就是末端元素
//注意2 要建立在排好序的基础上

int* pos=upper_bound(dat+l,dat+1+r,num);        //在整个序列中查找第一个大于num的元素
//注意1 返回的是一个指针,表示该元素的位置
//注意2 要建立在排好序的基础上

//lower_bound同理,但是注意lower_bound是返回第一个 大于等于的元素

其他不常用的函数

1
next_permutation(a+1,a+1+n);//自动求下一个排列

随机数

挖坑.

三角函数

挖坑.

杂碎函数

STL重载了很多变量类型的函数,比如

1
2
3
constexpr const long long &std::max<long long>(const long long &__a, const long long &__b)
constexpr const int &std::max<int>(const int &__a, const int &__b)
//也就是说不按上述类型的函数比较max会出锅,比如 max(0,(long long)1) 不能过编译

容器类

容器类也是左开右闭的区间,体现为 [vc.begin(),vc.end()) ,千万别对vc.end()取元素值(事实上取这个值没意义,一般这种小RE不算RE的)
如果你想用迭代器方式访问最后一个元素可以用 vc.rbegin() 逆迭代器.逆迭代器是 (rend(),rbegin()] 的顺序,掉了个方向.仍然使用 ++ 自增运算符进行遍历.

bitset

不会用,挖坑.

array

只是一个普通的数组,声明时长度已经定死了,没有任何特点,当成普通数组用就可以了.

1
vector<array<int,114>>vc;//声明一个二维数组,vc[514][113]的意思是先找vc的第515个元素,得到的是一个array,然后在array里面找第114个元素.

由于array过于平淡,在这里不介绍任何成员函数.

唯一需要介绍的是array的比较函数:以 < 为例:从下标0开始遍历两个array,如果满足 a<b 或 a>b 就return 1或0,否则继续遍历.(和pair一样,先比第一个,再比第二个…)
array作为普通数组的占位符,可以简单理解为pair的上位替代.

1
2
3
4
5
6
map<int,int[10]>mp;
map<int,array<int,10>>mmp;
int main(){
    mp[0][0]=114;
    return 0;
}

Flu也很惊讶,上面的代码居然能过编译…

vector

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
// 定义
vector<int>vc;

// 添加元素
vc.push_back(114514);

// 遍历
for(auto i:vc){
//需要注意auto i是复制元素进行遍历的,如果你想修改原始vector需要用 for(auto& i:vc) 引用传递
    i=0;
}

// 查找
// 很遗憾,没有查找函数.

// 删除(参数传递是一个指针)
vc.erase(vc.begin());
//这玩意好像是复杂度爆表(因为会暴力把后面所有元素复制过来),别用这个.
//非得vc删东西就swap到末端然后pop_back(),否则不要考虑用vector维护.

// 预留
vc.resize(100);//预留100个int的位置,此时[0,99]都可以正常访问,初始值是0.
vc.reserve(100);//预留100个int的位置,但只是预留位置了,你需要用push_back()逐渐占满这些位置,所以reserve之后[0,99]还是不确定值的状态

// 清空
vc.clear();

set

注意set是去重的.

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
// 定义
set<int>st;
//默认是小元素在前(也就是less<int>),你可以用greater<int>让大元素在前,例如set<int,greater<int>> sst;

// 添加元素
st.insert(114514);

// 遍历
for(auto i:st){
//一般情况下不建议在这里修改set的值,毕竟set很复杂,搞炸了怎么办
    i=0;
}

// 查找
st.find(114);//返回找到的指针
//如果没找到就返回 st.end()
/* Postscript:
STL容器类的指针都是 set<int>::iterator 的模样出现的,因为很长所以建议用 auto i=st.find(xxx)
我们比一个更复杂的例子:

set<pair<int,int>>st;
set<pair<int,int>>::iterator it=st.find({114,514});
cout<<(*it).first;

容器指针就是这么使用的,需要注意的是这个指针指向的元素是const类型的,自己不要私自直接改容器元素
*/
st.upper_bound(114);//set同时也维护了两个bound函数,用法不再赘述


// 删除(传参传指针或元素值都可以)
st.erase(st.begin());
st.erase(114514);

// 清空
st.clear();

需要注意的是,删除元素的时候树的形态会变,原来的指针部分会变成野指针.
举例1: st.erase(it); 这个时候it会变成野指针
举例2: 珂朵莉树对于set有一个小trick,见下面的板子:

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
struct Chtholly{
    struct node{
        int l,r;
        mutable i64 val;
        char operator <(const node& io)const{
            return l<io.l;
        }
        node(int a,int b,i64 c):l(a),r(b),val(c){}
    };
    set<node>st;
    int* dat;
    void init(int n){
        dat=new int[n+10];
        for(int i=1;i<=n;++i){
            fin>>dat[i];
        }
        int l=1;
        for(int i=1;i<=n;++i){
            if(dat[l]!=dat[i]){
                st.insert({l,i-1,dat[l]});
                l=i;
            }
        }
        st.insert({l,n,dat[l]});
    }
    set<node>::iterator split(int pos){
        auto i=st.lower_bound({pos,114514,114514});
        if(i!=st.end()&&(*i).l==pos){
            return i;
        }
        i--;
        int l=(*i).l;
        int r=(*i).r;
        i64 val=(*i).val;
        st.erase(i);
        st.insert({l,pos-1,val});
        return st.insert({pos,r,val}).first;
    }
    /*
    珂朵莉树维护的是区间的信息,所以split函数负责二分出想要的区间,然后在特定的地方断开.
    因为这里涉及到添加删除元素,所以因为set的特性我们要先split r区间再split l区间.
    当成一个小trick就行了.
    */
    void bbe(int l,int r,i64 val){
        auto itr=split(r+1),itl=split(l);
        st.erase(itl,itr);
        st.insert({l,r,val});
    }
    void aadd(int l,int r,i64 x){
        auto itr=split(r+1),itl=split(l);
        for(auto i=itl;i!=itr;++i){
            (*i).val+=x;
        }
    }
    i64 rrangek(int l,int r,int k){
        vector<node>vc;
        auto itr=split(r+1),itl=split(l);
        for(auto i=itl;i!=itr;++i){
            vc.push_back(*i);
        }
        sort(vc.begin(),vc.end(),[&](node& a,node& b){
            return a.val<b.val;
        });
        for(auto i:vc){
            int del=i.r-i.l+1;
            k-=del;
            if(k<=0){
                return i.val;
            }
        }
        return 114514;
    }
    i64 ppow(int l,int r,int x,int mod){
        i64 res=0;
        auto itr=split(r+1),itl=split(l);
        for(auto i=itl;i!=itr;++i){
            res=(res+qp((*i).val%mod,x,mod)*((*i).r-(*i).l+1)%mod)%mod;
        }
        res=(res+mod)%mod;
        return res;
    }
};

multiset

大致用法和set一样,只不过multiset允许多个元素.
值得注意的是,multiset删除元素也是完全删除,例如

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int main(){
    multiset<int>st;
    st.insert(10);
    st.insert(10);
    st.insert(10);
    st.insert(10);
    st.insert(10);
    for(auto i:st){fout<<i<<" ";}enter

    st.erase(10);
    for(auto i:st){fout<<i<<" ";}
    return 0;
}
/*回显
10 10 10 10 10

*/

map

1
2
3
4
5
6
7
map<int,map<int,int>>mp;//map是能嵌套各种奇怪容器的,这不罕见,毕竟map的本质是一个映射,只要你能搞清楚映射关系,map就能维护(暴论)

mp.find();
for(auto i:mp){
    i.first;//键是什么
    i.second;//键值是什么
}

有一个小点是,map会对所有直接访问的元素建立新表,也就是说如果你用 if(mp[0]==0)xxx; 而不是 if(mp.find(0)==mp.end()) 会让map对0建立索引,直接的影响就是 mp.size() 对不上,umap也有这个问题.

unordered_map

因为map本质是红黑树,它只需要一个比较运算符就能开出来,而umap本质是哈希表,你的自定义类需要写一个哈希方法才能过编译.

1
2
3
4
5
6
7
8
9
10
11
12
13
struct node{
    float aaa;
    double bbb;
    long long ccc;
    node(const float& _aaa,const double& _bbb,const long long& _ccc):aaa(_aaa),bbb(_bbb),ccc(_ccc){}
};
struct nodeHash{
    int operator()(const node& io)const{
        int res=io.aaa+io.bbb+io.ccc;
        return res;
    }
};
unordered_map<node,int,nodeHash>mp;

上面的代码使用简单的加一起的哈希.(这里只是教你们怎么过编译,程序常数问题暂且不考虑,一般我们用val的3次方或者5次方取模表示哈希,当然如果你会写FNV哈希那更好了)

其他用法和map差不多,不过这个在遍历的时候是按照加入的时间戳进行遍历的,先遍历最晚加进来的,和元素大小没有关系.

priority_queue

不能for遍历,也没有几个方法,不容易写错.

1
2
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
//priority_queue<元素,用什么容器存,怎么比较> 容器名字;

估计绝大多数人接触pq是在Dijkstra这里…
因为 greater<int> 的本质是对 int 调用内置的 > 比较方法,所以我们完全可以这么写:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct node{
    int val;
    node(int _val,int __val){
        val=_val+__val;
    }
    bool operator >(const node& io)const{
        //在这里改成<的时候会因为greater调用>的方法但是你没有而过不了编译
        return val>io.val;
    }
};
priority_queue<node,vector<node>,greater<node>>pq;

int main(){
    pq.push({114,514});
    return 0;
}

queue,stack,deque

这几个数据结构没什么方法,也不能for遍历,直接用VsCode自带的补全就可以了.

后记

“方法” 和 “函数” 其实是一回事.