C-STL算法函数-应用及其操作实现

JAY.LIN 收录于算法 C

2025-03-16 约 4828 字预计阅读 10 分钟

https://bing.ee123.net/img/rand?artid=146191023

C++ STL算法函数 —— 应用及其操作实现

一、STL算法函数分类概述

STL算法库提供了大量实用函数，按功能可分为以下五类：

1. 不修改序列的操作

定义：这些算法不会改变容器中的元素，仅对数据进行查询或统计。

典型函数 ：

函数	功能	示例
`find(first, last, value)`	在区间 `[first, last)` 内顺序查找值为 `value` 的元素。	`find(a.begin(), a.end(), 5)`
`count(first, last, value)`	统计区间内值为 `value` 的元素个数。	`count(a.begin(), a.end(), 3)`
`all_of(first, last, pred)`	检查区间内所有元素是否满足谓词 `pred` 。	`all_of(a.begin(), a.end(), is_positive)`
`accumulate(first, last, init)`	对区间内元素进行累加，初始值为 `init` 。	`accumulate(a.begin(), a.end(), 0)`

说明：

搜索操作 ：如 find 、 search 。
批量操作 ：如 for_each （对每个元素执行操作）。
折叠操作 ：如 accumulate （将元素通过运算折叠为一个值）。

2. 修改序列的操作

定义：这些算法会直接修改容器中的元素或顺序。 有复制操作、交换操作、生成操作、移除操作、顺序变更操作、采样操作。

典型函数 ：

函数	功能	示例
`copy(src_begin, src_end, dest)`	复制源区间元素到目标位置。	`copy(a.begin(), a.end(), b.begin())`
`swap(a, b)`	交换两个元素的值。	`swap(a[0], a[1])`
`remove(first, last, value)`	移除区间内所有值为 `value` 的元素（需配合 `erase` 使用）。	`a.erase(remove(a.begin(), a.end(), 5), a.end())`
`reverse(first, last)`	翻转区间内元素的顺序。	`reverse(a.begin(), a.end())`

说明：

复制操作 ：如 copy 、 copy_n 。
移除操作 ：如 remove 、 remove_if 。
顺序变更操作 ：如 reverse 、 rotate 。

3. 排序和相关操作

定义：涉及排序、划分、堆操作等与元素顺序相关的算法。有划分操作、排序操作、二分搜索操作（在已划分范围上）、集合操作（在已排序范围上）、归并操作（在已排序范围上）、堆操作、最大/最小操作、字典序比较操作、排列操作。

典型函数 ：

函数	功能	示例
`sort(first, last, cmp)`	对区间进行排序（默认升序）。	`sort(a.begin(), a.end())`
`binary_search(first, last, value)`	在已排序区间内进行二分查找。	`binary_search(a.begin(), a.end(), 10)`
`nth_element(first, nth, last)`	将第 `n` 大的元素放到正确位置，左侧均小于它，右侧均大于它。	`nth_element(a.begin(), a.begin()+3, a.end())`
`make_heap(first, last)`	将区间转换为堆结构。	`make_heap(a.begin(), a.end())`

说明：

划分操作 ：如 partition （按条件划分元素）。
集合操作 ：如 set_union （求并集，需已排序）。
排列操作 ：如 next_permutation （生成下一个排列）。

4. 数值运算

定义：与数学计算相关的算法，需包含 <numeric> 头文件。

典型函数 ：

函数	功能	示例
`iota(first, last, start)`	用连续递增的值填充区间，从 `start` 开始。	`iota(a.begin(), a.end(), 1)`
`inner_product(a_begin, a_end, b_begin, init)`	计算两个序列的内积（点积）。	`inner_product(a.begin(), a.end(), b.begin(), 0)`
`partial_sum(first, last, dest)`	计算前缀和并写入目标位置。	`partial_sum(a.begin(), a.end(), b.begin())`

说明：

此类算法通常用于数学计算，如求和、乘积、差值等。

5. 在未初始化内存上的操作

定义：直接在未初始化的内存区域构造对象，需包含 <memory> 头文件。

典型函数 ：

函数	功能	示例
`uninitialized_copy(src_begin, src_end, dest)`	将源区间复制到未初始化的内存。	`uninitialized_copy(a.begin(), a.end(), raw_mem)`
`uninitialized_fill(first, last, value)`	在未初始化内存区间填充 `value` 。	`uninitialized_fill(a.begin(), a.end(), 0)`

