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

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

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

容器適配器

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

仿函數(shù)

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

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

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

示例：

#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ù)進行排序
    std::sort(numbers.begin(), numbers.end(), Compare());
 
    std::cout << "Sorted numbers: ";
    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
 
    return 0;
}

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

priority_queue

priority_queue簡單介紹

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

模擬實現(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;
		}
	};

首先實現(xiàn)兩個仿函數(shù)可以用來建立大（?。┒?/p>

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

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

		// 向下調整
		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;
			}
		}

向上（向下）調整算法

向上調整算法：從最后一個節(jié)點開始與自己的父親比較，如果比父親大（?。┚秃透赣H交換位置，直到調整到根節(jié)點為止

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

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

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

		template<class Iterator>
		priority_queue(Iterator first, Iterator last)
			: c(first, last)
		{
			// 將c中的元素調整成堆的結構
			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();
		}

		// 堆頂元素不允許修改，因為：堆頂元素修改可以會破壞堆的特性
		const T& top()const
		{
			return c.front();
		}
        private:
		Container c;
	};

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

您可能感興趣的文章: