priority_queue匿名函数排序

### 如何使用 Lambda 函数对 `priority_queue` 进行自定义排序 在 C++ 中，`std::priority_queue` 是一种容器适配器，默认情况下它是一个最大堆（即顶部元素始终是最大的）。如果需要改变其默认行为并实现自定义排序，则可以通过提供一个比较函数来完成。从 C++11 起，支持使用 lambda 表达式作为这种比较函数。 以下是具体说明以及代码示例： #### 基本语法结构 要通过 lambda 实现自定义排序，需指定三个模板参数： 1. **数据类型**：存储的数据类型。 2. **底层容器**：通常是 `std::vector` 或其他 STL 容器。 3. **比较函数**：用于决定优先级顺序的规则。 对于第三个参数，可以传递一个 lambda 表达式的类型 (`decltype`) 和实例化后的 lambda 对象本身。 --- #### 示例代码 下面展示如何利用 lambda 创建一个小顶堆（最小堆）和大顶堆（最大堆）的例子。 ```cpp #include <iostream> #include <queue> int main() { // 小顶堆 (minimum heap): 顶部是最小值 auto minHeapComp = [](const int& a, const int& b) { return a > b; }; std::priority_queue<int, std::vector<int>, decltype(minHeapComp)> minPQ(minHeapComp); minPQ.push(10); minPQ.push(30); minPQ.push(20); std::cout << "Min Heap Top Element: " << minPQ.top() << std::endl; // 大顶堆 (maximum heap): 默认情况或者手动设置 auto maxHeapComp = [](const int& a, const int& b) { return a < b; }; std::priority_queue<int, std::vector<int>, decltype(maxHeapComp)> maxPQ(maxHeapComp); maxPQ.push(10); maxPQ.push(30); maxPQ.push(20); std::cout << "Max Heap Top Element: " << maxPQ.top() << std::endl; } ``` 上述程序展示了两种不同类型的堆构建方式，并分别打印它们的顶端元素[^2]。 #### 关键点解析 - **Lambda 的作用**: 在此场景下，lambda 主要用作比较运算符，返回布尔值以指示两个元素之间的相对位置关系。 - **decltype 的用途**: 当前编写的 lambda 需要在声明阶段告知编译器它的实际类型是什么；因此借助 `decltype` 提取该匿名函数的具体签名形式。 - **性能考量**: 使用标准库中的向量作为内部存储机制能够保证较好的时间复杂度 O(log n)，其中每次插入/删除操作均涉及重新调整树形结构的过程[^3]。 --- ### 注意事项 当处理更复杂的对象比如 `std::pair` 类型时，同样适用类似的模式。只需修改对应的 key 访问路径即可满足特定需求。 例如按第二个字段升序排列的一组整数对的小根堆可如下定义: ```cpp auto pairCompare = [](const std::pair<int,int>& lhs, const std::pair<int,int>& rhs){ return lhs.second > rhs.second; }; std::priority_queue<std::pair<int,int>, std::vector<std::pair<int,int>>, decltype(pairCompare)> pqPair(pairCompare); pqPair.emplace(1,5); pqPair.emplace(2,7); pqPair.emplace(3,6); while(!pqPair.empty()){ std::cout<<pqPair.top().first<<" "<<pqPair.top().second<<"\n"; pqPair.pop(); } ``` 以上片段实现了基于第二成员变量从小到大的排序逻辑. ---