说明：

这些函数用于低级内存管理，常见于自定义容器实现或性能优化场景。

总结

STL算法分类清晰，覆盖了从数据查询、修改到数学运算和内存管理的广泛需求。在算法竞赛中，合理使用这些函数可以大幅简化代码并提高效率。例如：

快速查找 ：使用 lower_bound 和 binary_search 。
高效排序 ：结合 sort 和 nth_element 。
灵活修改 ：通过 copy 和 reverse 调整数据顺序。

二、算法函数

下面简要介绍一些在算法竞赛中常用的函数：

函数	功能
unique(first, last)	去除容器中相邻的重复元素，所以一般需要先排序，然后用 `unique` 去重。返回值为指向去重后最后一个不同元素的迭代器。注意原容器大小不变，末尾的重复元素可以用 `erase()` 删除。
nth_element(a.begin(), a.begin() + mid, a.end(), cmp)	按指定范围进行分类，找出序列中第 `n` 大的元素，使其左边均为小于它的数，右边均为大于它的数。该函数一般用于求第 `k` 小的数。
binary_search(a.begin(), a.end(), value)	在已经排序的序列上做二分查找，需要先用 `sort()` 排序。 `value` 为需要查找的值，如果找到，返回 `true` ，否则返回 `false` 。
lower_bound(a.begin(), a.end(), x)	在一个有序序列中进行二分查找，返回指向第一个大于或等于 `x` 的元素的位置。如果不存在这样的元素，则返回尾迭代器。
upper_bound(a.begin(), a.end(), x)	在一个有序序列中进行二分查找，返回指向第一个大于 `x` 的元素的位置的迭代器。如果不存在这样的元素，则返回尾迭代器。
next_permutation(a.begin(), a.end())	将当前排列更改为全排列中的下一个排列。如果当前排列已经是全排列中的最后一个排列，该函数返回 `false` ，并将排列更改为全排列中的第一个排列。
prev_permutation()	将当前排列更改为全排列中的上一个排列，用法与 `next_permutation()` 相同。
max(), min()	查找最大、最小值。
swap()	交换两个元素的值。
find(a.begin(), a.end(), value)	顺序查找， `value` 为需要查找的值。如果找到，返回指向该元素的迭代器；否则返回尾迭代器。
reverse(a.begin(), a.end())	翻转数组、字符串。
sort(a.begin(), a.end(), cmp)	排序， `cmp` 为自定义的比较函数。如果没有提供 `cmp` ，默认按升序排序。

详细说明：

1. `unique(first, last)`

功能：去除相邻的重复元素，通常需要先对容器进行排序。返回的迭代器指向去重后的最后一个元素，原容器的大小不变，末尾的重复元素可以通过 erase() 删除。

std::unique 函数的作用是 去除相邻的重复元素，但它并不会改变容器的大小。它只是将不重复的元素移动到容器的前面，并返回一个指向去重后最后一个元素的迭代器。 去重后的元素范围是从 begin() 到 unique() 返回的迭代器之间的部分，而剩下的部分（从返回的迭代器到 end() ）仍然包含原来的元素，这些元素是未定义的（通常是重复元素的残留）。

为什么会有重复元素？

std::unique 只去除相邻的重复元素 ：
- 如果容器中有多个相同的元素，但它们不相邻， std::unique 不会去除它们。
- 例如， {1, 2, 2, 3, 2, 4} ， std::unique 只会将相邻的 2 去除，结果是 {1, 2, 3, 2, 4} ，后面的 2 仍然存在。
std::unique 不会改变容器的大小 ：
- 它只是将不重复的元素移动到容器的前面，并返回一个指向去重后最后一个元素的迭代器。
- 剩下的部分（从返回的迭代器到 end() ）仍然包含原来的元素，这些元素是未定义的（通常是重复元素的残留）。

为什么需要 `erase` ？

为了真正删除这些残留的重复元素，我们需要使用 erase 函数，将去重后的范围之后的元素删除。
如果不使用 erase ，容器的大小不会改变，末尾的残留元素仍然存在。

代码示例 ：

