1. 迭代算法for_each核心特性最基础的遍历算法对区间[first, last)中的每个元素执行指定操作是非修改性算法除非操作函数显式修改元素支持自定义操作函数指针、函数对象、Lambda 表达式返回值C11 后返回传入的操作函数对象函数原型templateclass InputIt, class UnaryFunction UnaryFunction for_each(InputIt first, InputIt last, UnaryFunction f);用法示例#include iostream #include vector #include algorithm int main() { std::vectorint vec {1, 2, 3, 4, 5}; // 1. 普通函数作为操作 auto print [](int x) { std::cout x ; }; std::for_each(vec.begin(), vec.end(), print); // 输出1 2 3 4 5 std::cout std::endl; // 2. 修改元素通过引用捕获 std::for_each(vec.begin(), vec.end(), [](int x) { x * 2; }); // 现在vec{2, 4, 6, 8, 10} // 3. 捕获外部变量 int sum 0; std::for_each(vec.begin(), vec.end(), [sum](int x) { sum x; }); std::cout 总和 sum std::endl; // 输出30 return 0; }注意事项与 C11 范围 for 循环的区别for_each可以返回操作函数对象适合需要累积状态的场景操作函数的参数如果是值传递无法修改原元素必须使用引用传递int x时间复杂度O (n)遍历一次区间2. 查找算法核心特性在区间中查找单个元素或满足条件的元素返回值找到则返回指向该元素的迭代器未找到则返回last迭代器适用于无序区间有序区间优先使用二分查找效率更高常用函数函数功能find(first, last, value)查找第一个等于value的元素find_if(first, last, pred)查找第一个满足谓词pred的元素find_if_not(first, last, pred)查找第一个不满足谓词pred的元素C11adjacent_find(first, last)查找第一对相邻且相等的元素find_first_of(first1, last1, first2, last2)查找区间 1 中第一个出现在区间 2 中的元素用法示例#include iostream #include vector #include algorithm int main() { std::vectorint vec {1, 3, 5, 3, 7, 9, 3}; // 1. 查找指定值 auto it1 std::find(vec.begin(), vec.end(), 3); if (it1 ! vec.end()) { std::cout 找到3位置 it1 - vec.begin() std::endl; // 输出1 } // 2. 查找第一个大于5的元素 auto it2 std::find_if(vec.begin(), vec.end(), [](int x) { return x 5; }); std::cout 第一个大于5的元素 *it2 std::endl; // 输出7 // 3. 查找第一对相邻相等的元素 std::vectorint vec2 {1, 2, 2, 3, 3, 3}; auto it3 std::adjacent_find(vec2.begin(), vec2.end()); std::cout 第一对相邻相等的元素 *it3 std::endl; // 输出2 return 0; }3. 搜索算法核心特性在区间中查找子序列或连续重复元素与查找算法的区别查找单个元素 vs 查找多个元素组成的序列返回值找到则返回子序列起始位置的迭代器未找到则返回last常用函数函数功能search(first1, last1, first2, last2)查找区间 1 中第一个出现的区间 2 子序列find_end(first1, last1, first2, last2)查找区间 1 中最后一个出现的区间 2 子序列search_n(first, last, count, value)查找连续count个等于value的元素用法示例#include iostream #include vector #include algorithm int main() { std::vectorint text {1, 2, 3, 4, 2, 3, 4, 5}; std::vectorint pattern {2, 3, 4}; // 1. 查找第一个子序列 auto it1 std::search(text.begin(), text.end(), pattern.begin(), pattern.end()); if (it1 ! text.end()) { std::cout 第一个子序列起始位置 it1 - text.begin() std::endl; // 输出1 } // 2. 查找最后一个子序列 auto it2 std::find_end(text.begin(), text.end(), pattern.begin(), pattern.end()); std::cout 最后一个子序列起始位置 it2 - text.begin() std::endl; // 输出4 // 3. 查找连续3个5 std::vectorint vec {1, 5, 5, 5, 2, 5}; auto it3 std::search_n(vec.begin(), vec.end(), 3, 5); if (it3 ! vec.end()) { std::cout 找到连续3个5起始位置 it3 - vec.begin() std::endl; // 输出1 } return 0; }4. 统计算法核心特性统计区间中满足条件的元素个数或进行数值累积分为两类计数类algorithm和数值累积类numeric常用函数头文件函数功能algorithmcount(first, last, value)统计等于value的元素个数algorithmcount_if(first, last, pred)统计满足谓词pred的元素个数numericaccumulate(first, last, init)计算区间元素与初始值init的和numericaccumulate(first, last, init, op)使用自定义操作op进行累积用法示例#include iostream #include vector #include algorithm #include numeric int main() { std::vectorint vec {1, 2, 3, 4, 5, 3, 3}; // 1. 统计等于3的元素个数 int cnt1 std::count(vec.begin(), vec.end(), 3); std::cout 3的个数 cnt1 std::endl; // 输出3 // 2. 统计偶数个数 int cnt2 std::count_if(vec.begin(), vec.end(), [](int x) { return x % 2 0; }); std::cout 偶数个数 cnt2 std::endl; // 输出2 // 3. 计算总和 int sum std::accumulate(vec.begin(), vec.end(), 0); std::cout 总和 sum std::endl; // 输出21 // 4. 计算乘积 int product std::accumulate(vec.begin(), vec.end(), 1, std::multipliesint()); std::cout 乘积 product std::endl; // 输出540 return 0; }5. 复制或变换算法核心特性将源区间的元素复制或变换后复制到目标区间要求目标区间有足够的空间否则使用back_inserter等插入迭代器变换算法可以对每个元素执行自定义操作常用函数函数功能copy(first, last, d_first)将区间[first, last)复制到以d_first开头的目标区间copy_if(first, last, d_first, pred)只复制满足谓词pred的元素C11copy_n(first, n, d_first)复制前n个元素C11transform(first, last, d_first, unary_op)对每个元素执行一元操作unary_op后复制transform(first1, last1, first2, d_first, binary_op)对两个区间的元素执行二元操作后复制用法示例#include iostream #include vector #include algorithm #include iterator // 用于back_inserter int main() { std::vectorint src {1, 2, 3, 4, 5}; std::vectorint dest; // 1. 复制所有元素使用back_inserter自动扩容 std::copy(src.begin(), src.end(), std::back_inserter(dest)); // dest{1, 2, 3, 4, 5} // 2. 复制偶数元素 std::vectorint even; std::copy_if(src.begin(), src.end(), std::back_inserter(even), [](int x) { return x % 2 0; }); // even{2, 4} // 3. 元素平方变换 std::vectorint squared; std::transform(src.begin(), src.end(), std::back_inserter(squared), [](int x) { return x * x; }); // squared{1, 4, 9, 16, 25} // 4. 两个区间元素相加 std::vectorint a {1, 2, 3}; std::vectorint b {4, 5, 6}; std::vectorint c; std::transform(a.begin(), a.end(), b.begin(), std::back_inserter(c), std::plusint()); // c{5, 7, 9} return 0; }6. 填充算法核心特性用指定值或生成的值填充区间分为两类固定值填充和生成值填充常用函数函数功能fill(first, last, value)用value填充区间[first, last)fill_n(first, n, value)用value填充前n个元素generate(first, last, gen)用生成函数gen的返回值填充区间generate_n(first, n, gen)用生成函数gen的返回值填充前n个元素用法示例#include iostream #include vector #include algorithm #include random int main() { std::vectorint vec(5); // 1. 填充固定值 std::fill(vec.begin(), vec.end(), 10); // vec{10, 10, 10, 10, 10} // 2. 填充前3个元素为0 std::fill_n(vec.begin(), 3, 0); // vec{0, 0, 0, 10, 10} // 3. 生成随机数填充 std::random_device rd; std::mt19937 gen(rd()); std::uniform_int_distribution dis(1, 100); std::generate(vec.begin(), vec.end(), []() { return dis(gen); }); // 示例输出{42, 17, 89, 3, 56} return 0; }7. 删除算法⚠️ 核心注意事项STL 删除算法不会真正删除容器元素只是将需要保留的元素移到区间前部返回新的尾迭代器。必须配合容器的erase方法才能真正释放内存。常用函数函数功能remove(first, last, value)移除所有等于value的元素remove_if(first, last, pred)移除所有满足谓词pred的元素unique(first, last)移除相邻重复的元素需先排序unique(first, last, pred)使用自定义谓词判断重复用法示例#include iostream #include vector #include algorithm int main() { std::vectorint vec {1, 3, 2, 3, 4, 3, 5}; // 1. 删除所有等于3的元素 auto new_end1 std::remove(vec.begin(), vec.end(), 3); // 此时vec{1, 2, 4, 5, ?, ?, ?}?为未定义值 vec.erase(new_end1, vec.end()); // 真正删除 // vec{1, 2, 4, 5} // 2. 删除所有偶数 std::vectorint vec2 {1, 2, 3, 4, 5, 6}; auto new_end2 std::remove_if(vec2.begin(), vec2.end(), [](int x) { return x % 2 0; }); vec2.erase(new_end2, vec2.end()); // vec2{1, 3, 5} // 3. 去重必须先排序 std::vectorint vec3 {1, 2, 2, 3, 3, 3, 4}; std::sort(vec3.begin(), vec3.end()); // 先排序 auto new_end3 std::unique(vec3.begin(), vec3.end()); vec3.erase(new_end3, vec3.end()); // vec3{1, 2, 3, 4} return 0; }8. 排序算法核心特性STL 提供了多种排序算法适用于不同场景默认使用运算符比较支持自定义比较函数时间复杂度O (n log n)主流排序算法常用函数函数功能时间复杂度稳定性sort(first, last)对区间进行快速排序不稳定O(n log n)不稳定stable_sort(first, last)对区间进行归并排序稳定O(n log n)稳定partial_sort(first, middle, last)对前middle-first个元素排序O (n log k)k 为排序元素个数不稳定nth_element(first, nth, last)将第 n 个元素放到正确位置左边都小于它右边都大于它O(n)不稳定用法示例#include iostream #include vector #include algorithm int main() { std::vectorint vec {5, 2, 9, 1, 5, 6}; // 1. 默认升序排序 std::sort(vec.begin(), vec.end()); // vec{1, 2, 5, 5, 6, 9} // 2. 自定义降序排序 std::sort(vec.begin(), vec.end(), std::greaterint()); // vec{9, 6, 5, 5, 2, 1} // 3. 部分排序前3个元素有序 std::vectorint vec2 {5, 2, 9, 1, 5, 6}; std::partial_sort(vec2.begin(), vec2.begin() 3, vec2.end()); // vec2{1, 2, 5, 9, 5, 6}前3个最小的元素有序 // 4. 找第3小的元素索引从0开始 std::vectorint vec3 {5, 2, 9, 1, 5, 6}; std::nth_element(vec3.begin(), vec3.begin() 2, vec3.end()); std::cout 第3小的元素 vec3[2] std::endl; // 输出5 return 0; }9. 堆操作核心特性STL 实现了大顶堆默认即堆顶元素是最大值堆是一种完全二叉树存储在数组中所有堆操作的时间复杂度均为 O (log n)常用函数函数功能make_heap(first, last)将区间[first, last)构建成一个堆push_heap(first, last)将最后一个元素插入到堆中需先将元素加到容器末尾pop_heap(first, last)将堆顶元素移到区间末尾剩余元素重新调整为堆sort_heap(first, last)将堆转换为有序区间升序is_heap(first, last)判断区间是否是一个堆C11用法示例#include iostream #include vector #include algorithm int main() { std::vectorint heap {3, 1, 4, 1, 5, 9, 2, 6}; // 1. 构建大顶堆 std::make_heap(heap.begin(), heap.end()); // 堆顶元素是最大值9 std::cout 堆顶元素 heap.front() std::endl; // 输出9 // 2. 插入元素 heap.push_back(7); // 先加到末尾 std::push_heap(heap.begin(), heap.end()); // 调整为堆 // 现在堆顶还是9 // 3. 删除堆顶元素 std::pop_heap(heap.begin(), heap.end()); // 堆顶移到末尾 heap.pop_back(); // 真正删除 // 新堆顶7 // 4. 堆排序升序 std::sort_heap(heap.begin(), heap.end()); // heap{1, 1, 2, 3, 4, 5, 6, 7} return 0; }10. 二分查找算法核心特性要求区间必须是有序的默认升序时间复杂度O (log n)远快于线性查找的 O (n)适用于大规模有序数据的查找常用函数函数功能返回值binary_search(first, last, value)判断value是否存在于区间中boollower_bound(first, last, value)查找第一个大于等于value的元素迭代器upper_bound(first, last, value)查找第一个大于value的元素迭代器equal_range(first, last, value)返回等于value的元素区间pair 迭代器迭代器用法示例#include iostream #include vector #include algorithm int main() { std::vectorint vec {1, 2, 3, 4, 4, 4, 5, 6}; // 1. 判断元素是否存在 bool exists std::binary_search(vec.begin(), vec.end(), 4); std::cout 4是否存在 std::boolalpha exists std::endl; // 输出true // 2. 查找第一个大于等于4的元素 auto it_low std::lower_bound(vec.begin(), vec.end(), 4); std::cout 第一个4的元素位置 it_low - vec.begin() std::endl; // 输出3 // 3. 查找第一个大于4的元素 auto it_high std::upper_bound(vec.begin(), vec.end(), 4); std::cout 第一个4的元素位置 it_high - vec.begin() std::endl; // 输出6 // 4. 统计等于4的元素个数 int cnt it_high - it_low; std::cout 4的个数 cnt std::endl; // 输出3 return 0; }11. 交换算法核心特性交换两个元素或两个区间的元素是 STL 中最基础的算法之一被其他算法广泛调用常用函数函数功能swap(a, b)交换两个对象a和b的值iter_swap(it1, it2)交换两个迭代器it1和it2指向的元素swap_ranges(first1, last1, first2)交换两个区间的元素用法示例#include iostream #include vector #include algorithm int main() { // 1. 交换两个变量 int a 10, b 20; std::swap(a, b); std::cout a a , b b std::endl; // 输出a20, b10 // 2. 交换两个迭代器指向的元素 std::vectorint vec {1, 2, 3, 4}; std::iter_swap(vec.begin(), vec.end() - 1); // vec{4, 2, 3, 1} // 3. 交换两个区间的元素 std::vectorint vec1 {1, 2, 3}; std::vectorint vec2 {4, 5, 6}; std::swap_ranges(vec1.begin(), vec1.end(), vec2.begin()); // vec1{4, 5, 6}, vec2{1, 2, 3} return 0; }