跳到主要内容

算法

在STL中，除了用容器类模板自身提供的成员函数来操作容器元素外，还提供了一系列通用的对容器中元素进行操作的函数模板，称为算法。 STL 提供了大约 100 个实现算法的模版函数，基本都包含在 <algorithm> 之中，还有一部分包含在 <numeric> 和 <functional>。完备的函数列表请 参见参考手册，排序相关的可以参考 排序内容的对应页面。 STL算法实现了对序列元素的一些常规操作，用函数模板实现的，主要包括：

  • 调序算法
  • 编辑算法
  • 查找算法
  • 算术算法
  • 集合算法
  • 堆算法
  • 元素遍历算法

除了算术算法在头文件numeric中定义外，其它算法都在头文件algorithm中定义。

大部分STL算法都是遍历指定容器中某范围内的元素，对满足条件的元素执行某项操作。

算法的内部实现往往隐含着循环操作，但这对使用者是隐藏的。

  1. 使用者只需要提供：容器（迭代器）、操作条件以及可能的自定义操作。
  2. 算法的控制逻辑则由算法内部实现，这体现了一种抽象的编程模式。

算法和容器的关系​

在STL中，不是把容器传给算法，而是把容器的某些迭代器传给它们，在算法中通过迭代器来访问和遍历相应容器中的元素。

这样做的好处是：使得算法不依赖于具体的容器，提高了算法的通用性。

虽然容器各不相同，但它们的迭代器往往具有相容关系，一个算法往往可以接受相容的多种迭代器。

算法接受的迭代器类型​

一个算法能接收的迭代器的类型是通过算法模板参数的名字来体现的。例如：

template <class InIt, class OutIt>
OutIt copy(InIt src_first, InIt src_last, OutIt dst_first) {...}
  1. src_first和src_last是输入迭代器，算法中只能读取它们指向的元素。
  2. dst_first是输出迭代器，算法中可以修改它指向的元素。
  3. 以上参数可以接受其它相容的迭代器。

算法的操作范围​

用算法对容器中的元素进行操作时，大都需要用两个迭代器来指出要操作的元素的范围。

例如：

void sort(RanIt first, RanIt last);

first是第一个元素的位置. last是最后一个元素的下一个位置.

有些算法可以有多个操作范围，这时，除第一个范围外，其它范围可以不指定最后一个元素位置，它由第一个范围中元素的个数决定。例如：

OutIt copy(InIt src_first, InIt src_last, OutIt dst_first);

一个操作范围的两个迭代器必须属于同一个容器，而不同操作范围的迭代器可以属于不同的容器。

算法的自定义操作条件​

有些算法可以让使用者提供一个函数或函数对象来作为自定义操作条件（或称为谓词），其参数类型为相应容器的元素类型，返回值类型为bool。

自定义操作条件可分为：

  1. Pred：一元“谓词”，需要一个元素作为参数
  2. BinPred：二元“谓词”，需要两个元素作为参数
// 简单查找算法，要求输入迭代器（input iterator）
find(beg, end, val); // 返回一个迭代器，指向输入序列中第一个等于 val 的元素，未找到返回 end
find_if(beg, end, unaryPred); // 返回一个迭代器，指向第一个满足 unaryPred 的元素，未找到返回 end
find_if_not(beg, end, unaryPred); // 返回一个迭代器，指向第一个令 unaryPred 为 false 的元素，未找到返回 end
count(beg, end, val); // 返回一个计数器，指出 val 出现了多少次
count_if(beg, end, unaryPred); // 统计有多少个元素满足 unaryPred
all_of(beg, end, unaryPred); // 返回一个 bool 值，判断是否所有元素都满足 unaryPred
any_of(beg, end, unaryPred); // 返回一个 bool 值，判断是否任意（存在）一个元素满足 unaryPred
none_of(beg, end, unaryPred); // 返回一个 bool 值，判断是否所有元素都不满足 unaryPred

