学习材料 - deque/list
#include<deque>
双端队列 deque 是一个支持在两端高效插入或删除元素的连续线性存储空间。 它就像 vector 和 queue 的结合。 与 vector 相比，deque 在头部增删元素仅需要 O(1) 的时间；与 queue 相比，deque 像数组一样支持随机访问。
| 方法 | 描述 | 示例 | 时间复杂度 |
|---|---|---|---|
| [] | 随机访问 | 与 vector 类似 |
|
| begin()/end() | deque 的头/尾部迭代器 |
与 vector 迭代器类似 |
|
| front()/back() | 队头/尾元素 | 与queue类似 |
|
| push_back(x) | 从队尾入队 | que.push_back(x); |
|
| push_front(x) | 从队头入队 | que.push_front(y); |
|
| pop_front() | 从队头出队 | que.pop_front( ); |
|
| pop_back() | 从队尾出队 | que.pop_back( ); |
|
| clear() | 清空队列 | que.clear( ); |
#include<list>
list 就是链表，在确定位置的情况下，能够快速插入、删除，但是不支持随机化访问。
可以将 list 当作双端队列使用，当定义多个双端队列时，list 效率要高很多。
| 方法 | 描述 | 示例 | 时间复杂度 |
|---|---|---|---|
| begin()/end() | 返回头/尾部迭代器 | 与 vector 迭代器类似 |
|
| front()/back() | 返回第一个/最后一个元素 | 与 queue 类似，l.front() 等价于 *l.begin() |
|
| size() | 返回 list 中元素个数 | 与 vector类似 |
|
| insert(iterator pos,value) | 在 pos 位置之前插入 value | l.insert(l.begin(),10) |
注意虽然插入是常数复杂度，但要找到 pos 位置需要 |
| erase(iterator pos) | 删除 pos 位置的元素 | l.erase(l.begin()); |
注意虽然删除是常数复杂度，但要找到 pos 位置需要 |
| push_front(x)/push_back(x) | 从头/尾添加 x | 同 deque |
|
| pop_front()/pop_back() | 从头/尾删除元素 |
例子：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ios::sync_with_stdio(0);cin.tie(0);
list<int> l = {7, 5, 16, 8};
l.push_front(25);
l.push_back(13);
// 查找 16 的位置 O(n)
auto it = std::find(l.begin(), l.end(), 16);
if (it != l.end())
l.insert(it, 42); //在找到位置的情况下 插入 O(1)
// 输出
cout << "l = { ";
for (int n : l)
cout << n << ", ";
cout << "};\n";
return 0;
}
输出：
l = { 25, 7, 5, 42, 16, 8, 13, };
学习完毕
{{ select(1) }}
- YES
- NO