lower_bound 和 upper_bound 是内置的二分查找函数。
lower_bound - 一个函数，以对数时间在排序数组中找到大于或等于给定值 k 的最小元素。
它以数组的边界和 k 的值作为参数。
返回指向找到的元素的迭代器，如果不存在这样的元素，则返回指向数组末尾（不包括在内）的迭代器。
您可以在 文档中阅读更多内容。
upper_bound - 一个在对数时间内在排序数组中找到严格大于给定值 k 的最小元素的函数。
它以数组的边界和 k 的值作为参数。
返回指向找到的元素的迭代器，如果不存在这样的元素，则返回指向数组末尾（不包括在内）的迭代器。
您可以在 文档中阅读更多内容。
值得澄清的是，由于上述随机访问集合中缺少迭代器，因此在集合或多重集合上使用这些函数在对数时间内不起作用。
但是，这些集合都有对应的内置方法（也就是说，你需要“通过一个点”来使用它们）。
例子：
矢量 a = { 0, 1, 3, 5, 7 };
vector::iterator 它；
it = lower_bound(a.begin(), a.end(), 4);
// *它== 5
it = lower_bound(a.begin(), a.end(), 5);
// *它== 5
it = lower_bound(a.begin(), a.end(), 8);
// 它 == a.end()
it = upper_bound(a.begin(), a.end(), 4);
// *它== 5
it = upper_bound(a.begin(), a.end(), 5);
// *它== 7
it = upper_bound(a.begin(), a.end(), -1);
// *它== 0
// 通过减去迭代器，你可以得到找到的元素的索引
int ind = lower_bound(a.begin(), a.end(), 4) - a.begin();
// 工业 == 3
// 需要对集合和类似集合使用方法而不是函数
设置 s{ 1, 3, 5 };
设置::迭代器坐下；
坐 = s.lower_bound(3);
// *坐 == 3
坐 = s.upper_bound(3);
// *坐 == 5
|
unique - 一种在线性时间内将所有相同连续元素序列压缩为一个的函数。
作为参数，它传递数组的边界，在该边界内有必要应用压缩。
迭代器返回到数组的新末端（不包括）。您应该小心处理新结尾之后但旧结尾之前的元素，因为它们将具有未定义的值。
您可以在 文档中阅读更多内容。
如果您在矢量上使用此函数，则可以方便地使用返回的结果调整大小（更多内容见下文）。
例子：
矢量 a = { 3, 3, 3, 2, 3, 3, 1, 1, 4, 5, 5 };
独特的（a.begin（），a.end（））;
// a = [3, 2, 3, 1, 4, 5, ?, ?, ?, ?, ?]
// 使用 unique 函数做起来很方便
//坐标压缩辅助数组
a = { 235, 10, 41, 10, 41, 41, 235, 500, 500 };
排序（a.begin（），a.end（））;
// a = [10, 10, 41, 41, 41, 235, 235, 500, 500]
a.resize(unique(a.begin(), a.end()) - a.begin());
// a = [10, 41, 235, 500]
|
merge - 合并两个排序数组的函数，即在线性时间内它得到一个排序数组，它由第一个和第二个数组的元素组成。
它有 5 个参数：每个数组的两个边界和目标的左边界（将放置结果数组的元素的位置）。
可以在 文档中找到更多详细信息。
例子：
// 源数组必须排序
矢量 a = { 1, 3, 5, 7 };
矢量 b = { 2, 4, 6 };
// 需要目的地足够大
矢量 c(7);
merge(a.begin(), a.end(), b.begin(), b.end(), c.begin());
// c = [1, 2, 3, 4, 5, 6, 7]
// 元素可以重复
一 = {1, 2, 4, 4};
b = { 2, 3, 3, 3, 4, 4 };
c.调整大小（10）；
merge(a.begin(), a.end(), b.begin(), b.end(), c.begin());
// c = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]
这个函数在归并排序的上下文中非常有用。
|
nth_element 是一个函数，可让您在线性时间内按排序顺序查找数组中的第 n 个元素。
该函数采用数组的左端、指向要查找其值的位置的迭代器以及数组的右端。
应用该函数后，所需的值将位于迭代器指示的位置，而剩余的值将获得混乱的顺序，但第n个左边的值将不超过它，并且向右不少。即应该理解为这个函数破坏了元素原有的顺序。
您可以在文档 (https://www.cplusplus.com/reference/algorithm/nth_element/) 中阅读更多内容。
例子：
矢量 a = { 4, 0, 3, 9, 2, 1, 8, 5, 6, 7 };
// 查找索引为 4 的元素
// 注意参数的顺序
nth_element(a.begin(), a.begin() + 4, a.end());
// a = [#, #, #, #, 4, $, $, $, $, $]
// 其中 # <= 4 和 4 <= $
|
长度为 n 的排列是没有重复数字 1、2、...、n 的有序集合。例如，[3, 1, 2] 和 [5, 4, 3, 2, 1] 是排列，但 [1, 2, 1, 3] 和 [1, 2, 4] 不是。
如果任务简化为需要遍历所有长度为 n 的排列，那么您可以使用 C++ 中一种方便的机制，称为“next_permutation”。
您可以在 文档中阅读更多相关信息，但重点是此函数会更改传递的数组以随后的字典顺序排列（通常是明确的和它的名字）。
要使用next_permutation，需要包含算法库（即在程序开头写#include ）
例子：
向量 arr;
arr = { 1, 2, 3 }; // 数组是 [1, 2, 3]
next_permutation(arr.begin(), arr.end()); // 将整个数组传递给函数
// 数组现在是 [1, 3, 2]
arr = { 2, 3, 1 }; // 数组是 [2, 3, 1]
next_permutation(arr.begin(), arr.end()); // 将整个数组传递给函数
// 数组现在是 [3, 1, 2]
next_permutation(arr.begin() + 1, arr.begin() + 3); // 可以将函数应用于数组的一部分，但实际上很少需要这样做
// 数组现在是 [3, 2, 1]
在这种情况下，该函数有一个布尔返回值，如果生成了下一个排列则为真，如果没有下一个排列则为假（当字典顺序中的最大排列被传递给函数时的情况）。
这使得在循环中使用该函数成为可能，这将允许我们一次迭代所有排列。由于 0 索引，在实践中使用从 0 到 n - 1 的数字排列通常更方便，尽管排列形式上包含从 1 到 n 的数字。但幸运的是，这不会导致代码中出现额外的叠加层，因为next_permutation 函数适用于 0 索引排列（甚至是数组中的重复元素，但您可以自己找到更多信息）。
通常，迭代所有排列的代码如下所示：
国际; // 排列大小
矢量烫发（n）； // perm 是“permutation”的缩写，即“排列”
for (int i = 0; i < n; i++)
perm[i] = i; // 初始化初始排列 0, 1, ..., n - 1
做 {
// 在循环中我们处理当前排列
} while (next_permutation(perm.begin(), perm.end())); // 如果没有下一个排列，则结束循环
此代码在 O(n! * f(n)) 中运行，其中 f(n) 是您处理一个特定排列所花费的时间。
|