第三节常用STL – GOATWU

Contents

STL

vector

构造函数

vector<int> a(5); // {0, 0, 0, 0, 0}
vector<int> b(5, 3); // {3, 3, 3, 3, 3}
int arr[5] = {0, 3, 2, 4, 1}
vector<int> c(arr + 1, arr + 5); // {3, 2, 4, 1}
vector<int> d(c.begin(), c.end() - 1) // {3, 2, 4}
vector<int> e(d) // {3, 2, 4}

vector 插入元素

// 在第 i 个元素后面插入a;
v.insert(v.begin() + i,a);

vector自定义排序

骚方法：

struct Data {
    int d, m, w, id;
};
vector<Data> Q;

sort(Q.begin(), Q.end(), [&](Data a, Data b) {
    return a.d == b.d ? a.m < b.m : a.d < b.d;
});

普通方法：

bool cmp(const int &a,const int &b) {
    return a > b;
}
sort(v.begin(), v.end(), cmp);

vector 删除元素

// 删除第 i + 1 个元素
v.erase(v.begin() + i);

vector 去重

void discreate(vector<int> &v) {
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
}

下一个排列

sort(v.begin(), v.end());
next_permutation(v.begin(), v.end());

优先队列

优先级高的先出队。默认为大根堆。

priority_queue<int> pq1; // 大根堆，大的先出
priority_queue< int, vector<int>, greater<int> > pq2; // 小根堆

自定义排序方式：

struct cmp {
bool operator () (int x, int y) {
    return x > y; // 小的优先级高
    //也可以写成其他方式，如：return p[x] > p[y]; 表示 p[i] 小的优先级高
    }
};
priority_queue<int, vector<int>, cmp> q;

struct node {
    int x, y;
    friend bool operator < (node a, node b) {
    return a.x > b.x; //结构体中，x 小的优先级高
    }
};
priority_queue<node> q;

set

struct Node {
    int x, y;
};
struct classcomp {
    //先按照 x 从小到大排序，x 相同则按照 y 从大到小排序
    bool operator() (const Node &a, const Node &b) const { 
        if (a.x != b.x) return a.x<b.x;
        else return a.y>b.y;
    }
};
multiset<Node,classcomp>mt;
multiset<Node,classcomp>::iterator it;

主要函数：
– begin()：返回指向第一个元素的迭代器
– clear()：清除所有元素
– count()：返回某个值元素的个数
– empty()：如果集合为空，返回 true
– end()：返回指向最后一个元素的迭代器
– erase()：删除集合中的元素 (参数是一个元素值，或者迭代器)；注意对于 multiset 删除操作之间删除值会把所以这个值的都删掉，删除一个要用迭代器。
– find()：返回一个指向被查找到元素的迭代器
– insert()：在集合中插入元素
– lower_bound()：返回指向大于（或等于）某值的第一个元素的迭代器
– upper_bound()：返回大于某个值元素的迭代器
– equal_range()：返回集合中与给定值相等的上下限的两个迭代器（存在pair中，相当于上面两个函数同时调用）

位运算

`__builtin` 函数

注意： long long 类型在函数后面加上 ll 即可，如：__builtin_clzll

__builtin_parity(unsigned int n)
该函数时判断n的二进制中1的个数的奇偶性

int n = 15;                          //二进制为1111
int m = 7;                           //二进制为111
cout << __builtin_parity(n) << endl; //偶数个1，输出0
cout << __builtin_parity(m) << endl; //奇数个1，输出1

__builtin_popcount(unsigned int n)

该函数时判断n的二进制中有多少个1

int n = 15;                            //二进制为1111
cout << __builtin_popcount(n) << endl; //输出结果为4

__builtin_ctz(unsigned int n)

该函数判断n的二进制末尾后面0的个数，n=0时结果未定义

int n = 1;                          //二进制为1
int m = 8;                          //二进制为1000
cout << __builtin_ctzll(n) << endl; //输出0
cout << __builtin_ctz(m) << endl;   //输出3

__builtin_clz(unsigned int n)

n前导0的个数, n=0时结果未定义

long long n = 1;                    //二进制为000....001 64位整数
int m = 8;                          //二进制为000...1000 32位整数
cout << __builtin_clzll(n) << endl; //输出63
cout << __builtin_clz(m) << endl;   //输出28

__builtin_ffs(unsigned int n)

