Learning C++ No.18【STL No.8】优先级队列

简介: Learning C++ No.18【STL No.8】优先级队列

引言:

北京时间:2023/3/18/21:47,周末,不摆烂,但是欠钱终于还是遭报应了,导致坐牢7小时(上午3.5,下午3.5),难受,充分意识到行哥是那么的和蔼可亲,励志下次上蛋哥的课可以还清债务(所以下一篇,乃至更多篇博客,都将是关于系统编程的知识);周末时光:昨天12点睡觉,今天7点40起床,然后到9点上课,12:50追一集动漫,1点整睡觉,睡到2点25分起床上第二节课,到6点,下楼丢垃圾,然后洗澡,到7点,开始看最后一节C++的录屏,现在写博客(吃饭都是在上课的时候完成),无论是上午还是下午,牢底坐穿,但是不怕,小强有韧性,记录周末第一天,还行,不怎么摆烂,但是感觉自己似乎也没学什么东西;这篇博客,我们就来学习一下上篇博客谈到的,优先级队列(堆)的实现和反向迭代器等知识。


image.png


自我实现优先级队列(堆)

上篇博客,我们了解到了优先级队列基本使用,就是类似于一个堆的结构(二叉堆),并且大致结构和二叉树是没有什么区别的,所以总的来说,优先级队列有如下几个特点:优先级队列是一个容器适配器,优先级最高的数据是位于堆的顶部(top),并且实现优先级队列,可以使用任意类型的容器(但一般使用vector),了解了这些,此时我们就来正式的自我实现一下优先级队列吧!


结构如图所示:


41.png


功能函数:

empty():检测容器是否为空

size():返回容器中有效元素个数

front():返回容器中第一个元素的引用

push_back():在容器尾部插入元素

pop_back():删除容器尾部元素

如下图:



42.png


如上代码,我们可以发现, 在一个堆中插入和删除数据,为了提高效率最终都需要重新建堆才可以,所以此时就涉及到了两个建堆的函数:adjust_up、adjust_down,所以接下来,让我们一起看一下优先级队列中最关键的两个函数,如下代码:


43.png

在写这两个函数的时候,我们可以和上图(堆的结构图)在脑海中想象,然后结合在一起,可以很好的把代码正确的写出来。


搞定了上述优先级队列中的几个函数关键函数和向上建堆、向下建堆的两个函数,此时优先级队列的大致我们就实现了,但是此时可以发现,在上述的代码中,我们默认都是建一个小堆,如果此时我们要建大堆怎么办,虽然此时是可以通过直接将大于改成小于的方式来实现,但是这样并不是很好,所以此时我们引入一个新概念,也就是昨天浅浅的了解了的仿函数概念。


浅谈仿函数

如下图:

44.png


如上图,我们通过函数重载的形式实现了两个模板类(用于比较大小),此时优先级队列就可以通过调用上述的模板类来实现建大堆和建小堆的直接切换,如下代码所示:

45.png


所以,如上图,当我们使用了仿函数之后,我们就可以直接通过更改模板参数的类型来进行仿函数的切换,来进行大堆和小堆的切换,不需要去使用什么函数指针的方法去调用相应的函数来实现,所以仿函数的发明,就是为了可以让一个模板类(运算符重载)直接被另一个模板类的模板参数使用,然后该模板类直接通过使用模板参数来实现相应的类似函数的功能,不需要使用函数指针,进而调用相应的函数;


总:模板的设计真的非常的牛,什么都可以通过模板的形式进行直接传递和使用


