头文件：algorithm

algorithm意为”算法”,是C++的标准模版库（STL）中最重要的头文件之一，提供了大量基于迭代器的非成员模版函数。

相关概念说明

  1. 容器 容器是用来存放各种数据的一个东西，<algorithm>中的算法是针对容器设计的。因此，不论数据是一些int，char还是自定义的class，<algorithm>中的函数都可以正确应对。vector是最常用的容器。
  2. 迭代器 迭代器是与容器进行配套使用的。它的作用是对容器中的元素进行遍历，比如数组的指针就可以看作一种迭代器。迭代器一般支持解引用（operator*()）、自加（operator++()）、相等（operator==()）等操作。
  3. 谓词 谓词是用来对<algorithm>中的函数进行定制操作的。谓词可以是lambda表达式或是函数/函数指针，并且<algorithm>中只有一元谓词和二元谓词，即函数只能接收一个或两个参数。对于需要额外参数的谓词可以使用lambda表达式的捕获功能。
  4. pair 部分算法会有两个返回值，pair有两个成员first和second，用来将两个值进行打包返回。

用到的主要参数说明

  • beg和end是表示元素范围的迭代器。
  • beg2是第二个输入序列开始位置的迭代器，end2表示第二个序列末尾位置（如果有的话）。如果没有end2，则假定beg2表示的序列与beg和end表示的序列一样大。beg和beg2不必是相同的类型，但两个序列中的元素都要能调用给定的可调用对像。比如beg是一个std::vector<int>::iterator，而beg2可以是一个std::deque<int>::iterator。
  • dest是表示目的序列的迭代器，目的序列必须保证能够存储算法生成的所有元素。若无法确定大小，可以调用std::back_inserter()函数获取目的序列的插入迭代器。
  • unaryPred和binayPred是一元和二元谓词，其实参都是序列中的元素。
  • comp是一个二元谓词，用于比较两个元素。
  • unaryOp和binaryOp是可调用对象。

此外，部分算法要求序列是有序的，默认是使用小于运算符（<）定义的升序。若使用谓词版本，则有序是按comp升序。

常用函数及用法

非修改性序列操作（12个）

循环

  • 对序列中的每个元素执行某操作 for_each()

查找

  • 在序列中找出某个值的第一次出现的位置 find() 利用底层元素的等于操作符，对范围内的元素与输入的值进行比较。当匹配时，结束搜索，返回该元素的一个 InputIterator 。
  • 在序列中找出符合某谓词的第一个元素 find_if()
  • 在序列中找出一子序列的最后一次出现的位置 find_end()
  • 在序列中找出第一次出现指定值集中之值的位置 find_first_of()
  • 在序列中找出相邻的一对值 adjacent_find()

计数

  • 在序列中统计某个值出现的次数 count()
  • 在序列中统计与某谓词匹配的次数 count_if()

比较

  • 找出两个序列相异的第一个元素 mismatch()
  • 两个序列中的对应元素都相同时为真 equal()

搜索

  • 在序列中找出一子序列的第一次出现的位置 search()
  • 在序列中找出一值的连续n次出现的位置 search_n()

修改性序列操作（27个）

复制

  • 从序列的第一个元素起进行复制 copy()
  • 从序列的最后一个元素起进行复制 copy_backward()

交换

  • 交换两个元素 swap()
  • 交换指定范围的元素 swap_ranges()
  • 交换由迭代器所指的两个元素 iter_swap()

变换

  • 将某操作应用于指定范围的每个元素 transform()

替换

  • 用一个给定值替换一些值 replace()
  • 替换满足谓词的一些元素 replace_if()
  • 复制序列时用一给定值替换元素 replace_copy()
  • 复制序列时替换满足谓词的元素 replace_copy_if()

填充

  • 用一给定值取代所有元素 fill()
  • 用一给定值取代前n个元素 fill_n()

生成

  • 用一操作的结果取代所有元素 generate()
  • 用一操作的结果取代前n个元素 generate_n()

删除

  • 删除具有给定值的元素 remove()
  • 删除满足谓词的元素 remove_if()
  • 复制序列时删除具有给定值的元素 remove_copy()
  • 复制序列时删除满足谓词的元素 remove_copy_if()

唯一

  • 删除相邻的重复元素 unique()
  • 复制序列时删除相邻的重复元素 unique_copy()

反转

  • 反转元素的次序 reverse()
  • 复制序列时反转元素的次序 reverse_copy()

环移

  • 循环移动元素 rotate()
  • 复制序列时循环移动元素 rotate_copy()

随机

  • 采用均匀分布来随机移动元素 random_shuffle()

划分

  • 将满足某谓词的元素都放到前面 partition()
  • 将满足某谓词的元素都放到前面并维持原顺序 stable_partition()

序列排序及相关操作（27个）

排序

  • 以很好的平均效率排序 sort()
  • 并维持相同元素的原有顺序 stable_sort()
  • 将序列的前一部分排好序 partial_sort()
  • 复制的同时将序列的前一部分排好序 partial_sort_copy()
  • 将第n各元素放到它的正确位置 nth_element()

二分检索

  • 找到大于等于某值的第一次出现 lower_bound()
  • 找到大于某值的第一次出现 upper_bound()
  • 找到（在不破坏顺序的前提下）可插入给定值的最大范围 equal_range()
  • 在有序序列中确定给定元素是否存在 binary_search()

归并

  • 归并两个有序序列 merge()
  • 归并两个接续的有序序列 inplace_merge()

有序结构上的集合操作

  • 一序列为另一序列的子序列时为真 includes()
  • 构造两个集合的有序并集 set_union()
  • 构造两个集合的有序交集 set_intersection()
  • 构造两个集合的有序差集 set_difference()
  • 构造两个集合的有序对称差集（并-交） set_symmetric_difference()

堆操作

  • 向堆中加入元素 push_heap()
  • 从堆中弹出元素 pop_heap()
  • 从序列构造堆 make_heap()
  • 给堆排序 sort_heap()

最大和最小

  • 两个值中较小的 min()
  • 两个值中较大的 max()
  • 序列中的最小元素 min_element()
  • 序列中的最大元素 max_element()

词典比较

  • 两个序列按字典序的第一个在前 lexicographical_compare()

排列生成器

  • 按字典序的下一个排列 next_permutation()
  • 按字典序的前一个排列 prev_permutation()

其他详细内容：https://www.lagou.com/lgeduarticle/9665.html