map

map 是一种映射容器，其头文件是 map。

遍历 map 可以使用迭代器。

map<int,int> m;
for(map<int,int>::iterator i=m.begin();i!=m.end();i++){
	int id=i->first; //id 为下标
  	int value=i->second;//value 为元素
}

其中 map<int,int>::iterator 在使用 C++11 以上时可替换为 auto，CSP-J/S 及 NOIP 等比赛可以使用。auto 为自动类型推断，请勿滥用 auto。

map 底层为二叉平衡树（红黑树），因此单次操作时间复杂度为 $O(\log n)$。

set

set 是一个 不可重 集合，其头文件是 set。

遍历 set 可以使用迭代器。

set<int> s;
for(set<int>::iterator i=s.begin();i!=s.end();i++){
	int value=*i;
}

set 会自动将元素去重并进行升序排序。

map 底层为二叉平衡树，因此单次操作时间复杂度为 $O(\log n)$。

multiset

multiset 与 set 类似，但是 multiset 是 可重的，其头文件是 set。

由于 multiset 是可重的，所以做删除操作有两种情况，分别是删除所有值为 x 的元素，和删除一个值为 x 的元素。

s.erase(x) //删除所有值为 x 的元素
if(s.find(x)!=s.end()){
    s.erase(s.find(x)); //删除一个值为 x 的元素
}

可以通过 lower_bound() 函数与 upper_bound() 函数查询 mutiset 中 x 的前驱及后继。

set<int>::iterator it=s.lower_bound(x);
it--;
int pre=*it; //前驱

set<int>::iterator it=s.upper_bound(x);
int nxt=*it; //后继

priority_queue

priority_queue 是一个优先队列，在头文件 queue 中。

优先队列是一个弹出元素时弹出最大值的数据结构。

priority_queue 可在 $O(\log n)$ 的时间复杂度插入元素，在 $O(1)$ 的时间复杂度获取/弹出队首元素。

例题：【模板】堆

给定一个数列，初始为空，请支持下面三种操作：

1. 给定一个整数 $x$，请将 $x$ 加入到数列中。
2. 输出数列中最小的数。
3. 删除数列中最小的数（如果有多个数最小，只删除 $1$ 个）。

思路：使用 priority_queue<int,vector<int>,greater<int> > q 让最小值放在队首，按照题目说明及上方表格完成操作。

例题：合并果子

通过模拟合并的过程，我们会发现每次选择两个最小的元素合并成较大的元素是最优策略，可以由哈夫曼编码证明（具体请参考《深基》）

因而，每次从序列中找到最小值和次小值，将其相加再放入序列中即可。时间复杂度为 $O(n \log n)$。