// 查找重复值的算法，传入向前迭代器（forward iterator）
adjacent_find(beg, end); // 返回指向第一对相邻重复元素的迭代器，无相邻元素则返回 end
adjacent_find(beg, end, binaryPred); // 返回指向第一对相邻重复元素的迭代器，无相邻元素则返回 end
search_n(beg, end, count, val); // 返回一个迭代器，从此位置开始有 count 个相等元素，不存在则返回 end
search_n(beg, end, count, val, binaryPred); // 返回一个迭代器，从此位置开始有 count 个相等元素，不存在则返回 end

// 查找子序列算法，除 find_first_of（前两个输入迭代器，后两个前向迭代器） 外，都要求两个前向迭代器
search(beg1, end1, beg2, end2); // 返回第二个输入范围（子序列）在爹一个输入范围中第一次出现的位置，未找到则返回 end1
search(beg1, end1, beg2, end2, binaryPred); // 返回第二个输入范围（子序列）在爹一个输入范围中第一次出现的位置，未找到则返回 end1
find_first_of(beg1, end1, beg2, end2); // 返回一个迭代器，指向第二个输入范围中任意元素在第一个范围中首次出现的位置，未找到则返回end1
find_first_of(beg1, end1, beg2, end2, binaryPred); // 返回一个迭代器，指向第二个输入范围中任意元素在第一个范围中首次出现的位置，未找到则返回end1
find_end(beg1, end1, beg2, end2); // 类似 search，但返回的最后一次出现的位置。如果第二个输入范围为空，或者在第一个输入范围为空，或者在第一个输入范围中未找到它，则返回 end1
find_end(beg1, end1, beg2, end2, binaryPred); // 类似 search，但返回的最后一次出现的位置。如果第二个输入范围为空，或者在第一个输入范围为空，或者在第一个输入范围中未找到它，则返回 end1

// 其他只读算法，传入输入迭代器
for_each(beg, end, unaryOp); // 对输入序列中的每个元素应用可调用对象 unaryOp，unaryOp 的返回值被忽略
mismatch(beg1, end1, beg2); // 比较两个序列中的元素。返回一个迭代器的 pair，表示两个序列中第一个不匹配的元素
mismatch(beg1, end1, beg2, binaryPred); // 比较两个序列中的元素。返回一个迭代器的 pair，表示两个序列中第一个不匹配的元素
equal(beg1, end1, beg2); // 比较每个元素，确定两个序列是否相等。
equal(beg1, end1, beg2, binaryPred); // 比较每个元素，确定两个序列是否相等。

// 二分搜索算法，传入前向迭代器或随机访问迭代器（random-access iterator），要求序列中的元素已经是有序的。通过小于运算符（<）或 comp 比较操作实现比较。
lower_bound(beg, end, val); // 返回一个非递减序列 [beg, end) 中的第一个大于等于值 val 的位置的迭代器，不存在则返回 end
lower_bound(beg, end, val, comp); // 返回一个非递减序列 [beg, end) 中的第一个大于等于值 val 的位置的迭代器，不存在则返回 end
upper_bound(beg, end, val); // 返回一个非递减序列 [beg, end) 中第一个大于 val 的位置的迭代器，不存在则返回 end
upper_bound(beg, end, val, comp); // 返回一个非递减序列 [beg, end) 中第一个大于 val 的位置的迭代器，不存在则返回 end
equal_range(beg, end, val); // 返回一个 pair，其 first 成员是 lower_bound 返回的迭代器，其 second 成员是 upper_bound 返回的迭代器
binary_search(beg, end, val); // 返回一个 bool 值，指出序列中是否包含等于 val 的元素。对于两个值 x 和 y，当 x 不小于 y 且 y 也不小于 x 时，认为它们相等。

// 只写不读算法，要求输出迭代器（output iterator）
fill(beg, end, val); // 将 val 赋予每个元素，返回 void
fill_n(beg, cnt, val); // 将 val 赋予 cnt 个元素，返回指向写入到输出序列最有一个元素之后位置的迭代器
genetate(beg, end, Gen); // 每次调用 Gen() 生成不同的值赋予每个序列，返回 void
genetate_n(beg, cnt, Gen); // 每次调用 Gen() 生成不同的值赋予 cnt 个序列，返回指向写入到输出序列最有一个元素之后位置的迭代器