该函数判断n的二进制末尾最后一个1的位置，从1开始

int n = 1;                        //二进制为1
int m = 8;                        //二进制为1000
cout << __builtin_ffs(n) << endl; //输出1
cout << __builtin_ffs(m) << endl; //输出4

bitset

构造函数

bitset<4> bitset1;　　//无参构造，长度为４，默认每一位为０

bitset<8> bitset2(12);　　//长度为８，二进制保存，前面用０补充

string s = "100101";
bitset<10> bitset3(s);　　//长度为10，前面用０补充

char s2[] = "10101";
bitset<13> bitset4(s2);　　//长度为13，前面用０补充

cout << bitset1 << endl;　　//0000
cout << bitset2 << endl;　　//00001100
cout << bitset3 << endl;　　//0000100101
cout << bitset4 << endl;　　//0000000010101

bitset1.reset()// 清空操作

可用的操作符

bitset<4> foo (string("1001"));
bitset<4> bar (string("0011"));

cout << (foo^=bar) << endl;       // 1010 (foo对bar按位异或后赋值给foo)
cout << (foo&=bar) << endl;       // 0010 (按位与后赋值给foo)
cout << (foo|=bar) << endl;       // 0011 (按位或后赋值给foo)

cout << (foo<<=2) << endl;        // 1100 (左移２位，低位补０，有自身赋值)
cout << (foo>>=1) << endl;        // 0110 (右移１位，高位补０，有自身赋值)

cout << (~bar) << endl;           // 1100 (按位取反)
cout << (bar<<1) << endl;         // 0110 (左移，不赋值)
cout << (bar>>1) << endl;         // 0001 (右移，不赋值)

cout << (foo==bar) << endl;       // false (0110==0011为false)
cout << (foo!=bar) << endl;       // true  (0110!=0011为true)

cout << (foo&bar) << endl;        // 0010 (按位与，不赋值)
cout << (foo|bar) << endl;        // 0111 (按位或，不赋值)
cout << (foo^bar) << endl;        // 0101 (按位异或，不赋值)

// 通过 [] 访问元素(类似数组)，注意最低位下标为０
bitset<4> foo ("1011");
cout << foo[0] << endl;　　//1
cout << foo[1] << endl;　　//1
cout << foo[2] << endl;　　//0

可用函数

bitset<8> foo ("10011011");

cout << foo.count() << endl;　//5　count函数用来求1的位数，foo中共有５个１
cout << foo.size() << endl;　 //8　size函数用来求bitset的大小，一共有８位

cout << foo.test(0) << endl;　//true
// test函数用来查下标处的元素是０还是１，此处foo[0]为１，返回true
cout << foo.test(2) << endl;　//false　（同理，foo[2]为０，返回false

cout << foo.any() << endl;　　//true　any函数检查bitset中是否有１
cout << foo.none() << endl;　 //false　none函数检查bitset中是否没有１
cout << foo.all() << endl;　　//false　all函数检查bitset中是全部为１

bitset<8> foo ("10011011");
cout << foo.flip(2) << endl;　　//10011111　　
// flip函数传参数时，用于将参数位取反，本行将foo下标２处"反转"，即０变１，１变０
cout << foo.flip() << endl;　　 //01100000　　
// flip函数不指定参数时，将bitset每一位全部取反

cout << foo.set() << endl;　　　//11111111　　
// set函数不指定参数时，将bitset的每一位全部置为１
cout << foo.set(3,0) << endl;　//11110111　　
// set函数指定两位参数时，将第一参数位的元素置为第二参数的值，本行相当于foo[3]=0
cout << foo.set(3) << endl;　　//11111111　　
// set函数只有一个参数时，将参数下标处置为１

cout << foo.reset(4) << endl;　//11101111　
// reset函数传一个参数时将参数下标处置为０
cout << foo.reset() << endl;　//00000000　
// reset函数不传参数时将bitset的每一位全部置为０

类型转换

bitset<8> foo ("10011011");

string s = foo.to_string();　//转换成string类型
unsigned long a = foo.to_ulong();　//转换成unsigned long类型
unsigned long long b = foo.to_ullong();　//转换成unsigned long long类型

cout << s << endl;　　//10011011
cout << a << endl;　　//155
cout << b << endl;　　//155

pbds

hash_table

头文件：

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;

用法：