优先级队列完整代码如下:

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
//要明白,此时的堆是一个数组(容器适配器默认是vector),就是使用数组的形式,给我们弄成了一个树的结构,就叫堆
namespace wwx
{
  template<class T>
  struct less//小堆仿函数
  {
    bool operator()(const T& x, const T& y)
    {
      return x < y;
    }
  };
  template<class T, class Container = vector<T>>//建大堆,我们用小于
  struct greater//大堆仿函数
  {
    bool operator()(const T& x, const T& y)
    {
      return x > y;
    }
  };
  template<class T, class Container = vector<T>, class Compare = greater<T>>//此时就可以不需要使用函数指针来调用某个函数了,可以直接使用模板类型来调用仿函数
  class priority_queue
  {
  public:
    void adjust_up(int child)
    {
      int parent = (child - 1) / 2;//这边一定要去把堆排序给复习一下(这个是可以自己推出来的)
      while (child > 0)//建大堆,最坏的情况就是当child为根结点的时候(也就是下标为0的时候),当下标为0就可以停下来了(不然它是会自己break出去的)
      {
        Compare com;
        //if (_con[parent] < _con[child])//建大堆
        if (com(_con[parent], _con[child]))//调用仿函数去比较
        {
          std::swap(_con[parent], _con[child]);
          child = parent;//建大堆(孩子结点大,此时就是让孩子变成父亲,然后重复再去寻找它的父结点)
          parent = (child - 1) / 2;//迭代走走
        }
        else
        {
          break;//此时此时只是向上调整,并不是堆排序
        }
      }
    }
    void adjust_down(int parent)//注意,此时是在类和对象中,所以可以直接使用this指针,所以可以直接使用我们的适配器来存储数据
    {
      int child = parent * 2 + 1;//父亲结点是唯一的,但是孩子结点是有两个
      while (child < _con.size())//这个条件不会写,就是把this指针给漏掉了
      {
        Compare com;
        //if (child + 1 < _con.size() && _con[child] < _con[child + 1])//左孩子小于右孩子(但是前提是右孩子存在,因为有的地方右孩子是不存在的),所以又漏了一个条件
        if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
        //if (child + 1 < _con.size() && Compare()(_con[child], _con[child + 1]))//使用匿名对象的写法
        {
          child += 1;
        }
        //if (_con[parent] < _con[child])//但是这种写法是有一个前提的(那种没有前提的写法要去复习)
        if (com(_con[parent], _con[child]))
        {
          std::swap(_con[parent], _con[child]);
          parent = child;
          child = parent * 2 + 1;//迭代
        }
        else
        {
          break;
        }                                  
      }
    }
    //总结:写这种代码,就是要把堆的结构给深深的烙印在脑海里面(树状结构)
    void push(const T& x)
    {
      _con.push_back(x);
      adjust_up(_con.size() - 1);//尾插数据之后,建堆,通过向上调整的形式
    }
    void pop()//上述是堆的插入,现在是堆的删除
    {//这边可以刚好去把堆排序给复习一下
      std::swap(_con[0], _con[_con.size() - 1]);
      _con.pop_back();
      adjust_down(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(1);
    pq.push(2);
    pq.push(3);
    pq.push(4);
    pq.push(5);
    while (!pq.empty())
    {
      cout << pq.top() << " ";
      pq.pop();
    }
    cout << endl;
  }
}
int main()
{
  wwx::test_priority_queue();
  return 0;
}

反向迭代器

我们当时在学习list的时候,已经将正向迭代器给实现了,所以现在,我们就来实现一下返向迭代器,区分为(我们认为的反向迭代器和源码中的反向迭代器),如下代码:


46.png如上图就是我们认为的,反向迭代器和正向迭代器的实现和区别,但是在真正的源码中却不是如上图中一样,而是实现了更高级的写法,如下代码所示:

47.png



通过上述的结构图,实现代码如下:

48.png



总:反向迭代器的源码是非常的高级的

image.png

总结:周末不摆烂,睡觉啦!

相关文章
|
7月前
|
编译器 C++ 容器
【c++丨STL】基于红黑树模拟实现set和map(附源码)
本文基于红黑树的实现,模拟了STL中的`set`和`map`容器。通过封装同一棵红黑树并进行适配修改,实现了两种容器的功能。主要步骤包括:1) 修改红黑树节点结构以支持不同数据类型;2) 使用仿函数适配键值比较逻辑;3) 实现双向迭代器支持遍历操作;4) 封装`insert`、`find`等接口,并为`map`实现`operator[]`。最终,通过测试代码验证了功能的正确性。此实现减少了代码冗余,展示了模板与仿函数的强大灵活性。
177 2
|
7月前
|
存储 算法 C++
【c++丨STL】map/multimap的使用
本文详细介绍了STL关联式容器中的`map`和`multimap`的使用方法。`map`基于红黑树实现,内部元素按键自动升序排列,存储键值对,支持通过键访问或修改值;而`multimap`允许存在重复键。文章从构造函数、迭代器、容量接口、元素访问接口、增删操作到其他操作接口全面解析了`map`的功能,并通过实例演示了如何用`map`统计字符串数组中各元素的出现次数。最后对比了`map`与`set`的区别,强调了`map`在处理键值关系时的优势。
348 73
|
7月前
|
存储 算法 C++
【c++丨STL】set/multiset的使用
本文深入解析了STL中的`set`和`multiset`容器,二者均为关联式容器,底层基于红黑树实现。`set`支持唯一性元素存储并自动排序,适用于高效查找场景;`multiset`允许重复元素。两者均具备O(logN)的插入、删除与查找复杂度。文章详细介绍了构造函数、迭代器、容量接口、增删操作(如`insert`、`erase`)、查找统计(如`find`、`count`)及`multiset`特有的区间操作(如`lower_bound`、`upper_bound`、`equal_range`)。最后预告了`map`容器的学习,其作为键值对存储的关联式容器,同样基于红黑树,具有高效操作特性。
287 3
|
8月前
|
存储 算法 C++
【c++丨STL】priority_queue(优先级队列)的使用与模拟实现
本文介绍了STL中的容器适配器`priority_queue`(优先级队列)。`priority_queue`根据严格的弱排序标准设计,确保其第一个元素始终是最大元素。它底层使用堆结构实现,支持大堆和小堆,默认为大堆。常用操作包括构造函数、`empty`、`size`、`top`、`push`、`pop`和`swap`等。我们还模拟实现了`priority_queue`,通过仿函数控制堆的类型,并调用封装容器的接口实现功能。最后,感谢大家的支持与关注。
393 1
|
8月前
|
编译器 C++ 开发者
【C++篇】深度解析类与对象(下)
在上一篇博客中,我们学习了C++的基础类与对象概念,包括类的定义、对象的使用和构造函数的作用。在这一篇,我们将深入探讨C++类的一些重要特性,如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象,以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念,提升代码的健壮性、灵活性和可维护性。
|
4月前
|
人工智能 机器人 编译器
c++模板初阶----函数模板与类模板
class 类模板名private://类内成员声明class Apublic:A(T val):a(val){}private:T a;return 0;运行结果:注意:类模板中的成员函数若是放在类外定义时,需要加模板参数列表。return 0;
95 0
|
4月前
|
存储 编译器 程序员
c++的类(附含explicit关键字,友元,内部类)
本文介绍了C++中类的核心概念与用法,涵盖封装、继承、多态三大特性。重点讲解了类的定义(`class`与`struct`)、访问限定符(`private`、`public`、`protected`)、类的作用域及成员函数的声明与定义分离。同时深入探讨了类的大小计算、`this`指针、默认成员函数(构造函数、析构函数、拷贝构造、赋值重载)以及运算符重载等内容。 文章还详细分析了`explicit`关键字的作用、静态成员(变量与函数)、友元(友元函数与友元类)的概念及其使用场景,并简要介绍了内部类的特性。
173 0
|
6月前
|
编译器 C++ 容器
【c++11】c++11新特性(上)(列表初始化、右值引用和移动语义、类的新默认成员函数、lambda表达式)
C++11为C++带来了革命性变化,引入了列表初始化、右值引用、移动语义、类的新默认成员函数和lambda表达式等特性。列表初始化统一了对象初始化方式,initializer_list简化了容器多元素初始化;右值引用和移动语义优化了资源管理,减少拷贝开销;类新增移动构造和移动赋值函数提升性能;lambda表达式提供匿名函数对象,增强代码简洁性和灵活性。这些特性共同推动了现代C++编程的发展,提升了开发效率与程序性能。
186 12
|
7月前
|
设计模式 安全 C++
【C++进阶】特殊类设计 && 单例模式
通过对特殊类设计和单例模式的深入探讨,我们可以更好地设计和实现复杂的C++程序。特殊类设计提高了代码的安全性和可维护性,而单例模式则确保类的唯一实例性和全局访问性。理解并掌握这些高级设计技巧,对于提升C++编程水平至关重要。
132 16
|
8月前
|
编译器 C语言 C++
类和对象的简述(c++篇)
类和对象的简述(c++篇)