[C++歷練之路]優先級隊列||反向迭代器的模擬實現

W...Y的主頁 😊?

代碼倉庫分享💕

🍔前言：
在C++的宇宙中，優先隊列似乎是一座巨大的寶庫，藏匿著算法的珍寶。而就在這片代碼的天空下，我們不僅可以探索優先隊列的神奇，還能夠揭開反向迭代器的神秘面紗。讓我們一同踏入這個編程的探險之旅，在這里，我們將用C++語言創造出一個能按照優先級排列元素的神奇容器，并且探索反向迭代器的魅力，仿佛是在編碼的星空下追逐著閃爍的代碼流星。準備好了嗎？讓我們邁出第一步，開啟這段驚險又充滿奇跡的模擬之旅。

了解priority_queue

模擬實現priority_queue

構建基本框架

仿函數的介紹以及第三個參數添加

反向迭代器的模板實現

了解priority_queue

1. 優先隊列是一種容器適配器，根據嚴格的弱排序標準，它的第一個元素總是它所包含的元素中最大的。
2. 此上下文類似于堆，在堆中可以隨時插入元素，并且只能檢索最大堆元素(優先隊列中位于頂部的元素)。
3. 優先隊列被實現為容器適配器，容器適配器即將特定容器類封裝作為其底層容器類，queue提供一組特定的成員函數來訪問其元素。元素從特定容器的“尾部”彈出，其稱為優先隊列的頂部。
4. 底層容器可以是任何標準容器類模板，也可以是其他特定設計的容器類。容器應該可以通過隨機訪問迭代器訪問，并支持以下操作：
empty()：檢測容器是否為空
size()：返回容器中有效元素個數
front()：返回容器中第一個元素的引用
push_back()：在容器尾部插入元素

op_back()：刪除容器尾部元素
5. 標準容器類vector和deque滿足這些需求。默認情況下，如果沒有為特定的priority_queue類實例化指定容器類，則使用vector。
6. 需要支持隨機訪問迭代器，以便始終在內部保持堆結構。容器適配器通過在需要時自動調用算法函數make_heap、push_heap和pop_heap來自動完成此操作。

?優先隊列其實就是數據結構中的堆，而我們想要進行其實現必須掌握其模板。

默認情況下，priority_queue是大堆，而第一個模板參數class T就是其對應的數據類型，第二個模板參數是其數據結構的類型，缺省值為vector，所以其默認的結構類型就是數組，不是鏈式結構類型的堆，如果在priority_queue中放自定義類型的數據，用戶需要在自定義類型中提供> 或者< 的重載。第三個模板類型就是一種仿函數，其可以操控其創建的是大堆還是小堆。

所以我們要用堆的思想來模擬實現優先隊列！

模擬實現priority_queue

構建基本框架

首先我們可以照貓畫虎，仿照其參數模板進行仿寫：

#pragma once
#include<vector>
#include<iostream>
#include<vector>
#include<deque>
#include<stdbool.h>
using namespace std;
namespace why
{template<class T, class Container = vector<T>>class priority_queue{public:void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}T& top(){return _con[0];}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};

我們將基本函數框架打好，將優先隊列的基本函數接口完善，這些都是我們復用的vector、list、deque等接口，可以直接從STL中直接調用。?

注意：這里我們在函數模板中未加入第三個參數進行參數，這里我們在最后實現。原模板接口的缺省默認參數為less<T>，是構建大堆的，所以我們模擬中是先建立大堆。、

往vector中push數據時就要建立大堆進行排序，pop數據得使用向下調整對堆中的數據重新排序成為大堆，所以建立大堆就是使用數據結構中的向上調整函數進行操作，而pop數據是用向下調整的方法進行。

如果對堆這一塊的不太了解，可以一下文章：

堆的基本實現——數據結構https://blog.csdn.net/m0_74755811/article/details/132794715?spm=1001.2014.3001.5502向上調整：

