仍在施工中

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

简介

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

成员

容器

map

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

$key -> value$

时间复杂度 $ O(log_n) $

使用前包含头文件

#include

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

1	map 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 ':' 

}

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

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

有一个综合案例，点击展开！

#include

#include

#define el endl

using namespace std;

int main() {

ios::sync_with_stdio(false);

cin.tie(nullptr);

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

//1 0



//删除

bool find_o_before = m.find("o") != m.end();

m.erase("o");

bool find_o_after = m.find("o") != m.end();

cout ' ' 

//1 0



//元素数量

cout size() 

//4



//遍历

for (auto it = m.begin(); it != m.end(); it++) {

string id = it->first;

int val = it->second;

cout ':' 

}

/*

  aaa:999

  bbb:8

  haha:888

  uuu:888

 */

return 0;

}

unordered_map

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

set

用以维护一个不可重集合

头文件：

#include

定义时：

1	set int>s;

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

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

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

1 2	for (auto it=s.begin();it!=s.end();it++) cout " ";

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

我觉得这样更方便：

1 2	for (int val : s) cout " ";

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

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

multiset

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

它也包含在中。

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

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

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

删除所有值为 x 的元素

1	m.erase(x);

删除一个值为 x 的元素

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

注意判断 x 是否存在

priority_set

优先队列。

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

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

头文件：

1	priority_queue int>q;

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

1	priority_queue int, vectorint>, greaterint> >q;

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

q.top()：获取队首

q.pop()：弹出队首

q.size()：获取大小

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

优先队列不提供clear

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

函数

sort

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

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

1	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等，使用

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

（会修改以前的数组！

简介

成员

容器

map