【c++】STL-容器适配器priority_queue与仿函数

mosheng

发布于 2026-01-14 18:31:07

720

文章被收录于专栏：c++c++

hello~ 很高兴见到大家! 这次带来的是C++中关于priority_queue容器迭代器这部分的一些知识点,如果对你有所帮助的话,可否留下你宝贵的三连呢? 个人主页: 默|笙

一、priority_queue的介绍和使用

1.介绍

<priority_queue文档介绍>

<堆介绍博客>

priority_queue（优先级队列）基本情况：priority_queue是一种容器适配器，它的逻辑结构跟堆差不多，默认是大堆；物理结构要看底层容器，默认是vector，也可以用deque。上面是大根堆与小根堆的逻辑结构。

默认底层容器是vector的原因：因为它的下标访问速率更快。不支持list作为底层容器，因为list仅提供双向迭代器，而priority_queue需要的是随机迭代器。

以上是 priority_queue提供的一些接口，接下来我来简要的说明一些常用接口的作用：

(constructor)：构造函数，用于构造 priority_queue 类对象。其中系统自动生成的无参默认构造和范围(迭代器区间)构造用得比较多。
empty()：判断priority_queue对象是否为空。
size()：返回 priority_queue对象里元素的个数。
top()：返回优先级队列顶部的元素，即堆顶元素。
push()：压入一个元素。
pop()：移除优先级队列顶部元素，它没有返回值，不会返回被移除的元素值。

2. 使用

关于priority_queue对象的创建：能够看到，priority_queue这个容器适配器有三个模板参数，依次是：T: 接收存储元素的类型，Container：接收底层容器的类型，Compare：接收比较器（一般传递仿函数类类型，之后会讲到）的类型。其中后面两个模板参数都有默认值，在进行实例化对象时可以不用传递参数。

 //使用priority_queue时要包含头文件queue
 priority_queue<int> pq1;

关于Container：vector是默认容器，我们也可以根据需求来改变底层容器，比如deque。

priority_queue<int, deque<int>> pq2;

关于Compare：默认值是less这个仿函数类型，因为它，priority_queue对象里大的数据的优先级更高，是大堆结构。我们可以传递另一个仿函数类型greater，这样是小堆结构，小的数据的优先级更高。比如下列代码：

priority_queue<int> pq1;
priority_queue<int, deque<int>> pq2;
//要传递第三个参数的话，第二个参数的值也不能漏掉
priority_queue<int, vector<int>, greater<int>> pq3;

pq1.push(1);
pq1.push(2);
pq1.push(3);
pq1.push(4);

pq3.push(1);
pq3.push(2);
pq3.push(3);
pq3.push(4);

cout << "less: ";
while (!pq1.empty())
{
	cout << pq1.top() << " ";
	pq1.pop();
}
cout << endl;

cout << "greater: ";
while (!pq3.empty())
{
	cout <<  pq3.top() << " ";
	pq3.pop();
}

由于priority_queue也是不支持迭代器（迭代器能提供随机访问）的，所以其对象的遍历需要用到top()与pop()接口来实现。

less -> " < " 大堆
greater -> " > " 小堆

它跟我们平常的思维习惯是反着来的，这一点要注意。其中的 < 与 > 是关于它的实现，可以参考下面的仿函数章节。

不要搞混sort里面的Compare与priority_queue的Compare：sort是一个函数模板，而priority_queue是一个类模板。一个是函数模板类型参数，接收的是对象；一个是类模板参数，接收的是类型。

一般比较器接收的是仿函数类类型的原因：比较器通常接收仿函数类类型而非函数指针或其他形式，一部分原因是因为类型的传递。就比如函数指针传递的是函数指针它的类型，而非传递函数指针所指向的函数，我们不知道实例化出来的对象里的函数指针指向哪里，可能是空指针，也可能是随机值，总之都是无效指针。当然，也不是不能传递函数指针，不过这个过程会非常麻烦。

二、仿函数

仿函数，数如其名，它不是真函数，而是一个类。不过它的实例化对象可以像函数一样使用，这就得归功于仿函数内部对于()的重载。也可以这样说，重载了()的就是仿函数。
我们来实现两个简单的less和greater仿函数以便更好的了解它：

namespace mosheng//防止与std里的冲突
{
	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()(cosnt T& a, cosnt T& b)
		{
			return a > b;
		}
	};
}

我们可以把它用在冒泡排序里来控制升序和降序：

template<class T, class Compare = mosheng::less<T>>
	void BubbleSort(T* a, int n, Compare com)
	{
		int exchange = 0;
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n - i - 1; j++)
			{
				//等价于com.operator()(a[j + 1], a[j])
				if (com(a[j + 1], a[j]))
				{
					exchange = 1;
					swap(a[j], a[j + 1]);
				}
			}
			if (exchange == 0)
			{
				break;
			}
		}
	}
int main()
{
	int arr[] = { 1, 5, 12, 2, 1, 3, 77 };
	BubbleSort(arr, 7, mosheng::less<int>());
	cout << "less: ";
	for (auto e : arr)
	{
		cout << e << " ";
	}
	cout << endl;

	cout << "greater: ";
	BubbleSort(arr, 7, mosheng::greater<int>());
	for (auto e : arr)
	{
		cout << e << " ";
	}
	cout << endl;
	return 0;
}

就有：

