<iterator>类

迭代器的选择与种类

迭代器的操作：

通用迭代器 std::advance(it, n)

• it：要移动的迭代器（按引用传递，会被修改）
• n：移动的步数（整数，正数向前，负数向后） 特点：直接修改传入的迭代器，并且适用于所有迭代器类型

向前移动迭代器std::next(it, n)

• it：起始迭代器（按值传递，不会被修改）
• n：移动步数（默认为 1，可选 特点：不修改原迭代器，需要用另一个迭代器输入这个值。

向后移动迭代器 std::prev()

• it：起始迭代器（按值传递，不会被修改）
• n：向后移动的步数（默认为 1） 特点与前迭代器相同，这两个迭代器需要双向迭代器（如 list, map, set 的迭代器），不支持如forward_list的单向迭代器。

距离计算器std::distance(first, last)，计算两个迭代器之间的元素数量，一般是用来计算index用的。

迭代器适配器

迭代器适配器是 C++ 中一种特殊类型的迭代器，它们通过包装和修改现有迭代器的行为来提供新的功能。基本来说就是把赋值操作进行一些改变，而不是传统的赋值。

• std::back_inserter(container)创建一个输出迭代器适配器，当向它赋值时，会自动调用容器的 push_back() 方法，在容器的末尾添加新元素。container：必须支持 push_back() 的容器（如 std::vector, std::deque, std::list, std::string）。其返回值是一个 std::back_insert_iterator 类型的迭代器适配器对象。与需要写入元素的算法（如 std::copy, std::transform, std::set_intersection, std::fill_n）一起使用，将结果直接追加到容器末尾，避免预先分配空间。

std::vector<int> src = {1, 2, 3};
std::vector<int> dest(3); // 预先分配空间
std::copy(src.begin(), src.end(), dest.begin());
// dest = {1, 2, 3}

// 使用插入迭代器（无需预分配）
std::vector<int> dest2;
std::copy(src.begin(), src.end(), std::back_inserter(dest2));

• std::front_inserter(container)创建一个输出迭代器适配器，当向它赋值时，会自动调用容器的 push_front() 方法，在容器的开头添加新元素。 container：必须支持 push_front() 的容器（如 std::deque, std::list，std::vector 不支持）。 返回值：一个 std::front_insert_iterator 类型的迭代器适配器对象。 用法和back_inserter()类似，与需要写入元素的算法一起使用，将结果直接添加到容器开头。注意：结果顺序会颠倒，因为元素是逐个插入到最前面的。
• std::inserter(container, pos)创建一个输出迭代器适配器，当向它赋值时，会自动调用容器的 insert() 方法，在指定位置 pos 之前插入新元素。插入后迭代器 pos 会自动指向新元素之后的位置，确保后续插入保持顺序。 container：必须支持 insert(position, value) 的容器（几乎所有标准容器都支持：vector, deque, list, set, map, string）。 pos：一个指向 container 中有效位置的迭代器（新元素将插入在 pos 指向的元素之前）。 返回值是一个 std::insert_iterator 类型的迭代器适配器对象，通常来说就是一个在指定位置插入的inserter。

<algorithm>类

非修改序列操作

1. find(first, last, val)

• 功能: 在序列 [first, last) 中查找第一个值等于 val 的元素。
• 返回值:
  • 如果找到，返回指向该元素的迭代器。
  • 如果未找到，返回 last 迭代器。

示例:

std::vector<int> v = {10, 20, 30, 40};
auto it = std::find(v.begin(), v.end(), 30);
if (it != v.end()) {
    std::cout << "找到了元素: " << *it << std::endl; // 输出: 找到了元素: 30
}

2. count(first, last, val)

• 功能: 统计在序列 [first, last) 中值等于 val 的元素出现的次数。
• 返回值: 一个整数，表示 val 出现的次数。

示例:

std::vector<int> v = {10, 20, 30, 20, 10, 20};
int num = std::count(v.begin(), v.end(), 20);
std::cout << "20 出现了 " << num << " 次" << std::endl; // 输出: 20 出现了 3 次

3. all_of(first, last, pred)

• 功能: 检查序列 [first, last) 中的所有元素是否都满足谓词 pred 所指定的条件。
• 返回值:
  • 如果所有元素都满足条件（或序列为空），返回 true。
  • 否则，返回 false。

示例: 检查所有元素是否都是偶数。

std::vector<int> v = {2, 4, 6, 8};
bool result = std::all_of(v.begin(), v.end(), [](int i){ return i % 2 == 0; });
// result 的值为 true

4. any_of(first, last, pred)

• 功能: 检查序列 [first, last) 中是否至少有一个元素满足谓词 pred 所指定的条件。
• 返回值:
  • 如果至少有一个元素满足条件，返回 true。
  • 如果所有元素都不满足条件（或序列为空），返回 false。

示例: 检查是否存在负数。

std::vector<int> v = {1, 5, -3, 8};
bool result = std::any_of(v.begin(), v.end(), [](int i){ return i < 0; });
// result 的值为 true

5. for_each(first, last, func)

• 功能: 对序列 [first, last) 中的每一个元素应用一元函数 func。func 不应该修改其参数，但函数本身可以有副作用（比如打印）。
• 返回值: 返回传入的 func 的一个副本。

示例: 打印容器中的所有元素。

std::vector<int> v = {10, 20, 30};
std::for_each(v.begin(), v.end(), [](int i){ std::cout << i << " "; });
// 输出: 10 20 30

6. search(f1, l1, f2, l2)

