C++ 容器适配器仿函数与priority_queue的使用

目录

• 容器适配器
• 仿函数
• priority_queue
• priority_queue简单介绍
• 模拟实现

容器适配器

适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。 它们的底层都是其他的容器，例如stack和queue的底层容器默认是deque，而priority_queue的底层容器是vector。它们是对这些容器进行了包装提供了用户想要的接口。

仿函数

定义：仿函数不是函数，而是行为类似函数的类，它重载了opprator()

仿函数的优势：

• 状态维护：仿函数可以持有状态，每次调用可以根据状态改变行为。
• 内联调用：由于仿函数是通过对象调用的，编译器可以轻易地将其内联，减少调用开销。
• 高度定制：可以通过对象的属性来调整其行为。

示例：

#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};
 
    // 使用仿函数进行排序
    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是一个仿函数，它重载了operator()来进行整数比较。我们使用这个仿函数作为std::sort的比较函数，用来对一个整数向量进行排序。

priority_queue

priority_queue简单介绍

priority_queue是一个容器适配器（如stack,queue)它的底层容器是vector。它的行为类似与heap（堆）默认情况下建立的是大堆。它的底层容器必须能支持随时访问任意位置的元素（这也是为了满足建堆的要求）

模拟实现

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

首先实现两个仿函数可以用来建立大（小）堆

然后实现向下和向上调整算法

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

向上（向下）调整算法

向上调整算法：从最后一个节点开始与自己的父亲比较，如果比父亲大（小）就和父亲交换位置，直到调整到根节点为止

向下调整算法：从根节点开始，与左右孩子节点中较大（较小)者比较，若根节点比较大(小)则交换位置，一直向下调整到最后一个节点。

接下来就是比较简单的利用接口进行实现

template<class T, class Container = std::vector<T>, class Compare = less<T>>
	class priority_queue
	{
	public:
		// 创造空的优先级队列
		priority_queue() : c() {}

		template<class Iterator>
		priority_queue(Iterator first, Iterator last)
			: c(first, last)
		{
			// 将c中的元素调整成堆的结构
			int count = c.size();
			www.devze.comint 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();http://www.devze.com
		}

		bool empty()constwww.devze.com
		{
			return c.empty();
		}

		// 堆顶元素不允许修改，因为：堆顶元素修改可以会破坏堆的特性
		const T& top()const
		{
			return c.front();
		}
        private:
		Container c;
	};

到此这篇关于C++ 容器适配器仿函数与priority_queue的文章就介绍到这了,更多相关C++ 容器适配器与priority_queue内容请搜索编http://www.devze.com程客栈(www.devze.com)以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程客栈(www.devze.com)！