简介本文承接前文仿函数、Lambda、bind 相关知识点主要讲解std::function函数包装器以及 STL 系列常用算法包含填充、生成、删除、排序、堆操作、二分查找。一、std::function 函数包装器知识点总结std::function是标准库提供的函数包装器类模板可以封装普通函数、函数指针、Lambda 表达式、仿函数等所有可调用对象。核心作用给匿名 Lambda 具名、统一可调用对象类型常用来实现回调函数、函数多态传参。语法格式function返回值类型(参数列表) 变量名 可调用对象;std::function与auto区别表格特性autostd::function本质编译期类型推导关键字标准库通用函数包装类作用自动推导变量类型简化代码封装任意可调用对象统一类型运行开销无任何开销和手写类型一致存在开销虚函数 / 类型擦除存储函数仅做类型推导不能统一管理函数专门用于存放各类可调用对象使用场景简化变量、迭代器、Lambda 声明回调函数、函数参数、多态调用完整源码原生代码 注释#includeiostream #includevector #includedeque #includelist #includemap #includeunordered_map #includealgorithm// 算法头文件 #includefunctional #includeiterator #includeiomanip #includectime #includecstdlib using namespace std; #if 0 //function函数包装器的类模板 封装可被调用对象对lambda表达式具名。 // //语法 function函数返回类型函数的参数列表 名称 lambda 表达式或函数指针或函数表达式 // 例如 // functionvoid(int) f1 [](int a) {cout a endl; }; // int add(int a,int b) {return ab;} // int sub(int a, int b) {return a - b;} // functionint(int, int) f2 add; // functionint(int, int) f3 sub; //为一个类模板 //可以封装成任意可以调用的对象 //lambda的本质是匿名的函数对象但它的类型是编译器生成的匿名闭包类型 int add(int a, int b) { return a b; } int sub(int a, int b) { return a - b; } int mul(int a, int b) { return a * b; } int divrture(int a, int b) { return a / b; } //以上四个函数定义函数类型名称 using Func int(*)(int, int);//定义一个函数的类型 int compare(int a, int b, Func f) { return f(a, b); }; int compare1(int a, int b, functionint(int, int) f) { return f(a, b); }; int compare11(int a, functionint(int) f) { return f(a); }; int main() { cout compare(10, 20, add) endl; cout compare(10, 20, sub) endl; cout compare(10, 20, mul) endl; cout compare(10, 20, divrture) endl; functionint(int) f1 [](int a) {return a 1; }; cout compare11(10,f1) endl; } #endif //与auto 的区别 //特性 auto std::function //是什么 编译期类型推导关键字 标准库的通用函数包装类 //作用 自动推导变量类型简化代码 封装任意可调用对象统一类型 //运行时开销 无任何开销和手写类型一样 有开销虚函数 / 类型擦除 //能不能存函数 不能只是推导类型 能专门存各种可调用对象 //使用场景 简化变量声明、迭代器、lambda 等 回调函数、函数参数、多态调用二、fill 填充算法 generate 生成算法知识点总结fill容器区间批量填充固定值。generate借助可调用对象函数 / Lambda/function动态生成容器元素。C 语言随机数生成固定公式rand() % (最大值 - 最小值 1) 最小值。完整源码#if 0 //2.fill 填充算法 //generat 生成算法提供仿函数返回特定值 #includectime #includecstdlib int main() { vectorint v(10); fill(v.begin(), v.end(), 100);//填充100 里面的每个元素都是100 for_each(v.begin(), v.end(), [](int a) {cout a ; }); cout endl; //随机生成到1到100之间的整数 // [a到b] // rand() % (b - a 1) a 固定公式c语言生成随机数的固定公式 srand(time(NULL)); functionint() f []() { return rand() % 100 1; }; generate(v.begin(), v.end(), f); for_each(v.begin(), v.end(), [](int a) {cout a ; }); } #endif三、删除算法remove /remove_if/remove_copy_if /unique知识点总结remove/remove_if不会真正删除元素、不会改变容器大小仅将有效元素向前覆盖返回有效区间尾迭代器。remove_copy_if过滤元素将符合条件的元素拷贝至新容器。unique仅删除相邻重复元素想要全局去重必须先对容器排序。完整源码//3.删除算法 //remove //remove_if //remove_copy //remove_copy_if #if 0 int main() { vectorint v{ 1,2,3,4,5,6,7 } ; auto newEnd remove(v.begin(), v.end(), 3);//删除单个元素3 //remove将待删除的元素后面的元素往前挪并且复制尾部的元素补充。但是v.end()所确定的边界不变 //它的返回值为删除后的在整个数据结构的最后一个元素的位置 for_each(v.begin(), newEnd, [](int a) {cout a ; }); cout endl; for_each(v.begin(), v.end(), [](int a) {cout a ; }); cout endl; //1,2,4,5,6,7,7 //删除满足条件的元素删除所有偶数 auto newEnd1 remove_if(v.begin(), v.end(), [](int a) {return a % 2 0; }); for_each(v.begin(), newEnd1, [](int a) {cout a ; }); cout endl; //1,5,7,7 for_each(v.begin(), v.end(), [](int a) {cout a ; }); cout endl; //将删除的数据转移到新的容器中 vectorint d; auto newEnd3 remove_copy_if(v.begin(),v.end(),back_inserter(d), [](int a) {return a % 2 ! 0; });//保存条件成立的元素不成立的则移动到新的容器中 for_each(d.begin(), d.end(), [](int a) {cout a ; }); cout endl; vectorint v2{ 1,5,1,3,1,4,1,1,4,8,9,1,5 }; #if 1 sort(v2.begin(), v2.end());//排序算法升序 #endif//结合排序之后的数字特点删除相邻的重复元素就能删掉要删除的值的所有元素 auto newEnd4 unique(v2.begin(), v2.end());//删除相邻的重复元素//也就是重复元素删除 for_each(v2.begin(), newEnd4, [](int a) {cout a ; }); cout endl; for_each(v2.begin(), v2.end(), [](int a) {cout a ; }); cout endl; } #endif四、基础排序算法 sort /stable_sort知识点总结sort自适应综合排序数据量不同自动选用快排 / 插排 / 归并排序不稳定排序要求容器支持随机访问迭代器vector/deque。stable_sort稳定排序排序后值相等的元素保留原有相对位置。sort_heap堆排序配合堆结构使用。完整源码//排序算法 //sort(): 自省选择排序算法快速 (中量)插入小量归并排序大量 //支持随机访问迭代器 vector,deque //stable_sort() 同sort 相同排序值时保持原有的顺序 //sort_heap: 堆排序大堆小堆 functionint() gen []() {return rand() % 100 1; }; functionvoid(int) show [](int x) { cout x ; }; #if 0 int main() { vectorint v(20); srand(time(NULL));//不能在全局去放这个函数 generate(v.begin(), v.end(), gen); for_each(v.begin(), v.end(), [](int a) {cout a ; }); cout endl; sort(v.begin(), v.end()); for_each(v.begin(), v.end(), show); cout endl; stable_sort(v.begin(), v.end()); for_each(v.begin(), v.end(), show); cout endl; } #endif五、结构体自定义排序结合 std::function知识点总结对自定义结构体排序需要手动提供比较规则。使用静态std::function封装多套排序逻辑可灵活切换按编号、姓名、年龄排序。搭配stable_sort实现稳定结构体排序。完整源码#if 0 struct Person { int pid; string name; int age; Person(int pid, string name, int age) :pid(pid), name(name), age(age) {} // bool operator(Person p){} static functionbool(const Person, const Person) byPid; static functionbool(const Person, const Person) byName; static functionbool(const Person, const Person) byAge; }; functionbool(const Person, const Person) Person::byPid [](const Person l, const Person r) { return l.pid r.pid; }; functionbool(const Person, const Person) Person::byName [](const Person l, const Person r) { return l.name r.name; }; functionbool(const Person, const Person) Person::byAge [](const Person l, const Person r) { return l.age r.age; }; int main() { vectorPerson v; v.push_back(Person(5, Jack, 21)); v.push_back(Person(15, Mack, 18)); v.push_back(Person(8, Lucy, 19)); v.push_back(Person(11, MiMi, 18)); v.push_back(Person(9, Cici, 20)); v.push_back(Person(7, YaYa, 21)); v.push_back(Person(25, YiWan, 22)); v.push_back(Person(13, Cerry, 19)); stable_sort(v.begin(), v.end(), Person::byAge); // less for_each(v.begin(), v.end(), [](const Person p) { cout p.pid | p.name | p.age endl; }); return 0; } #endif六、堆操作相关算法知识点总结make_heap将容器区间构建为堆默认大顶堆传入greater可构建小顶堆。is_heap判断容器区间是否为合法堆结构。sort_heap将堆结构转为有序序列。pop_heap仅将堆顶元素移动到容器尾部剩余元素重新建堆不会真正删除元素需要配合pop_back完成删除。完整源码#if 0 // 5. 堆操作 // make_heap 生成最大堆 // int main() { vectorint v{ 1, 2, 7, 9, 4, 2, 3 }; // 94 7 2123 // make_heap(v.begin(), v.end()); //less 默认是最大堆 make_heap(v.begin(), v.end(), greater()); // 最小堆 // 验证数列 是否为小/大堆 cout is_heap(v.begin(), v.end(), greater()) endl; // 将小堆变大堆: 按大堆 sort_heap(v.begin(), v.end(), greater()); while (!v.empty()) { // 取出最大的值 堆顶 pop_heap(v.begin(), v.end()); // 将堆顶的元素 移动到尾部 /*它的行为可以分为两步 将堆顶元素移动到末尾 对于最大堆pop_heap会将当前最大值堆顶移动到容器的末尾 对于最小堆pop_heap会将当前最小值堆顶移动到容器的末尾 调整剩余元素为堆结构 移动后容器的前n - 1个元素会被重新组织成一个有效的堆*/ cout v.back() endl; v.pop_back(); // 删除尾删操作 } return 0; } #endif七、二分查找算法 binary_search知识点总结binary_search二分查找算法返回值为bool标识元素是否存在。强制要求查找区间必须提前排序否则查找结果错误。时间复杂度\(O(logN)\)查找效率远高于普通遍历。完整源码//6.二分查找算法 //binary_search: 二分查找返回bool 要求必须有序 #if 0 int main() { vectorint v(10); srand(time(NULL)); generate(v.begin(), v.end(), gen); sort(v.begin(), v.end()); int vv; while (true) { cout请输入要查找的值; cin vv; if (vv 0) break; if (binary_search(v.begin(), v.end(), vv)) { cout 找到了 endl; } else { cout 没找到 endl; } } } #endif全文知识点汇总std::function通用函数包装器统一管理各类可调用对象多用于回调、函数传参。填充 / 生成算法fill填充固定值generate动态生成元素。删除算法remove系列只移动元素不缩容依靠返回迭代器遍历有效数据unique结合排序实现全局去重。排序算法sort不稳定排序、stable_sort稳定排序支持自定义规则实现结构体排序。堆算法完成建堆、判堆、堆排序、弹出堆顶等操作适用于优先级场景。二分查找高效查找算法使用前提为容器区间有序。