• 功能: 在第一个序列 [f1, l1) 中搜索第二个序列 [f2, l2) (子序列) 首次出现的位置。
• 时间复杂度: O(n⋅m)，其中 n 是第一个序列的长度，m 是子序列的长度。
• 返回值:
  • 如果找到子序列，返回一个指向第一个序列中子序列起始位置的迭代器。
  • 如果未找到，返回 l1。

示例:

std::string text = "this is a simple example";
std::string sub = "simple";
auto it = std::search(text.begin(), text.end(), sub.begin(), sub.end());
if (it != text.end()) {
    std::cout << "找到了子序列" << std::endl;
}

7. mismatch(f1, l1, f2)

• 功能: 并行比较两个序列，第一个序列由 [f1, l1) 定义，第二个序列从 f2 开始。它会找出并返回两个序列中第一对不匹配的元素。
• 返回值: 返回一个 std::pair，包含两个迭代器：
  • 第一个迭代器指向第一个序列中不匹配的元素。
  • 第二个迭代器指向第二个序列中不匹配的元素。
  • 如果两个序列在 [f1, l1) 范围内完全匹配，则第一个迭代器等于 l1。

示例:

std::vector<int> v1 = {1, 2, 3, 5};
std::vector<int> v2 = {1, 2, 4, 5};
auto p = std::mismatch(v1.begin(), v1.end(), v2.begin());
std::cout << "第一个不匹配的位置: " << *p.first << " 和 " << *p.second <<    std::endl;
// 输出: 第一个不匹配的位置: 3 和 4

8.transform()

1. 一元操作: 接受一个输入序列，对其中每个元素执行一个一元函数（接受一个参数），然后将结果存入目标序列。
2. 二元操作: 接受两个输入序列，从每个序列中各取一个元素，对这两个元素执行一个二元函数（接受两个参数），然后将结果存入目标序列。
3. 目标空间: 必须确保目标迭代器指向的容器有足够的空间。通常使用 std::back_inserter 会非常方便，因为它可以在添加元素时自动扩展容器。
• 示例：

对一个或两个序列中的每个元素应用一个指定的函数，并将结果存储到目标序列中。

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
int main() {
    std::vector<int> v1 = {1, 2, 3, 4, 5};
    std::vector<int> v2 = {10, 20, 30, 40, 50};
    std::vector<int> dest;

    // 一元操作: 将 v1 中的每个元素平方后放入 dest
    std::transform(v1.begin(), v1.end(), std::back_inserter(dest),
                   [](int x) { return x * x; });
    // dest 现在是: {1, 4, 9, 16, 25}

    dest.clear(); // 清空 dest

    // 二元操作: 将 v1 和 v2 中对应位置的元素相加后放入 dest
    std::transform(v1.begin(), v1.end(), v2.begin(), std::back_inserter(dest),
                   [](int x, int y) { return x + y; });
    // dest 现在是: {11, 22, 33, 44, 55}
	
    return 0;
}

修改序列操作

1. copy(src_f, src_l, dest_f)

• 功能: 将源序列 [src_f, src_l) 中的元素复制到以 dest_f 开始的目标位置。
• 注意:
  • 源序列和目标序列不能重叠，如果可能重叠，应使用 copy_backward。
  • 必须保证从 dest_f 开始的目标容器有足够的容量。

示例:

std::vector<int> src = {1, 2, 3, 4, 5};
std::vector<int> dest(5); // 必须预先分配空间
std::copy(src.begin(), src.end(), dest.begin());
// 现在 dest 的内容是 {1, 2, 3, 4, 5}
// src 的内容不变

2. move(src_f, src_l, dest_f) (C++11)

• 功能: 将源序列 [src_f, src_l) 中的元素移动到以 dest_f 开始的目标位置。它对每个元素使用 std::move，这可以将资源（如动态分配的内存）的所有权从源对象转移到目标对象，而不是简单地复制。
• 效果: 对于拥有动态资源的对象（如 std::string, std::vector, std::unique_ptr），move 通常比 copy 更高效。移动后，源对象处于一种有效的、但未指定的状态，不应再使用其值。

示例:

std::vector<std::string> src = {"hello", "world"};
std::vector<std::string> dest(2);
std::move(src.begin(), src.end(), dest.begin());
// dest 的内容是 {"hello", "world"}
// src 中的字符串现在处于有效但未指定的状态，移动后不应再使用

3. fill(first, last, val)

• 功能: 将序列 [first, last) 中的所有元素都赋值为 val。

示例: 将一个 vector 的所有元素设置为 100。

std::vector<int> v(5); // v 是 {0, 0, 0, 0, 0} (默认初始化)
std::fill(v.begin(), v.end(), 100);
// 现在 v 的内容是 {100, 100, 100, 100, 100}

4. replace(first, last, old, new)

• 功能: 将序列 [first, last) 中所有值等于 old_value 的元素替换为 new_value。

示例:

std::vector<int> v = {1, 2, 3, 1, 2, 1};
std::replace(v.begin(), v.end(), 1, 99);
// 现在 v 的内容是 {99, 2, 3, 99, 2, 99}

5. reverse(first, last)

• 功能: 将序列 [first, last) 中元素的顺序完全反转。

示例:

std::vector<int> v = {1, 2, 3, 4, 5};
std::reverse(v.begin(), v.end());
// 现在 v 的内容是 {5, 4, 3, 2, 1}

6. rotate(first, mid, last)

• 功能: 对序列 [first, last) 进行循环旋转，使得 mid 所指向的元素成为新的第一个元素。原来的 [first, mid) 区间的元素会被移动到序列的末尾。

示例:

std::vector<int> v = {1, 2, 3, 4, 5, 6};
// 将 {1, 2} 旋转到末尾
auto mid = v.begin() + 2; // mid 指向 3
std::rotate(v.begin(), mid, v.end());
// 现在 v 的内容是 {3, 4, 5, 6, 1, 2}

