12306网站为什么做不好,奉贤区专业建网站,wordpress 功能 删除,如何申请百度定位地址W...Y的主页 #x1f60a;
代码仓库分享#x1f495; #x1f354;前言#xff1a; 在C的宇宙中#xff0c;优先队列似乎是一座巨大的宝库#xff0c;藏匿着算法的珍宝。而就在这片代码的天空下#xff0c;我们不仅可以探索优先队列的神奇#xff0c;还能够揭开反向迭…
W...Y的主页
代码仓库分享 前言 在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
#includevector
#includeiostream
#includevector
#includedeque
#includestdbool.h
using namespace std;
namespace why
{templateclass T, class Container vectorTclass 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中直接调用。
注意这里我们在函数模板中未加入第三个参数进行参数这里我们在最后实现。原模板接口的缺省默认参数为lessT是构建大堆的所以我们模拟中是先建立大堆。、
往vector中push数据时就要建立大堆进行排序pop数据得使用向下调整对堆中的数据重新排序成为大堆所以建立大堆就是使用数据结构中的向上调整函数进行操作而pop数据是用向下调整的方法进行。
如果对堆这一块的不太了解可以一下文章
堆的基本实现——数据结构https://blog.csdn.net/m0_74755811/article/details/132794715?spm1001.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函数的第三个默认缺省参数为lessT如果我们传greaterT才可以创建小堆。而我们模拟的函数中创建大小堆只不过是将其比较符号进行转换即可。所以我们就可以使用仿函数创建两个不同类型的进行调用。
#pragma once
#includevector
#includeiostream
#includevector
#includedeque
#includestdbool.h
using namespace std;
namespace why
{templateclass Tstruct less{bool operator()(const T x, const T y){return x y;}};templateclass Tstruct greater{bool operator()(const T x, const T y){return x y;}};templateclass T, class Container vectorT, class Compare lessTclass 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节点也就是尾节点即可。
templateclass T, class Ref, class Ptr
struct __list_reverse_iterator
{typedef list_nodeT node;typedef __list_reverse_iteratorT, 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_OPERATORpointer 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
{templateclass Iterator, class Refstruct ReverseIterator{typedef ReverseIteratorIterator, 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中优先队列的本质并感受到了反向迭代器的便利之处。这不仅是一次代码之旅更是对数据结构和算法的深刻思考是对编程艺术的一次追求和探索。
或许在未来的编程征途中你会在实际项目中运用这些知识创造出更为强大、高效的代码。无论何时何地优先队列和反向迭代器的魔法都将伴随着你成为解决问题的得力工具。
让我们怀着对编码奇迹的敬畏之心结束这段代码的冒险。愿你的代码之路充满创造与探索愿你的算法之舞永远翩翩起舞。编码的世界里冒险永不止步期待着你下一次的代码奇迹。
