C++标准库算法详解
一、非修改序列算法
以下是一些不会改变容器内容的算法：
1. 查找算法
- `search(first1, last1, first2, last2)`：查找子序列首次出现的位置。
- `find_first_of(first1, last1, first2, last2)`：查找第一个出现在另一范围中的元素。
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> data = {10, 20, 30, 40};
auto result = std::search(data.begin(), data.end(),
std::vector<int>{20, 30}.begin(),
std::vector<int>{20, 30}.end());
if (result != data.end()) {
std::cout << "Found at position: " << std::distance(data.begin(), result) << '\n';
}
}
2. 统计与遍历
- `for_each_n(first, count, func)`：对指定数量的元素应用函数。
- `adjacent_find(first, last)`：查找相邻重复元素。
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> nums = {1, 2, 2, 3, 4};
auto pos = std::adjacent_find(nums.begin(), nums.end());
if (pos != nums.end()) {
std::cout << "Adjacent duplicates found: " << *pos << '\n';
}
}
二、修改序列算法
这些算法会直接修改容器中的数据：
1. 替换与移除
- `swap_ranges(first1, last1, first2)`：交换两个范围内的元素。
- `unique_copy(first, last, result)`：复制去重后的元素到新位置。
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> src = {1, 1, 2, 3, 3};
std::vector<int> dest(src.size());
auto end = std::unique_copy(src.begin(), src.end(), dest.begin());
for (auto it = dest.begin(); it != end; ++it) {
std::cout << *it << ' ';
}
}
2. 变换与生成
- `generate(first, last, gen)`：用生成器填充范围。
- `transform_inclusive_scan(first, last, result, op, init)`：执行累加变换。
#include <numeric>
#include <iostream>
#include <vector>
int main() {
std::vector<int> data = {1, 2, 3, 4};
std::vector<int> sums(data.size());
std::inclusive_scan(data.begin(), data.end(), sums.begin(), std::plus<>(), 0);
for (const auto& val : sums) {
std::cout << val << ' ';
}
}
三、排序与搜索
以下为排序和搜索相关操作：
1. 排序算法
- `nth_element(first, nth, last)`：部分排序，使第 n 个元素位于正确位置。
- `is_sorted_until(first, last)`：找到首个未按顺序排列的元素。
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> vec = {5, 1, 3, 4, 2};
std::nth_element(vec.begin(), vec.begin() + 2, vec.end());
std::cout << "Third smallest element: " << vec[2] << '\n';
}
2. 搜索算法
- `equal_range(first, last, value)`：返回值所在范围的起止迭代器。
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> sorted = {1, 2, 2, 3, 4};
auto range = std::equal_range(sorted.begin(), sorted.end(), 2);
std::cout << "Elements in range: " << std::distance(range.first, range.second) << '\n';
}
四、数值计算
以下是涉及数值处理的算法：
1. 数值操作
- `inner_product(first1, last1, first2, init)`：计算两个序列的内积。
- `partial_sum(first, last, result)`：计算部分和并存储结果。
#include <numeric>
#include <iostream>
#include <vector>
int main() {
std::vector<int> a = {1, 2, 3}, b = {4, 5, 6};
int product = std::inner_product(a.begin(), a.end(), b.begin(), 0);
std::cout << "Inner product: " << product << '\n';
}
五、集合操作
以下为集合相关的算法：
1. 集合运算
- `set_symmetric_difference(first1, last1, first2, last2, result)`：计算对称差集。
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> v1 = {1, 2, 3}, v2 = {2, 3, 4};
std::vector<int> res(v1.size() + v2.size());
auto it = std::set_symmetric_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), res.begin());
res.erase(it, res.end());
for (const auto& val : res) {
std::cout << val << ' ';
}
}