7. shuffle(first, last, gen) (C++11)

• 功能: 使用一个均匀分布的随机数生成器 gen，对序列 [first, last) 中的元素进行随机重排（洗牌）。
• 注意: 这是进行随机化操作的推荐方式，比旧的 std::random_shuffle 更好，因为它允许你提供自己的、质量更高的随机数引擎。

示例:

#include <random> // 需要包含这个头文件
#include <chrono>

std::vector<int> v = {1, 2, 3, 4, 5, 6};

// 创建一个高质量的随机数生成器
unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
std::default_random_engine gen(seed);

std::shuffle(v.begin(), v.end(), gen);
// v 的内容被随机打乱，例如可能变为 {4, 1, 6, 3, 5, 2}

8. copy_if

• 作用：它的功能是“有条件地复制”。它会遍历一个源序列（比如一个 vector 或者 list），并将其中满足特定条件的元素复制到一个目标序列中。
• 参数详解：
  • first, last：输入迭代器，定义了源序列的范围。例如，一个 vector 的 begin() 和 end()。
  • d_first：输出迭代器，定义了目标序列的起始位置。复制的元素将从这个位置开始存放。
  • pred：一个一元谓词 (Unary Predicate)。这通常是一个返回布尔值（true 或 false）的函数或 Lambda 表达式。copy_if 会对源序列中的每个元素调用这个谓词，只有当谓词返回 true 时，该元素才会被复制。

带_n后缀的操作

1. fill_n(dest, n, val)

• 功能: 从迭代器 dest 指向的位置开始，将后续的 n 个元素都赋值为 val。
• 与 fill 的区别: fill(first, last, val) 填充的是一个已经存在的、由两个迭代器界定的范围；而 fill_n 则是从一个点开始，向后填充固定数量的元素。

示例:

std::vector<int> v(10); // 创建一个有10个元素的vector，初始值为0
// 将从第3个元素（索引为2）开始的5个元素设置为88
std::fill_n(v.begin() + 2, 5, 88);
// 现在 v 的内容是: {0, 0, 88, 88, 88, 88, 88, 0, 0, 0}

2. generate_n(dest, n, gen)

• 功能: 从迭代器 dest 指向的位置开始，用一个生成器函数 gen 的返回值来填充后续的 n 个元素。每填充一个元素，就调用一次 gen。
• 生成器 (Generator): gen 是一个不需要任何参数的可调用对象（比如 lambda [](){...} 或一个普通函数），它的返回值被用来赋给序列中的元素。

示例: 生成一个包含 1, 2, 3, 4, 5 的序列。

std::vector<int> v(5);
int current_num = 1;
// 使用一个lambda表达式作为生成器，每次调用都返回递增的数字
std::generate_n(v.begin(), 5, [&current_num]() {
    return current_num++;
});
// 现在 v 的内容是: {1, 2, 3, 4, 5}

3. copy_n(src, n, dest) (C++11)

• 功能: 从迭代器 src 指向的位置开始，精确地复制 n 个元素到从 dest 开始的目标位置。
• 与 copy 的区别: copy(src_f, src_l, dest_f) 复制的是 [src_f, src_l) 整个区间，区间的长度是 std::distance(src_f, src_l)；而 copy_n 则是明确指定要复制 n 个。
• 返回值: 返回一个指向目标范围末尾的迭代器（即最后一个被复制元素的下一个位置）。

示例:

std::vector<int> src = {10, 20, 30, 40, 50, 60};
std::vector<int> dest(4); // 确保目标容器有足够空间

// 从 src 的开头复制 4 个元素到 dest 的开头
std::copy_n(src.begin(), 4, dest.begin());
// 现在 dest 的内容是: {10, 20, 30, 40}

排序与划分

1. sort(first, last)

• 功能描述: 对序列 [first, last) 内的元素进行升序排序。
• 稳定性: 这是不稳定排序 (unstable sort)。如果序列中有多个值相等的元素，排序后它们之间的原始相对顺序不保证被维持。
• 时间复杂度: 平均和最坏情况下都是 O(nlogn)。C++标准库的 std::sort 通常采用一种混合排序算法，称为内省排序 (Introsort)，它结合了快速排序、堆排序和插入排序的优点，以确保优异的平均性能和最坏情况下的性能保证。
• sort还有一个三参数版本sort(first, last, compare)，第三个参数可以自己指定，通常降序排序使用<funtional>的greater<T>()，或者自己写一个lambda表达式。

示例:

std::vector<int> v = {3, 1, 4, 1, 5, 9};
std::sort(v.begin(), v.end());
// v 的内容是 {1, 1, 3, 4, 5, 9}

2. stable_sort(first, last)

• 功能描述: 对序列 [first, last) 内的元素进行升序排序，同时保持相等元素的原始相对顺序。
• 稳定性: 这是稳定排序 (stable sort)。
• 时间复杂度: 如果有足够的额外内存，时间复杂度为 O(nlogn)。如果内存不足，可能会慢一些，达到 O(n(logn)2)。它通常通过归并排序的变体实现。

示例: 假设我们有一个包含姓名和分数的结构体，并按分数排序。

struct Player { std::string name; int score; };
std::vector<Player> players = {{"B", 90}, {"A", 100}, {"C", 90}};
// 按分数降序进行稳定排序
std::stable_sort(players.begin(), players.end(),
    [](const Player& a, const Player& b) {
        return a.score > b.score;
    });
// 结果: {{"A", 100}, {"B", 90}, {"C", 90}}
// "B" 在 "C" 之前，因为它的原始顺序就在前面。如果用 std::sort，顺序可能颠倒。

