模拟实现（优先级队列）priority_queue：优先级队列、仿函数、反向迭代器等的介绍

🕗 发布于 2024-09-28 11:56 c++ 反向迭代器

文章目录

前言
一、优先级队列
二、仿函数
三、反向迭代器
总结

前言

模拟实现（优先级队列）priority_queue：优先级队列、仿函数、反向迭代器等的介绍

一、优先级队列

优先级队列本质是一个堆，使用vector容器进一步改进进行实现，优先级队列可以传入比较模板参数，来确定建立大根堆还是小根堆，比较模板参数本质上是一个仿函数。

namespace hhb
{

template<class T>
struct Less
{
bool operator()(const T& left, const T& right)
{
return (left < right);
}
};

template<class T>
struct Greater
{
bool operator()(const T& left, const T& right)
{
return (left > right);
}
};

template <class T, class Container = vector<T>, class Compare = Less<T>>
class priority_queue
{

private:
void AdjustDown(int parent)
{

Compare _com;

// 找到子节点
int child = parent * 2 + 1;
// 找字节点中大的一个
if (child + 1 < _con.size() && _com(_con[child], _con[child + 1]))
{
++child;
}

while (child < _con.size())
{
if (_com(_con[parent], _con[child]))
{
swap(_con[parent], _con[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}


}

void AdjustUp(int child)
{
Compare _com;
// 找到父节点
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;
}
}

}
public:

priority_queue() {};
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last)
{
while (first != last)
{
_con.push_back(*first);
++first;
}

// 向下调整建堆
for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(i);
}

}

void push(const T& x)
{
_con.push_back(x);

AdjustUp(_con.size() - 1);
}

void pop()
{
swap(_con[0], _con[_con.size() - 1]);

_con.pop_back();

AdjustDown(0);
}


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

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

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

private:
Container _con;
};
}

测试：

#include <iostream>
#include <vector>

using namespace std;

#include "Priority_queue.h"

void test_priority_queue1()
{
hhb::priority_queue<int> pq1;
pq1.push(3);
pq1.push(1);
pq1.push(5);
pq1.push(2);
pq1.push(4);


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


vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(4);
v.push_back(3);
v.push_back(5);


hhb::priority_queue<int> pq2(v.begin(), v.end());

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

cout << endl;
}


void test_priority_queue2()
{
//Less<int> less;
//cout << less(1, 2) << endl;

hhb::priority_queue<int, vector<int>, hhb::Less<int>> pq1;
pq1.push(1);
pq1.push(2);
pq1.push(3);
pq1.push(4);
pq1.push(5);



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


hhb::priority_queue<int, vector<int>, hhb::Greater<int>> pq2;
pq2.push(5);
pq2.push(4);
pq2.push(3);
pq2.push(2);
pq2.push(1);


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

}

class Date
{
public:
Date(int year = 1949, int month = 10, int day = 1)
:_year(year)
,_month(month)
,_day(day)
{}

Date(const Date& d)
{
_year = d._year;
_month = d._month;
_day = d._day;
}

bool operator<(const Date& d) const
{
if (_year < d._year)
{
return true;
}
else if (_year == d._year && _month < d._month)
{
return true;
}
else if (_year == d._year && _month == d._month && _day < d._day)
{
return true;
}
else
{
return false;
}
}

bool operator>(const Date& d) const
{
if (_year > d._year)
{
return true;
}
else if (_year == d._year && _month > d._month)
{
return true;
}
else if (_year == d._year && _month == d._month && _day > d._day)
{
return true;
}
else
{
return false;
}
}

friend ostream& operator<<(ostream& out, const Date& d);


private:
int _year;
int _month;
int _day;
};

ostream& operator<<(ostream& out, const Date& d)
{
out << d._year << '-' << d._month << '-' << d._day;
return out;
}


void test_priority_queue3()
{
hhb::priority_queue<Date, vector<Date>, hhb::Less<Date>> pq1;

pq1.push(Date(2024, 9, 23));
pq1.push(Date(2024, 10, 23));
pq1.push(Date(2024, 8, 23));

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


hhb::priority_queue<Date, vector<Date>, hhb::Greater<Date>> pq2;

pq2.push(Date(2024, 9, 23));
pq2.push(Date(2024, 10, 23));
pq2.push(Date(2024, 8, 23));

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

}

int main()
{

//test_priority_queue1();

//test_priority_queue2();

 test_priority_queue3();

return 0;
}

在这里插入图片描述

二、仿函数

仿函数指的是类的实例化对象可以像函数一样使用，也可以叫函数对象。
本质上，仿函数是在类中进行了()运算符重载。

template<class T>
struct Less
{
bool operator()(const T& left, const T& right)
{
return (left < right);
}
};


void test_priority_queue4()
{
Less<int> less; // 类的实例化对象
cout << less(1, 2) << endl; // 可以像函数一样使用
}

测试：

void test_priority_queue4()
{
Less<int> less; // 类的实例化对象
cout << less(1, 2) << endl; // 可以像函数一样使用
}

在这里插入图片描述

有些特殊情况下，必须要使用仿函数，比如在优先级队列中，比较两个指针

