一、栈（Stack）：后进先出（LIFO）的线性结构

1. 核心特性与应用场景

• 特性：仅允许在栈顶进行元素的插入（push）和删除（pop）操作，遵循 “后进先出” 原则。
• 典型应用：
  • 函数调用栈：记录函数调用顺序与局部变量状态。
  • 表达式求值：如逆波兰表达式（后缀表达式）计算。
  • 括号匹配：检测代码中括号是否成对出现。

2. C++ 标准库 stack 使用指南

2.1 头文件与命名空间

#include <stack>
using namespace std;//或者std::stack<int> st;

2.2 常用接口

接口	说明
stack<T>	构造空栈
push(x)	将元素 x 压入栈顶
pop()	弹出栈顶元素（不返回值）
top()	返回栈顶元素引用
empty()	检测栈是否为空（返回布尔值）
size()	返回栈中元素个数

二、队列（Queue）：先进先出（FIFO）的线性结构

1. 核心特性与应用场景

• 特性：元素从队尾入队（push），从队头出队（pop），遵循 “先进先出” 原则。
• 典型应用：
  • 任务调度：如打印机任务队列、操作系统进程调度。
  • 广度优先搜索（BFS）：用于遍历图或树结构。
  • 消息缓冲：网络请求、事件处理中的消息队列。

2. C++ 标准库 queue 使用指南

2.1 头文件与命名空间

#include <queue>
using namespace std;

2.2 常用接口

接口	说明
queue<T>	构造空队列
push(x)	将元素 x 入队（队尾）
pop()	弹出队头元素（不返回值）
front()	返回队头元素引用
back()	返回队尾元素引用
empty()	检测队列是否为空
size()	返回队列中元素个数

2.3 示例代码：用队列实现栈

class MyStack {
private:queue<int> q1, q2; // 使用两个队列模拟栈
public:void push(int x) {q1.push(x); // 新元素始终加入非空队列}int pop() {if (q1.empty()) swap(q1, q2); // 切换队列while (q1.size() > 1) {q2.push(q1.front()); // 转移元素，保留最后一个（栈顶）q1.pop();}int val = q1.front();q1.pop();return val;}int top() { return q1.empty() ? q2.back() : q1.back(); }
};

三、优先队列（Priority Queue）：基于堆的动态优先级结构

1. 核心特性与应用场景

• 特性：每个元素有优先级，每次取出优先级最高（或最低）的元素，底层基于堆实现。
• 典型应用：
  • 堆排序：利用优先队列实现高效排序。
  • 任务调度：操作系统中按优先级分配资源。
  • 图算法：Dijkstra 算法求最短路径、Prim 算法求最小生成树。

2. C++ 标准库 priority_queue 使用指南

2.1 头文件与命名空间

#include <queue>
using namespace std;

2.2 常用接口

接口	说明
priority_queue<T>	构造大顶堆（默认）
push(x)	插入元素 x 并调整堆结构
pop()	弹出堆顶元素（最大 / 最小值）
top()	返回堆顶元素引用
empty()	检测优先队列是否为空
size()	返回元素个数

四、容器适配器：stack 和 queue 的底层实现

1. 适配器模式简介

• 定义：将一个类的接口转换为另一种接口，使原本不兼容的类可以协同工作。
• STL 中的应用：stack 和 queue 本质是容器适配器，通过封装其他容器（如 deque、vector）的接口实现特定功能。

2. 为什么选择 deque 作为默认底层容器？

• deque 的优势：
  • 双端操作高效：头插 / 头删、尾插 / 尾删均为 O (1) 时间复杂度。
  • 内存利用率高：相比 list，连续存储（分段连续）减少指针开销。
  • 避免 vector 的缺陷：扩容时无需搬移大量元素，适合频繁插入 / 删除场景。
• 适配性：stack 仅需尾插 / 尾删，queue 需尾插 / 头删，deque 完美满足需求。

3. deque 的本质与逻辑结构

3.1 分段连续的存储空间

deque 是一种 双开口的 “连续” 空间数据结构，但实际并非物理连续，而是由 一段段连续的小空间（缓冲区）拼接而成，整体呈现 “逻辑连续” 的假象 。

• 每个缓冲区（buffer）通常是固定大小的数组（如 8 或 16 字节）。

• 缓冲区之间通过 中控器（map） 管理，中控器是一个指针数组，每个元素指向一个缓冲区的起始地址 。

• 逻辑示意图：

   
  • 中控器维护缓冲区的地址，形成 “动态二维数组” 结构。
  • 通过这种设计，deque 既具备类似 vector 的随机访问能力，又支持高效的双端操作。

3.2 迭代器的复杂性

deque 的迭代器需要维护 “逻辑连续” 的假象，因此设计复杂。每个迭代器包含以下信息 ：

• cur：当前指针，指向缓冲区中的具体元素。

• first：当前缓冲区的起始地址。

• last：当前缓冲区的结束地址（不包含）。

• node：指向中控器中当前缓冲区对应的指针（即 map 中的元素）。

• 迭代器移动逻辑：

