120 <algorithm>库
1
Gemini(2.0 Flash Thinking) Prompts:
2
请生成系统性、结构化的学习笔记，要求涵盖各个知识点。关于：c++的库。
3
**内容要求**如下：
4
1. 先写介绍，再写正文，最后做总结。
5
2. 合理使用emoji；
6
3. 不能遗漏任何知识点；
7
4. 对每个API(函数、变量)给出名称、用途、原型、代码、注释；
8
5. 在专业的角度指明最佳实践、常见错误用法、陷阱等；
9
**格式要求**如下：
10
1. **多级标题**：用 `## 1 一级标题` → `### 1.1 二级标题` → `### 1.1.1 三级标题` 的层级编号；
11
2. **单级条目**：所有 `1.` `2.` `3.` 这样的单级列表，改用带圈数字 `①` `②` `③` 表示；
12
3. **禁止使用**：Markdown 的 `-` `*` 无序列表或 `1.` `2.` 有序列表语法；
13
4. 请自动生成层级编号（如 1.1、1.2），无需我手动输入数字。不要大标题，正文从## 1. 开始；
14
5. 在表格或代码块的前后添加空行；
1. <algorithm> 库介绍 🚀
<algorithm> 是 C++ 标准库中的一个头文件，它提供了大量用于操作序列（如数组、std::vector、std::list 等）的通用算法。这些算法可以执行各种操作，包括排序、搜索、计数、修改、比较等等。使用 <algorithm> 库可以大大简化代码，提高效率和可读性，并减少出错的可能性。它利用了迭代器的概念，使得算法可以独立于容器类型进行操作，具有高度的通用性。
2. <algorithm> 库正文
2.1 排序算法 🥇
2.1.1 std::sort
① 名称: std::sort
② 用途: 对指定范围内的元素进行升序排序。
③ 原型:
1
template <class RandomAccessIterator>
2
void sort(RandomAccessIterator first, RandomAccessIterator last);
3
4
template <class RandomAccessIterator, class Compare>
5
void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
int main() {
6
std::vector<int> v = {5, 2, 8, 1, 9, 4};
7
std::cout << "排序前: ";
8
for (int x : v) std::cout << x << " ";
9
std::cout << std::endl;
10
11
std::sort(v.begin(), v.end()); // 默认升序排序
12
13
std::cout << "排序后: ";
14
for (int x : v) std::cout << x << " ";
15
std::cout << std::endl;
16
17
std::sort(v.begin(), v.end(), std::greater<int>()); // 使用比较函数进行降序排序
18
19
std::cout << "降序排序后: ";
20
for (int x : v) std::cout << x << " ";
21
std::cout << std::endl;
22
23
return 0;
24
}
⑤ 注释:
- 第一个版本使用元素类型的 < 运算符进行比较。
- 第二个版本接受一个自定义的比较函数或函数对象 comp，用于定义元素的排序规则。
- first 和 last 是指向要排序范围的首尾迭代器（左闭右开区间 [first, last)）。
- std::sort 的平均时间复杂度为 O(N log N)，其中 N 是元素个数。
⑥ 最佳实践:
- 对于需要稳定排序的场景（即相等元素的相对顺序在排序后保持不变），应使用 std::stable_sort。
- 如果只需要部分排序（例如找到最小的 K 个元素），可以考虑使用 std::partial_sort。
⑦ 常见错误用法:
- 传递无效的迭代器范围（例如 first 大于或等于 last）。
- 在自定义比较函数中没有定义严格弱序关系（strict weak ordering），可能导致未定义的行为。
⑧ 陷阱:
- std::sort 要求迭代器类型是随机访问迭代器，因此不能直接用于 std::list 或 std::forward_list。对于这些容器，应使用其成员函数 sort()。
2.1.2 std::stable_sort
① 名称: std::stable_sort
② 用途: 对指定范围内的元素进行稳定排序（相等元素的相对顺序保持不变）。
③ 原型:
1
template <class RandomAccessIterator>
2
void stable_sort(RandomAccessIterator first, RandomAccessIterator last);
3
4
template <class RandomAccessIterator, class Compare>
5
void stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
struct Person {
6
std::string name;
7
int age;
8
};
9
10
bool compareByName(const Person& a, const Person& b) {
11
return a.name < b.name;
12
}
13
14
int main() {
15
std::vector<Person> people = {
16
{"Alice", 30},
17
{"Bob", 25},
18
{"Charlie", 30},
19
{"David", 20}
20
};
21
22
std::stable_sort(people.begin(), people.end(), compareByName);
23
24
std::cout << "按姓名稳定排序后:" << std::endl;
25
for (const auto& p : people) {
26
std::cout << p.name << " (" << p.age << ")" << std::endl;
27
}
28
29
return 0;
30
}
⑤ 注释:
- 与 std::sort 类似，但保证相等元素的原始相对顺序不变。
- 时间复杂度通常比 std::sort 略高，在最坏情况下可能达到 O(N log² N) 或 O(N log N)，取决于实现和可用内存。
⑥ 最佳实践:
- 当需要保持相等元素的相对顺序时使用，例如在多级排序中。
⑦ 常见错误用法:
- 与 std::sort 类似。
⑧ 陷阱:
- 性能可能比 std::sort 差，应根据实际需求选择合适的排序算法。
2.1.3 std::partial_sort
① 名称: std::partial_sort
② 用途: 对指定范围内的元素进行部分排序，使得范围内的前 middle - first 个元素是有序的，并且它们是整个范围中最小（或根据比较函数定义）的那些元素。
③ 原型:
1
template <class RandomAccessIterator>
2
void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);
3
4
template <class RandomAccessIterator, class Compare>
5
void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
int main() {
6
std::vector<int> v = {5, 2, 8, 1, 9, 4, 7, 3, 6};
7
std::cout << "排序前: ";
8
for (int x : v) std::cout << x << " ";
9
std::cout << std::endl;
10
11
std::partial_sort(v.begin(), v.begin() + 3, v.end()); // 将最小的 3 个元素排序到前面
12
13
std::cout << "部分排序后 (前 3 个最小元素): ";
14
for (int x : v) std::cout << x << " ";
15
std::cout << std::endl;
16
17
std::partial_sort(v.begin(), v.begin() + 3, v.end(), std::greater<int>()); // 将最大的 3 个元素排序到前面
18
19
std::cout << "部分排序后 (前 3 个最大元素): ";
20
for (int x : v) std::cout << x << " ";
21
std::cout << std::endl;
22
23
return 0;
24
}
⑤ 注释:
- middle 是一个迭代器，指向排序后应该位于中间的元素（不包括）。
- [first, middle) 范围内的元素是排序后的结果。
- [middle, last) 范围内的元素顺序未定义。
- 时间复杂度约为 O(N log K)，其中 N 是元素总数，K 是 middle - first。
⑥ 最佳实践:
- 当只需要找到并排序最小或最大的 K 个元素时非常有用，比完全排序更高效。
⑦ 常见错误用法:
- middle 超出 [first, last] 的范围。
⑧ 陷阱:
- [middle, last) 范围内的元素顺序是不确定的。
2.1.4 std::partial_sort_copy
① 名称: std::partial_sort_copy
② 用途: 将源范围内的部分排序结果复制到目标范围。
③ 原型:
1
template <class InputIterator, class RandomAccessIterator>
2
RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last,
3
RandomAccessIterator result_first, RandomAccessIterator result_last);
4
5
template <class InputIterator, class RandomAccessIterator, class Compare>
6
RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last,
7
RandomAccessIterator result_first, RandomAccessIterator result_last,
8
Compare comp);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
int main() {
6
std::vector<int> source = {5, 2, 8, 1, 9, 4};
7
std::vector<int> result(3);
8
9
std::partial_sort_copy(source.begin(), source.end(), result.begin(), result.end());
10
11
std::cout << "部分排序复制后 (最小的 3 个): ";
12
for (int x : result) std::cout << x << " ";
13
std::cout << std::endl;
14
15
std::vector<int> result_desc(3);
16
std::partial_sort_copy(source.begin(), source.end(), result_desc.begin(), result_desc.end(), std::greater<int>());
17
18
std::cout << "部分排序复制后 (最大的 3 个): ";
19
for (int x : result_desc) std::cout << x << " ";
20
std::cout << std::endl;
21
22
return 0;
23
}
⑤ 注释:
- 从 [first, last) 读取元素，并将排序后的前 result_last - result_first 个最小（或根据比较函数定义）的元素写入到 [result_first, result_last)。
- 返回指向目标范围中最后一个写入元素的下一个位置的迭代器。
- 如果源范围的元素个数少于目标范围的大小，则目标范围中未被写入的部分的值不确定。
⑥ 最佳实践:
- 当需要在不修改原始数据的情况下获取部分排序结果时使用。
- 确保目标范围足够大以容纳所需的排序元素。
⑦ 常见错误用法:
- 目标范围太小，无法容纳部分排序的结果。
⑧ 陷阱:
- 如果目标范围大于源范围，目标范围的剩余部分不会被修改。
2.1.5 std::nth_element
① 名称: std::nth_element
② 用途: 将指定范围内的第 n 个元素（按排序顺序）放置在其正确的位置上，使得该元素之前的所有元素都小于或等于它，并且该元素之后的所有元素都大于或等于它。
③ 原型:
1
template <class RandomAccessIterator>
2
void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);
3
4
template <class RandomAccessIterator, class Compare>
5
void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
int main() {
6
std::vector<int> v = {5, 2, 8, 1, 9, 4, 7, 3, 6};
7
std::cout << "原向量: ";
8
for (int x : v) std::cout << x << " ";
9
std::cout << std::endl;
10
11
std::nth_element(v.begin(), v.begin() + 4, v.end()); // 找到第 5 小的元素 (索引为 4)
12
13
std::cout << "找到第 5 小的元素后: ";
14
for (int x : v) std::cout << x << " ";
15
std::cout << std::endl;
16
std::cout << "第 5 小的元素是: " << v[4] << std::endl;
17
18
return 0;
19
}
⑤ 注释:
- nth 是一个迭代器，指向要放置在其正确位置上的第 n 个元素。
- 调用后，*nth 将是如果整个范围排序后应该位于该位置的元素。
- [first, nth) 范围内的元素都小于或等于 *nth，但它们的顺序未定义。
- [nth + 1, last) 范围内的元素都大于或等于 *nth，但它们的顺序未定义。
- 平均时间复杂度为 O(N)。
⑥ 最佳实践:
- 当只需要找到中位数或某个特定排名的元素时非常高效。
⑦ 常见错误用法:
- nth 超出 [first, last) 的范围。
⑧ 陷阱:
- 除了第 n 个元素之外，其他元素的顺序是不确定的。
2.1.6 std::is_sorted
① 名称: std::is_sorted
② 用途: 检查指定范围内的元素是否已按升序排序。
③ 原型:
1
template <class ForwardIterator>
2
bool is_sorted(ForwardIterator first, ForwardIterator last);
3
4
template <class ForwardIterator, class Compare>
5
bool is_sorted(ForwardIterator first, ForwardIterator last, Compare comp);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
int main() {
6
std::vector<int> v1 = {1, 2, 3, 4, 5};
7
std::vector<int> v2 = {5, 2, 8, 1, 9};
8
9
if (std::is_sorted(v1.begin(), v1.end())) {
10
std::cout << "v1 是已排序的" << std::endl;
11
} else {
12
std::cout << "v1 不是已排序的" << std::endl;
13
}
14
15
if (std::is_sorted(v2.begin(), v2.end())) {
16
std::cout << "v2 是已排序的" << std::endl;
17
} else {
18
std::cout << "v2 不是已排序的" << std::endl;
19
}
20
21
return 0;
22
}
⑤ 注释:
- 返回 true 如果范围 [first, last) 中的元素按升序排序，否则返回 false。
- 第二个版本使用自定义的比较函数 comp。
⑥ 最佳实践:
- 在执行依赖于已排序数据的操作之前进行检查。
⑦ 常见错误用法:
- 无。
⑧ 陷阱:
- 空范围被认为是已排序的。
2.1.7 std::is_sorted_until
① 名称: std::is_sorted_until
② 用途: 找到指定范围内第一个破坏排序顺序的元素。
③ 原型:
1
template <class ForwardIterator>
2
ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last);
3
4
template <class ForwardIterator, class Compare>
5
ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last, Compare comp);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
int main() {
6
std::vector<int> v = {1, 2, 3, 5, 4, 6, 7};
7
auto it = std::is_sorted_until(v.begin(), v.end());
8
9
if (it == v.end()) {
10
std::cout << "向量已完全排序" << std::endl;
11
} else {
12
std::cout << "向量排序到元素: " << *it << std::endl;
13
std::cout << "该元素的索引是: " << std::distance(v.begin(), it) << std::endl;
14
}
15
16
return 0;
17
}
⑤ 注释:
- 返回一个指向范围内第一个不满足排序顺序的元素的迭代器。
- 如果整个范围都已排序，则返回 last。
- 第二个版本使用自定义的比较函数 comp。
⑥ 最佳实践:
- 用于确定已排序范围的长度。
⑦ 常见错误用法:
- 无。
⑧ 陷阱:
- 空范围返回 first (等于 last)。
2.2 搜索算法 🔍
2.2.1 std::binary_search
① 名称: std::binary_search
② 用途: 在已排序的范围内查找是否存在指定的值。
③ 原型:
1
template <class ForwardIterator, class T>
2
bool binary_search(ForwardIterator first, ForwardIterator last, const T& value);
3
4
template <class ForwardIterator, class T, class Compare>
5
bool binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
int main() {
6
std::vector<int> v = {1, 3, 5, 7, 9};
7
8
if (std::binary_search(v.begin(), v.end(), 5)) {
9
std::cout << "5 存在于向量中" << std::endl;
10
} else {
11
std::cout << "5 不存在于向量中" << std::endl;
12
}
13
14
if (std::binary_search(v.begin(), v.end(), 6)) {
15
std::cout << "6 存在于向量中" << std::endl;
16
} else {
17
std::cout << "6 不存在于向量中" << std::endl;
18
}
19
20
return 0;
21
}
⑤ 注释:
- 返回 true 如果在 [first, last) 中找到等于 value 的元素，否则返回 false。
- 前提条件: 输入范围必须是已排序的。
- 时间复杂度为 O(log N)。
⑥ 最佳实践:
- 用于在大型已排序数据集中快速查找元素。
⑦ 常见错误用法:
- 在未排序的范围内使用 std::binary_search，结果是未定义的。
⑧ 陷阱:
- 如果范围内存在多个等于 value 的元素，std::binary_search 不保证找到的是哪一个。
2.2.2 std::lower_bound
① 名称: std::lower_bound
② 用途: 在已排序的范围内查找第一个大于或等于给定值的元素。
③ 原型:
1
template <class ForwardIterator, class T>
2
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value);
3
4
template <class ForwardIterator, class T, class Compare>
5
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
int main() {
6
std::vector<int> v = {1, 3, 3, 5, 7, 9};
7
auto it = std::lower_bound(v.begin(), v.end(), 3);
8
9
if (it != v.end()) {
10
std::cout << "第一个大于或等于 3 的元素是: " << *it << "，索引是: " << std::distance(v.begin(), it) << std::endl;
11
} else {
12
std::cout << "没有大于或等于 3 的元素" << std::endl;
13
}
14
15
auto it2 = std::lower_bound(v.begin(), v.end(), 4);
16
if (it2 != v.end()) {
17
std::cout << "第一个大于或等于 4 的元素是: " << *it2 << "，索引是: " << std::distance(v.begin(), it2) << std::endl;
18
} else {
19
std::cout << "没有大于或等于 4 的元素" << std::endl;
20
}
21
22
return 0;
23
}
⑤ 注释:
- 返回一个指向范围内第一个大于或等于 value 的元素的迭代器。
- 如果所有元素都小于 value，则返回 last。
- 前提条件: 输入范围必须是已排序的。
- 时间复杂度为 O(log N)。
⑥ 最佳实践:
- 用于查找插入新元素以保持排序顺序的合适位置。
⑦ 常见错误用法:
- 在未排序的范围内使用。
⑧ 陷阱:
- 即使 value 不存在于范围内，也会返回一个迭代器。需要检查返回的迭代器是否等于 last。
2.2.3 std::upper_bound
① 名称: std::upper_bound
② 用途: 在已排序的范围内查找第一个大于给定值的元素。
③ 原型:
1
template <class ForwardIterator, class T>
2
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value);
3
4
template <class ForwardIterator, class T, class Compare>
5
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
int main() {
6
std::vector<int> v = {1, 3, 3, 5, 7, 9};
7
auto it = std::upper_bound(v.begin(), v.end(), 3);
8
9
if (it != v.end()) {
10
std::cout << "第一个大于 3 的元素是: " << *it << "，索引是: " << std::distance(v.begin(), it) << std::endl;
11
} else {
12
std::cout << "没有大于 3 的元素" << std::endl;
13
}
14
15
auto it2 = std::upper_bound(v.begin(), v.end(), 9);
16
if (it2 != v.end()) {
17
std::cout << "第一个大于 9 的元素是: " << *it2 << "，索引是: " << std::distance(v.begin(), it2) << std::endl;
18
} else {
19
std::cout << "没有大于 9 的元素" << std::endl;
20
}
21
22
return 0;
23
}
⑤ 注释:
- 返回一个指向范围内第一个大于 value 的元素的迭代器。
- 如果所有元素都小于或等于 value，则返回 last。
- 前提条件: 输入范围必须是已排序的。
- 时间复杂度为 O(log N)。
⑥ 最佳实践:
- 与 std::lower_bound 结合使用可以确定已排序范围内等于某个值的元素的范围。
⑦ 常见错误用法:
- 在未排序的范围内使用。
⑧ 陷阱:
- 即使 value 不存在于范围内，也会返回一个迭代器。需要检查返回的迭代器是否等于 last。
2.2.4 std::equal_range
① 名称: std::equal_range
② 用途: 在已排序的范围内查找所有等于给定值的元素的范围。
③ 原型:
1
template <class ForwardIterator, class T>
2
std::pair<ForwardIterator, ForwardIterator>
3
equal_range(ForwardIterator first, ForwardIterator last, const T& value);
4
5
template <class ForwardIterator, class T, class Compare>
6
std::pair<ForwardIterator, ForwardIterator>
7
equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
int main() {
6
std::vector<int> v = {1, 3, 3, 3, 5, 7, 9};
7
auto result = std::equal_range(v.begin(), v.end(), 3);
8
9
if (result.first != result.second) {
10
std::cout << "找到等于 3 的元素的范围: ["
11
<< std::distance(v.begin(), result.first) << ", "
12
<< std::distance(v.begin(), result.second) << ")" << std::endl;
13
std::cout << "这些元素是: ";
14
for (auto it = result.first; it != result.second; ++it) {
15
std::cout << *it << " ";
16
}
17
std::cout << std::endl;
18
} else {
19
std::cout << "没有找到等于 3 的元素" << std::endl;
20
}
21
22
return 0;
23
}
⑤ 注释:
- 返回一个 std::pair，其中 first 是指向第一个大于或等于 value 的元素的迭代器（等同于 std::lower_bound 的返回值），second 是指向第一个大于 value 的元素的迭代器（等同于 std::upper_bound 的返回值）。
- 如果范围内没有等于 value 的元素，则 first 和 second 将指向同一个位置。
- 前提条件: 输入范围必须是已排序的。
- 时间复杂度为 O(log N)。
⑥ 最佳实践:
- 用于高效地获取已排序范围内特定值的所有匹配项。
⑦ 常见错误用法:
- 在未排序的范围内使用。
⑧ 陷阱:
- 即使 value 不存在于范围内，也会返回一个迭代器对。需要检查 first 是否等于 second。
2.2.5 std::find
① 名称: std::find
② 用途: 在指定范围内查找第一个等于给定值的元素。
③ 原型:
1
template <class InputIterator, class T>
2
InputIterator find(InputIterator first, InputIterator last, const T& value);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
int main() {
6
std::vector<int> v = {1, 3, 5, 7, 9};
7
auto it = std::find(v.begin(), v.end(), 5);
8
9
if (it != v.end()) {
10
std::cout << "找到元素: " << *it << "，索引是: " << std::distance(v.begin(), it) << std::endl;
11
} else {
12
std::cout << "没有找到该元素" << std::endl;
13
}
14
15
auto it2 = std::find(v.begin(), v.end(), 6);
16
if (it2 != v.end()) {
17
std::cout << "找到元素: " << *it2 << std::endl;
18
} else {
19
std::cout << "没有找到该元素" << std::endl;
20
}
21
22
return 0;
23
}
⑤ 注释:
- 返回一个指向范围内第一个等于 value 的元素的迭代器。
- 如果未找到，则返回 last。
- 时间复杂度为 O(N)。
⑥ 最佳实践:
- 用于在未排序的范围内查找元素。
⑦ 常见错误用法:
- 无。
⑧ 陷阱:
- 对于大型已排序数据集，std::binary_search、std::lower_bound、std::upper_bound 和 std::equal_range 通常更高效。
2.2.6 std::find_if
① 名称: std::find_if
② 用途: 在指定范围内查找第一个满足给定谓词（predicate）的元素。
③ 原型:
1
template <class InputIterator, class Predicate>
2
InputIterator find_if(InputIterator first, InputIterator last, Predicate pred);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
bool is_even(int n) {
6
return n % 2 == 0;
7
}
8
9
int main() {
10
std::vector<int> v = {1, 3, 5, 8, 7, 9};
11
auto it = std::find_if(v.begin(), v.end(), is_even);
12
13
if (it != v.end()) {
14
std::cout << "找到第一个偶数: " << *it << "，索引是: " << std::distance(v.begin(), it) << std::endl;
15
} else {
16
std::cout << "没有找到偶数" << std::endl;
17
}
18
19
return 0;
20
}
⑤ 注释:
- pred 是一个可调用对象（函数、函数对象、lambda 表达式），它接受范围内的元素并返回一个可转换为 bool 的值。
- 返回一个指向范围内第一个使 pred 返回 true 的元素的迭代器。
- 如果未找到，则返回 last。
- 时间复杂度为 O(N)。
⑥ 最佳实践:
- 用于根据特定条件查找元素。
⑦ 常见错误用法:
- 谓词函数的逻辑错误。
⑧ 陷阱:
- 无。
2.2.7 std::find_if_not
① 名称: std::find_if_not
② 用途: 在指定范围内查找第一个不满足给定谓词的元素。
③ 原型:
1
template <class InputIterator, class Predicate>
2
InputIterator find_if_not(InputIterator first, InputIterator last, Predicate pred);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
bool is_odd(int n) {
6
return n % 2 != 0;
7
}
8
9
int main() {
10
std::vector<int> v = {1, 3, 5, 8, 7, 9};
11
auto it = std::find_if_not(v.begin(), v.end(), is_odd);
12
13
if (it != v.end()) {
14
std::cout << "找到第一个非奇数 (偶数): " << *it << "，索引是: " << std::distance(v.begin(), it) << std::endl;
15
} else {
16
std::cout << "所有元素都是奇数" << std::endl;
17
}
18
19
return 0;
20
}
⑤ 注释:
- 与 std::find_if 类似，但查找的是第一个使 pred 返回 false 的元素。
⑥ 最佳实践:
- 用于查找不满足特定条件的元素。
⑦ 常见错误用法:
- 谓词函数的逻辑错误。
⑧ 陷阱:
- 无。
2.2.8 std::adjacent_find
① 名称: std::adjacent_find
② 用途: 在指定范围内查找第一对相邻的相等元素。
③ 原型:
1
template <class ForwardIterator>
2
ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last);
3
4
template <class ForwardIterator, class BinaryPredicate>
5
ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate binary_pred);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
int main() {
6
std::vector<int> v1 = {1, 2, 3, 3, 4, 5};
7
auto it1 = std::adjacent_find(v1.begin(), v1.end());
8
if (it1 != v1.end()) {
9
std::cout << "在 v1 中找到相邻的相等元素: " << *it1 << " 和 " << *(it1 + 1) << std::endl;
10
} else {
11
std::cout << "在 v1 中没有找到相邻的相等元素" << std::endl;
12
}
13
14
std::vector<int> v2 = {1, 2, 3, 4, 5};
15
auto it2 = std::adjacent_find(v2.begin(), v2.end());
16
if (it2 != v2.end()) {
17
std::cout << "在 v2 中找到相邻的相等元素" << std::endl;
18
} else {
19
std::cout << "在 v2 中没有找到相邻的相等元素" << std::endl;
20
}
21
22
std::vector<int> v3 = {1, 2, 4, 3, 5};
23
auto it3 = std::adjacent_find(v3.begin(), v3.end(), [](int a, int b){ return std::abs(a - b) > 1; });
24
if (it3 != v3.end()) {
25
std::cout << "在 v3 中找到相邻元素差的绝对值大于 1 的元素: " << *it3 << " 和 " << *(it3 + 1) << std::endl;
26
} else {
27
std::cout << "在 v3 中没有找到满足条件的相邻元素" << std::endl;
28
}
29
30
return 0;
31
}
⑤ 注释:
- 第一个版本使用 == 运算符比较相邻元素。
- 第二个版本使用自定义的二元谓词 binary_pred 来比较相邻元素。
- 返回一个指向第一对相等（或满足谓词）的第一个元素的迭代器。
- 如果未找到，则返回 last。
- 时间复杂度为 O(N)。
⑥ 最佳实践:
- 用于检测序列中是否存在重复项或满足特定关系的相邻元素。
⑦ 常见错误用法:
- 谓词函数的逻辑错误。
⑧ 陷阱:
- 无。
2.2.9 std::search
① 名称: std::search
② 用途: 在一个范围内搜索另一个子序列的第一次出现。
③ 原型:
1
template <class ForwardIterator1, class ForwardIterator2>
2
ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1,
3
ForwardIterator2 first2, ForwardIterator2 last2);
4
5
template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
6
ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1,
7
ForwardIterator2 first2, ForwardIterator2 last2,
8
BinaryPredicate binary_pred);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
int main() {
6
std::vector<int> v1 = {1, 2, 3, 4, 5, 2, 3, 4};
7
std::vector<int> v2 = {2, 3, 4};
8
auto it = std::search(v1.begin(), v1.end(), v2.begin(), v2.end());
9
10
if (it != v1.end()) {
11
std::cout << "在 v1 中找到子序列 v2，起始位置的索引是: " << std::distance(v1.begin(), it) << std::endl;
12
} else {
13
std::cout << "在 v1 中没有找到子序列 v2" << std::endl;
14
}
15
16
std::vector<int> v3 = {1, 2, 3, 4, 5};
17
std::vector<int> v4 = {2, 4};
18
auto it2 = std::search(v3.begin(), v3.end(), v4.begin(), v4.end(),
19
[](int a, int b){ return a == b; }); // 仍然使用相等比较
20
21
if (it2 != v3.end()) {
22
std::cout << "在 v3 中找到子序列 v4" << std::endl;
23
} else {
24
std::cout << "在 v3 中没有找到子序列 v4" << std::endl;
25
}
26
27
return 0;
28
}
⑤ 注释:
- 在范围 [first1, last1) 中搜索子序列 [first2, last2) 的第一次出现。
- 第一个版本使用 == 运算符比较元素。
- 第二个版本使用自定义的二元谓词 binary_pred 来比较元素。
- 返回一个指向 [first1, last1) 中子序列第一次出现位置的第一个元素的迭代器。
- 如果未找到，则返回 last1。
- 时间复杂度在最坏情况下为 O((N-M+1)M)，其中 N 是第一个范围的大小，M 是第二个范围的大小。
⑥ 最佳实践:
- 用于在一个序列中查找另一个序列。
⑦ 常见错误用法:
- 谓词函数的逻辑错误。
⑧ 陷阱*:
- 空子序列被认为存在于任何范围内（返回 first1）。
2.2.10 std::search_n
① 名称: std::search_n
② 用途: 在一个范围内搜索指定值的连续出现。
③ 原型:
1
template <class ForwardIterator, class Size, class T>
2
ForwardIterator search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value);
3
4
template <class ForwardIterator, class Size, class T, class BinaryPredicate>
5
ForwardIterator search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value,
6
BinaryPredicate binary_pred);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
int main() {
6
std::vector<int> v = {1, 2, 2, 2, 3, 4, 2, 2};
7
auto it = std::search_n(v.begin(), v.end(), 3, 2);
8
9
if (it != v.end()) {
10
std::cout << "找到连续 3 个 2，起始位置的索引是: " << std::distance(v.begin(), it) << std::endl;
11
} else {
12
std::cout << "没有找到连续 3 个 2" << std::endl;
13
}
14
15
auto it2 = std::search_n(v.begin(), v.end(), 2, 2, [](int a, int b){ return a == b; });
16
if (it2 != v.end()) {
17
std::cout << "找到连续 2 个 2，起始位置的索引是: " << std::distance(v.begin(), it2) << std::endl;
18
} else {
19
std::cout << "没有找到连续 2 个 2" << std::endl;
20
}
21
22
return 0;
23
}
⑤ 注释:
- 在范围 [first, last) 中搜索 count 个连续的等于 value 的元素。
- 第一个版本使用 == 运算符比较元素。
- 第二个版本使用自定义的二元谓词 binary_pred 来比较元素。
- 返回一个指向第一个连续匹配序列的第一个元素的迭代器。
- 如果未找到，则返回 last。
- 时间复杂度在最坏情况下为 O((N-count+1)count)。
⑥ 最佳实践:
- 用于查找序列中重复出现的特定值。
⑦ 常见错误用法:
- count 为 0 时，总是返回 first。
- 谓词函数的逻辑错误。
⑧ 陷阱*:
- 无。
2.2.11 std::find_first_of
① 名称: std::find_first_of
② 用途: 在一个范围内查找另一个范围中任何一个元素的第一次出现。
③ 原型:
1
template <class InputIterator1, class InputIterator2>
2
InputIterator1 find_first_of(InputIterator1 first1, InputIterator1 last1,
3
InputIterator2 first2, InputIterator2 last2);
4
5
template <class InputIterator1, class InputIterator2, class BinaryPredicate>
6
InputIterator1 find_first_of(InputIterator1 first1, InputIterator1 last1,
7
InputIterator2 first2, InputIterator2 last2,
8
BinaryPredicate binary_pred);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
int main() {
6
std::vector<int> v1 = {1, 2, 3, 4, 5};
7
std::vector<int> v2 = {4, 6};
8
auto it = std::find_first_of(v1.begin(), v1.end(), v2.begin(), v2.end());
9
10
if (it != v1.end()) {
11
std::cout << "在 v1 中找到 v2 中的元素: " << *it << "，索引是: " << std::distance(v1.begin(), it) << std::endl;
12
} else {
13
std::cout << "在 v1 中没有找到 v2 中的任何元素" << std::endl;
14
}
15
16
std::vector<char> s1 = {'a', 'b', 'c', 'd'};
17
std::vector<char> s2 = {'c', 'e'};
18
auto it2 = std::find_first_of(s1.begin(), s1.end(), s2.begin(), s2.end(),
19
[](char c1, char c2){ return std::tolower(c1) == std::tolower(c2); });
20
21
if (it2 != s1.end()) {
22
std::cout << "在 s1 中找到 s2 中的元素 (忽略大小写): " << *it2 << std::endl;
23
} else {
24
std::cout << "在 s1 中没有找到 s2 中的任何元素 (忽略大小写)" << std::endl;
25
}
26
27
return 0;
28
}
⑤ 注释:
- 在范围 [first1, last1) 中查找第一个与范围 [first2, last2) 中的任何元素相等的元素。
- 第一个版本使用 == 运算符比较元素。
- 第二个版本使用自定义的二元谓词 binary_pred 来比较元素。
- 返回一个指向 [first1, last1) 中第一个匹配元素的迭代器。
- 如果未找到，则返回 last1。
- 时间复杂度在最坏情况下为 O(NM)，其中 N 是第一个范围的大小，M 是第二个范围的大小。
⑥ 最佳实践:
- 用于在一个字符串中查找任何一个来自另一个字符串的字符。
⑦ 常见错误用法:
- 谓词函数的逻辑错误。
⑧ 陷阱*:
- 如果第二个范围为空，则总是返回 first1。
2.3 计数算法 🔢
2.3.1 std::count
① 名称: std::count
② 用途: 计算指定范围内等于给定值的元素个数。
③ 原型:
1
template <class InputIterator, class T>
2
typename iterator_traits<InputIterator>::difference_type
3
count(InputIterator first, InputIterator last, const T& value);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
int main() {
6
std::vector<int> v = {1, 2, 2, 3, 2, 4, 2};
7
int count_of_2 = std::count(v.begin(), v.end(), 2);
8
9
std::cout << "向量中 2 的个数是: " << count_of_2 << std::endl;
10
11
return 0;
12
}
⑤ 注释:
- 返回范围 [first, last) 中等于 value 的元素个数。
- 时间复杂度为 O(N)。
⑥ 最佳实践:
- 用于统计特定值在序列中出现的次数。
⑦ 常见错误用法:
- 无。
⑧ 陷阱:
- 无。
2.3.2 std::count_if
① 名称: std::count_if
② 用途: 计算指定范围内满足给定谓词的元素个数。
③ 原型:
1
template <class InputIterator, class Predicate>
2
typename iterator_traits<InputIterator>::difference_type
3
count_if(InputIterator first, InputIterator last, Predicate pred);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
bool is_greater_than_2(int n) {
6
return n > 2;
7
}
8
9
int main() {
10
std::vector<int> v = {1, 2, 3, 4, 1, 5};
11
int count_greater_than_2 = std::count_if(v.begin(), v.end(), is_greater_than_2);
12
13
std::cout << "向量中大于 2 的元素个数是: " << count_greater_than_2 << std::endl;
14
15
return 0;
16
}
⑤ 注释:
- 返回范围 [first, last) 中使谓词 pred 返回 true 的元素个数。
- 时间复杂度为 O(N)。
⑥ 最佳实践:
- 用于统计满足特定条件的元素在序列中出现的次数。
⑦ 常见错误用法:
- 谓词函数的逻辑错误。
⑧ 陷阱:
- 无。
2.4 修改序列的操作 🛠️
2.4.1 std::copy
① 名称: std::copy
② 用途: 将一个范围内的元素复制到另一个范围。
③ 原型:
1
template <class InputIterator, class OutputIterator>
2
OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
int main() {
6
std::vector<int> source = {1, 2, 3, 4, 5};
7
std::vector<int> destination(5);
8
9
auto it = std::copy(source.begin(), source.end(), destination.begin());
10
11
std::cout << "复制后的目标向量: ";
12
for (int x : destination) std::cout << x << " ";
13
std::cout << std::endl;
14
std::cout << "返回的迭代器指向: " << (it == destination.end() ? "end()" : "非 end()") << std::endl;
15
16
return 0;
17
}
⑤ 注释:
- 将范围 [first, last) 中的元素复制到以 result 开头的范围。
- 返回一个指向目标范围中最后一个写入元素的下一个位置的迭代器。
- 目标范围必须有足够的空间来容纳要复制的元素。
- 时间复杂度为 O(N)，其中 N 是要复制的元素个数。
⑥ 最佳实践:
- 用于复制容器或容器的一部分。
⑦ 常见错误用法:
- 目标范围没有足够的空间，导致越界访问。
⑧ 陷阱:
- 如果源范围和目标范围有重叠，且目标范围的起始位置在源范围之内，行为是未定义的。在这种情况下，应使用 std::copy_backward。
2.4.2 std::copy_if
① 名称: std::copy_if
② 用途: 将一个范围内满足给定谓词的元素复制到另一个范围。
③ 原型:
1
template <class InputIterator, class OutputIterator, class Predicate>
2
OutputIterator copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
bool is_positive(int n) {
6
return n > 0;
7
}
8
9
int main() {
10
std::vector<int> source = {1, -2, 3, 0, 4, -5};
11
std::vector<int> destination;
12
13
std::copy_if(source.begin(), source.end(), std::back_inserter(destination), is_positive);
14
15
std::cout << "复制后的目标向量 (仅正数): ";
16
for (int x : destination) std::cout << x << " ";
17
std::cout << std::endl;
18
19
return 0;
20
}
⑤ 注释:
- 将范围 [first, last) 中使谓词 pred 返回 true 的元素复制到以 result 开头的范围。
- 通常与 std::back_inserter、std::front_inserter 或 std::inserter 结合使用，以便在目标容器中动态插入元素。
- 返回一个指向目标范围中最后一个写入元素的下一个位置的迭代器。
- 时间复杂度为 O(N)。
⑥ 最佳实践:
- 用于根据条件过滤并复制元素。
⑦ 常见错误用法:
- 谓词函数的逻辑错误。
⑧ 陷阱:
- 如果目标范围是固定大小的，需要确保有足够的空间。
2.4.3 std::copy_n
① 名称: std::copy_n
② 用途: 将一个范围内的前 n 个元素复制到另一个范围。
③ 原型:
1
template <class InputIterator, class Size, class OutputIterator>
2
OutputIterator copy_n(InputIterator first, Size n, OutputIterator result);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
int main() {
6
std::vector<int> source = {1, 2, 3, 4, 5};
7
std::vector<int> destination(3);
8
9
auto it = std::copy_n(source.begin(), 3, destination.begin());
10
11
std::cout << "复制后的目标向量 (前 3 个元素): ";
12
for (int x : destination) std::cout << x << " ";
13
std::cout << std::endl;
14
std::cout << "返回的迭代器指向: " << (it == destination.begin() + 3 ? "正确位置" : "错误位置") << std::endl;
15
16
return 0;
17
}
⑤ 注释:
- 从 first 开始复制 n 个元素到以 result 开头的范围。
- 返回一个指向目标范围中最后一个写入元素的下一个位置的迭代器。
- 需要确保源范围至少有 n 个元素，并且目标范围有足够的空间。
- 时间复杂度为 O(n)。
⑥ 最佳实践:
- 当需要复制固定数量的元素时使用。
⑦ 常见错误用法:
- n 大于源范围的元素个数，导致读取越界。
- 目标范围没有足够的空间。
⑧ 陷阱:
- 如果 n 为负数，行为是未定义的。
2.4.4 std::copy_backward
① 名称: std::copy_backward
② 用途: 将一个范围内的元素从后向前复制到另一个范围。
③ 原型:
1
template <class BidirectionalIterator1, class BidirectionalIterator2>
2
BidirectionalIterator2 copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last,
3
BidirectionalIterator2 result);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
int main() {
6
std::vector<int> source = {1, 2, 3};
7
std::vector<int> destination = {0, 0, 0, 0, 0};
8
9
auto it = std::copy_backward(source.begin(), source.end(), destination.begin() + 5);
10
11
std::cout << "复制后的目标向量 (从后向前): ";
12
for (int x : destination) std::cout << x << " ";
13
std::cout << std::endl;
14
std::cout << "返回的迭代器指向: " << (it == destination.begin() + 2 ? "正确位置" : "错误位置") << std::endl;
15
16
return 0;
17
}
⑤ 注释:
- 从 [first, last) 复制元素到以 result 结尾的范围。复制从 last - 1 开始，一直到 first。
- 返回一个指向目标范围中第一个被写入元素的迭代器。
- 目标范围必须有足够的空间来容纳要复制的元素。
- 当源范围和目标范围有重叠，且目标范围的起始位置在源范围之内时，应使用 std::copy_backward。
- 时间复杂度为 O(N)。
⑥ 最佳实践:
- 用于在原地移动元素或在重叠范围之间复制数据。
⑦ 常见错误用法:
- 目标范围没有足够的空间。
- 迭代器类型不匹配（需要双向迭代器）。
⑧ 陷阱:
- result 指向的是目标范围的结束位置。
2.4.5 std::move
① 名称: std::move
② 用途: 将一个范围内的元素移动到另一个范围。移动操作通常比复制更高效，特别是对于拥有大量资源的类型。
③ 原型:
1
template <class InputIterator, class OutputIterator>
2
OutputIterator move(InputIterator first, InputIterator last, OutputIterator result);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
int main() {
6
std::vector<std::string> source = {"Alice", "Bob", "Charlie"};
7
std::vector<std::string> destination(3);
8
9
auto it = std::move(source.begin(), source.end(), destination.begin());
10
11
std::cout << "移动后的源向量: ";
12
for (const auto& s : source) std::cout << s << " ";
13
std::cout << std::endl;
14
std::cout << "移动后的目标向量: ";
15
for (const auto& s : destination) std::cout << s << " ";
16
std::cout << std::endl;
17
std::cout << "返回的迭代器指向: " << (it == destination.end() ? "end()" : "非 end()") << std::endl;
18
19
return 0;
20
}
⑤ 注释:
- 将范围 [first, last) 中的元素移动到以 result 开头的范围。
- 移动后，源范围中的元素将处于有效的但不确定的状态。
- 返回一个指向目标范围中最后一个移动元素的下一个位置的迭代器。
- 目标范围必须有足够的空间。
- 时间复杂度为 O(N)。
⑥ 最佳实践:
- 对于移动语义有意义的类型（例如拥有动态分配内存的类型），使用 std::move 可以提高性能。
⑦ 常见错误用法:
- 在移动后仍然依赖源范围中的元素的值。
⑧ 陷阱:
- 移动操作后，源对象的状态是不确定的，应该避免再次使用。
2.4.6 std::move_backward
① 名称: std::move_backward
② 用途: 将一个范围内的元素从后向前移动到另一个范围。
③ 原型:
1
template <class BidirectionalIterator1, class BidirectionalIterator2>
2
BidirectionalIterator2 move_backward(BidirectionalIterator1 first, BidirectionalIterator1 last,
3
BidirectionalIterator2 result);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
int main() {
6
std::vector<std::string> source = {"Alice", "Bob", "Charlie"};
7
std::vector<std::string> destination = {"", "", "", "", ""};
8
9
auto it = std::move_backward(source.begin(), source.end(), destination.begin() + 5);
10
11
std::cout << "移动后的源向量: ";
12
for (const auto& s : source) std::cout << s << " ";
13
std::cout << std::endl;
14
std::cout << "移动后的目标向量 (从后向前): ";
15
for (const auto& s : destination) std::cout << s << " ";
16
std::cout << std::endl;
17
std::cout << "返回的迭代器指向: " << (it == destination.begin() + 2 ? "正确位置" : "错误位置") << std::endl;
18
19
return 0;
20
}
⑤ 注释:
- 将范围 [first, last) 中的元素从后向前移动到以 result 结尾的范围。
- 移动后，源范围中的元素将处于有效的但不确定的状态。
- 返回一个指向目标范围中第一个被移动元素的迭代器。
- 目标范围必须有足够的空间。
- 时间复杂度为 O(N)。
⑥ 最佳实践:
- 与 std::move 类似，但在需要从后向前移动时使用。
⑦ 常见错误用法:
- 在移动后仍然依赖源范围中的元素的值。
⑧ 陷阱:
- result 指向的是目标范围的结束位置。
2.4.7 std::fill
① 名称: std::fill
② 用途: 将指定范围内的所有元素设置为给定的值。
③ 原型:
1
template <class ForwardIterator, class T>
2
void fill(ForwardIterator first, ForwardIterator last, const T& value);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
int main() {
6
std::vector<int> v = {1, 2, 3, 4, 5};
7
std::fill(v.begin() + 1, v.end() - 1, 0);
8
9
std::cout << "填充后的向量: ";
10
for (int x : v) std::cout << x << " ";
11
std::cout << std::endl;
12
13
return 0;
14
}
⑤ 注释:
- 将范围 [first, last) 中的每个元素都赋值为 value。
- 时间复杂度为 O(N)。
⑥ 最佳实践:
- 用于初始化容器或将容器的某部分设置为特定值。
⑦ 常见错误用法:
- 传递无效的迭代器范围。
⑧ 陷阱:
- 无。
2.4.8 std::fill_n
① 名称: std::fill_n
② 用途: 将从指定位置开始的 n 个元素设置为给定的值。
③ 原型:
1
template <class OutputIterator, class Size, class T>
2
OutputIterator fill_n(OutputIterator first, Size n, const T& value);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
int main() {
6
std::vector<int> v = {1, 2, 3, 4, 5};
7
std::fill_n(v.begin() + 2, 2, 10);
8
9
std::cout << "填充后的向量: ";
10
for (int x : v) std::cout << x << " ";
11
std::cout << std::endl;
12
13
return 0;
14
}
⑤ 注释:
- 从 first 开始，将接下来的 n 个元素赋值为 value。
- 返回一个指向最后一个被赋值元素的下一个位置的迭代器。
- 需要确保目标范围有足够的空间容纳 n 个元素。
- 时间复杂度为 O(n)。
⑥ 最佳实践:
- 用于初始化容器的一部分或在指定位置插入重复值。
⑦ 常见错误用法:
- n 大于目标范围的剩余空间，导致越界访问。
⑧ 陷阱:
- 如果 n 为负数，行为是未定义的。
2.4.9 std::transform
① 名称: std::transform
② 用途: 对指定范围内的每个元素应用一个函数，并将结果存储到另一个范围（或原地）。
③ 原型:
1
template <class InputIterator, class OutputIterator, class UnaryOperation>
2
OutputIterator transform(InputIterator first1, InputIterator last1,
3
OutputIterator result, UnaryOperation op);
4
5
template <class InputIterator1, class InputIterator2, class OutputIterator, class BinaryOperation>
6
OutputIterator transform(InputIterator1 first1, InputIterator1 last1,
7
InputIterator2 first2,
8
OutputIterator result, BinaryOperation binary_op);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
#include <string>
5
#include <cctype>
6
7
int main() {
8
std::vector<int> v1 = {1, 2, 3, 4, 5};
9
std::vector<int> v2(v1.size());
10
std::transform(v1.begin(), v1.end(), v2.begin(), [](int n){ return n * n; });
11
12
std::cout << "平方后的向量: ";
13
for (int x : v2) std::cout << x << " ";
14
std::cout << std::endl;
15
16
std::vector<int> v3 = {10, 20, 30, 40, 50};
17
std::vector<int> v4(v1.size());
18
std::transform(v1.begin(), v1.end(), v3.begin(), v4.begin(), std::plus<int>());
19
20
std::cout << "两个向量相加的结果: ";
21
for (int x : v4) std::cout << x << " ";
22
std::cout << std::endl;
23
24
std::string s = "Hello World";
25
std::string s_upper(s.size(), ' ');
26
std::transform(s.begin(), s.end(), s_upper.begin(), ::toupper);
27
28
std::cout << "转换为大写后的字符串: " << s_upper << std::endl;
29
30
return 0;
31
}
⑤ 注释:
- 第一个版本对 [first1, last1) 中的每个元素应用一元操作 op，并将结果存储到以 result 开头的范围。
- 第二个版本对 [first1, last1) 和 [first2, first2 + (last1 - first1)) 中的对应元素应用二元操作 binary_op，并将结果存储到以 result 开头的范围。
- 返回一个指向目标范围中最后一个转换元素的下一个位置的迭代器。
- 目标范围必须有足够的空间。
- 时间复杂度为 O(N)。
⑥ 最佳实践:
- 用于对序列中的元素进行批量操作或转换。
⑦ 常见错误用法:
- 目标范围大小不足。
- 二元操作的版本中，第二个输入范围的大小与第一个输入范围不匹配。
⑧ 陷阱:
- 如果 result 指向输入范围内的某个位置，需要小心处理原地转换的情况。
2.4.10 std::generate
① 名称: std::generate
② 用途: 使用一个生成器函数为指定范围内的所有元素赋值。
③ 原型:
1
template <class ForwardIterator, class Generator>
2
void generate(ForwardIterator first, ForwardIterator last, Generator gen);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
int main() {
6
std::vector<int> v(5);
7
int n = 0;
8
std::generate(v.begin(), v.end(), [&n](){ return n++; });
9
10
std::cout << "生成的向量: ";
11
for (int x : v) std::cout << x << " ";
12
std::cout << std::endl;
13
14
return 0;
15
}
⑤ 注释:
- 对范围 [first, last) 中的每个元素调用生成器函数 gen，并将返回值赋给该元素。
- 生成器函数不接受任何参数。
- 时间复杂度为 O(N)。
⑥ 最佳实践:
- 用于使用函数或函数对象动态生成序列的值。
⑦ 常见错误用法:
- 生成器函数没有正确实现。
⑧ 陷阱:
- 无。
2.4.11 std::generate_n
① 名称: std::generate_n
② 用途: 使用一个生成器函数为从指定位置开始的 n 个元素赋值。
③ 原型:
1
template <class OutputIterator, class Size, class Generator>
2
OutputIterator generate_n(OutputIterator first, Size n, Generator gen);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
int main() {
6
std::vector<int> v(5);
7
int n = 10;
8
std::generate_n(v.begin(), 3, [&n](){ return n += 5; });
9
10
std::cout << "生成的向量 (前 3 个元素): ";
11
for (int x : v) std::cout << x << " ";
12
std::cout << std::endl;
13
14
return 0;
15
}
⑤ 注释:
- 从 first 开始，对接下来的 n 个元素调用生成器函数 gen，并将返回值赋给这些元素。
- 返回一个指向最后一个被赋值元素的下一个位置的迭代器。
- 需要确保目标范围有足够的空间容纳 n 个元素。
- 时间复杂度为 O(n)。
⑥ 最佳实践:
- 用于生成固定数量的动态值。
⑦ 常见错误用法:
- n 大于目标范围的剩余空间。
- 生成器函数没有正确实现。
⑧ 陷阱:
- 如果 n 为负数，行为是未定义的。
2.4.12 std::remove
① 名称: std::remove
② 用途: 从指定范围中移除所有等于给定值的元素（实际上是将这些元素移动到范围的末尾）。
③ 原型:
1
template <class ForwardIterator, class T>
2
ForwardIterator remove(ForwardIterator first, ForwardIterator last, const T& value);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
int main() {
6
std::vector<int> v = {1, 2, 3, 2, 4, 2, 5};
7
auto it = std::remove(v.begin(), v.end(), 2);
8
9
std::cout << "移除 2 后的向量: ";
10
for (auto i = v.begin(); i != it; ++i) {
11
std::cout << *i << " ";
12
}
13
std::cout << std::endl;
14
std::cout << "逻辑上移除的元素之后的内容: ";
15
for (auto i = it; i != v.end(); ++i) {
16
std::cout << *i << " ";
17
}
18
std::cout << std::endl;
19
20
v.erase(it, v.end()); // 真正从容器中删除元素
21
22
std::cout << "真正移除 2 后的向量: ";
23
for (int x : v) std::cout << x << " ";
24
std::cout << std::endl;
25
26
return 0;
27
}
⑤ 注释:
- 返回一个指向逻辑上移除的元素之后的新末尾的迭代器。
- 范围 [first, 返回值) 中的元素是不等于 value 的元素。
- 范围 [返回值, last) 中的元素是原来等于 value 的元素，但它们的顺序是不确定的。
- std::remove 并不改变容器的大小，要真正删除元素，需要与容器的 erase() 方法结合使用。
- 时间复杂度为 O(N)。
⑥ 最佳实践:
- 用于从序列中移除不需要的元素。
- 总是与 erase() 结合使用来改变容器的大小。
⑦ 常见错误用法:
- 忘记调用 erase() 来真正删除元素。
⑧ 陷阱:
- 不适用于关联容器（如 std::set、std::map），因为它们的元素是只读的。
2.4.13 std::remove_if
① 名称: std::remove_if
② 用途: 从指定范围中移除所有满足给定谓词的元素（同样是将它们移动到范围的末尾）。
③ 原型:
1
template <class ForwardIterator, class Predicate>
2
ForwardIterator remove_if(ForwardIterator first, ForwardIterator last, Predicate pred);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
bool is_odd(int n) {
6
return n % 2 != 0;
7
}
8
9
int main() {
10
std::vector<int> v = {1, 2, 3, 4, 5, 6};
11
auto it = std::remove_if(v.begin(), v.end(), is_odd);
12
13
std::cout << "移除奇数后的向量: ";
14
for (auto i = v.begin(); i != it; ++i) {
15
std::cout << *i << " ";
16
}
17
std::cout << std::endl;
18
19
v.erase(it, v.end());
20
21
std::cout << "真正移除奇数后的向量: ";
22
for (int x : v) std::cout << x << " ";
23
std::cout << std::endl;
24
25
return 0;
26
}
⑤ 注释:
- 与 std::remove 类似，但移除的是使谓词 pred 返回 true 的元素。
- 同样需要与 erase() 结合使用来真正删除元素。
- 时间复杂度为 O(N)。
⑥ 最佳实践:
- 用于根据条件移除序列中的元素。
- 总是与 erase() 结合使用。
⑦ 常见错误用法:
- 谓词函数的逻辑错误。
- 忘记调用 erase()。
⑧ 陷阱:
- 不适用于关联容器。
2.4.14 std::replace
① 名称: std::replace
② 用途: 将指定范围内所有等于给定旧值的元素替换为给定的新值。
③ 原型:
1
template <class ForwardIterator, class T>
2
void replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
int main() {
6
std::vector<int> v = {1, 2, 3, 2, 4, 2, 5};
7
std::replace(v.begin(), v.end(), 2, 10);
8
9
std::cout << "替换后的向量: ";
10
for (int x : v) std::cout << x << " ";
11
std::cout << std::endl;
12
13
return 0;
14
}
⑤ 注释:
- 将范围 [first, last) 中所有等于 old_value 的元素替换为 new_value。
- 时间复杂度为 O(N)。
⑥ 最佳实践:
- 用于批量替换序列中的特定值。
⑦ 常见错误用法:
- 无。
⑧ 陷阱:
- 无。
2.4.15 std::replace_if
① 名称: std::replace_if
② 用途: 将指定范围内所有满足给定谓词的元素替换为给定的新值。
③ 原型:
1
template <class ForwardIterator, class Predicate, class T>
2
void replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, const T& new_value);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
bool is_negative(int n) {
6
return n < 0;
7
}
8
9
int main() {
10
std::vector<int> v = {1, -2, 3, -4, 5};
11
std::replace_if(v.begin(), v.end(), is_negative, 0);
12
13
std::cout << "替换后的向量 (负数替换为 0): ";
14
for (int x : v) std::cout << x << " ";
15
std::cout << std::endl;
16
17
return 0;
18
}
⑤ 注释:
- 将范围 [first, last) 中所有使谓词 pred 返回 true 的元素替换为 new_value。
- 时间复杂度为 O(N)。
⑥ 最佳实践:
- 用于根据条件批量替换序列中的元素。
⑦ 常见错误用法:
- 谓词函数的逻辑错误。
⑧ 陷阱:
- 无。
2.4.16 std::swap
① 名称: std::swap
② 用途: 交换两个对象的值。
③ 原型:
1
template <class T>
2
void swap(T& a, T& b);
④ 代码:
1
#include <iostream>
2
#include <algorithm>
3
4
int main() {
5
int a = 10, b = 20;
6
std::cout << "交换前: a = " << a << ", b = " << b << std::endl;
7
std::swap(a, b);
8
std::cout << "交换后: a = " << a << ", b = " << b << std::endl;
9
10
return 0;
11
}
⑤ 注释:
- 交换 a 和 b 的值。
- 通常通过调用类型的移动构造函数和移动赋值运算符来实现，如果可用的话，否则使用拷贝。
- 时间复杂度通常为 O(1)。
⑥ 最佳实践:
- 用于交换变量或容器中的元素。
⑦ 常见错误用法:
- 无。
⑧ 陷阱:
- 确保 a 和 b 是相同类型的对象。
2.4.17 std::iter_swap
① 名称: std::iter_swap
② 用途: 交换两个迭代器所指向的元素的值。
③ 原型:
1
template <class ForwardIterator1, class ForwardIterator2>
2
void iter_swap(ForwardIterator1 a, ForwardIterator2 b);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
int main() {
6
std::vector<int> v = {1, 2, 3, 4, 5};
7
auto it1 = v.begin() + 1;
8
auto it2 = v.begin() + 3;
9
10
std::cout << "交换前: v[" << std::distance(v.begin(), it1) << "] = " << *it1
11
<< ", v[" << std::distance(v.begin(), it2) << "] = " << *it2 << std::endl;
12
13
std::iter_swap(it1, it2);
14
15
std::cout << "交换后: v[" << std::distance(v.begin(), it1) << "] = " << *it1
16
<< ", v[" << std::distance(v.begin(), it2) << "] = " << *it2 << std::endl;
17
18
return 0;
19
}
⑤ 注释:
- 交换迭代器 a 和 b 所指向的元素的值。
- 时间复杂度通常为 O(1)。
⑥ 最佳实践:
- 用于在容器中交换元素，尤其是在使用迭代器进行操作时。
⑦ 常见错误用法:
- 传递无效的迭代器。
⑧ 陷阱:
- 确保迭代器指向有效的元素。
2.4.18 std::reverse
① 名称: std::reverse
② 用途: 反转指定范围内的元素顺序。
③ 原型:
1
template <class BidirectionalIterator>
2
void reverse(BidirectionalIterator first, BidirectionalIterator last);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
int main() {
6
std::vector<int> v = {1, 2, 3, 4, 5};
7
std::reverse(v.begin(), v.end());
8
9
std::cout << "反转后的向量: ";
10
for (int x : v) std::cout << x << " ";
11
std::cout << std::endl;
12
13
return 0;
14
}
⑤ 注释:
- 反转范围 [first, last) 中元素的顺序。
- 要求迭代器是双向迭代器。
- 时间复杂度为 O(N)。
⑥ 最佳实践:
- 用于反转序列的顺序。
⑦ 常见错误用法:
- 传递不支持双向迭代器的迭代器（例如，来自 std::forward_list）。
⑧ 陷阱:
- 无。
2.4.19 std::reverse_copy
① 名称: std::reverse_copy
② 用途: 将指定范围内的元素反转后复制到另一个范围。
③ 原型:
1
template <class BidirectionalIterator, class OutputIterator>
2
OutputIterator reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
int main() {
6
std::vector<int> source = {1, 2, 3, 4, 5};
7
std::vector<int> destination(source.size());
8
9
std::reverse_copy(source.begin(), source.end(), destination.begin());
10
11
std::cout << "反转复制后的目标向量: ";
12
for (int x : destination) std::cout << x << " ";
13
std::cout << std::endl;
14
15
return 0;
16
}
⑤ 注释:
- 将范围 [first, last) 中的元素反转后复制到以 result 开头的范围。
- 要求输入迭代器是双向迭代器。
- 返回一个指向目标范围中最后一个写入元素的下一个位置的迭代器。
- 目标范围必须有足够的空间。
- 时间复杂度为 O(N)。
⑥ 最佳实践:
- 用于在不修改原始序列的情况下获取反转后的副本。
⑦ 常见错误用法:
- 目标范围大小不足。
- 输入迭代器不支持双向迭代。
⑧ 陷阱:
- 无。
2.4.20 std::rotate
① 名称: std::rotate
② 用途: 将指定范围内的元素循环左移，使得 middle 指向的元素成为新的第一个元素。
③ 原型:
1
template <class ForwardIterator>
2
ForwardIterator rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
int main() {
6
std::vector<int> v = {1, 2, 3, 4, 5};
7
auto it = std::rotate(v.begin(), v.begin() + 2, v.end());
8
9
std::cout << "旋转后的向量: ";
10
for (int x : v) std::cout << x << " ";
11
std::cout << std::endl;
12
std::cout << "返回的迭代器指向原来第一个元素的位置: " << *it << std::endl;
13
14
return 0;
15
}
⑤ 注释:
- 将范围 [first, last) 中的元素循环左移，直到 middle 指向的元素成为新的 first。
- 返回一个迭代器，指向原来第一个元素的位置。
- 要求迭代器是前向迭代器。
- 时间复杂度为 O(N)。
⑥ 最佳实践:
- 用于循环移动序列中的元素。
⑦ 常见错误用法:
- middle 超出 [first, last] 的范围。
⑧ 陷阱:
- 无。
2.4.21 std::rotate_copy
① 名称: std::rotate_copy
② 用途: 将指定范围内的元素循环左移后复制到另一个范围。
③ 原型:
1
template <class ForwardIterator, class OutputIterator>
2
OutputIterator rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
int main() {
6
std::vector<int> source = {1, 2, 3, 4, 5};
7
std::vector<int> destination(source.size());
8
9
std::rotate_copy(source.begin(), source.begin() + 2, source.end(), destination.begin());
10
11
std::cout << "旋转复制后的目标向量: ";
12
for (int x : destination) std::cout << x << " ";
13
std::cout << std::endl;
14
15
return 0;
16
}
⑤ 注释:
- 将范围 [first, last) 中的元素循环左移（以 middle 为新的开始）后复制到以 result 开头的范围。
- 要求输入迭代器是前向迭代器。
- 返回一个指向目标范围中最后一个写入元素的下一个位置的迭代器。
- 目标范围必须有足够的空间。
- 时间复杂度为 O(N)。
⑥ 最佳实践:
- 用于在不修改原始序列的情况下获取旋转后的副本。
⑦ 常见错误用法:
- middle 超出 [first, last] 的范围。
- 目标范围大小不足。
⑧ 陷阱:
- 无。
2.4.22 std::random_shuffle (C++11 已弃用，建议使用 std::shuffle)
① 名称: std::random_shuffle
② 用途: 随机打乱指定范围内的元素顺序。
③ 原型:
1
template <class RandomAccessIterator>
2
void random_shuffle(RandomAccessIterator first, RandomAccessIterator last);
3
4
template <class RandomAccessIterator, class RandomNumberGenerator>
5
void random_shuffle(RandomAccessIterator first, RandomAccessIterator last, RandomNumberGenerator& rand);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
#include <random>
5
6
int main() {
7
std::vector<int> v = {1, 2, 3, 4, 5};
8
std::random_device rd;
9
std::mt19937 gen(rd());
10
std::shuffle(v.begin(), v.end(), gen);
11
12
std::cout << "随机打乱后的向量: ";
13
for (int x : v) std::cout << x << " ";
14
std::cout << std::endl;
15
16
return 0;
17
}
⑤ 注释:
- 第一个版本使用默认的随机数生成器，其质量可能不高。
- 第二个版本允许提供自定义的随机数生成器。
- 注意: std::random_shuffle 在 C++11 中已被弃用，建议使用 std::shuffle。
- 要求迭代器是随机访问迭代器。
- 时间复杂度通常为 O(N)。
⑥ 最佳实践:
- 使用 std::shuffle 和高质量的随机数生成器（如 std::mt19937）来获得更好的随机性。
⑦ 常见错误用法:
- 在 C++11 及更高版本中使用 std::random_shuffle。
⑧ 陷阱:
- 默认的随机数生成器可能不适合安全或统计要求较高的应用。
2.4.23 std::shuffle
① 名称: std::shuffle
② 用途: 使用指定的随机数生成器随机打乱指定范围内的元素顺序。
③ 原型:
1
template <class RandomAccessIterator, class UniformRandomBitGenerator>
2
void shuffle(RandomAccessIterator first, RandomAccessIterator last, UniformRandomBitGenerator& g);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
#include <random>
5
6
int main() {
7
std::vector<int> v = {1, 2, 3, 4, 5};
8
std::random_device rd;
9
std::mt19937 gen(rd());
10
std::shuffle(v.begin(), v.end(), gen);
11
12
std::cout << "随机打乱后的向量: ";
13
for (int x : v) std::cout << x << " ";
14
std::cout << std::endl;
15
16
return 0;
17
}
⑤ 注释:
- 使用提供的均匀随机位生成器 g 来打乱范围 [first, last) 中的元素。
- 要求迭代器是随机访问迭代器。
- 时间复杂度通常为 O(N)。
⑥ 最佳实践:
- 使用高质量的随机数生成器（如 std::mt19937）来获得良好的随机性。
⑦ 常见错误用法:
- 使用低质量的随机数生成器。
⑧ 陷阱:
- 确保随机数生成器已正确初始化。
2.4.24 std::sample (C++17)
① 名称: std::sample
② 用途: 从输入范围中随机选择指定数量的元素，并将它们复制到输出范围。
③ 原型:
1
template <class InputIterator, class OutputIterator, class Size, class UniformRandomBitGenerator>
2
OutputIterator sample(InputIterator first, InputIterator last,
3
OutputIterator out, Size n,
4
UniformRandomBitGenerator& g);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
#include <random>
5
6
int main() {
7
std::vector<int> population = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
8
std::vector<int> sample(5);
9
std::random_device rd;
10
std::mt19937 gen(rd());
11
12
std::sample(population.begin(), population.end(), sample.begin(), sample.size(), gen);
13
14
std::cout << "从 population 中随机抽取的 5 个元素: ";
15
for (int x : sample) std::cout << x << " ";
16
std::cout << std::endl;
17
18
return 0;
19
}
⑤ 注释:
- 从范围 [first, last) 中随机选择 n 个元素，并将它们复制到以 out 开头的范围。
- 如果 n 大于输入范围的大小，则复制所有元素。
- 使用提供的均匀随机位生成器 g 进行选择。
- 返回一个指向输出范围中最后一个写入元素的下一个位置的迭代器。
- 要求输入迭代器是前向迭代器，输出迭代器是输出迭代器。
- 时间复杂度取决于实现，通常与输入范围的大小成线性关系。
⑥ 最佳实践:
- 用于从大型数据集中随机抽取样本。
⑦ 常见错误用法:
- 输出范围大小不足。
- 使用低质量的随机数生成器。
⑧ 陷阱:
- 确保随机数生成器已正确初始化。
2.4.25 std::unique
① 名称: std::unique
② 用途: 从指定范围中移除相邻的重复元素（实际上是将重复元素移动到范围的末尾）。
③ 原型:
1
template <class ForwardIterator>
2
ForwardIterator unique(ForwardIterator first, ForwardIterator last);
3
4
template <class ForwardIterator, class BinaryPredicate>
5
ForwardIterator unique(ForwardIterator first, ForwardIterator last, BinaryPredicate binary_pred);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
int main() {
6
std::vector<int> v1 = {1, 2, 2, 3, 3, 3, 4, 4, 5};
7
auto it1 = std::unique(v1.begin(), v1.end());
8
std::cout << "去除相邻重复元素后的 v1: ";
9
for (auto i = v1.begin(); i != it1; ++i) std::cout << *i << " ";
10
std::cout << std::endl;
11
v1.erase(it1, v1.end());
12
std::cout << "真正去除相邻重复元素后的 v1: ";
13
for (int x : v1) std::cout << x << " ";
14
std::cout << std::endl;
15
16
std::vector<int> v2 = {1, 2, 2, 3, 3, 1, 1, 5};
17
std::sort(v2.begin(), v2.end()); // 先排序以将所有重复元素相邻
18
auto it2 = std::unique(v2.begin(), v2.end());
19
std::cout << "排序并去除相邻重复元素后的 v2: ";
20
for (auto i = v2.begin(); i != it2; ++i) std::cout << *i << " ";
21
std::cout << std::endl;
22
v2.erase(it2, v2.end());
23
std::cout << "真正去除相邻重复元素后的 v2: ";
24
for (int x : v2) std::cout << x << " ";
25
std::cout << std::endl;
26
27
return 0;
28
}
⑤ 注释:
- 第一个版本使用 == 运算符比较相邻元素。
- 第二个版本使用自定义的二元谓词 binary_pred 来比较相邻元素。
- 返回一个指向逻辑上移除的重复元素之后的新末尾的迭代器。
- 与 std::remove 类似，std::unique 并不改变容器的大小，需要与 erase() 结合使用。
- 重要: std::unique 只移除相邻的重复元素。要移除所有重复元素，需要先对序列进行排序。
- 时间复杂度为 O(N)。
⑥ 最佳实践:
- 用于去除序列中的相邻重复项。
- 通常在排序后使用以去除所有重复项。
- 总是与 erase() 结合使用。
⑦ 常见错误用法:
- 忘记先排序就使用 std::unique 来去除所有重复项。
- 忘记调用 erase()。
⑧ 陷阱:
- 只处理相邻的重复元素。
2.4.26 std::unique_copy
① 名称: std::unique_copy
② 用途: 将指定范围内的元素复制到另一个范围，同时移除相邻的重复元素。
③ 原型:
1
template <class InputIterator, class OutputIterator>
2
OutputIterator unique_copy(InputIterator first, InputIterator last, OutputIterator result);
3
4
template <class InputIterator, class OutputIterator, class BinaryPredicate>
5
OutputIterator unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate binary_pred);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
int main() {
6
std::vector<int> source = {1, 2, 2, 3, 3, 3, 4, 5};
7
std::vector<int> destination;
8
9
std::unique_copy(source.begin(), source.end(), std::back_inserter(destination));
10
11
std::cout << "去除相邻重复元素并复制后的目标向量: ";
12
for (int x : destination) std::cout << x << " ";
13
std::cout << std::endl;
14
15
std::vector<int> source2 = {1, 2, 3, 2, 4, 1, 5};
16
std::vector<int> destination2;
17
std::sort(source2.begin(), source2.end());
18
std::unique_copy(source2.begin(), source2.end(), std::back_inserter(destination2));
19
std::cout << "排序并去除相邻重复元素后复制的目标向量: ";
20
for (int x : destination2) std::cout << x << " ";
21
std::cout << std::endl;
22
23
return 0;
24
}
⑤ 注释:
- 第一个版本使用 == 运算符比较相邻元素。
- 第二个版本使用自定义的二元谓词 binary_pred 来比较相邻元素。
- 将范围 [first, last) 中不相邻的重复元素复制到以 result 开头的范围。
- 返回一个指向目标范围中最后一个写入元素的下一个位置的迭代器。
- 目标范围需要有足够的空间。
- 重要: 与 std::unique 类似，只处理相邻的重复元素。
- 时间复杂度为 O(N)。
⑥ 最佳实践:
- 用于在复制序列的同时去除相邻重复项。
- 通常在排序后使用以去除所有重复项并复制结果。
⑦ 常见错误用法:
- 忘记先排序就使用 std::unique_copy 来去除所有重复项。
- 目标范围大小不足。
⑧ 陷阱:
- 只处理相邻的重复元素。
2.5 划分操作 🔪
2.5.1 std::partition
① 名称: std::partition
② 用途: 将指定范围内的元素划分为两个子范围：满足给定谓词的元素放在前面，不满足的放在后面。元素的相对顺序可能不被保留。
③ 原型:
1
template <class ForwardIterator, class Predicate>
2
ForwardIterator partition(ForwardIterator first, ForwardIterator last, Predicate pred);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
bool is_even(int n) {
6
return n % 2 == 0;
7
}
8
9
int main() {
10
std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8};
11
auto it = std::partition(v.begin(), v.end(), is_even);
12
13
std::cout << "划分后的向量 (偶数在前): ";
14
for (int x : v) std::cout << x << " ";
15
std::cout << std::endl;
16
std::cout << "指向第一个奇数的迭代器: " << *it << std::endl;
17
18
return 0;
19
}
⑤ 注释:
- 返回一个指向第一个不满足谓词的元素的迭代器，即第二个子范围的开始。
- [first, 返回值) 中的元素满足 pred。
- [返回值, last) 中的元素不满足 pred。
- 元素的相对顺序可能不被保留。
- 时间复杂度为 O(N)。
⑥ 最佳实践:
- 用于将序列中的元素根据某个条件分组。
⑦ 常见错误用法:
- 谓词函数的逻辑错误。
⑧ 陷阱:
- 元素的相对顺序可能改变。
2.5.2 std::stable_partition
① 名称: std::stable_partition
② 用途: 与 std::partition 类似，但保证划分后每个子范围内的元素的相对顺序保持不变。
③ 原型:
1
template <class BidirectionalIterator, class Predicate>
2
BidirectionalIterator stable_partition(BidirectionalIterator first, BidirectionalIterator last, Predicate pred);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
bool is_even(int n) {
6
return n % 2 == 0;
7
}
8
9
int main() {
10
std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8};
11
auto it = std::stable_partition(v.begin(), v.end(), is_even);
12
13
std::cout << "稳定划分后的向量 (偶数在前): ";
14
for (int x : v) std::cout << x << " ";
15
std::cout << std::endl;
16
std::cout << "指向第一个奇数的迭代器: " << *it << std::endl;
17
18
return 0;
19
}
⑤ 注释:
- 与 std::partition 类似，但保证元素的相对顺序。
- 要求迭代器是双向迭代器。
- 时间复杂度通常为 O(N log N) 或 O(N)，取决于可用内存。
⑥ 最佳实践:
- 当需要根据条件分组元素，并且保持原始顺序时使用。
⑦ 常见错误用法:
- 谓词函数的逻辑错误۔
⑧ 陷阱:
- 性能可能比 std::partition 差。
2.5.3 std::is_partitioned
① 名称: std::is_partitioned
② 用途: 检查指定范围内的元素是否已根据给定的谓词划分。
③ 原型:
1
template <class InputIterator, class Predicate>
2
bool is_partitioned(InputIterator first, InputIterator last, Predicate pred);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
bool is_even(int n) {
6
return n % 2 == 0;
7
}
8
9
int main() {
10
std::vector<int> v1 = {2, 4, 6, 1, 3, 5};
11
std::vector<int> v2 = {1, 2, 3, 4, 5, 6};
12
13
if (std::is_partitioned(v1.begin(), v1.end(), is_even)) {
14
std::cout << "v1 已根据 is_even 划分" << std::endl;
15
} else {
16
std::cout << "v1 未根据 is_even 划分" << std::endl;
17
}
18
19
if (std::is_partitioned(v2.begin(), v2.end(), is_even)) {
20
std::cout << "v2 已根据 is_even 划分" << std::endl;
21
} else {
22
std::cout << "v2 未根据 is_even 划分" << std::endl;
23
}
24
25
return 0;
26
}
⑤ 注释:
- 返回 true 如果范围 [first, last) 中的所有满足 pred 的元素都在不满足 pred 的元素之前，否则返回 false。
⑥ 最佳实践:
- 在执行依赖于已划分数据的操作之前进行检查。
⑦ 常见错误用法:
- 谓词函数的逻辑错误۔
⑧ 陷阱:
- 空范围被认为是已划分的。
2.5.4 std::partition_copy
① 名称: std::partition_copy
② 用途: 将输入范围内的元素复制到两个不同的输出范围，一个包含满足谓词的元素，另一个包含不满足谓词的元素。
③ 原型:
1
template <class InputIterator, class OutputIterator1, class OutputIterator2, class Predicate>
2
std::pair<OutputIterator1, OutputIterator2>
3
partition_copy(InputIterator first, InputIterator last,
4
OutputIterator1 out_true, OutputIterator2 out_false, Predicate pred);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
bool is_even(int n) {
6
return n % 2 == 0;
7
}
8
9
int main() {
10
std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8};
11
std::vector<int> evens;
12
std::vector<int> odds;
13
14
std::partition_copy(v.begin(), v.end(), std::back_inserter(evens), std::back_inserter(odds), is_even);
15
16
std::cout << "偶数: ";
17
for (int x : evens) std::cout << x << " ";
18
std::cout << std::endl;
19
std::cout << "奇数: ";
20
for (int x : odds) std::cout << x << " ";
21
std::cout << std::endl;
22
23
return 0;
24
}
⑤ 注释:
- 将 [first, last) 中满足 pred 的元素复制到以 out_true 开头的范围。
- 将 [first, last) 中不满足 pred 的元素复制到以 out_false 开头的范围。
- 返回一个 std::pair，其中 first 指向写入 out_true 的最后一个元素的下一个位置，second 指向写入 out_false 的最后一个元素的下一个位置。
- 时间复杂度为 O(N)。
⑥ 最佳实践:
- 用于将序列中的元素根据条件分离到不同的容器中。
⑦ 常见错误用法:
- 谓词函数的逻辑错误۔
⑧ 陷阱:
- 需要确保输出范围有足够的空间（或者使用插入型迭代器）。
2.5.5 std::partition_point
① 名称: std::partition_point
② 用途: 在已根据给定谓词划分的范围内，找到划分点的迭代器。
③ 原型:
1
template <class ForwardIterator, class Predicate>
2
ForwardIterator partition_point(ForwardIterator first, ForwardIterator last, Predicate pred);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
bool is_even(int n) {
6
return n % 2 == 0;
7
}
8
9
int main() {
10
std::vector<int> v = {2, 4, 6, 1, 3, 5};
11
auto it = std::partition_point(v.begin(), v.end(), is_even);
12
13
std::cout << "划分点指向: " << *it << std::endl;
14
std::cout << "划分点之前的元素 (满足谓词): ";
15
for (auto i = v.begin(); i != it; ++i) std::cout << *i << " ";
16
std::cout << std::endl;
17
std::cout << "划分点之后的元素 (不满足谓词): ";
18
for (auto i = it; i != v.end(); ++i) std::cout << *i << " ";
19
std::cout << std::endl;
20
21
return 0;
22
}
⑤ 注释:
- 返回一个指向第一个不满足谓词的元素的迭代器。
- 前提条件: 范围 [first, last) 必须已根据 pred 划分。
- 时间复杂度为 O(log N) 如果迭代器是随机访问迭代器，否则为 O(N)。
⑥ 最佳实践:
- 用于在已划分的序列中查找两个子范围之间的边界。
⑦ 常见错误用法:
- 在未划分的范围内使用。
- 谓词函数的逻辑错误۔
⑧ 陷阱:
- 如果所有元素都满足谓词，则返回 last。如果所有元素都不满足谓词，则返回 first。
2.6 堆操作 🏗️
2.6.1 std::make_heap
① 名称: std::make_heap
② 用途: 将指定范围内的元素转换为一个最大堆（max-heap）。
③ 原型:
1
template <class RandomAccessIterator>
2
void make_heap(RandomAccessIterator first, RandomAccessIterator last);
3
4
template <class RandomAccessIterator, class Compare>
5
void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
int main() {
6
std::vector<int> v = {1, 5, 3, 2, 4};
7
std::cout << "构建堆之前: ";
8
for (int x : v) std::cout << x << " ";
9
std::cout << std::endl;
10
11
std::make_heap(v.begin(), v.end());
12
13
std::cout << "构建堆之后: ";
14
for (int x : v) std::cout << x << " ";
15
std::cout << std::endl;
16
17
return 0;
18
}
⑤ 注释:
- 第一个版本使用 < 运算符进行比较，创建一个最大堆。
- 第二个版本使用自定义的比较函数 comp。
- 要求迭代器是随机访问迭代器。
- 时间复杂度为 O(N)。
⑥ 最佳实践:
- 用于将现有数据转换为堆结构，以便进行堆排序或优先队列操作。
⑦ 常见错误用法:
- 传递不支持随机访问迭代器的迭代器۔
⑧ 陷阱:
- 堆的内部结构可能与直观的排序不同，但满足堆的性质（父节点的值大于或等于其子节点的值）。
2.6.2 std::push_heap
① 名称: std::push_heap
② 用途: 将堆末尾的元素移动到堆中的正确位置，前提是该元素已添加到堆的末尾。
③ 原型:
1
template <class RandomAccessIterator>
2
void push_heap(RandomAccessIterator first, RandomAccessIterator last);
3
4
template <class RandomAccessIterator, class Compare>
5
void push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
int main() {
6
std::vector<int> v = {1, 5, 3, 2, 4};
7
std::make_heap(v.begin(), v.end());
8
std::cout << "初始堆: ";
9
for (int x : v) std::cout << x << " ";
10
std::cout << std::endl;
11
12
v.push_back(6);
13
std::push_heap(v.begin(), v.end());
14
15
std::cout << "添加元素后的堆: ";
16
for (int x : v) std::cout << x << " ";
17
std::cout << std::endl;
18
19
return 0;
20
}
⑤ 注释:
- 在调用 push_heap 之前，必须先使用 push_back（或其他方式）将新元素添加到堆的末尾。
- 要求迭代器是随机访问迭代器。
- 时间复杂度为 O(log N)。
⑥ 最佳实践:
- 用于向已有的堆中添加元素。
⑦ 常见错误用法:
- 在调用 push_heap 之前没有将新元素添加到堆的末尾۔
⑧ 陷阱:
- [first, last - 1) 必须是一个有效的堆。
2.6.3 std::pop_heap
① 名称: std::pop_heap
② 用途: 将堆顶（最大）元素移动到堆的末尾，并维护剩余元素的堆性质。
③ 原型:
1
template <class RandomAccessIterator>
2
void pop_heap(RandomAccessIterator first, RandomAccessIterator last);
3
4
template <class RandomAccessIterator, class Compare>
5
void pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
int main() {
6
std::vector<int> v = {5, 4, 3, 2, 1};
7
std::make_heap(v.begin(), v.end());
8
std::cout << "初始堆: ";
9
for (int x : v) std::cout << x << " ";
10
std::cout << std::endl;
11
12
std::pop_heap(v.begin(), v.end());
13
std::cout << "弹出堆顶后的堆: ";
14
for (int x : v) std::cout << x << " ";
15
std::cout << std::endl;
16
std::cout << "弹出的元素在末尾: " << v.back() << std::endl;
17
v.pop_back(); // 真正移除堆顶元素
18
19
return 0;
20
}
⑤ 注释:
- 在调用 pop_heap 之后，可以使用 pop_back 从容器中真正移除堆顶元素。
- 要求迭代器是随机访问迭代器。
- 时间复杂度为 O(log N)。
⑥ 最佳实践:
- 用于从堆中移除最大元素。
- 通常与 pop_back 结合使用。
⑦ 常见错误用法:
- 在调用 pop_heap 之后忘记调用 pop_back。
⑧ 陷阱:
- [first, last) 必须是一个有效的堆。
2.6.4 std::sort_heap
① 名称: std::sort_heap
② 用途: 将一个最大堆转换为一个已排序的范围（升序）。
③ 原型:
1
template <class RandomAccessIterator>
2
void sort_heap(RandomAccessIterator first, RandomAccessIterator last);
3
4
template <class RandomAccessIterator, class Compare>
5
void sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
int main() {
6
std::vector<int> v = {5, 4, 3, 2, 1};
7
std::make_heap(v.begin(), v.end());
8
std::cout << "初始堆: ";
9
for (int x : v) std::cout << x << " ";
10
std::cout << std::endl;
11
12
std::sort_heap(v.begin(), v.end());
13
14
std::cout << "排序后的堆: ";
15
for (int x : v) std::cout << x << " ";
16
std::cout << std::endl;
17
18
return 0;
19
}
⑤ 注释:
- 调用 sort_heap 后，原来的堆不再是一个有效的堆。
- 要求迭代器是随机访问迭代器。
- 时间复杂度为 O(N log N)。
⑥ 最佳实践:
- 用于对已有的堆进行排序。
⑦ 常见错误用法:
- 在未构建为堆的范围上调用 sort_heap。
⑧ 陷阱:
- 排序后，原来的堆结构会丢失。
2.6.5 std::is_heap
① 名称: std::is_heap
② 用途: 检查指定范围内的元素是否构成一个最大堆。
③ 原型:
1
template <class RandomAccessIterator>
2
bool is_heap(RandomAccessIterator first, RandomAccessIterator last);
3
4
template <class RandomAccessIterator, class Compare>
5
bool is_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
int main() {
6
std::vector<int> v1 = {5, 3, 4, 1, 2};
7
std::cout << "v1 是否是堆: " << std::is_heap(v1.begin(), v1.end()) << std::endl;
8
9
std::make_heap(v1.begin(), v1.end());
10
std::cout << "v1 构建堆后是否是堆: " << std::is_heap(v1.begin(), v1.end()) << std::endl;
11
12
return 0;
13
}
⑤ 注释:
- 返回 true 如果范围 [first, last) 中的元素构成一个最大堆，否则返回 false。
- 要求迭代器是随机访问迭代器。
⑥ 最佳实践:
- 用于验证一个范围是否满足堆的性质。
⑦ 常见错误用法:
- 传递不支持随机访问迭代器的迭代器۔
⑧ 陷阱:
- 空范围被认为是堆。
2.6.6 std::is_heap_until
① 名称: std::is_heap_until
② 用途: 找到指定范围内第一个破坏堆性质的元素。
③ 原型:
1
template <class RandomAccessIterator>
2
RandomAccessIterator is_heap_until(RandomAccessIterator first, RandomAccessIterator last);
3
4
template <class RandomAccessIterator, class Compare>
5
RandomAccessIterator is_heap_until(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
int main() {
6
std::vector<int> v = {5, 3, 4, 1, 2, 6};
7
auto it = std::is_heap_until(v.begin(), v.end());
8
9
if (it == v.end()) {
10
std::cout << "向量是堆" << std::endl;
11
} else {
12
std::cout << "向量直到元素 " << *it << " (索引 " << std::distance(v.begin(), it) << ") 是堆" << std::endl;
13
}
14
15
return 0;
16
}
⑤ 注释:
- 返回一个指向范围内第一个破坏堆性质的元素的迭代器。
- 如果整个范围都是堆，则返回 last。
- 要求迭代器是随机访问迭代器。
⑥ 最佳实践:
- 用于确定一个范围中作为堆的前缀的长度。
⑦ 常见错误用法:
- 传递不支持随机访问迭代器的迭代器۔
⑧ 陷阱:
- 空范围返回 first (等于 last)。
2.7 最小值和最大值操作 ⛰️
2.7.1 std::min
① 名称: std::min
② 用途: 返回两个值中的较小者。
③ 原型:
1
template <class T> const T& min(const T& a, const T& b);
2
template <class T, class Compare> const T& min(const T& a, const T& b, Compare comp);
3
template <class T> T min(std::initializer_list<T> il);
4
template <class T, class Compare> T min(std::initializer_list<T> il, Compare comp);
④ 代码:
1
#include <iostream>
2
#include <algorithm>
3
#include <vector>
4
5
int main() {
6
int a = 10, b = 20;
7
std::cout << "min(a, b) = " << std::min(a, b) << std::endl;
8
9
std::vector<int> v = {5, 2, 8, 1, 9};
10
std::cout << "min({5, 2, 8, 1, 9}) = " << std::min({5, 2, 8, 1, 9}) << std::endl;
11
12
return 0;
13
}
⑤ 注释:
- 第一个版本使用 < 运算符进行比较。
- 第二个版本使用自定义的比较函数 comp。
- 后两个版本接受一个 std::initializer_list。
- 如果两个值相等，返回第一个值。
⑥ 最佳实践:
- 用于获取两个或多个值中的最小值。
⑦ 常见错误用法:
- 无۔
⑧ 陷阱:
- 确保比较操作满足严格弱序关系。
2.7.2 std::max
① 名称: std::max
② 用途: 返回两个值中的较大者。
③ 原型:
1
template <class T> const T& max(const T& a, const T& b);
2
template <class T, class Compare> const T& max(const T& a, const T& b, Compare comp);
3
template <class T> T max(std::initializer_list<T> il);
4
template <class T, class Compare> T max(std::initializer_list<T> il, Compare comp);
④ 代码:
1
#include <iostream>
2
#include <algorithm>
3
#include <vector>
4
5
int main() {
6
int a = 10, b = 20;
7
std::cout << "max(a, b) = " << std::max(a, b) << std::endl;
8
9
std::vector<int> v = {5, 2, 8, 1, 9};
10
std::cout << "max({5, 2, 8, 1, 9}) = " << std::max({5, 2, 8, 1, 9}) << std::endl;
11
12
return 0;
13
}
⑤ 注释:
- 第一个版本使用 < 运算符进行比较。
- 第二个版本使用自定义的比较函数 comp。
- 后两个版本接受一个 std::initializer_list。
- 如果两个值相等，返回第一个值。
⑥ 最佳实践:
- 用于获取两个或多个值中的最大值۔
⑦ 常见错误用法:
- 无۔
⑧ 陷阱:
- 确保比较操作满足严格弱序关系.
2.7.3 std::minmax
① 名称: std::minmax
② 用途: 返回两个值中的最小值和最大值。
③ 原型:
1
template <class T> std::pair<const T&, const T&> minmax(const T& a, const T& b);
2
template <class T, class Compare> std::pair<const T&, const T&> minmax(const T& a, const T& b, Compare comp);
3
template <class T> std::pair<T, T> minmax(std::initializer_list<T> il);
4
template <class T, class Compare> std::pair<T, T> minmax(std::initializer_list<T> il, Compare comp);
④ 代码:
1
#include <iostream>
2
#include <algorithm>
3
#include <vector>
4
5
int main() {
6
int a = 10, b = 20;
7
auto result1 = std::minmax(a, b);
8
std::cout << "minmax(a, b) = {" << result1.first << ", " << result1.second << "}" << std::endl;
9
10
std::vector<int> v = {5, 2, 8, 1, 9};
11
auto result2 = std::minmax({5, 2, 8, 1, 9});
12
std::cout << "minmax({5, 2, 8, 1, 9}) = {" << result2.first << ", " << result2.second << "}" << std::endl;
13
14
return 0;
15
}
⑤ 注释:
- 返回一个 std::pair，其中 first 是最小值，second 是最大值۔
- 第一个版本使用 < 运算符进行比较۔
- 第二个版本使用自定义的比较函数 comp۔
- 后两个版本接受一个 std::initializer_list۔
⑥ 最佳实践:
- 用于同时获取最小值和最大值，通常比分别调用 std::min 和 std::max 更高效۔
⑦ 常见错误用法:
- 无۔
⑧ 陷阱:
- 确保比较操作满足严格弱序关系.
2.7.4 std::min_element
① 名称: std::min_element
② 用途: 返回指向指定范围内最小元素的迭代器۔
③ 原型:
1
template <class ForwardIterator>
2
ForwardIterator min_element(ForwardIterator first, ForwardIterator last);
3
4
template <class ForwardIterator, class Compare>
5
ForwardIterator min_element(ForwardIterator first, ForwardIterator last, Compare comp);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
int main() {
6
std::vector<int> v = {5, 2, 8, 1, 9};
7
auto it = std::min_element(v.begin(), v.end());
8
9
if (it != v.end()) {
10
std::cout << "最小元素是: " << *it << "，索引是: " << std::distance(v.begin(), it) << std::endl;
11
}
12
13
return 0;
14
}
⑤ 注释:
- 第一个版本使用 < 运算符进行比较۔
- 第二个版本使用自定义的比较函数 comp۔
- 如果范围内有多个最小元素，返回指向第一个出现的最小元素的迭代器۔
- 如果范围为空，返回 last۔
- 时间复杂度为 O(N)۔
⑥ 最佳实践:
- 用于查找序列中的最小元素۔
⑦ 常见错误用法:
- 在空范围上解引用返回的迭代器۔
⑧ 陷阱:
- 确保比较操作满足严格弱序关系.
2.7.5 std::max_element
① 名称: std::max_element
② 用途: 返回指向指定范围内最大元素的迭代器۔
③ 原型:
1
template <class ForwardIterator>
2
ForwardIterator max_element(ForwardIterator first, ForwardIterator last);
3
4
template <class ForwardIterator, class Compare>
5
ForwardIterator max_element(ForwardIterator first, ForwardIterator last, Compare comp);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
int main() {
6
std::vector<int> v = {5, 2, 8, 1, 9};
7
auto it = std::max_element(v.begin(), v.end());
8
9
if (it != v.end()) {
10
std::cout << "最大元素是: " << *it << "，索引是: " << std::distance(v.begin(), it) << std::endl;
11
}
12
13
return 0;
14
}
⑤ 注释:
- 第一个版本使用 < 运算符进行比较۔
- 第二个版本使用自定义的比较函数 comp۔
- 如果范围内有多个最大元素，返回指向第一个出现的最大元素的迭代器۔
- 如果范围为空，返回 last۔
- 时间复杂度为 O(N)۔
⑥ 最佳实践:
- 用于查找序列中的最大元素۔
⑦ 常见错误用法:
- 在空范围上解引用返回的迭代器۔
⑧ 陷阱:
- 确保比较操作满足严格弱序关系.
2.7.6 std::minmax_element
① 名称: std::minmax_element
② 用途: 返回一个包含指向指定范围内最小和最大元素的迭代器的 std::pair۔
③ 原型:
1
template <class ForwardIterator>
2
std::pair<ForwardIterator, ForwardIterator>
3
minmax_element(ForwardIterator first, ForwardIterator last);
4
5
template <class ForwardIterator, class Compare>
6
std::pair<ForwardIterator, ForwardIterator>
7
minmax_element(ForwardIterator first, ForwardIterator last, Compare comp);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
int main() {
6
std::vector<int> v = {5, 2, 8, 1, 9};
7
auto result = std::minmax_element(v.begin(), v.end());
8
9
if (result.first != v.end() && result.second != v.end()) {
10
std::cout << "最小元素是: " << *result.first << "，索引是: " << std::distance(v.begin(), result.first) << std::endl;
11
std::cout << "最大元素是: " << *result.second << "，索引是: " << std::distance(v.begin(), result.second) << std::endl;
12
}
13
14
return 0;
15
}
⑤ 注释:
- 返回一个 std::pair，其中 first 是指向最小元素的迭代器，second 是指向最大元素的迭代器۔
- 第一个版本使用 < 运算符进行比较۔
- 第二个版本使用自定义的比较函数 comp۔
- 如果范围内有多个最小或最大元素，返回指向第一个出现的迭代器۔
- 如果范围为空，返回 (last, last)۔
- 时间复杂度为 O(N)۔
⑥ 最佳实践:
- 用于同时查找序列中的最小和最大元素，通常比分别调用 std::min_element 和 std::max_element 更高效۔
⑦ 常见错误用法:
- 在空范围上解引用返回的迭代器۔
⑧ 陷阱:
- 确保比较操作满足严格弱序关系.
2.8 比较操作 ⚖️
2.8.1 std::equal
① 名称: std::equal
② 用途: 比较两个范围内的元素是否相等。
③ 原型:
1
template <class InputIterator1, class InputIterator2>
2
bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);
3
4
template <class InputIterator1, class InputIterator2, class BinaryPredicate>
5
bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, BinaryPredicate binary_pred);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
int main() {
6
std::vector<int> v1 = {1, 2, 3, 4, 5};
7
std::vector<int> v2 = {1, 2, 3, 4, 5};
8
std::vector<int> v3 = {1, 2, 3};
9
10
if (std::equal(v1.begin(), v1.end(), v2.begin())) {
11
std::cout << "v1 和 v2 相等" << std::endl;
12
} else {
13
std::cout << "v1 和 v2 不相等" << std::endl;
14
}
15
16
if (std::equal(v1.begin(), v3.end(), v3.begin())) {
17
std::cout << "v1 的前 3 个元素和 v3 相等" << std::endl;
18
} else {
19
std::cout << "v1 的前 3 个元素和 v3 不相等" << std::endl;
20
}
21
22
return 0;
23
}
⑤ 注释:
- 第一个版本使用 == 运算符比较元素۔
- 第二个版本使用自定义的二元谓词 binary_pred 进行比较۔
- 如果第一个范围 [first1, last1) 中的每个元素都等于从 first2 开始的第二个范围中的对应元素，则返回 true۔
- 第二个范围必须至少与第一个范围一样长۔
- 时间复杂度为 O(N)，其中 N 是第一个范围的大小۔
⑥ 最佳实践:
- 用于比较两个序列是否相同۔
⑦ 常见错误用法:
- 假设第二个范围的大小与第一个范围相同，但实际并非如此۔
⑧ 陷阱:
- 如果第一个范围比第二个范围长，行为是未定义的。
2.8.2 std::mismatch
① 名称: std::mismatch
② 用途: 查找两个范围中第一个不匹配的元素对۔
③ 原型:
1
template <class InputIterator1, class InputIterator2>
2
std::pair<InputIterator1, InputIterator2>
3
mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);
4
5
template <class InputIterator1, class InputIterator2, class BinaryPredicate>
6
std::pair<InputIterator1, InputIterator2>
7
mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, BinaryPredicate binary_pred);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
int main() {
6
std::vector<int> v1 = {1, 2, 3, 4, 5};
7
std::vector<int> v2 = {1, 2, 8, 4, 5};
8
auto result = std::mismatch(v1.begin(), v1.end(), v2.begin());
9
10
if (result.first == v1.end()) {
11
std::cout << "两个向量完全匹配" << std::endl;
12
} else {
13
std::cout << "第一个不匹配的元素在 v1 中的索引是: " << std::distance(v1.begin(), result.first)
14
<< "，值为: " << *result.first << std::endl;
15
std::cout << "第一个不匹配的元素在 v2 中的索引是: " << std::distance(v2.begin(), result.second)
16
<< "，值为: " << *result.second << std::endl;
17
}
18
19
return 0;
20
}
⑤ 注释:
- 第一个版本使用 == 运算符比较元素۔
- 第二个版本使用自定义的二元谓词 binary_pred 进行比较۔
- 返回一个 std::pair，其中 first 是指向第一个范围中不匹配元素的迭代器，second 是指向第二个范围中对应不匹配元素的迭代器۔
- 如果所有元素都匹配，则 first 将等于 last1۔
- 第二个范围必须至少与第一个范围一样长۔
- 时间复杂度为 O(K)，其中 K 是第一个不匹配元素的索引，或者 N（如果所有元素都匹配），N 是第一个范围的大小۔
⑥ 最佳实践:
- 用于查找两个序列中第一个不同的位置۔
⑦ 常见错误用法:
- 假设第二个范围的大小与第一个范围相同，但实际并非如此۔
⑧ 陷阱:
- 如果第一个范围比第二个范围长，行为是未定义的。
2.8.3 std::lexicographical_compare
① 名称: std::lexicographical_compare
② 用途: 按字典顺序比较两个范围内的元素。
③ 原型:
1
template <class InputIterator1, class InputIterator2>
2
bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
3
InputIterator2 first2, InputIterator2 last2);
4
5
template <class InputIterator1, class InputIterator2, class Compare>
6
bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
7
InputIterator2 first2, InputIterator2 last2,
8
Compare comp);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
#include <string>
5
6
int main() {
7
std::vector<int> v1 = {1, 2, 3};
8
std::vector<int> v2 = {1, 2, 4};
9
std::vector<int> v3 = {1, 2};
10
std::string s1 = "apple";
11
std::string s2 = "apply";
12
13
if (std::lexicographical_compare(v1.begin(), v1.end(), v2.begin(), v2.end())) {
14
std::cout << "v1 < v2 (字典顺序)" << std::endl;
15
} else {
16
std::cout << "v1 >= v2 (字典顺序)" << std::endl;
17
}
18
19
if (std::lexicographical_compare(v1.begin(), v1.end(), v3.begin(), v3.end())) {
20
std::cout << "v1 < v3 (字典顺序)" << std::endl;
21
} else {
22
std::cout << "v1 >= v3 (字典顺序)" << std::endl;
23
}
24
25
if (std::lexicographical_compare(s1.begin(), s1.end(), s2.begin(), s2.end())) {
26
std::cout << "s1 < s2 (字典顺序)" << std::endl;
27
} else {
28
std::cout << "s1 >= s2 (字典顺序)" << std::endl;
29
}
30
31
return 0;
32
}
⑤ 注释:
- 第一个版本使用 < 运算符比较元素۔
- 第二个版本使用自定义的比较函数 comp 进行比较۔
- 如果第一个范围按字典顺序小于第二个范围，则返回 true۔
- 字典顺序的比较方式类似于字符串的比较۔
- 时间复杂度为 O(min(N, M))，其中 N 是第一个范围的大小，M 是第二个范围的大小۔
⑥ 最佳实践:
- 用于比较序列的字典顺序، 例如字符串或字符数组۔
⑦ 常见错误用法:
- 无۔
⑧ 陷阱:
- 空范围按字典顺序小于任何非空范围۔ 两个空范围按字典顺序相等.
2.9 集合操作 🧩 (针对已排序的范围)
2.9.1 std::includes
① 名称: std::includes
② 用途: 检查一个已排序的范围是否包含另一个已排序的范围中的所有元素。
③ 原型:
1
template <class InputIterator1, class InputIterator2>
2
bool includes(InputIterator1 first1, InputIterator1 last1,
3
InputIterator2 first2, InputIterator2 last2);
4
5
template <class InputIterator1, class InputIterator2, class Compare>
6
bool includes(InputIterator1 first1, InputIterator1 last1,
7
InputIterator2 first2, InputIterator2 last2, Compare comp);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
int main() {
6
std::vector<int> v1 = {1, 2, 3, 4, 5};
7
std::vector<int> v2 = {2, 4};
8
std::vector<int> v3 = {2, 6};
9
10
if (std::includes(v1.begin(), v1.end(), v2.begin(), v2.end())) {
11
std::cout << "v1 包含 v2" << std::endl;
12
} else {
13
std::cout << "v1 不包含 v2" << std::endl;
14
}
15
16
if (std::includes(v1.begin(), v1.end(), v3.begin(), v3.end())) {
17
std::cout << "v1 包含 v3" << std::endl;
18
} else {
19
std::cout << "v1 不包含 v3" << std::endl;
20
}
21
22
return 0;
23
}
⑤ 注释:
- 第一个版本使用 < 运算符进行比较，假设两个范围都已按升序排序。
- 第二个版本使用自定义的比较函数 comp。
- 返回 true 如果 [first1, last1) 包含 [first2, last2) 中的所有元素，否则返回 false。
- 时间复杂度为 O(N + M)，其中 N 是第一个范围的大小，M 是第二个范围的大小。
⑥ 最佳实践:
- 用于检查一个集合是否是另一个集合的超集。
⑦ 常见错误用法:
- 在未排序的范围上使用。
⑧ 陷阱:
- 如果第二个范围为空，则总是返回 true。
2.9.2 std::set_union
① 名称: std::set_union
② 用途: 计算两个已排序范围的并集，并将结果存储到另一个范围。
③ 原型:
1
template <class InputIterator1, class InputIterator2, class OutputIterator>
2
OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,
3
InputIterator2 first2, InputIterator2 last2,
4
OutputIterator result);
5
6
template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
7
OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,
8
InputIterator2 first2, InputIterator2 last2,
9
OutputIterator result, Compare comp);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
#include <iterator>
5
6
int main() {
7
std::vector<int> v1 = {1, 2, 3, 4, 5};
8
std::vector<int> v2 = {3, 5, 6, 7};
9
std::vector<int> result;
10
11
std::set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(result));
12
13
std::cout << "v1 和 v2 的并集: ";
14
for (int x : result) std::cout << x << " ";
15
std::cout << std::endl;
16
17
return 0;
18
}
⑤ 注释:
- 第一个版本使用 < 运算符进行比较，假设两个范围都已按升序排序。
- 第二个版本使用自定义的比较函数 comp۔
- 将两个输入范围的并集写入到以 result 开头的范围。
- 如果一个元素在两个输入范围中都存在，则在结果中只包含一次。
- 返回一个指向输出范围中最后一个写入元素的下一个位置的迭代器۔
- 时间复杂度为 O(N + M)۔
⑥ 最佳实践:
- 用于计算两个已排序集合的并集۔
⑦ 常见错误用法:
- 在未排序的范围上使用۔
- 输出范围大小不足（通常使用插入型迭代器）。
⑧ 陷阱:
- 结果范围中的元素也是已排序的。
2.9.3 std::set_intersection
① 名称: std::set_intersection
② 用途: 计算两个已排序范围的交集，并将结果存储到另一个范围。
③ 原型:
1
template <class InputIterator1, class InputIterator2, class OutputIterator>
2
OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1,
3
InputIterator2 first2, InputIterator2 last2,
4
OutputIterator result);
5
6
template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
7
OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1,
8
InputIterator2 first2, InputIterator2 last2,
9
OutputIterator result, Compare comp);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
#include <iterator>
5
6
int main() {
7
std::vector<int> v1 = {1, 2, 3, 4, 5};
8
std::vector<int> v2 = {3, 5, 6, 7};
9
std::vector<int> result;
10
11
std::set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(result));
12
13
std::cout << "v1 和 v2 的交集: ";
14
for (int x : result) std::cout << x << " ";
15
std::cout << std::endl;
16
17
return 0;
18
}
⑤ 注释:
- 第一个版本使用 < 运算符进行比较，假设两个范围都已按升序排序。
- 第二个版本使用自定义的比较函数 comp۔
- 将两个输入范围的交集写入到以 result 开头的范围۔
- 返回一个指向输出范围中最后一个写入元素的下一个位置的迭代器۔
- 时间复杂度为 O(N + M)۔
⑥ 最佳实践:
- 用于计算两个已排序集合的交集۔
⑦ 常见错误用法:
- 在未排序的范围上使用۔
- 输出范围大小不足（通常使用插入型迭代器）。
⑧ 陷阱:
- 结果范围中的元素也是已排序的۔
2.9.4 std::set_difference
① 名称: std::set_difference
② 用途: 计算两个已排序范围的差集（第一个范围中存在但第二个范围中不存在的元素），并将结果存储到另一个范围。
③ 原型:
1
template <class InputIterator1, class InputIterator2, class OutputIterator>
2
OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1,
3
InputIterator2 first2, InputIterator2 last2,
4
OutputIterator result);
5
6
template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
7
OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1,
8
InputIterator2 first2, InputIterator2 last2,
9
OutputIterator result, Compare comp);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
#include <iterator>
5
6
int main() {
7
std::vector<int> v1 = {1, 2, 3, 4, 5};
8
std::vector<int> v2 = {3, 5, 6, 7};
9
std::vector<int> result;
10
11
std::set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(result));
12
13
std::cout << "v1 和 v2 的差集 (v1 - v2): ";
14
for (int x : result) std::cout << x << " ";
15
std::cout << std::endl;
16
17
return 0;
18
}
⑤ 注释:
- 第一个版本使用 < 运算符进行比较، 假设两个范围都已按升序排序۔
- 第二个版本使用自定义的比较函数 comp۔
- 将第一个输入范围中存在但第二个输入范围中不存在的元素写入到以 result 开头的范围۔
- 返回一个指向输出范围中最后一个写入元素的下一个位置的迭代器۔
- 时间复杂度为 O(N + M)۔
⑥ 最佳实践:
- 用于计算两个已排序集合的差集۔
⑦ 常见错误用法:
- 在未排序的范围上使用۔
- 输出范围大小不足（通常使用插入型迭代器）。
⑧ 陷阱:
- 结果范围中的元素也是已排序的۔
2.9.5 std::set_symmetric_difference
① 名称: std::set_symmetric_difference
② 用途: 计算两个已排序范围的对称差集（只在一个范围中存在的元素），并将结果存储到另一个范围。
③ 原型:
1
template <class InputIterator1, class InputIterator2, class OutputIterator>
2
OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
3
InputIterator2 first2, InputIterator2 last2,
4
OutputIterator result);
5
6
template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
7
OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
8
InputIterator2 first2, InputIterator2 last2,
9
OutputIterator result, Compare comp);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
#include <iterator>
5
6
int main() {
7
std::vector<int> v1 = {1, 2, 3, 4, 5};
8
std::vector<int> v2 = {3, 5, 6, 7};
9
std::vector<int> result;
10
11
std::set_symmetric_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(result));
12
13
std::cout << "v1 和 v2 的对称差集: ";
14
for (int x : result) std::cout << x << " ";
15
std::cout << std::endl;
16
17
return 0;
18
}
⑤ 注释:
- 第一个版本使用 < 运算符进行比较，假设两个范围都已按升序排序۔
- 第二个版本使用自定义的比较函数 comp۔
- 将只在一个输入范围中存在的元素写入到以 result 开头的范围۔
- 返回一个指向输出范围中最后一个写入元素的下一个位置的迭代器۔
- 时间复杂度为 O(N + M)۔
⑥ 最佳实践:
- 用于计算两个已排序集合的对称差集۔
⑦ 常见错误用法:
- 在未排序的范围上使用۔
- 输出范围大小不足（通常使用插入型迭代器）。
⑧ 陷阱:
- 结果范围中的元素也是已排序的۔
2.10 组合生成器 ⚙️ (针对已排序的范围)
2.10.1 std::merge
① 名称: std::merge
② 用途: 合并两个已排序的范围到一个新的已排序范围。
③ 原型:
1
template <class InputIterator1, class InputIterator2, class OutputIterator>
2
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
3
InputIterator2 first2, InputIterator2 last2,
4
OutputIterator result);
5
6
template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
7
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
8
InputIterator2 first2, InputIterator2 last2,
9
OutputIterator result, Compare comp);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
#include <iterator>
5
6
int main() {
7
std::vector<int> v1 = {1, 3, 5};
8
std::vector<int> v2 = {2, 4, 6};
9
std::vector<int> result;
10
11
std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(result));
12
13
std::cout << "合并后的范围: ";
14
for (int x : result) std::cout << x << " ";
15
std::cout << std::endl;
16
17
return 0;
18
}
⑤ 注释:
- 第一个版本使用 < 运算符进行比较，假设两个输入范围都已按升序排序۔
- 第二个版本使用自定义的比较函数 comp۔
- 将两个输入范围的元素合并到一个以 result 开头的已排序的范围۔
- 如果一个元素在两个输入范围中都存在，则在结果中保留所有副本（保持稳定性）。
- 返回一个指向输出范围中最后一个写入元素的下一个位置的迭代器۔
- 时间复杂度为 O(N + M)۔
⑥ 最佳实践:
- 用于合并两个已排序的序列。
⑦ 常见错误用法:
- 在未排序的范围上使用۔
- 输出范围大小不足（通常使用插入型迭代器）。
⑧ 陷阱:
- 结果范围中的元素也是已排序的。
2.10.2 std::inplace_merge
① 名称: std::inplace_merge
② 用途: 合并同一个序列中两个相邻的已排序子范围。
③ 原型:
1
template <class BidirectionalIterator>
2
void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last);
3
4
template <class BidirectionalIterator, class Compare>
5
void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
int main() {
6
std::vector<int> v = {1, 3, 5, 2, 4, 6};
7
std::sort(v.begin(), v.begin() + 3); // 对前 3 个元素排序
8
std::sort(v.begin() + 3, v.end()); // 对后 3 个元素排序
9
std::cout << "排序后的向量 (两个子范围): ";
10
for (int x : v) std::cout << x << " ";
11
std::cout << std::endl;
12
13
std::inplace_merge(v.begin(), v.begin() + 3, v.end());
14
15
std::cout << "原地合并后的向量: ";
16
for (int x : v) std::cout << x << " ";
17
std::cout << std::endl;
18
19
return 0;
20
}
⑤ 注释:
- 第一个版本使用 < 运算符进行比较，假设 [first, middle) 和 [middle, last) 都是已按升序排序的。
- 第二个版本使用自定义的比较函数 comp۔
- 原地合并这两个子范围，使得整个范围 [first, last) 都是已排序的。
- 要求迭代器是双向迭代器۔
- 时间复杂度通常为 O(N)，但最坏情况下可能是 O(N log N)۔
⑥ 最佳实践:
- 用于在原地合并已排序的相邻子序列。
⑦ 常见错误用法:
- 子范围没有事先排序۔
- 传递不支持双向迭代器的迭代器۔
⑧ 陷阱:
- 无۔
2.11 数值算法 (部分) ➕
2.11.1 std::accumulate (位于 <numeric> 头文件，但常与 <algorithm> 一起使用)
① 名称: std::accumulate
② 用途: 计算指定范围内元素的和（或使用自定义的二元操作）。
③ 原型:
1
template <class InputIterator, class T>
2
T accumulate(InputIterator first, InputIterator last, T init);
3
4
template <class InputIterator, class T, class BinaryOperation>
5
T accumulate(InputIterator first, InputIterator last, T init, BinaryOperation op);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <numeric> // 注意：accumulate 在 <numeric> 中
4
#include <algorithm>
5
6
int main() {
7
std::vector<int> v = {1, 2, 3, 4, 5};
8
int sum = std::accumulate(v.begin(), v.end(), 0);
9
std::cout << "向量元素的和: " << sum << std::endl;
10
11
int product = std::accumulate(v.begin(), v.end(), 1, std::multiplies<int>());
12
std::cout << "向量元素的积: " << product << std::endl;
13
14
return 0;
15
}
⑤ 注释:
- 第一个版本从 init 开始，对范围 [first, last) 中的每个元素执行加法操作。
- 第二个版本使用自定义的二元操作 op 代替加法。
- 返回累积的结果。
- 时间复杂度为 O(N)。
⑥ 最佳实践:
- 用于计算序列的总和、积或其他聚合值۔
⑦ 常见错误用法:
- 初始值 init 的类型与元素类型不兼容，可能导致精度损失或溢出۔
- 自定义二元操作的逻辑错误۔
⑧ 陷阱:
- 空范围的累积结果是初始值 init。
2.12 迭代器操作 (部分) 🚶♂️
2.12.1 std::advance (位于 <iterator> 头文件，但常与 <algorithm> 一起使用)
① 名称: std::advance
② 用途: 将迭代器向前（或向后，对于双向或随机访问迭代器）移动指定的距离。
③ 原型:
1
template <class InputIterator, class Distance>
2
void advance(InputIterator& it, Distance n);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <iterator> // 注意：advance 在 <iterator> 中
4
#include <algorithm>
5
6
int main() {
7
std::vector<int> v = {1, 2, 3, 4, 5};
8
auto it = v.begin();
9
std::advance(it, 3);
10
std::cout << "迭代器指向的元素: " << *it << std::endl;
11
12
std::advance(it, -1); // 对于双向迭代器可以向后移动
13
std::cout << "迭代器向后移动后的元素: " << *it << std::endl;
14
15
return 0;
16
}
⑤ 注释:
- 将迭代器 it 移动 n 个位置。
- 对于输入迭代器和前向迭代器，n 必须是非负的。
- 对于双向迭代器，n 可以是负数。
- 对于随机访问迭代器，操作是常量时间复杂度。对于其他迭代器类型，时间复杂度与移动的距离成线性关系。
⑥ 最佳实践:
- 用于在不知道迭代器类型的情况下移动迭代器。
⑦ 常见错误用法:
- 将迭代器移动到超出其有效范围的位置。
- 尝试向后移动输入迭代器或前向迭代器。
⑧ 陷阱:
- 无。
2.12.2 std::distance (位于 <iterator> 头文件，但常与 <algorithm> 一起使用)
① 名称: std::distance
② 用途: 计算两个迭代器之间的距离。
③ 原型:
1
template <class InputIterator>
2
typename iterator_traits<InputIterator>::difference_type
3
distance(InputIterator first, InputIterator last);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <iterator> // 注意：distance 在 <iterator> 中
4
#include <algorithm>
5
6
int main() {
7
std::vector<int> v = {1, 2, 3, 4, 5};
8
auto it1 = v.begin();
9
auto it2 = v.end();
10
auto dist = std::distance(it1, it2);
11
std::cout << "迭代器之间的距离: " << dist << std::endl;
12
13
auto it3 = v.begin() + 1;
14
auto it4 = v.begin() + 4;
15
auto dist2 = std::distance(it3, it4);
16
std::cout << "迭代器之间的距离: " << dist2 << std::endl;
17
18
return 0;
19
}
⑤ 注释:
- 返回迭代器 first 和 last 之间的距离。
- 对于随机访问迭代器，操作是常量时间复杂度。对于其他迭代器类型，时间复杂度与距离成线性关系。
⑥ 最佳实践:
- 用于获取容器中元素的索引或计算子范围的大小۔
⑦ 常见错误用法:
- 传递的迭代器不属于同一个容器。
⑧ 陷阱:
- last 必须是可以通过从 first 开始重复递增来达到的。
2.13 其他算法 💡
2.13.1 std::for_each
① 名称: std::for_each
② 用途: 对指定范围内的每个元素应用一个函数对象。
③ 原型:
1
template <class InputIterator, class Function>
2
Function for_each(InputIterator first, InputIterator last, Function f);
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
5
void print_element(int n) {
6
std::cout << n << " ";
7
}
8
9
int main() {
10
std::vector<int> v = {1, 2, 3, 4, 5};
11
std::cout << "向量元素: ";
12
std::for_each(v.begin(), v.end(), print_element);
13
std::cout << std::endl;
14
15
int sum = 0;
16
std::for_each(v.begin(), v.end(), [&](int n){ sum += n; });
17
std::cout << "向量元素之和: " << sum << std::endl;
18
19
return 0;
20
}
⑤ 注释:
- 对范围 [first, last) 中的每个元素调用函数对象 f。
- f 可以是一个函数指针、函数对象或 lambda 表达式。
- 返回 f 的副本。
- 时间复杂度为 O(N)。
⑥ 最佳实践:
- 用于对序列中的每个元素执行相同的操作。
⑦ 常见错误用法:
- 尝试在 for_each 中修改容器的结构（例如插入或删除元素），这可能导致未定义的行为۔
⑧ 陷阱:
- 函数对象 f 应该避免副作用，除非明确需要。
2.13.2 std::transform_reduce (C++17，位于 <numeric>，但概念上与 transform 和 reduce 相关)
① 名称: std::transform_reduce
② 用途: 将一个范围的元素通过一元函数转换，然后使用二元函数对转换后的结果进行归约。可以指定初始值和第二个输入范围。
③ 原型:
1
template <class InputIterator1, class InputIterator2, class T,
2
class BinaryOperation1, class BinaryOperation2>
3
T transform_reduce(InputIterator1 first1, InputIterator1 last1,
4
InputIterator2 first2,
5
T init, BinaryOperation1 binary_op1,
6
BinaryOperation2 binary_op2);
7
8
template <class InputIterator, class T,
9
class BinaryOperation, class UnaryOperation>
10
T transform_reduce(InputIterator first, InputIterator last,
11
T init, BinaryOperation binary_op,
12
UnaryOperation unary_op);
13
14
template <class InputIterator, class T,
15
class BinaryOperation>
16
T transform_reduce(InputIterator first, InputIterator last,
17
T init, BinaryOperation binary_op); // unary_op 为 identity
18
19
template <class InputIterator, class T>
20
T transform_reduce(InputIterator first, InputIterator last,
21
T init); // binary_op 为加法，unary_op 为 identity
④ 代码:
1
#include <iostream>
2
#include <vector>
3
#include <numeric> // 注意：transform_reduce 在 <numeric> 中
4
#include <algorithm>
5
6
int main() {
7
std::vector<int> v1 = {1, 2, 3, 4, 5};
8
std::vector<int> v2 = {10, 20, 30, 40, 50};
9
10
// 计算 (v1[i] + 1) * v2[i] 的总和
11
int result1 = std::transform_reduce(v1.begin(), v1.end(), v2.begin(), 0, std::plus<int>(),
12
[](int a, int b){ return (a + 1) * b; });
13
std::cout << "结果 1: " << result1 << std::endl;
14
15
// 计算 v1 中每个元素的平方和
16
int result2 = std::transform_reduce(v1.begin(), v1.end(), 0, std::plus<int>(),
17
[](int a){ return a * a; });
18
std::cout << "结果 2: " << result2 << std::endl;
19
20
return 0;
21
}
⑤ 注释:
- 这是一个功能强大的算法，可以组合转换和归约操作。
- 第一个版本对两个输入范围的对应元素应用二元操作 binary_op2，然后使用 binary_op1 对结果进行归约，初始值为 init。
- 第二个版本对一个输入范围的每个元素应用一元操作 unary_op，然后使用 binary_op 对结果进行归约，初始值为 init。
- 后两个版本是特化形式，提供了更简洁的用法。
- 时间复杂度为 O(N)。
⑥ 最佳实践:
- 用于高效地执行复杂的聚合操作。
⑦ 常见错误用法:
- 操作符的逻辑错误。
- 初始值 init 的选择不当。
⑧ 陷阱:
- 需要仔细理解各个参数的含义和作用。
2.13.3 std::clamp (C++17)
① 名称: std::clamp
② 用途: 将一个值限制在指定的最小值和最大值之间。
③ 原型:
1
template <class T>
2
const T& clamp(const T& val, const T& low, const T& high);
3
4
template <class T, class Compare>
5
const T& clamp(const T& val, const T& low, const T& high, Compare comp);
④ 代码:
1
#include <iostream>
2
#include <algorithm>
3
4
int main() {
5
int val1 = 15;
6
int low = 10;
7
int high = 20;
8
int clamped_val1 = std::clamp(val1, low, high);
9
std::cout << "clamp(15, 10, 20) = " << clamped_val1 << std::endl;
10
11
int val2 = 5;
12
int clamped_val2 = std::clamp(val2, low, high);
13
std::cout << "clamp(5, 10, 20) = " << clamped_val2 << std::endl;
14
15
int val3 = 25;
16
int clamped_val3 = std::clamp(val3, low, high);
17
std::cout << "clamp(25, 10, 20) = " << clamped_val3 << std::endl;
18
19
return 0;
20
}
⑤ 注释:
- 第一个版本使用 < 运算符进行比较。
- 第二个版本使用自定义的比较函数 comp。
- 如果 val 小于 low，返回 low。
- 如果 val 大于 high，返回 high。
- 否则，返回 val。
- 要求 low <= high。
⑥ 最佳实践:
- 用于将数值限制在有效范围内。
⑦ 常见错误用法:
- low 大于 high。
⑧ 陷阱:
- 无。
3. 总结 📝
<algorithm> 库是 C++ 中处理序列数据的强大工具箱。它提供了各种各样的算法，涵盖了排序、搜索、计数、修改、比较、集合操作、堆操作等等。熟练掌握这些算法能够帮助开发者编写更高效、更简洁、更易于维护的代码。
核心要点回顾:
- 通用性: 大部分算法通过迭代器进行操作，可以应用于不同类型的容器。
- 效率: 标准库的算法通常经过高度优化，具有良好的性能。
- 可读性: 使用算法可以使代码逻辑更清晰，减少手动编写循环的需求。
- 正确性: 标准库的实现经过广泛测试，可靠性高。
学习建议:
- 理解每个算法的用途、前提条件（例如，是否需要已排序的范围）和时间复杂度。
- 学会根据具体需求选择合适的算法。
- 多练习编写使用
<algorithm>库的代码，加深理解。 - 关注 C++ 标准的新特性，例如 C++11 引入的
std::shuffle和 C++17 引入的std::sample和std::clamp等。
希望这份系统性、结构化的学习笔记能够帮助你更好地理解和使用 C++ 的 <algorithm> 库！Happy coding! 😊