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

╰半橙微兮° 2024-02-05 22:33 37阅读 0赞

#### 文章目录 ####

*  一、二元谓词
 *   *  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;
    };

**执行结果 :**

遍历容器 :  
2 5 7 9 遍历结束  
请按任意键继续. . .

![在这里插入图片描述][367a6fda34d64c0480700bd705329638.png]

[367a6fda34d64c0480700bd705329638.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/ba1e6262de9441b7b551f06b8d854c97.png