C++中priority_queue與仿函數(shù)實(shí)現(xiàn)方法
1 priority_queue 介紹
p r i o i r t prioirt prioirt_ q u e u e queue queue 文檔介紹
- 優(yōu)先級(jí)隊(duì)列是一種
容器適配器，根據(jù)嚴(yán)格的弱排序標(biāo)準(zhǔn)，它的第一個(gè)元素總是它所包含的元素中最大(或最小)的 - 此上下文類似于堆，在堆中可以隨時(shí)插入元素，并且只能檢索最大堆元素（優(yōu)先隊(duì)列中位于定部的元素）
- 優(yōu)先隊(duì)列被實(shí)現(xiàn)為
容器適配器，容器適配器即將特定容器類封裝作為其底層容器類， q u e u e queue queue 提供一組特定的成員函數(shù)來訪問其元素。元素從特定容器的"尾部"彈出，其稱為優(yōu)先隊(duì)列的頂部。 - 底層容器可以是任何標(biāo)準(zhǔn)容器類模板，也可以是其他特定設(shè)計(jì)的容器類。容器應(yīng)該可以通過隨機(jī)訪問迭代器訪問，并支持以下操作：
| 函數(shù)名 | 檢測(cè)容器是否為空 |
|---|---|
| e m p t y empty empty() | 檢測(cè)容器是否為空 |
| s i z e size size() | 返回容器中有效元素個(gè)數(shù) |
| f r o n t front front() | 返回容器中第一個(gè)元素的引用 |
| p u s h push push_ b a c k back back() | 在容器尾部插入數(shù)據(jù) |
| p o p pop pop_ b a c k back back() | 刪除容器尾部元素 |
- 標(biāo)準(zhǔn)容器類 v e c t o r vector vector 和 d e q u e deque deque 滿足這些需求。默認(rèn)情況下，如果沒有為特定的 p r i o r i t y priority priority_ q u e u e queue queue 類實(shí)例化特定容器類，則使用
vector 需要支持隨機(jī)訪問的迭代器，以便始終在內(nèi)部保存堆結(jié)構(gòu)。容器適配器通過在需要時(shí)自動(dòng)調(diào)用算法函數(shù)make_heap、push_heap和pop_heap來自動(dòng)完成此操作
2 priority_queue 的使用
2.1 priority_queue 的函數(shù)接口
優(yōu)先級(jí)隊(duì)列默認(rèn)使用 v e c t o r vector vector 作為其底層存儲(chǔ)數(shù)據(jù)的容器，在 v e c t o r vector vector 上又使用了堆算法將 v e c t o r vector vector 中元素構(gòu)成堆的結(jié)構(gòu)，因此 p r i o r i t y priority priority_ q u e u e queue queue 就是 堆，所有需要用到堆的地方，都可以考慮使用 p r i o r i t y priority priority_ q u e u e queue queue。
注意：默認(rèn)情況下 p r i o r i t y priority priority _ q u e u e queue queue 是大堆
| 函數(shù)聲明 | 接口說明 |
|---|---|
| p r i o r i t y priority priority_ q u e u e queue queue() | 構(gòu)造一個(gè)空的優(yōu)先級(jí)隊(duì)列 |
| e m p t y empty empty() | 檢測(cè)優(yōu)先級(jí)隊(duì)列是否為空，是返回 t r u e true true，否則返回 f a l s e false false |
| t o p top top() | 返回優(yōu)先級(jí)隊(duì)列中最大（最?。┰?，即堆定元素 |
| p u s h push push( x x x) | 在優(yōu)先級(jí)隊(duì)列中插入元素 x x x |
| p o p pop pop() | 刪除優(yōu)先級(jí)隊(duì)列中最大(最小)元素，即堆頂元素 |
2.2 priority_queue 的使用
優(yōu)先級(jí)隊(duì)列一個(gè)有三個(gè)模板參數(shù)：class T、class Container = vector<T>、class Compare = less<typename Container::value_type> 第一個(gè)參數(shù)是確定優(yōu)先級(jí)隊(duì)列的存儲(chǔ)類型；第二個(gè)參數(shù)確定 p r i o r i t y priority priority_ q u e u e queue queue 底層容器的結(jié)構(gòu)，默認(rèn)為 v e c t o r vector vector，priority_queue也是一種適配器模式；第三個(gè)參數(shù)確定是建大堆還是小堆，默認(rèn)是大堆，建立小堆的話要自己傳遞一個(gè)仿函數(shù)。
我們來簡(jiǎn)單使用一下 p r i o r i t y priority priority_ q u e u e queue queue
void test1()
{
priority_queue<int> pq;
pq.push(4);
pq.push(1);
pq.push(5);
pq.push(7);
pq.push(9);
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
cout << endl;
}
運(yùn)行結(jié)果：
我們?cè)賮碓囋囆《?/p>
void test2()
{
priority_queue<int, vector<int>, greater<int>> pq;
pq.push(4);
pq.push(1);
pq.push(5);
pq.push(7);
pq.push(9);
cout << " ";
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
cout << endl;
}
但第三個(gè)模板參數(shù)class Compare = less<typename Container::value_type> 是什么東西呢？為什么傳 g r e a t e r < i n t > greater<int> greater<int> 就從大堆變小堆了呢？這其實(shí)是一個(gè)仿函數(shù)，我們慢慢來介紹。
3 仿函數(shù)
3.1 什么是仿函數(shù)
什么是仿函數(shù)呢？仿函數(shù)本質(zhì)是一個(gè) 類 ！它里面重載了 o p e r a t o r operator operator() 函數(shù)（即函數(shù)調(diào)用操作符：func()中的()）。
比如現(xiàn)在我想寫兩個(gè)整型的比較的仿函數(shù)，可以怎么寫呢？
class Less
{
public:
bool operator()(int x, int y)
{
return x < y;
}
};
可以看到它沒有成員變量；其實(shí)仿函數(shù)大部分都是空類 ，都是沒有成員變量的
我們將其改造一下就成了模板，可以支持多種類型的比較。但并不是說仿函數(shù)就是模板，仿函數(shù)類指的是它重載了 o p e r a t o r ( ) operator() operator() 函數(shù)的類
template<class T>
class Less
{
public:
bool operator()(const T& x, const T& y)
{
return x < y;
}
};
那我們又如何調(diào)用呢？如下：
int main()
{
Less<int> LessFunc;
cout << LessFunc(1, 2) << endl;
return 0
}
按照我們以前的理解，LessFunc(1, 2)是個(gè)函數(shù)調(diào)用，LessFunc是一個(gè)函數(shù)名或函數(shù)指針。但現(xiàn)在，它一個(gè)對(duì)象。
仿函數(shù)本質(zhì)是一個(gè)類，這個(gè)類重載 o p e r a t o r ( ) operator() operator()，它的對(duì)象可以像函數(shù)一樣使用 LessFunc本質(zhì)是調(diào)用了 o p e r a t o r ( ) operator() operator()
cout << LessFunc(1, 2) << endl; cout << LessFunc.operator()(1, 2) << endl;
同樣，我們還可以實(shí)現(xiàn)一個(gè) g r e a t e r greater greater 的仿函數(shù)
template<class T>
class Greater
{
public:
bool operator()(const T& x, const T& y)
{
return x > y;
}
};
3.2 仿函數(shù)的應(yīng)用
那 p r i o r i t y priority priority_ q u e u e queue queue 為什么要仿函數(shù)作為模板參數(shù)呢？
我們知道堆的插入，是要調(diào)用向上調(diào)整算法的
template<class T, class Container = vector<T>>
class priority_queue
{
public:
void AdjustUp(int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (_con[parent] < _con[child])
{
swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
break;
}
}
private:
Container _con;
};
上述實(shí)現(xiàn)的向上調(diào)整算法，判斷條件是if (_con[parent] < _con[child])建的是大堆，那如果我想建小堆怎么辦？自己手動(dòng)改代碼嗎？那也太離譜了吧。
這時(shí)，仿函數(shù)的作用就出來了。
我們?cè)僭黾右粋€(gè)模板參數(shù)： C o m p a r e Compare Compare， C o m p a r e Compare Compare 是一個(gè)類型，傳遞一個(gè)仿函數(shù)。我們還可以給一個(gè)缺省值
template<class T, class Container = vector<T>, class Compare = Less<T>>
這時(shí)，我們就可以將比較邏輯寫成泛型
if (Compare(_con[parent], _con[child]))
如果我們想建大堆，比較邏輯是 < ，傳遞 Less<T> 類型；反之傳遞 Greater<T> 類型。（庫(kù)中是 l e s s less less<T> 和 g r e a t e r greater greater<T>）
int main()
{
Priority_queue<int, vector<int>, Less<int>> p3;
Priority_queue<int, vector<int>, Greater<int>> p4;
return 0;
}
注：模板模板實(shí)例化時(shí)傳遞的是類型，而函數(shù)模板傳參時(shí)需要傳的是對(duì)象
如：寫一個(gè)向上調(diào)整算法的函數(shù)模板
template<class Compare>
void AdjustUp(int* a, int child, Compare com)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (com(a[child], a[parent]))
{
swap(a[child], a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
int main()
{
int a[] = { 1 };
Less<int> LessFunc;
AdjustUp(a, 1, LessFunc);//傳遞有名對(duì)象
AdjustUp(a, 1, Less<int>());//傳遞匿名對(duì)象
return 0;
}
4 需自己寫仿函數(shù)的情況
庫(kù)中是幫我們實(shí)現(xiàn)了仿函數(shù) l e s s less less 和 g r e a t e r greater greater 的，也就是說一般情況下我們是不用自己實(shí)現(xiàn)仿函數(shù)，這直接調(diào)用庫(kù)里的就好了
less
greater
但有些情況時(shí)需要我們自己寫的。
4.1 類類型不支持比較大小
class Date
{
public :
Date(int year = 1900, int month = 1, int day = 1)
: _year(year)
, _month(month)
, _day(day)
{}
private:
int _year;
int _month;
int _day;
};
int main()
{
priority_queue<Date> q1;
q1.push(Date(2018, 10, 29));
q1.push(Date(2018, 10, 28));
q1.push(Date(2018, 10, 30));
return 0;
}
D a t e Date Date類 中并沒有重載 o p e r a t o r operator operator< 和 o p e r a t o r operator operator> 的函數(shù)，編譯就會(huì)報(bào)錯(cuò)
這時(shí)，就需要我們自己實(shí)現(xiàn) l e s s less less 和 g r e a t e r greater greater 仿函數(shù)
4.2 類中支持的比較方式不是我們想要的
class Date
{
public :
Date(int year = 1900, int month = 1, int day = 1)
: _year(year)
, _month(month)
, _day(day)
{}
bool operator<(const Date& d)const
{
return (_year < d._year) ||
(_year == d._year && _month < d._month) ||
(_year == d._year && _month == d._month && _day < d._day);
}
bool operator>(const Date& d)const
{
return (_year > d._year) ||
(_year == d._year && _month > d._month) ||
(_year == d._year && _month == d._month && _day > d._day);
}
private:
int _year;
int _month;
int _day;
};
現(xiàn)在 D a t e Date Date類 中支持了比較方式，但如果我們這樣傳參呢？
int main()
{
priority_queue<Date*> q1;
q1.push(new Date(2018, 10, 29));
q1.push(new Date(2018, 10, 28));
q1.push(new Date(2018, 10, 30));
cout << *q1.top() << endl;
q1.pop();
cout << *q1.top() << endl;
q1.pop();
cout << *q1.top() << endl;
q1.pop();
return 0;
}
你會(huì)發(fā)現(xiàn)，每次的結(jié)果都不一樣，我們控制不住。這時(shí)因?yàn)槲覀儌鬟f的是指針，它是按指針大小來比較
這時(shí)就需要我們自己實(shí)現(xiàn)仿函數(shù)
class DateLess
{
bool operator()(Date* p1, Date* p2)
{
return *p1 < *p2;
}
};
5 priority_queue 的模擬實(shí)現(xiàn)
namespace my_priority_queue
{
template <class T, class Container = vector<T>, class Compare = less<T> >
class priority_queue
{
public:
template <class InputIterator>
priority_queue(InputIterator first, InputIterator last)
{
InputIterator it = first;
while (it != last)
{
push(*it);
++it;
}
}
priority_queue() {}
bool empty() const
{
return _c.empty();
}
size_t size() const
{
return _c.size();
}
const T& top() const
{
return _c.front();
}
T& top()
{
return _c.front();
}
void push(const T& x)
{
_c.push_back(x);
AdjustUp(size() - 1);
}
void AdjustUp(int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (_comp(_c[parent], _c[child]))
{
swap(_c[parent], _c[child]);
child = parent;
parent = (child - 1) / 2;
}
else
break;
}
}
void AdjustDown(int parent, int end)
{
int child = parent * 2 + 1;
while (child <= end)
{
if (child + 1 <= end && _comp(_c[child], _c[child + 1]))
++child;
if (_comp(_c[parent], _c[child]))
{
std::swap(_c[parent], _c[child]);
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}
void pop()
{
assert(!empty());
std::swap(_c[0], _c[size() - 1]);
_c.pop_back();
AdjustDown(0, size() - 1);
}
private:
Container _c;
Compare _comp;
};
}
總結(jié)
到此這篇關(guān)于C++中priority_queue與仿函數(shù)實(shí)現(xiàn)方法的文章就介紹到這了,更多相關(guān)C++ priority_queue與仿函數(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
FFmpeg中的libavfilter模塊(或庫(kù))用于filter(過濾器),?filter可以有多個(gè)輸入和多個(gè)輸出,下面就跟隨小編一起簡(jiǎn)單學(xué)習(xí)一下它的巨日使用吧2023-08-08
這篇文章主要介紹了C語(yǔ)言怎么獲得進(jìn)程的PE文件信息的相關(guān)代碼,需要的朋友可以參考下2016-01-01
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言掃雷游戲的實(shí)現(xiàn)代碼，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-11-11
Qt提供了QDomElement 類用于完成對(duì)xml文件的讀取和寫入,這篇文章主要給大家介紹了關(guān)于C++、Qt分別讀寫xml文件的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2023-03-03
這篇文章主要介紹了C語(yǔ)言關(guān)鍵字union的定義和使用詳解,本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-02-02
這篇文章主要介紹了實(shí)現(xiàn)去除c語(yǔ)言注釋的小工具，說是C語(yǔ)言，但其實(shí)所有C語(yǔ)系的都可以，比如Java,需要的朋友可以參考下2014-02-02
C++的get()函數(shù)與getline()函數(shù)使用詳解
這篇文章主要介紹了C++的get()函數(shù)與getline()函數(shù)使用詳解,是C++入門學(xué)習(xí)中的基礎(chǔ)知識(shí),需要的朋友可以參考下2015-09-09
VScode搭建OpenCV環(huán)境的詳細(xì)步驟
用vscode來寫opencv代碼需要自己編譯OpenCV，主要用到MinGW-w64和CMake工具。接下來通過本文給大家介紹VScode搭建OpenCV環(huán)境的相關(guān)知識(shí),需要的朋友可以參考下2021-11-11
C++實(shí)現(xiàn)簡(jiǎn)單插件機(jī)制原理解析
這篇文章主要介紹了C++實(shí)現(xiàn)簡(jiǎn)單插件機(jī)制原理解析,本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-02-02
一起來學(xué)習(xí)C++的構(gòu)造和析構(gòu)
這篇文章主要為大家詳細(xì)介紹了C++構(gòu)造和析構(gòu)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-03-03