// 使用输入迭代器的写算法，读取一个输入序列，将值写入到一个输出序列（dest）中
copy(beg, end, dest); // 从输入范围将元素拷贝所有元素到 dest 指定定的目的序列
copy_if(beg, end, dest, unaryPred); // 从输入范围将元素拷贝满足 unaryPred 的元素到 dest 指定定的目的序列
copy_n(beg, n, dest); // 从输入范围将元素拷贝前 n 个元素到 dest 指定定的目的序列
move(beg, end, dest); // 对输入序列中的每个元素调用 std::move，将其移动到迭代器 dest 开始始的序列中
transform(beg, end, dest, unaryOp); // 调用给定操作（一元操作），并将结果写到dest中
transform(beg, end, beg2, dest, binaryOp); // 调用给定操作（二元操作），并将结果写到dest中
replace_copy(beg, end, dest, old_val, new_val); // 将每个元素拷贝到 dest，将等于 old_val 的的元素替换为 new_val
replace_copy_if(beg, end, dest, unaryPred, new_val); // 将每个元素拷贝到 dest，将满足 unaryPred 的的元素替换为 new_val
merge(beg1, end1, beg2, end2, dest); // 两个输入序列必须都是有序的，用 < 运算符将合并后的序列写入到 dest 中
merge(beg1, end1, beg2, end2, dest, comp); // 两个输入序列必须都是有序的，使用给定的比较操作（comp）将合并后的序列写入到 dest 中

// 使用前向迭代器的写算法，要求前向迭代器
iter_swap(iter1, iter2); // 交换 iter1 和 iter2 所表示的元素，返回 void
swap_ranges(beg1, end1, beg2); // 将输入范围中所有元素与 beg2 开始的第二个序列中所有元素进行交换。返回递增后的的 beg2，指向最后一个交换元素之后的位置。
replace(beg, end, old_val, new_val); // 用 new_val 替换等于 old_val 的每个匹配元素
replace_if(beg, end, unaryPred, new_val); // 用 new_val 替换满足 unaryPred 的每个匹配元素

// 使用双向迭代器的写算法，要求双向选代器（bidirectional iterator）
copy_backward(beg, end, dest); // 从输入范围中拷贝元素到指定目的位置。如果范围为空,则返回值为 dest；否则，返回值表示从 *beg 中拷贝或移动的元素。
move_backward(beg, end, dest);  // 从输入范围中移动元素到指定目的位置。如果范围为空,则返回值为 dest；否则,返回值表示从 *beg 中拷贝或移动的元素。
inplace_merge(beg, mid, end); // 将同一个序列中的两个有序子序列合并为单一的有序序列。beg 到 mid 间的子序列和 mid 到 end 间的子序列被合并，并被写入到原序列中。使用 < 比较元素。
inplace_merge(beg, mid, end, comp); // 将同一个序列中的两个有序子序列合并为单一的有序序列。beg 到 mid 间的子序列和 mid 到 end 间的子序列被合并，并被写入到原序列中。使用给定的 comp 操作。

// 划分算法，要求双向选代器（bidirectional iterator）
is_partitioned(beg, end, unaryPred); // 如果所有满足谓词 unaryPred 的元素都在不满足 unarypred 的元素之前，则返回 true。若序列为空，也返回 true
partition_copy(beg, end, dest1, dest2, unaryPred); // 将满足 unaryPred 的元素拷贝到到 dest1，并将不满足 unaryPred 的元素拷贝到到 dest2。返回一个迭代器 pair，其 first 成员表示拷贝到 dest1 的的元素的末尾，second 表示拷贝到 dest2 的元素的末尾。
partitioned_point(beg, end, unaryPred); // 输入序列必须是已经用 unaryPred 划分过的。返回满足  unaryPred 的范围的尾后迭代器。如果返回的迭代器不是 end，则它指向的元素及其后的元素必须都不满足 unaryPred
stable_partition(beg, end, unaryPred); // 使用 unaryPred 划分输入序列。满足 unaryPred 的元素放置在序列开始，不满足的元素放在序列尾部。返回一个迭代器，指向最后一个满足 unaryPred 的元素之后的位置如果所有元素都不满足 unaryPred，则返回 beg
partition(beg, end, unaryPred); // 使用 unaryPred 划分输入序列。满足 unaryPred 的元素放置在序列开始，不满足的元素放在序列尾部。返回一个迭代器，指向最后一个满足 unaryPred 的元素之后的位置如果所有元素都不满足 unaryPred，则返回 beg

