C++容器适配器深度解析：stack/queue/priority_queue的设计哲学

watergraphically

851人浏览 · 2025-10-19 15:01:24

watergraphically · 2025-10-19 15:01:24 发布

1. stack

栈是一种容器适配器，专门设计用于后进先环境，在这种环境中，元素只从容器的一端插入和提取。栈是作为容器适配器实现的，这些适配器是使用特定容器类的封装对象作为其底层容器的类，提供一组特定的成员函数来访问其元素。

stack 与我们之前所学的容器有很明显的区别，从模板的声明可以看出。如 vector 容器的模板声明：template < class T, class Alloc = allocator<T> > class vector；stack 的模板声明为：template <class T, class Container = deque<T> > class stack 。vector 的第二个模板参数是 class Alloc = allocator<T> ，是内存池；stack 是 class Container = deque<T>，是容器。

stack 支持的函数接口：

stack() —— 构造空的栈

empty() —— 检测 stack 是否为空

size() —— 返回 stack 中元素的个数

top() —— 返回栈顶元素的引用

push() —— 将元素 val 压入 stack 中

pop() —— 将 stack 中尾部的元素弹出

需要注意的是 stack 容器不支持 begin 和 end 函数，也就不支持迭代器/范围for，并且栈也不支持下标随机访问，应该怎么遍历 stack 中的数据呢？如下所示：

// 栈不为空，就一直取栈顶元素
while (!st.empty())
{
	// 取栈顶元素
	cout << st.top() << " ";
	// 出栈顶元素
	st.pop();
}

模拟实现 stack

栈是一个特殊的 vector ，我们可以使用 vector 来实现 stack 。

template<class T>
class stack
{
public:
	//入栈 --- push 函数
	void push(const T& val)
	{
		// 尾插
		_v.push_back(val);
	}

	// 出栈 --- pop 函数
	void pop()
	{
		// 尾删
		_v.pop_back();
	}

	// 取栈顶数据 --- top 函数
	T& top()
	{
		// 取 vector 中最后一个元素
		return  _v.back();
	}

	// 获取栈中有效数据个数 --- size 函数
	size_t size() const
	{
		return _v.size();
	}

	// 判断栈是否为空 --- empty 函数
	bool empty() const
	{
		return _v.empty();
	}

private:
	vector<T> _v;
};

2. queue

queue 的模板声明与 stack 类似，queue 的模板声明为：template <class T, class Container = deque<T> > class queue。

队列也是一种容器适配器。专门用于在先进先出的上下文中操作，其中元素从容器的一端插入，从另一端取出。队列作为容器适配器实现，即使用特定容器类封装的对象作为其底层容器的类，并提供一组特定的成员函数来访问其元素。

queue 支持的函数接口：

queue() —— 构造空的队列

empty() —— 检测队列是否为空，是返回true，否则返回false

size() —— 返回队列中有效元素的个数

front() —— 返回队头元素的引用

back() —— 返回队尾元素的引用

push() —— 入队列

pop() —— 出队列

需要注意的是 queue 容器不支持 begin 和 end 函数，也就不支持迭代器/范围for，并且 queue 也不支持下标访问，应该怎么遍历 queue 中的数据呢？如下所示：

// 队列不为空，就一直取队头元素
while (!q.empty())
{
	// 取队头元素
	cout << q.front() << " ";
	// 出队头元素
	q.pop();
}

模拟实现 queue

由于 queue 的接口中存在头删和尾插，因此使用 vector 来封装效率太低，可以借助 list 来实现 queue 。

template<class T>
class queue
{
public:
	// 构造函数 --- queue
	queue()
	{}

	// 检测队列是否为空 --- empty 函数
	bool empty() const
	{
		return _lt.empty();
	}

	// 获取队列中有效元素个数 --- size 函数
	size_t size() const
	{
		return _lt.size();
	}

	// 返回队头元素的引用 --- front 函数
	T& front()
	{
		return _lt.front();
	}