我们将仿函数类类型less与greater传递给Campare，进而创造出Compare类型的实例化对象com，再通过com调用operator()函数，com(a[j + 1], a[j])，等价于com.operator()(a[j + 1], a[j])，进而达到目的。可以看到，虽然com不是函数，只是类的实例化对象，但它与函数的功能无二，所以是仿函数。
有的时候，库里面提供的仿函数不能够达到我们的目的，比如为Date类的指针排序，它比较的是指针的大小，而不是指针所指向的数据。这个时候我们就得自己构建仿函数。如下：

class Date
{
public:
	Date(int year = 1900, int month = 1, int day = 1)
		: _year(year)
		, _month(month)
		, _day(day)
	{}

	bool operator<(const Date& d)const
	{
		return (_year < d._year) ||
			(_year == d._year && _month < d._month) ||
			(_year == d._year && _month == d._month && _day < d._day);
	}

	bool operator>(const Date& d)const
	{
		return (_year > d._year) ||
			(_year == d._year && _month > d._month) ||
			(_year == d._year && _month == d._month && _day > d._day);
	}

	friend ostream& operator<<(ostream& _cout, const Date& d);
private:
	int _year;
	int _month;
	int _day;
};

ostream& operator<<(ostream& _cout, const Date& d)
{
	_cout << d._year << "-" << d._month << "-" << d._day;
	return _cout;
}

//构建仿函数
struct PDateLess
{
	bool operator()(const Date* p1, const Date* p2)
	{
		return *p1 < *p2;
	}
};


int main()
{
	priority_queue<Date*, vector<Date*>> q1;
	q1.push(new Date(2025, 7, 20));
	q1.push(new Date(2025, 7, 21));
	q1.push(new Date(2025, 7, 22));
	
	cout << "原始：";
	while (!q1.empty())
	{
		cout << *q1.top() << " ";
		q1.pop();
	}
	cout << endl;


	cout << "构建的PDteLess：";
	priority_queue<Date*, vector<Date*>, PDateLess> q2;
	q2.push(new Date(2025, 7, 20));
	q2.push(new Date(2025, 7, 21));
	q2.push(new Date(2025, 7, 22));

	while (!q2.empty())
	{
		cout << *q2.top() << " ";
		q2.pop();
	}
	cout << endl;
	return 0;
}

原始里面的顺序是随机的，不是我们预期的效果。

还有的时候，我们在查阅算法库里面的一些函数时，常常能够看到很多函数不光有普通版本，还有一个if 版本，这个就是给仿函数准备的版本。比如我们在使用 find_if 时，可以传递我们自己的仿函数来控制 find_if 函数所找元素的特征，比如找一串数据里的奇数，偶数等等。例如查找第一个偶数：

struct op1
{
	bool operator()(int x)
	{
		return x % 2 == 0;
	}
};

int main()
{
	int a[] = { 1, 3, 5, 8, 2 };
	//找第一个偶数
    auto x = find_if(a, a + 5, op1());
	cout << *x << endl;
	return 0;
}

小总结：

一般在两种时候我们自己构造仿函数：

标准库里提供的仿函数无法满足我们的要求时。
使用算法库里面的一些特殊函数时。

三、priority_queue的模拟实现

priority_queue的模拟实现离不开堆排序里的向上调正算法和向下调整算法，可以看这篇博客->堆排序

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;
	}
};



namespace mosheng
{
	template<class T, class Container = vector<T>, class Compare = Less<T>>
	class priority_queue
	{
	public:
		priority_queue() = default;//强制生成默认构造函数

		//range构造函数
		template<class InputIterator>
		priority_queue(InputIterator first, InputIterator last)
			: _con(first, last)
		{
			//向下调整建堆
			size_t parent = (_con.size() - 1 - 1) / 2;

			while (parent >= 0)
			{
				size_t child = parent * 2 + 1;
				if ((child + 1 < _con.size()) && (_con[child] < _con[child + 1]))
				{
					child = child + 1;
				}
				if (com(_con[parent], _con[child]))
				{
					std::swap(_con[child], _con[parent]);
				}
				
				parent--;
			}

		}

		//插入
		void push(const T& x)
		{
			_con.push_back(x);
			//向上调整算法
			AdjustUp();

		}

		//取堆顶数据
		T& top()
		{
			return _con[0];
		}
		const T& top()const
		{
			return _con[0];
		}


		//移除
		void pop()
		{
			//先交换首尾数据再向下调整数据
			std::swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			//向下调整数据
			size_t parent = 0;
			size_t child = parent * 2 + 1;

			
			while (child < _con.size())
			{

				if ((child + 1 < _con.size()) && (_con[child] < _con[child + 1]))
				{
					child = child + 1;
				}

				if (com(_con[parent], _con[child]))
				{
					std::swap(_con[parent], _con[child]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}

			


		}

		//返回大小
		size_t size()
		{
			return _con.size();
		}

		bool empty()const
		{
			return _con.empty();
		}

	private:
		void AdjustUp()
		{
			size_t child = _con.size() - 1;
			size_t parent = (child - 1) / 2;

			while (child > 0)
			{
				if (com(_con[parent], _con[child]))
				{
					std::swap(_con[parent], _con[child]);
					child = parent;
					parent = (child - 1) / 2;
				}

				else
				{
					break;
				}
			}
		}
	private:

		Container _con;
		Compare com;
	};
}