DinS          Written on 2017/5/20

本专题介绍c++的核心之一：容器。

容器是高效使用c++的必要途径，c++程序员或多或少都会使用，因此本专题只探讨一些容器的高级内容。

对于最基础的容器vector/list/stack/queue等等，有关概念可见我写的数据结构专题，去导航页查看，使用方法可以直接参考cplusplus reference。

1.priority_queue

优先级队列默认使用<比较元素，因此top一定是最大的。如果要建立小顶堆，可以使用<functional>里面定义的函数对象，比如如下代码：

greater<int>表示使用>来比较int类型，这种用法在泛型算法中也经常出现。
结果：

优先级队列的高级用法是如何让其支持自定义类。
有两种方法，一是重载运算符，二是提供自己的函数对象用于比较。
比如我们定义一个node类型，如下

重载了<运算符，于是可以这样使用PQ

就像使用内置类型一样，运行结果：

再试试使用函数对象的方式。

这个函数对象相当于定义了node类型的>比较方式。
然后可以这样建立PQ

结果：

2.map

multimap与map的区别就是允许关键字重复，重复的元素都相邻排列。
首先必须指出，map内部使用的是（通常来说）红黑树，把map当做BBST理解和使用更贴近实际，查找、插入、删除都是O(logn)，并且元素之间有序排列，可以遍历（按升序）。有关BBST的介绍可见《binary search tree》。

map的基础用法与PQ很像，因为二者都是需要比较元素之间的大小。
自定义map的key类型跟PQ一样，或者重载<运算符，或者提供一个函数对象用以填充map构造的第三个参数，这里就不演示了。

使用map而不是unordered_map最重要的一个原因是map里元素是有序的，即我们可以查询范围内的元素。
通常不对关联容器使用泛型算法，利用成员函数完成相应功能。
为了达到这一点，需要使用map的成员函数lower_bound或者upper_bound。

沿用了上个PQ的node结构体。结果：

特别注意虽然叫做lower_bound但是返回的是大于等于的那个元素。

3.unordered_map

这个是hash table，查找插入删除都只要O(1)。有关概念可见《hash table》。
难点在于如何自定义hash的key。

我们定义了一个结构体，将要使用这个结构体作为hash的key。为了做到这一点，我们需要提供hash function

也是一个函数对象，重载()的格式有要求，必须返回size_t且需要是const。
这是入口形式，内部由程序员自己提供hash方式，一般而言可以使用标准库提供的hash内置类型然后拼接。
但是仅仅提供了hash function还不够，为了使用unordered_map我们还需要提供==比较方式。hash table可以不需要<但是必须有==。

也是一个函数对象，不过如果重载了==就不需要单独提供了。
准备好这些之后就可以使用unordered_map了。

构造时除了key和value，依次指定hash function和==。
我用的VS2012的编译器对于自定义key必须用insert(make_pair)才行，也许之后的编译器修复了这个bug?实际上map和unordered_map里面存的都是pair，所以insert的参数必须也是pair才行。
结果：