柚子快報激活碼778899分享：c++ priority
柚子快報激活碼778899分享：c++ priority
文章目錄
全部的實現(xiàn)代碼放在了文章末尾什么是適配器模式？準備工作包含頭文件定義命名空間類的成員變量什么是仿函數(shù)？比較仿函數(shù)在priority_queue中的作用通過傳入不同的仿函數(shù)可以做到大堆和小堆之間的切換通過傳入不同的仿函數(shù)可以做到改變priority_queue里面的比較邏輯
構造函數(shù)默認構造迭代器區(qū)間構造
sizeemptytoppushpop
全部代碼
全部的實現(xiàn)代碼放在了文章末尾
【不了解堆（priority_queue）的可以看我這篇文章：模擬實現(xiàn)堆的接口函數(shù)】
priority_queue的模擬實現(xiàn)和stack，queue一樣，采用了C++適配器模式
priority_queue的適配器一般是vector，也可以是deque
因為priority_queue是有特殊限制的線性表【只能取堆頂數(shù)據(jù)，并且需要高效的尾插尾刪，還要支持高效的下標訪問（因為priority_queue的push和pop一般是調(diào)用適配器的尾插，尾刪。 實現(xiàn)向下（上）調(diào)整算法的時候需要高效的下標訪問方法）】 所以只要是線性結構并且可以高效的實現(xiàn)尾插和尾刪，支持高效的下標訪問的線性表，就可以作為priority_queue的適配器
什么是適配器模式？
適配器模式是一種設計模式，它允許將不兼容接口的類一起工作。
適配器模式通常用于以下情況：
希望使用一個類，但其接口與其他代碼不兼容。希望創(chuàng)建一個可重用的類，它能夠?qū)⒔涌谵D換為其他接口。希望使用第三方庫或遺留代碼，但其接口與其他代碼不兼容。
適配器模式通常包括以下三個主要部分：
目標接口（Target）：這是期望使用的接口，客戶端代碼只能與目標接口交互。源接口（Adaptee）：這是需要適配的類，其接口與目標接口不兼容。適配器（Adapter）：這是一個類，它實現(xiàn)了目標接口，并將調(diào)用轉換為對源接口的調(diào)用。適配器將源接口的調(diào)用轉換為目標接口的調(diào)用，使得客戶端代碼可以與目標接口交互。
可以類比我們生活中的家庭電源接口和筆記本電腦充電口與電源適配器，它們之間也是一種適配器關系
筆記本電腦充電口是上面提到的目標接口 家庭電源接口是上面提到的源接口 電源適配器是上面提到的適配器
筆記本電腦的充電口是不能和家庭電源接口直接連接進行充電的，因為筆記本電腦用的是直流電，而家庭電源輸出的是交流電，所以要把交流電轉換為直流電才能給筆記本電腦供電，而電源適配器就能做到這一點
對應了上面提到的適配器模式解決的問題： 可以將不兼容接口的類一起工作
準備工作
創(chuàng)建兩個文件，一個頭文件mypriority_queue.hpp，一個源文件test.cpp
【因為模板的聲明和定義不能分處于不同的文件中，所以把成員函數(shù)的聲明和定義放在了同一個文件mypriority_queue.hpp中】
mypriority_queue.hpp：存放包含的頭文件，命名空間的定義，成員函數(shù)和命名空間中的函數(shù)的定義 test.cpp：存放main函數(shù)，以及測試代碼
包含頭文件
iostream：用于輸入輸出vector：提供vector類型的適配對象deque: 提供deque類型的適配對象assert.h:提供assert報錯函數(shù)
定義命名空間
在文件mypriority_queue.hpp中定義上一個命名空間mypriority_queue 把priority_queue類和它的成員函數(shù)放進命名空間封裝起來，防止與包含的頭文件中的函數(shù)/變量重名的沖突問題
類的成員變量
有兩個一個是適配器對象，一個是提供比較的仿函數(shù)，默認con是vector類型，comp是std庫里面的less
什么是仿函數(shù)？
C++中的仿函數(shù)是指那些能夠像函數(shù)一樣調(diào)用的對象，它們的類至少需要有成員函數(shù)operator()()。 仿函數(shù)可以是任何類型的對象，只要它的類重載了運算符()，它就能夠被調(diào)用，就可以作為函數(shù)使用。 在C++中，標準模板庫（STL）中的一些容器算法使用仿函數(shù)來封裝各種操作，使得這些操作可以應用于容器中的元素。
仿函數(shù)可以是用戶自定義的，也可以是C++標準庫中定義的。例如，STL中的std::less和std::greater就是兩個標準的比較仿函數(shù)，它們用于排序算法中。用戶也可以定義自己的仿函數(shù)
總結： C++的仿函數(shù)是重載了operator()的類實例化的對象，它可以被像函數(shù)那樣調(diào)用
舉個例子： 下圖是一個可以簡單進行大于比較的仿函數(shù)和它的類
比較仿函數(shù)在priority_queue中的作用
通過傳入不同的仿函數(shù)可以做到大堆和小堆之間的切換
【stl庫里面是傳入less類型的仿函數(shù)為大堆，傳入greater為小堆。 即大于是小堆，小于是大堆】 為什么呢？ 因為priority_queue需要用到比較的地方是向上（下）調(diào)整算法 如下圖： 【向上（調(diào)整）這篇文章不做詳細講解，不了解的可以看我這篇文章：模擬實現(xiàn)堆的接口函數(shù)】
根據(jù)傳給priorit_queue的第三個模板參數(shù)的不同，就可以得到不同類型的comp 這樣調(diào)用comp實現(xiàn)的功能就不一樣 std::less類型的comp的功能是判斷左參數(shù)是否小于右參數(shù) std::greater類型的comp的功能是判斷左參數(shù)是否大于右參數(shù) 通過這一點就可以調(diào)整大小堆了 因為 如果comp是小于，那么comp(con[parent],con[child])就是父親節(jié)點<孩子節(jié)點就交換，那么就會把大的節(jié)點一直往堆頂送，就可以實現(xiàn)大堆 comp是小于的時候同理
通過傳入不同的仿函數(shù)可以做到改變priority_queue里面的比較邏輯
我們使用priority_queue的時候，一般不需要我們傳入我們自己寫的仿函數(shù)，使用庫里面的std::less和std::greater就可以滿足我們的大部分需求
但是總規(guī)有一些情況，庫里面的比較仿函數(shù)的比較邏輯不符合我們的要求 此時就需要我們自己寫一個比較仿函數(shù)，傳給priority_queue
例 如果我們定義了一個坐標類pos
假設我們比較兩個pos對象的大小的時候分兩種情況
優(yōu)先比x，誰的x大誰就大，x相等時y大就大優(yōu)先比y，誰的y大誰就大，y相等時x大就大
如果我們用這兩種比較方式建出來的堆（priority_queue）肯定是不同的
這個時候庫里面的仿函數(shù)就滿足不了我們的要求了
我們要自己寫仿函數(shù)：
此時傳入不同的仿函數(shù)，得到的堆就不同 例
構造函數(shù)
默認構造
由于默認構造可以直接傳入適配器對象，因為傳入的適配器對象里面可能已經(jīng)有數(shù)據(jù)了，所以要把這些數(shù)據(jù)給建成堆，就算傳入的適配器對象是空的也能處理
例
迭代器區(qū)間構造
例
size
因為把priority_queue的數(shù)據(jù)都存儲在了適配器對象里面
所以適配器對象的size，就是priority_queue的size
加const是為了讓const修飾的對象也能調(diào)用
size_t size()const
{
return _con.size();
}
empty
因為把priority_queue的數(shù)據(jù)都存儲在了適配器對象里面
所以判斷適配器對象是否為空即可
加const是為了讓const修飾的對象也能調(diào)用
bool empty() const
{
return con.empty();
}
top
堆頂?shù)臄?shù)據(jù)只支持讀取， 不支持 修改
因為改了就有可能不是 堆 了
所以返回值是const T&
const T& top() const
{
因為把priority_queue的數(shù)據(jù)都存儲在了適配器對象里面
而且堆頂?shù)臄?shù)據(jù)存儲在適配器對象的第一個數(shù)據(jù)位置
所以直接調(diào)用front即可
return con.front();
}
push
void push(const T& val)
{
因為要把priority_queue的數(shù)據(jù)都存儲在適配器對象里面
所以新數(shù)據(jù)，直接尾插到適配器對象里面存儲
con.push_back(val);
再堆新插入的數(shù)據(jù)調(diào)用向上調(diào)整算法
保持插入之后也還是 堆 結構
AdiuUp(size() - 1);
}
pop
void pop()
{
堆不為空才能刪除
assert(!empty());
把堆頂與適配器最后一個數(shù)據(jù)交換
方便尾刪
std::swap(con[0], con[size() - 1]);
尾刪，把原來的堆頂數(shù)據(jù)刪除
con.pop_back();
對換到堆頂?shù)臄?shù)據(jù)進行向下調(diào)整算法
保持刪除之后也還是 堆 結構
AdiuDown(0);
}
全部代碼
#include
#include
#include
#include
using namespace std;
namespace mypriority_queue
{
template
class priority_queue
{
private:
//擁有比較大小能力的仿函數(shù)
Compare comp;
//適配器對象
Container con;
//向上調(diào)整算法
void AdiuUp(int child)
{
//找到 邏輯結構 中的父親節(jié)點
int parent = (child - 1) / 2;
while (child > 0)
{
//使用 比較仿函數(shù)comp 進行比較大小
//默認的comp是 std::less 類型的
//即 左參數(shù)<右參數(shù) 就返回true，否則返回false
if (comp(con[parent],con[child]))
{
std::swap(con[parent], con[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
//向下調(diào)整算法
void AdiuDown(int parent)
{
int n = this->size();
//找到 邏輯結構 中的左孩子節(jié)點
int child = parent*2+1;
while (child { if (child + 1 < n && comp(con[child], con[child + 1])) { child++; } //使用 比較仿函數(shù)comp 進行比較大小 //默認的comp是 std::less 類型的 if (comp(con[parent], con[child])) { std::swap(con[parent], con[child]); parent = child; child = parent * 2 + 1; } else { break; } } } public: priority_queue(const Container & ctnr = Container(),const Compare & comp = Compare()) { this->comp = comp; this->con = ctnr; int n = con.size(); //建堆，從最后一個葉子節(jié)點的父親節(jié)點開始 //n-1為邏輯結構上的 最后一個葉子節(jié)點的下標 //它的父親節(jié)點的下標等于 它的下標-1，再除以2 for (int i = (n - 1 - 1) / 2; i >= 0; i--) { //向下調(diào)整算法 AdiuDown(i); } } template priority_queue(InputIterator first, InputIterator last) { //遍歷迭代器區(qū)間 while (first != last) { //復用push進行插入 push(*first); ++first; } } size_t size()const { return con.size(); } bool empty() const { return con.empty(); } //堆頂?shù)臄?shù)據(jù)只支持讀取， 不支持 修改 //因為改了就有可能不是 堆 了 //所以返回值是const T& const T& top() const { //堆頂?shù)臄?shù)據(jù)存儲在適配器對象的第一個數(shù)據(jù)位置 return con.front(); } void push(const T& val) { //因為要把priority_queue的數(shù)據(jù)都存儲在適配器對象里面 //所以新數(shù)據(jù)，直接尾插到適配器對象里面存儲 con.push_back(val); //再堆新插入的數(shù)據(jù)調(diào)用向上調(diào)整算法 //保持插入之后也還是 堆 結構 AdiuUp(size() - 1); } void pop() { //堆不為空才能刪除 assert(!empty()); //把堆頂與適配器最后一個數(shù)據(jù)交換 //方便尾刪 std::swap(con[0], con[size() - 1]); //尾刪，把原來的堆頂數(shù)據(jù)刪除 con.pop_back(); //對換到堆頂?shù)臄?shù)據(jù)進行向下調(diào)整算法 //保持刪除之后也還是 堆 結構 AdiuDown(0); } }; } 柚子快報激活碼778899分享：c++ priority 推薦閱讀
本文內(nèi)容根據(jù)網(wǎng)絡資料整理，出于傳遞更多信息之目的，不代表金鑰匙跨境贊同其觀點和立場。
轉載請注明，如有侵權，聯(lián)系刪除。
Voghion時尚行
