场景

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

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

说明

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

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

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

例子

以下对整数比较, 日期比较的 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