C++:优先级队列模拟实现和仿函数的概念使用

简介: C++:优先级队列模拟实现和仿函数的概念使用

本篇总结优先级队列

使用方法

首先在官网查看它的一些用法

template <class T, class Container = vector<T>,
  class Compare = less<typename Container::value_type> > class priority_queue;

从它的介绍可以看出,也是一个用到了容器适配器的容器,这里不同于stackqueue的适配器,这里使用的是vector作为它的适配器,也是用了模板来实例化,但是多了一个Compare的概念,关于Compare后面来引入

具体用法:

Priority queue

Priority queues are a type of container adaptors, specifically designed such that its first element is always the greatest of the elements it contains, according to some strict weak ordering criterion.

This context is similar to a heap, where elements can be inserted at any moment, and only the max heap element can be retrieved (the one at the top in the priority queue).

Priority queues are implemented as container adaptors, which are classes that use an encapsulated object of a specific container class as its underlying container, providing a specific set of member functions to access its elements. Elements are popped from the “back” of the specific container, which is known as the top of the priority queue.

The underlying container may be any of the standard container class templates or some other specifically designed container class. The container shall be accessible through random access iterators and support the following

从上面的英文中可以很明显的获取到信息,它的用法和堆非常类似,因此对应的接口设计也很像,下面用实验来简单使用一下

#include <iostream>
#include <queue>
using namespace std;
int main()
{
  priority_queue<int> pq;
  pq.push(3);
  pq.push(2);
  pq.push(1);
  pq.push(4);
  while (!pq.empty())
  {
    cout << pq.top() << " ";
    pq.pop();
  }
  return 0;
}

上面是对优先级队列的简单使用,从中可以看出,在队列中添加了3,2,1,4四个元素,但是最后输出的确实4,3,2,1,证明它确实是和堆是一样的,那么基于这个原理就可以对它进行模拟实现了,具体实现如下:

// Version1--初级版本
#include <iostream>
#include <vector>
using namespace std;
namespace my_priority_queue
{
  template<class T, class Container = vector<int>>
  class priority_queue
  {
  public:
    bool empty()
    {
      return _con.empty();
    }
    size_t size()
    {
      return _con.size();
    }
    const T& top()
    {
      return _con.front();
    }
    void adjust_up(int child)
    {
      int parent = (child - 1) / 2;
      while (child > 0)
      {
        if (_con[parent] < _con[child])
        {
          swap(_con[parent], _con[child]);
          child = parent;
          parent = (child - 1) / 2;
        }
        else
        {
          break;
        }
      }
    }
    void push(const T& x)
    {
      _con.push_back(x);
      adjust_up(_con.size() - 1);
    }
    void adjust_down(int parent)
    {
      int child = parent * 2 + 1;
      while (child < _con.size())
      {
        if (child + 1 < _con.size() && _con[child + 1] > _con[child])
        {
          child++;
        }
        if (_con[parent] < _con[child])
        {
          swap(_con[parent], _con[child]);
          parent = child;
          child = parent * 2 + 1;
        }
        else
        {
          break;
        }
      }
    }
    void pop()
    {
      swap(_con[0], _con[_con.size() - 1]);
      _con.pop_back();
      adjust_down(0);
    }
  private:
    Container _con;
  };
}

整体来说实现难度不大,只是需要对于向上和向下调整算法要熟悉,有了这两个算法解决问题并不难,但是这样的实现虽然可以适配前面的测试用例,但是并不是库内实现的方法,库内的实现还有一个Compare的概念

Compare仿函数

对于库内的函数,只能实现降序排序,很明显库内不可能只支持降序输出,那么如何控制降序输出?

库中定义的仿函数默认是less,与之对应的还有greater,如果使用greater就将是升序输出:

int main()
{
  priority_queue<int,vector<int>,less<int>> pq1;
  pq1.push(3);
  pq1.push(2);
  pq1.push(1);
  pq1.push(4);
  cout << "降序排列:" << endl;
  while (!pq1.empty())
  {
    cout << pq1.top() << " ";
    pq1.pop();
  }
  cout << endl;
  priority_queue<int, vector<int>, greater<int>> pq2;
  pq2.push(3);
  pq2.push(2);
  pq2.push(1);
  pq2.push(4);
  cout << "升序排列:" << endl;
  while (!pq2.empty())
  {
    cout << pq2.top() << " ";
    pq2.pop();
  }
  cout << endl;
  return 0;
}
// 输出结果
降序排列:
4 3 2 1
升序排列:
1 2 3 4

那么这个lessgreater到底是什么?由此引出下面仿函数的概念

在前面实现的Version1的实现中,并没有实现这个功能,这是由于在建堆的时候,建立的是大堆还是小堆已经限定了,但是在实际的应用中这里不应该被限定,应该根据实际情况创建对应的堆,但是代码逻辑只能根据大于和小于来判断,由此引出可以使用仿函数来实现这个功能

template<class T>
class Less
{
public:
  bool operator()(const T& x, const T& y)
  {
    return x < y;
  }
};
template<class T>
class Greater
{
public:
  bool operator()(const T& x, const T& y)
  {
    return x > y;
  }
};

上面就是对于仿函数的定义,其实从中可以看出仿函数其实就是一个只有一个函数的类,里面定义了运算符重载,而当程序执行到需要进行比大小的时候,就可以借助这个运算符重载得出结论,进而执行,这样就实现了改变大小于关系的函数

根据这个原理,就可以实现下面的过程:

// Version2
// 头文件
#include <iostream>
#include <vector>
using namespace std;
namespace my_priority_queue
{
  template<class T, class Container = vector<int>, class Compare = Less<class T> >
  class priority_queue
  {
  public:
    bool empty()
    {
      return _con.empty();
    }
    size_t size()
    {
      return _con.size();
    }
    const T& top()
    {
      return _con.front();
    }
    void adjust_up(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;
        }
      }
    }
    void push(const T& x)
    {
      _con.push_back(x);
      adjust_up(_con.size() - 1);
    }
    void adjust_down(int parent)
    {
      Compare com;
      int child = parent * 2 + 1;
      while (child < _con.size())
      {
        if (child + 1 < _con.size() && 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[0], _con[_con.size() - 1]);
      _con.pop_back();
      adjust_down(0);
    }
  private:
    Container _con;
  };
}

// main.c文件
#include <iostream>
#include <queue>
#include "priority_queue.h"
using namespace std;
template<class T>
class Less
{
public:
  bool operator()(const T& x, const T& y)
  {
    return x < y;
  }
};
template<class T>
class Greater
{
public:
  bool operator()(const T& x, const T& y)
  {
    return x > y;
  }
};
void test1()
{
  my_priority_queue::priority_queue<int, vector<int>, Less<int>> pq1;
  pq1.push(3);
  pq1.push(2);
  pq1.push(1);
  pq1.push(4);
  cout << "降序排列:" << endl;
  while (!pq1.empty())
  {
    cout << pq1.top() << " ";
    pq1.pop();
  }
  cout << endl;
  my_priority_queue::priority_queue<int, vector<int>, Greater<int>> pq2;
  pq2.push(3);
  pq2.push(2);
  pq2.push(1);
  pq2.push(4);
  cout << "升序排列:" << endl;
  while (!pq2.empty())
  {
    cout << pq2.top() << " ";
    pq2.pop();
  }
  cout << endl;
}
int main()
{
  test1();
  return 0;
}

具体的指向演示如下:

一些场景

其实仿函数的应用场景很多,这里说比较基础的场景

例如算法库中存在的sort排序函数,其实也是有仿函数的存在的