用法和 unordered_map 一样。其中 cc_hash_table 是拉链法，gp_hash_table 是探查法。后者速度更快一点但不稳定，最好用 cc_hash_table。

cc_hash_table<int, int> tb;
gp_hash_table<int, int> tb;

priority_queue

头文件：

#include <ext/pb_ds/priority_queue.hpp>
using namespace __gnu_pbds;
typedef __gnu_pbds::priority_queue<pii, less<pii>, pairing_heap_tag> heap;

用法：

共有五种操作：push，pop，modify，erase，join。常用标记：

pairing_heap_tag：push 和 join 为 $O(1)$ ，其余 $O(\log n)$ .
binary_heap_tag：只支持 push 和 pop，均为均摊 $O(\log n)$ 。比 std::priority_queue 要快.

需要用到可并堆（左偏树）时

例题：P1456 Monkey King

题目大意：

一开始有 $n$ 只孤独的猴子，然后他们要打 $m$ 次架，每次打架，都会拉上自己朋友最牛叉的出来跟别人打，打完之后战斗力就会减半，每次打完架就会成为朋友。问每次打完架之后那俩猴子最牛叉的朋友战斗力还有多少，若朋友打架就输出 $-1$ .

请注意，如果 $A$ 和 $B$ 是朋友， $B$ 和 $C$ 是朋友，那么我们认为 $A$ 和 $C$ 也是朋友。

#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
#define mp(x, y) make_pair(x, y)
using namespace std;
using namespace __gnu_pbds;
typedef pair<int, int> pii;
typedef __gnu_pbds::priority_queue<pii, less<pii>, pairing_heap_tag> heap;
const int N = 1e5 + 50;
int n, m;
heap h[N];

int f[N];
void init() {
    for(int i = 1; i <= n; i++) h[i].clear();
    for(int i = 1; i <= n; i++) f[i] = i;
}
int find(int x) {
    return x == f[x] ? x : (f[x] = find(f[x]));
}

int main() {
    while (~scanf("%d", &n)) {
        init();
        for (int i = 1, w; i <= n; i++) {
            scanf("%d", &w); h[i].push(mp(w, i));
        }
        scanf("%d", &m);
        for (int i = 1, a, b; i <= m; i++) {
            scanf("%d%d", &a, &b);
            int fa = find(f[a]), fb = find(f[b]);
            if (fa == fb) {
                puts("-1"); continue;
            }
            pii x = h[fa].top(), y = h[fb].top();
            h[fa].pop(); h[fb].pop();
            x = mp(x.first / 2, x.second);
            y = mp(y.first / 2, y.second);
            h[fa].push(x); h[fb].push(y);
            h[fa].join(h[fb]); f[fb] = fa;
            printf("%d\n", h[fa].top().first);
        }
    }
    return 0;
}

需要用到修改优先队列元素时

例子：堆优化Dijkstra

#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;
using namespace __gnu_pbds;
#define mp make_pair
typedef pair<int, int> pii;
typedef __gnu_pbds::priority_queue<pii, greater<pii>, pairing_heap_tag> heap;
const int N = 1e5 + 50, M = 2e5 + 50;
int n, m, s;
heap::point_iterator it[M];
heap pq;

int head[N], tot;
struct Edge {
    int nex, to, w;
}e[M];
void add(int a, int b, int c) {
    e[++tot] = {head[a], b, c};
    head[a] = tot;
}

