• stack和queue和优先级队列（大堆和小堆）模拟实现和仿函数讲解

    这里写目录标题

    1.适配器简单了解

    当我们写stack之前我们先来简单了解下适配器，就以我们手机充电为例子，大家都知道我们家用电是220，手机充电有个充电线，而手机充电的电源适配器，用不了那么高的电，会相应的降低，这样子会没有那么危险，而适配器最重要的作用是转换，转换成我想要的东西

    2.stack模拟实现

    写之前我们就要用到stack的适配器了，deque有了它实现栈就特别简单了，栈是先进后出

    #pragma once

namespace stk
{
	template<class T, class Container = deque<T>>
	class stack
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}

		void pop()
		{
			_con.pop_back();
		}

		const T& top()
		{
			return _con.back();
		}

		size_t size()
		{
			return _con.size();
		}

		bool empty()
		{
			return _con.empty();
		}


	private:
		Container _con;

	};

	void test_stack()
	{
		stack<int> s;
		//stack> s;
		//stack> s;
		//stack s; // 

		s.push(1);
		s.push(2);
		s.push(3);
		s.push(4);
		s.push(300);

		while (!s.empty())
		{
			cout << s.top() << " ";
			s.pop();
		}
		cout << endl;
	}

};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61

    这样子就写完了，可以看到写栈的代码特别简单，而且少，也好理解，因为写这个栈只要调用库里面封装好的函数就行了
    上面test的代码
    stack s;
    stack s;
    stack s;
    stack s;
    这些不同类型的都可以运行不会报错，
    除了 stack s; 为什么呢？
    运行报告
    在这里插入图片描述
    会出现截断或者溢出的问题

    2.queue模拟实现

    和栈不一样的是先进先出

    #pragma once

namespace que
{
	template<class T, class Container = deque<T>>
	class queue
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}

		void pop()
		{
			_con.pop_front();
		}

		const T& front()
		{
			return _con.front();
		}

		const T& back()
		{
			return _con.back();
		}

		size_t size()
		{
			return _con.size();
		}

		bool empty()
		{
			return _con.empty();
		}
	private:
		Container _con;
	};

	void test_queue()
	{
		//queue q;
		queue<int, list<int>> q;
		//queue> q; // 不行

		q.push(1);
		q.push(2);
		q.push(3);
		q.push(4);

		while (!q.empty())
		{
			cout << q.front() << " ";
			q.pop();
		}
		cout << endl;
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60

    这里要注意的是vector是不支持的，因为vector不支持头删

    3.优先级队列

    优先级队列我放在队列后面的

    	// 优先级队列 -- 大堆 <  小堆 >
	template<class T, class Container = vector<T>>
	class priority_queue
	{
	public:
		void AdjustUp(int child)
		{
			int parent = (child - 1) / 2;
			while (child > 0)
			{
				if (_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)
		{
			size_t child = parent * 2 + 1;
			while (child < _con.size())
			{
				if (child+1 < _con.size() && _con[child] < _con[child+1])				
				{
					++child;
				}

				if (_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;
	};

	void test_priority_queue()
	{
		priority_queue<int> pq;
		pq.push(2);
		pq.push(5);
		pq.push(1);
		pq.push(6);
		pq.push(8);

		while (!pq.empty())
		{
			cout << pq.top() << " ";
			pq.pop();
		}
		cout << endl;
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97

    这样子就可以了，但是这样子控制大堆或者小堆就很麻烦，这个时候我们就用仿函数
    仿函数其实是赋值来的但是看起来很像函数

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    我们在模板里面加上greater，再把向上调整，和向下调整改下，我们就是小堆
    代码

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

	// 优先级队列 -- 大堆 <  小堆 >
	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;
	};

	void test_priority_queue()
	{
		/*less LessCom;
		cout << LessCom(1, 2) << endl;

		greater GreaterCom;
		cout << GreaterCom(1, 2) << endl;*/

		//priority_queue pq;
		priority_queue<int, vector<int>, greater<int>> pq;

		pq.push(2);
		pq.push(5);
		pq.push(1);
		pq.push(6);
		pq.push(8);

		while (!pq.empty())
		{
			cout << pq.top() << " ";
			pq.pop();
		}
		cout << endl;
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128

    运行结果
    在这里插入图片描述
    我们不加上greator，因为我们默认是less是大堆
    在这里插入图片描述

    4.仿函数

    仿函数的优点是用来代替函数指针
    因为c++是c衍生过来的，所以c++是会支持c的用法
    下面为了支持函数指针为什么怎么写，如果不指定函数地址，那么就会调用构造函数，如果没有写构造函数就是随机值，写了如果没有函数的地址，那么指向的就是空指针，那么函数的地址是什么，函数名就可以当函数的地址，所以才有了下面的写法

    	priority_queue<int, vector<int>, bool(*)(int, int)> pq(ComIntLess);

    • 1
    	// 优先级队列 -- 大堆 <  小堆 >
	template<class T, class Container = vector<T>, class Compare = less<T>>
	class priority_queue
	{
		Compare _comFunc;
	public:
		priority_queue(const Compare& comFunc = Compare())
			:_comFunc(comFunc)
		{}

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

	bool ComIntLess(int x1, int x2)
	{
		return x1 > x2;
	}

	void test_priority_queue()
	{
		//priority_queue, greater> pq;
		//priority_queue> pq;
		priority_queue<int, vector<int>, bool(*)(int, int)> pq(ComIntLess);


		pq.push(2);
		pq.push(5);
		pq.push(1);
		pq.push(6);
		pq.push(8);

		while (!pq.empty())
		{
			cout << pq.top() << " ";
			pq.pop();
		}
		cout << endl;
	}

-

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118

    运行结果
    如果没用函数指针默认就是大堆，因为之前用仿函数实现了，如果用函数指针实现大堆和上面实现小堆一样，其实可以看的出来函数指针比起仿函数来讲真的是麻烦太多了
    在这里插入图片描述

    接下来要比较下面的代码怎么用sort来比较

    // 商品
struct Goods
{
	string _name;
	double _price;
	size_t _saleNum;
};



void test_goods()
{
	Goods gds[4] = { { "苹果", 2.1, 1000}, { "香蕉", 3.0, 200}, { "橙子", 2.2,300}, { "菠萝", 1.5,50} };
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    这样子？
    在这里插入图片描述
    看到报错了，要比较可以用operator<
    在这里插入图片描述

    可以看到没有问题了，但是这只能比较价格啊，要是我想比较其他怎么办？而且继续用operator也不行因为只有一个相同的参数，也构不成函数重载。
    这个时候就要看仿函数了

    #include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#include"stack.h"
#include"queue.h"

// 商品
struct Goods
{
	string _name;
	double _price;
	size_t _saleNum;

	//bool operator<(const Goods& g) const
	//{
	//	return _price < g._price;
	//}
};

struct LessPrice
{
	bool operator()(const Goods& g1, const Goods& g2) const
	{
		return g1._price < g2._price;
	}
};

struct GreaterPrice
{
	bool operator()(const Goods& g1, const Goods& g2) const
	{
		return g1._price > g2._price;
	}
};

struct LessSaleNum
{
	bool operator()(const Goods& g1, const Goods& g2) const
	{
		return g1._saleNum < g2._saleNum;
	}
};


struct GreaterSaleNum
{
	bool operator()(const Goods& g1, const Goods& g2) const
	{
		return g1._saleNum > g2._saleNum;
	}
};



void test_goods()
{
	int i = 0;
	Goods gds[4] = { { "苹果", 2.1, 1000}, { "香蕉", 3.0, 200}, { "橙子", 2.2,300}, { "菠萝", 1.5,50} };
	sort(gds, gds + 4, LessPrice());
	for (i = 0; i < 4; i++)
	{
		cout << gds[i]._name << " ";
		cout << gds[i]._price << " ";
		cout << gds[i]._saleNum << " ";
	}
	cout << endl;
	sort(gds, gds + 4, GreaterPrice());
	for (i = 0; i < 4; i++)
	{
		cout << gds[i]._name << " ";
		cout << gds[i]._price << " ";
		cout << gds[i]._saleNum << " ";
	}
	cout << endl;
	sort(gds, gds + 4, LessSaleNum());
	for (i = 0; i < 4; i++)
	{
		cout << gds[i]._name << " ";
		cout << gds[i]._price << " ";
		cout << gds[i]._saleNum << " ";
	}
	cout << endl;
	sort(gds, gds + 4, GreaterSaleNum());
	for (i = 0; i < 4; i++)
	{
		cout << gds[i]._name << " ";
		cout << gds[i]._price << " ";
		cout << gds[i]._saleNum << " ";
	}
	cout << endl;
}


int main()
{
	test_goods();
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104

    运行结果
    可以看到很舒服，想比较什么就调用什么
    在这里插入图片描述

  • 相关阅读:
    内存函数介绍
    睡眠剥夺后皮层微结构的广泛变化
    vue中实现千位分隔符
    关于什么是AndroidX（二）
    锂离子电池充电管理芯片应用
    【图形学】 06 四元数（一）
    maven 进阶
    【数据结构】链表的八种形态
    XSS靶机通关以及XSS介绍
    5. HTTPS的特点
  • 原文地址：https://blog.csdn.net/li1829146612/article/details/126008841