STL 简单讲解

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

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

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

一切 STL 从：正向迭代器

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

jeefy

C++ STL 容器简单讲解

STL 简单讲解

失效的迭代器

STL 的字符串