19.02.11 ~ 19.02.13
hjmmm要专攻STL辣
先列一下大纲？
- 第一天：各种基础容器
- 第二天：实现平衡树和平板电视pbds
- 第三天：非变异算法和变异算法
那么我们就开始吧！
Day1
【各种基础容器】
还是先列一下小目录
- vector
- deque
- list
- queue & stack
- priority_queue
- biset
- 集合 set
- 映射 map
分类
| 种类 | 名称 |
|---|---|
| 序列性容器 （可以用链表模拟的那种） | vector, deque, list |
| 关联性容器 （可以用平衡树模拟的那种） | set, map, multiset, multimap |
| 容器适配器（可以用数组模拟的那种） | stack, queue |
基本每个容器都会有的又
比较常用的函数
| 函数名 | 函数类型 | 意义 |
|---|---|---|
| .empty() | bool | 没有元素返回true |
| .size() | int | 元素个数 |
| .max_size() | int | 最大元素个数 |
| = | operator | 将一个容器赋给另一个容器 |
| swap | void | 交换两个容器的元素 |
| .begin() | iterator | 返回第一个元素 |
| .end() | iterator | 返回最后一个元素后面的元素 |
| .erase(xxx) | void | 清除一个元素或几个元素 |
| .clear() | void | 清空所有元素 |
头文件要求
基本上都是 #include <容器名>
好啦现在分别突破！
vector & deque & list
共有的函数
小声：我一直不知道insert函数返回的那个迭代器是什么。。
知道的大佬麻烦在评论指导一下qvq感恩不尽
另外我没写构造函数因为蒟蒻一般不用。。
| 函数名 | 函数类型 | 意义 |
|---|---|---|
| .insert(iterator it, const T& x) | iterator | 在it所指那个元素前加一个x元素 |
| .insert(iterator it, int n, const T& x) | void | 在it所指那个元素前加n个x元素 |
| .insert(iterator it, const_iterator first, const_iterator end) | void | 在it所指那个元素前加入另一个同类型容器[first, last)之间的数据 |
| .push_back(const T& x) | void | 尾部增加元素x |
| .push_front(const T& x) (只有deque，list可以用) | void | 首部增加元素x |
| .erase(iterator it) | iterator | 删除it所指元素 |
| .erase(iterator first, iterator last) | iterator | 删除[first, last)之间的元素 |
| .pop_back() | void | 容器不为空时，删除最后一个元素 |
| .pop_front() （只有deque，list可以用） | void | 容器不为空时，删除第一个元素 |
| .front() | reference（引用） | 首元素引用 |
| .back() | reference | 尾元素引用 |
| .assign(int n, const T& x) | void | 设置容器大小为n每个元素为x |
| .assign(const_iterator first, const_iterator last) | void | 设置容器有且只有[first, last)中的元素 |
deque，vector貌似没有什么别的常用操作了。。
但list还有好多、
函数名 | 函数类型 | 意义
------|----- | -----
.remove(const T& x) | void | 删除元素值等于x的元素
.sort() | void | 排序（默认升序）
.unique() | void | 去重
.reverse() | void | 反转顺序
.splice(iterator it, list& x) | void | 将x中所有元素移入当前list的it元素前
.splice(iterator it, list& x, iterator first) | void | 将x中[first, end)元素移入当前list的it元素前
.splice(iterator it, list& x, iterator first, iterator last) | void | 将x中[first, last)元素移入当前list的it元素前
.merge(list& x) | void | 将x与当前list合并（不同于splice的是， 两序列若各自升序，合并完还是升序）
需要注意的是
- 对任何位置的插入和删除 list永远是常数时间
- vector容量翻倍开，容易炸哦
- vector随机位置插入删除元素比较慢
- deque随机位置操作是线性时间
- list随机位置插入较快 但不支持随机访问
stack & queue & priority_queue
这个大家都跟熟悉啦~
共有的函数
| 函数名 | 函数类型 | 意义 |
|---|---|---|
| .push(const T& x) | void | 插入元素（队尾or栈顶） |
| .pop() | void | 删除元素（队尾or栈顶） |
各自的
- 队首
.front() - 队尾
.back() - 栈顶或优先队列堆顶
.top()
返回值都是reference哦