void test_priority_queue5()
{
hhb::priority_queue<Date*> pq;

pq.push(new Date(2024, 9, 23));
pq.push(new Date(2024, 10, 23));
pq.push(new Date(2024, 8, 23));

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

在这里插入图片描述

直接进行指针的比较，是随机的，应该比较指针指向的对象。

struct LessPDate
{
bool operator()(const Date* left, const Date* right)
{
return (*left < *right);
}
};

void test_priority_queue5()
{
hhb::priority_queue<Date*, vector<Date*>, LessPDate> pq;

pq.push(new Date(2024, 9, 23));
pq.push(new Date(2024, 10, 23));
pq.push(new Date(2024, 8, 23));

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

在这里插入图片描述

三、反向迭代器

反向迭代器使用的是一种是适配器模式。可以适配所有支持迭代器的容器
反向迭代器与正向迭代器是镜像的，如：反向迭代器的rbegin是正向迭代器的end();

在这里插入图片描述


namespace hhb
{
template <class Iterator, class Ref, class Ptr>
struct ReverseIterator
{
typedef ReverseIterator<Iterator, Ref, Ptr> Self;

ReverseIterator(Iterator it)
:_it(it)
{}

Ref operator*()
{
Iterator tmp = _it;
return *(--tmp);
}

Ptr operator->()
{
return &(operator*());
}

Self& operator++()
{
--_it;
return *this;
}

Self& operator--()
{
++_it;
return *this;
}

bool operator!=(const Self& s)
{
return _it != s._it;
}


Iterator _it;
};
}

vector：

namespace hhb
{
template <class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;


typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;



iterator begin() 
{
return _start;
}

iterator end() 
{
return _finish;
}

const_iterator begin() const
{
return _start;
}

const_iterator end() const
{
return _finish;
}

reverse_iterator rbegin()
{
return end();
}


reverse_iterator rend()
{
return begin();
}


const_reverse_iterator rbegin() const
{
return end();
}


const_reverse_iterator rend() const
{
return begin();
}
}
}

list:

 template<class T> 
class list
{
typedef list_node<T> Node;
public:
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;

typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;

iterator begin()
{
return _head->_next;
}

iterator end()
{
return _head;
}

const_iterator begin() const
{
return _head->_next;
}

const_iterator end() const
{
return _head;
}


reverse_iterator rbegin()
{
return reverse_iterator(end());
}

reverse_iterator rend()
{
return reverse_iterator(begin());
}
}

测试：

#include "vector.h"
#include "list.h"

void test6()
{
hhb::list<int> lt;

lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);


for (auto e : lt)
{
cout << e << " ";
}
cout << endl;


hhb::list<int>::reverse_iterator rit1 = lt.rbegin();
while (rit1 != lt.rend())
{
cout << *rit1 << " ";
++rit1;
}
cout << endl;


hhb::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
v.push_back(6);

for (auto e : v)
{
cout << e << " ";
}
cout << endl;


hhb::vector<int>::reverse_iterator rit2 = v.rbegin();
while (rit2 != v.rend())
{
cout << *rit2 << " ";
++rit2;
}
cout << endl;

}

在这里插入图片描述

总结

模拟实现（优先级队列）priority_queue：优先级队列、仿函数、反向迭代器等的介绍

原文地址：https://blog.csdn.net/Farewell_me/article/details/142464326

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：翻译：Recent Event Camera Innovations: A Survey
下一篇：一款前后端分离设计的企业级快速开发平台，支持单体服务与微服务之间灵活切换（附源码）

MySQL数据库基础
在过去的mysql中主要是使用的utf8mb3，但是mysql显示的就是utf8，中mysql8中区分显示了。类似于不同的编译器，虽然C/C++的代码是一样的，但是预处理、编译、汇编、链接这些过程却不
阅读更多2024-09-30
Percona Monitoring and Management
Percona Monitoring and Management (PMM)是一款开源的专用于管理和监控MySQL、MongoDB、PostgreSQL。
阅读更多2024-09-30
鸿蒙开发（NEXT/API 12）【已连接穿戴设备查询】手机侧应用开发
Wear Engine提供查询用户已连接的穿戴设备列表（即支持Wear Engine能力且与手机侧运动健康App处于连接状态的穿戴设备）的接口。
阅读更多2024-09-30
Redis数据库
本篇文章介绍了redis的相关知识，并使用springboot集成redis，实现缓存和分布式锁，后续会对文章勘误及更新~~
阅读更多2024-09-30
旧版的存档
【代码】旧版的存档。
阅读更多2024-09-30
Spring Boot 封装统一返回结果及全局异常处理
为了更细致地控制异常处理，我们可以定义一些自定义异常。然后，在全局异常处理器中添加对自定义异常的处理。通过封装统一的返回结果和全局异常处理，我们可以让Spring Boot应用更加健壮和易于维护。这种
阅读更多2024-09-30
【C++】IO流
C++IO流，包含输入输出流、文件流、字符流
阅读更多2024-09-30
低至1元/小时：国庆七天，30元通关《黑神话：悟空》！
随着《黑神话：悟空》自8月20日全球同步上线，正式登陆PC、PS5平台以来，以其精湛的画面和流畅的战斗体验，在发售三天后，该作的全平台销量超过1000万套，打破中国游戏历史记录，被媒体称为“中国首款3
阅读更多2024-09-30
阿里巴巴国际站获取商品详情item_get接口技术分享
item_get API接口是阿里巴巴开放平台提供的一个重要接口，它允许商家通过API调用，获取阿里巴巴平台上的商品详细信息。这些信息包括商品标题、价格、库存、属性、描述等，为商家提供了全面、准确的商
阅读更多2024-09-30
软件测试谣言二三事，认真你就输了
软件测试的职业寿命，取决于互联网行业能存活多久，至少目前看来，这个职业没有消失的风险，至于你能在这个职业待多久，那取决于你自己的能力，我见过不少超过35岁的老员工还在测试的职位上兢兢业业。以广州为例，
阅读更多2024-09-30

模拟实现（优先级队列）priority_queue：优先级队列、仿函数、 反向迭代器等的介绍

文章目录

前言

一、优先级队列

二、仿函数

三、 反向迭代器

总结

相关文章

模拟实现（优先级队列）priority_queue：优先级队列、仿函数、反向迭代器等的介绍

三、反向迭代器