C 标准模板库STL提供了丰富的算法库定义在algorithm头文件中这些算法多为通用函数模板可配合容器和迭代器高效操作数据。1、非修改序列算法这些算法不会改变它们所操作的容器中的元素。1.1 find 和 find_iffind(begin, end, value)查找第一个等于value的元素返回迭代器未找到返回end。find_if(begin, end, predicate)查找第一个满足谓词的元素。find_end(begin, end, sub_begin, sub_end)查找子序列最后一次出现的位置。1234567891011121314151617vectorint nums {1, 3, 5, 7, 9};// 查找值为5的元素auto it find(nums.begin(), nums.end(), 5);if(it ! nums.end()) {cout found: *it endl;// 输出5}// 查找第一个大于6的元素auto it2 find_if(nums.begin(), nums.end(), [](intx) {returnx 6;});cout first 6: *it2 endl;// 输出7// 查找子序列vectorint sub {3, 5};auto it3 find_end(nums.begin(), nums.end(), sub.begin(), sub.end());if(it3 ! nums.end()) {cout subsequence starts at index: it3 - nums.begin() endl;// 输出1}1.2 count 和 count_ifcount(begin, end, value)统计等于value的元素个数。count_if(begin, end, predicate)统计满足谓词predicate的元素个数。12345std::vectorint vec {1, 2, 3, 2, 4, 2};intcnt std::count(vec.begin(), vec.end(), 2);// 计数2的个数结果为3inteven_cnt std::count_if(vec.begin(), vec.end(), [](intx) {returnx % 2 0;});// 偶数个数结果为41.3 for_each对范围内的每个元素应用一个函数12345std::vectorint vec {1, 2, 3, 4, 5};std::for_each(vec.begin(), vec.end(), [](int x) {x * 2;// 将每个元素乘以2});// 现在vec变为{2, 4, 6, 8, 10}1.4 equal 与 mismatchequal(b1, e1, b2)判断两个范围[b1,e1)和[b2, b2(e1-b1))是否相等。mismatch(b1, e1, b2)返回两个范围中第一个不相等元素的迭代器对pair。1234567891011vectorint a {1, 2, 3};vectorint b {1, 2, 4};vectorint c {1, 2, 3, 4};// 比较a和b的前3个元素boolis_equal equal(a.begin(), a.end(), b.begin());cout a b? boolalpha is_equal endl;// 输出false// 查找a和c的第一个不匹配元素auto mis mismatch(a.begin(), a.end(), c.begin());if(mis.first ! a.end()) {cout mismatch: *mis.first vs *mis.second endl;// 无输出a和c前3元素相等}1.5 all_of, any_of, none_of检查范围内元素是否全部、存在或没有满足条件的12345678910std::vectorint vec {2, 4, 6, 8};boolall_even std::all_of(vec.begin(), vec.end(), [](intx) {returnx % 2 0;});// trueboolany_odd std::any_of(vec.begin(), vec.end(), [](intx) {returnx % 2 ! 0;});// falseboolnone_negative std::none_of(vec.begin(), vec.end(), [](intx) {returnx 0;});// true2、修改序列算法这些算法会修改它们所操作的容器中的元素。2.1 copy 和 copy_ifcopy(begin, end, dest)将[begin, end)中的元素复制到dest开始的位置。copy_if(begin, end, dest, predicate)复制满足谓词的元素到dest。123456789vectorint src {1, 2, 3, 4, 5};vectorint dest(5);// 需预先分配足够空间// 复制所有元素copy(src.begin(), src.end(), dest.begin());// dest: [1,2,3,4,5]// 复制偶数元素到新容器vectorint evens;copy_if(src.begin(), src.end(), back_inserter(evens), [](intx) {returnx % 2 0;});// evens: [2,4]注意back_inserter(dest)会自动调用push_back无需提前分配空间。2.2 transform对范围内的每个元素应用一个函数并将结果存储在另一个范围内12345678910111213vectorint nums {1, 2, 3};vectorint squares(3);// 计算平方单参数转换transform(nums.begin(), nums.end(), squares.begin(), [](intx) {returnx * x;});// squares: [1,4,9]// 两容器元素相加双参数转换vectorint a {1, 2, 3};vectorint b {4, 5, 6};vectorint sum(3);transform(a.begin(), a.end(), b.begin(), sum.begin(), [](intx,inty) {returnx y;});// sum: [5,7,9]2.3 replace、replace_if与 replace_copyreplace(begin, end, old_val, new_val)将所有old_val替换为new_val。replace_if(begin, end, predicate, new_val)替换满足谓词的元素。replace_copy(begin, end, dest, old_val, new_val)复制时替换元素不修改原容器。12345678910vectorint nums {1, 2, 3, 2, 5};// 替换所有2为20replace(nums.begin(), nums.end(), 2, 20);// nums: [1,20,3,20,5]// 替换大于10的元素为0replace_if(nums.begin(), nums.end(), [](intx) {returnx 10;}, 0);// nums: [1,0,3,0,5]// 复制时替换3为300原容器不变vectorint res;replace_copy(nums.begin(), nums.end(), back_inserter(res), 3, 300);// res: [1,0,300,0,5]2.4 remove、remove_if 与 eraseremove(begin, end, value)将等于value的元素 “移动” 到容器末尾返回新的逻辑尾迭代器不实际删除元素需配合erase。remove_if(begin, end, predicate)移动满足谓词的元素到末尾。12345678910vectorint nums {1, 2, 3, 2, 4};// 逻辑删除所有2移动到末尾auto new_end remove(nums.begin(), nums.end(), 2);// nums: [1,3,4,2,2]// 物理删除真正移除元素nums.erase(new_end, nums.end());// nums: [1,3,4]// 结合lambda删除偶数nums {1, 2, 3, 4, 5};nums.erase(remove_if(nums.begin(), nums.end(), [](intx) {returnx % 2 0;}), nums.end());// nums: [1,3,5]2.5 unique移除范围内连续的重复元素返回新的逻辑结尾迭代器。通常与erase结合使用。123std::vectorint vec {1, 1, 2, 2, 3, 3, 3, 4, 5};auto last std::unique(vec.begin(), vec.end());vec.erase(last, vec.end());// vec变为{1, 2, 3, 4, 5}2.6 reverse反转范围内的元素顺序12std::vectorint vec {1, 2, 3, 4, 5};std::reverse(vec.begin(), vec.end());// vec变为{5, 4, 3, 2, 1}2.7 rotate旋转范围内的元素使中间元素成为新的第一个元素12std::vectorint vec {1, 2, 3, 4, 5};std::rotate(vec.begin(), vec.begin() 2, vec.end());// 以3为起点旋转vec变为{3, 4, 5, 1, 2}2.8 shuffle随机重排范围内的元素需要C11或更高版本123456#include random#include algorithmstd::vectorint vec {1, 2, 3, 4, 5};std::random_device rd;std::mt19937 g(rd());std::shuffle(vec.begin(), vec.end(), g);// 随机打乱vec中的元素3、排序和相关算法3.1 sort、stable_sort 与 partial_sortsort(begin, end)对元素进行快速排序不稳定平均时间复杂度 O (n log n)。stable_sort(begin, end)稳定排序相等元素相对位置不变。partial_sort(begin, mid, end)部分排序使[begin, mid)为整个范围中最小的元素并排序。1234567891011121314std::vectorint vec {5, 3, 1, 4, 2};std::sort(vec.begin(), vec.end());// 默认升序vec变为{1, 2, 3, 4, 5}std::sort(vec.begin(), vec.end(), std::greaterint());// 降序vec变为{5, 4, 3, 2, 1}std::sort(vec.begin(), vec.end(), [](inta,intb) {returna b;});// 升序自定义比较std::vectorstd::pairint,int vec {{1, 2}, {2, 1}, {1, 1}, {2, 2}};std::stable_sort(vec.begin(), vec.end(), [](constauto a,constauto b) {returna.first b.first;// 按first排序保持相等元素的相对顺序});std::vectorint vec {5, 3, 1, 4, 2, 6};// 将最小的3个元素放在前面并排序std::partial_sort(vec.begin(), vec.begin() 3, vec.end());// 现在vec前三个元素是1, 2, 3后面是未排序的4, 5, 63.2 nth_element重新排列范围使得指定位置的元素等于排序后的元素并且左边的元素都不大于它右边的元素都不小于它1234std::vectorint vec {5, 3, 1, 4, 2, 6};// 找到第三小的元素索引2std::nth_element(vec.begin(), vec.begin() 2, vec.end());// 现在vec[2]是3它左边的元素3右边的33.3 binary_search、lower_bound、upper_bound需在已排序的容器上使用binary_search(begin, end, value)判断value是否存在返回bool。lower_bound(begin, end, value)返回第一个不小于value的元素迭代器。upper_bound(begin, end, value)返回第一个大于value的元素迭代器。123456789vectorint sorted {1, 3, 3, 5, 7};// 必须先排序// 判断3是否存在boolexists binary_search(sorted.begin(), sorted.end(), 3);// true// 查找第一个3的元素auto lb lower_bound(sorted.begin(), sorted.end(), 3);cout lower_bound index: lb - sorted.begin() endl;// 输出1// 查找第一个3的元素auto ub upper_bound(sorted.begin(), sorted.end(), 3);cout upper_bound index: ub - sorted.begin() endl;// 输出33.4 merge合并两个已排序的范围到新容器保持排序12345vectorint a {1, 3, 5};vectorint b {2, 4, 6};vectorint merged(a.size() b.size());// 合并a和b均需已排序merge(a.begin(), a.end(), b.begin(), b.end(), merged.begin());// merged: [1,2,3,4,5,6]4、堆算法STL提供了将范围作为堆来操作的算法包括make_heap,push_heap,pop_heap,sort_heap等。12345678std::vectorint vec {4, 1, 3, 2, 5};std::make_heap(vec.begin(), vec.end());// 构建最大堆vec变为{5, 4, 3, 2, 1}vec.push_back(6);std::push_heap(vec.begin(), vec.end());// 将新元素加入堆vec变为{6, 4, 5, 2, 1, 3}std::pop_heap(vec.begin(), vec.end());// 将最大元素移到末尾vec变为{5, 4, 3, 2, 1, 6}intmax_val vec.back();// 获取最大元素6vec.pop_back();// 移除最大元素std::sort_heap(vec.begin(), vec.end());// 将堆排序为升序序列vec变为{1, 2, 3, 4, 5}5、最小/最大值算法5.1 min 和 max返回两个值或初始化列表中的最小/最大值12345inta 5, b 3;intmin_val std::min(a, b);// 3intmax_val std::max(a, b);// 5auto min_of_list std::min({4, 2, 8, 5, 1});// 1auto max_of_list std::max({4, 2, 8, 5, 1});// 85.2 min_element 和 max_element返回范围内的最小/最大元素的迭代器123std::vectorint vec {3, 1, 4, 2, 5};auto min_it std::min_element(vec.begin(), vec.end());// 指向1auto max_it std::max_element(vec.begin(), vec.end());// 指向55.3 minmax_element (C11)同时返回范围内的最小和最大元素的迭代器123std::vectorint vec {3, 1, 4, 2, 5};auto minmax std::minmax_element(vec.begin(), vec.end());// minmax.first指向1minmax.second指向56、数值算法在numeric中6.1 accumulate计算范围内元素的累加和或自定义操作1234#include numericstd::vectorint vec {1, 2, 3, 4, 5};intsum std::accumulate(vec.begin(), vec.end(), 0);// 和初始值为0结果为15intproduct std::accumulate(vec.begin(), vec.end(), 1, std::multipliesint());// 乘积初始值为1结果为1206.2 inner_product计算两个范围的内积或自定义操作123std::vectorint a {1, 2, 3};std::vectorint b {4, 5, 6};intdot std::inner_product(a.begin(), a.end(), b.begin(), 0);// 1*4 2*5 3*6 326.3 iota用连续递增的值填充范围12std::vectorint vec(5);std::iota(vec.begin(), vec.end(), 10);// 填充为10, 11, 12, 13, 146.4 partial_sum计算部分和将结果存储在目标范围内123std::vectorint src {1, 2, 3, 4, 5};std::vectorint dst(src.size());std::partial_sum(src.begin(), src.end(), dst.begin());// dst变为{1, 3, 6, 10, 15}6.5 adjacent_difference计算相邻元素的差值将结果存储在目标范围内123std::vectorint src {1, 2, 3, 4, 5};std::vectorint dst(src.size());std::adjacent_difference(src.begin(), src.end(), dst.begin());// dst变为{1, 1, 1, 1, 1}7、其他7.1 generate用生成函数填充范围12345std::vectorint vec(5);intn 0;std::generate(vec.begin(), vec.end(), [n]() {returnn;});// 填充为0, 1, 2, 3, 47.2 generate_n用生成函数填充范围的开始n个元素12345std::vectorint vec(5);intn 10;std::generate_n(vec.begin(), 3, [n]() {returnn;});// 前三个元素为10, 11, 12后两个保持不变7.3 includes检查一个排序范围是否包含另一个排序范围的所有元素123std::vectorint vec1 {1, 2, 3, 4, 5};std::vectorint vec2 {2, 4};boolincludes std::includes(vec1.begin(), vec1.end(), vec2.begin(), vec2.end());// true7.3 set_union, set_intersection, set_difference, set_symmetric_difference执行集合操作并集、交集、差集和对称差集123456789101112131415161718std::vectorint v1 {1, 2, 3, 4, 5};std::vectorint v2 {3, 4, 5, 6, 7};std::vectorint result;// 并集std::set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(result));// result为{1, 2, 3, 4, 5, 6, 7}// 交集result.clear();std::set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(result));// result为{3, 4, 5}// 差集 (v1 - v2)result.clear();std::set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(result));// result为{1, 2}// 对称差集 (v1 ∪ v2 - v1 ∩ v2)result.clear();std::set_symmetric_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(result));// result为{1, 2, 6, 7}8、常见问题sort与stable_sort的区别sort采用快速排序实际是 introsort 算法不稳定相等元素的相对位置可能改变平均时间复杂度 O (n log n)。stable_sort采用归并排序稳定相等元素相对位置不变时间复杂度 O (n log n)但空间开销略大。
C++ STL 常用算法操作实例详解
C 标准模板库STL提供了丰富的算法库定义在algorithm头文件中这些算法多为通用函数模板可配合容器和迭代器高效操作数据。1、非修改序列算法这些算法不会改变它们所操作的容器中的元素。1.1 find 和 find_iffind(begin, end, value)查找第一个等于value的元素返回迭代器未找到返回end。find_if(begin, end, predicate)查找第一个满足谓词的元素。find_end(begin, end, sub_begin, sub_end)查找子序列最后一次出现的位置。1234567891011121314151617vectorint nums {1, 3, 5, 7, 9};// 查找值为5的元素auto it find(nums.begin(), nums.end(), 5);if(it ! nums.end()) {cout found: *it endl;// 输出5}// 查找第一个大于6的元素auto it2 find_if(nums.begin(), nums.end(), [](intx) {returnx 6;});cout first 6: *it2 endl;// 输出7// 查找子序列vectorint sub {3, 5};auto it3 find_end(nums.begin(), nums.end(), sub.begin(), sub.end());if(it3 ! nums.end()) {cout subsequence starts at index: it3 - nums.begin() endl;// 输出1}1.2 count 和 count_ifcount(begin, end, value)统计等于value的元素个数。count_if(begin, end, predicate)统计满足谓词predicate的元素个数。12345std::vectorint vec {1, 2, 3, 2, 4, 2};intcnt std::count(vec.begin(), vec.end(), 2);// 计数2的个数结果为3inteven_cnt std::count_if(vec.begin(), vec.end(), [](intx) {returnx % 2 0;});// 偶数个数结果为41.3 for_each对范围内的每个元素应用一个函数12345std::vectorint vec {1, 2, 3, 4, 5};std::for_each(vec.begin(), vec.end(), [](int x) {x * 2;// 将每个元素乘以2});// 现在vec变为{2, 4, 6, 8, 10}1.4 equal 与 mismatchequal(b1, e1, b2)判断两个范围[b1,e1)和[b2, b2(e1-b1))是否相等。mismatch(b1, e1, b2)返回两个范围中第一个不相等元素的迭代器对pair。1234567891011vectorint a {1, 2, 3};vectorint b {1, 2, 4};vectorint c {1, 2, 3, 4};// 比较a和b的前3个元素boolis_equal equal(a.begin(), a.end(), b.begin());cout a b? boolalpha is_equal endl;// 输出false// 查找a和c的第一个不匹配元素auto mis mismatch(a.begin(), a.end(), c.begin());if(mis.first ! a.end()) {cout mismatch: *mis.first vs *mis.second endl;// 无输出a和c前3元素相等}1.5 all_of, any_of, none_of检查范围内元素是否全部、存在或没有满足条件的12345678910std::vectorint vec {2, 4, 6, 8};boolall_even std::all_of(vec.begin(), vec.end(), [](intx) {returnx % 2 0;});// trueboolany_odd std::any_of(vec.begin(), vec.end(), [](intx) {returnx % 2 ! 0;});// falseboolnone_negative std::none_of(vec.begin(), vec.end(), [](intx) {returnx 0;});// true2、修改序列算法这些算法会修改它们所操作的容器中的元素。2.1 copy 和 copy_ifcopy(begin, end, dest)将[begin, end)中的元素复制到dest开始的位置。copy_if(begin, end, dest, predicate)复制满足谓词的元素到dest。123456789vectorint src {1, 2, 3, 4, 5};vectorint dest(5);// 需预先分配足够空间// 复制所有元素copy(src.begin(), src.end(), dest.begin());// dest: [1,2,3,4,5]// 复制偶数元素到新容器vectorint evens;copy_if(src.begin(), src.end(), back_inserter(evens), [](intx) {returnx % 2 0;});// evens: [2,4]注意back_inserter(dest)会自动调用push_back无需提前分配空间。2.2 transform对范围内的每个元素应用一个函数并将结果存储在另一个范围内12345678910111213vectorint nums {1, 2, 3};vectorint squares(3);// 计算平方单参数转换transform(nums.begin(), nums.end(), squares.begin(), [](intx) {returnx * x;});// squares: [1,4,9]// 两容器元素相加双参数转换vectorint a {1, 2, 3};vectorint b {4, 5, 6};vectorint sum(3);transform(a.begin(), a.end(), b.begin(), sum.begin(), [](intx,inty) {returnx y;});// sum: [5,7,9]2.3 replace、replace_if与 replace_copyreplace(begin, end, old_val, new_val)将所有old_val替换为new_val。replace_if(begin, end, predicate, new_val)替换满足谓词的元素。replace_copy(begin, end, dest, old_val, new_val)复制时替换元素不修改原容器。12345678910vectorint nums {1, 2, 3, 2, 5};// 替换所有2为20replace(nums.begin(), nums.end(), 2, 20);// nums: [1,20,3,20,5]// 替换大于10的元素为0replace_if(nums.begin(), nums.end(), [](intx) {returnx 10;}, 0);// nums: [1,0,3,0,5]// 复制时替换3为300原容器不变vectorint res;replace_copy(nums.begin(), nums.end(), back_inserter(res), 3, 300);// res: [1,0,300,0,5]2.4 remove、remove_if 与 eraseremove(begin, end, value)将等于value的元素 “移动” 到容器末尾返回新的逻辑尾迭代器不实际删除元素需配合erase。remove_if(begin, end, predicate)移动满足谓词的元素到末尾。12345678910vectorint nums {1, 2, 3, 2, 4};// 逻辑删除所有2移动到末尾auto new_end remove(nums.begin(), nums.end(), 2);// nums: [1,3,4,2,2]// 物理删除真正移除元素nums.erase(new_end, nums.end());// nums: [1,3,4]// 结合lambda删除偶数nums {1, 2, 3, 4, 5};nums.erase(remove_if(nums.begin(), nums.end(), [](intx) {returnx % 2 0;}), nums.end());// nums: [1,3,5]2.5 unique移除范围内连续的重复元素返回新的逻辑结尾迭代器。通常与erase结合使用。123std::vectorint vec {1, 1, 2, 2, 3, 3, 3, 4, 5};auto last std::unique(vec.begin(), vec.end());vec.erase(last, vec.end());// vec变为{1, 2, 3, 4, 5}2.6 reverse反转范围内的元素顺序12std::vectorint vec {1, 2, 3, 4, 5};std::reverse(vec.begin(), vec.end());// vec变为{5, 4, 3, 2, 1}2.7 rotate旋转范围内的元素使中间元素成为新的第一个元素12std::vectorint vec {1, 2, 3, 4, 5};std::rotate(vec.begin(), vec.begin() 2, vec.end());// 以3为起点旋转vec变为{3, 4, 5, 1, 2}2.8 shuffle随机重排范围内的元素需要C11或更高版本123456#include random#include algorithmstd::vectorint vec {1, 2, 3, 4, 5};std::random_device rd;std::mt19937 g(rd());std::shuffle(vec.begin(), vec.end(), g);// 随机打乱vec中的元素3、排序和相关算法3.1 sort、stable_sort 与 partial_sortsort(begin, end)对元素进行快速排序不稳定平均时间复杂度 O (n log n)。stable_sort(begin, end)稳定排序相等元素相对位置不变。partial_sort(begin, mid, end)部分排序使[begin, mid)为整个范围中最小的元素并排序。1234567891011121314std::vectorint vec {5, 3, 1, 4, 2};std::sort(vec.begin(), vec.end());// 默认升序vec变为{1, 2, 3, 4, 5}std::sort(vec.begin(), vec.end(), std::greaterint());// 降序vec变为{5, 4, 3, 2, 1}std::sort(vec.begin(), vec.end(), [](inta,intb) {returna b;});// 升序自定义比较std::vectorstd::pairint,int vec {{1, 2}, {2, 1}, {1, 1}, {2, 2}};std::stable_sort(vec.begin(), vec.end(), [](constauto a,constauto b) {returna.first b.first;// 按first排序保持相等元素的相对顺序});std::vectorint vec {5, 3, 1, 4, 2, 6};// 将最小的3个元素放在前面并排序std::partial_sort(vec.begin(), vec.begin() 3, vec.end());// 现在vec前三个元素是1, 2, 3后面是未排序的4, 5, 63.2 nth_element重新排列范围使得指定位置的元素等于排序后的元素并且左边的元素都不大于它右边的元素都不小于它1234std::vectorint vec {5, 3, 1, 4, 2, 6};// 找到第三小的元素索引2std::nth_element(vec.begin(), vec.begin() 2, vec.end());// 现在vec[2]是3它左边的元素3右边的33.3 binary_search、lower_bound、upper_bound需在已排序的容器上使用binary_search(begin, end, value)判断value是否存在返回bool。lower_bound(begin, end, value)返回第一个不小于value的元素迭代器。upper_bound(begin, end, value)返回第一个大于value的元素迭代器。123456789vectorint sorted {1, 3, 3, 5, 7};// 必须先排序// 判断3是否存在boolexists binary_search(sorted.begin(), sorted.end(), 3);// true// 查找第一个3的元素auto lb lower_bound(sorted.begin(), sorted.end(), 3);cout lower_bound index: lb - sorted.begin() endl;// 输出1// 查找第一个3的元素auto ub upper_bound(sorted.begin(), sorted.end(), 3);cout upper_bound index: ub - sorted.begin() endl;// 输出33.4 merge合并两个已排序的范围到新容器保持排序12345vectorint a {1, 3, 5};vectorint b {2, 4, 6};vectorint merged(a.size() b.size());// 合并a和b均需已排序merge(a.begin(), a.end(), b.begin(), b.end(), merged.begin());// merged: [1,2,3,4,5,6]4、堆算法STL提供了将范围作为堆来操作的算法包括make_heap,push_heap,pop_heap,sort_heap等。12345678std::vectorint vec {4, 1, 3, 2, 5};std::make_heap(vec.begin(), vec.end());// 构建最大堆vec变为{5, 4, 3, 2, 1}vec.push_back(6);std::push_heap(vec.begin(), vec.end());// 将新元素加入堆vec变为{6, 4, 5, 2, 1, 3}std::pop_heap(vec.begin(), vec.end());// 将最大元素移到末尾vec变为{5, 4, 3, 2, 1, 6}intmax_val vec.back();// 获取最大元素6vec.pop_back();// 移除最大元素std::sort_heap(vec.begin(), vec.end());// 将堆排序为升序序列vec变为{1, 2, 3, 4, 5}5、最小/最大值算法5.1 min 和 max返回两个值或初始化列表中的最小/最大值12345inta 5, b 3;intmin_val std::min(a, b);// 3intmax_val std::max(a, b);// 5auto min_of_list std::min({4, 2, 8, 5, 1});// 1auto max_of_list std::max({4, 2, 8, 5, 1});// 85.2 min_element 和 max_element返回范围内的最小/最大元素的迭代器123std::vectorint vec {3, 1, 4, 2, 5};auto min_it std::min_element(vec.begin(), vec.end());// 指向1auto max_it std::max_element(vec.begin(), vec.end());// 指向55.3 minmax_element (C11)同时返回范围内的最小和最大元素的迭代器123std::vectorint vec {3, 1, 4, 2, 5};auto minmax std::minmax_element(vec.begin(), vec.end());// minmax.first指向1minmax.second指向56、数值算法在numeric中6.1 accumulate计算范围内元素的累加和或自定义操作1234#include numericstd::vectorint vec {1, 2, 3, 4, 5};intsum std::accumulate(vec.begin(), vec.end(), 0);// 和初始值为0结果为15intproduct std::accumulate(vec.begin(), vec.end(), 1, std::multipliesint());// 乘积初始值为1结果为1206.2 inner_product计算两个范围的内积或自定义操作123std::vectorint a {1, 2, 3};std::vectorint b {4, 5, 6};intdot std::inner_product(a.begin(), a.end(), b.begin(), 0);// 1*4 2*5 3*6 326.3 iota用连续递增的值填充范围12std::vectorint vec(5);std::iota(vec.begin(), vec.end(), 10);// 填充为10, 11, 12, 13, 146.4 partial_sum计算部分和将结果存储在目标范围内123std::vectorint src {1, 2, 3, 4, 5};std::vectorint dst(src.size());std::partial_sum(src.begin(), src.end(), dst.begin());// dst变为{1, 3, 6, 10, 15}6.5 adjacent_difference计算相邻元素的差值将结果存储在目标范围内123std::vectorint src {1, 2, 3, 4, 5};std::vectorint dst(src.size());std::adjacent_difference(src.begin(), src.end(), dst.begin());// dst变为{1, 1, 1, 1, 1}7、其他7.1 generate用生成函数填充范围12345std::vectorint vec(5);intn 0;std::generate(vec.begin(), vec.end(), [n]() {returnn;});// 填充为0, 1, 2, 3, 47.2 generate_n用生成函数填充范围的开始n个元素12345std::vectorint vec(5);intn 10;std::generate_n(vec.begin(), 3, [n]() {returnn;});// 前三个元素为10, 11, 12后两个保持不变7.3 includes检查一个排序范围是否包含另一个排序范围的所有元素123std::vectorint vec1 {1, 2, 3, 4, 5};std::vectorint vec2 {2, 4};boolincludes std::includes(vec1.begin(), vec1.end(), vec2.begin(), vec2.end());// true7.3 set_union, set_intersection, set_difference, set_symmetric_difference执行集合操作并集、交集、差集和对称差集123456789101112131415161718std::vectorint v1 {1, 2, 3, 4, 5};std::vectorint v2 {3, 4, 5, 6, 7};std::vectorint result;// 并集std::set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(result));// result为{1, 2, 3, 4, 5, 6, 7}// 交集result.clear();std::set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(result));// result为{3, 4, 5}// 差集 (v1 - v2)result.clear();std::set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(result));// result为{1, 2}// 对称差集 (v1 ∪ v2 - v1 ∩ v2)result.clear();std::set_symmetric_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(result));// result为{1, 2, 6, 7}8、常见问题sort与stable_sort的区别sort采用快速排序实际是 introsort 算法不稳定相等元素的相对位置可能改变平均时间复杂度 O (n log n)。stable_sort采用归并排序稳定相等元素相对位置不变时间复杂度 O (n log n)但空间开销略大。
