初级C++：优先级队列、仿函数、模板进阶

• 前言
• 仿函数
• • 变异玩法
• 优先级队列
• • 各项功能模拟实现
• 模板特化
• • 类模板特化
  • 模板总结
• 结语

基础不牢，地动山摇，现已大地震…

是个自定义的类，对象可以像函数一样去使用

class lless  //仿函数自定义类型  对象可以像函数一样去使用
	{
	public://不写默认私有      
		bool operator()(int x, int y) //对（）重载，
		{
			return x > y;
		}
	};
	void testless()
	{
		lless le;
		std::cout << le(20,30) << std::endl;
	}

可以通过仿函数控制比较方式 ,例子：对日期类取最值

日期类
class Dtae
{
	friend ostream& operator<<(ostream& _cout, const Dtae& d);//友元函数
public:
	Dtae(int y = 2015, int m = 9, int d = 1);

	bool operator>( const Dtae& y)const //切记加const
	{
		return (_y > y._y ||
			(_y == y._y && _m > y._m) ||
			(_y == y._y && _m == y._m && _d > y._d));
	}
	friend class PDateLess;
private:
	int _y;
	int _m;
	int _d;
};
日期构造
Dtae::Dtae(int y,int m,int d)
{
	_y = y;
	_m = m;
	_d = d;
}
重载
ostream& operator<<(ostream& _cout, const Dtae& d)//友元在全局定义
{
	_cout << d._y << "-" << d._m << "-" << d._d << endl;
	return _cout;
}
仿函数
class PDateGreater
{
public:
	bool operator()(const Dtae p1, const Dtae p2)
	{
		return p1 > p2;
	}
};

int main()
{
    mypriority::priority_queue, PDateGreater> pq;
	pq.push( Dtae(2023, 11, 24));  /匿名对象
	pq.push(Dtae(2021, 10, 24));
	pq.push(Dtae(2021, 12, 24));
	pq.push(Dtae(2022, 1, 24));

	std::cout << pq.top() << std::endl;
	pq.pop();
	return 0；
}

namespace mypriority
{
	自己写的仿函数
	template
	class less
	{
	public:
		bool operator()(const T& x, const T& y)
		{
			return x < y;
		}
	};
	template
	class greater
	{
	public:   //不写默认私有
		bool operator()(const T& x, const T& y) 
		{
			return x > y;
		}
	};

	//哪头入不管，出的时候，要这个队列里面的最值  底层 完全二叉树，建堆 
	template,class Compare =greater>
	class priority_queue
	{
	public:
		priority_queue(){} /编译器对自定义类型 会调用它的默认构造
		void push(const T& x);
		void pop();
		void Adjustup(size_t child);
		void Adjustdown(size_t parent);
		const T& top();
		size_t size();
		bool empty();
	迭代器区间构造函数重载模板
		template
		priority_queue(Intr first, Intr Last)
		{
			while (first!=Last)
			{
				push(*first);
				++first;
			}
		}
	private:   //推荐使用容器 vector  
		Container _qu;
	};
	template  //模板参数列表类外定义 不要写缺省参数
	void priority_queue::push(const T& x)
	{
			_qu.push_back(x);
			//尾插就调用向上调整算法
			Adjustup(_qu.size() - 1);
	}
	template
	void priority_queue::pop()//交换头尾元素。size减减，从0开始调
	{
		if (_qu.empty())
		{
			return;
		}
		else
		{
		//交换首尾，容器popbacak，只有根不满足，其他节点满足堆的性质，调用向下调整
			std::swap(_qu[0], _qu[_qu.size() - 1]);
			_qu.pop_back();
			Adjustdown(0);
		}
	}
	template//参数列表类外定义不要写缺省参数
	void priority_queue::Adjustup(size_t child)
	{
	//向上调整：只有最后一个结点不满足堆的性质
	//传过来的是孩子节点，找最后一个孩子的双亲结点，孩子只需和双亲结点比就可以
		Compare le;//仿函数创建一个对象
		size_t parent = (child - 1) / 2;
		while (child>0)
		{
			if (le(_qu[child],_qu[parent]))
			{
				std::swap(_qu[parent], _qu[child]);//用仿函数传参
				child = parent;
				parent = (child-1)/2;
			}
			else
			{
				break;
			}
		}
	}
	template
	void priority_queue::Adjustdown(size_t parent)
	{
	//穿过来的是根节点，找孩子结点，和孩子中最值的比，不满足堆的性质就交换。
		Compare ge; //仿函数创建一个对象
		size_t child = parent * 2 + 1;
		while (child<_qu.size())
		{
			if (child + 1 < _qu.size() && ge(_qu[child+1], _qu[child])) //用仿函数传参
			{
				++child;
			}
			if (ge(_qu[child], _qu[parent]))
			{
				std::swap(_qu[child], _qu[parent]);
				parent = child;
				child = parent * 2 + 1;
			}
			else
			{
				break;
			}
		}
	}
	template
	const T& priority_queue::top()
	{
		return _qu[0];
	}
	template
	size_t priority_queue::size()
	{
		return _qu.size();
	}
	template
	bool priority_queue::empty()
	{
		return _qu.empty();
	}
}

测试函数

void testpriority_queue()
	{
		//不传会使用缺省的模板参数
		priority_queue pq;   
		//priority_queue,greater> pq1;
		pq.push(19);
		pq.push(200);
		pq.push(30);
		pq.push(7000);
		pq.push(40);
		pq.push(10);

		while (!pq.empty())
		{
			std::cout << pq.top() << std::endl;
			pq.pop();
		}
		std::cout << pq.size() << std::endl;
		std::cout << pq.empty() << std::endl;
	}

• 对模板参数类型的进一步限制：全特化，半特化偏特化

• 函数模板特化，依然根据匹配原则，进行特殊化处理，有现成用现成的，没现成的用通用的。

template
class Da
{
public:
	Da()
	{
		cout << "Da" << endl;
	}
private:
	T1 _d1;
	T2 _d2;
};

template<>
class Da
{
public:
	Da()
	{
		cout << "Da" << endl;
	}
private:
	int _d;
	char _c;
};

template
class Da
{
public:
	Da()
	{
		cout << "Da" << endl;
	}
private:
	T1 _d;
	char _c;
};


template
class Da
{
public:
	Da()
	{
		cout << "Da" << endl;
	}
private:
	T1 _d1;
	T2 _d2;
};

template
class Da
{
public:
	Da()
	{
		cout << "Da" << endl;
	}
private:
	T1 _d1;
	T2 _d2;
};

void testT()
{
	Da d1;
	Da d2;
	Dad3
	Da d4;
	Da d5;
}

不支持分离编译，将声明定义写在同一个文件

优缺点

假装已经会了…