	// 返回队尾元素的引用 -- back 函数
	T& back()
	{
		return _lt.back();
	}

	// 入队列(队尾) --- push 函数
	void push(const T& val)
	{
		_lt.push_back(val);
	}

	// 出队列(队头) --- pop 函数
	void pop()
	{
		_lt.pop_front();
	}

private:
	list<T> _lt;
};

3. 容器适配器

容器适配器不是独立的容器，而是在现有容器之上包装一层，提供不同的接口和行为的类。适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类的接口转换成用户希望的另外一个接口。

尽管 stack 和 queue 中可以存放元素，但在 STL 中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为stack和队列只是对其他容器的接口进行了包装，STL 中 stack 和 queue 默认使用 deque 。

将 stack 实现成容器适配器

// 容器适配器
template<class T, class Container = deque<T>>
class stack
{
public:
	// 入栈 -- push 函数
	void push(const T& val)
	{
		_cont.push_back(val);
	}

	// 出栈 --- pop 函数
	void pop()
	{
		_cont.pop_back();
	}

	// 取栈顶数据 --- top 函数
	T& top()
	{
		// 所有的线性容器都实现了front/back接口
		_cont.back();
	}

	// 获取栈中有效数据个数 --- size 函数
	size_t size()
	{
		_cont.size();
	}

	// 判断栈是否为空
	bool empty()
	{
		_cont.empty();
	}

private:
	Container _cont;
};

将 queue 实现成容器适配器

// 容器适配器
template<class T, class Container = deque<T>>
class queue
{
public:
	// 构造函数 --- queue
	queue() {}

	// 检测队列是否为空 --- empty函数
	bool empty()
	{
		return _cont.empty();
	}

	// 获取队列中有效元素个数 --- size 函数
	size_t size()
	{
		return _cont.size();
	}

	// 返回队头元素的引用 --- front 函数
	T& front()
	{
		return _cont.front();
	}
	 
	// 返回队尾元素的引用 --- back 函数
	T& back()
	{
		return _cont.back();
	}

	// 入队列(队尾) --- push 函数
	void push(const T& val)
	{
		_cont.push_back(val);
	}

	// 出队列(队头) --- pop 函数
	void pop()
	{
		_cont.pop_front();
	}

private:
	Container _cont;
};

queue 的默认容器不能是 vector ，因为 vector 容器不支持 pop_front 函数。

4. deque

stack 和 queue 的默认容器都是 deque ，deque 是什么？

deque是双端队列，是一种双开口的"连续"空间的数据结构。双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与 vector 比较，头插效率高，不需要挪动元素；与 list 比较，空间利用率比较高。可以将 deque 理解为vector 和 list 的结合体。

从 deque 的优点来看，似乎 deque 在 vector 和 list 之上？如果真是这样，为什么平常很少使用deque，而是vector 和 list? deque 确实在某些方面比 vector 和 list ，但是终究比不上。至于为什么，请看下文。

vector 和 list 的优缺点：

vector：

• 底层结构是动态数组，是一段连续的内存区间

• 内存是连续的

• 支持随机访问，访问速度快，时间复杂度为O(1)

• 在尾部插入或删除，速度快，在头部/中间插入或删除，速度慢

• 空间开销小

• 具有缓存友好性，cpu 高速缓存命中率高

• 迭代器类型为随机迭代器

• 插入/删除可能导致迭代器失效

list：

• 底层结构是双向链表，分散的结点通过指针连接

• 内存是非连续的

• 不支持随机访问，访问速度慢，时间复杂度为O(N)

• 在已知操作位置时，执行插入和删除操作速度快，时间复杂度为O(1)

• 空间开销小

• 数据分散，cpu 缓存命中率低，还可能存在缓存污染

• 迭代器类型为双向迭代器

• 插入不会使迭代器失效，删除只会使指向被删除元素的迭代器失效

既然各有优缺点，实际使用中应该如何选择？

使用 vector：

需要频繁的随机访问元素。

主要是在容器的尾部进行插入和删除操作（如：栈）。

