W...Y的主頁(yè) ???

代碼倉(cāng)庫(kù)分享??

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

目錄

了解priority_queue

模擬實(shí)現(xiàn)priority_queue

構(gòu)建基本框架

仿函數(shù)的介紹以及第三個(gè)參數(shù)添加

反向迭代器的模板實(shí)現(xiàn)

了解priority_queue

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

op_back()：刪除容器尾部元素
5. 標(biāo)準(zhǔn)容器類vector和deque滿足這些需求。默認(rèn)情況下，如果沒(méi)有為特定的priority_queue類實(shí)例化指定容器類，則使用vector。
6. 需要支持隨機(jī)訪問(wèn)迭代器，以便始終在內(nèi)部保持堆結(jié)構(gòu)。容器適配器通過(guò)在需要時(shí)自動(dòng)調(diào)用算法函數(shù)make_heap、push_heap和pop_heap來(lái)自動(dòng)完成此操作。

?優(yōu)先隊(duì)列其實(shí)就是數(shù)據(jù)結(jié)構(gòu)中的堆，而我們想要進(jìn)行其實(shí)現(xiàn)必須掌握其模板。

默認(rèn)情況下，priority_queue是大堆，而第一個(gè)模板參數(shù)class T就是其對(duì)應(yīng)的數(shù)據(jù)類型，第二個(gè)模板參數(shù)是其數(shù)據(jù)結(jié)構(gòu)的類型，缺省值為vector，所以其默認(rèn)的結(jié)構(gòu)類型就是數(shù)組，不是鏈?zhǔn)浇Y(jié)構(gòu)類型的堆，如果在priority_queue中放自定義類型的數(shù)據(jù)，用戶需要在自定義類型中提供> 或者< 的重載。第三個(gè)模板類型就是一種仿函數(shù)，其可以操控其創(chuàng)建的是大堆還是小堆。

所以我們要用堆的思想來(lái)模擬實(shí)現(xiàn)優(yōu)先隊(duì)列！

模擬實(shí)現(xiàn)priority_queue

構(gòu)建基本框架

首先我們可以照貓畫(huà)虎，仿照其參數(shù)模板進(jìn)行仿寫(xiě)：

#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;
	};

我們將基本函數(shù)框架打好，將優(yōu)先隊(duì)列的基本函數(shù)接口完善，這些都是我們復(fù)用的vector、list、deque等接口，可以直接從STL中直接調(diào)用。?

注意：這里我們?cè)诤瘮?shù)模板中未加入第三個(gè)參數(shù)進(jìn)行參數(shù)，這里我們?cè)谧詈髮?shí)現(xiàn)。原模板接口的缺省默認(rèn)參數(shù)為less<T>，是構(gòu)建大堆的，所以我們模擬中是先建立大堆。、

往vector中push數(shù)據(jù)時(shí)就要建立大堆進(jìn)行排序，pop數(shù)據(jù)得使用向下調(diào)整對(duì)堆中的數(shù)據(jù)重新排序成為大堆，所以建立大堆就是使用數(shù)據(jù)結(jié)構(gòu)中的向上調(diào)整函數(shù)進(jìn)行操作，而pop數(shù)據(jù)是用向下調(diào)整的方法進(jìn)行。

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

堆的基本實(shí)現(xiàn)——數(shù)據(jù)結(jié)構(gòu)https://blog.csdn.net/m0_74755811/article/details/132794715?spm=1001.2014.3001.5502向上調(diào)整：

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;
		}
	}
}

向下調(diào)整：

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;
		}
	}
}

仿函數(shù)的介紹以及第三個(gè)參數(shù)添加

在C++中，仿函數(shù)（Functor）是一種重載了函數(shù)調(diào)用操作符 operator() 的對(duì)象。它實(shí)際上是一個(gè)類或者結(jié)構(gòu)體，通過(guò)重載 operator()，使得該對(duì)象可以像函數(shù)一樣被調(diào)用。仿函數(shù)可以像函數(shù)一樣接受參數(shù)，并返回結(jié)果，同時(shí)可以包含狀態(tài)信息，因此它們?cè)贑++中被廣泛用于實(shí)現(xiàn)函數(shù)對(duì)象，作為算法的參數(shù)傳遞，或者用于定義自定義的操作。

通過(guò)仿函數(shù)，可以實(shí)現(xiàn)自定義的比較、排序、轉(zhuǎn)換或者其他操作，這些操作可以被算法直接使用，例如在標(biāo)準(zhǔn)庫(kù)中的排序算法 std::sort、查找算法 std::find，或者容器類中的自定義排序規(guī)則等。使用仿函數(shù)可以提供更大的靈活性，使得算法能夠適應(yīng)不同的需求。

下面是一個(gè)簡(jiǎn)單的示例，展示了一個(gè)自定義的仿函數(shù)用于比較兩個(gè)整數(shù)的大?。?/p>

#include <iostream>

// 定義一個(gè)比較器仿函數(shù)
struct Compare {
    bool operator()(int a, int b) const {
        return a < b; // 自定義的比較規(guī)則：a < b
    }
};

int main() {
    Compare cmp; // 創(chuàng)建比較器對(duì)象

    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;
}

