仍在施工中

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

简介

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

成员

容器

map

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

$$ key -> value $$

时间复杂度 $ O(log\_n) $

使用前包含头文件 <map>

#include

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

map 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 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 q;

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

priority\_queue , greater >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());

（会修改以前的数组！

标签：无

你的评论