W…Y的主页 😊
代码仓库分享💕
![[C++历练之路]优先级队列||反向迭代器的模拟实现](https://img-blog.csdnimg.cn/8c6b11c7767544a9ba3c4bab8079a6a2.gif)
🍔前言：
在C++的宇宙中，优先队列似乎是一座巨大的宝库，藏匿着算法的珍宝。而就在这片代码的天空下，我们不仅可以探索优先队列的神奇，还能够揭开反向迭代器的神秘面纱。让我们一同踏入这个编程的探险之旅，在这里，我们将用C++语言创造出一个能按照优先级排列元素的神奇容器，并且探索反向迭代器的魅力，仿佛是在编码的星空下追逐着闪烁的代码流星。准备好了吗？让我们迈出第一步，开启这段惊险又充满奇迹的模拟之旅。
目录
了解priority_queue
模拟实现priority_queue
构建基本框架
仿函数的介绍以及第三个参数添加
反向迭代器的模板实现
了解priority_queue
1. 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
2. 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。
3. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。
4. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：
empty()：检测容器是否为空
size()：返回容器中有效元素个数
front()：返回容器中第一个元素的引用
push_back()：在容器尾部插入元素op_back()：删除容器尾部元素
5. 标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。
6. 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。
优先队列其实就是数据结构中的堆，而我们想要进行其实现必须掌握其模板。
默认情况下，priority_queue是大堆，而第一个模板参数class T就是其对应的数据类型，第二个模板参数是其数据结构的类型，缺省值为vector，所以其默认的结构类型就是数组，不是链式结构类型的堆，如果在priority_queue中放自定义类型的数据，用户需要在自定义类型中提供> 或者< 的重载。第三个模板类型就是一种仿函数，其可以操控其创建的是大堆还是小堆。
所以我们要用堆的思想来模拟实现优先队列！
模拟实现priority_queue
构建基本框架
首先我们可以照猫画虎，仿照其参数模板进行仿写：
#pragma once
#include<vector>
#include<iostream>
#include<vector>
#include<deque>
#include<stdbool.h>
using namespace std;
namespace why
{
template<class T, class Container = vector<T>>
class priority_queue
{
public:
void push(const T& x)
{
_con.push_back(x);
adjust_up(_con.size() - 1);
}
void pop()
{
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
adjust_down(0);
}
T& top()
{
return _con[0];
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
private:
Container _con;
};
我们将基本函数框架打好，将优先队列的基本函数接口完善，这些都是我们复用的vector、list、deque等接口，可以直接从STL中直接调用。
注意：这里我们在函数模板中未加入第三个参数进行参数，这里我们在最后实现。原模板接口的缺省默认参数为less<T>，是构建大堆的，所以我们模拟中是先建立大堆。、
往vector中push数据时就要建立大堆进行排序，pop数据得使用向下调整对堆中的数据重新排序成为大堆，所以建立大堆就是使用数据结构中的向上调整函数进行操作，而pop数据是用向下调整的方法进行。
如果对堆这一块的不太了解，可以一下文章：
堆的基本实现——数据结构
https://blog.csdn.net/m0_74755811/article/details/132794715?spm=1001.2014.3001.5502向上调整：
void adjust_up(size_t child)
{
//Compare com;
size_t parent = (child - 1) / 2;
while (child > 0)
{
if (_con[child] > _con[parent])
//if (com(_con[parent],_con[child]))
{
swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}向下调整：
void adjust_down(size_t parent)
{
//Compare com;
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() && com(_con[child], _con[child + 1]))
{
child++;
}
if(_con[child] > _con[parent])
//if (com(_con[parent], _con[child]))
{
swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}仿函数的介绍以及第三个参数添加
在C++中，仿函数（Functor）是一种重载了函数调用操作符 operator() 的对象。它实际上是一个类或者结构体，通过重载 operator()，使得该对象可以像函数一样被调用。仿函数可以像函数一样接受参数，并返回结果，同时可以包含状态信息，因此它们在C++中被广泛用于实现函数对象，作为算法的参数传递，或者用于定义自定义的操作。
通过仿函数，可以实现自定义的比较、排序、转换或者其他操作，这些操作可以被算法直接使用，例如在标准库中的排序算法 std::sort、查找算法 std::find，或者容器类中的自定义排序规则等。使用仿函数可以提供更大的灵活性，使得算法能够适应不同的需求。
下面是一个简单的示例，展示了一个自定义的仿函数用于比较两个整数的大小：
#include <iostream>
// 定义一个比较器仿函数
struct Compare {
bool operator()(int a, int b) const {
return a < b; // 自定义的比较规则：a < b
}
};
int main() {
Compare cmp; // 创建比较器对象
int x = 5, y = 10;
if (cmp(x, y)) {
std::cout << "x is less than y." << std::endl;
} else {
std::cout << "x is greater than or equal to y." << std::endl;
}
return 0;
}
在这个示例中，Compare 结构体重载了 operator()，定义了一个比较规则，判断第一个参数是否小于第二个参数。然后在 main 函数中，创建了一个 Compare 类型的对象 cmp，并使用它进行比较操作。
因此，仿函数是C++中的一种强大机制，可以扩展函数的行为，提供更灵活的功能，并允许开发者以更抽象的方式定义特定操作。
所以我们可以使用仿函数针对第三个参数。
priority_queue函数的第三个默认缺省参数为less<T>，如果我们传greater<T>才可以创建小堆。而我们模拟的函数中创建大小堆只不过是将其比较符号进行转换即可。所以我们就可以使用仿函数创建两个不同类型的进行调用。
#pragma once
#include<vector>
#include<iostream>
#include<vector>
#include<deque>
#include<stdbool.h>
using namespace std;
namespace why
{
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;
}
};
template<class T, class Container = vector<T>, class Compare = less<T>>
class priority_queue
{
public:
void adjust_up(size_t child)
{
Compare com;
size_t parent = (child - 1) / 2;
while (child > 0)
{
//if (_con[child] > _con[parent])
if (com(_con[parent],_con[child]))
{
swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void adjust_down(size_t parent)
{
Compare com;
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() && com(_con[child], _con[child + 1]))
{
child++;
}
//if(_con[child] > _con[parent])
if (com(_con[parent], _con[child]))
{
swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void push(const T& x)
{
_con.push_back(x);
adjust_up(_con.size() - 1);
}
void pop()
{
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
adjust_down(0);
}
T& top()
{
return _con[0];
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
private:
Container _con;
};
这样我们只需要在模拟函数中创建一个模板变量即可在函数中进行调用。
反向迭代器的模板实现
在STL中的所有容器里都有迭代器与反向迭代器，而在每个容器的模拟实现中我们也将其进行复现。string、vector中的迭代器都可以类似与指针，因为其底层的存储物理空间是连续的，我们可以很好的进行重定义使用。但是list却不行，因为空间是不连续的，所以我们得重新定义封装出一个类迭代器的重定义，将其运算符进行重载成合理的进行使用。
而反向迭代器中我们可以将list中封装的迭代器进行复制粘贴修改，就可以正确使用。
rend指向头节点，而rbegin指向_head->_prev节点，也就是尾节点即可。
template<class T, class Ref, class Ptr>
struct __list_reverse_iterator
{
typedef list_node<T> node;
typedef __list_reverse_iterator<T, Ref, Ptr> self;
node* _node;
__list_reverse_iterator(node* n)
:_node(n)
{}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
self& operator++()
{
_node = _node->_prev;
return *this;
}
self operator++(int)
{
self tmp(*this);
_node = _node->_prev;
return tmp;
}
self& operator--()
{
_node = _node->_next;
return *this;
}
self operator--(int)
{
self tmp(*this);
_node = _node->_next;
return tmp;
}
bool operator!=(const self& s)
{
return _node != s._node;
}
bool operator==(const self& s)
{
return _node == s._node;
}
};我们只需要将++、–运算符进行重载即可。将++指向当前节点的_prev节点，而–指向当前节点的_next节点。
那我们看一下STL-list中的反向迭代器是怎么写的：
class reverse_bidirectional_iterator {
typedef reverse_bidirectional_iterator<_BidirectionalIterator, _Tp,
_Reference, _Distance> _Self;
protected:
_BidirectionalIterator current;
public:
typedef bidirectional_iterator_tag iterator_category;
typedef _Tp value_type;
typedef _Distance difference_type;
typedef _Tp* pointer;
typedef _Reference reference;
reverse_bidirectional_iterator() {}
explicit reverse_bidirectional_iterator(_BidirectionalIterator __x)
: current(__x) {}
_BidirectionalIterator base() const { return current; }
_Reference operator*() const {
_BidirectionalIterator __tmp = current;
return *--__tmp;
}
#ifndef __SGI_STL_NO_ARROW_OPERATOR
pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */
_Self& operator++() {
--current;
return *this;
}
_Self operator++(int) {
_Self __tmp = *this;
--current;
return __tmp;
}
_Self& operator--() {
++current;
return *this;
}
_Self operator--(int) {
_Self __tmp = *this;
++current;
return __tmp;
}
};
STL中的反向迭代器是封装了正向迭代器，构造一个反向迭代器了。正向迭代器的++就是反向迭代器的–，而正向迭代器的–就是反向迭代器的++。
注意：STL源码中的复用代码rbegin()与rend()的源码为：
直接返回的是其正向迭代器的begin()与end()，所以其解引用的内容就要发生变化：
其结构就不同：
与原来的结构是不同的。
我们可以自己封装一个类进行使用：
#pragma once
namespace why
{
template<class Iterator, class Ref>
struct ReverseIterator
{
typedef ReverseIterator<Iterator, Ref> Self;
Iterator _cur;
ReverseIterator(Iterator it)
:_cur(it)
{}
Ref operator*()
{
Iterator tmp = _cur;
--tmp;
return *tmp;
}
Self& operator++()
{
--_cur;
return *this;
}
Self& operator--()
{
++_cur;
return *this;
}
bool operator!=(const Self& s)
{
return _cur != s._cur;
}
};
}但是这样复用正向迭代器与刚才的写法所表达的写法是一样的，为什么还要这样单独创建一个类呢？因为list的正向迭代器就是进行封装的，可以复用。但是string、vector的正向迭代器就是指针就不能进行此操作了，所以我们必须复用。
总结：
在这段代码的奇妙旅程中，我们成功地创造了一个C++中的优先队列，仿佛编织了一个可以按照优先级排序元素的魔法网。这个队列不仅仅是一段代码，更是算法的交响乐，奏响着排序、插入、删除的优美旋律。而更加令人惊叹的是，我们在这个编码的仙境中，还揭开了反向迭代器的神秘面纱，为我们的容器增添了一抹独特的色彩。
通过这个模拟实现，我们深入理解了C++中优先队列的本质，并感受到了反向迭代器的便利之处。这不仅是一次代码之旅，更是对数据结构和算法的深刻思考，是对编程艺术的一次追求和探索。
或许，在未来的编程征途中，你会在实际项目中运用这些知识，创造出更为强大、高效的代码。无论何时何地，优先队列和反向迭代器的魔法都将伴随着你，成为解决问题的得力工具。
让我们怀着对编码奇迹的敬畏之心，结束这段代码的冒险。愿你的代码之路充满创造与探索，愿你的算法之舞永远翩翩起舞。编码的世界里，冒险永不止步，期待着你下一次的代码奇迹。
文章出处登录后可见！
