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