STL初步

目录

• vector/queue/deque/priority queue（前面讲过的）

• set/multiset

• map/multimap

• unordered的容器

set（集合）

set（集合）是兼顾插入、删除、查找的一个优秀的数据结构，其底层代码实现是红黑树（平衡树），可以做到插入、删除、查找都是 $O(\log n)$ 的。

另外set中不会出现相同的元素。如果需要重复元素，用multiset。

插入和删除操作：

insert(x)当容器中没有等价元素的时候，插入x

erase(x)删除值为x的所有元素，返回删除元素的个数

erase(pos)删除迭代器为pos的元素，要求迭代器合法

erase(first,last)删除迭代器在[first,last)内的所有元素

clear()清空set

set的迭代器和其他结构不太一样，不能直接for一个整数变量做。

遍历set的一般方法：

set<int> s;
set<int>::iterator it;
for(it=s.begin();it!=s.end();++it) cout<<*it<<" ";

在c++11及以上（-std=c++14），可以使用范围类型的循环使得代码更简洁。

set<int> s;
for(auto x:s) cout<<x<<" ";

跟查找有关的函数：

count(x)返回set内键为x的元素数量

find(x)在set内存在键为x的元素时返回该元素的迭代器，否则返回end()。

lower_bound(x)返回指向首个不小于给定键的元素的迭代器，若不存在返回end()

upper_bound(x)返回指向首个大于给定键的元素的迭代器，若不存在返回end()

empty()返回容器是否为空

size()返回容器内元素个数

注意，set中的元素都是排好序的！

板子：暂无

1. P5250 木材仓库

题面

博艾市有一个木材仓库，里面可以存储各种长度的木材，但是保证没有两个木材的长度是相同的。作为仓库负责人，你有时候会进货，有时候会出货，因此需要维护这个库存。有不超过 100000 条的操作：

进货，格式1 Length：在仓库中放入一根长度为 Length(不超过 10^9) 的木材。如果已经有相同长度的木材那么输出Already Exist。

出货，格式2 Length：从仓库中取出长度为 Length 的木材。如果没有刚好长度的木材，取出仓库中存在的和要求长度最接近的木材。如果有多根木材符合要求，取出比较短的一根。输出取出的木材长度。如果仓库是空的，输出Empty。

输入：

输出：

解析

可以用map做，不过set更方便。

这是由于set的insert(x)函数有返回值，它返回一个pair，这个pair的第二项是一个布尔变量表示是否插入成功。

因此可以直接用s.insert(x).second来判断是否有重复。

对于查找，可以用lower_bound函数找到第一个不小于指定长度的，用它和它的前一个来比较指定长度即可。

set用处小结

其实set就是一个平衡树，可以用来插入、删除、查找第k名的数据等。

不过set的功能和比较方式比较单一，如果要其他功能的话需要自己写。

map

map 是有序键值对容器，它的元素的键是唯一的。搜索、移除和插入操作拥有对数复杂度。map 通常实现为 红黑树。

设想如下场景：现在需要存储一些键值对，例如存储学生姓名对应的分数：Tom 0，Bob 100，Alan 100。但是由于数组下标只能为非负整数，所以无法用姓名作为下标来存储，这个时候最简单的办法就是使用 STL 中的 map。（虽然开结构体也行，但是如果遇到一个键可能对应多个值的时候，结构体的查找就显得很慢）

定义方式：

map<Keytype, Valuetype>mp;

这里Keytype是键的类型，Valuetype是值的类型，如：

map<string,int>mp;

map可以使用[]来访问元素，具体规则是map[key]=value。

map中不会存在键相同的元素，如果需要使用键相同的元素，请使用multimap。

可以直接通过下标访问来进行插入和删除操作。

如：map[Alan]=99

或者直接map.insert(pair<Keytype,Valuetype>)

例：在上一页的map里可以这么插入：

mp.insert(pair<string,int>(“Alan”,100));

删除可以用map.erase(key)来做，会删除键为key的所有元素。

而清空可以用map.clear()来做。

如果你在map里访问了一个原来不存在的key，那么map会先把这个key插入到里面再访问。

当下标访问操作过于频繁时，容器中会出现大量无意义元素，影响 map 的效率。因此一般情况下推荐使用 find() 函数来寻找特定键的元素。

map提供以下的查询操作：

count(x): 返回容器内键为 x 的元素数量。复杂度为 O(log(size)+ans)（关于容器大小对数复杂度，加上匹配个数）。

find(x): 若容器内存在键为 x 的元素，会返回该元素的迭代器；否则返回 end()。

lower_bound(x): 返回指向首个不小于给定键的元素的迭代器。

upper_bound(x): 返回指向首个大于给定键的元素的迭代器。若容器内所有元素均小于或等于给定键，返回 end()。

empty(): 返回容器是否为空。

size(): 返回容器内元素个数。

1. P5266

题面

输入：

输出：

解析

如果用结构体的话，查找会很麻烦。

所以，这题可以算是map的板子题，用map的操作即可实现所有功能。

无序关联式容器

上面的四种容器都有其unordered的版本。 无序版本采用哈希来进行存储，内部元素不以任何特定顺序进行排序，所以访问无序关联式容器中的元素时，访问顺序也没有任何保证。

采用哈希存储的特点使得无序关联式容器“在平均情况下”大多数操作（包括查找，插入，删除）都能在常数时间复杂度内完成，相较于关联式容器与容器大小成对数的时间复杂度更加优秀。

在操作方式上和之前讲的容器基本也一样，这里不再多说。

这些容器本质上都是哈希表，哈希表我们放到后面讲。