关心存储效率和访问速度，vector的缓存友好性通常能带来压倒性的性能优势。

元素数量相对稳定，或者也可以在开始时预留足够的空间（reserve()）。

使用 list：

需要在容器的任意位置进行频繁的插入和删除（并且已经有了指向该位置的迭代器）

关心插入/删除操作后迭代器、指针和引用的稳定性

不需要进行随机访问

容器的大小变化非常剧烈，无法承受 vector 重新分配的开销

建议：

首选 vector：在大多数情况下，vector 应该是默认选择。它连续的存储结构带来的缓存友好性，使得它在遍历、随机访问等操作上的性能优势，通常远超过在中间插入/删除的劣势。

慎用 list：只有在有非常明确的、需要在序列中间进行大量且频繁的插入删除操作，并且对迭代器稳定性有严格要求时，才考虑使用 list。

既然 vector 和 list 各有优缺点，可不可以新创一个容器，集 vector 和 list 的优点与一身呢？deque 因此诞生。

deque 是由一段段连续的小空间拼接而成的，并不是真正连续的空间，实际上 deque 类似于一个动态的二维数组。其底层结构如下图所示：

创建一个个的小数组，名为 buff ，buff 数组满了之后，再开一个数组。这一个个数组是不连续的，我们可以创建一个数组，名为中控数组，用于存储这一个个数组的指针。中控数组满了之后也需要扩容，但是拷贝代价小。

双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问的假象，这一重任落在了 deque 的迭代器身上，因此deque的迭代器设计得就比较复杂。

deque 的迭代器封装了 4 个指针：cur，first，last，node。库中双端队列的迭代器的底层结构为：

typedef T** map_pointer;

T* cur;
T* first;
T* last;
map_pointer node;

map_pointer 是 T** typedef 而来，所以 node 是二级指针，因为它存储中控数组（中控数组中的数据是指针）的某位置的地址。

4 个指针的指向如下图所示：

start 是 begin 返回的迭代器，finish 是 end 返回的迭代器。源码中的实现：

iterator begin() { return start; }
iterator end() { return finish; }

下面来了解源码中 deque 的迭代器是如何实现的。代码如下所示：

template <class T, class Ref, class Ptr, size_t BufSiz>
struct __deque_iterator {
	typedef random_access_iterator_tag iterator_category;
	typedef T value_type;  // 模板参数
	typedef Ptr pointer;   // 指针
	typedef Ref reference; // 引用
	typedef size_t size_type;
	typedef ptrdiff_t difference_type;
	typedef T** map_pointer;

	typedef __deque_iterator self;
	__deque_iterator(T* x, map_pointer y)
		: cur(x), first(*y), last(*y + buffer_size()), node(y) {
	}

	reference operator*() const { return *cur; }

	difference_type operator-(const self& x) const {
		return difference_type(buffer_size()) * (node - x.node - 1) +
			(cur - first) + (x.last - x.cur);
	}

	self& operator++() {
		++cur;
		if (cur == last)  
		{
			set_node(node + 1);
			cur = first;
		}
		return *this;
	}
	self operator++(int) {
		self tmp = *this;
		++*this;
		return tmp;
	}

	self& operator--() {
		if (cur == first) {
			set_node(node - 1);
			cur = last;
		}
		--cur;
		return *this;
	}
	self operator--(int) {
		self tmp = *this;
		--*this;
		return tmp;
	}

	self& operator+=(difference_type n) {
		difference_type offset = n + (cur - first);
		if (offset >= 0 && offset < difference_type(buffer_size()))
			cur += n;
		else {
			difference_type node_offset =
				offset > 0 ? offset / difference_type(buffer_size())
				: -difference_type((-offset - 1) / buffer_size()) - 1;
			set_node(node + node_offset);
			cur = first + (offset - node_offset * difference_type(buffer_size()));
		}
		return *this;
	}

	self operator+(difference_type n) const {
		self tmp = *this;
		return tmp += n;
	}