// 排序算法，要求随机访问迭代器（random-access iterator）
sort(beg, end); // 排序整个范围
stable_sort(beg, end); // 排序整个范围（稳定排序）
sort(beg, end, comp); // 排序整个范围
stable_sort(beg, end, comp); // 排序整个范围（稳定排序）
is_sorted(beg, end); // 返回一个 bool 值，指出整个输入序列是否有序
is_sorted(beg, end, comp); // 返回一个 bool 值，指出整个输入序列是否有序
is_sorted_until(beg, end); // 在输入序列中査找最长初始有序子序列，并返回子序列的尾后迭代器
is_sorted_until(beg, end, comp); // 在输入序列中査找最长初始有序子序列，并返回子序列的尾后迭代器
partial_sort(beg, mid, end); // 排序 mid-beg 个元素。即，如果 mid-beg 等于 42，则此函数将值最小的 42 个元素有序放在序列前 42 个位置
partial_sort(beg, mid, end, comp); // 排序 mid-beg 个元素。即，如果 mid-beg 等于 42，则此函数将值最小的 42 个元素有序放在序列前 42 个位置
partial_sort_copy(beg, end, destBeg, destEnd); // 排序输入范围中的元素，并将足够多的已排序元素放到 destBeg 和 destEnd 所指示的序列中
partial_sort_copy(beg, end, destBeg, destEnd, comp); // 排序输入范围中的元素，并将足够多的已排序元素放到 destBeg 和 destEnd 所指示的序列中
nth_element(beg, nth, end); // nth 是一个迭代器，指向输入序列中第 n 大的元素。nth 之前的元素都小于等于它，而之后的元素都大于等于它
nth_element(beg, nth, end, comp); // nth 是一个迭代器，指向输入序列中第 n 大的元素。nth 之前的元素都小于等于它，而之后的元素都大于等于它

// 使用前向迭代器的重排算法。普通版本在输入序列自身内部重拍元素，_copy 版本完成重拍后写入到指定目的序列中，而不改变输入序列
remove(beg, end, val); // 通过用保留的元素覆盖要删除的元素实现删除 ==val 的元素，返回一个指向最后一个删除元素的尾后位置的迭代器
remove_if(beg, end, unaryPred); // 通过用保留的元素覆盖要删除的元素实现删除满足 unaryPred 的元素，返回一个指向最后一个删除元素的尾后位置的迭代器
remove_copy(beg, end, dest, val); // 通过用保留的元素覆盖要删除的元素实现删除 ==val 的元素，返回一个指向最后一个删除元素的尾后位置的迭代器
remove_copy_if(beg, end, dest, unaryPred); // 通过用保留的元素覆盖要删除的元素实现删除满足 unaryPred 的元素，返回一个指向最后一个删除元素的尾后位置的迭代器
unique(beg, end); // 通过对覆盖相邻的重复元素（用 == 确定是否相同）实现重排序列。返回一个迭代器，指向不重复元素的尾后位置
unique (beg, end, binaryPred); // 通过对覆盖相邻的重复元素（用 binaryPred 确定是否相同）实现重排序列。返回一个迭代器，指向不重复元素的尾后位置
unique_copy(beg, end, dest); // 通过对覆盖相邻的重复元素（用 == 确定是否相同）实现重排序列。返回一个迭代器，指向不重复元素的尾后位置
unique_copy_if(beg, end, dest, binaryPred); // 通过对覆盖相邻的重复元素（用 binaryPred 确定是否相同）实现重排序列。返回一个迭代器，指向不重复元素的尾后位置
rotate(beg, mid, end); // 围绕 mid 指向的元素进行元素转动。元素 mid 成为为首元素，随后是 mid+1 到到 end 之前的元素，再接着是 beg 到 mid 之前的元素。返回一个迭代器，指向原来在 beg 位置的元素
rotate_copy(beg, mid, end, dest); // 围绕 mid 指向的元素进行元素转动。元素 mid 成为为首元素，随后是 mid+1 到到 end 之前的元素，再接着是 beg 到 mid 之前的元素。返回一个迭代器，指向原来在 beg 位置的元素

