当前位置：网站首页>Stack and queue and priority queue (large heap and small heap) simulation implementation and explanation of imitation function
Stack and queue and priority queue (large heap and small heap) simulation implementation and explanation of imitation function
2022-07-29 04:52:00 【Korean suspense】
Here's the catalog title
1. The adapter is simple
When we write stack Before that, let's briefly understand the adapter , Take our mobile phone charging as an example , Everyone knows that our household electricity is 220, There is a charging line for mobile phone charging , And the power adapter for mobile phone charging , You can't use that high electricity , Will be reduced accordingly , It would be less dangerous , The most important function of the adapter is to transform , Into what I want
2.stack Simulation Implementation
We need to use before writing stack The adapter for ,deque With it, the implementation of stack is particularly simple , Stack is first in first out
#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<int, vector<int>> s;
//stack<int, list<int>> s;
//stack<int, string> 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;
}
};
In this way, I'm finished , You can see that the code for writing stacks is particularly simple , And less , Also understand , Because to write this stack, you only need to call the functions encapsulated in the Library
above test Code for
stack s;
stack<int, vector> s;
stack<int, list> s;
stack<int, string> s;
These different types can run without error ,
except stack<int, string> s; Why? ？
Operation report 
There will be problems of truncation or overflow
2.queue Simulation Implementation
Unlike stack, first in, first out
#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<int> q;
queue<int, list<int>> q;
//queue<int, vector<int>> q; // no way
q.push(1);
q.push(2);
q.push(3);
q.push(4);
while (!q.empty())
{
cout << q.front() << " ";
q.pop();
}
cout << endl;
}
}
What we should pay attention to here is vector Is not supported , because vector Header deletion is not supported
3. Priority queue
Priority queue I put behind the queue
// Priority queue -- A lot < Little heap >
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;
}
In this way, we can , But it's troublesome to control large or small piles like this , At this time, we use the imitative function
Imitative functions are actually assigned values, but they look like functions
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;
}
};
We add greater, Then adjust upward , And downward adjustment , We are just a small pile
Code
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;
}
};
// Priority queue -- A lot < Little heap >
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<int> LessCom; cout << LessCom(1, 2) << endl; greater<int> GreaterCom; cout << GreaterCom(1, 2) << endl;*/
//priority_queue<int> 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;
}
Running results 
We don't add greator, Because we default to less It's a lot 
4. functor
The advantage of imitating function is to replace function pointer
because c++ yes c Derived from , therefore c++ Will support c Usage of
Next, in order to support why function pointers are written , If you do not specify the function address , Then the constructor will be called , If you don't write a constructor, it's a random value , Write the address if there is no function , Then the pointer is a null pointer , So what is the address of the function , The function name can be the address of the function , That's why we have the following writing
priority_queue<int, vector<int>, bool(*)(int, int)> pq(ComIntLess);
// Priority queue -- A lot < Little heap >
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<int, vector<int>, greater<int>> pq;
//priority_queue<int, vector<int>> 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;
}
-
Running results
If you don't use function pointers, the default is a lot , Because it was realized by imitating function , If you use function pointers to implement a large heap, it is the same as the above implementation of a small heap , In fact, it can be seen that function pointers are really too much trouble compared with imitation functions 
Next, we will compare how the following code is used sort To compare
// goods
struct Goods
{
string _name;
double _price;
size_t _saleNum;
};
void test_goods()
{
Goods gds[4] = {
{
" Apple ", 2.1, 1000}, {
" Banana ", 3.0, 200}, {
" The oranges ", 2.2,300}, {
" Pineapple ", 1.5,50} };
}
It looks like ？
See the wrong report , To compare, you can use operator<
You can see that there is no problem , But this can only compare the price , What if I want to compare others ？ And continue to use operator No, because there is only one same parameter , Nor does it constitute a function overload .
At this time, it depends on the imitative function
#include <iostream>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <deque>
#include <functional>
#include <assert.h>
using namespace std;
#include"stack.h"
#include"queue.h"
// goods
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] = {
{
" Apple ", 2.1, 1000}, {
" Banana ", 3.0, 200}, {
" The oranges ", 2.2,300}, {
" Pineapple ", 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;
}
Running results
It's comfortable to see , Call whatever you want to compare 
边栏推荐
- Oracle update and delete data
- SGuard64.exe ACE-Guard Client EXE：造成磁盘经常读写，游戏卡顿，及解决方案
- Using jupyter (I), install jupyter under windows, open the browser, and modify the default opening address
- Reveal installation configuration debugging
- Introduction to auto.js script development
- [c language] PTA 7-49 have fun with numbers (partially correct)
- Actual combat of flutter - DIO of request encapsulation (II)
- Mujoco and mujoco_ Install libxcursor.so 1:NO such dictionary
- WPS插入超链接无法打开，提示“无法打开指定文件”怎么办！
- Flink+iceberg environment construction and production problem handling
猜你喜欢
Several simple and difficult OJ problems with sequential force deduction
带你一文理解JS数组
spinning up安装完使用教程测试是否成功，出现Library“GLU“ not found和‘from pyglet.gl import *错误解决办法
Reveal installation configuration debugging
SSM integration, addition, deletion, modification and query
ios面试准备 - 网络篇
MySQL定时调用预置函数完成数据更新
Torch.nn.crossentropyloss() details
![Academic | [latex] super detailed texlive2022+tex studio download installation configuration](/img/4d/f8c60c0fbbd98c4da198cfac7989fa.png)
Academic | [latex] super detailed texlive2022+tex studio download installation configuration
学术 | [LaTex]超详细Texlive2022+Tex Studio下载安装配置
随机推荐
WPS如何进行快速截屏？WPS快速截屏的方法
网络之以太网
mujoco和mujoco_py安装以及解决libXcursor.so.1:NO such dictionary
Makefile+make Basics
Climbing the pit of traffic flow prediction (II): the simplest LSTM predicts traffic flow using tensorflow2
Basic grammar of C language
PHP determines whether the user has logged in. If logged in, the home page will be displayed. If not, enter the login page or registration page
[c language] PTA 7-51 sum the first n terms of odd part sequence
SGuard64.exe ACE-Guard Client EXE：造成磁盘经常读写，游戏卡顿，及解决方案
Recyclerview switches the focus up and down through the dpad key. When switching to the control outside the interface, the focus will jump left and right
【无标题】
Star a pathfinding in LAYA
On prepayment of house purchase
ios面试准备 - objective-c篇
Reveal安装配置调试
Improve the readability of your regular expressions a hundred times
Reveal installation configuration debugging
Leetcode (Sword finger offer) - 53 - I. find the number I in the sorted array
央企建筑企业数字化转型核心特征是什么？
输入的查询SQL语句，是如何执行的？