在這個(gè)示例中，Compare 結(jié)構(gòu)體重載了 operator()，定義了一個(gè)比較規(guī)則，判斷第一個(gè)參數(shù)是否小于第二個(gè)參數(shù)。然后在 main 函數(shù)中，創(chuàng)建了一個(gè) Compare 類型的對(duì)象 cmp，并使用它進(jìn)行比較操作。

因此，仿函數(shù)是C++中的一種強(qiáng)大機(jī)制，可以擴(kuò)展函數(shù)的行為，提供更靈活的功能，并允許開(kāi)發(fā)者以更抽象的方式定義特定操作。

所以我們可以使用仿函數(shù)針對(duì)第三個(gè)參數(shù)。

priority_queue函數(shù)的第三個(gè)默認(rèn)缺省參數(shù)為less<T>，如果我們傳greater<T>才可以創(chuàng)建小堆。而我們模擬的函數(shù)中創(chuàng)建大小堆只不過(guò)是將其比較符號(hào)進(jìn)行轉(zhuǎn)換即可。所以我們就可以使用仿函數(shù)創(chuàng)建兩個(gè)不同類型的進(jìn)行調(diào)用。

#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;
	};

這樣我們只需要在模擬函數(shù)中創(chuàng)建一個(gè)模板變量即可在函數(shù)中進(jìn)行調(diào)用。

反向迭代器的模板實(shí)現(xiàn)

在STL中的所有容器里都有迭代器與反向迭代器，而在每個(gè)容器的模擬實(shí)現(xiàn)中我們也將其進(jìn)行復(fù)現(xiàn)。string、vector中的迭代器都可以類似與指針，因?yàn)槠涞讓拥拇鎯?chǔ)物理空間是連續(xù)的，我們可以很好的進(jìn)行重定義使用。但是list卻不行，因?yàn)榭臻g是不連續(xù)的，所以我們得重新定義封裝出一個(gè)類迭代器的重定義，將其運(yùn)算符進(jìn)行重載成合理的進(jìn)行使用。

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

rend指向頭節(jié)點(diǎn)，而rbegin指向_head->_prev節(jié)點(diǎn)，也就是尾節(jié)點(diǎn)即可。?

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;
	}
};

我們只需要將++、--運(yùn)算符進(jìn)行重載即可。將++指向當(dāng)前節(jié)點(diǎn)的_prev節(jié)點(diǎn)，而--指向當(dāng)前節(jié)點(diǎn)的_next節(jié)點(diǎn)。

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

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_OPERATOR
  pointer 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中的反向迭代器是封裝了正向迭代器，構(gòu)造一個(gè)反向迭代器了。正向迭代器的++就是反向迭代器的--，而正向迭代器的--就是反向迭代器的++。

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

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

其結(jié)構(gòu)就不同：

與原來(lái)的結(jié)構(gòu)是不同的。

我們可以自己封裝一個(gè)類進(jìn)行使用：

#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;
		}
	};
}

?但是這樣復(fù)用正向迭代器與剛才的寫(xiě)法所表達(dá)的寫(xiě)法是一樣的，為什么還要這樣單獨(dú)創(chuàng)建一個(gè)類呢？因?yàn)閘ist的正向迭代器就是進(jìn)行封裝的，可以復(fù)用。但是string、vector的正向迭代器就是指針就不能進(jìn)行此操作了，所以我們必須復(fù)用。

總結(jié)：

在這段代碼的奇妙旅程中，我們成功地創(chuàng)造了一個(gè)C++中的優(yōu)先隊(duì)列，仿佛編織了一個(gè)可以按照優(yōu)先級(jí)排序元素的魔法網(wǎng)。這個(gè)隊(duì)列不僅僅是一段代碼，更是算法的交響樂(lè)，奏響著排序、插入、刪除的優(yōu)美旋律。而更加令人驚嘆的是，我們?cè)谶@個(gè)編碼的仙境中，還揭開(kāi)了反向迭代器的神秘面紗，為我們的容器增添了一抹獨(dú)特的色彩。

通過(guò)這個(gè)模擬實(shí)現(xiàn)，我們深入理解了C++中優(yōu)先隊(duì)列的本質(zhì)，并感受到了反向迭代器的便利之處。這不僅是一次代碼之旅，更是對(duì)數(shù)據(jù)結(jié)構(gòu)和算法的深刻思考，是對(duì)編程藝術(shù)的一次追求和探索。

或許，在未來(lái)的編程征途中，你會(huì)在實(shí)際項(xiàng)目中運(yùn)用這些知識(shí)，創(chuàng)造出更為強(qiáng)大、高效的代碼。無(wú)論何時(shí)何地，優(yōu)先隊(duì)列和反向迭代器的魔法都將伴隨著你，成為解決問(wèn)題的得力工具。

讓我們懷著對(duì)編碼奇跡的敬畏之心，結(jié)束這段代碼的冒險(xiǎn)。愿你的代碼之路充滿創(chuàng)造與探索，愿你的算法之舞永遠(yuǎn)翩翩起舞。編碼的世界里，冒險(xiǎn)永不止步，期待著你下一次的代碼奇跡。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-755976.html

到了這里，關(guān)于[C++歷練之路]優(yōu)先級(jí)隊(duì)列||反向迭代器的模擬實(shí)現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！