#include <iostream>
#include <vector>
#include <algorithm>

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

    // 先排序，确保相同的元素相邻
    std::sort(vec.begin(), vec.end());

    // 使用 unique 去除相邻的重复元素
    auto last = std::unique(vec.begin(), vec.end());

    // 使用 erase 删除末尾的残留元素
    vec.erase(last, vec.end());

    // 输出去重后的结果
    for (int i : vec) {
        std::cout << i << " ";
    }

    return 0;
}

输出：1 2 3 4 5

2. `nth_element(a.begin(), a.begin() + mid, a.end(), cmp)`

功能：在序列中找到第 n 大的元素，并将其放置在正确的位置，使得左边的元素都小于它，右边的元素都大于它。常用于快速找到第 k 小的元素。

在 std::nth_element 函数中， cmp 参数是一个可选的比较函数，用于定义元素的排序规则。如果不提供 cmp 参数， std::nth_element 会使用默认的比较规则，即 升序排序 （从小到大）。

默认行为

如果不提供 cmp ， std::nth_element 会使用 operator< 来比较元素。
这意味着它会将序列划分为：左边的元素都小于第 n 个元素，右边的元素都大于或等于第 n 个元素。

代码示例（默认）：

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec = {5, 3, 1, 4, 2};
    int mid = 2; // 找第3小的元素

    // 使用默认的比较规则（升序）
    std::nth_element(vec.begin(), vec.begin() + mid, vec.end());

    std::cout << "第3小的元素是: " << vec[mid] << std::endl;

    // 输出整个向量
    for (int i : vec) {
        std::cout << i << " ";
    }

    return 0;
}

输出：第3小的元素是: 3

代码示例（自定义比较函数）：

#include <iostream>
#include <vector>
#include <algorithm>

bool cmp(int a, int b) {
    return a > b; // 降序排序
}

int main() {
    std::vector<int> vec = {5, 3, 1, 4, 2};
    int mid = 2; // 找第3大的元素

    // 使用自定义的比较规则（降序）
    std::nth_element(vec.begin(), vec.begin() + mid, vec.end(), cmp);

    std::cout << "第3大的元素是: " << vec[mid] << std::endl;

    // 输出整个向量
    for (int i : vec) {
        std::cout << i << " ";
    }

    return 0;
}

3. `binary_search(a.begin(), a.end(), value)`

功能：在已排序的序列中进行二分查找，查找值为 value 。如果找到，返回 true ，否则返回 false 。

代码示例 ：

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    bool found = std::binary_search(vec.begin(), vec.end(), 3);

    std::cout << (found ? "找到" : "未找到") << std::endl;
    return 0;
}

输出：找到

4. `lower_bound(a.begin(), a.end(), x)`

功能：在有序序列中查找第一个 大于或等于 x 的元素的位置。如果不存在这样的元素，返回尾迭代器。

代码示例 ：

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec = {1, 2, 4, 4, 5};
    auto it = std::lower_bound(vec.begin(), vec.end(), 3);

    if (it != vec.end()) {
        std::cout << "第一个大于或等于3的元素是: " << *it << std::endl;
    } else {
        std::cout << "未找到" << std::endl;
    }
    return 0;
}

输出：第一个大于或等于3的元素是: 4

5. `upper_bound(a.begin(), a.end(), x)`

功能：在有序序列中查找第一个大于 x 的元素的位置。如果不存在这样的元素，返回尾迭代器。

代码示例 ：

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec = {1, 2, 4, 4, 5};
    auto it = std::upper_bound(vec.begin(), vec.end(), 3);

    if (it != vec.end()) {
        std::cout << "第一个大于3的元素是: " << *it << std::endl;
    } else {
        std::cout << "未找到" << std::endl;
    }
    return 0;
}

输出：第一个大于3的元素是: 4

6. `next_permutation(a.begin(), a.end())`

功能： 将当前排列更改为全排列中的下一个排列。如果当前排列已经是最后一个排列，则返回 false ，并将排列重置为第一个排列。

代码示例 ：

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec = {1, 2, 3};
    do {
        for (int i : vec) {
            std::cout << i << " ";
        }
        std::cout << std::endl;
    } while (std::next_permutation(vec.begin(), vec.end()));
    return 0;
}

输出：

7. `prev_permutation()`

功能： 将当前排列更改为全排列中的上一个排列。用法与 next_permutation() 类似。