	self& operator-=(difference_type n) { return *this += -n; }

	self operator-(difference_type n) const {
		self tmp = *this;
		return tmp -= n;
	}

	reference operator[](difference_type n) const { return *(*this + n); }

	void set_node(map_pointer new_node) {
		// 更新迭代器的指向
		node = new_node;   // node 指向下一个 node 
		first = *new_node; // first 指针指向下一个buff的开始
		// last 指针指向下一个buff的末尾
		last = first + difference_type(buffer_size()); 
	}
};

其中尤其需要注意的就是 * 运算符重载函数和前置 ++ 运算符重载函数，重载实现了这两个运算符就可以使用迭代器遍历容器了。

operator* 就是 cur 的解引用；前置++，只需要动 cur 即可，若 cur 等于 last 了，说明当前的 buff 走到头了，若再 ++ ，就指向下一个 buff 了，怎么找到下一个 buff ？通过 node 指针，node + 1就找到下一个 buff 了。

若要实现尾插操作，需要找到最后一个buff，可以通过 finish 迭代器找到，finish 迭代器就是指向中控数组中最后一个 buff 。找到之后，还需判断最后一个 buff 数组中的数据满了没，如何判断？若 cur == last，则说明 buff 中没有空间了，需要新开一个 buff ，然后插入到新开 buff 的首位置。由分析可知尾插的效率比 vector 和 list 的都要高。

若要实现头插操作，应该怎么实现？我们仔细看中控数组的结构，它与我们之前常见的数组有些区别，常见的数组存储数据都是从数组的首位置开始，而它存储数据是从中间开始存的，中控数组这样设置是有什么深意吗？现在分析如何实现头插，先找到迭代器的起始位置，也就是 start 指向的位置，将待插入的数据插入 buff 的首位置。若 buff 满了，需要新开 buff ，start 需要更新指向新开的 buff ，而中控数组从中间开始存储数据，就是为了应对这种情况。完毕后，将数据插入到新开buff 的末尾，为了保持逻辑上的连续性。如下图所示：

若是中间插入/删除操作，就需要移动数据，所有的 buff 都需要移动，效率与 vector 差不多。

对于 operator[ ] 函数，若想要访问第 pos 位置的数据，过程是怎样的？

需要判断 pos 的精确位置，也就是第几个 buff ，buff 中的哪个位置。如何知道 pos 的确切位置，使用除法和取模运算符，pos 是第 pos/buffsize() 个 buff ，buff 的第 pos % buffsize() 的位置（使用这些公式的前提是每个buff数组的大小都是一样的）。对于下图：

如果访问的是第12个数据（从0开始），那么这个数据位于第 pos/buffsize()，即12/8 = 1，也就是第1个 buff ，buff 的第 pos%buffsize() ，即12%8 = 4，也就是 buff 的第 4 个数据，在上图所查找到的就是值为12 的元素。果真和我们所想象的那般简单吗？来看 deque 的源码是如何实现的：

reference operator[](size_type n) { return start[difference_type(n)]; }

// ……

