[C/C++]_[初级]_[std::priority_queue的介绍]

场景

1. 有时候我们需要一个容器, 在插入时能按照指定的顺序排列, 从而在元素全部插入后, 或者删除某个元素时不需要重新对容器进行sort.

2. std::vector 和 std::queue 不具备这种特性. std::map的key具备这种特性, 但是缺点就是不能进行复杂的比较. std::map的使用细节

说明

1. std::priority_queue 可以在进行插入数据时就进行比较并排序. 可以指定复杂的排序. 缺点就是只支持一次性枚举, 如果需要枚举std::priority_queue, 那么需要类似于queue的特性那样pop出来.

2. std::priority_queue 提供常量的时间复杂度查询最大值. 插入和提取的时间复杂度是 对数时间(logarithmic time).

3. Compare比较器如果使用std::greater<T>时, 最小的元素出现在top位置. 比较器使用strict weak ordering..

Establishes strict weak ordering relation with the following properties
For all a, comp(a,a)==false
If comp(a,b)==true then comp(b,a)==false
if comp(a,b)==true and comp(b,c)==true then comp(a,c)==true

例子

1. 以下对整数比较, 日期比较的 std::priority_queue.

图示

template<typename T>
class A
{
public:
	std::basic_string<T> date;

};

// https://en.cppreference.com/w/cpp/named_req/Compare
// https://en.cppreference.com/w/cpp/container/priority_queue
void TestPriorityQueue()
{
	std::priority_queue<int> q;
	srand(time(NULL));
	for(int i = 0; i< 10; ++i)
		q.push(rand());

	auto q1 = q; // 如果需要继续使用 std::priority_queue 容器数据, 需要复制.
	print_queue(q); // 打印或者说枚举 queue 里的元素, 需要 pop 出元素. 也就是只能枚举一次.

	// 自定义比较函数
	typedef A<wchar_t> A1;
	auto Func = [](const A1& first, const A1& second)->bool{
		return first.date < second.date;
	};
	std::priority_queue<A1,std::vector<A1>,decltype(Func)> a_queue;
	long long temp = 20181001;
	for(int i = 0; i< 10;++i){
		A1 a;
		a.date = std::to_wstring(temp+i);
		a_queue.push(a);
	}
	
	while(!a_queue.empty()) {
		std::wcout << a_queue.top().date << L" ";
		a_queue.pop();
	}
	std::wcout << L'\n';
}

输出

31180 28104 24260 23942 21404 19083 11173 8284 6993 567
20181010 20181009 20181008 20181007 20181006 20181005 20181004 20181003 20181002
 20181001

参考

C++ named requirements: Compare
std::priority_queue