STL 简单讲解

网上有很多很好的资料可以参考

而直接看标准是最准确清晰的

vector
- stack
- queue / priority_queue
- deque
array
map / multimap
set / multiset
unordered_map
unordered_set
关于指针和迭代器
!!! pbds
……

本文默认认为读者会基本的 STL 应用。

一切 STL 从 \(0\) 开始左闭右开！

顺序容器

vector 是最常用的，动态数组。

vector<int> v(n, 0)
v.reserve(n) 预分配空间，加速 push_back
v.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 一模一样（只是常数比较大）。

deque-alloc

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 << ' ';