reference operator[](difference_type n) const {
	return *(*this + n);
self operator+(difference_type n) const {
		self tmp = *this;
		return tmp += n;
}

// ……

self& operator+=(difference_type n) {
	difference_type offset = n + (cur - first);
	if (offset >= 0 && offset < difference_type(buffer_size()))
		cur += n;
	else {
		difference_type node_offset =
			offset > 0 ? offset / difference_type(buffer_size())
			: -difference_type((-offset - 1) / buffer_size()) - 1;
		set_node(node + node_offset);
		cur = first + (offset - node_offset * difference_type(buffer_size()));
	}
	return *this;
}

operator[ ] 的主要实现，依赖于 operator+= 的实现，最终需要看 += 是如何实现的。

为什么一开始要让 n + (cur - first) ?

对于下图，cur -first = 0.

但是对于下图所示的情况呢？

cur – first 不等于0，它之所以要 n + (cur – first) 就是考虑到了第一个 buff 不满的情况。如果不加cur-first，来计算第 12 个数据的确切位置，结果为位于第1个 buff 的第4个位置，值为 4，实际上是错误的，第12个数据的值为10；若加上 cur – first，也就是 6 ，那么计算第12个数据的确切位置，可以认为是计算第18个数据的确切位置，计算后的确切位置为第2个 buff 第2个位置，值为10。cur -first 计算的是位置的偏移量，考虑的是 start 迭代器指向的 buff 数组不满的情况。源码中还额外考虑了 offset 为负值的情况，因为 n 可能传的是负值。

由分析来看，deque 的下标访问的效率还行，与 list 和 vector 的访问效率相比较：list << deque < vector 。

deque 的总结：

Deque 适合头尾插入和删除数据，因此非常适合作为stack和queue的底层结构

下标随机访问的效率还行，但是涉及百万级以上的访问时，效率略低于vector

中间插入和删除数据时，需要挪动大量的数据

在需要线性结构时，大多数情况下优先考虑 vector 和 list

5. priority_queue

优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。由此可知，priority_queue 类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。

优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue 提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。

priority_queue 支持的函数接口：

• empty —— 检测容器是否为空

• size —— 返回容器中有效元素个数

• top —— 返回容器中第一个元素引用（堆顶）

• push —— 在容器尾部插入元素

• pop —— 删除容器尾部元素

需要注意的是 priority_queue 容器不支持 begin 和 end 函数，也就不支持迭代器/范围for，并且 priority_queue 也不支持下标访问，应该怎么遍历 priority_queue 中的数据呢？如下所示：

// 堆不为空，就一直出堆顶的元素
while (!pq.empty())
{
    // 取堆顶的元素
	cout << pq.top() << " ";
    // 删除堆顶的元素
	pq.pop();
}

使用 priority_queue 时，需要包含头文件 <queue> ，它的模板声明为：template <class T, class Container = vector<T>, class Compare = less<typename Container::value_type> > class priority_queue。其中 compare 称之为仿函数。

优先级队列默认使用 vector 作为其底层存储数据的容器，在 vector 上又使用了堆算法将 vector 中元素构造成堆的结构，因此 priority_queue 就是堆，所有需要用到堆的位置，都可以考虑使用 priority_queue。注意：默认情况下priority_queue是大堆，大的优先级高。如果想要小的优先级高，需要控制仿函数。在传第三个模板参数时，默认传的是 less，除此以外还有 greater。less 和greater 是库中写好的仿函数。

传小于 less 仿函数，大的优先级高，建大堆；传大于 greater 仿函数，小的优先级高，建小堆。

less 和 greater 都是类模板，模板声明分别为：template <class T> struct less 和 template <class T> struct greater。

对比仿函数为 less 和 greater 时的遍历结果：

// 仿函数使用 less
priority_queue<int> pqless;
pqless.push(4);
pqless.push(7);
pqless.push(3);
pqless.push(9);
pqless.push(5);

while (!pqless.empty())
{
	cout << pqless.top() << " ";
	pqless.pop();
}
cout << endl;

// 仿函数使用 greater
priority_queue<int, vector<int>, greater<int>> pqgreater;
pqgreater.push(4);
pqgreater.push(7);
pqgreater.push(3);
pqgreater.push(9);
pqgreater.push(5);

while (!pqgreater.empty())
{
	cout << pqgreater.top() << " ";
	pqgreater.pop();
}
cout << endl;

运行结果：

接下来看算法库中的 sort 函数，模板声明为：template <class RandomAccessIterator, class Compare> void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp)。priority_queue 的模板声明为：template <class T, class Container = vector<T>, class Compare = less<typename Container::value_type> > class priority_queue。仔细对比priority_queue和sort的原型：sort 是 Compare comp ，priority_queue 是 class Compare，它们两者之间的存在区别。sort 的是函数模板参数，需要传对象，priority_queue是类模板参数，需要传类型。