template <class RandomAccessIterator>
  void sort (RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class Compare>
  void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

于是可以利用这些函数实现效果

void test2()
{
  Less<int> com;
  int arr[] = { 7,6,5,4,3,9,8,6 };
  int sz = sizeof(arr) / sizeof(arr[0]);
  sort(arr, arr + sz, com);
  for (auto ch : arr)
  {
    cout << ch << " ";
  }
  cout << endl;
  Greater<int> comp;
  sort(arr, arr + sz, comp);
  for (auto ch : arr)
  {
    cout << ch << " ";
  }
  cout << endl;
}

模板参数和函数参数

对比模板参数和函数参数:

// 模板参数
template<class T, class Container = vector<int>, class Compare = Less<class T> >
my_priority_queue::priority_queue<int, vector<int>, Greater<int>> pq;
// 函数参数
sort(arr, arr + sz, Less<int>());

对于这里需要注意的是,模板参数内传的是类的名字,而函数传参传的是对象,因此上面的写法其实是匿名对象的写法

相关文章
|
30天前
|
存储 算法 调度
【C++打怪之路Lv11】-- stack、queue和优先级队列
【C++打怪之路Lv11】-- stack、queue和优先级队列
32 1
|
1月前
|
程序员 C++ 开发者
C++入门教程:掌握函数重载、引用与内联函数的概念
通过上述介绍和实例,我们可以看到,函数重载提供了多态性;引用提高了函数调用的效率和便捷性;内联函数则在保证代码清晰的同时,提高了程序的运行效率。掌握这些概念,对于初学者来说是非常重要的,它们是提升C++编程技能的基石。
21 0
|
2月前
|
C++
C++(十七)仿函数
### Functor 仿函数简介 Functor(仿函数)是一种通过在类中实现 `operator()` 使其行为像函数的对象。这种方式可以让类拥有更多可定制的功能,同时保持函数般的简洁调用方式。下面展示了如何定义和使用一个计算幂运算的仿函数类,并通过示例说明了其在 `std::sort` 中的优势与灵活性。
|
4月前
|
JSON Go C++
开发与运维C++问题之在iLogtail新架构中在C++主程序中新增插件的概念如何解决
开发与运维C++问题之在iLogtail新架构中在C++主程序中新增插件的概念如何解决
45 1
|
4月前
|
存储 算法 Java
【C++】优先级队列priority_queue模拟实现&&仿函数
【C++】优先级队列priority_queue模拟实现&&仿函数
38 1
|
4月前
|
C++ 开发者
C++一分钟之-概念(concepts):C++20的类型约束
【7月更文挑战第4天】C++20引入了Concepts,提升模板编程的类型约束和可读性。概念定义了模板参数需遵循的规则。常见问题包括过度约束、约束不完整和重载决议复杂性。避免问题的关键在于适度约束、全面覆盖约束条件和理解重载决议。示例展示了如何用Concepts限制模板函数接受的类型。概念将增强模板的安全性和灵活性,但需谨慎使用以防止错误。随着C++的发展,Concepts将成为必备工具。
92 2
|
5月前
|
C++
C++一分钟之-继承与多态概念
【6月更文挑战第21天】**C++的继承与多态概述:** - 继承允许类从基类复用代码,增强代码结构和重用性。 - 多态通过虚函数实现,使不同类对象能以同一类型处理。 - 关键点包括访问权限、构造/析构、菱形问题、虚函数与动态绑定。 - 示例代码展示如何创建派生类和调用虚函数。 - 注意构造函数初始化、空指针检查和避免切片问题。 - 应用这些概念能提升程序设计和维护效率。
39 2
|
5月前
|
算法 安全 编译器
【C++进阶】模板进阶与仿函数:C++编程中的泛型与函数式编程思想
【C++进阶】模板进阶与仿函数:C++编程中的泛型与函数式编程思想
49 1
|
4月前
|
C++ 开发者
C++一分钟之-概念(concepts):C++20的类型约束
【7月更文挑战第6天】C++20引入了Concepts,提升模板编程的精确性和可读性。概念允许设定模板参数的编译时约束。常见问题包括过度约束、不完整约束及重载决议复杂性。要避免这些问题,需适度约束、全面覆盖约束条件并理解重载决议。示例展示了如何定义和使用`Incrementable`概念约束函数模板。概念是C++模板编程的强大力量,但也需谨慎使用以优化效率和代码质量。
101 0
|
4月前
|
存储 算法 C语言
【C++】详解STL的适配器容器之一:优先级队列 priority_queue
【C++】详解STL的适配器容器之一:优先级队列 priority_queue