AI 助理
备案控制台
开发者社区 云原生 容器服务 文章 正文

【C++】-- STL容器适配器之priority_queue（二）

2023-02-07 144
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
本文涉及的产品
容器镜像服务 ACR，镜像仓库100个 不限时长
简介： 【C++】-- STL容器适配器之priority_queue

三、priority_queue模拟实现

priority_queue底层用堆实现，priority_queue的模拟实现只需要对堆进行封装即可。

1.仿函数

priority_queue默认是大堆，那么该如何实现小堆呢？需要先了解仿函数。

（1）概念

仿函数让一个类的使用看上去像个函数。仿函数是在类中实现了一个operator( )，是一个类的对象，这个类就有了类似函数的行为，所以这个类就是一个仿函数类，目的是为了让函数拥有类的性质。

这个类的对象即仿函数，可以当作一般函数去用，只不过仿函数的功能是在一个类中的运算符operator()中实现的，使用的时候把函数作为参进行传递即可。

（2）优点

① 仿函数比函数指针的执行速度快，函数指针通过地址调用，而仿函数是对运算符operator进行自定义来提高调用的效率。

② 仿函数比一般函数灵活，可以同时拥有两个不同的状态实体，一般函数不具备此种功能。

③ 仿函数可以作为模板参数使用，因为每个仿函数都拥有自己的类型。

（3）缺点

① 需要单独实现一个类。

② 定义形式比较复杂。

（4）实现

先看如下函数isLess，它实现了<的比较

1. #include<iostream>
2. 
3. bool isLess(int l, int r)
4. {
5.  return l < r;
6. }
7. 
8. int main()
9. {
10.   cout << isLess(1, 3) << endl;
11. }

如果在一个类里，实现同样功能，Less这个类就变成了仿函数类，它的对象就是一个仿函数

1. struct less
2. {
3.  bool operator()(int l, int r)
4.  {
5.    return l < r;
6.  }
7. };

这个类还可以再完善一下，使用类模板来支持不同类型的数据使用<比较大小

1. template <class T>
2. struct less
3. {
4.  bool operator()(const T& l, const T& r)
5.  {
6.    return l < r;//<的比较
7.  }
8. };

同样，>的仿函数类也可以实现了：

1. template <class T>
2. struct greater
3. {
4.  bool operator()(const T& l, const T& r)
5.  {
6.    return l > r;//>的比较
7.  }
8. };

如何使用仿函数呢？

1. int main()
2. {
3.  less<int> lessInt;//定义一个仿函数类对象，参数类型指定为int
4.  std::cout << lessInt(1, 3) << std::endl;//对仿函数的调用等价于std::cout << lessInt.operator()(1, 3) << std::endl;
5. }

priority_queue模板中的less替换成greater就可以实现>的比较了：

1. template <class T, class Container = vector<T>,
2. class Compare = greater<typename Container::value_type> > class priority_queue;

2.堆的插入删除

要对priority_queue插入删除，就是在堆上插入删除，堆在物理上是数组，在逻辑上是一颗完全二叉树。根据【数据结构】堆-C语言版一文回忆一下堆的插入删除相关知识

（1）堆的插入（先插入，再向上调整）

（2）堆的删除（先交换，然后删除，再向下调整）

3.代码实现

priority_queue类默认的Container是vector，是自定义类型。因此priority_queue的构造函数、拷贝构造函数、赋值运算符重载函数、析构函数都不用写，会调vector的默认构造函数、拷贝构造函数、赋值运算符重载函数、析构函数。只需要实现7个函数：仿函数<、仿函数>、push、pop、top、size、empty。

（1）仿函数<

1. template<class T>
2. struct less
3. {
4.  bool operator()(const T& l, const T& r)
5.  {
6.    return l < r;
7.  }
8. };

（2）仿函数>

1.  template<class T>
2.  struct greater
3.  {
4.    bool operator()(const T& l, const T& r)
5.    {
6.      return l > r;
7.    }
8.  };

（3）push()

