Blog of RuSun

\begin {array}{c} \mathfrak {One Problem Is Difficult} \\\\ \mathfrak {Because You Don't Know} \\\\ \mathfrak {Why It Is Diffucult} \end {array}

STL的妙用

发表于 分类于
本文字数： 3.2k 阅读时长 ≈ 3 分钟
标签：    

介绍一些 STL 的基本常识和使用。

迭代器

迭代器是 STL 容器中类似指针的东西。在很多时候善于利用迭代器可以让 STL 更加强大。

对于一个容器 s ，可以通过 s.begin() 和 s.end() 得到内存区间。

不同容器的迭代器在这种容器的命名空间中，如定义一个迭代器 set <int> :: iterator it = s.begin() 。

获得这个迭代器 it 对应的值，使用 *it ，如一个 set 中最小的元素为 *s.begin() ，最大的元素为 *--s.end() 。

双向容器支持 it++ ，it-- ，单向容器只支持 it++ 。

例如在 vector <int> 中，需要遍历所有的元素。

因为它支持随机访问元素，所以可以这样写：

1
2
for (int i = 0; i < v.size(); i++)
    // v[i]

因为它支持单向迭代，所以可以这样写：

1
2
for (vector <int> :: iterator i = v.begin(); i != v.end(); i++)
    // *i

注意迭代器不支持 < > 运算，所以使用 != 。

大多数容器也可以这样写：

1
2
for (int i : v)
    // i

STL 算法

大多数容器都可以用的。

  • sort(s.begin(), s.end())
  • reverse(s.begin(), s.end())
  • unique(s.begin(), s.end())
  • erase(s.begin(), s.end())

lower_bound 与 upper_bound

用法 lower_bound(s.begin(), s.end(), v)

前者返回第一个值大于等于 v 的迭代器，后者返回第一个大于 v 的迭代器，通过这两个函数可以实现后继查询。

通过 --lower_bound(s.begin(), s.end(), v) 和 --upper_bound(s.begin(), s.end(), v) 可以实现前驱查询。

在有序的容器下复杂度为 $O(\log n)$ ，一般在排好序的 vector 中使用，因为 vector 的迭代器支持 + - 运算。

注意，set 中需要使用 s.lower_bound(v) 和 s.upper_bound(v) 才能保证复杂度为 $O(\log n)$ ，否则会退化到 $O(n)$ 。

离散化的实现

1
2
3
4
5
6
7
vector <int> ws;
for (int i = 1; i <= n; i++)
    ws.push_back(w[i]);
sort(ws.begin(), ws.end());
int m = ws.erase(unique(ws.begin(), ws.end()), ws.begin()) - ws.begin();
for (int i = 1; i <= n; i++)
    w[i] = lower_bound(ws.begin(), ws.end(), w[i]) - ws.begin() + 1;

list

不想写链表？使用 list ！

  • 头文件：#include <list> 。

  • 左边插入 s.push_front() ，删除 s.pop_front() 。

  • 右边插入 s.push_back() ，删除 s.pop_back() 。

  • 定位到这个元素的迭代器后 s.erase(it) 。注意，删除后不能继续迭代，因为当前迭代器被删除了，就不能正确地找到下一个迭代器了。正确的写法是这样：

    1
    2
    3
    4
    5
    for (list<pair<int, int>>::iterator i = s.begin(); i != s.end();)
        if ((*i).first == 3)
            i = s.erase(i);
    else
        i++;

    因为 s.erase() 会返回下一个删除的迭代器。

    当然也支持区间删除，这意味着你还是需要找到两个迭代器。

list 并不能替代链表的所有功能，但在简单的应用上很方便。

priority_queue

优先队列不是线性的。

本质是堆，操作有一个 $\log$ 。

配合结构体使用会很强大。

注意默认是大根堆，需要重载运算符 > 。

1
2
3
4
5
struct Node {
    int t, k;
    friend bool operator > (const Node &x, const Node &y) { return x.k < y.k; }
}
priority_queue <Node> q;

或者这样写：

1
2
3
4
5
struct Node {
    int t, k;
    friend bool operator < (const Node &x, const Node &y) { return x.k > y.k; }
}
priority_queue <Node, vector <Node>, greater<Node> > q;

还可以写 lambda 函数自定义 Compare

1
2
3
typedef pair<int, int> PII;
bool cmp = [](const PII &x, const PII &y) { return x.second < y.second; };
priority_queue<PII, std::vector<PII>, decltype(cmp)> q(cmp);

在其他的 STL 中，如 set 中，不能写 lambda 函数。

必须写在一个类里面，因此，可以这样写：

1
2
3
4
struct cmp {
  bool operator()(int a, int b) { return a > b; }
};
set<int, cmp> s;

string

几个常见的函数：

  • s.find(t) 。
  • s.substr(st, len) 。
  • s.insert(st, t) 。
  • s.erase(st, len) 。

还支持 s += t s + t 。

但是注意复杂度和字符串长度线性相关，并且输入输出必须用 cin cout ，所以比较慢。

一般尽量用 char ，遇到字符串的题，做不来，可以用 string 的函数打暴力。

bitset

相当于 vector<bool> 但是强大得多；相当于用于状压的 int ，但是没有 $32$ 位的限制。

定义： bitset<N> f ，位数为 $N$ 。

一般用于优化暴力，比如

1
2
for (int i = 0; i < n; i++)
    f[k][i] &= f[k -1][i];

可以写作

1
f[k] &= f[k - 1]

复杂度可以从 $O(n)$ 优化到 $O(\frac n \omega)$ 。

支持所有位运算，但是不能和 int 计算，支持 cin cout 。

unordered_map 和 unordered_set

这是两个坑，千万不要用。遇到大值域问题，优先考虑离散化，实在不行另可多一个 $\log$ 用 map 或 set ，因为这两个坑最坏情况下单次操作为 $O(n)$ 。

deque

可以完全用 list 代替了。

stack 和 queue

推荐手写，如果操作中不能确定需要多大空间，就用 STL。

相关文章