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

1 基础知识

无。

2 模板

vector, 变长数组，倍增的思想size()  返回元素个数empty()  返回是否为空clear()  清空front()/back() 使用时，必须判断向量类容器非空push_back()/pop_back()begin()/end()[]支持比较运算，按字典序pair<int, int>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<int, vector<int>, greater<int>> 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/multisetinsert()  插入一个数find()  查找一个数count()  返回某一个数的个数erase()(1) 输入是一个数x，删除所有x   O(k + logn)(2) 输入一个迭代器，删除这个迭代器lower_bound()/upper_bound()lower_bound(x)  返回大于等于x的最小的数的迭代器upper_bound(x)  返回大于x的最小的数的迭代器map/multimapinsert()  插入的数是一个pairerase()  输入的参数是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()  返回有多少个1any()  判断是否至少有一个1none()  判断是否全为0set()  把所有位置成1set(k, v)  将第k位变成vreset()  把所有位变成0flip()  等价于~flip(k) 把第k位取反list, 链表

3 使用示例

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

3.1 vector

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

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

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

#include <iostream>
#include <vector>using namespace std;int main() {vector<int> a = {10};vector<int> b = {1,2};if (a > b) puts("a > b");return 0;
}

输出为，

a > b

3.2 pair

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

#include <iostream>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;
}

输出为，

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

3.3 string

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

#include <iostream>
#include <string>using namespace std;int main() {string s = "abcdefgh";string s1 = s.substr(1,2); //从下标1开始，长度为2的子串，即bcstring s2 = s.substr(1,7); //从下标1开始，长度为7的子串，即bcdefghstring s3 = s.substr(1,10); //从下标1开始，长度为10的子串。由于从下标1开始到末尾的子串的长度为7，而10大于7，那么返回空子串。cout << "s1 = " << s1 << ", s2 = " << s2 << ", s3 = " << endl;return 0;
}

输出如下内容，

s1 = bc, s2 = bcdefgh, s3 = 

3.4 queue

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

#include <iostream>
#include <queue>using namespace std;int main() {queue<int> q;q.push(1);q.push(2);q.push(3);q = queue<int>();return 0;
}