【C++】STL 算法 ⑥ ( 二元谓词 | std::sort 算法简介 | 为 std::sort 算法设置二元谓词排序规则 )

文章目录

一、二元谓词
- 1、二元谓词简介
- 2、 std::sort 算法简介
- 3、代码示例 - 为 std::sort 算法设置二元谓词排序规则

一、二元谓词

1、二元谓词简介

" 谓词 ( Predicate ) " 是一个返回布尔 bool 类型值的函数对象 / 仿函数或 Lambda 表达式 / 普通函数 , 可用于对某个条件进行检查 ;

" 谓词 ( Predicate ) " 类型 :

普通函数
函数指针
重载了函数调用操作符的函数对象 / 仿函数 , 有 operator() 函数 ;

" 谓词 ( Predicate ) " 通常被设计成可以接受一定数量的参数

一元谓词 : 接受一个参数
二元谓词 : 接受两个参数

谓词的函数体中根据传入的参数进行计算 , 并返回 true 或 false 布尔值 ;

" 二元谓词 " 就是接受两个参数的谓词 ,

" 谓词 " 是返回布尔 bool 类型值的函数对象 ,

" 函数对象 " 是重载函数调用操作符 () 函数的类 ;

下面的结构体类函数对象 , 就是一个 " 二元谓词 " , 其作用是将传入的两个 int 参数 , 返回前者是否比后者大 ;

struct Compare {  
    bool operator()(int a, int b) const {  
        return a > b;  
    }  
};

2、 std::sort 算法简介

C++ 标准模板库 ( STL , Standard Template Library ) 中的 std::sort 算法是 " 排序算法 "，其底层算法原理就是使用排序算法对容器中的元素进行排序 , 排序时根据不同的容器规模 , 自动选择合适的排序算法 , 以提高排序的效率 ;

大型序列使用 " 快速排序 Quicksort " 算法 ;
小型序列使用 " 插入排序 Insertion Sort " 算法 ;
递归层次深的序列使用 " 堆排序 Heap Sort " 算法 , 避免快排的最坏情况 ;

std::sort 算法函数原型 :

template <class _RanIt, class _Pr>
void sort(const _RanIt _First, const _RanIt _Last, _Pr _Pred) { // order [_First, _Last), using _Pred
    _Adl_verify_range(_First, _Last);
    const auto _UFirst = _Get_unwrapped(_First);
    const auto _ULast  = _Get_unwrapped(_Last);
    _Sort_unchecked(_UFirst, _ULast, _ULast - _UFirst, _Pass_fn(_Pred));
}

sort 算法函数接受两个迭代器参数 , 这两个迭代器定义了一个需要排序的元素范围 , 注意这是一个前闭后开区间 [_First, _Last) ;

_First 迭代器指向第一个需要排序的元素 ;
_Last 迭代器指向最后一个元素之后的位置 ;

sort 算法还可以接受一个可选的第三个参数 , 即比较函数 , 该函数用于定义排序的规则 ;

如果不提供排序规则 , sort 会默认使用 operator< 重载操作符函数对元素进行比较 ;

sort 算法的时间复杂度 : 在最理想的情况下是 O(n log n) , 其中 n 是待排序元素的数 , 这是 " 快速排序 Quicksort " 算法的时间复杂度 ; 在实际应用场景中 , 排序的性能可能会受到数据分布 , 元素类型以及比较函数的影响 , 如递归层次比较深有可能出现极端情况 ;

sort 算法的空间复杂度 : sort 算法是一种原地排序算法 , 该算法不需要额外的存储空间来保存排序结果 ; 而是在输入序列中直接进行排序 ;

std::sort 排序算法用法示例 :

//函数对象 类重载了()
template <typename T>
class Compare {
public:
	bool operator()(T& a, T& b) const {
		return a < b;
	}
};

// 创建一个 vector 单端数组容器
vector<int> vec;

// std::sort 排序算法, 默认使用快速排序
sort(vec.begin(), vec.end(), Compare<int>());

3、代码示例 - 为 std::sort 算法设置二元谓词排序规则

在下面的代码中 , 定义了二元谓词 Compare ;

//函数对象 类重载了()
template <typename T>
class Compare {
public:
	bool operator()(T& a, T& b) const {
		return a < b;
	}
};

在该二元谓词的重载函数调用操作符函数中 , 接收 2 个元素 , 返回第一个元素是否小于第二个元素 , 这是进行从小到大排序的规则 ;

然后 , 创建一个 vector 单端数组容器 , 之后将该容器中的元素进行排序 ;

	// 创建一个 vector 单端数组容器
	vector<int> vec;

最后 , 调用 sort 排序算法 , 将 vector 容器中的元素进行排序 ;

	// std::sort 排序算法, 默认使用快速排序
	sort(vec.begin(), vec.end(), Compare<int>());

代码示例 :

#include "iostream"
using namespace std;
#include <vector>
#include <algorithm>
#include "functional"

//函数对象 类重载了()
template <typename T>
class Compare {
public:
	bool operator()(T& a, T& b) const {
		return a < b;
	}
};

int main() {

	// 创建一个 vector 单端数组容器
	vector<int> vec;

	// 向容器中插入元素
	vec.push_back(9);
	vec.push_back(5);
	vec.push_back(2);
	vec.push_back(7);

	// std::sort 排序算法, 默认使用快速排序
	sort(vec.begin(), vec.end(), Compare<int>());

	//容器的遍历
	cout << "遍历容器 :" << endl;
	for (auto it = vec.begin(); it != vec.end(); it++)
	{
		cout << *it << " ";
	}
	cout << "遍历结束" << endl;

	// 控制台暂停 , 按任意键继续向后执行
	system("pause");
	return 0;
};