C++标准库中的头文件提供的常用算法|c++|std|向量|头文件|序列|标准库|算法

在C++中，头文件提供了一系列用于操作序列（如数组、向量、列表等）的算法。这些算法可以极大地简化数据处理任务，提高代码的可读性和可维护性。本文将详细介绍头文件中提供的一些常用算法，并通过代码示例来解释其用法。

一、查找算法 1. std::find

std::find是一个线性查找算法，用于在序列中查找特定元素。

#include #include #include int main() {    std::vector vec = {1, 2, 3, 4, 5};    int val = 3;        // 使用std::find查找val在vec中的位置    auto it = std::find(vec.begin(), vec.end(), val);        if (it != vec.end()) {        std::cout << "找到元素 " << val << " 在位置 " << std::distance(vec.begin(), it) << std::endl;    } else {        std::cout << "未找到元素 " << val << std::endl;    }        return 0;}

2. std::find_if

std::find_if允许你根据特定条件在序列中查找元素。

#include #include #include bool is_even(int i) {    return (i % 2) == 0;}int main() {    std::vector vec = {1, 2, 3, 4, 5};        // 使用std::find_if查找第一个偶数元素    auto it = std::find_if(vec.begin(), vec.end(), is_even);        if (it != vec.end()) {        std::cout << "找到第一个偶数 " << *it << " 在位置 " << std::distance(vec.begin(), it) << std::endl;    } else {        std::cout << "未找到偶数" << std::endl;    }        return 0;}

二、排序算法 1. std::sort

std::sort是一个高效的排序算法，通常实现为快速排序、堆排序或归并排序的混合体。

#include #include #include int main() {    std::vector vec = {5, 2, 3, 1, 4};        // 使用std::sort对vec进行排序    std::sort(vec.begin(), vec.end());        // 输出排序后的向量    for (int i : vec) {        std::cout << i << " ";    }    std::cout << std::endl;        return 0;}

2. std::stable_sort

std::stable_sort是一种稳定的排序算法，即相等元素的相对顺序在排序后保持不变。

// 用法与std::sort类似，但保证排序的稳定性。

三、修改序列算法 1. std::for_each

std::for_each用于对序列中的每个元素执行特定操作。

#include #include #include void print(int i) {    std::cout << i << " ";}int main() {    std::vector vec = {1, 2, 3, 4, 5};        // 使用std::for_each打印vec中的每个元素    std::for_each(vec.begin(), vec.end(), print);    std::cout << std::endl;        return 0;}

2. std::transform

std::transform用于对序列中的每个元素执行某种转换，并将结果存储到另一个序列中。

#include #include #include #include  // 为了使用std::plus等函数对象int main() {    std::vector vec = {1, 2, 3, 4, 5};    std::vector result(vec.size());        // 使用std::transform将vec中的每个元素加倍并存储到result中    std::transform(vec.begin(), vec.end(), result.begin(), [](int x) { return x * 2; });        // 输出转换后的结果向量    for (int i : result) {        std::cout << i << " ";    }    std::cout << std::endl;        return 0;}

四、其他常用算法 1. std::unique_copy

std::unique_copy算法用于从一个输入序列中复制不重复的元素到一个输出序列。这个算法假定输入序列是已排序的，因为只有已排序的序列才能保证相邻的重复元素被识别并去除。

#include #include #include #include int main() {    std::vector source = {1, 2, 2, 3, 4, 4, 4, 5};    std::vector destination;    std::unique_copy(source.begin(), source.end(), std::back_inserter(destination));    // 输出目标向量，应不包含重复的元素    for (int val : destination) {        std::cout << val << " ";    }    std::cout << std::endl;    return 0;}

注意：在这个例子中，std::back_inserter是一个插入迭代器，它将新元素添加到destination容器的末尾。

2. std::merge

std::merge算法用于合并两个已排序的序列，结果也是一个已排序的序列。

#include #include #include #include int main() {    std::vector vec1 = {1, 3, 5, 7};    std::vector vec2 = {2, 4, 6, 8};    std::vector result(vec1.size() + vec2.size());    std::merge(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), result.begin());    // 输出合并后的结果向量    for (int val : result) {        std::cout << val << " ";    }    std::cout << std::endl;    return 0;}

3. 集合算法：std::set_difference, std::set_intersection, std::set_union, std::set_symmetric_difference

这些算法用于在两个已排序的序列之间执行集合操作。

std::set_difference：计算两个已排序范围的差集。
std::set_intersection：计算两个已排序范围的交集。
std::set_union：计算两个已排序范围的并集。
std::set_symmetric_difference：计算两个已排序范围的对称差集（即属于第一个范围但不属于第二个范围，以及属于第二个范围但不属于第一个范围的所有元素）。

下面是std::set_union的一个例子：

#include #include #include #include int main() {    std::vector vec1 = {1, 2, 3, 4, 5};    std::vector vec2 = {4, 5, 6, 7, 8};    std::vector union_result;    std::set_union(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), std::back_inserter(union_result));    // 输出并集结果向量    for (int val : union_result) {        std::cout << val << " ";    }    std::cout << std::endl;    return 0;}

对于其他集合算法，使用方法是类似的，只是调用的函数名不同，以及它们处理集合运算的方式不同。这些算法在处理大量数据时可以显著提高效率，因为它们都利用了输入数据已排序的特性来优化性能。

五、其他值得注意的算法

除了之前提到的算法外，C++标准库还提供了许多其他有用的算法，这些算法在处理各种编程任务时都非常实用。

1. std::partition 和 std::stable_partition

std::partition 和 std::stable_partition 算法用于根据给定谓词对序列进行划分，使得满足谓词的元素出现在不满足谓词的元素之前。std::stable_partition 还保持了等价元素的相对顺序。

2. std::nth_element

std::nth_element 算法用于对序列进行部分排序，使得第n个位置的元素在排序后处于它在完全排序序列中的位置，且该位置左边的所有元素都小于或等于它，右边的所有元素都大于或等于它。

3. std::rotate 和 std::rotate_copy

std::rotate 算法用于将序列中的元素循环左移或右移，而 std::rotate_copy 则在旋转的同时将结果复制到一个新的序列中。

4. std::remove 和 std::remove_if

std::remove 算法用于从序列中移除所有等于给定值的元素，而 std::remove_if 则根据给定的谓词来移除元素。这两个算法并不实际删除元素，而是将不需要删除的元素移动到序列的前面，并返回一个迭代器指向新的序列末尾。

5. std::lower_bound 和 std::upper_bound