代码示例 ：

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec = {3, 2, 1};
    do {
        for (int i : vec) {
            std::cout << i << " ";
        }
        std::cout << std::endl;
    } while (std::prev_permutation(vec.begin(), vec.end()));
    return 0;
}

输出：

8. `max(), min()`

功能：用于查找序列中的最大值和最小值。

代码示例 ：

#include <iostream>
#include <algorithm>

int main() {
    int a = 5, b = 3;
    std::cout << "最大值: " << std::max(a, b) << std::endl;
    std::cout << "最小值: " << std::min(a, b) << std::endl;
    return 0;
}

输出：

最大值: 5
最小值: 3

9. `swap()`

功能：交换两个元素的值。

代码示例 ：

#include <iostream>
#include <algorithm>

int main() {
    int a = 5, b = 3;
    std::swap(a, b);
    std::cout << "a: " << a << ", b: " << b << std::endl;
    return 0;
}

输出：a: 3, b: 5

10. `find(a.begin(), a.end(), value)`

功能： 在序列中顺序查找值为 value 的元素。如果找到，返回指向该元素的迭代器；否则返回尾迭代器。

代码示例 ：

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    auto it = std::find(vec.begin(), vec.end(), 3);

    if (it != vec.end()) {
        std::cout << "找到: " << *it << std::endl;
    } else {
        std::cout << "未找到" << std::endl;
    }
    return 0;
}

输出：找到: 3

11. `reverse(a.begin(), a.end())`

功能：翻转数组或字符串。

代码示例 ：

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    std::reverse(vec.begin(), vec.end());

    for (int i : vec) {
        std::cout << i << " ";
    }
    return 0;
}

输出：5 4 3 2 1

12. `sort(a.begin(), a.end(), cmp)`

功能：对序列进行排序， cmp 为自定义的比较函数。如果没有提供 cmp ，默认按升序排序。

代码示例 ：

#include <iostream>
#include <vector>
#include <algorithm>

bool cmp(int a, int b) {
    return a > b; // 降序排序
}

int main() {
    std::vector<int> vec = {5, 3, 1, 4, 2};
    std::sort(vec.begin(), vec.end(), cmp);

    for (int i : vec) {
        std::cout << i << " ";
    }
    return 0;
}

输出：5 4 3 2 1

三、两种相关例子说明

注意：最重要的一点是迭代器是左闭右开区间，即最左边能取到，但是最右边取不到，换成数组也是一样的。

1. 使用 `vector` 定义数列的代码

#include <bits/stdc++.h>  // 包含标准库的所有头文件
using namespace std;      // 使用标准命名空间

vector<int> a {23, 5, 36, 4, 8, 7, 5, 23};  // 初始化一个 vector，包含元素 23, 5, 36, 4, 8, 7, 5, 23

void out() {  // 定义一个输出函数，用于打印 vector 的内容
    for (int i = 0; i < a.size(); i++)  // 遍历 vector
        cout << a[i] << " ";  // 输出每个元素
    cout << endl;  // 换行
}

int main() {
    auto it = find(a.begin(), a.end(), 5);  // 在 vector 中查找值为 5 的元素
    if (it != a.end()) cout << "yes" << endl;  // 如果找到，输出 "yes"
    else cout << "no" << endl;  // 如果没找到，输出 "no"

    nth_element(a.begin(), a.begin() + 4, a.end());  // 将第 5 小的元素放到正确位置
    out();  // 输出当前 vector 内容
    cout << "第 5 小:" << a[4] << endl;  // 输出第 5 小的元素

    sort(a.begin(), a.end());  // 对 vector 进行升序排序
    out();  // 输出排序后的 vector

    auto last = unique(a.begin(), a.end());  // 去除相邻重复元素，返回去重后的尾迭代器
    out();  // 输出去重后的 vector

    a.erase(last, a.end());  // 删除末尾的重复元素
    out();  // 输出最终去重后的 vector

    it = lower_bound(a.begin(), a.end(), 11);  // 查找第一个大于或等于 11 的元素
    if (it != a.end()) cout << *it << endl;  // 如果找到，输出该元素

    it = upper_bound(a.begin(), a.end(), 5);  // 查找第一个大于 5 的元素
    if (it != a.end()) cout << *it << endl;  // 如果找到，输出该元素

    return 0;  // 主函数结束
}

