C++中priority_queue模擬實(shí)現(xiàn)
前言
作者今天上午模擬實(shí)現(xiàn)了C++stl的queue，晚上實(shí)現(xiàn)priority_queue后，寫(xiě)下了這篇博客
prority_queue也是一個(gè)容器適配器，不過(guò)它的底層是用數(shù)組來(lái)實(shí)現(xiàn)的，即默認(rèn)為vector容器
它還多了第三個(gè)模板參數(shù)，一個(gè)用于改變比較方式的類(lèi)，通過(guò)設(shè)置不同的類(lèi)，能實(shí)現(xiàn)大根堆或者小根堆
1. 仿函數(shù)的使用
template <class T>
struct less
{
bool operator()(const T &x, const T &y) const
{
return x < y;
}
}; template <class T, class Container = std::vector<T>, class Compare = less<T>>
class MyPriorityQueue
{
public:比如這樣實(shí)例化一個(gè)對(duì)象，MyPriorityQueue<int> q; 第二個(gè)和第三個(gè)模板參數(shù)以及默認(rèn)給出，那么q對(duì)象中有一個(gè)成員Compare _com的類(lèi)型就為less<T>類(lèi)型，_com是一個(gè)less<T>類(lèi)型的對(duì)象
比較兩個(gè)int類(lèi)型的變量時(shí)，直接_com(a, b)就會(huì)調(diào)用運(yùn)算符重載函數(shù)去比較
2. 向上調(diào)整算法時(shí)，父節(jié)點(diǎn)左右孩子也作比較
int child = parent * 2 + 1;
while (child < n)
{
if (child + 1 < n && _com(_con[child], _con[child + 1]))
{
child++;
}
if (_com(_con[parent], _con[child]))
{
std::swap(_con[parent], _con[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}以大根堆為例，首先要保證堆的父結(jié)點(diǎn)大于子結(jié)點(diǎn)，作者先對(duì)兩個(gè)子節(jié)點(diǎn)進(jìn)行比較，挑出一個(gè)更大的，這樣保證了在父子結(jié)點(diǎn)交換后，被交換上去的子節(jié)點(diǎn)一定比另一個(gè)子節(jié)點(diǎn)大
3. 為什么仿函數(shù)的運(yùn)算符重載函數(shù)要設(shè)置為const成員函數(shù)
template <class T>
struct less
{
bool operator()(const T &x, const T &y) const
{
return x < y;
}
};比如實(shí)例化一個(gè)const MyPriorityQueue<int> q;對(duì)象，那么q對(duì)象的成員變量不能被修改
即Compare _com其實(shí)是const Compare _com，那么一個(gè)const對(duì)象在調(diào)用它的成員函數(shù)時(shí)，無(wú)法調(diào)用非const成員函數(shù)
而operator本身作為比較邏輯，是不會(huì)修改對(duì)象的，所以要加上const修飾this指針
4. top()和pop()需要對(duì)元素個(gè)數(shù)做檢查
void pop()
{
assert(size() > 0);
std::swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
if (size() > 1)
{
AdjustDown(_con.size(), 0);
}
}
T &top()
{
assert(size() > 0);
return _con[0];
}
const T &top() const
{
assert(size() > 0);
return _con[0];
}為了防止刪除空vector或者獲取空vector里的數(shù)據(jù)，從而造成非法訪問(wèn)
需要嚴(yán)格保證進(jìn)行top獲取堆頂元素或者刪除堆頂元素的時(shí)候，保證堆非空
5. explicit關(guān)鍵字 修飾函數(shù)的作用
explicit MyPriorityQueue(const Compare &com = Compare())
: _com(com)
{
}explicit防止了實(shí)參的隱式類(lèi)型轉(zhuǎn)換
因?yàn)殡[式類(lèi)型轉(zhuǎn)換會(huì)帶來(lái)代碼可讀性的問(wèn)題
以及誤寫(xiě)出代碼時(shí)，不好排查
6. MyPriorityQueue仿函數(shù)類(lèi)對(duì)象 構(gòu)造函數(shù)存在的意義
explicit MyPriorityQueue(const Compare &com = Compare())
: _com(com)
{
}用仿函數(shù)類(lèi)對(duì)象 來(lái)構(gòu)造 MyPriorityQueue，是為了適配各種仿函數(shù)類(lèi)，因?yàn)槌俗髡邔?xiě)的greater<int>和less<int>以外，還會(huì)有帶狀態(tài)變量的仿函數(shù)類(lèi)
template<class T>
struct MyComp
{
int flag;
// 構(gòu)造時(shí)傳入 flag
MyComp(int f) : flag(f) {}
bool operator()(const T &a, const T &b) const {
if (flag == 1)
return a < b; // 大堆
else
return a > b; // 小堆
}
};比如MyPriorityQueue<int, std::vector<int>, MyComp> q1(MyComp(1));
q1是大根堆，因?yàn)闃?gòu)造MyComp時(shí)狀態(tài)為1，比較時(shí)會(huì)走flag==1的邏輯
MyPriorityQueue<int, std::vector<int>, MyComp> q2(MyComp(2));
q2是小根堆，因?yàn)闃?gòu)造MyComp時(shí)狀態(tài)不為1，比較時(shí)會(huì)走else的邏輯
7. 命名空間防止與stl里面的函數(shù)或類(lèi)發(fā)生沖突
自定義的less模板類(lèi)與std庫(kù)里面的less模板類(lèi)同名了，所以為了解決同名沖突，給less，greater，MyPriorityQueue 放在一個(gè)命名空間中
那么可以用 命名空間名::來(lái)指定less或者其它同名變量、類(lèi)、函數(shù)等是哪個(gè)命名空間里的，防止命名沖突的發(fā)生
總體實(shí)現(xiàn)
#pragma once
#include <vector>
#include <cassert>
namespace MyPriorityQueueModule
{
template <class T>
struct less
{
bool operator()(const T &x, const T &y) const
{
return x < y;
}
};
template <class T>
struct greater
{
bool operator()(const T &x, const T &y) const
{
return x > y;
}
};
template <class T, class Container = std::vector<T>, class Compare = less<T>>
class MyPriorityQueue
{
public:
// 為了支持帶狀態(tài)的比較器
explicit MyPriorityQueue(const Compare &com = Compare())
: _com(com)
{
}
void AdjustUp(int child)
{
int 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;
}
}
}
void push(const T &x)
{
_con.push_back(x);
AdjustUp(_con.size() - 1);
}
void AdjustDown(int n, int parent)
{
int child = parent * 2 + 1;
while (child < n)
{
if (child + 1 < n && _com(_con[child], _con[child + 1]))
{
child++;
}
if (_com(_con[parent], _con[child]))
{
std::swap(_con[parent], _con[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void pop()
{
assert(size() > 0);
std::swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
if (size() > 1)
{
AdjustDown(_con.size(), 0);
}
}
T &top()
{
assert(size() > 0);
return _con[0];
}
const T &top() const
{
assert(size() > 0);
return _con[0];
}
size_t size() const
{
return _con.size();
}
bool empty() const
{
return _con.empty();
}
private:
Container _con;
Compare _com;
};
}
測(cè)試代碼
#include <iostream>
#include <vector>
#include "MyPriorityQueue.hpp"
// 不寫(xiě) using namespace！
// 帶狀態(tài)比較器
struct MyComp
{
int flag;
MyComp(int f) : flag(f) {}
bool operator()(int a, int b) const {
if (flag == 1) return a < b;
else return a > b;
}
};
int main()
{
// 大根堆（明確寫(xiě)：MyPriorityQueueModule::）
std::cout << "大根堆：";
MyPriorityQueueModule::MyPriorityQueue<int> q1;
q1.push(3);
q1.push(1);
q1.push(5);
q1.push(2);
q1.push(4);
while (!q1.empty()) {
std::cout << q1.top() << " ";
q1.pop();
}
std::cout << std::endl;
// 小根堆
std::cout << "小根堆：";
MyPriorityQueueModule::MyPriorityQueue<int, std::vector<int>, MyPriorityQueueModule::greater<int>> q2;
q2.push(3);
q2.push(1);
q2.push(5);
q2.push(2);
q2.push(4);
while (!q2.empty()) {
std::cout << q2.top() << " ";
q2.pop();
}
std::cout << std::endl;
return 0;
}測(cè)試結(jié)果
./test
大根堆：5 4 3 2 1
小根堆：1 2 3 4 5
到此這篇關(guān)于C++中priority_queue模擬實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)C++ priority_queue模擬內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
在?C++?編程中,調(diào)試日志對(duì)于定位問(wèn)題和優(yōu)化代碼至關(guān)重要,本文將介紹幾種常用的調(diào)試日志輸出方法,并教你如何在日志中添加時(shí)間戳,希望對(duì)大家有所幫助2025-01-01
C語(yǔ)言編程C++柔性數(shù)組結(jié)構(gòu)示例講解
這篇文章主要介紹了C語(yǔ)言編程系列中的柔性數(shù)組，文中含有詳細(xì)的示例代碼講解，有需要的朋友可以借鑒參考下，希望能夠有所幫助2021-09-09
變長(zhǎng)參數(shù)的函數(shù)，即參數(shù)個(gè)數(shù)可變、參數(shù)類(lèi)型不定的函數(shù)。設(shè)計(jì)一個(gè)參數(shù)個(gè)數(shù)可變、參數(shù)類(lèi)型不定的函數(shù)是可能的，最常見(jiàn)的例子是printf函數(shù)、scanf函數(shù)和高級(jí)語(yǔ)言的Format函數(shù)。最近的一個(gè)項(xiàng)目中就遇到這么一個(gè)相關(guān)的問(wèn)題，感興趣的朋友們下面來(lái)一起看看吧。2016-10-10
JSON是一種對(duì)源自Javascript的對(duì)象數(shù)據(jù)進(jìn)行編碼的格式,但現(xiàn)在被廣泛用作互聯(lián)網(wǎng)上的數(shù)據(jù)交換格式,本文主要介紹了Qt使用Json的項(xiàng)目實(shí)踐,詳細(xì)的介紹了主要使用的類(lèi)以及Json實(shí)戰(zhàn),感興趣的可以了解一下2023-09-09
學(xué)習(xí)二維動(dòng)態(tài)數(shù)組指針做矩陣運(yùn)算的方法
這片文章介紹了如何利用二維動(dòng)態(tài)數(shù)組指針做矩陣運(yùn)算,需要的朋友可以參考下2015-07-07
C++實(shí)現(xiàn)進(jìn)程間通信(IPC)的終極指南
進(jìn)程間通信（IPC,Inter-Process Communication）,指至少兩個(gè)進(jìn)程或線(xiàn)程間傳送數(shù)據(jù)或信號(hào)的一些技術(shù)或方法,下面小編來(lái)和大家深入介紹一下C++實(shí)現(xiàn)進(jìn)程間通信(IPC)的相關(guān)方法吧2025-04-04
C/C++編譯報(bào)錯(cuò)printf was not declared in
這篇文章主要介紹了C/C++編譯報(bào)錯(cuò)printf was not declared in this scope問(wèn)題及解決方案,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-08-08
VC++開(kāi)發(fā)中完美解決頭文件相互包含問(wèn)題的方法解析
本文中，為了敘述方便，把class AClass;語(yǔ)句成為類(lèi)AClass的聲明，把class AClass開(kāi)始的對(duì)AClass的類(lèi)成員變量、成員函數(shù)原型等的說(shuō)明稱(chēng)為類(lèi)的定義，而把在CPP中的部分稱(chēng)為類(lèi)的定義2013-09-09
這篇文章主要介紹了c++讀取sqlserver的示例,需要的朋友可以參考下2014-02-02
Qt 是一個(gè)跨平臺(tái)的應(yīng)用程序開(kāi)發(fā)框架,除了用于創(chuàng)建圖形界面應(yīng)用程序外,還可以用來(lái)生成 Word 和 PDF 文檔,本文將介紹如何使用 Qt 來(lái)生成Word和PDF文檔,以及相關(guān)的代碼示例,需要的朋友可以參考下2023-10-10