【c++】STL-容器适配器priority_queue与仿函数
·
- priority_queue（优先级队列）基本情况：priority_queue是一种容器适配器，它的逻辑结构跟堆差不多，默认是大堆；物理结构要看底层容器，默认是vector，也可以用deque。上面是大根堆与小根堆的逻辑结构。
默认底层容器是vector的原因：因为它的下标访问速率更快。不支持list作为底层容器，因为list仅提供双向迭代器，而priority_queue需要的是随机迭代器。
在这里插入图片描述
- 以上是 priority_queue提供的一些接口，接下来我来简要的说明一些常用接口的作用：
- (constructor)：构造函数，用于构造 priority_queue 类对象。其中系统自动生成的无参默认构造和范围(迭代器区间)构造用得比较多。
- empty()：判断priority_queue对象是否为空。
- size()：返回 priority_queue对象里元素的个数。
- top()：返回优先级队列顶部的元素，即堆顶元素。
- push()：压入一个元素。
- pop()：移除优先级队列顶部元素，它没有返回值，不会返回被移除的元素值。
2. 使用
在这里插入图片描述
关于priority_queue对象的创建：能够看到，priority_queue这个容器适配器有三个模板参数，依次是：T: 接收存储元素的类型，Container：接收底层容器的类型，Compare：接收比较器（一般传递仿函数类类型，之后会讲到）的类型。其中后面两个模板参数都有默认值，在进行实例化对象时可以不用传递参数。
代码语言：javascript
AI代码解释
//使用priority_queue时要包含头文件queue
priority_queue<int> pq1;
关于Container：vector是默认容器，我们也可以根据需求来改变底层容器，比如deque。
代码语言：javascript
AI代码解释
priority_queue<int, deque<int>> pq2;
关于Compare：默认值是less这个仿函数类型，因为它，priority_queue对象里大的数据的优先级更高，是大堆结构。我们可以传递另一个仿函数类型greater，这样是小堆结构，小的数据的优先级更高。比如下列代码：
代码语言：javascript
AI代码解释
priority_queue<int> pq1;
priority_queue<int, deque<int>> pq2;
//要传递第三个参数的话，第二个参数的值也不能漏掉
priority_queue<int, vector<int>, greater<int>> pq3;
pq1.push(1);
pq1.push(2);
pq1.push(3);
pq1.push(4);
pq3.push(1);
pq3.push(2);
pq3.push(3);
pq3.push(4);
cout << "less: ";
while (!pq1.empty())
{
cout << pq1.top() << " ";
pq1.pop();
}
cout << endl;
cout << "greater: ";
while (!pq3.empty())
{
cout << pq3.top() << " ";
pq3.pop();
}
在这里插入图片描述
- 由于priority_queue也是不支持迭代器（迭代器能提供随机访问）的，所以其对象的遍历需要用到top()与pop()接口来实现。
- less -> " < " 大堆
- greater -> " > " 小堆
它跟我们平常的思维习惯是反着来的，这一点要注意。其中的 < 与 > 是关于它的实现，可以参考下面的仿函数章节。
- 不要搞混sort里面的Compare与priority_queue的Compare：sort是一个函数模板，而priority_queue是一个类模板。一个是函数模板类型参数，接收的是对象；一个是类模板参数，接收的是类型。
在这里插入图片描述
- 一般比较器接收的是仿函数类类型的原因：比较器通常接收仿函数类类型而非函数指针或其他形式，一部分原因是因为类型的传递。就比如函数指针传递的是函数指针它的类型，而非传递函数指针所指向的函数，我们不知道实例化出来的对象里的函数指针指向哪里，可能是空指针，也可能是随机值，总之都是无效指针。当然，也不是不能传递函数指针，不过这个过程会非常麻烦。
二、仿函数
- 仿函数，数如其名，它不是真函数，而是一个类。不过它的实例化对象可以像函数一样使用，这就得归功于仿函数内部对于()的重载。也可以这样说，重载了()的就是仿函数。
- 我们来实现两个简单的less和greater仿函数以便更好的了解它：
代码语言：javascript
AI代码解释
namespace mosheng//防止与std里的冲突
{
template<class T>
class less
{
public:
bool operator()(const T& a, const T& b)
{
return a < b;
}
};
template<class T>
class greater
{
public:
bool operator()(cosnt T& a, cosnt T& b)
{
return a > b;
}
};
}
- 我们可以把它用在冒泡排序里来控制升序和降序：
代码语言：javascript
AI代码解释
template<class T, class Compare = mosheng::less<T>>
void BubbleSort(T* a, int n, Compare com)
{
int exchange = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n - i - 1; j++)
{
//等价于com.operator()(a[j + 1], a[j])
if (com(a[j + 1], a[j]))
{
exchange = 1;
swap(a[j], a[j + 1]);
}
}
if (exchange == 0)
{
break;
}
}
}
int main()
{
int arr[] = { 1, 5, 12, 2, 1, 3, 77 };
BubbleSort(arr, 7, mosheng::less<int>());
cout << "less: ";
for (auto e : arr)
{
cout << e << " ";
}
cout << endl;
cout << "greater: ";
BubbleSort(arr, 7, mosheng::greater<int>());
for (auto e : arr)
{
cout << e << " ";
}
cout << endl;
return 0;
}
就有：
在这里插入图片描述
- 我们将仿函数类类型less与greater传递给Campare，进而创造出Compare类型的实例化对象com，再通过com调用operator()函数，com(a[j + 1], a[j])，等价于com.operator()(a[j + 1], a[j])，进而达到目的。可以看到，虽然com不是函数，只是类的实例化对象，但它与函数的功能无二，所以是仿函数。
- 有的时候，库里面提供的仿函数不能够达到我们的目的，比如为Date类的指针排序，它比较的是指针的大小，而不是指针所指向的数据。这个时候我们就得自己构建仿函数。如下：
代码语言：javascript
AI代码解释
class Date
{
public:
Date(int year = 1900, int month = 1, int day = 1)
: _year(year)
, _month(month)
, _day(day)
{}
bool operator<(const Date& d)const
{
return (_year < d._year) ||
(_year == d._year && _month < d._month) ||
(_year == d._year && _month == d._month && _day < d._day);
}
bool operator>(const Date& d)const
{
return (_year > d._year) ||
(_year == d._year && _month > d._month) ||
(_year == d._year && _month == d._month && _day > d._day);
}
friend ostream& operator<<(ostream& _cout, const Date& d);
private:
int _year;
int _month;
int _day;
};
ostream& operator<<(ostream& _cout, const Date& d)
{
_cout << d._year << "-" << d._month << "-" << d._day;
return _cout;
}
//构建仿函数
struct PDateLess
{
bool operator()(const Date* p1, const Date* p2)
{
return *p1 < *p2;
}
};
int main()
{
priority_queue<Date*, vector<Date*>> q1;
q1.push(new Date(2025, 7, 20));
q1.push(new Date(2025, 7, 21));
q1.push(new Date(2025, 7, 22));
cout << "原始：";
while (!q1.empty())
{
cout << *q1.top() << " ";
q1.pop();
}
cout << endl;
cout << "构建的PDteLess：";
priority_queue<Date*, vector<Date*>, PDateLess> q2;
q2.push(new Date(2025, 7, 20));
q2.push(new Date(2025, 7, 21));
q2.push(new Date(2025, 7, 22));
while (!q2.empty())
{
cout << *q2.top() << " ";
q2.pop();
}
cout << endl;
return 0;
}
在这里插入图片描述
- 原始里面的顺序是随机的，不是我们预期的效果。
更多推荐
27
0- 0
已为社区贡献65条内容
所有评论(0)