STL
比较函数
使用容器时经常需要我们自定义比较函数,C++的自定义比较函数是一个非常令人疑惑的领域
接下来,请你记住这句话:在C++中,元素x在元素y前面,可以等价表述为:x的优先级比y的优先级低,可以用偏序对<x,y>表示
偏序对
「偏序对」描述了一个容器中两个元素之间的关系,任意一个数据结构由若干个偏序对组成:
- 有序列表(有序数组或有序链表)中,
描述任意两个元素的位置关系,x在y前面 - 树中,
描述子节点和父节点的关系,x是子节点,y是父节点
为了表述这种位置关系/优先级关系,C++默认:
- 比较函数有两个参数a和b,a和b为需要比较「优先级」的两个元素
- a和b的类型需要相同
- 默认第一个参数a的优先级低于第二个参数b,满足该关系时比较函数返回
true,否则返回false
默认比较函数
我们来看C++默认的比较函数:std::less<T>和std::greater<T>
默认a的比较级比b低时返回true,而在less函数中规定了a < b返回true,因此我们得出:a < b时,a的比较级比b低,对应到有序列表就是a在b的前面
从这个例子,你应该会发现,函数内得到true的条件决定了元素的哪个性质使得第一个参数a优先级比b低,对应到有序列表就是:值小的在前面
在greater函数中,参数a仍然默认在b的前面,此时返回true的条件是a > b,因此:当a > b的时候,a的优先级比b大,对应有序列表就是:值大的在前面
从以上两个函数的分析,我们可以得出:第一个参数a比第二个参数b的优先级低这一结果是不变的,决定实际元素排布顺序的是「返回true的条件」
自定义比较函数
我们可以模仿这两个函数实现自定义比较函数,例如:
等价于
一句话总结自定义比较函数
返回true的条件决定元素排布顺序:
- 对于有序列表:
- 如果「a的xx性质 > b的xx性质」,则xx性质大的在前面
- 如果「a的xx性质 < b的xx性质」,则xx性质小的在前面
- 对于树:
- 如果「a的xx性质 > b的xx性质」,则xx性质大的为子节点
- 如果「a的xx性质 < b的xx性质」,则xx性质小的为子节点
优先级队列
容器定义:
template<
class T,
class Container = std::vector<T>,
class Compare = std::less<typename Container::value_type>
> class priority_queue;
T:队列中存储的元素类型。Container:底层容器类型,默认为std::vector<T>。Compare:比较函数对象类型,默认为std::less<T>,即大根堆。(小根堆对应std::greater<T>)
比较函数
本容器难点在于比较函数
比较函数详细解释见:比较函数。 简单来说,就是比较函数返回
true表示第一个参数的优先级比第二个参数低,而优先级队列,就是保证父节点的优先级比两个子节点高,不同比较函数对优先级的不同定义导致了不同优先级队列(大根堆、小根堆)的出现。
堆的本质是完全二叉树,即树,<x, y>表示x是y的子节点
比较函数返回true的条件决定了谁是谁的子节点
大根堆
默认情况下,std::priority_queue 使用 std::less<T> 作为比较函数:
在less函数,返回true的条件是a < b,所以值大的是父节点,值小的是子节点
因此,较大的元素会被推到堆顶,形成 大根堆。
小根堆
如果你希望实现 小根堆,可以使用 std::greater
在greater函数,返回true的条件是a > b,所以值小的是父节点,值大的是子节点
因此,较小的元素会被推到堆顶,形成 小根堆。
自定义堆
我们自定义一个大根堆为例:
为什么自定义结构体而不是自定义比较函数
对于sort,可以使用自定义比较函数
而为什么priority_queue只能使用自定义结构体呢?
这涉及到模板类和模板函数的知识
简单来说:
std::sort 和 std::priority_queue 它们的实现机制不同:
std::sort
函数模板:std::sort 是一个函数模板,它接受一个比较函数对象作为参数。由于它是函数模板,可以在运行时传递各种类型的比较函数对象(如函数指针、lambda表达式或仿函数)。
template <typename RandomIt, typename Compare>
void sort(RandomIt first, RandomIt last, Compare comp);
std::priority_queue
类模板:std::priority_queue 是一个类模板,其第三个模板参数 Compare 需要是一个类型,而不是一个具体的对象或函数指针。这是因为类模板需要在编译期确定所有模板参数的类型信息。
二分查找
https://blog.csdn.net/weixin_45031801/article/details/137544229
lower_bound( begin , end , val , less
upper_bound
前提是有序的情况下,upper_bound返回第一个大于val值的位置。(通过二分查找)
lower_bound
前提是有序的情况下,lower_bound 返回指向第一个值不小于 val 的位置,也就是返回第一个大于等于val值的位置。(通过二分查找)
*注意:*需要注意的是如果例子中(val >= 8),那么迭代器就会指向last位置,*也就是数组尾元素的下一个,不管val多大,迭代器永远指向尾元素的下一个位置*
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
vector<int> v = { 3,4,1,2,8 };
// 先排序
sort(v.begin(), v.end()); // 1 2 3 4 8
// 定义两个迭代器变量
vector<int>::iterator iter1;
vector<int>::iterator iter2;
// 在动态数组中寻找 >=3 出现的第一个数 并以迭代器的形式返回
iter1 = lower_bound(v.begin(), v.end(), 3); // -- 指向3
// 在动态数组中寻找 >=7 出现的第一个数 并以迭代器的形式返回
iter2 = lower_bound(v.begin(), v.end(), 7); // -- 指向8
cout << distance(v.begin(), iter1) << endl; //下标 2
cout << distance(v.begin(), iter2) << endl; //下标 4
return 0;
}
其他细节
等价于