// 使用双向迭代器的重排算法
reverse(beg, end); // 翻转序列中的元素，返回 void
reverse_copy(beg, end, dest);; // 翻转序列中的元素，返回一个迭代器，指向拷贝到目的序列的元素的尾后位置

// 使用随机访问迭代器的重排算法
random_shuffle(beg, end); // 混洗输入序列中的元素，返回 void
random_shuffle(beg, end, rand); // 混洗输入序列中的元素，rand 接受一个正整数的随机对象，返回 void
shuffle(beg, end, Uniform_rand); // 混洗输入序列中的元素，Uniform_rand 必须满足均匀分布随机数生成器的要求，返回 void

// 最小值和最大值，使用 < 运算符或给定的比较操作 comp 进行比较
min(val1, va12); // 返回 val1 和 val2 中的最小值，两个实参的类型必须完全一致。参数和返回类型都是 const的引引用，意味着对象不会被拷贝。下略
min(val1, val2, comp);
min(init_list);
min(init_list, comp);
max(val1, val2);
max(val1, val2, comp);
max(init_list);
max(init_list, comp);
minmax(val1, val2); // 返回一个 pair，其 first 成员为提供的值中的较小者，second 成员为较大者。下略
minmax(vall, val2, comp);
minmax(init_list);
minmax(init_list, comp);
min_element(beg, end); // 返回指向输入序列中最小元素的迭代器
min_element(beg, end, comp); // 返回指向输入序列中最小元素的迭代器
max_element(beg, end); // 返回指向输入序列中最大元素的迭代器
max_element(beg, end, comp); // 返回指向输入序列中最大元素的迭代器
minmax_element(beg, end); // 返回一个 pair，其中 first 成员为最小元素，second 成员为最大元素
minmax_element(beg, end, comp); // 返回一个 pair，其中 first 成员为最小元素，second 成员为最大元素

// 字典序比较，根据第一对不相等的元素的相对大小来返回结果。如果第一个序列在字典序中小于第二个序列，则返回 true。否则，返回 fa1se。如果个序列比另一个短，且所有元素都与较长序列的对应元素相等，则较短序列在字典序中更小。如果序列长度相等，且对应元素都相等，则在字典序中任何一个都不大于另外一个。
lexicographical_compare(beg1, end1, beg2, end2);
lexicographical_compare(beg1, end1, beg2, end2, comp);

Pred​

一种'统计'算法的使用
size_t count_if(InIt first, InIt last, Pred cond);

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

bool f(int x) { return x > 0; }

int main() 
{
    vector<int> v;
    ...... // 往容器中放了元素
    cout << count_if(v.begin(), v.end(), f); // 统计v中正数的个数
    return 0;
}

BinPred​

void sort(RanIt first, RanIt last); // 按“<”排序
void sort(RanIt first, RanIt last, BinPred comp); // 按comp返回true规定的次序

#include <vector>
#include <algorithm>
using namespace std;

bool greater2(int x1, int x2) { return x1 > x2; }

int main()
{
    vector<int> v;
    ...... // 往容器中放了元素
    sort(v.begin(), v.end()); // 从小到大排序
    sort(v.begin(), v.end(), greater2); // 从大到小排序
    return 0;
}

算法的自定义操作​

有些算法可以让使用者提供一个函数或函数对象作为自定义操作，其参数和返回值类型由相应的算法决定。

自定义操作可分为：

  1. Op或Fun：一元操作，需要一个参数
  2. BinOp或BinFun：二元操作，需要两个参数
元素遍历的Op算法
Fun for_each(InIt first, InIt last, Fun f);

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void f(int x) { cout << ' ' << x; }

int main()
{
     vector<int> v;
     ...... // 往容器中放了元素
     for_each(v.begin(), v.end(), f); // 对v中的每个元素去调用函数f进行操作
     return 0;
}
二元操作
T accumulate(InIt first, InIt last, T val); // 按“+”操作
T accumulate(InIt first, InIt last, T val, BinOp op); // 由op决定累积的含义

