网站外部链接,旅行网站开发,相城区住房建设局网站,网页制作题库一、引言
队列的特性是先进先出。优先级队列的本质是一个有序队列#xff0c;根据成员的优先级#xff0c;对队列中的成员进行排序。优先级队列默认是大顶堆#xff0c;即堆顶元素最大
二、常用函数
empty()size()top()push()emplace()pop()swap()
三、代码示例
class …一、引言
队列的特性是先进先出。优先级队列的本质是一个有序队列根据成员的优先级对队列中的成员进行排序。优先级队列默认是大顶堆即堆顶元素最大
二、常用函数
empty()size()top()push()emplace()pop()swap()
三、代码示例
class SS {public:SS(int _val 0) : val(_val) {}bool operator(const SS ss) const { return val ss.val; } // 声明 pq1 的基础bool operator(const SS ss) const { return val ss.val; } // 声明 pq2 的基础int val;
};struct SS_Compare {public:bool operator()(const SS ss1, const SS ss2) const { // 声明 pq 的基础return ss1.val ss2.val;}
};int main() {priority_queueSS, vectorSS, SS_Compare pq;priority_queueSS, vectorSS, lessSS pq1;priority_queueSS, vectorSS, greaterSS pq2;pq.push(SS(1));pq.push(SS(2));pq.push(SS(3));vectorSS v;sort(v.begin(), v.end(), SS_Compare());while (!pq.empty()) {std::cout pq.top().val std::endl;pq.pop();}return 0;
}四、自定义排序方法
在上述的代码示例中展示了三种使用自定义排序函数的方法
使用仿函数重载然后使用less重载然后使用greater 注意到在使用仿函数的时候我们给优先级队列传递的是类型而在sort()函数中使用仿函数的时候我们传递的实参是临时函数对象。 这个差异源于优先级队列(priority_queue)和排序算法(sort)在C中不同的设计方式。 那为什么要这么设计呢 优先级队列: 需要存储比较器作为成员变量因此需要在构造时知道类型排序算法: 是一次性操作可以直接接受一个比较器对象 这种设计差异是C标准库的历史和实用性的结果反映了不同容器和算法的使用模式。 五、容器
优先级队列使用的默认容器是vector也可以选用deque或者自定义容器类型。 但自定义容器类型必须满足一些要求才能被优先级队列接受。 此外默认容器vector已经足够高效所以通常不建议使用自定义容器。