仿函数是用来替代函数指针的，函数指针适用于函数中，但是不适用于类模板中，类模板需要传类型，而仿函数就适用于模板。仿函数是一个类，类中重载了() 操作符。仿函数也被称之为函数对象，因为仿函数对象能像函数般被使用。如下所示：

template<class T>
class Less
{
public:
	bool operator()(const T& x, const T& y)
	{
		return x < y;
	}
};

int main()
{    
    Less<int> lessfunc;
	cout << lessfunc(1, 2) << endl;
    
    return 0;
}

将仿函数运用到排序中

// 仿函数
template<class T>
class Less
{
public:
	bool operator()(const T& x, const T& y)
	{
		return x < y;
	}
};

template<class T>
class Greater
{
public:
	bool operator()(const T& x, const T& y)
	{
		return x > y;
	}
};

int main()
{
    int arr[] = { 8, 4, 9, 3, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    sort(arr, arr + n, Less<int>());
    for (int i = 0; i < n; i++)
    {
    	cout << arr[i] << " ";
    }
    cout << endl;
    sort(arr, arr + n, Greater<int>());
    for (int i = 0; i < n; i++)
    {
	    cout << arr[i] << " ";
    }
    
    retrun 0;
}

运行结果：

模拟实现 priority_queue

优先队列的底层就是堆，在数据结构堆中已经详细的演示向上调整建堆和向下调整建堆算法，以及其时间复杂度，这里就不过多赘述，直接给出代码：

// 仿函数 —— less
template<class T>
class Less
{
public:
	bool operator()(const T& x, const T& y)
	{
		return x < y;
	}
};

// 仿函数 —— greater
template<class T>
class Greater
{
public:
	bool operator()(const T& x, const T& y)
	{
		return x > y;
	}
};

namespace AY
{
	// 优先级队列是一个容器适配器
	// priority_queue的底层是堆
	// 堆的底层是数组，使用vector作为优先队列的底层数据结构
	// 大堆 --- Less  小堆 --- Greater
	template<class T, class Container = std::vector<T>, class Compare = Less<T>>
	class priority_queue
	{
		// 默认是大堆

        // 向上和向下调整建堆算法只有 priority_queue 中使用
        // 因此可以定义为 private
	private:
		// 交换函数
		template<class T>
		void swap(T& r1, T& r2)
		{
			T tmp = r1;
			r1 = r2;
			r2 = tmp;
		}
        
		// 向上调整建堆算法
		// 向上指的是插入的数据向上
		void AdjustUp(int child)
		{
			Compare cmp;
			// 循环调整
			// 调整到根结点就停止调整,即 child = 0
			while (child > 0)
			{
				int parent = (child - 1) / 2;
				// 大的往上放，小的往下放
				//if (_cont[child] > _cont[parent])
				// 大堆 --- Less  小堆 --- Greater
				if(cmp(_cont[parent], _cont[child]))
				{
					swap(_cont[parent], _cont[child]);
					// 移动 child 的位置
					child = parent;
				}
				// 小于等于，就结束调整
				else
				{
					break;
				}
			}
		}
    
		// 向下调整建堆算法
		// 向下指的是根结点向下
		void AdjustDown(int parent)
		{
			int child = parent * 2 + 1; // 左孩子
			Compare cmp;
			// 让根结点与左右孩子中大的那个数进行比较
			// 让大的往上放，小的往下放
			// 孩子下标不能越界
			while (child < _cont.size())
			{
				// 找左右孩子中大的那个孩子
				// child + 1 < _cont.size() 是为了判断右孩子是否存在
				if (child + 1 < _cont.size() && _cont[child + 1] > _cont[child])
				{
					child++;
				}
				
				// 孩子结点大于根结点，交换
				//if (_cont[child] > _cont[parent])
				// 大堆 --- Less  小堆 --- Greater
				if (cmp(_cont[parent], _cont[child]))
				{
					swap(_cont[child], _cont[parent]);
					// child 和 parnet 向下走
					parent = child;
					child = parent * 2 + 1;
				}
				// 孩子结点小于等于根结点，建堆完毕，跳出循环
				else
				{
					break;
				}
			}
		}

	public:
		// 强制编译器默认生成构造函数
		// 对底层的容器初始化
		priority_queue() = default;

		// 迭代器区间初始化
		template<class InputIterator>
		priority_queue(InputIterator first, InputIterator last)
			: _cont(first, last)
		{
			// 使用向下调整算法建堆,向下调整建堆的算法的效率更高
			for (int i = (_cont.size() - 1 - 1) / 2; i >= 0; i--)
			{
				AdjustDown(i);
			}
		}

		// 入堆 —— push 函数
		void push(const T& val)
		{
			// 尾插
			_cont.push_back(val);
			
			// 向上调整建堆 --- 从堆尾开始调整
			AdjustUp(_cont.size() - 1);
		}

		// 出堆顶数据 —— pop 函数
		void pop()
		{
			// 将堆顶数据与堆尾数据交换
			swap(_cont[0], _cont[_cont.size() - 1]);
			// 再删除堆尾元素
			_cont.pop_back();
			// 向下调整建堆 --- 从堆头开始
			AdjustDown(0);
		}

		// 取堆顶数据 —— top 函数
		T& top()
		{
			// 取优先级队列第一个元素
			return _cont[0];
		}

		// 判断堆是否为空 —— empty 函数
		bool empty()
		{
			return _cont.empty();
		}

		// 获取堆中有效元素个数 —— size 函数
		size_t size()
		{
			return _cont.size();
		}
	private:
		Container _cont;
	};
}

前面我们实现的仿函数都是用来比较大小，是不是所有的仿函数都只能用于比较大小？并不是，我们可以根据具体的情况，设置自己需求的仿函数。如算法库中的 find_if 函数，模板声明为：template <class InputIterator, class UnaryPredicate> InputIterator find_if (InputIterator first, InputIterator last, UnaryPredicate pred)，pred 就是一个仿函数，它的内部实现是判断遍历到的元素是否等于查找的目标元素。若使用 find_if 函数来查找容器中第一个偶数，则仿函数的内部实现又不一样。

6. 知识回顾

实现顺序结构二叉树-CSDN博客

栈和队列（C）_c语言入栈操作-CSDN博客

亚马逊云科技技术品牌专区

更多推荐

open-code-review Codex 插件教程：对话式调用评审技能指南

本文是一份面向新手的 **open-code-review Codex 插件教程**，教你在 Codex 中通过对话式方式调用 open-code-review 的 AI 代码评审技能。open-code-review 是阿里巴巴开源的 AI 代码评审工具，采用"确定性流水线 + LLM Agent"混合架构，内置多语言评审规则（NPE、线程安全、XSS、SQL 注入等），可在 Codex 里用一

亚马逊云科技技术品牌专区

OBS Studio 完整指南：免费开源录屏与直播软件从零上手

想做一场像模像样的直播，或者把屏幕内容录成教程视频，但一想到商用软件的订阅费就有些犹豫？其实你不需要花一分钱。OBS Studio 是一款免费开源的直播与录屏软件，支持 Windows、macOS 和 Linux，采集、混音、编码、推流、录制，一条流水线全包了。## 先搞清楚 OBS Studio 是什么OBS Studio 是一个"场景化"的采集合成工具：你把摄像头、窗口、浏览器、图片、

亚马逊云科技技术品牌专区

如何用MediaCrawler爬取小红书抖音数据？7大平台爬虫从安装到实战完整指南

MediaCrawler 是一个支持小红书、抖音、快手、B站、微博、百度贴吧、知乎的开源自媒体数据采集工具。它能按关键词、按帖子、按创作者主页三种方式抓取笔记/视频内容、评论甚至二级评论，并把结果存成 JSON、CSV、Excel 或数据库。适合做市场调研、竞品监控、内容选题的运营人员，以及想要现成爬虫框架而不想从零写 JS 逆向的开发者。## 从一次"手动抄数据"说起想象这个场景：你负责