1.  template<class T, class Container = vector<T>,class Compare = delia::less<T>>//指定Compare方式是less，按<比较
2.  class priority_queue
3.  {
4.  public:   
5.    //向上调整算法
6.    void AdjustUp(size_t child)
7.    {
8.      Compare com;//定义仿函数类对象
9. 
10.       size_t parent = (child - 1) / 2;//找父亲的位置
11.       while (child > 0)
12.       {
13.         //if (_con[parent] < _con[child])//父亲比孩子小，孩子就要往上提
14.         if (com(_con[parent] , _con[child]))//使用仿函数比较
15.         {
16.           swap(_con[parent], _con[child]);//交换父亲和孩子
17.           child = parent;//父亲变孩子
18.           parent = (child - 1) / 2;//重新计算新孩子的父亲位置
19.         }
20.         else
21.         {
22.           //父亲>=孩子就不用动
23.           break;
24.         } 
25.       }
26.     }
27. 
28.     //插入
29.     void push(const T& x)
30.     {
31.       _con.push_back(x);//尾插到堆
32.       AdjustUp(_con.size() - 1);//向上调整
33.     }
34. 
35. private:
36.     Container _con;
37.   };

（4）pop()

1.    //向下调整算法
2.    void AdjustDown(size_t parent)
3.    {
4.      Compare com;//定义仿函数类对象
5. 
6.      size_t child = 2 * parent + 1;//找孩子位置
7.      while (child < _con.size())
8.      {
9.        //找大孩子
10.         if (child + 1 < _con.size() && _con[child+1] > _con[child])
11.         {
12.           child++;
13.         }
14. 
15.         //if(_con[parent] < _con[child])父亲比孩子小，父亲就要往下挪
16.         if (com(_con[parent], _con[child]))//使用仿函数比较
17.         {
18.           swap(_con[parent], _con[child]);//交换父亲和孩子
19.           parent = child;//孩子变父亲
20.           child = parent * 2 + 1;//重新计算孩子的位置
21.         }
22.         else
23.         {
24.           break;
25.         }
26.       }
27.     }
28. 
29. //删除
30.     void pop()
31.     {
32.       swap(_con[0], _con[_con.size() - 1]);//交换堆顶元素和堆尾元素
33.       _con.pop_back();//删除堆顶元素      
34.       AdjustDown(0);//向下调整算法
35.     }

（5）top()

1.    //返回priority_queue第一个元素，即堆顶元素
2.    T top()
3.    {
4.      return _con[0];
5.    }

（6）size()

1.    //求priority_queue队列中元素个数
2.    size_t size()
3.    {
4.      return _con.size();
5.    }

（7）empty()

1.    //判断priority_queue是否为空
2.    bool empty()
3.    {
4.      return _con.empty();
5.    }

4.完整代码段

 

018-priority_queue.h