#include <vector>
#include <numeric>
using namespace std;

int f1(int partial, int x) { return partial 
* x; }
int f2(int partial, int x) { return partial + x 
* x; }
double f3(double partial, int x) { return partial + 1.0 / x; }

int main
{
    vector<int> v;
    ...... // 往容器中放了元素
    
    int sum = accumulate(v.begin(), v.end(), 0); // 所有元素和
    int product = accumulate(v.begin(), v.end(), 1, f1); // 所有元素的乘积
    int sq_sum = accumulate(v.begin(), v.end(), 0, f2); // 所有元素平方和
    int rec_sum = accumulate(v.begin(), v.end(), 0.0, f3); // 元素倒数和
    
    return 0;
}

swap()​

很多算法使用swap()函数交换两个对象的值, 特别是sort(); 这类算法通常假定swap()非常快且不会抛出异常. 标准库提供了一个std::swap(a,b)来实现. 他进行了3步操作:temp = a; a = b; b = temp. 如果你设计一个类的拷贝代价很高而且有可能被交换, 则应为其提供移动操作和swap().

标准库容器和string都具有快速移动操作.

hash<>​

标准库unordered_map<K,V>是一种哈希表,K是关键字类型,V是值类型. 将类型X用作关键字, 我们必须定义hash<X>

算法​

算法主要由头文件<algorithm><functional><numeric>组成

  • <algorithm> 是所有 STL 头文件中最大的一个，其中常用的功能涉及到比较、交换、查找、遍历、复制、修改、反转、排序、合并等

  • <numeric> 体积很小，只包括在几个序列容器上进行简单运算的模版函数

  • <functional> 定义了一些模版类，用以声明函数对象

自定义的类如果想要直接使用算法库，则需补全默认构造函数、拷贝构造函数、析构函数、赋值操作符、小于操作符、等于操作符。

常用遍历算法​

for_each​

/**  
* 遍历算法 遍历容器元素 
* @param beg 开始迭代器 
* @param end 结束迭代器 
* @param _callback 函数回调或者函数对象 
* @return 函数对象
*/ 

for_each(iterator beg, iterator end, _callback);

transform​

/**  
* transform算法 将指定容器内的元素搬运到另一个容器中 
* 注意：transform不会给目标容器分配内存，所以需要我们提前分配好内存 
* @param beg1 源容器开始迭代器 
* @param end1 源容器结束迭代器 
* @param beg2 目标容器开始迭代器 
* @param _callback 回调函数或者函数对象 
* @return 返回目标容器迭代器 
*/ 
iterator  transform(iterator beg1,  iterator end1,  iterator beg2,  _callback);

注意：目标容器一定要提前分配好内存。

常用查找算法​

find​

/**  
* find 算法 查找元素 
* @param beg 容器开始迭代器 
* @param end 容器结束迭代器 
* @param value 查找的元素 
* @return 返回查找元素的位置 
*/ 
iterator  find(iterator beg,  iterator end,  value);

find_if​

/**  
* find_if 算法 条件查找 
* @param beg 容器开始迭代器 
* @param end 容器结束迭代器 
* @param _callback 回调函数或者谓词(返回 bool 类型的函数对象) 
* @return 返回查找元素的位置 
*/ 
iterator  find_if(iterator beg,  iterator end,  _callback);

利用 find_if 实现自定义类的 find 操作的时候，之前的函数适配器可能会派上用场。

adjacent_find​

/**  
* adjacent_find 算法 查找相邻重复元素 
* @param beg 容器开始迭代器 
* @param end 容器结束迭代器 
* @param _callback 回调函数或者谓词(返回 bool 类型的函数对象) 
* @return 返回相邻元素的第一个位置的迭代器 
*/ 
iterator  adjacent_find(iterator beg,  iterator end,  _callback);
/**  
* binary_search 算法 二分法查找 
* 注意：在无序序列中不可用 
* @param beg 容器开始迭代器 
* @param end 容器结束迭代器 
* @param value 查找的元素 
* @return bool 查找返回true，否则false 
*/ 
bool  binary_search(iterator beg,  iterator end,  value);

count​

