当前位置：网站首页>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 
边栏推荐
- Unity Foundation (3) -- various coordinate systems in unity
- What are the core features of the digital transformation of state-owned construction enterprises?
- MySQL time calculation function
- Un7.28: common commands of redis client.
- [C language] PTA 7-47 binary leading zero
- Mujoco and mujoco_ Install libxcursor.so 1:NO such dictionary
- Mysql:The user specified as a definer (‘root‘@‘%‘) does not exist 的解决办法
- C语言实现三子棋
- Live in small private enterprises
- Use jupyter (2) to establish shortcuts to open jupyter and common shortcut keys of jupyter
猜你喜欢
Ethernet of network
新产品上市最全推广方案
Delete blank pages in word documents
Data Lake: spark, a distributed open source processing engine
img 响应式图片的实现（含srcset属性、sizes属性的使用方法，设备像素比详解）
五个关联分析，领略数据分析师一大重要必会处理技能
ios面试准备 - 网络篇
Corresponding order of 18 and 25coco data of openpose and joint points
IOS interview preparation - Online
Reveal installation configuration debugging
随机推荐
Review key points and data sorting of information metrology in the second semester of 2022 (teacher zhaorongying of Wuhan University)
Wps如何使用智能填充快速填充数据？Wps快速填充数据的方法
MySQL time calculation function
软件测试面试题（四）
正确的用户拖拽方式
STL source code analysis (Hou Jie) notes - STL overview
[C language] power table of 3 generated by PTA 7-53
[c language] PTA 7-50 output Fahrenheit Celsius temperature conversion table
On prepayment of house purchase
UE 在场景或UMG中播放视频
删除word文档中的空白页
怎样监测微型的网站服务
1 sentence of code, get asp Net core binds multiple sources to the same class
STL source code analysis (Hou Jie) notes -- Classification and testing of stl containers
pulsar起client客户端时(client,producer,consumer)各个配置
Simply change the picture color
Climbing the pit of traffic flow prediction (III): using pytorch to realize LSTM to predict traffic flow
Data Lake: spark, a distributed open source processing engine
Classes and objects (I)
Using jupyter (I), install jupyter under windows, open the browser, and modify the default opening address