3. partial_sort(first, mid, last)

• 功能描述: 对序列 [first, last) 进行部分排序。排序完成后，[first, mid) 区间内包含了整个序列中最小的 mid - first 个元素，并且这部分元素是已排序的。[mid, last) 区间内剩余的元素顺序是未指定的。
• 时间复杂度: O(nlogk)，其中 n 是 last - first，k 是 mid - first。
• 应用场景: 当你只需要序列中“Top K”个最小（或最大）的元素，且需要这 K 个元素是有序的时，这个函数非常高效。例如，求排行榜前10名。

示例:

std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
// 找出最小的3个元素，并让它们有序地放在vector的开头
std::partial_sort(v.begin(), v.begin() + 3, v.end());
// v 的内容可能是 {1, 1, 2, 9, 5, 6, 4, 3}
// 前3个元素是 {1, 1, 2}，是整个序列最小的3个且有序。后面的元素顺序不确定。

4. nth_element(first, nth, last)

• 功能描述: 重新排列 [first, last) 中的元素，使得 nth 位置上的元素正是如果整个序列被完全排序后应该处于该位置的那个元素。所有在 nth 之前的元素都小于或等于它，所有在 nth 之后的元素都大于或等于它。
• 保证: 它只保证 nth 位置的正确性，不保证 [first, nth) 和 [nth+1, last) 这两个子序列内部是有序的。
• 时间复杂度: 平均线性时间 O(n)。
• 应用场景: 当你只需要找到第k小的元素（例如，中位数）而不需要排序其他元素时，这是最高效的方法。

示例: 找出中位数。

std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
// 找到中位数应该在的位置
auto median_it = v.begin() + v.size() / 2;
std::nth_element(v.begin(), median_it, v.end());
// v 的内容可能是 {1, 1, 2, 3, 4, 9, 6, 5}
// *median_it 的值现在是 4 (假设v.size()为8, 中位数是第4个元素)
// 4 左边的元素 {1,1,2,3} 都 <= 4
// 4 右边的元素 {9,6,5} 都 >= 4

5. partition(first, last, pred)

• 功能描述: 根据一元谓词 pred 重新排列 [first, last) 中的元素。所有使 pred 返回 true 的元素会被移动到序列的前面，所有使 pred 返回 false 的元素会被移动到序列的后面。
• 返回值: 返回一个迭代器，指向第二组（pred 返回 false）的第一个元素。
• 稳定性: 不保证维持相等元素的相对顺序。如果需要，请使用 std::stable_partition。

示例: 将偶数移动到奇数前面。

std::vector<int> v = {1, 2, 3, 4, 5, 6, 7};
auto boundary = std::partition(v.begin(), v.end(),
                               [](int i){ return i % 2 == 0; });
// v 的内容可能是 {6, 2, 4, 3, 5, 1, 7}
// boundary 指向 3
// {6, 2, 4} 是偶数分区
// {3, 5, 1, 7} 是奇数分区

6. is_sorted(first, last)

• 功能描述: 检查序列 [first, last) 中的元素是否已经按升序（或自定义比较规则）排好序。
• 返回值: 如果已有序，返回 true；否则返回 false。
• 时间复杂度: O(n)，在找到第一个乱序的元素时就会提前返回。

示例:

std::vector<int> v1 = {1, 2, 3, 4, 5};
std::vector<int> v2 = {1, 3, 2, 4, 5};
bool sorted1 = std::is_sorted(v1.begin(), v1.end()); // true
bool sorted2 = std::is_sorted(v2.begin(), v2.end()); // false

二分搜索（要求有序序列）

1. lower_bound(first, last, val)

• 功能描述: 在已排序的序列 [first, last) 中，返回一个迭代器，指向第一个不小于（也就是大于或等于 ≥）val 的元素。
• 返回值:
  • 如果找到了这样的元素，返回指向它的迭代器。
  • 如果序列中所有元素都小于 val，则返回 last。
• 用途: 查找一个值在序列中可以插入的第一个合法位置，同时不破坏序列的顺序。

2. upper_bound(first, last, val)

• 功能描述: 在已排序的序列 [first, last) 中，返回一个迭代器，指向第一个大于 > val 的元素。
• 返回值:
  • 如果找到了这样的元素，返回指向它的迭代器。
  • 如果序列中所有元素都小于或等于 val，则返回 last。
• 用途: 查找一个值在序列中可以插入的最后一个合法位置，同时不破坏序列的顺序。

3. binary_search(first, last, val)

• 功能描述: 在已排序的序列 [first, last) 中，检查是否存在等于 val 的元素。
• 返回值: 一个布尔值。如果存在至少一个值为 val 的元素，返回 true；否则返回 false。
• 注意: 这个函数只告诉你“有”还是“没有”，它不返回元素的位置或迭代器。如果你需要找到元素的位置，应该使用 lower_bound。

示例:

std::vector<int> v = {10, 20, 30, 40, 50};
bool found_30 = std::binary_search(v.begin(), v.end(), 30); // true
bool found_25 = std::binary_search(v.begin(), v.end(), 25); // false

4. equal_range(first, last, val)

• 功能描述: 这是一个组合函数，它一次性返回一个包含 val 的完整范围。这个范围由两个迭代器界定，分别是 val 的 lower_bound 和 upper_bound。
• 返回值: 返回一个 std::pair，其中：
  • pair.first 等价于 std::lower_bound(first, last, val) 的结果。
  • pair.second 等价于 std::upper_bound(first, last, val) 的结果。