/**  
* count 算法 统计元素出现次数 
* @param beg 容器开始迭代器 
* @param end 容器结束迭代器 
* @param value 待计数的元素 
* @return int 返回元素个数 
*/ 
int  count(iterator beg,  iterator end,  value);

count_if​

/**  
* count_if 算法 统计元素出现次数 
* @param beg 容器开始迭代器 
* @param end 容器结束迭代器 
* @param _callback 回调函数或者谓词 
* @return int 返回元素个数 
*/ 
int  count_if(iterator beg,  iterator end,  _callback);

常用排序算法​

merge​

/**  
* merge 算法 容器元素合并，并储存到另一个容器中 
* 注意：两个容器必须是有序的 
* @param beg1 容器1开始迭代器 
* @param end1 容器1结束迭代器 
* @param beg2 容器2开始迭代器 
* @param end2 容器2结束迭代器 
* @param dest 目标容器开始迭代器 
*/ 
merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);

sort​

/**  
* sort 算法 容器元素排序 
* @param beg 容器开始迭代器 
* @param end 容器结束迭代器 
* @param _callback 回调函数或者谓词 
*/ 
sort(iterator beg, iterator end, _callback);

random_shuffle​

/**  
* random_shuffle 算法 对指定范围内的元素随机调整次序 
* @param beg 容器开始迭代器 
* @param end 容器结束迭代器 
*/ 
random_shuffle(iterator beg, iterator end);

如果想要每次打乱不同，需要自己设置随机数种子：

#include  <ctime> 
using  namespace std;   
int  main() {  
    srand((unsigned  int)time(NULL)); ......//random_shuffle 
}

reverse​

/**  
* reverse 算法 反转指定范围的元素 
* @param beg 容器开始迭代器 
* @param end 容器结束迭代器 
*/ 
reverse(iterator beg, iterator end);

常用拷贝和替换算法​

copy​

/**  
* copy算法 将容器内指定范围的元素拷贝到另一容器当中 
* @param beg 容器开始迭代器 
* @param end 容器结束迭代器 
* @param dest 目标容器开始迭代器 
*/ 
copy(iterator beg, iterator end, iterator dest);

使用 copy 算法快速打印容器：

vector<int> v = {1,  2,  3,  4,  5}; 
for_each(v.begin(),  v.end(), [](int val){cout << val <<  " ";}); // 等价于 
//copy(v.begin(),  v.end(),  ostream_iterator<int>(cout,  " ")); // 需要#include <iterator>

其实第一种方法已经够用了，不过为了提升一下逼格，不妨也了解一下第二种。

replace​

/**  
* replace算法 将容器内指定范围的旧元素修改为新元素 
* @param beg 容器开始迭代器 
* @param end 容器结束迭代器 
* @param oldvalue 旧元素 
* @param newvalue 新元素 
*/ 
replace(inerator beg, iterator end, oldvalue, newvalue);

replace_if​

/**  
* replace_if 算法 将容器内指定范围满足条件的元素替换为新元素 
* @param beg 容器开始迭代器 
* @param end 容器结束迭代器 
* @param _callback 回调函数或者谓词（返回bool类型的函数对象） 
* @param newvalue 新元素 
*/ 
replace_if(inerator beg, inerator end, _callback, newvalue);

swap​

/**  
* swap 算法 互换两个容器元素 
* @param c1 容器1 
* @param c2 容器2 
*/ 
swap(container c1, container c2);

常用算数生成算法​

accumulate​

#include  <numeric>  // 注意头文件不是algorithm了 
/**  
* accumulate 算法 计算容器元素累计总和 
* @param beg 容器开始迭代器 
* @param end 容器结束迭代器 
* @param value 起始累加值 
*/ 
accumulate(iterator beg, iterator end, value);

fill​

/**  
* fill 算法 
* @param beg 容器开始迭代器 
* @param end 容器结束迭代器 
* @param value 填充元素 
*/ 
fill(iterator beg, iterator end, value);

常用集合算法​

set_intersection​

/**  
* set_intersection 算法 求两个set集合的交集 
* 注意：两个集合必须是有序序列 
* @param beg1 容器1开始迭代器 
* @param end1 容器1结束迭代器 
* @param beg2 容器2开始迭代器 
* @param end2 容器2结束迭代器 
* @param dest 目标容器开始迭代器 
* @return 目标容器最后一个元素的迭代器地址 
*/ 
set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);

