STL算法库

std::算法库

按照功能划分的STL算法库。

内容详细来源：算法库 - cppreference.com

图解：C++ Standard Library Algorithms Visual Overview | hacking C++ (hackingcpp.com)

注意：如果算法仅仅是替代了for循环，那么std算法适用于序列化容器。容器自己有相应方法时不要使用std算法。例如remove和成员方法erease。

检查元素

• all_of;any_of;none_of 检查元素是否符合谓词

查找元素

• find;find_if 找到首个满足条件的元素
• find_end
• find_first_of 查找目标序列中是否有与给定集合中任意一个元素匹配的元素
• search 搜索一个范围，例如子串查找
• search_n 搜索连续元素范围
• adjacent_find 搜索首对相邻元素
• mis_match 两个范围内首个不同
• 二分查找
  • lower_bound;upper_bound 找到不小于或大于的迭代器
  • binary_search 确定元素是否在范围中，返回bool
  • equal_range 查找某个值的连续序列

计数

• count;count_if

复制与移动

• copy;copy_if;copy_n;copy_backward 调用拷贝赋值函数*d_first++ = *first++;

• move;move_backward

• uninitialized_copy;uninitialized_copy_n 将范围内的对象复制到未初始化的内存区域

• uninitialized_move;uninitialized_move_n

uninitialized系列会调用拷贝构造函数::new (static_cast<void*>(std::addressof(*current))) T(*first);，适用于需要额外分配内存的场景，例如对象内有一个char*，需要构造函数进行分配空间。

填充

• fill;fill_n 给范围内每个元素赋值const value
• generate;generate_n 给范围内每个元素赋值
• iota 用从起始值开始连续递增的值填充
• uninitialized_fill;uninitialized_fill_n

遍历处理

• transform 输出结果到新的
• for_each 原地处理

移除与替换

• remove;remove_if 移动不符合的元素到末尾

• remove_copy;remove_copy_if 复制不符合的元素到指定位置

• replace;replace_if

• replace_copy;replace_copy_if 替换并复制到指定位置

• unique;unique_copy 移除连续重复元素

  auto end = unique(v.begin(), v.end(), [](const pair<int, string> &a, const pair<int, string> &b) { return a.first == b.first; });
  // 返回无效的第一个，有效的最后一个的后一个
  

• destroy;destroy_n;destroy_at 调用范围内元素的析构函数/从指定位置开始的n个

交换与改变顺序

• swap;swap_ranges
• iter_swap 交换迭代器所指
• reverse;reverse_copy 后者会额外创建一个副本
• rotate;rotate_copy [first mid end]以mid为中心交换前后
• shuffle;random_shuffle 打乱序列，前者需要额外指定一个随机数生成器
• sample 随机选择n个元素

划分

• is_partitioned;partition_point 是否已经按照谓词划分，确定划分点
• partition;partition_copy 按照谓词划分
• stable_partition 保持相对顺序

排序

• is_sorted;is_sorted_until 是否已经升序
• sort 排序
• partial_sort;partial_sort_copy 部分排序
• stable_sort 稳定排序
• nth_element 找到一个序列中第 n 个元素，并将这个元素放在序列的第 n 个位置，类似快排的一次分区

集合（已排序范围上）

• merge;inplace_merge 前者会创建一个新序列
• includes 若一个范围是另一个范围的子数组返回true
• set_difference 获得差集
• set_intersection 获得交集
• set_symmetric_difference 获得对称差
• set_union 获得并集

最大堆

堆是一种满足特定规则的完全二叉树，其中每个节点的值都大于等于（或小于等于）它的子节点的值。堆通常使用数组来实现。最大堆是指大根堆，root是最大的

• is_heap 是否是最大堆
• is_heap_until 用于查找一个序列中前面一部分元素最后一个不满足堆的条件的位置的函数
• make_heap;push_heap;pop_heap
• sort_heap 将一个最大堆变成一个按升序排序的元素范围

最小最大值与比较

• max;max_element 后者应用于一个范围
• min;min_element
• minmax;minmax_element 返回两个元素/范围的较小和较大者
• clamp 输入元素，返回符合限制的元素
• equal 比较两个元素集合是否相同

排列

• is_permutation 判断一个序列是否为另一个序列的排列
• next_permutation 产生某个元素范围的按字典顺序的下一个较大的排列
• prev_permutation产生某个元素范围的按字典顺序的下一个较小的排列

数值运算

• accumulate 范围求和
• inner_product 内积。如果我们有两个n维向量x和y，它们的内积可以表示为： x·y = x1y1 + x2y2 + … + xnyn
• adjacent_difference 计算范围内相邻元素的差，写入到出口
• partial_sum 累加到某个元素然后写入。2, 2, 2, 2, 2, 2, 2, 2, 2, 2 -> 2 4 6 8 10 12 14 16 18 20
• reduce 将一组值简化为一个单一的值，广义accumulate

惯用法

移动和擦除 remove and erease

remove等会把元素移动到末尾并返回无效的第一个（有效的最后一个元素的后一个）的迭代器。

利用erease移除这个迭代器到最后一个无效的，即可达成真正的移除目的。

auto end = unique(v.begin(), v.end());
v.erase(end, v.end());