acwing算法基础之数据结构--STL简介

1 基础知识

无。

2 模板

vector, 变长数组，倍增的思想
    size()  返回元素个数
    empty()  返回是否为空
    clear()  清空
    front()/back() 使用时，必须判断向量类容器非空
    push_back()/pop_back()
    begin()/end()
    []
    支持比较运算，按字典序

pair
    first, 第一个元素
    second, 第二个元素
    支持比较运算，以first为第一关键字，以second为第二关键字（字典序）

string，字符串
    size()/length()  返回字符串长度
    empty()
    clear()
    substr(起始下标，(子串长度))  返回子串
    c_str()  返回字符串所在字符数组的起始地址

queue, 队列
    size()
    empty()
    push()  向队尾插入一个元素
    front()  返回队头元素
    back()  返回队尾元素
    pop()  弹出队头元素

priority_queue, 优先队列，默认是大根堆
    size()
    empty()
    push()  插入一个元素
    top()  返回堆顶元素
    pop()  弹出堆顶元素
    定义成小根堆的方式：priority_queue, greater> q;

stack, 栈
    size()
    empty()
    push()  向栈顶插入一个元素
    top()  返回栈顶元素
    pop()  弹出栈顶元素

deque, 双端队列
    size()
    empty()
    clear()
    front()/back()
    push_back()/pop_back()   往队尾插入元素/弹出队尾
    push_front()/pop_front() 往队头插入元素/弹出队头 
    begin()/end()
    [] 支持随机寻址

set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列
    size()
    empty()
    clear()
    begin()/end()
    ++, -- 返回前驱和后继，时间复杂度 O(logn)

    set/multiset
        insert()  插入一个数
        find()  查找一个数
        count()  返回某一个数的个数
        erase()
            (1) 输入是一个数x，删除所有x   O(k + logn)
            (2) 输入一个迭代器，删除这个迭代器
        lower_bound()/upper_bound()
            lower_bound(x)  返回大于等于x的最小的数的迭代器
            upper_bound(x)  返回大于x的最小的数的迭代器
    map/multimap
        insert()  插入的数是一个pair
        erase()  输入的参数是pair或者迭代器
        find()
        []  注意multimap不支持此操作。 时间复杂度是O(logn)
        lower_bound()/upper_bound()

unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表
    和上面类似，增删改查的时间复杂度是 O(1)
    不支持 lower_bound()/upper_bound()， 迭代器的++，--

bitset, 圧位
    bitset<10000> s;
    ~, &, |, ^
    >>, <<
    ==, !=
    []

    count()  返回有多少个1

    any()  判断是否至少有一个1
    none()  判断是否全为0

    set()  把所有位置成1
    set(k, v)  将第k位变成v
    reset()  把所有位变成0
    flip()  等价于~
    flip(k) 把第k位取反

list, 链表
    
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

3 使用示例

支持front()和back()操作的容器有：vector、queue、deque。
支持top()和pop()操作的容器有：stack、priority_queue。

3.1 vector

系统为某一程序分配空间时，该操作所需时间与待申请的空间大小无关，与申请次数有关。

故需要优化申请空间的操作次数。

vector支持比较运算，规则是按照字典序进行比较。看如下代码，

#include 
#include 

using namespace std;

int main() {
    vector<int> a = {10};
    vector<int> b = {1,2};
    
    if (a > b) puts("a > b");
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

输出为，

a > b
1

3.2 pair

pair可以通过{1,2}或make_pair(1,2)来初始化。看下面代码，

#include 

using namespace std;

int main() {
    pair<int, int> a = {1, 2};
    pair<int, int> b = make_pair(1, 2);
    
    cout << "a.first = " << a.first << ", a.second = " << a.second << endl;
    cout << "b.first = " << b.first << ", b.second = " << b.second << endl;
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

输出为，

a.first = 1, a.second = 2
b.first = 1, b.second = 2
1
2

3.3 string

substr(i, n)返回下标i开始长度为n的子串，当n大于从i到末尾的长度时，返回空子串。请看如下代码，

#include 
#include 

using namespace std;

int main() {
    string s = "abcdefgh";
    string s1 = s.substr(1,2); //从下标1开始，长度为2的子串，即bc
    string s2 = s.substr(1,7); //从下标1开始，长度为7的子串，即bcdefgh
    string s3 = s.substr(1,10); //从下标1开始，长度为10的子串。由于从下标1开始到末尾的子串的长度为7，而10大于7，那么返回空子串。
    
    cout << "s1 = " << s1 << ", s2 = " << s2 << ", s3 = " << endl;
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

输出如下内容，

s1 = bc, s2 = bcdefgh, s3 = 
1

3.4 queue

queue没有clear()函数，故它的清空为queue()。请看如下代码，

#include 
#include 

using namespace std;

int main() {
    queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);
    
    q = queue<int>();
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

3.5 deque

duque为双端队列，正常队列只能在队尾插入，队头弹出，而双端队列可以在队尾插入或队头插入，队头弹出或队尾弹出。

C++代码如下，

#include 
#include 

using namespace std;

int main() {
    deque<int> dq;
    dq.push_back(1);//往队尾插入
    dq.push_back(2);
    dq.push_back(3);
    
    while (!dq.empty()) {
        cout << dq.front() << endl; //输出队头
        dq.pop_front(); //弹出队头
    }
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18