  • 当 cur 指向当前缓冲区的末尾时，迭代器通过 node 切换到下一个缓冲区，并将 cur 指向新缓冲区的起始位置，反之亦然。
  • 这种机制使得 deque 的迭代器可以像 vector 一样进行 ++/-- 操作，但实际会涉及缓冲区的切换 。

4.deque 的核心特性

4.1 双端操作的高效性

• 头插 / 头删（O (1) 时间复杂度）：
  • 无需像 vector 一样搬移大量元素，只需在头部缓冲区添加 / 删除元素，或新建 / 销毁一个缓冲区（极端情况） 。
• 尾插 / 尾删（O(1) 时间复杂度）：
  • 与 vector 类似，直接操作尾部缓冲区，仅在缓冲区满时新建一个缓冲区 。

4.2 与vector、list 的对比

特性	deque	vector	list
内存结构	分段连续（逻辑连续）	物理连续	非连续（链表）
头插 / 头删效率	O (1)（无需搬移元素）	O (n)（需搬移全部元素）	O(1)
随机访问效率	O (1)（通过迭代器切换缓冲区）	O (1)（直接指针运算）	O (n)（需遍历链表）
空间利用率	高（缓冲区紧凑，无额外指针）	高（连续存储）	低（每个节点含前驱 / 后继指针）
典型场景	双端操作频繁（如 stack/queue 底层）	随机访问频繁（如数组下标操作）	任意位置插入 / 删除频繁

4.3 致命缺陷：遍历效率低

• deque 的迭代器在遍历时需要频繁检测是否到达缓冲区边界，导致效率低于 vector 的原生指针遍历。因此，deque 不适合高频遍历场景 。
• 高效场景：栈（push_back/pop_back）、队列（push_back/pop_front）。
• 低效场景：多次调用 begin() 到 end() 的遍历（如 for (auto it = d.begin(); it != d.end(); ++it)）。

5.deque 作为 stack/queue 底层容器的原因

5.1 适配性分析

• stack 需求：仅需 push_back/pop_back，deque 的尾操作与 vector 等价，但扩容时无需搬移元素（效率更高） 。
• queue 需求：需 push_back/pop_front，deque 的头删操作（pop_front）效率优于 vector（vector 头删需搬移所有元素），且空间利用率优于 list 。

5.2 deque 的设计完美契合 stack/queue 的接口需求

• 不需要遍历（无迭代器需求），避开遍历低效的缺陷。
• 双端操作高效，内存使用紧凑。
• STL 中 stack/queue 的默认底层容器为 deque，而非 vector 或 list 。

6.对比分析

知识点	知识点
deque 的逻辑结构	分段连续空间，通过中控器管理缓冲区，呈现 “逻辑连续” 假象
迭代器设计	头插 / 头删效率优于 vector，空间利用率优于 list
双端操作优势	迭代器需频繁检测缓冲区边界，遍历效率低，不适合高频遍历场景
遍历缺陷	迭代器需频繁检测缓冲区边界，遍历效率低，不适合高频遍历场景
作为 stack/queue 底层	双端操作高效 无需遍历，完美适配 stack/queue 的接口需求

总结：deque 的核心价值

deque 的设计是 双端操作高效性 与 空间利用率 的平衡：

• 优势场景：需要频繁双端操作（如栈、队列），但无需高频遍历的数据结构。
• 局限性：遍历效率低，因此 STL 中 algorithm 算法优先推荐使用 vector 或 list。

六、优先队列中的仿函数（Functor）应用

1. 仿函数基础概念

• 定义：仿函数是一种可调用对象，本质是重载了 operator() 的类或结构体。
• 作用：在优先队列中，通过仿函数自定义元素的比较规则，实现大顶堆或小顶堆的灵活切换。

2. 仿函数在优先队列中的使用场景

优先队列默认使用 大顶堆（通过 < 运算符比较元素），若需创建 小顶堆，需显式指定仿函数 greater<T>。例如：

#include <queue>
#include <functional> // 包含 greater 仿函数void TestPriorityQueue() {vector<int> v = {3, 1, 4, 2};// 默认大顶堆（使用 less<int> 仿函数，可省略不写）priority_queue<int> max_heap;for (int x : v) max_heap.push(x); // 堆顶为 4// 显式使用 greater<int> 仿函数创建小顶堆priority_queue<int, vector<int>, greater<int>> min_heap(v.begin(), v.end());// 堆顶为 1（最小值）
}