• 效率: 调用 equal_range 一次通常比分别调用 lower_bound 和 upper_bound 更高效。
• 用途: 当你需要找到序列中所有等于 val 的元素构成的子序列时，这个函数是最佳选择。

示例: 找出所有等于 30 的元素。

std::vector<int> v = {10, 20, 30, 30, 30, 40, 50};
auto range = std::equal_range(v.begin(), v.end(), 30);

// range.first 指向第一个 30
// range.second 指向 40

std::cout << "值为30的元素有: ";
for (auto it = range.first; it != range.second; ++it) {
    std::cout << *it << " "; // 输出 30 30 30
}
std::cout << std::endl;

// 计算数量
auto count = std::distance(range.first, range.second);
std::cout << "30的数量是: " << count << std::endl; // 输出 3

集合操作

1. set_union(f1, l1, f2, l2, dest)

• 功能描述: 计算两个已排序序列的并集。结果会包含在第一个序列中或在第二个序列中（或两者都有）的所有元素，并写入到 dest。
• 处理重复元素: 如果某个元素在第一个序列中出现 c1 次，在第二个序列中出现 c2 次，那么在并集中它会出现 max(c1, c2) 次。
• 返回值: 指向输出范围末尾的迭代器。

示例:

std::vector<int> v1 = {1, 2, 3, 3, 4};
std::vector<int> v2 = {3, 4, 4, 5};
std::vector<int> dest; // 目标容器

// 使用 std::back_inserter 可以自动扩展容器，无需预分配空间
std::set_union(v1.begin(), v1.end(),
               v2.begin(), v2.end(),
               std::back_inserter(dest));
// dest 的内容是: {1, 2, 3, 3, 4, 4, 5}

2. set_intersection(f1, l1, f2, l2, dest)

• 功能描述: 计算两个已排序序列的交集。结果会包含同时存在于两个序列中的所有元素，并写入到 dest。
• 处理重复元素: 如果某个元素在第一个序列中出现 c1 次，在第二个序列中出现 c2 次，那么在交集中它会出现 min(c1, c2) 次。
• 返回值: 指向输出范围末尾的迭代器。

示例:

std::vector<int> v1 = {1, 2, 3, 3, 4};
std::vector<int> v2 = {3, 4, 4, 5};
std::vector<int> dest;

std::set_intersection(v1.begin(), v1.end(),
                      v2.begin(), v2.end(),
                      std::back_inserter(dest));
// dest 的内容是: {3, 4}

3. set_difference(f1, l1, f2, l2, dest)

• 功能描述: 计算两个已排序序列的差集。结果会包含所有在第一个序列中出现、但不在第二个序列中出现的元素，并写入到 dest。可以理解为 A - B。
• 处理重复元素: 如果某个元素在第一个序列中出现 c1 次，在第二个序列中出现 c2 次，那么在差集中它会出现 max(0, c1 - c2) 次。
• 返回值: 指向输出范围末尾的迭代器。

示例:

std::vector<int> v1 = {1, 2, 3, 3, 4};
std::vector<int> v2 = {3, 4, 4, 5};
std::vector<int> dest;

std::set_difference(v1.begin(), v1.end(),
                    v2.begin(), v2.end(),
                    std::back_inserter(dest));
// dest 的内容是: {1, 2, 3} (v1中的两个3，一个被v2中的3抵消)

4. set_symmetric_difference(f1, l1, f2, l2, dest)

• 功能描述: 计算两个已排序序列的对称差集。结果会包含所有只在其中一个序列出现、而不同时在两个序列中出现的元素，并写入到 dest。可以理解为 (A-B) ∪ (B-A) 或 (A∪B) - (A∩B)。
• 处理重复元素: 如果某个元素在第一个序列中出现 c1 次，在第二个序列中出现 c2 次，那么在对称差集中它会出现 |c1 - c2| 次。
• 返回值: 指向输出范围末尾的迭代器。

示例:

std::vector<int> v1 = {1, 2, 3, 3, 4};
std::vector<int> v2 = {3, 4, 4, 5};
std::vector<int> dest;

std::set_symmetric_difference(v1.begin(), v1.end(),
                              v2.begin(), v2.end(),
                              std::back_inserter(dest));
// dest 的内容是: {1, 2, 3, 4, 5}

5. merge(f1, l1, f2, l2, dest)

• 功能描述: 将两个已排序的序列合并成一个单一的、更大的、依然有序的序列。它会保留两个源序列中的所有元素。
• 与 set_union 的区别: merge 会保留所有元素。如果一个值在 v1 中有2个，在 v2 中有3个，那么 merge 的结果中将有5个。而 set_union 只会保留3个（max(2,3)）。merge 是一个纯粹的归并操作，而不是集合操作。
• 返回值: 指向输出范围末尾的迭代器。

示例:

std::vector<int> v1 = {1, 3, 5};
std::vector<int> v2 = {2, 4, 6};
std::vector<int> dest;

std::merge(v1.begin(), v1.end(),
           v2.begin(), v2.end(),
           std::back_inserter(dest));
// dest 的内容是: {1, 2, 3, 4, 5, 6}

6. includes(f1, l1, f2, l2)

• 功能描述: 检查第一个已排序序列 [f1, l1) 是否包含第二个已排序序列 [f2, l2) 作为子集。也就是说，[f2, l2) 中的每一个元素是否都能在 [f1, l1) 中找到。
• 返回值: 一个布尔值。如果包含，返回 true；否则返回 false。

示例:

std::vector<int> v1 = {1, 2, 3, 4, 5, 6};
std::vector<int> sub1 = {2, 4};
std::vector<int> sub2 = {2, 7};

bool res1 = std::includes(v1.begin(), v1.end(), sub1.begin(), sub1.end()); // true
bool res2 = std::includes(v1.begin(), v1.end(), sub2.begin(), sub2.end()); // false