set_union​

/**  
* set_union 算法 求两个set集合的并集 
* 注意：两个集合必须是有序序列 
* @param beg1 容器1开始迭代器 
* @param end1 容器1结束迭代器 
* @param beg2 容器2开始迭代器 
* @param end2 容器2结束迭代器 
* @param dest 目标容器开始迭代器 
* @return 目标容器最后一个元素的迭代器地址 
*/ 
set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);

set_difference​

/**  
* set_difference 算法 求两个set集合的差集 
* 注意：两个集合必须是有序序列 
* @param beg1 容器1开始迭代器 
* @param end1 容器1结束迭代器 
* @param beg2 容器2开始迭代器 
* @param end2 容器2结束迭代器 
* @param dest 目标容器开始迭代器 
* @return 目标容器最后一个元素的迭代器地址 
*/ 
set_difference(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);

find：顺序查找。find(v.begin(), v.end(), value)，其中 value 为需要查找的值。

reverse：翻转数组、字符串。reverse(v.begin(), v.end()) 或 reverse(a + begin, a + end)。

unique：去除容器中相邻的重复元素。unique(ForwardIterator first, ForwardIterator last)，返回值为指向 去重后 容器结尾的迭代器，原容器大小不变。与 sort 结合使用可以实现完整容器去重。

shuffle

random_shuffle 自 C++14 起被弃用，C++17 起被移除。

在 C++11 以及更新的标准中，您可以使用 shuffle 函数代替原来的 random_shuffle。使用方法为 shuffle(v.begin(), v.end(), rng)（最后一个参数传入的是使用的随机数生成器，一般情况使用以真随机数生成器 random_device 播种的梅森旋转伪随机数生成器 mt19937）。

#include <random>
std::mt19937 rng(std::random_device{}());
std::shuffle(v.begin(), v.end(), rng);

sort：排序。sort(v.begin(), v.end(), cmp) 或 sort(a + begin, a + end, cmp)，其中 end 是排序的数组最后一个元素的后一位，cmp 为自定义的比较函数。

stable_sort：稳定排序，用法同 sort()。

nth_element：按指定范围进行分类，即找出序列中第 n 大的元素，使其左边均为小于它的数，右边均为大于它的数。nth_element(v.begin(), v.begin() + mid, v.end(), cmp) 或 nth_element(a + begin, a + begin + mid, a + end, cmp)。

binary_search：二分查找。binary_search(v.begin(), v.end(), value)，其中 value 为需要查找的值。

merge：将两个（已排序的）序列 有序合并 到第三个序列的 插入迭代器 上。merge(v1.begin(), v1.end(), v2.begin(), v2.end() ,back_inserter(v3))。

inplace_merge：将两个（已按小于运算符排序的）：[first,middle), [middle,last) 范围 原地合并为一个有序序列。inplace_merge(v.begin(), v.begin() + middle, v.end())。

lower_bound：在一个有序序列中进行二分查找，返回指向第一个 大于等于 x 的元素的位置的迭代器。如果不存在这样的元素，则返回尾迭代器。lower_bound(v.begin(),v.end(),x)。

upper_bound：在一个有序序列中进行二分查找，返回指向第一个 大于 x 的元素的位置的迭代器。如果不存在这样的元素，则返回尾迭代器。upper_bound(v.begin(),v.end(),x)。

next_permutation：将当前排列更改为 全排列中的下一个排列。如果当前排列已经是 全排列中的最后一个排列（元素完全从大到小排列），函数返回 false 并将排列更改为 全排列中的第一个排列（元素完全从小到大排列）；否则，函数返回 true。next_permutation(v.begin(), v.end()) 或 next_permutation(v + begin, v + end)。

prev_permutation：将当前排列更改为 全排列中的上一个排列。用法同 next_permutation。

partial_sum：求前缀和。设源容器为 x，目标容器为 y，则令 y[i]=x[0]+x[1]+\dots+x[i]。partial_sum(src.begin(), src.end(), back_inserter(dst))。

Loading Comments...