1. #pragma once
2. #include<vector>
3. using namespace std;
4. 
5. namespace delia
6. {
7.  template<class T>
8.  struct less
9.  {
10.     bool operator()(const T& l, const T& r)
11.     {
12.       return l < r;
13.     }
14.   };
15. 
16.   template<class T>
17.   struct greater
18.   {
19.     bool operator()(const T& l, const T& r)
20.     {
21.       return l > r;
22.     }
23.   };
24. 
25.   template<class T, class Container = vector<T>,class Compare = std::less<T>>
26.   class priority_queue
27.   {
28.   public:
29.     //Container默认是vector，自定义类型
30.     //构造函数、拷贝构造函数、赋值运算符重载函数、析构函数都不用写，会调用vector的构造函数和析构函数等
31. 
32. 
33. 
34.     //向上调整算法
35.     void AdjustUp(size_t child)
36.     {
37.       Compare com;//定义仿函数类对象
38. 
39.       size_t parent = (child - 1) / 2;//找父亲的位置
40.       while (child > 0)
41.       {
42.         //if (_con[parent] < _con[child])//父亲比孩子小，孩子就要往上提
43.         if (com(_con[parent] , _con[child]))//使用仿函数比较
44.         {
45.           swap(_con[parent], _con[child]);//交换父亲和孩子
46.           child = parent;//父亲变孩子
47.           parent = (child - 1) / 2;//重新计算新孩子的父亲位置
48.         }
49.         else
50.         {
51.           //父亲>=孩子就不用动
52.           break;
53.         } 
54.       }
55.     }
56. 
57.     //插入
58.     void push(const T& x)
59.     {
60.       _con.push_back(x);//尾插到堆
61.       AdjustUp(_con.size() - 1);//向上调整
62.     }
63. 
64.     //向下调整算法
65.     void AdjustDown(size_t parent)
66.     {
67.       Compare com;//定义仿函数类对象
68. 
69.       size_t child = 2 * parent + 1;//找孩子位置
70.       while (child < _con.size())
71.       {
72.         //找大孩子
73.         if (child + 1 < _con.size() && _con[child+1] > _con[child])
74.         {
75.           child++;
76.         }
77. 
78.         //if(_con[parent] < _con[child])父亲比孩子小，父亲就要往下挪
79.         if (com(_con[parent], _con[child]))//使用仿函数比较
80.         {
81.           swap(_con[parent], _con[child]);//交换父亲和孩子
82.           parent = child;//孩子变父亲
83.           child = parent * 2 + 1;//重新计算孩子的位置
84.         }
85.         else
86.         {
87.           break;
88.         }
89.       }
90.     }
91. 
92.     //删除
93.     void pop()
94.     {
95.       swap(_con[0], _con[_con.size() - 1]);//交换堆顶元素和堆尾元素
96.       _con.pop_back();//删除堆顶元素      
97.       AdjustDown(0);//向下调整算法
98.     }
99. 
100.    //返回priority_queue第一个元素，即堆顶元素
101.    T top()
102.    {
103.      return _con[0];
104.    }
105. 
106.    //求priority_queue队列中元素个数
107.    size_t size()
108.    {
109.      return _con.size();
110.    }
111. 
112.    //判断priority_queue是否为空
113.    bool empty()
114.    {
115.      return _con.empty();
116.    }
117. 
118.  private:
119.    Container _con;
120.  };
121. 
122. }

018-test.cpp

