个人主页：点我进入主页
专栏分类：C语言初阶 C语言进阶 数据结构初阶 Linux C++初阶 算法
欢迎大家点赞，评论，收藏。
一起努力，一起奔赴大厂
目录
一.stack,queue,priority_queue简介以及代码模拟
1.1 stack
1.2queue
1.3 priority_queue
二.仿函数
2.1priority_queue中的仿函数
2.2sort函数中的仿函数
2.3货物类中的仿函数
一.stack,queue,priority_queue简介以及代码模拟
在这里我们的stack,queue,priority_queue是适配器，适配器就是不需要我们自己去写，只需要使用我们已有的容器来写，可以使用vector，特可以使用list，但是我们默认使用的是deque，我们看看是如何实现stack,queue,priority_queue这三个的，我们可以直接看代码。这里的大部分内容我在前面写过，可以看博客栈和队列 ，堆。
1.1 stack
template <class T, class Container = deque<T> >
class stack
{
public:
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_back();
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
const T& top()
{
return _con.back();
}
private:
Container _con;
};1.2queue
template <class T,class Containter=deque<T>>
class queue
{
public:
void push(const T& val)
{
_con.push_front(val);
}
void pop()
{
_con.pop_front();
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
const T& front()
{
return _con.front();
}
const T& back()
{
return _con.back();
}
private:
Containter _con;
};1.3 priority_queue
priority_queue就是堆，默认为大堆，适配器是vector。
template <class T, class Container = vector<T>,class Comper=less<T>>
class priority_queue
{
public:
Comper com;
bool empty()
{
return _con.empty();
}
size_t size()
{
return _con.size();
}
const T& top()
{
return _con[0];
}
void AdJust_up(int n)
{
int child = n;
int parent = (child - 1) / 2;
while (child > 0)
{
if (com(_con[parent] , _con[child]))
{
swap(_con[parent], _con[child]);
child = parent;
parent = (child - 1) / 2;
}
else break;
}
}
void push(const T& val)
{
_con.push_back(val);
AdJust_up(_con.size()-1);
}
void AdJust_down()
{
int n = _con.size();
int parent = 0;
int child = parent * 2 + 1;
while (child<n)
{
if (child + 1 < n &&com( _con[child] ,_con[child + 1])) child++;
if (com(_con[parent] , _con[child]))
{
swap(_con[parent], _con[child]);
parent = child;
child = parent * 2 + 1;
}
else break;
}
}
void pop()
{
swap(_con[_con.size() - 1],_con[0]);
_con.pop_back();
AdJust_down();
}
private:
Container _con;
};二.仿函数
2.1priority_queue中的仿函数
在priority_queue中仿函数就是我们的比较大小时写的，默认为Less<T>，表示大堆，我们可以先看看大堆的仿函数
template <class T>
struct less
{
bool operator()(const T& x, const T& y)
{
return x < y;
}
};我们小堆的仿函数是
template <class T>
struct greater
{
bool operator()(const T& x, const T& y)
{
return x > y;
}
};不管是大堆还是小堆，我们用模板来写，默认传的是大堆，所以我们使用时先实例化一个对象，然后利用operator（）来进行比较，也就是com(x,y)；如果我们想要传小堆，我们需要把vector传进去，样例如下：
priority_queue<int,vector<int>,greater<int>> q2.2sort函数中的仿函数
sort默认是升序排序，我们需要传它的迭代器，我们先看样例
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
vector<int> v;
v.push_back(5);
v.push_back(4);
v.push_back(3);
v.push_back(2);
v.push_back(1);
sort(v.begin(), v.end());
vector<int>::iterator it = v.begin();
while (it != v.end())
{
cout << *it << " ";
it++;
}
cout << endl;
return 0;
}运行结果为：
它的默认的仿函数就是Less<int>,和priority_queuet的一样
sort(v.begin(), v.end(), less<int>());它的降序就是
sort(v.begin(), v.end(), greater<int>());2.3货物类中的仿函数
struct Goods
{
string _name; // 名字
double _price; // 价格
int _evaluate; // 评价
Goods(const char* str, double price, int evaluate)
:_name(str)
, _price(price)
, _evaluate(evaluate)
{}
};我们可以针对名字，价格，评价来进行排序，因此我们需要写关于这三种的仿函数，
struct CmpNameLess
{
bool operator()(const Goods& x, const Goods& y)
{
return x._name< y._name;
}
};
struct CmpPriceLess
{
bool operator()(const Goods& x, const Goods& y)
{
return x._price < y._price ;
}
};
struct CmpEvaluateLess
{
bool operator()(const Goods& x, const Goods& y)
{
return x._evaluate < y._evaluate ;
}
};，我们在传参数时只需要写成匿名对象就可以
int main()
{
vector<Goods> v = { { "苹果", 2.1, 5 }, { "香蕉", 3, 4 }, { "橙子", 2.2,
3 }, { "菠萝", 1.5, 4 } };
//名字
sort(v.begin(), v.end(), CmpNameLess());
vector<Goods>::iterator it = v.begin();
while (it != v.end())
{
cout << it->_name << " " << it->_price << " " << it->_evaluate << endl;;
it++;
}
cout << endl;
//价格
sort(v.begin(), v.end(), CmpPriceLess());
it = v.begin();
while (it != v.end())
{
cout << it->_name << " " << it->_price << " " << it->_evaluate << endl;;
it++;
}
cout << endl;
//评价
sort(v.begin(), v.end(), CmpEvaluateLess());
it = v.begin();
while (it != v.end())
{
cout << it->_name << " " << it->_price << " " << it->_evaluate << endl;;
it++;
}
cout << endl;
}运行结果如下：
