容器适配器

所谓容器适配器，就是给顺序容器换了一套“接口”——呃，就是换了一套成员函数。为什么好端端的要换成员函数呢？因为换了一套成员函数可以让这个容器更像典型的数据结构。

栈

堆栈（Stack），简称栈，是一种典型的数据结构。它可以存放一系列数据，但向其中增删有一定的限制。这个增删限制称为“后进先出”（Last-In First-Out），后进入栈的数据必须先离开栈。

想象这样的场景，在餐厅摞了一堆盘子。这些盘子从下到上码放起来，分别代表栈中的数据。如果想要拿到最底下的盘子，就必须把上面的盘子都拿掉才可以。反之，如果想要往里面增加盘子，只能把它放在最上面。这就是堆栈这个词的来源，它形象地解释了堆栈“后进先出”这个限制。

向栈中增加元素称为栈的推入（Push）操作，从栈中移除元素称为站的弹出（Pop）操作。一般，栈中可以被弹出的那个元素——就是最顶上的盘子——是栈中唯一可以读取的元素，它被称为栈的顶（Top）元素。

std::stack 类模板通过给 std::vector 换了一套接口模拟了这些操作。

#include <stack> // 定义于此
int main() {
    std::stack<int> a;
    // 推入
    a.push(1);
    a.push(2);
    a.push(3);
    // 读取栈顶并弹出
    int top{a.top()}; // 3
    a.pop();
    top = a.top();    // 2
    // 其它操作
    a.empty(); // 检查栈是否为空
    a.size();  // 获取栈中元素个数
}

队列

队列（Queue），也是一种典型的数据结构。它可以存放一系列数据，但向其中增删也有称为“先进先出”（First-In First-Out）的限制：先进入队列的数据必须先离开队列。想象队列的场景也非常自然：比如排队买票。每个人代表队列中的数据，只有队首买到票的人才能离开队列，而新来的人必须排在队列的末尾。

向队列中添加元素也叫推入（Push），从队列中移除元素也叫弹出（Pop）。一般，队列中可以读取两个元素：可以弹出的队首（Front）元素和最后一个队尾（Back）元素。

std::queue 类模板通过给 std::deque 换了一套接口模拟了这些操作。

#include <queue> // 定义于此
int main() {
    std::stack<int> a;
    // 推入
    a.push(1);
    a.push(2);
    a.push(3);
    // 读取队首和队尾
    int front{a.front()}; // 1
    int back{a.back()};   // 3
    // 弹出
    a.pop();
    front = a.front();    // 2
    // 其它操作
    a.empty(); // 检查队列是否为空
    a.size();  // 获取队列元素个数
}

优先队列（堆）

优先队列是一种抽象的数据结构。它同样存放一系列数据，但特点是总能把最大的元素放在首个位置上。当然这是有代价的，每次向其中插入元素，都需要进行一番调整才能做到。而且它颇像关联容器：不能自己控制元素的顺序，且不允许中途修改某个元素的值。

优先队列提供了两种操作：推入（Push）元素并进行调整，以及弹出（Pop）最大的元素。同样地，一般只允许读取优先队列的队首，也就是最大的元素的值。

由于优先队列往往是通过维护堆（Heap）的结构来实现的，所以有时直接称优先队列为堆。不论如何，std::priority_queue 类模板通过给 std::vector 换了一套接口实现了优先队列。

#include <queue> // 定义于此
int main() {
    std::priority_queue<int> a;
    // 推入
    a.push(2);
    a.push(3);
    a.push(1);
    // 读取队首并弹出
    int max{a.top()}; // 3
    a.pop();
    max = a.top();    // 2
    a.pop();
    max = a.top();    // 1
    // 其它操作
    a.empty(); // 检查队列是否为空
    a.size();  // 获取队列元素个数
}

容器适配器为了保证只能读取特定位置的元素，不提供迭代器接口。无法遍历容器适配器的元素。这或许是 C++ 封装特性的典型体现。

std::priority_queue 类模板一共有三个模板形参，第一个是元素类型，第二个是被包装的底层容器，第三个则是判断“最大值”的依据。由于 std::priority_queue 是非常早进入标准库的，所以它是通过一个重载了 operator() 的类 Comp 作为判断最大值的依据。如果容器中两个元素 a 和 b 满足 Comp()(a, b) 为 true 的话，就认为 a 比 b 要小。默认的参数是 std::less<T> 类，它会将 a < b 的结果作为其 operator() 的返回值。
我说这么多就是为了简单地阐述这样一个事实：如果需要让最小的元素跑到队首，那么需要这样声明优先队列：std::priority_queue<T, std::vector<T>, std::greater<T>>，把 std::greater<T> 作为第三模板实参。总之挺麻烦的。

在本文最后，我们回到第六章总结中提到的 std::string。std::string 也提供了 begin 和 end 成员函数，它们返回的是连续迭代器。这使得它看上去和 std::vector<char> 功能上是类似的；但作为字符串的实现，它更进一步提供了一些细致的字符串操作。并且为了和 C 风格字符串兼容，std::string 总是以空字符结束的。你当然可以把 std::string 视为一个精致的容器，但由于 STL 是一个历史性的术语，而 std::string 的诞生远早于其它 STL 容器，所以一般不认为 std::string 是 STL 的一部分。

# 容器适配器

# 栈

# 队列

# 优先队列（堆）

容器适配器

栈

队列

优先队列（堆）