void adjust_up(size_t child)
{//Compare com;size_t parent = (child - 1) / 2;while (child > 0){if (_con[child] > _con[parent])//if (com(_con[parent],_con[child])){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}

向下調整：

void adjust_down(size_t parent)
{//Compare com;size_t child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && _con[child] < _con[child + 1])//if(child + 1 < _con.size() && com(_con[child], _con[child + 1])){child++;}if(_con[child] > _con[parent])//if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

仿函數的介紹以及第三個參數添加

在C++中，仿函數（Functor）是一種重載了函數調用操作符 operator() 的對象。它實際上是一個類或者結構體，通過重載 operator()，使得該對象可以像函數一樣被調用。仿函數可以像函數一樣接受參數，并返回結果，同時可以包含狀態信息，因此它們在C++中被廣泛用于實現函數對象，作為算法的參數傳遞，或者用于定義自定義的操作。

通過仿函數，可以實現自定義的比較、排序、轉換或者其他操作，這些操作可以被算法直接使用，例如在標準庫中的排序算法 std::sort、查找算法 std::find，或者容器類中的自定義排序規則等。使用仿函數可以提供更大的靈活性，使得算法能夠適應不同的需求。

下面是一個簡單的示例，展示了一個自定義的仿函數用于比較兩個整數的大小：

#include <iostream>// 定義一個比較器仿函數
struct Compare {bool operator()(int a, int b) const {return a < b; // 自定義的比較規則：a < b}
};int main() {Compare cmp; // 創建比較器對象int x = 5, y = 10;if (cmp(x, y)) {std::cout << "x is less than y." << std::endl;} else {std::cout << "x is greater than or equal to y." << std::endl;}return 0;
}

在這個示例中，Compare 結構體重載了 operator()，定義了一個比較規則，判斷第一個參數是否小于第二個參數。然后在 main 函數中，創建了一個 Compare 類型的對象 cmp，并使用它進行比較操作。

因此，仿函數是C++中的一種強大機制，可以擴展函數的行為，提供更靈活的功能，并允許開發者以更抽象的方式定義特定操作。

所以我們可以使用仿函數針對第三個參數。

priority_queue函數的第三個默認缺省參數為less<T>，如果我們傳greater<T>才可以創建小堆。而我們模擬的函數中創建大小堆只不過是將其比較符號進行轉換即可。所以我們就可以使用仿函數創建兩個不同類型的進行調用。

#pragma once
#include<vector>
#include<iostream>
#include<vector>
#include<deque>
#include<stdbool.h>
using namespace std;
namespace why
{template<class T>struct less{bool operator()(const T& x, const T& y){return x < y;}};template<class T>struct greater{bool operator()(const T& x, const T& y){return x > y;}};template<class T, class Container = vector<T>, class Compare = less<T>>class priority_queue{public:void adjust_up(size_t child){Compare com;size_t parent = (child - 1) / 2;while (child > 0){//if (_con[child] > _con[parent])if (com(_con[parent],_con[child])){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void adjust_down(size_t parent){Compare com;size_t child = parent * 2 + 1;while (child < _con.size()){//if (child + 1 < _con.size() && _con[child] < _con[child + 1])if(child + 1 < _con.size() && com(_con[child], _con[child + 1])){child++;}//if(_con[child] > _con[parent])if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}T& top(){return _con[0];}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};

這樣我們只需要在模擬函數中創建一個模板變量即可在函數中進行調用。

反向迭代器的模板實現

在STL中的所有容器里都有迭代器與反向迭代器，而在每個容器的模擬實現中我們也將其進行復現。string、vector中的迭代器都可以類似與指針，因為其底層的存儲物理空間是連續的，我們可以很好的進行重定義使用。但是list卻不行，因為空間是不連續的，所以我們得重新定義封裝出一個類迭代器的重定義，將其運算符進行重載成合理的進行使用。

而反向迭代器中我們可以將list中封裝的迭代器進行復制粘貼修改，就可以正確使用。

rend指向頭節點，而rbegin指向_head->_prev節點，也就是尾節點即可。?

template<class T, class Ref, class Ptr>
struct __list_reverse_iterator
{typedef list_node<T> node;typedef __list_reverse_iterator<T, Ref, Ptr> self;node* _node;__list_reverse_iterator(node* n):_node(n){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}self& operator++(){_node = _node->_prev;return *this;}self operator++(int){self tmp(*this);_node = _node->_prev;return tmp;}self& operator--(){_node = _node->_next;return *this;}self operator--(int){self tmp(*this);_node = _node->_next;return tmp;}bool operator!=(const self& s){return _node != s._node;}bool operator==(const self& s){return _node == s._node;}
};

我們只需要將++、--運算符進行重載即可。將++指向當前節點的_prev節點，而--指向當前節點的_next節點。

那我們看一下STL-list中的反向迭代器是怎么寫的：

class reverse_bidirectional_iterator {typedef reverse_bidirectional_iterator<_BidirectionalIterator, _Tp, _Reference, _Distance>  _Self;
protected:_BidirectionalIterator current;
public:typedef bidirectional_iterator_tag iterator_category;typedef _Tp                        value_type;typedef _Distance                  difference_type;typedef _Tp*                       pointer;typedef _Reference                 reference;reverse_bidirectional_iterator() {}explicit reverse_bidirectional_iterator(_BidirectionalIterator __x): current(__x) {}_BidirectionalIterator base() const { return current; }_Reference operator*() const {_BidirectionalIterator __tmp = current;return *--__tmp;}
#ifndef __SGI_STL_NO_ARROW_OPERATORpointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */_Self& operator++() {--current;return *this;}_Self operator++(int) {_Self __tmp = *this;--current;return __tmp;}_Self& operator--() {++current;return *this;}_Self operator--(int) {_Self __tmp = *this;++current;return __tmp;}
};

STL中的反向迭代器是封裝了正向迭代器，構造一個反向迭代器了。正向迭代器的++就是反向迭代器的--，而正向迭代器的--就是反向迭代器的++。

注意：STL源碼中的復用代碼rbegin()與rend()的源碼為：

直接返回的是其正向迭代器的begin()與end()，所以其解引用的內容就要發生變化：

其結構就不同：

與原來的結構是不同的。

我們可以自己封裝一個類進行使用：

#pragma once
namespace why
{template<class Iterator, class Ref>struct ReverseIterator{typedef ReverseIterator<Iterator, Ref> Self;Iterator _cur;ReverseIterator(Iterator it):_cur(it){}Ref operator*(){Iterator tmp = _cur;--tmp;return *tmp;}Self& operator++(){--_cur;return *this;}Self& operator--(){++_cur;return *this;}bool operator!=(const Self& s){return _cur != s._cur;}};
}

?但是這樣復用正向迭代器與剛才的寫法所表達的寫法是一樣的，為什么還要這樣單獨創建一個類呢？因為list的正向迭代器就是進行封裝的，可以復用。但是string、vector的正向迭代器就是指針就不能進行此操作了，所以我們必須復用。

總結：

在這段代碼的奇妙旅程中，我們成功地創造了一個C++中的優先隊列，仿佛編織了一個可以按照優先級排序元素的魔法網。這個隊列不僅僅是一段代碼，更是算法的交響樂，奏響著排序、插入、刪除的優美旋律。而更加令人驚嘆的是，我們在這個編碼的仙境中，還揭開了反向迭代器的神秘面紗，為我們的容器增添了一抹獨特的色彩。

通過這個模擬實現，我們深入理解了C++中優先隊列的本質，并感受到了反向迭代器的便利之處。這不僅是一次代碼之旅，更是對數據結構和算法的深刻思考，是對編程藝術的一次追求和探索。

或許，在未來的編程征途中，你會在實際項目中運用這些知識，創造出更為強大、高效的代碼。無論何時何地，優先隊列和反向迭代器的魔法都將伴隨著你，成為解決問題的得力工具。

讓我們懷著對編碼奇跡的敬畏之心，結束這段代碼的冒險。愿你的代碼之路充滿創造與探索，愿你的算法之舞永遠翩翩起舞。編碼的世界里，冒險永不止步，期待著你下一次的代碼奇跡。