1. #include "018-priority_queue.h"
2. #include<iostream>
3. 
4. void test_priority_queue()
5. {
6.  delia::priority_queue<int> pq;
7.  pq.push(9);
8.  pq.push(26);
9.  pq.push(31);
10.   pq.push(3);
11.   pq.push(11);
12.   pq.push(1);
13.   pq.push(5);
14.   pq.push(39);
15.   pq.push(23);
16.   pq.push(18);
17. 
18.   std::cout << "priority_queue:" << std::endl;
19.   while (!pq.empty())
20.   {
21.     std::cout << pq.top() << std::endl;
22.     pq.pop();
23.   }
24.   std::cout << std::endl;
25. }
26. 
27. void test_priority_queue_push()
28. {
29.   delia::priority_queue<int> pq;
30.   pq.push(9);
31.   pq.push(26);
32.   pq.push(31);
33.   pq.push(3);
34.   pq.push(11);
35.   pq.push(1);
36.   pq.push(5);
37.   pq.push(39);
38.   pq.push(23);
39.   pq.push(18);
40. 
41.   pq.push(83);
42. 
43.   std::cout << "push:" << std::endl;
44.   while (!pq.empty())
45.   {
46.     std::cout << pq.top() << std::endl;
47.     pq.pop();
48.   }
49.   std::cout << std::endl;
50. }
51. 
52. void test_priority_queue_pop()
53. {
54.   delia::priority_queue<int> pq;
55.   pq.push(9);
56.   pq.push(26);
57.   pq.push(31);
58.   pq.push(3);
59.   pq.push(11);
60.   pq.push(1);
61.   pq.push(5);
62.   pq.push(39);
63.   pq.push(23);
64.   pq.push(18);
65. 
66.   std::cout << "pop:" << std::endl;
67.   pq.pop();
68.   while (!pq.empty())
69.   {
70.     std::cout << pq.top() << std::endl;
71.     pq.pop();
72.   }
73.   std::cout << std::endl;
74. }
75. 
76. void test_priority_queue_top()
77. {
78.   delia::priority_queue<int> pq;
79.   pq.push(9);
80.   pq.push(26);
81.   pq.push(31);
82.   pq.push(3);
83.   pq.push(11);
84.   pq.push(1);
85.   pq.push(5);
86.   pq.push(39);
87.   pq.push(23);
88.   pq.push(18);
89. 
90.   std::cout << "top:" << std::endl;
91.   std::cout << pq.top() << std::endl;
92.   std::cout << std::endl;
93. }
94. 
95. void test_priority_queue_size()
96. {
97.   delia::priority_queue<int> pq;
98.   pq.push(9);
99.   pq.push(26);
100.  pq.push(31);
101.  pq.push(3);
102.  pq.push(11);
103.  pq.push(1);
104.  pq.push(5);
105.  pq.push(39);
106.  pq.push(23);
107.  pq.push(18);
108. 
109.  std::cout << "size:" << std::endl;
110.  std::cout << pq.size() << std::endl;
111.  std::cout << std::endl;
112. }
113. 
114. void test_priority_queue_empty()
115. {
116.  delia::priority_queue<int> pq;
117.  pq.push(9);
118.  pq.push(26);
119.  pq.push(31);
120.  pq.push(3);
121.  pq.push(11);
122.  pq.push(1);
123.  pq.push(5);
124.  pq.push(39);
125.  pq.push(23);
126.  pq.push(18);
127. 
128.  std::cout << "empty:" << std::endl;
129.  std::cout << pq.empty() << std::endl;
130.  std::cout << std::endl;
131. }
132. 
133. int main()
134. {
135.  test_priority_queue();
136.  test_priority_queue_push();
137.  test_priority_queue_pop();
138.  test_priority_queue_top();
139.  test_priority_queue_size();
140.  test_priority_queue_empty();
141. 
142.  return 0;
143. 
144. }

运行结果如下

