一、priority_queue的介紹

priority_queue官方文檔介紹

翻譯：

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

empty()：檢測(cè)容器是否為空。

size()：返回容器中有效元素個(gè)數(shù)。

front()：返回容器中第一個(gè)元素的引用。

push_back()：在容器尾部插入元素。

pop_back()：刪除容器尾部元素。

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

二、priority_queue的使用

優(yōu)先級(jí)隊(duì)列默認(rèn)使用vector作為其底層存儲(chǔ)數(shù)據(jù)的容器，在vector上又使用了堆算法（堆的創(chuàng)建與應(yīng)用）將vector中元素構(gòu)造成堆的結(jié)構(gòu)，因此priority_queue就是堆，所有需要用到堆的位置，都可以考慮使用priority_queue。注意:默認(rèn)情況下priority_queue是大堆。

??????：常用的函數(shù)接口

• priority_queue()/priority_queue(first,last),構(gòu)造優(yōu)先級(jí)隊(duì)列。
• empty()，檢測(cè)優(yōu)先級(jí)隊(duì)列是否為空，若是返回True。
• top()，返回優(yōu)先級(jí)隊(duì)列中最大（最?。┰兀炊秧斣?。
• push()，在優(yōu)先級(jí)隊(duì)列中插入元素。
• pop()，刪除優(yōu)先級(jí)隊(duì)列中最大（最?。┰?，即堆頂元素。

下面我們就舉一個(gè)例子:

存放自定義類型，這樣更具代表性！

template<class T>
class greater
{
public:
	bool operator()(const T& p1, const T& p2) const
	{
		return p1 > p2;
	}
};
struct person
{
	person(string name = "", int age = -1)
		:_name(name)
		, _age(age)
	{}
	bool operator<(const person& p) const
	{
		return _age < p._age;
	}
	bool operator>(const person& p) const
	{
		return _age > p._age;
	}
	string _name;
	int _age;
};
ostream& operator<<(ostream& out, const person& p)
{
	out << "name:" << p._name << "   " << "age:" << p._age << endl;
	return out;
}
void test02()
{
	person arr[] = { { "pxl", 23 },
					 { "dyx", 21 }, 
					 { "wjz", 24 }, 
					 { "ztd", 20 } };
	priority_queue<person, vector<person>, greater<person>> pq(arr, arr + sizeof(arr) / sizeof(arr[0]));//小堆
	pq.push(person("yzc", 22));
	cout <<"堆頂元素是："<< pq.top() << endl;
	while (!pq.empty())
	{
		cout << pq.top() << endl;
		pq.pop();
	}
}
int main()
{
	test02();//自定義類型
	system("pause");
	return 0;
}

??????注意點(diǎn)：

• 如果存放自定義類型，我們想要自定義類型像內(nèi)置類型一樣進(jìn)行各種運(yùn)算，那么就要在類中重載相應(yīng)的運(yùn)算符。
• 輸出自定義類型，需要重載流輸出。
• 在priority_queue的第三個(gè)參數(shù)時(shí)，我們可以用庫中的greater函數(shù)（頭文件：functional），也可以我們自己寫一個(gè)仿函數(shù)（如上述代碼）。

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

	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;
		}
	};
	// 優(yōu)先級(jí)隊(duì)列 -- 大堆 < 小堆 >
	template<class T, class Container = vector<T>, class Compare = less<T>>
	class priority_queue
	{
	public:
		void AdjustUp(int child)
		{
			Compare comFunc;
			int parent = (child - 1) / 2;
			while (child > 0)
			{
				//if (_con[parent] < _con[child])
				if (comFunc(_con[parent], _con[child]))
				{
					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 parent)
		{
			Compare comFunc;
			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() && comFunc(_con[child], _con[child + 1]))
				{
					++child;
				}
				//if (_con[parent] < _con[child])
				if (comFunc(_con[parent], _con[child]))
				{
					swap(_con[parent], _con[child]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}
		void pop()
		{
			assert(!_con.empty());
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			AdjustDown(0);
		}
		const T& top()
		{
			return _con[0];
		}
		size_t size()
		{
			return _con.size();
		}
		bool empty()
		{
			return _con.empty();
		}
	private:
		Container _con;
	};

代碼解釋：

• 這里模擬實(shí)現(xiàn)底層容器缺省參數(shù)使用vector，比較規(guī)則使用Less。
• 這里的比較方式均是自己實(shí)現(xiàn)的仿函數(shù)。

四、容器適配器

4.1、什么是適配器

適配器是一種設(shè)計(jì)模式（設(shè)計(jì)模式是一套被反復(fù)使用的，多數(shù)人知曉的，經(jīng)過分類編目的，代碼設(shè)計(jì)經(jīng)驗(yàn)的總結(jié)），該模式是講一個(gè)類的接口轉(zhuǎn)換成客戶希望的另一個(gè)接口。

4.2、適配模式

• 在計(jì)算機(jī)編程中，適配器模式（有時(shí)候也稱包裝樣式或者包裝）將一個(gè)類的接口適配成用戶所期待的。一個(gè)適配允許通常因?yàn)榻涌诓患嫒荻荒茉谝黄鸸ぷ鞯念惞ぷ髟谝黄?，做法是將類自己的接口包裹在一個(gè)已存在的類中。
• 適配器模式主要應(yīng)用于，當(dāng)接口里定義的方法無法滿足客戶的需求，或者說接口里定義的方法的名稱或者方法界面與客戶需求有沖突的情況。
• 兩類模式：對(duì)象適配器模式 - 在這種適配器模式中，適配器容納一個(gè)它我包裹的類的實(shí)例。在這種情況下，適配器調(diào)用被包裹對(duì)象的物理實(shí)體。類適配器模式 - 這種適配器模式下，適配器繼承自已實(shí)現(xiàn)的類（一般多重繼承）。
• 在計(jì)算機(jī)編程中，適配器包括：容器適配器、迭代器適配器、泛函適配器等。

4.3、STL標(biāo)準(zhǔn)庫中stack和queue的底層結(jié)構(gòu)

雖然stack和queue也可以存放元素，但是在STL中并沒有將其劃分在容器的行列，而是將其稱為容器適配器，這是因?yàn)闂：完?duì)列只是對(duì)其他容器的接口進(jìn)行了包裝，STL中stack和queue默認(rèn)使用deque，比如：

當(dāng)然了，這里的容器都是默認(rèn)容器，容器不唯一，我們可以顯式傳對(duì)應(yīng)的容器。

到此這篇關(guān)于C++深入刨析優(yōu)先級(jí)隊(duì)列priority_queue的使用的文章就介紹到這了,更多相關(guān)C++ priority_queue內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論