STL 简单讲解
网上有很多很好的资料可以参考
而直接看标准是最准确清晰的
vectorstackqueue/priority_queuedeque
arraymap/multimapset/multisetunordered_mapunordered_set- 关于指针和迭代器
- !!!
pbds - ……
本文默认认为读者会基本的 STL 应用。
一切 STL 从 \(0\) 开始左闭右开！
顺序容器
vector 是最常用的，动态数组。
vector<int> v(n, 0)v.reserve(n)预分配空间，加速push_backv.push_back(x)v.clear()只是移动指针，但是不会改变占用的内存！v.shrink_to_fit()缩减内存到恰好有v.size()个。
其常用的复杂度如下：
- 随机访问：\(O(1)\)
- 在末尾删除或者加入元素：均摊 \(O(1)\)
- 插入或删除一个元素：与到
vector末尾的距离成线性 \(O(n)\)。
还有一些常用的成员函数：
-
v.at(i)访问指定位置的元素，进行越界检查（聊胜于无） -
v.front(), v.back()访问开头/结尾的元素，在空容器上调用是未定义行为 -
v.empty() / v.size() / v.resize() -
\(O(n)\) 删除/加入一个元素的写法，删除需要保证一定存在！
v.erase(lower_bound(begin(v), end(v), x)); v.insert(lower_bound(begin(v), end(v), x), x); -
离散化的操作？ \(O(n \log n + n)\)
sort(begin(v), end(v)); v.erase(unique(begin(v), end(v)), end(v));begin(v)和v.begin()等价，end(v)同理
deque 是神秘的双端队列。
与 std::vector 相反，deque 的元素不是相接存储的：典型实现用单独分配的固定尺寸数组的序列，外加额外的登记，这表示下标访问必须进行二次指针解引用，与之相比 vector 的下标访问只进行一次。
摘自 cppreference
也就是唯一与 vector 的区别在于可以 \(O(1)\) 的 push_front() / pop_front()。
其他的东西和 vector 一模一样（只是常数比较大）。
stack 和 queue 以及 priority_queue 称为容器适配器。
该类模板表现为底层容器的包装器—，即只提供特定函数集合。
默认情况下，stack 和 queue 都是使用 deque 作为底层，所以常数很大。
一般来说，stack 应当用 vector 代替，queue 手写即可（除非不知道到底会有多少元素入队）。
priority_queue 底层默认是 vector，其常数仍然很大……但是还是有替代品（一般不需要）
在 algorithm 库中有 make_heap / push_heap / pop_heap / sort_heap 操作，但我声称没有必要。
还有三个存在感极差的顺序容器：
array<T, N>就是 STL 中的静态数组，一般用在套 vector 的情况：vector< array<int, 2> > f(n);list / forward_list可以用在邻接表中，但是不如用vector快。
在这些顺序容器上可以有一些神秘的 STL 操作：
#define all(x) begin(x), end(x)
auto it = find(all(v), x)\(O(n)\) 的在数组中寻找首个 \(x\) 的位置，无返回end(v)。auto it = lower/upper_bound(all(v), x)\(O(\log n)\) 的在有序的数组中寻找 \(x\) 的位置。int cnt = count(all(v), x)\(O(n)\) 的返回其中 \(x\) 的个数。reverse(all(v))\(O(n)\) 翻转。merge(all(v1), all(v2), back_inserter(res))\(O(n + m)\) 的归并两个有序数组。T res = max/min(all(v))\(O(n)\) 的返回最大/最小元素。pair<T, T> res = minmax(all(v))\(O(n)\) 的返回一个pair。iota(all(v), x)循环赋值 \(v[i] = x + i\)。fill(all(v), x) / fill_n(begin(v), siz, x)赋值。- ……
关联容器
分为两大类：
- 有序
map和set和multi...：- 红黑树
- 都是 \(O(\log n)\) 单次操作
- 无序
unordered_map和unoredered_set和unordered_multi...：- 哈希表
- 平均 \(O(1)\)，最坏 \(O(n)\)
有序容器上的操作
s.lower_bound(x)才是 \(O(\log n)\) 的s.find(x)如果没找到返回的是end(s)- 在
multiset上执行count操作是 \(O(\log n + s)\) 的，\(s\) 是元素的个数。
无序上的操作
s.reserve(n)预留 \(n\) 个元素的空间，减少多次插入的时间。
迭代器
有四种迭代器，但是一般只会用到一种：正向迭代器
begin(x), end(x) 返回的就是指向容器开头，末尾的迭代器。
对于顺序容器，操作返回的迭代器为 随机访问迭代器，而关联容器（和 list）返回的则是 双向迭代器。
对于随机访问迭代器，我们可以 it +/- x，而双向迭代器只能 ++it / --it。
对于空迭代器（例如 end(v)）的操作是未定义行为，可能 RE，也可能无事发生。
vector<int> v(10, -1);
iota(begin(v), begin(v) + 5, 0);
vector<int>::iterator it = find(begin(v), end(v), 4);
// int* 也可以看作是随机访问迭代器
int a[100];
fill(a, a + 50, 7);
// for (int i = 0; i < 50; ++i) a[i] = 7;
int *it = lower_bound(a, a + 50, 8); // it == a + 50
失效的迭代器
写珂朵莉树或多或少都知道：
auto itr = split(r + 1), itl = split(l); // 顺序不能颠倒，否则可能RE
这是因为 split(r + 1) 操作可能影响到 l 所在的节点，导致迭代器失效。
不会修改容器的方法一定不会使迭代器或引用失效。修改容器内容的方法可能会使迭代器和/或引用失效。
对于 vector，后面的操作不会影响前面迭代器，如果容量变化也会失效。
vector<int> v(10);
auto it = begin(v) + 5;
v.insert(begin(v) + 7); // it 不失效
v.insert(begin(v)); // it 失效
v.resize(5) // it 失效
对于 deque，可以认为只要修改了内容迭代器就失效了。
对于 map, set, multi... 认为一直有效，除非本身被 erase 或容器被 clear。
对于 unordered_... 也认为一直情况有效，除非插入导致重哈希。
STL 的字符串
读入一行：
string s;
cin >> std::ws;
getline(cin, s);
关于 std::string 的那些事……
可以 clear / insert / pop/push_back / erase / resize / reserve / ...，类似于 vector<char>。
只是多了 s.substr(pos, len) 返回子串 \([pos, pos + len)\) 或者 \([pos, size())\)。
在 \(pos \gt size()\) 时会报错（RE），复杂度与 \(len\) 成线性。
如果不需要对原字符串进行修改，但是需要获取子串，推荐 string_view。
string s = "ni hao guai er zi";
string_view v(s);
string_view sub = v.substr(3, 3); // sub == "hao", O(1);
sub.remove_prefix(1); // sub == "ao", O(1);
sub.remove_suffix(1); // sub == "a", O(1);
然而，我声称可以定义广义字符串：
basic_string<int> v;
for (int i = 0; i < 5; ++i) v += i;
// v = {0, 1, 2, 3, 4}
/* 以下是 C++17 及以上的行为 */
basic_string_view<int> vi(v);
vi.remove_prefix(2);
for (int x : vi) cout << x << ' ';