堆操作

1. make_heap(first, last)

• 功能描述: 将序列 [first, last) 内的元素重新排列，使其满足最大堆的性质。
• 时间复杂度: O(n)。这是一个非常高效的操作，因为它不是通过逐个插入元素（这会是 O(nlogn)）来实现的，而是使用了更优化的建堆算法（Floyd's algorithm）。

示例:

std::vector<int> v = {3, 1, 4, 1, 5, 9};
std::make_heap(v.begin(), v.end());
// v 的内容现在满足最大堆，可能是 {9, 5, 4, 1, 1, 3}
// v.front() 的值现在是 9，即最大元素。

2. push_heap(first, last)

• 功能描述: 将一个新元素添加到已经存在的堆中。这是一个两步过程。
  1. 第一步: 你必须先通过容器自身的方法（如 push_back）将新元素添加到容器的末尾。
  2. 第二步: 然后对包含新元素的整个范围调用 push_heap，它会将新元素从末尾“上浮”到正确的位置以维持堆的性质。

示例:

std::vector<int> v = {9, 5, 4}; // 假设这已经是一个堆
v.push_back(10); // 1. 先将10添加到末尾。v 现在是 {9, 5, 4, 10}
std::push_heap(v.begin(), v.end()); // 2. 调整堆。
// v 现在是 {10, 9, 4, 5}，堆顶变成了 10。

3. pop_heap(first, last)

• 功能描述: 从堆中“移除”堆顶（最大）元素。这也是一个两步过程。
  1. 第一步: 调用 pop_heap，它会将第一个元素（堆顶）与最后一个元素交换，然后对范围 [first, last-1) 重新构建堆，以保证除了最后一个元素外，前面的序列仍然是有效的堆。
  2. 第二步: 此时，最大的元素已经被移到了容器的末尾，你需要自己通过容器的方法（如 pop_back）将其真正地从容器中删除。

示例:

std::vector<int> v = {10, 9, 4, 5}; // 假设这是一个堆
std::pop_heap(v.begin(), v.end()); // 1. 交换堆顶和末尾元素，并调整
// v 现在是 {9, 5, 4, 10}，v.back() 是曾经的堆顶 10
v.pop_back(); // 2. 移除末尾的元素
// v 现在是 {9, 5, 4}，仍然是一个有效的堆。

4. sort_heap(first, last)

• 功能描述: 对一个有效的最大堆进行排序。排序后，序列会变成一个升序排列的普通序列，不再是堆。
• 工作原理: 它本质上是不断地执行 pop_heap 操作。每次都将堆顶（当前最大元素）放到序列的末尾，并缩小堆的范围，直到整个序列都排好序。
• 时间复杂度: O(nlogn)。

示例:

std::vector<int> v = {9, 5, 4, 1, 1, 3};
std::make_heap(v.begin(), v.end()); // 首先确保v是一个堆

std::sort_heap(v.begin(), v.end());
// v 的内容现在是 {1, 1, 3, 4, 5, 9}，一个有序序列。

排列与去重

1. next_permutation(first, last)

• 功能描述: 将序列 [first, last) 就地转换为下一个字典序更大的排列。
• 返回值:
  • 如果成功生成了一个更大的排列，返回 true。
  • 如果当前排列已经是字典序最大的（例如 [3, 2, 1]），函数会将序列转换为字典序最小的排列（例如 [1, 2, 3]），并返回 false。
• 应用场景: 常用于暴力枚举一个集合的所有可能排列组合。

示例:

std::string s = "123";
std::sort(s.begin(), s.end()); // 必须从最小排列开始
do {
    std::cout << s << std::endl;
} while (std::next_permutation(s.begin(), s.end()));
/*
输出:
123
132
213
231
312
321
*/

2. prev_permutation(first, last)

• 功能描述: 与 next_permutation 相反，它将序列 [first, last) 就地转换为上一个字典序更小的排列。
• 返回值:
  • 如果成功生成了一个更小的排列，返回 true。
  • 如果当前排列已经是字典序最小的（例如 [1, 2, 3]），函数会将序列转换为字典序最大的排列（例如 [3, 2, 1]），并返回 false。

示例:

std::string s = "321";
// 从最大排列开始
do {
    std::cout << s << std::endl;
} while (std::prev_permutation(s.begin(), s.end()));
/*
输出:
321
312
231
213
132
123
*/

3. unique(first, last)

• 功能描述: “移除”序列中的相邻重复元素。它通过将不重复的元素前移来覆盖重复的元素，最终返回一个指向新的逻辑末尾的迭代器。
• 重要前提: 为了移除所有的重复元素（而不仅仅是相邻的），你必须先对序列进行排序。
• 返回值: 指向去重后序列的末尾的下一个位置的迭代器。
• 注意：我们需要对未指定的值的结果进行清除。

Erase-remove idiom:

std::vector<int> v = {1, 2, 1, 3, 2, 2, 1, 4};

// 1. 排序，使所有相同元素相邻
std::sort(v.begin(), v.end());
// v 现在是: {1, 1, 1, 2, 2, 2, 3, 4}

// 2. 调用 unique 进行逻辑移除
auto last = std::unique(v.begin(), v.end());
// v 现在是: {1, 2, 3, 4, ?, ?, ?, ?}  (问号代表未指定的值)
// last 指向了元素 4 后面的位置

// 3. 调用 erase 进行物理移除
v.erase(last, v.end());
// v 现在是: {1, 2, 3, 4}

4. remove_if(first, last, pred)