文章标签：
C++
容器
关键词：
C++ stl
C++容器适配器
容器适配器
C++适配器
C++容器
玲娜贝儿～
目录
相关文章
ephemerals__
|
24天前
|
C++ 容器
【c++丨STL】stack和queue的使用及模拟实现
本文介绍了STL中的两个重要容器适配器：栈（stack）和队列（queue）。容器适配器是在已有容器基础上添加新特性或功能的结构，如栈基于顺序表或链表限制操作实现。文章详细讲解了stack和queue的主要成员函数（empty、size、top/front/back、push/pop、swap），并提供了使用示例和模拟实现代码。通过这些内容，读者可以更好地理解这两种数据结构的工作原理及其实现方法。最后，作者鼓励读者点赞支持。 总结：本文深入浅出地讲解了STL中stack和queue的使用方法及其模拟实现，帮助读者掌握这两种容器适配器的特性和应用场景。
ephemerals__
55 21
ephemerals__
|
2月前
|
编译器 C语言 C++
【c++丨STL】list模拟实现（附源码）
本文介绍了如何模拟实现C++中的`list`容器。`list`底层采用双向带头循环链表结构，相较于`vector`和`string`更为复杂。文章首先回顾了`list`的基本结构和常用接口，然后详细讲解了节点、迭代器及容器的实现过程。 最终，通过这些步骤，我们成功模拟实现了`list`容器的功能。文章最后提供了完整的代码实现，并简要总结了实现过程中的关键点。 如果你对双向链表或`list`的底层实现感兴趣，建议先掌握相关基础知识后再阅读本文，以便更好地理解内容。
ephemerals__
42 1
ephemerals__
|
2月前
|
算法 C语言 C++
【c++丨STL】list的使用
本文介绍了STL容器`list`的使用方法及其主要功能。`list`是一种双向链表结构，适用于频繁的插入和删除操作。文章详细讲解了`list`的构造函数、析构函数、赋值重载、迭代器、容量接口、元素访问接口、增删查改操作以及一些特有的操作接口如`splice`、`remove_if`、`unique`、`merge`、`sort`和`reverse`。通过示例代码，读者可以更好地理解如何使用这些接口。最后，作者总结了`list`的特点和适用场景，并预告了后续关于`list`模拟实现的文章。
ephemerals__
69 7
ephemerals__
|
2月前
|
存储 编译器 C语言
【c++丨STL】vector模拟实现
本文深入探讨了 `vector` 的底层实现原理，并尝试模拟实现其结构及常用接口。首先介绍了 `vector` 的底层是动态顺序表，使用三个迭代器（指针）来维护数组，分别为 `start`、`finish` 和 `end_of_storage`。接着详细讲解了如何实现 `vector` 的各种构造函数、析构函数、容量接口、迭代器接口、插入和删除操作等。最后提供了完整的模拟实现代码，帮助读者更好地理解和掌握 `vector` 的实现细节。
ephemerals__
67 0
羑悻的小杀马特
|
2天前
|
编译器 C语言 C++
类和对象的简述（c++篇）
类和对象的简述（c++篇）
羑悻的小杀马特
48 28
RossyYan
|
1月前
|
C++ 芯片
【C++面向对象——类与对象】Computer类（头歌实践教学平台习题）【合集】
声明一个简单的Computer类，含有数据成员芯片（cpu）、内存（ram）、光驱（cdrom）等等，以及两个公有成员函数run、stop。只能在类的内部访问。这是一种数据隐藏的机制，用于保护类的数据不被外部随意修改。根据提示，在右侧编辑器补充代码，平台会对你编写的代码进行测试。成员可以在派生类（继承该类的子类）中访问。成员，在类的外部不能直接访问。可以在类的外部直接访问。为了完成本关任务，你需要掌握。
RossyYan
68 19
RossyYan
|
1月前
|
存储 编译器 数据安全/隐私保护
【C++面向对象——类与对象】CPU类（头歌实践教学平台习题）【合集】
声明一个CPU类，包含等级（rank）、频率（frequency）、电压（voltage）等属性，以及两个公有成员函数run、stop。根据提示，在右侧编辑器补充代码，平台会对你编写的代码进行测试。​ 相关知识 类的声明和使用。 类的声明和对象的声明。 构造函数和析构函数的执行。 一、类的声明和使用 1.类的声明基础 在C++中，类是创建对象的蓝图。类的声明定义了类的成员，包括数据成员（变量）和成员函数（方法）。一个简单的类声明示例如下： classMyClass{ public: int
RossyYan
50 13
RossyYan
|
1月前
|
编译器 数据安全/隐私保护 C++
【C++面向对象——继承与派生】派生类的应用（头歌实践教学平台习题）【合集】
本实验旨在学习类的继承关系、不同继承方式下的访问控制及利用虚基类解决二义性问题。主要内容包括： 1. **类的继承关系基础概念**：介绍继承的定义及声明派生类的语法。 2. **不同继承方式下对基类成员的访问控制**：详细说明`public`、`private`和`protected`继承方式对基类成员的访问权限影响。 3. **利用虚基类解决二义性问题**：解释多继承中可能出现的二义性及其解决方案——虚基类。 实验任务要求从`people`类派生出`student`、`teacher`、`graduate`和`TA`类，添加特定属性并测试这些类的功能。最终通过创建教师和助教实例，验证代码
RossyYan
50 5
RossyYan
|
1月前
|
存储 算法 搜索推荐
【C++面向对象——群体类和群体数据的组织】实现含排序功能的数组类（头歌实践教学平台习题）【合集】
1. **相关排序和查找算法的原理**：介绍直接插入排序、直接选择排序、冒泡排序和顺序查找的基本原理及其实现代码。 2. **C++ 类与成员函数的定义**：讲解如何定义`Array`类，包括类的声明和实现，以及成员函数的定义与调用。 3. **数组作为类的成员变量的处理**：探讨内存管理和正确访问数组元素的方法，确保在类中正确使用动态分配的数组。 4. **函数参数传递与返回值处理**：解释排序和查找函数的参数传递方式及返回值处理，确保函数功能正确实现。 通过掌握这些知识，可以顺利地将排序和查找算法封装到`Array`类中，并进行测试验证。编程要求是在右侧编辑器补充代码以实现三种排序算法
RossyYan
40 5
RossyYan
|
1月前
|
Serverless 编译器 C++
【C++面向对象——类的多态性与虚函数】计算图像面积（头歌实践教学平台习题）【合集】
本任务要求设计一个矩形类、圆形类和图形基类，计算并输出相应图形面积。相关知识点包括纯虚函数和抽象类的使用。 **目录：** - 任务描述 - 相关知识 - 纯虚函数 - 特点 - 使用场景 - 作用 - 注意事项 - 相关概念对比 - 抽象类的使用 - 定义与概念 - 使用场景 - 编程要求 - 测试说明 - 通关代码 - 测试结果 **任务概述：** 1. **图形基类（Shape）**：包含纯虚函数 `void PrintArea()`。 2. **矩形类（Rectangle）**：继承 Shape 类，重写 `Print
RossyYan
48 4
云原生

容器服务

热门文章

最新文章

  • 1
    Docker 镜像加速器
  • 2
    Docker CE 镜像源站
  • 3
    Minikube - Kubernetes本地实验环境
  • 4
    Docker的Windows容器初体验
  • 5
    Docker学习路线图 (持续更新中)
  • 6
    当 Kubernetes 遇到阿里云
  • 7
    基于Docker容器的，Jenkins、GitLab构建持续集成CI
  • 8
    容器镜像服务 Docker镜像的基本使用
  • 9
    利用Helm简化Kubernetes应用部署
  • 10
    理解Docker容器的进程管理
  • 1
    【赵渝强老师】K8s中Pod探针的TCPSocketAction
    150
  • 2
    【赵渝强老师】K8s中Pod探针的ExecAction
    55
  • 3
    【赵渝强老师】K8s中Pod探针的HTTPGetAction
    47
  • 4
    【赵渝强老师】Kubernetes中Pod的探针
    71
  • 5
    容器服务：智算时代云原生操作系统及月之暗面Kimi、深势科技实践分享
    118
  • 6
    canal-starter 监听解析 storeValue 不一样，同样的sql 一个在mybatis执行 一个在数据库操作，导致解析不出正确对象
    70
  • 7
    【Docker最新版教程】一文带你快速入门Docker常见用法，实现容器编排和自动化部署上线项目
    512
  • 8
    【最新版正确姿势】Docker安装教程（简单几步即可完成）
    3749
  • 9
    ​​国内 5 个最佳的控制面板，可轻松管理服务器
    274
  • 10
    【赵渝强老师】K8s的有状态控制器StatefulSet
    158

    • 相关课程

    更多
  • 容器持久化储存训练营
  • 现代应用容器技术快速入门
  • 云计算、容器和云原生基础课程
  • Serverless 容器从入门到精通: - Serverless Kubernetes
  • 容器安全与Palo Alto Networks解决方案
  • C++ 入门教程开发文档

    • 相关电子书

    更多
  • 使用CNFS搭建弹性Web服务
  • 阿里云文件存储 NAS 在容器场景的最佳实践
  • 何种数据存储才能助力容器计算

    • 相关实验场景

    更多
  • 基于ACK Serverless实现容器应用弹性伸缩
  • 容器中的volume卷
  • 容器的文件系统挂载
  • 容器的配置和存储
  • 容器DevSecOps全链路体验
  • 容器的共享网络模型
    • 下一篇
    PAI Model Gallery 支持云上一键部署 DeepSeek-V3、DeepSeek-R1 系列模型