仍在施工中

介绍C++ STL的一些函数和容器的用法。

简介

C++ Standard Template Library（标准模板库），简称 STL

成员

容器

map

有建立映射的关系。对于每一个 $key$ 有一个 $value$ 与之对应。

$$ key -> value $$

时间复杂度 $ O(log_n) $

使用前包含头文件 <map>

#include<map>

比如我们新建了一个 map 叫 m，$key$ 是 string 类型，$key$ 是 int 类型，可以这么写：

map <string, int>m;

m.find(x)：传入 $key$。如果找到返回迭代器；否则返回 m.end()。由此可以发现，m.find(x)!=m.end() 可以判断 m[x] 是否存在

m.erase(x)：删除 m[x]

m.clear()：清空 m

如何遍历 map 中的元素？

for (auto it = m.begin(); it != m.end(); it++) {
    string id = it->first;
    int val = it->second;
    cout << id << ':' << val << el;
}

其中的 auto 会自动获取类型。在此样例中等价于map <string, int>::iterator

注：auto 需要在 C++11 下使用。正式赛中也可使用

#include<iostream>
#include<map>
#define el endl
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    map <string, int>m;
    m["aaa"] = 999;
    m["bbb"] = 8;
    m["uuu"] = 888;
    m["haha"] = 888;
    m["o"] = 23456;
    //查询
    bool find_bbb = m.find("bbb") != m.end();
    bool find_ccc = m.find("ccc") != m.end();
    cout << find_bbb << ' ' << find_ccc << el;
    //1 0

    //删除
    bool find_o_before = m.find("o") != m.end();
    m.erase("o");
    bool find_o_after = m.find("o") != m.end();
    cout << find_o_before << ' ' << find_o_after << el;
    //1 0

    //元素数量
    cout << m.size() << el;
    //4

    //遍历
    for (auto it = m.begin(); it != m.end(); it++) {
        string id = it->first;
        int val = it->second;
        cout << id << ':' << val << el;
    }
    /*
      aaa:999
      bbb:8
      haha:888
      uuu:888
     */
    return 0;
}

unordered_map

与map类似，但底层是通过Hash实现的，打CF比赛不要用，由于它的Hash模数是固定的所以容易被Hack。它的时间复杂度为 $ O(1) $

set

用以维护一个不可重集合

头文件<set>：

#include<set>

定义时：

set <int>s;

会定义一个名叫s的、存储元素类型为int的集合

与map类似，也有find、erase、size、clear函数

遍历元素：和 map 一样，也可以使用迭代器来遍历元素：

for (auto it=s.begin();it!=s.end();it++)
    cout << *it << " ";

set 会自动对其中的元素做升序排列并去重

我觉得这样更方便：

for (int val : s)
    cout << val << " ";

set 与 map 一样，依赖与二叉平衡树。时间复杂度 $ O(log_n) $

如果我们希望维护一个可重的集合如 $A=\{1,1,2,3\}$，可以使用 multiset 来实现

multiset

multiset 可以维护一个可重的集合

它也包含在 <set> 中。

m.lower_bound(val)：返回小于等于 val 中最大数的地址（-1就是 val的前驱）

m.upper_bound(val)：返回 val的后继

由于 multiset 可重的特性，删除元素有两种情况

• 删除所有值为 x 的元素

m.erase(x);

• 删除一个值为 x 的元素

if (m.find(x) != m.end())
    m.erase(m.find(x));

注意判断 x 是否存在

priority_set

优先队列。

给一个序列插入元素并及时获取最大值或最小值

以 $O(log_n)$ 插入元素；$O(1)$ 获得最大/小值

头文件：<queue>

priority_queue <int>q;

建立名为 q 的优先队列，存储元素类型为 int

priority_queue <int, vector<int>, greater<int> >q;

同上，但这让队首从最大值变为最小值

q.top()：获取队首

q.pop()：弹出队首

q.size()：获取大小

q.push(x)：将 x 插入优先队列

优先队列不提供clear

这里有一道优先队列的例题：P3378 【模板】堆

函数

sort

传入排序的开始和结束的下一个地址。

排序类似 vector、string的容器排序时：调用

sort(s.begin(), s.end());

unique

（英文单词独特）

对有序数组进行去重的功能

假设我们有：

$$ a_1=1,a_2=1,a+3=2,a_4=2 $$

要对 $a_1$ ~ $a_4$ 去重，调用 unique(a+1,a+1+4)即可

unique(a+1,a+1+4)会返回

reverse

翻转。

传入翻转的开始和结束的下一个地址。同sort，如果是string等，使用

reverse(s.begin(), s.end());

（会修改以前的数组！