第一章 STL概论与版本简介

STL 的提出是为了提高代码的复用性, 提升编程效率. STL 提供六大组件, 彼此可以组合套用:

容器(containers): 各种数据结构, 如 vector, list, deque, set, map 等 class template;
算法(algorithms): 各种常用算法如 sort, search, copy, erase 等 function template;
迭代器(iterators): 扮演容器与算法之间的胶合剂, 从实现角度看, 迭代器是一种将 operator*, operator->, operator++, operator-- 等指针相关操作予以重载的 class template;
仿函数(functors): 行为类似函数, 可作为算法的某种策略.
配接器(adapters): 一种用来修饰容器(containers), 仿函数(functors), 或者迭代器(iterators)接口的东西. 例如, STL 提供的 queue 和 stack, 虽然看似容器, 其实只能算是一种容器配接器, 因为它们的底层完全借助 deque 完成. 改变 functor 接口者, 称为 function adapter, 改变 container 接口者, 称为 container adapter, 改变 iterator 接口者, 称为 iterator adapter.
配置器(allocators): 负责空间配置与管理, 从实现角度来看, 配置是是一个实现了动态空间配置, 空间管理, 空间释放的 class template.

以上六者的关系为: Container 通过 Allocator 取得数据存储空间, Algorithm 通过 Iterator 存取 Container 内容, Functor 可以协助 Algorithm 完成不同的策略变化, Adapter 可以修饰或套接 Functor.

4.8 priority_queue

priority_queue 首先是一个队列, 因此它允许在底端加入元素, 并从顶端取出元素, 除此之外别无其他存取元素的途径. priority_queue带有权值观念, 其内部的元素并非依照插入顺序排序, 而是按照元素的权值进行排列, 权值较高者, 排在最前面.

缺省情况下 priority_queue 利用一个 max-heap 完成, 也即 top() 元素表示的是队列中值最大的元素.

priority_queue 的实现在缺省情况下是以 vector 为底部容器, 再加上 heap 相关处理规则, 所以其实现非常简单, 也因此, 我们通常并不认为 priority_queue 并非是一种新的容器, 而只是把它归类为 container adapter(容器配接器).

1	// priority_queue 内部完整实现

由于 priority_queue 只有顶端元素 (权值最高者) 才有机会被外界使用, 因此, priority_queue 不提供遍历功能, 也不提供迭代器.

//TODO