前言
stringvectorlist这种线性结构是最基础的存储结构，C++（STL）container很好的帮助我们数据存储的问题。
容器适配器
介绍
- 容器适配器是C++标准模板库（
STL）中的一种设计模式，它允许将一个容器的接口转换为另一个接口，从而提供不同的操作和行为。 - 容器适配器通常用于封装现有容器，以实现特定的数据结构特性，如栈（后进先出）、队列（先进先出）和优先队列（根据优先级排序）。
应用
-
栈（stack）：栈是一种后进先出的数据结构，其操作包括入栈（push）、出栈（pop）、查看栈顶元素（top）等。栈适配器可以基于多种底层容器实现，如
vector、deque或list. -
队列（queue）：队列是一种先进先出的数据结构，其操作包括入队（push）、出队（pop）、查看队首元素（front）和查看队尾元素（back）。队列适配器同样可以基于
deque或list实现，以适应不同的性能需求. -
优先队列（priority_queue）：优先队列是一种特殊的队列，它根据元素的优先级进行排序。其底层容器通常是
vector或deque，并通过堆算法维护元素的优先级顺序。优先队列适配器提供了插入和删除具有最高优先级元素的操作.
双重结束队列（双端队列（deque））
特点
- 双端操作效率：支持在两端进行快速的插入和删除操作。
- 随机访问：可以通过索引直接访问容器中的元素。
- 无需预先分配固定大小：与
vector不同，deque不需要在创建时指定大小，它可以根据需要动态增长。 - 内存分配策略：
deque不需要像vector那样一次性分配大量内存，而是分散在内存中，这有助于减少内存碎片。
存储结构
双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问的假象，落 在了deque的迭代器身上，因此deque的迭代器设计就比较复杂，如下图所示：
List 、vector deque对比
| 对比维度 | Vector | Deque | List |
|---|---|---|---|
| 内存连续性 | 是 | 否 | 否 |
| 随机访问性能 | O(1) | O(1) 但可能不如Vector | O(n) |
| 插入/删除性能 | 非末尾O(n) | 两端O(1), 中间O(n) | 两端及中间O(1) |
| 内存重用效率 | 扩容时需移动元素 | 两端添加删除不需移动 | 不适用 |
| 内存分配模式 | 动态数组，连续内存 | 分段连续内存 | 非连续内存 |
| 迭代器失效 | 可能 | 不会 | 不会 |
| 支持的操作 | [] 访问、.at() 等 | [] 访问、.at() 等 | [] 访问、.at() 等 |
| 内存管理开销 | 高（扩容时） | 中等（两端操作） | 低 |
| 适用场景 | 需要快速随机访问且元素数量稳定 | 需要两端快速插入删除，随机访问需求适中 | 频繁插入删除，不关心随机访问 |
栈（stack）
栈的介绍
| 函数说明 | 接口说明 |
|---|---|
| stack() | 构造空的栈 |
| empty() | 检测stack是否为空 |
| size() | 返回stack中元素的个数 |
| top() | 返回栈顶元素的引用 |
| push() | 将元素val压入stack中 |
| pop() | 将stack中尾部的元素弹出 |
栈的模拟实现
利用容器适配器的设计原理，很容易实现栈
- 将栈放
mystack的命名空间，以防止和库中冲突 - 类模板设计
container可以给缺省参数，默认deque(容器适配器) - 在里面利用
deque的接口实现
namespace mystack
{
template<class T, class Container = std::deque<T>>
class stack
{
public:
void push_back(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_back();
}
size_t size()
{
return _con.size();
}
T& top()
{
return _con.back();
}
bool empty()
{
return _con.empty();
}
private:
Container _con;
};
}
队列
队列介绍
| 函数声明 | 接口说明 |
|---|---|
| queue() | 构造空的队列 |
| empty() | 检测队列是否为空，是返回true，否则返回false |
| size() | 返回队列中有效元素的个数 |
| front() | 返回队头元素的引用 |
| back() | 返回队尾元素的引用 |
| push() | 在队尾将元素val入队列 |
| pop() | 将队头元素出队列 |
队列模拟实现
- 将栈放
myqueue的命名空间，以防止和库中冲突 - 类模板设计
container可以给缺省参数，默认deque(容器适配器) - 在里面利用
deque的接口实现
namespace myqueue
{
template<class T, class Container = std::deque<T >>
class queue
{
public:
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con