• 功能描述: 根据一元谓词 pred，“移除”序列中所有满足条件的元素。它通过将不满足条件的元素前移来覆盖满足条件的元素。
• 逻辑移除: 与 unique 类似，它只做逻辑移除，返回一个指向新的逻辑末尾的迭代器。
• 返回值: 指向保留下来的元素序列的末尾的下一个位置的迭代器。

Erase-remove idiom: 移除所有偶数。

std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8};

// 1. 调用 remove_if 进行逻辑移除
// 谓词 pred 返回 true 表示“要移除”
auto last = std::remove_if(v.begin(), v.end(), [](int i) {
    return i % 2 == 0; // 如果 i 是偶数，则移除
});
// v 现在是: {1, 3, 5, 7, ?, ?, ?, ?} (问号代表未指定的值)
// last 指向了元素 7 后面的位置

// 2. 调用 erase 进行物理移除
v.erase(last, v.end());
// v 现在是: {1, 3, 5, 7}

注意: 还有一个 std::remove(first, last, value) 版本，它移除所有等于 value 的元素，其工作方式与 remove_if 完全相同。

最值和比较

1. min_element(first, last)

• 功能描述: 在序列 [first, last) 中查找并返回指向第一个最小元素的迭代器。
• 返回值: 指向序列中第一个最小元素的迭代器。如果序列为空，则返回 last。

示例:

std::vector<int> v = {3, 1, 4, 1, 5, 9};
auto it = std::min_element(v.begin(), v.end());

// it 指向 v[1]，因为第一个 1 在索引 1 的位置
std::cout << "最小的元素是: " << *it << std::endl; // 输出: 1

2. max_element(first, last)

• 功能描述: 在序列 [first, last) 中查找并返回指向第一个最大元素的迭代器。
• 返回值: 指向序列中第一个最大元素的迭代器。如果序列为空，则返回 last。

示例:

std::vector<int> v = {3, 1, 4, 1, 5, 9};
auto it = std::max_element(v.begin(), v.end());

// it 指向 v[5]，因为 9 在索引 5 的位置
std::cout << "最大的元素是: " << *it << std::endl; // 输出: 9

3. minmax_element(first, last) (C++11)

• 功能描述: 在一次遍历中同时查找到最小和最大的元素。
• 效率: 这比分别调用 min_element 和 max_element 更高效。单独调用两次需要 2n-2 次比较，而 minmax_element 只需要约 1.5n 次比较。
  • pair.first 是指向第一个最小元素的迭代器。
  • pair.second 是指向最后一个最大元素的迭代器。

返回值: 返回一个 std::pair，其中：

std::vector<int> v = {3, 1, 9, 1, 5, 9};
auto result_pair = std::minmax_element(v.begin(), v.end());

// result_pair.first 指向 v[1] (第一个 1)
// result_pair.second 指向 v[5] (最后一个 9)
std::cout << "最小元素: " << *result_pair.first << std::endl;  // 输出: 1
std::cout << "最大元素: " << *result_pair.second << std::endl; // 输出: 9

4. lexicographical_compare(f1, l1, f2, l2)

• 功能描述: 按字典序 (dictionary order) 比较两个序列 [f1, l1) 和 [f2, l2)。
• 工作原理: 它逐个比较两个序列中对应位置的元素。
  • 如果在某个位置上，第一个序列的元素小于第二个序列的元素，则函数立即返回 true。
  • 如果在某个位置上，第一个序列的元素大于第二个序列的元素，则函数立即返回 false。
  • 如果在遍历完其中一个序列（例如第一个序列）后，所有元素都相等，那么只要第一个序列比第二个序列短，函数就返回 true。
• 返回值: 如果第一个序列按字典序小于第二个序列，则返回 true；否则返回 false。

示例:

std::vector<int> v1 = {1, 2, 3};
std::vector<int> v2 = {1, 2, 4};
// v1 和 v2 在前两个元素上相等，但在第三个元素上 3 < 4
bool r1 = std::lexicographical_compare(v1.begin(), v1.end(), v2.begin(), v2.end()); // true

std::string s1 = "apple";
std::string s2 = "apply";
// s1 和 s2 在前四个字符上相等，但在第五个字符上 'e' < 'y'
bool r2 = std::lexicographical_compare(s1.begin(), s1.end(), s2.begin(), s2.end()); // true

std::vector<int> v3 = {1, 2, 3};
std::vector<int> v4 = {1, 2};
// v4 是 v3 的前缀，所以 v4 更小。因此比较 v3 和 v4 时，v3 更大。
bool r3 = std::lexicographical_compare(v3.begin(), v3.end(), v4.begin(), v4.end()); // false

<numeric>类

1. std::accumulate

std::accumulate 有两个版本（重载）：

基础版本：累加求和

这是最常用的形式，用于计算一个序列中所有元素的总和。

• 参数详解：
  • first, last：输入迭代器，定义了要进行累积计算的元素范围。例如，一个 vector 的 begin() 和 end()。
  • init：累积的初始值。这个参数非常重要，因为：
    1. 它为累积操作提供了一个起点。
    2. 它的类型决定了累积过程和返回值的类型。
• 工作方式： 它从 init 值开始，依次将范围 [first, last) 中的每个元素加到累积值上。

示例代码：

#include <iostream>
#include <vector>
#include <numeric> // 必须包含 <numeric> 头文件

int main() {
    std::vector<int> numbers = {10, 20, 30, 40, 50};

    // 计算所有元素的和，初始值为 0
    int sum = std::accumulate(numbers.begin(), numbers.end(), 0);

    std::cout << "Vector 中所有元素的和是: " << sum << std::endl; // 输出 150

    // 初始值也可以是其他数
    int sum_with_initial = std::accumulate(numbers.begin(), numbers.end(), 100);
    std::cout << "从 100 开始累加的和是: " << sum_with_initial << std::endl; // 输出 250
}

