C++学习笔记（三十八）——STL之修改算法
STL 算法分类：
| 类别 | 常见算法 | 作用 |
|---|---|---|
| 排序 | sort、stable_sort、partial_sort、nth_element等 | 排序 |
| 搜索 | find、find_if、count、count_if、binary_search等 | 查找元素 |
| 修改 | copy、replace、replace_if、swap、fill等 | 修改容器内容 |
| 删除 | remove、remove_if、unique等 | 删除元素 |
| 归约 | for_each、accumulate等 | 处理数据 |
| 合并 | merge、set_union、set_intersection等 | 处理有序序列 |
| 排列组合 | next_permutation、prev_permutation等 | 生成排列 |
| 堆操作 | push_heap、pop_heap、make_heap、sort_heap等 | 处理堆 |
STL 修改算法
在 C++ 标准库（STL）中，修改算法可以在容器中应用特定的操作，如修改元素的值、替换值、插入新元素等。
修改算法通常返回容器的迭代器，指示修改的位置或结果。
| 算法名称 | 功能描述 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|---|
fill | 用指定的值填充容器中的所有元素 | O(n) | O(1) | 填充容器的所有元素 |
fill_n | 用指定的值填充容器中的部分元素 | O(n) | O(1) | 填充容器的部分元素 |
copy | 将一个范围内的元素复制到另一个范围中 | O(n) | O(1) | 将容器中的元素复制到另一个容器 |
swap | 交换两个元素的值 | O(1) | O(1) | 交换两个元素或两个容器的内容 |
replace | 替换容器中所有指定值的元素 | O(n) | O(1) | 替换容器中的指定值 |
replace_if | 替换容器中所有满足条件的元素 | O(n) | O(1) | 根据条件替换容器中的元素 |
transform | 对容器中每个元素应用操作并存储结果 | O(n) | O(1) | 对容器中每个元素进行变换 |
rotate | 将给定范围内的元素旋转指定次数 | O(n) | O(1) | 容器中元素的旋转操作 |
（1）fill
- 功能：用指定的值填充容器中的所有元素。
- 时间复杂度：O(n)，其中
n是容器的元素数量。 - 空间复杂度：O(1)，原地操作。
示例：
#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>int main() {vector<int> vec(5, 0); // 初始化为5个0fill(vec.begin(), vec.end(), 10); // 将所有元素修改为10for (int x : vec){cout << x << " "; // 输出：10 10 10 10 10}cout << endl;system("pause");return 0;
}
注意：
fill适用于，当需要用相同的值填充整个容器时。
（2）fill_n
- 功能：从指定位置开始填充指定数量的元素为给定值。
- 时间复杂度：O(n)，其中
n是填充的元素数量。 - 空间复杂度：O(1)，原地操作。
示例：
#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>int main() {vector<int> vec(5, 0);fill_n(vec.begin(), 3, 10); // 将前3个元素填充为10for (int x : vec){cout << x << " "; // 输出：10 10 10 0 0}cout << endl;system("pause");return 0;
}
注意：
fill_n适用于，当需要填充容器的部分元素时。
（3）copy
- 功能：将一个范围内的元素复制到另一个范围中。
- 时间复杂度：O(n)，其中
n是源范围中的元素数量。 - 空间复杂度：O(1)，原地操作。
示例：
#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>int main() {vector<int> src = { 1, 2, 3, 4, 5 };vector<int> dest(5);// 将 src 中的元素复制到 dest 中copy(src.begin(), src.end(), dest.begin());cout << "复制的vector: ";for (int val : dest) {cout << val << " ";}cout << endl;system("pause");return 0;
}
注意：
copy用于将一个容器中的元素复制到另一个容器，或从一个容器复制到数组等。
（4）swap
- 功能：交换两个变量或容器中的元素。
- 时间复杂度：O(1)，它直接交换两个元素，不涉及其他复杂操作。
- 空间复杂度：O(1)，原地操作。
示例：
#include <iostream>
using namespace std;
#include <algorithm>int main() {int a = 5, b = 10;// 交换 a 和 b 的值swap(a, b);cout << "a = " << a << ", b = " << b << endl;system("pause");return 0;
}
注意：
swap适用于，当需要交换两个元素或两个容器的内容时。
（5）replace
- 功能：将容器中所有等于指定值的元素替换为新值。
- 时间复杂度：O(n)，其中
n是容器的元素数量。 - 空间复杂度：O(1)，原地操作。
示例：
#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>int main() {vector<int> vec = { 1, 2, 3, 2, 5 };replace(vec.begin(), vec.end(), 2, 10); // 将所有2替换为10for (int x : vec){cout << x << " "; // 输出：1 10 3 10 5}cout << endl;system("pause");return 0;
}
注意：
replace适用于，当需要将容器中的指定值替换为其他值时。
（6）replace_if
- 功能：将容器中所有满足条件的元素替换为新值。
- 时间复杂度：O(n)，其中
n是容器的元素数量。 - 空间复杂度：O(1)，原地操作。
示例：
#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>bool is_odd(int n)
{return n % 2 != 0;
}int main() {vector<int> vec = { 1, 2, 3, 4, 5 };replace_if(vec.begin(), vec.end(), is_odd, 10); // 将所有奇数替换为10for (int x : vec){cout << x << " "; // 输出：10 2 10 4 10}cout << endl;system("pause");return 0;
}
注意：
replace_if适用于，当需要根据某种条件替换容器中元素时。
（7）transform
- 功能：对容器中的每个元素应用指定的操作，并将结果存储到目标容器中。
- 时间复杂度：O(n)，其中
n是容器的元素数量。 - 空间复杂度：O(1)。
示例：
#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>int square(int n)
{return n * n;
}int main() {vector<int> vec = { 1, 2, 3, 4, 5 };vector<int> result(vec.size());transform(vec.begin(), vec.end(), result.begin(), square);for (int x : result){cout << x << " "; // 输出：1 4 9 16 25}cout << endl;system("pause");return 0;
}
注意：
transform适用于，当需要对容器中的每个元素进行某些变换时。
（8）rotate
- 功能：将范围内的元素旋转指定次数（左旋/循环左移）。
- 时间复杂度：O(n)，其中
n是范围中的元素数量。 - 空间复杂度：O(1)，原地操作。
示例：
#include <iostream>
#include <algorithm> // std::rotate
#include <vector>int main() {std::vector<int> vec = {1, 2, 3, 4, 5};// 将 vec 中的元素旋转 2 次std::rotate(vec.begin(), vec.begin() + 2, vec.end());std::cout << "Rotated vector: ";for (int val : vec) {std::cout << val << " ";}std::cout << std::endl;return 0;
}
注意：
rotate适用于，当需要将容器中的元素旋转时。