久久建筑网是个什么样的网站,做响应式网站哪家公司好,论述网站建设流程,网站开发知识视频教程文章目录 一、二元谓词1、二元谓词简介2、 std::sort 算法简介3、 代码示例 - 为 std::sort 算法设置 二元谓词 排序规则 一、二元谓词 1、二元谓词简介 谓词 ( Predicate ) 是一个 返回 布尔 bool 类型值 的 函数对象 / 仿函数 或 Lambda 表达式 / 普通函数 , … 文章目录 一、二元谓词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 单端数组容器
vectorint vec;// std::sort 排序算法, 默认使用快速排序
sort(vec.begin(), vec.end(), Compareint());3、 代码示例 - 为 std::sort 算法设置 二元谓词 排序规则 在下面的代码中 , 定义了 二元谓词 Compare ;
//函数对象 类重载了()
template typename T
class Compare {
public:bool operator()(T a, T b) const {return a b;}
};在该 二元谓词 的 重载 函数调用操作符 函数中 , 接收 2 个元素 , 返回 第一个元素 是否 小于第二个元素 , 这是进行 从小到大 排序的 规则 ;
然后 , 创建一个 vector 单端数组容器 , 之后将该 容器中的元素进行排序 ; // 创建一个 vector 单端数组容器vectorint vec;最后 , 调用 sort 排序算法 , 将 vector 容器中的元素进行排序 ; // std::sort 排序算法, 默认使用快速排序sort(vec.begin(), vec.end(), Compareint());代码示例 :
#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 单端数组容器vectorint vec;// 向容器中插入元素vec.push_back(9);vec.push_back(5);vec.push_back(2);vec.push_back(7);// std::sort 排序算法, 默认使用快速排序sort(vec.begin(), vec.end(), Compareint());//容器的遍历cout 遍历容器 : endl;for (auto it vec.begin(); it ! vec.end(); it){cout *it ;}cout 遍历结束 endl;// 控制台暂停 , 按任意键继续向后执行system(pause);return 0;
};执行结果 :
遍历容器 : 2 5 7 9 遍历结束 请按任意键继续. . .
