快捷導(dǎo)航

C++ 容器適配器仿函數(shù)與priority_queue的使用

更新時(shí)間：2024年09月26日 08:30:18 作者：FITMT

本文主要介紹了C++ 容器適配器仿函數(shù)與priority_queue的使用,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

容器適配器

適配器是一種設(shè)計(jì)模式(設(shè)計(jì)模式是一套被反復(fù)使用的、多數(shù)人知曉的、經(jīng)過分類編目的、代碼設(shè)計(jì)經(jīng)驗(yàn)的總結(jié))，該種模式是將一個(gè)類的接口轉(zhuǎn)換成客戶希望的另外一個(gè)接口。它們的底層都是其他的容器，例如stack和queue的底層容器默認(rèn)是deque，而priority_queue的底層容器是vector。它們是對這些容器進(jìn)行了包裝提供了用戶想要的接口。

仿函數(shù)

定義：仿函數(shù)不是函數(shù)，而是行為類似函數(shù)的類，它重載了opprator()

仿函數(shù)的優(yōu)勢：

狀態(tài)維護(hù)：仿函數(shù)可以持有狀態(tài)，每次調(diào)用可以根據(jù)狀態(tài)改變行為。
內(nèi)聯(lián)調(diào)用：由于仿函數(shù)是通過對象調(diào)用的，編譯器可以輕易地將其內(nèi)聯(lián)，減少調(diào)用開銷。
高度定制：可以通過對象的屬性來調(diào)整其行為。

示例：

#include <iostream>
#include <algorithm>
#include <vector>
 
class Compare {
public:
    bool operator()(int a, int b) {
        return a < b;
    }
};
 
int main() {
    std::vector<int> numbers = {10, 65, 30, 99, 23};
 
    // 使用仿函數(shù)進(jìn)行排序
    std::sort(numbers.begin(), numbers.end(), Compare());
 
    std::cout << "Sorted numbers: ";
    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
 
    return 0;
}

在這個(gè)示例中，Compare是一個(gè)仿函數(shù)，它重載了operator()來進(jìn)行整數(shù)比較。我們使用這個(gè)仿函數(shù)作為std::sort的比較函數(shù)，用來對一個(gè)整數(shù)向量進(jìn)行排序。

priority_queue

priority_queue簡單介紹

priority_queue是一個(gè)容器適配器（如stack,queue)它的底層容器是vector。它的行為類似與heap（堆）默認(rèn)情況下建立的是大堆。它的底層容器必須能支持隨時(shí)訪問任意位置的元素（這也是為了滿足建堆的要求）

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

template<class T>
	struct less
	{
		bool operator()(const T& left, const T& right)
		{
			return left < right;
		}
	};

	template<class T>
	struct greater
	{
		bool operator()(const T& left, const T& right)
		{
			return left > right;
		}
	};

首先實(shí)現(xiàn)兩個(gè)仿函數(shù)可以用來建立大（小）堆

然后實(shí)現(xiàn)向下和向上調(diào)整算法

void AdjustUP(int child)
		{
			int parent = ((child - 1) >> 1);
			while (child)
			{
				if (Compare()(c[parent], c[child]))
				{
					swap(c[child], c[parent]);
					child = parent;
					parent = ((child - 1) >> 1);
				}
				else
				{
					return;
				}
			}
		}

		// 向下調(diào)整
		void AdjustDown(int parent)
		{
			size_t child = parent * 2 + 1;
			while (child < c.size())
			{
				// 找以parent為根的較大的孩子
				if (child + 1 < c.size() && Compare()(c[child], c[child + 1]))
					child += 1;

				// 檢測雙親是否滿足情況
				if (Compare()(c[parent], c[child]))
				{
					swap(c[child], c[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
					return;
			}
		}

向上（向下）調(diào)整算法

向上調(diào)整算法：從最后一個(gè)節(jié)點(diǎn)開始與自己的父親比較，如果比父親大（小）就和父親交換位置，直到調(diào)整到根節(jié)點(diǎn)為止

向下調(diào)整算法：從根節(jié)點(diǎn)開始，與左右孩子節(jié)點(diǎn)中較大（較小)者比較，若根節(jié)點(diǎn)比較大(小)則交換位置，一直向下調(diào)整到最后一個(gè)節(jié)點(diǎn)。

接下來就是比較簡單的利用接口進(jìn)行實(shí)現(xiàn)

template<class T, class Container = std::vector<T>, class Compare = less<T>>
	class priority_queue
	{
	public:
		// 創(chuàng)造空的優(yōu)先級隊(duì)列
		priority_queue() : c() {}

		template<class Iterator>
		priority_queue(Iterator first, Iterator last)
			: c(first, last)
		{
			// 將c中的元素調(diào)整成堆的結(jié)構(gòu)
			int count = c.size();
			int root = ((count - 2) >> 1);
			for (; root >= 0; root--)
				AdjustDown(root);
		}

		void push(const T& data)
		{
			c.push_back(data);
			AdjustUP(c.size() - 1);
		}

		void pop()
		{
			if (empty())
				return;

			swap(c.front(), c.back());
			c.pop_back();
			AdjustDown(0);
		}

		size_t size()const
		{
			return c.size();
		}

		bool empty()const
		{
			return c.empty();
		}

		// 堆頂元素不允許修改，因?yàn)椋憾秧斣匦薷目梢詴茐亩训奶匦?
		const T& top()const
		{
			return c.front();
		}
        private:
		Container c;
	};

到此這篇關(guān)于C++ 容器適配器仿函數(shù)與priority_queue的文章就介紹到這了,更多相關(guān)C++ 容器適配器與priority_queue內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: