当使用 sort函数 和 Priority_queue优先队列 时， Container 中的元素会被自动排序

当待排列的元素为一个对象时，我们既可以通过自定义比较函数，也可以通过重载运算符来达到目的。

下面我们对 Object 的讨论都基于下述 Person 类

class Person {  
public:  
	string name;  
	int age;  
	Person(string name, int age) {  
		this->name = name;  
		this->age = age;  
	}  
};

Sort函数

重载运算符

当 Container 中的元素是基本数据类型时，使用 less 是升序排序，使用 greater 是降序排序

下面👇对元素为 Object 的情况作详细说明

less

sort函数在默认情况下使用std::less作为比较函数类

sort(people.begin(), people.end());

而std::less需要重载小于号<运算符：

class Person {
	...

	bool operator<(const Person &p) const {  
		return this->age < p.age;  
	}

	...
}

经过上述的重载后，sort 会将元素按 age 升序排序

括号内的 const 表示其修饰的参数为常量，在函数内不能修改该参数

括号外的 const 表示该函数为常成员函数，在函数内不能需修改成员变量

如果我们把函数体内的 < 替换为 >，元素将会按 age 降序排序

greater

还可以使用std::greater作为比较函数类

sort(people.begin(), people.end(), greater<>());

那么就需要重载大于号>运算符：

class Person {
	...

	bool operator>(const Person &p) const {  
		return this->age > p.age;  
	}

	...
}

经过上述的重载后，sort 会将元素按 age 降序排序

自定义比较函数

bool cmp(const Person &p1, const Person &p2) {  
	return p1.age < p2.age;  
}

sort(people.begin(), people.end(), cmp);

经过上述操作后，元素将会按 age 升序排序

Priority_queue堆优先队列

堆是一种数据结构，可以用数组或树实现，常用于实现优先队列、排序算法等。

优先队列（priority queue）就是堆（heap）的一种应用。

C++中的优先队列实现就是堆优先队列，底层使用堆来实现。

std::priority_queue是一个模板类，它的模板参数有三个，分别是：

  1. T：指定队列中存储的元素类型。
  2. Container：指定用于存储元素的容器类型，默认是std::vector<T>。
  3. Compare：指定用于比较元素优先级的比较函数类型，默认是std::less<T>。

在C++中，优先队列可以通过指定比较函数来控制是使用大根堆还是小根堆。

默认情况下，使用 std::less<> 作为比较函数，则意味着使用大根堆，最大值会优先出队，大根堆(Max Heap)是一种完全二叉树,它满足两个特性:

  1. 任意一个节点的值都大于等于其左右子节点的值
  2. 根节点的值最大

如果使用 std::greater<> 作为比较函数，则意味着使用小根堆，最小值会优先出队

常用操作

  • pq.push(elem)：入队
  • pq.pop()：出队
  • pq.top()：返回堆顶元素

重载运算符

less

  • priority_queue<T> pq：默认构造大根堆，需要重载 <
class Person {
	...

	bool operator<(const Person &p) const {  
		return this->age < p.age;  
	}

	...
}

大根堆，最大值会先出队

greater

  • priority_queue<T, vector<T>, greater<>> pq：构造最小堆，需要重载 >
class Person {
	...

	bool operator>(const Person &p) const {  
		return this->age > p.age;  
	}

	...
}

小根堆，最小值会先出队