STL提供了4种关联容器：set、multiset、map、multimap。关联容器将值和键关联在一起，通过键来查找值。这4种容器都是可反转的经过排序的关联容器，不可以指定插入位置，因为需要保持有序性，可提供对元素的快速访问，内部采用红黑树实现。

set是有序集合，multiset是有序多重集合。set的键和值是统一的，值就是键，set的每个键都是唯一的，不允许重复；而multiset与set类似，只是允许多个值的键相同。使用set或multiset时，需要引入头文件#include<set>。

set或multiset的迭代器为双向访问，不支持随机访问。执行一次“++”和“--”操作的时间复杂度均为 O (log n )。默认的元素顺序为升序，也可以通过第2个模板的参数设置为降序。

成员函数如下。

● size/empty/clear：元素个数、判空、清空。

● begin/end：开始位置和结束位置。

● insert( x )：将元素 x 插入集合。

● erase( x )：删除所有等于 x 的元素。

● erase(it)：删除it迭代器指向的元素。

● find( x )：查找元素 x 在集合中的位置，若不存在，则返回end。

● count( x )：统计等于 x 的元素个数。

● lower_bound/upper_bound：返回大于或等于 x 的最小元素位置、大于 x 的最小元素位置。

训练1　集合合并

题目描述（HDU1412）： 给定两个集合 A 、 B ，求 A + B （在同一个集合中不会有两个相同的元素）。

输入： 每组输入数据均分为三行。第1行包含两个整数 n 和 m （0< n , m ≤10 000），分别表示集合 A 和集合 B 中的元素个数；后两行分别表示集合 A 和集合 B 中的元素（不超出int范围的整数），元素之间以一个空格隔开。

输出： 单行输出合并后的集合，要求从小到大输出，元素之间以一个空格隔开。

1. 算法设计

本题是两个集合的合并问题，集合不允许元素重复，且输出时有序。set是有序集合，且每个键都是唯一的，不允许重复，因此可以使用set解决，具体如下。

（1）定义一个set，记录合并后的集合。

（2）将第1个集合中的元素插入set。

（3）将第2个集合中的元素插入set。

（4）按顺序输出集合中的元素。

2. 算法实现

训练2　并行处理

题目描述（POJ1281）： 并行处理中的编程范型之一是生产者/消费者范型，可以使用具有管理者进程和多个客户进程的系统来实现。客户可以是生产者、消费者等，管理者跟踪客户进程。每个进程都有一个成本（正整数，范围是1～10 000）。具有相同成本的进程数不能超过10 000。队列根据三种类型的请求进行管理，如下所述。

● a x ：将成本为 x 的进程添加到队列中。

● r ：根据当前管理者策略从队列中删除进程（如果可能）。

● p i ：执行管理者的策略 i ，其中 i 是1或2。1表示删除最小成本进程；2表示删除最大成本进程。默认管理者策略为1。

● e ：结束请求列表。

只有在删除列表中包含已删除进程的序号时，管理者才会输出已删除进程的成本。编写一个程序来模拟管理者进程。

输入： 输入中的每个数据集都有以下格式。

● 进程的最大成本。

● 删除列表的长度。

● 删除列表。查询已删除进程的序号列表；例如1 4，表示查询第1个和第4个已删除进程的成本。

● 每个请求列表，各占一行。

每个数据集都以 e 请求结束。数据集以空行分隔。

输出： 如果删除请求的序号在列表中，并且此时队列不为空，则单行输出删除的每个进程的成本。如果队列为空，则输出-1。以空行分隔不同数据集的结果。

1. 算法设计

因为可能有多个相同成本，因此使用multiset解决。

（1）用vis[]标记删除列表要显示的序号。

（2）默认管理者策略， p =1。

（3）读入字符，判断执行相应的操作。

（4）进行删除操作时，如果队列为空，则输出-1；判断管理者策略，如果 p =1，则删除最小成本，否则删除最大成本。如果删除的成本序号在删除列表中，则输出该成本。 3wzY7NDpKuzr557oQO/baLrnyd/lq5rUWVJ1LnSGtkJNM7lE40EsPyaT7tegvSF4

2. 算法实现