3. 自定义仿函数：处理自定义类型

当优先队列存储自定义类型时，需通过仿函数或重载运算符定义比较规则。以下是通过独立仿函数实现相同功能的方式：

class Date {
public:int _year, _month, _day;Date(int y, int m, int d) : _year(y), _month(m), _day(d) {}
};// 自定义仿函数：大顶堆（按日期从大到小排序）
struct DateGreater {bool operator()(const Date& d1, const Date& d2) const {if (d1._year != d2._year) return d1._year > d2._year;if (d1._month != d2._month) return d1._month > d2._month;return d1._day > d2._day;}
};// 自定义仿函数：小顶堆（按日期从小到大排序）
struct DateLess {bool operator()(const Date& d1, const Date& d2) const {if (d1._year != d2._year) return d1._year < d2._year;if (d1._month != d2._month) return d1._month < d2._month;return d1._day < d2._day;}
};// 使用示例
void TestCustomFunctor() {vector<Date> dates = {Date(2023, 10, 5),Date(2023, 10, 3),Date(2023, 11, 1)};// 大顶堆：优先取出最新日期priority_queue<Date, vector<Date>, DateGreater> max_heap(dates.begin(), dates.end());cout << max_heap.top()._year << "-" << max_heap.top()._month << "-" << max_heap.top()._day << endl; // 输出：2023-11-1// 小顶堆：优先取出最旧日期priority_queue<Date, vector<Date>, DateLess> min_heap(dates.begin(), dates.end());cout << min_heap.top()._year << "-" << min_heap.top()._month << "-" << min_heap.top()._day << endl; // 输出：2023-10-3
}

4. 仿函数与运算符重载的选择

• 场景一：若自定义类型可自然排序（如 Date 类的日期顺序），建议重载 operator<（对应大顶堆）或 operator>（对应小顶堆），保持代码简洁。
• 场景二：若需灵活切换多种排序规则（如有时按年份、有时按月日排序），使用独立仿函数更灵活，避免污染类的运算符定义。

5. 关键细节

• 默认情况下，priority_queue 是大堆，底层通过 less<T> 仿函数实现。
• 若需小堆，需显式指定第三个模板参数为 greater<T> 或自定义仿函数，如：

  priority_queue<int, vector<int>, greater<int>> min_heap; // 小顶堆
  

• 自定义仿函数的返回值必须为 bool，且遵循 严格弱序关系（strict weak ordering），确保堆结构正确维护。

总结：仿函数的核心作用

灵活控制排序规则：通过仿函数，优先队列可轻松切换大顶堆 / 小顶堆，或为自定义类型定制比较逻辑。

七、栈和队列的模拟实现

1. 栈的模拟实现（基于 deque）

1.1 类模板定义与模板参数

namespace My_stack {template<class T, class Con = std::deque<T>>class stack { /* ... */ };
}

• 模板参数：
  • T：栈中存储元素的类型（必填）。
  • Con：底层容器类型（可选，默认 std::deque<T>），文档中提到 stack 本质是容器适配器，可封装任意支持 push_back/pop_back/back 接口的容器（如 vector、list） 。
• 命名空间：
  My_stack 避免与标准库 std::stack 命名冲突，符合自定义组件的封装规范。

1.2 构造函数

stack() {}

• 功能：默认构造空栈，底层容器 _c 调用 Con 的默认构造函数（如 deque 的空构造）。
• 复杂度：O (1)，仅初始化底层容器。