输出结果：

Vector 中所有元素的和是: 150
从 100 开始累加的和是: 250

函数原型：

template< class InputIt, class T >
T accumulate( InputIt first, InputIt last, T init );

高级版本：自定义累积操作

这个版本允许你提供一个自定义的二元操作来代替默认的加法。这使得 std::accumulate 的功能变得异常强大。

• 参数详解：
  • first, last, init：与基础版本相同。
  • op：一个二元操作（Binary Operation）。它可以是一个函数、函数对象或 Lambda 表达式。该操作接收两个参数：当前的累积值和序列中的下一个元素，并返回新的累积值。

函数原型：

template< class InputIt, class T, class BinaryOperation >
T accumulate( InputIt first, InputIt last, T init, BinaryOperation op );

示例 1：计算所有元素的乘积

#include <iostream>
#include <vector>
#include <numeric>

int main() {
    std::vector<int> factors = {1, 2, 3, 4, 5};

    // 计算所有元素的乘积，初始值为 1
    // 注意：乘法累积的初始值必须是 1，否则结果永远是 0
    long long product = std::accumulate(
        factors.begin(),
        factors.end(),
        1LL, // 使用 1LL (long long) 作为初始值，防止结果溢出
        [](long long acc, int val) {
            return acc * val;
        }
    );

    std::cout << "所有元素的乘积是: " << product << std::endl; // 输出 120
}

示例 2：连接字符串

accumulate 不仅限于数字，它可以处理任何类型，只要初始值类型和二元操作定义得当。

#include <iostream>
#include <vector>
#include <string>
#include <numeric>

int main() {
    std::vector<std::string> words = {"Hello", " ", "World", "!"};
    
    // 将 vector 中的所有字符串连接起来
    std::string sentence = std::accumulate(
        words.begin(),
        words.end(),
        std::string(""), // 初始值是一个空字符串
        [](const std::string& acc, const std::string& word) {
            return acc + word;
        }
    );

    std::cout << "连接后的字符串是: \"" << sentence << "\"" << std::endl;
}

输出结果：

连接后的字符串是: "Hello World!"

2 std::inner_product

此算法计算两组数据的内积。

#include <iostream>
#include <vector>
#include <numeric>

int main() {
    std::vector<int> a = {1, 2, 3};
    std::vector<int> b = {4, 5, 6};

    // 计算 a 和 b 的内积
    // 第三个参数是初始值，内积的计算公式是 init + a[0]*b[0] + a[1]*b[1] + ...
    int result = std::inner_product(a.begin(), a.end(), b.begin(), 0);

    // 计算过程: 0 + (1*4) + (2*5) + (3*6) = 0 + 4 + 10 + 18 = 32
    std::cout << "向量 a 和 b 的内积是: " << result << std::endl;
}

3. std::partial_sum

此算法创建一个新序列，其中每个元素都是原始序列从开始到当前位置所有元素的累积和。

#include <iostream>
#include <vector>
#include <numeric>
#include <iterator> // For std::ostream_iterator

int main() {
    std::vector<int> monthly_sales = {100, 120, 80, 150};
    std::vector<int> cumulative_sales(monthly_sales.size());

    // 计算累计销售额
    std::partial_sum(monthly_sales.begin(), monthly_sales.end(), cumulative_sales.begin());

    std::cout << "每月销售额: ";
    for(int sale : monthly_sales) std::cout << sale << " ";
    std::cout << std::endl;

    // 结果将会是: 100, (100+120), (100+120+80), (100+120+80+150)
    std::cout << "累计销售额: ";
    for(int sale : cumulative_sales) std::cout << sale << " ";
    std::cout << std::endl; // 输出: 100 220 300 450
}

4. std::adjacent_difference

此算法可以看作是 std::partial_sum 的逆操作。它创建一个新序列，其中第一个元素与源序列相同，后续每个元素是源序列中当前元素与前一个元素的差。

#include <iostream>
#include <vector>
#include <numeric>

int main() {
    std::vector<int> daily_prices = {100, 105, 102, 108, 107};
    std::vector<int> price_changes(daily_prices.size());

    // 计算每日价格变化
    std::adjacent_difference(daily_prices.begin(), daily_prices.end(), price_changes.begin());

    std::cout << "每日股价: ";
    for(int price : daily_prices) std::cout << price << " ";
    std::cout << std::endl;

    // 结果将会是: 100, (105-100), (102-105), (108-102), (107-108)
    std::cout << "价格变化: ";
    for(int change : price_changes) std::cout << change << " ";
    std::cout << std::endl; // 输出: 100 5 -3 6 -1
}

5. std::iota

这是一个非常方便的工具，用于快速填充一个序列，使其包含从指定初始值开始的连续递增值。

#include <iostream>
#include <vector>
#include <numeric>

int main() {
    // 创建一个包含 10 个元素的 vector
    std::vector<int> v(10);

    // 使用 iota 填充它，从 0 开始，依次递增
    std::iota(v.begin(), v.end(), 0);

    std::cout << "用 iota 生成的序列: ";
    for (int num : v) {
        std::cout << num << " ";
    }
    std::cout << std::endl; // 输出: 0 1 2 3 4 5 6 7 8 9

    // 也可以从任意值开始
    std::iota(v.begin(), v.end(), -4);
    std::cout << "从 -4 开始的序列: ";
    for (int num : v) {
        std::cout << num << " ";
    }
    std::cout << std::endl; // 输出: -4 -3 -2 -1 0 1 2 3 4 5
}