2. 使用数组定义数列的代码

#include <bits/stdc++.h>  // 包含标准库的所有头文件
using namespace std;      // 使用标准命名空间

int a[] = {23, 5, 36, 4, 8, 7, 5, 23};  // 初始化一个数组，包含元素 23, 5, 36, 4, 8, 7, 5, 23
int n = 8;  // 数组的长度

void out() {  // 定义一个输出函数，用于打印数组的内容
    for (int i = 0; i < n; i++)  // 遍历数组
        cout << a[i] << " ";  // 输出每个元素
    cout << endl;  // 换行
}

int main() {
    int k = find(a, a + n, 5) - a;  // 在数组中查找值为 5 的元素，返回其索引
    if (k != n) cout << "yes" << endl;  // 如果找到，输出 "yes"
    else cout << "no" << endl;  // 如果没找到，输出 "no"

    nth_element(a, a + 4, a + n);  // 将第 5 小的元素放到正确位置
    out();  // 输出当前数组内容
    cout << "第 5 小:" << a[4] << endl;  // 输出第 5 小的元素

    sort(a, a + n);  // 对数组进行升序排序
    out();  // 输出排序后的数组

    n = unique(a, a + n) - a;  // 去除相邻重复元素，并更新数组长度
    out();  // 输出去重后的数组

    k = lower_bound(a, a + n, 11) - a;  // 查找第一个大于或等于 11 的元素
    if (k != n) cout << a[k] << endl;  // 如果找到，输出该元素

    k = upper_bound(a, a + n, 5) - a;  // 查找第一个大于 5 的元素
    if (k != n) cout << a[k] << endl;  // 如果找到，输出该元素

    if (binary_search(a, a + n, 23)) cout << "yes1" << endl;  // 在数组中二分查找值为 23 的元素
    else cout << "no1" << endl;  // 如果没找到，输出 "no1"

    reverse(a, a + n);  // 反转数组
    out();  // 输出反转后的数组

    int b[] = {2, 5, 7, 4, 5};  // 初始化另一个数组
    do {  // 使用 do-while 循环生成排列
        for (int i = 1; i < 4; i++) cout << b[i] << " ";  // 输出数组的部分元素
        cout << " ";  // 输出空格
    } while (next_permutation(b + 1, b + 4));  // 生成从第 2 个元素到第 4 个元素的全排列

    return 0;  // 主函数结束
}

总结

vector 版本 ：使用 STL 容器 vector ，支持动态大小调整，操作更灵活。
数组版本 ：使用静态数组，操作更底层，适合固定大小的场景。
两段代码的功能基本相同，包括查找、排序、去重、二分查找、排列生成等操作。

目录

C-STL算法函数-应用及其操作实现

C++ STL算法函数 —— 应用及其操作实现

一、STL算法函数分类概述

1. 不修改序列的操作

2. 修改序列的操作

3. 排序和相关操作

4. 数值运算

5. 在未初始化内存上的操作

总结

二、算法函数

详细说明：

1. unique(first, last)

为什么会有重复元素？

为什么需要 erase ？

2. nth_element(a.begin(), a.begin() + mid, a.end(), cmp)

3. binary_search(a.begin(), a.end(), value)

4. lower_bound(a.begin(), a.end(), x)

5. upper_bound(a.begin(), a.end(), x)

6. next_permutation(a.begin(), a.end())

7. prev_permutation()

8. max(), min()

9. swap()

10. find(a.begin(), a.end(), value)

11. reverse(a.begin(), a.end())

12. sort(a.begin(), a.end(), cmp)

三、两种相关例子说明

1. 使用 vector 定义数列的代码

2. 使用数组定义数列的代码

总结

1. `unique(first, last)`

为什么需要 `erase` ？

2. `nth_element(a.begin(), a.begin() + mid, a.end(), cmp)`

3. `binary_search(a.begin(), a.end(), value)`

4. `lower_bound(a.begin(), a.end(), x)`

5. `upper_bound(a.begin(), a.end(), x)`

6. `next_permutation(a.begin(), a.end())`

7. `prev_permutation()`

8. `max(), min()`

9. `swap()`

10. `find(a.begin(), a.end(), value)`

11. `reverse(a.begin(), a.end())`

12. `sort(a.begin(), a.end(), cmp)`

1. 使用 `vector` 定义数列的代码