1.3 核心接口实现

1.3.1 压栈操作：push(const T& x)

void push(const T& x) { _c.push_back(x); }

• 原理：调用底层容器的 push_back 接口，在容器尾部添加元素，符合栈的 “后进先出” 特性 。
• 示例：若 Con 为 deque，元素被添加到双端队列的尾部，时间复杂度 O (1)（均摊）。

1.3.2 弹栈操作：pop()

void pop() { _c.pop_back(); }

• 原理：调用底层容器的 pop_back 接口，移除尾部元素（即栈顶元素），不返回值 。
• 注意：若栈为空时调用 pop()，会导致未定义行为（需提前通过 empty() 检测）。

1.3.3 获取栈顶元素：top()

T& top() { return _c.back(); }
const T& top()const { return _c.back(); }

• 重载版本：
  • 非 const 版本：返回栈顶元素的可修改引用。
  • const 版本：返回栈顶元素的常量引用，用于 const stack 对象。
• 底层调用：通过容器的 back() 接口获取尾部元素，时间复杂度 O (1) 。

1.3.4 辅助接口：size() 和 empty()

size_t size()const { return _c.size(); }
bool empty()const { return _c.empty(); }

功能：

• size()：返回栈中元素个数，调用容器的 size() 接口。
• empty()：检测栈是否为空，调用容器的 empty() 接口，等价于 size() == 0 。
• 复杂度：均为 O (1)，直接转发底层容器的实现。

1.4 底层容器选择：默认使用 deque 的原因

class stack { template<class T, class Con = std::deque<T>> /* ... */ }

• 文档依据：
  STL 中 stack 的默认底层容器为 deque，因其双端操作高效且内存利用率高。
  • deque 的 push_back/pop_back 均为 O (1) 操作，且扩容时无需像 vector 一样搬移大量元素 。
  • 对于栈而言，无需遍历功能，完美避开 deque 遍历效率低的缺陷 。
• 可替代性：
  若显式指定 Con 为 vector 或 list，需确保容器支持以下接口：

  push_back(const T&)  // 压栈
  pop_back()           // 弹栈
  back() const&        // 获取栈顶
  size() const         // 元素个数
  empty() const        // 判空
  

1.5.示例用法

#include<iostream>
using namespace std;int main() {My_stack::stack<int> s; // 使用默认 deque 作为底层容器s.push(10);s.push(20);cout << "栈顶元素：" << s.top() << endl; // 输出 20s.pop();cout << "栈大小：" << s.size() << endl; // 输出 1cout << "是否为空：" << boolalpha << s.empty() << endl; // 输出 falsereturn 0;
}

 2. 队列的模拟实现（基于 deque）

namespace My_Queue
{template<class T, class Con = std::deque<T>>class queue{public:queue(){ }void push(const T& x){_c.push_back(x);}void pop(){_c.pop_front();}T& back(){return _c.back();}const T& back()const{return _c.back();}T& front(){return _c.front();}const T& front()const{return _c.front();}size_t size()const{return _c.size();}bool empty()const{return _c.empty();}private:Con _c;};
};

3. 优先队列的模拟实现（基于 vector 和堆算法）

3.1 类模板定义与模板参数

template<class T, class container=std::vector<T>, class compare=less<T>>
class priority_queue { /* ... */ };

• 模板参数：
  • T：优先队列中存储元素的类型（必填）。
  • container：底层容器类型（可选，默认 std::vector<T>），需支持随机访问（如 vector、deque），文档提到优先队列底层容器需满足 push_back/pop_back/front 等接口 。
  • compare：比较仿函数（可选，默认 less<T>），用于定义元素优先级。less<T> 表示大顶堆（默认），greater<T> 表示小顶堆 。
• 设计意图：通过模板参数实现容器和比较规则的灵活配置，符合文档中 “优先队列是容器适配器” 的定位 。

3.2 核心接口实现

3.2.1 构造函数：priority_queue()

priority_queue() { }

• 功能：默认构造空优先队列，底层容器 _con 调用 container 的默认构造函数（如 vector 的空构造）。
• 复杂度：O (1)，仅初始化底层容器。

3.3.2 插入元素：push(const T& val)

void push(const T& val) {_con.push_back(val); // 尾部添加元素Adjustup(_con.size()-1); // 向上调整堆，维持堆性质
}