int dis[N];
void Dijkstra(int rt) {
    memset(dis, 0x7f, sizeof(dis));
    memset(it, 0, sizeof(it));
    while (!pq.empty()) pq.pop();
    dis[rt] = 0;
    it[rt] = pq.push(mp(0, rt));
    while (!pq.empty()) {
        pii t = pq.top(); pq.pop();
        int id = t.second, x = t.first;
        for (int i = head[id]; i; i = e[i].nex) {
            int to = e[i].to;
            if (dis[to] > x + e[i].w) {
                dis[to] = x + e[i].w;
                if (it[to] == NULL) it[to] = pq.push(mp(dis[to], to));
                else pq.modify(it[to], mp(dis[to], to));
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    scanf("%d%d%d", &n, &m, &s);
    for (int i = 1, a, b, c; i <= m; i++) {
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    Dijkstra(s);
    for (int i = 1; i <= n; i++) printf("%d%c", dis[i], i == n ? '\n' : ' ');
    return 0;
}

tree

头文件：

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

基础用法：

对于 map 型：

tree<int, int, less<int>, rb_tree_tag, tree_order_statistics_node_update> t;

对于 set 型（老版本的 null_type 改成 null_mapped_type）：

tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> t;

支持的函数：

t.insert(x)：插入 x；
t.erase(x)：删除 x；
t.find_by_order(x);：找第 x+1 小的元素的迭代器，如果过大则返回 t.end()；
t.order_of_key(x)：找 t 中有多少个比 x 小的元素；
t.lower_bound(x)：找第一个大于等于 x 元素的迭代器；
t.upper_bound(x)：找第一个大于 x 元素的迭代器；
t.join(s)：将树 s 合并入 t（不能有重复元素）；
t.split(v, s)：小于等于 v 的元素属于 t，其余属于 s。

例题：

插入一个整数 $x$ 。
删除一个整数 $x$ （若有多个相同的数，只删除一个）。
查询整数 $x$ 的排名（排名定义为比当前数小的数的个数 $+1$ ）。
查询排名为 $x$ 的数（如果不存在，则认为是排名小于 $x$ 的最大数）。
求 $x$ 的前驱（前驱定义为小于 $x$ ，且最大的数）。
求 $x$ 的后继（后继定义为大于 $x$ ，且最小的数）。

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define  mp(x, y) make_pair(x, y)
using namespace std;
using namespace __gnu_pbds;
const int INF = 2e9;
typedef pair<int, int> pii;
typedef long long ll;
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> Tree;
Tree tr;
Tree::iterator it;

int n, m;
int o, x, tot;

int main(int argc, const char * argv[]) {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    int ans = 0;
    for (int i = 1, x; i <= n; i++) {
        cin >> x;
        tr.insert(mp(x, ++tot));
    }
    for (int i = 1, l = 0, o, x; i <= m; i++) {
        cin >> o >> x;
        x ^= l;
        if (o == 1) tr.insert(mp(x, ++tot));
        else if (o == 2) {
            it = tr.lower_bound(mp(x, 0));
            tr.erase(it);
        }
        else {
            if (o == 3) l = tr.order_of_key(mp(x, 0)) + 1;
            if (o == 4) l = tr.find_by_order(x - 1)->first;
            if (o == 5) l = (--tr.lower_bound(mp(x, 0)))->first;
            if (o == 6) l = tr.upper_bound(mp(x, INF))->first;
            ans ^= l;
        }
    }
    cout << ans << "\n";
    return 0;
}

高级用法：

我们可以自定义 Node_Update 方法（tree_order_statistics_node_update 是维护子树的大小）。例如维护一个可以查询 key 值在 l 和 r 之间所有 value 之和的 map：

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

template <class Node_CItr, class Node_Itr, class Cmp_Fn, class _Alloc>
struct my_node_update {
    virtual Node_CItr node_begin() const = 0;
    virtual Node_CItr node_end() const = 0;
    typedef int metadata_type;
    // 以上为固定格式
    void operator()(Node_Itr it, Node_CItr end_it) {
        Node_Itr l = it.get_l_child(), r = it.get_r_child();
        int left = 0, right = 0;
        if (l != end_it) left = l.get_metadata();
        if (r != end_it) right = r.get_metadata();
        const_cast <metadata_type&>(it.get_metadata()) = left + right + (*it)->second;
    }
    // operator 的功能是将节点信息更新为左右孩子信息之和
    int prefix_sum(int x) {
        int ans = 0;
        Node_CItr it = node_begin();
        while (it != node_end()) {
            Node_CItr l = it.get_l_child() , r = it.get_r_child();
            if (Cmp_Fn()(x ,(*it)->first)) it = l;
            else {
                ans += (*it)->second ;
                if (l != node_end()) ans += l.get_metadata();
                it = r;
            }
        }
        return ans ;
    }
    int interval_sum (int l, int r) {
        return prefix_sum(r) - prefix_sum(l - 1);
    }
};

tree<int, int, less<int>, rb_tree_tag, my_node_update> t;

int main() {
    for (int i = 1; i <= 10; i += 2) {
        t.insert(make_pair(i, i * 2 + 1));
    }
    printf("%d\n", t.interval_sum(3, 6));
    return 0;
}

STL

vector

优先队列

set

位运算

__builtin 函数

bitset

pbds

hash_table

priority_queue

tree

发送评论 编辑评论

`__builtin` 函数

发送评论编辑评论