1. C标准库算法概览C标准库提供了丰富的算法主要定义在 和 头文件中。这些算法可以大大简化我们的编程工作避免重复造轮子。根据算法对容器的影响我们可以将其分为两大类非修改序列算法和修改序列算法。非修改序列算法不会改变容器中的元素内容主要包括查找、计数、遍历等操作。这类算法通常以容器的begin和end迭代器作为参数对容器中的元素进行只读访问。例如find、count、for_each等算法都属于这一类。修改序列算法则会改变容器中的元素内容或顺序包括复制、替换、删除、排序等操作。这类算法通常也会接收容器的begin和end迭代器但会对元素进行修改。例如copy、replace、sort等算法都属于这一类。2. 非修改序列算法详解2.1 查找算法查找算法是日常编程中最常用的算法之一。C提供了多种查找方式可以满足不同的需求场景。2.1.1 find和find_iffind算法用于在指定范围内查找特定值的元素vectorint nums {1, 3, 5, 7, 9}; auto it find(nums.begin(), nums.end(), 5); if (it ! nums.end()) { cout Found: *it endl; }find_if算法则更加灵活它接受一个谓词函数查找第一个满足条件的元素auto it find_if(nums.begin(), nums.end(), [](int x) { return x 6; });提示对于自定义类型的查找需要确保类型支持运算符或者提供自定义的比较函数。2.1.2 find_end和searchfind_end算法用于查找子序列最后一次出现的位置vectorint main {1,2,3,4,1,2,3}; vectorint sub {1,2}; auto it find_end(main.begin(), main.end(), sub.begin(), sub.end());search算法与find_end类似但它查找的是子序列第一次出现的位置。2.2 计数算法2.2.1 count和count_ifcount算法统计范围内等于指定值的元素个数vectorint vec {1, 2, 3, 2, 4, 2}; int cnt count(vec.begin(), vec.end(), 2); // 结果为3count_if则统计满足特定条件的元素个数int even_cnt count_if(vec.begin(), vec.end(), [](int x) { return x % 2 0; });2.3 遍历算法for_eachfor_each算法对范围内的每个元素应用一个函数vectorint vec {1, 2, 3, 4, 5}; for_each(vec.begin(), vec.end(), [](int x) { x * 2; });注意for_each不会返回修改后的容器它只是应用函数到每个元素上。如果需要保留结果可以使用transform算法。2.4 比较算法2.4.1 equal和mismatchequal算法判断两个范围是否相等vectorint a {1, 2, 3}; vectorint b {1, 2, 3}; bool is_equal equal(a.begin(), a.end(), b.begin());mismatch算法返回两个范围中第一个不匹配的位置auto p mismatch(a.begin(), a.end(), b.begin()); if (p.first ! a.end()) { cout First mismatch: *p.first vs *p.second endl; }2.4.2 all_of/any_of/none_of这些算法检查范围内的元素是否满足特定条件vectorint vec {2, 4, 6, 8}; bool all_even all_of(vec.begin(), vec.end(), [](int x) { return x % 2 0; });3. 修改序列算法详解3.1 复制算法3.1.1 copy和copy_ifcopy算法将源范围复制到目标位置vectorint src {1, 2, 3, 4, 5}; vectorint dest(5); copy(src.begin(), src.end(), dest.begin());copy_if算法只复制满足条件的元素vectorint evens; copy_if(src.begin(), src.end(), back_inserter(evens), [](int x) { return x % 2 0; });提示使用back_inserter可以自动处理目标容器大小问题非常方便。3.2 变换算法transformtransform算法对范围内的元素进行转换并将结果存储到目标位置vectorint nums {1, 2, 3}; vectorint squares(3); transform(nums.begin(), nums.end(), squares.begin(), [](int x) { return x * x; });transform还可以处理两个输入范围vectorint a {1, 2, 3}; vectorint b {4, 5, 6}; vectorint sum(3); transform(a.begin(), a.end(), b.begin(), sum.begin(), [](int x, int y) { return x y; });3.3 替换算法3.3.1 replace和replace_ifreplace算法将指定值替换为新值vectorint nums {1, 2, 3, 2, 5}; replace(nums.begin(), nums.end(), 2, 20);replace_if算法替换满足条件的元素replace_if(nums.begin(), nums.end(), [](int x) { return x 10; }, 0);3.3.2 replace_copyreplace_copy算法在复制过程中进行替换不修改原容器vectorint res; replace_copy(nums.begin(), nums.end(), back_inserter(res), 3, 300);3.4 删除算法3.4.1 remove和remove_ifremove算法移除指定值的元素实际是移动到末尾vectorint nums {1, 2, 3, 2, 4}; auto new_end remove(nums.begin(), nums.end(), 2); nums.erase(new_end, nums.end());remove_if算法移除满足条件的元素nums.erase(remove_if(nums.begin(), nums.end(), [](int x) { return x % 2 0; }), nums.end());重要remove系列算法不会改变容器大小必须配合erase使用才能真正删除元素。3.4.2 unique算法unique算法移除连续的重复元素vectorint vec {1, 1, 2, 2, 3, 3, 3, 4, 5}; auto last unique(vec.begin(), vec.end()); vec.erase(last, vec.end());注意unique只处理相邻的重复元素如果需要移除所有重复元素应先排序。3.5 其他修改算法3.5.1 reverse算法reverse算法反转范围内的元素顺序vectorint vec {1, 2, 3, 4, 5}; reverse(vec.begin(), vec.end());3.5.2 rotate算法rotate算法旋转范围内的元素vectorint vec {1, 2, 3, 4, 5}; rotate(vec.begin(), vec.begin() 2, vec.end());3.5.3 shuffle算法shuffle算法随机打乱元素顺序random_device rd; mt19937 g(rd()); shuffle(vec.begin(), vec.end(), g);4. 排序及相关算法4.1 基本排序算法4.1.1 sort算法sort算法对范围进行排序vectorint vec {5, 3, 1, 4, 2}; sort(vec.begin(), vec.end()); // 升序 sort(vec.begin(), vec.end(), greaterint()); // 降序4.1.2 stable_sort算法stable_sort是稳定的排序算法保持相等元素的相对顺序vectorpairint, int vec {{1, 2}, {2, 1}, {1, 1}, {2, 2}}; stable_sort(vec.begin(), vec.end(), [](const auto a, const auto b) { return a.first b.first; });4.1.3 partial_sort算法partial_sort算法部分排序使前N个元素有序vectorint vec {5, 3, 1, 4, 2, 6}; partial_sort(vec.begin(), vec.begin() 3, vec.end());4.2 其他排序相关算法4.2.1 nth_element算法nth_element算法使第n个元素处于正确位置vectorint vec {5, 3, 1, 4, 2, 6}; nth_element(vec.begin(), vec.begin() 2, vec.end());4.2.2 二分查找算法二分查找算法要求范围已排序vectorint sorted {1, 3, 3, 5, 7}; bool exists binary_search(sorted.begin(), sorted.end(), 3); auto lb lower_bound(sorted.begin(), sorted.end(), 3); auto ub upper_bound(sorted.begin(), sorted.end(), 3);4.2.3 merge算法merge算法合并两个已排序的范围vectorint a {1, 3, 5}; vectorint b {2, 4, 6}; vectorint merged(a.size() b.size()); merge(a.begin(), a.end(), b.begin(), b.end(), merged.begin());5. 堆算法C标准提供了将序列作为堆操作的算法vectorint vec {4, 1, 3, 2, 5}; make_heap(vec.begin(), vec.end()); // 构建最大堆 vec.push_back(6); push_heap(vec.begin(), vec.end()); // 加入新元素 pop_heap(vec.begin(), vec.end()); // 将最大元素移到末尾 vec.pop_back(); // 移除最大元素 sort_heap(vec.begin(), vec.end()); // 堆排序6. 数值算法数值算法定义在 头文件中6.1 accumulate算法accumulate算法计算累加和或自定义操作vectorint vec {1, 2, 3, 4, 5}; int sum accumulate(vec.begin(), vec.end(), 0); int product accumulate(vec.begin(), vec.end(), 1, multipliesint());6.2 inner_product算法inner_product算法计算内积vectorint a {1, 2, 3}; vectorint b {4, 5, 6}; int dot inner_product(a.begin(), a.end(), b.begin(), 0);6.3 iota算法iota算法填充递增序列vectorint vec(5); iota(vec.begin(), vec.end(), 10); // 10,11,12,13,146.4 partial_sum算法partial_sum算法计算部分和vectorint src {1, 2, 3, 4, 5}; vectorint dst(src.size()); partial_sum(src.begin(), src.end(), dst.begin());6.5 adjacent_difference算法adjacent_difference算法计算相邻差值vectorint src {1, 2, 3, 4, 5}; vectorint dst(src.size()); adjacent_difference(src.begin(), src.end(), dst.begin());7. 其他实用算法7.1 generate算法generate算法用生成函数填充范围vectorint vec(5); int n 0; generate(vec.begin(), vec.end(), [n]() { return n; });7.2 集合算法集合算法要求输入范围已排序vectorint v1 {1, 2, 3, 4, 5}; vectorint v2 {3, 4, 5, 6, 7}; vectorint result; set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(result)); set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(result)); set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(result)); set_symmetric_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(result));8. 算法使用经验与技巧在实际项目中使用STL算法时我总结了一些有价值的经验算法组合使用很多算法可以组合使用实现复杂功能。例如先用sort排序再用unique和erase删除重复元素。谓词函数的优化对于频繁调用的谓词函数如sort的比较函数尽量使其简单高效。复杂的谓词会显著影响算法性能。迭代器失效问题在修改容器时要注意迭代器失效问题。例如在循环中调用erase会使当前迭代器失效。算法选择根据需求选择合适的算法。例如如果只需要前N个有序元素使用partial_sort比完全排序更高效。C17的新特性C17引入了并行算法执行策略如par、par_unseq可以显著提升算法在多核处理器上的性能。内存分配考虑对于back_inserter等插入迭代器频繁的内存分配可能影响性能。预先分配足够空间可以提高效率。自定义类型的支持对于自定义类型需要确保实现了必要的运算符如、等或者提供自定义的比较函数。算法复杂度了解不同算法的时间复杂度对于大数据量操作尤为重要。例如sort是O(n log n)而find是O(n)。