• 核心逻辑：
  1. 新元素添加到容器尾部（对应堆的最后一个位置）。
  2. 调用 Adjustup 从下往上调整堆，确保父节点优先级高于子节点（大顶堆场景）。
• Adjustup 算法：
  • 比较当前节点（child）与父节点（parent），若父节点优先级低于子节点（com(_con[parent], _con[child]) 为真），则交换两者位置，直至堆性质满足 。
  • 时间复杂度：O (log n)，其中 n 为堆中元素个数。

void Adjustup(size_t child)
{compare com;size_t parent = (child - 1) / 2;        while (child > 0){if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}

3.3.3 删除堆顶元素：pop()

void pop() {swap(_con[0], _con[size() - 1]); // 交换堆顶与最后一个元素_con.pop_back(); // 删除最后一个元素（原堆顶）Adjustdown(0); // 向下调整堆，维持堆性质
}

• 核心逻辑：
  1. 将堆顶元素（最大 / 最小值）与堆尾元素交换，使堆顶元素位于容器尾部。
  2. 删除尾部元素（即原堆顶），此时堆顶为新元素，可能破坏堆性质。
  3. 调用 Adjustdown 从上往下调整堆，重新确定新堆顶的位置。
• Adjustdown 算法：
  • 比较当前节点（parent）与左右子节点（child），选择优先级最高的子节点交换位置，直至堆性质满足 。
  • 时间复杂度：O(log n)。

void Adjustdown(size_t parent)
{compare com;size_t child = 2 * parent + 1;size_t size = size();while (child < size){if (child + 1 < size && com(_con[child]  ,_con[child + 1])){child++;}if (com(_con[parent] , _con[child])){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

3.3.4 获取堆顶元素：top()

const T& top() { return _con[0]; }

• 功能：返回堆顶元素的常量引用（大顶堆为最大值，小顶堆为最小值）。
• 前提条件：队列非空，否则访问 _con[0] 会导致未定义行为（需提前通过 empty() 检测）。
• 底层实现：直接返回容器首元素，时间复杂度 O (1)，符合文档中 “优先队列只能检索堆顶元素” 的特性 。

3.3.5 辅助接口：size() 和 empty()

size_t size() { return _con.size(); }
bool empty() { return _con.empty(); }

• 功能：
  • size()：返回队列中元素个数，调用容器的 size() 接口。
  • empty()：检测队列是否为空，等价于 size() == 0。
• 复杂度：均为 O (1)，直接转发底层容器的实现。

4.底层容器与比较仿函数

4.1 底层容器 container

• 默认选择 vector 的原因：
  • vector 支持随机访问（通过下标 []），满足堆算法（Adjustup/Adjustdown）的索引需求。
  • push_back/pop_back 操作高效，且扩容时通过复制实现，保证数据连续性 。
• 可替代性：
  若指定为 deque，需确保其支持随机访问（deque 符合要求），但实际优先队列更常用 vector 作为底层容器（文档默认场景） 。

4.2 比较仿函数 compare

• 默认 less<T>（大顶堆）：

  compare com; // 实例化仿函数
  if (com(_con[parent], _con[child])) { // 若 parent < child（大顶堆逻辑）swap(_con[child], _con[parent]); // 父节点与子节点交换，使父节点更大
  }
  

• 切换为小顶堆（greater<T>）：
  只需将模板参数 compare 改为 greater<T>，此时 com(a, b) 判断 a > b 是否成立，调整堆时确保父节点更小。
• 自定义仿函数：
  参考文档中 Date 类的比较逻辑，可自定义仿函数实现特定优先级规则，如：

  struct MyCompare {bool operator()(const int& a, const int& b) {return a % 10 < b % 10; // 按个位数大小排序}
  };
  priority_queue<int, vector<int>, MyCompare> pq; // 使用自定义比较规则
  

5.示例用法（大顶堆）

#include<iostream>
using namespace std;int main() {priority_queue<int> pq; // 默认大顶堆，底层 vector，比较仿函数 less<int>pq.push(30);pq.push(10);pq.push(20);cout << "堆顶元素（最大值）：" << pq.top() << endl; // 输出 30pq.pop();cout << "新堆顶元素：" << pq.top() << endl; // 输出 20return 0;
}

八、经典算法题实战

 1. 最小栈

class MinStack {
private:stack<int> data;       // 存储所有元素stack<int> min_data;   // 存储最小值
public:void push(int x) {data.push(x);if (min_data.empty() || x <= min_data.top()) {min_data.push(x);}}void pop() {if (data.top() == min_data.top()) {min_data.pop();}data.pop();}int top() { return data.top(); }int getMin() { return min_data.top(); }
};

2. 栈的压入、弹出序列

题目：给定入栈序列 pushV 和出栈序列 popV，判断 popV 是否为 pushV 的有效弹出序列。
思路：用栈模拟入栈和出栈过程，逐个匹配出栈元素。
代码：

bool IsPopOrder(vector<int> pushV, vector<int> popV) {if (pushV.size() != popV.size()) return false;stack<int> s;int i = 0; // 入栈指针for (int num : popV) {// 栈顶元素不等于当前出栈元素时，继续入栈while (s.empty() || s.top() != num) {if (i >= pushV.size()) return false; // 无元素可入栈s.push(pushV[i++]);}s.pop(); // 匹配成功，弹出栈顶}return true;
}

3. 逆波兰表达式求值

题目：根据逆波兰表达式（后缀表达式）计算结果，运算符包括 +、-、*、/。
思路：用栈存储操作数，遇到运算符时弹出栈顶两个元素计算结果并压栈。
代码：

int evalRPN(vector<string>& tokens) {stack<int> sv;for(const auto& e:tokens){if(e=="+"||e=="-"||e=="*"||e=="/"){int a=sv.top();sv.pop();int b=sv.top();sv.pop();switch(e[0]){case '/':sv.push(b/a);break;case '*':sv.push(a*b);break;case '-':sv.push(b-a);break;case '+':sv.push(a+b);break;}}else{sv.push(stoi(e));}}return sv.top();
}

六、总结与拓展建议

1. 核心对比

数据结构	访问规则	底层容器（STL 默认）	典型场景
stack	后进先出（LIFO）	deque	函数调用、表达式求值
queue	先进先出（FIFO）	deque	BFS、任务队列
priority_queue	优先级优先	vector（堆结构）	堆排序、最短路径算法

2. 拓展学习建议

• 底层原理：深入理解 deque 的分段连续存储结构与迭代器设计。
• 算法应用：练习用栈实现回溯算法（如括号生成），用队列实现层序遍历。
• 自定义类型：在 priority_queue 中使用自定义类时，需重载比较运算符（< 或 >）。

通过本文的理论解析与实战代码，相信你已掌握 C++ 中栈与队列的核心概念与应用。在实际开发中，根据场景选择合适的数据结构，能显著提升代码效率与可读性。

附录

模拟实现

//stack.h
#include<iostream>
#include<deque>namespace My_stack
{template<class T, class Con = std::deque<T>>class stack{public:stack(){}void push(const T& x){_c.push_back(x);}void pop(){_c.pop_back();}T& top(){return _c.back();}const T& top()const{return _c.back();}size_t size()const{return _c.size();}bool empty()const{return _c.empty();}private:Con _c;};
};

//queue.h
namespace My_Queue
{template<class T, class Con = std::deque<T>>class queue{public:queue(){ }void push(const T& x){_c.push_back(x);}void pop(){_c.pop_front();}T& back(){return _c.back();}const T& back()const{return _c.back();}T& front(){return _c.front();}const T& front()const{return _c.front();}size_t size()const{return _c.size();}bool empty()const{return _c.empty();}private:Con _c;};template<class T>class less{public:bool operator()(const T& a, const T& b){return a < b;}};template<class T>class greater{public:bool operator()(const T& a, const T& b){return a > b;}};template<class T,class container=std::vector<T>,class compare=less<T>>class priority_queue{public:priority_queue(){ }void push(const T& val){_con.push_back(val);Adjustup(_con.size()-1);}void pop(){swap(_con[0], _con[size() - 1]);_con.push_back();Adjustdown(0);}const T& top(){return _con[0];}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:void Adjustup(size_t child){compare com;size_t parent = (child - 1) / 2;while (child > 0){if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void Adjustdown(size_t parent){compare com;size_t child = 2 * parent + 1;size_t size = size();while (child < size){if (child + 1 < size && com(_con[child]  ,_con[child + 1])){child++;}if (com(_con[parent] , _con[child])){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}private:container _con;};
};