algorithm中常见算法

1、前言

C++的<algorithm>库是C++标准库中的一个重要组成部分，它提供了一系列的函数，用于执行各种常见的算法操作，比如排序、查找、替换、合并等。这些算法函数通常以模板函数的形式提供，可以用于任何符合特定条件的容器类型。

2、常见用法举例

下面结合点云数据处理中常用的算法，介绍该库中一些常用函数。

2.1 最大值与最小值获取

<algorithm>库提供了min_element和max_element函数，这些函数用于在给定范围内查找最小值和最大值元素。这两个函数都返回一个迭代器，指向范围内最小或最大元素的第一个实例。如下，为一个数组vec，使用上面两个函数，获取该数组的最大值与最小值。同时，其提供的max()、min()函数，可以比较两个数大小。

#include <algorithm> // 包含算法库
#include <vector>
#include <iostream>
using namespace std;

//获取最大值与最小值
int main()
{
	std::vector<int> vec = { 5, 3, 9, 1, 4, 10, 0, 0 };

	// 找到最小元素的迭代器
	auto min_it = std::min_element(vec.begin(), vec.end());
	std::cout << "最小元素: " << *min_it << std::endl;

	// 找到最大元素的迭代器
	auto max_it = std::max_element(vec.begin(), vec.end());
	std::cout << "最大元素: " << *max_it << std::endl;

	cout << std::max(30, 18) << endl;

	cout << std::min(30, 18) << endl;

	system("pause");

	return 0;
}

2.2 数组排序

<algorithm>库提供了sort函数用于对容器内的元素进行排序，而reverse函数用于将容器内的元素顺序颠倒。这两个函数经常一起使用，以满足不同的排序需求。注意，第一次使用sort，其对容器内元素进行升序排序，再使用一次，则是降序排序。另外，使用reverse时，其将容器颠倒过来。如果reverse之前是升序，那么操作reverse后变为降序；若reverse之前为降序，那么reverse之后为升序。

#include <iostream>
#include <vector>
#include <algorithm> // 引入sort和reverse函数

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

	// 升序排序
	std::sort(numbers.begin(), numbers.end());
	std::cout << "升序排序后的数组: ";
	for (int num : numbers) {
		std::cout << num << " ";
	}
	std::cout << std::endl;

	// 降序排序
	std::sort(numbers.rbegin(), numbers.rend());
	std::cout << "降序排序后的数组: ";
	for (int num : numbers) {
		std::cout << num << " ";
	}
	std::cout << std::endl;

	// 颠倒顺序
	std::reverse(numbers.begin(), numbers.end());
	std::cout << "颠倒顺序后的数组: ";
	for (int num : numbers) {
		std::cout << num << " ";
	}
	std::cout << std::endl;
	system("pause");

	return 0;
}

初始容器无序，经过sort()处理后，变为升序，也就是sort()默认是进行升序处理。后面再进行sort()处理，变为降序处理。降序处理后，经过reverse()处理后，又变为升序。因此，其实可以使用两次sort()达到降序目的。

2.3 查找

使用 std::find() 算法可以查找容器中第一次出现指定值的元素。如下，给出一个数组，里面包含多个5，但其只返回第一次出现5的索引号，即4。

#include <iostream>
#include <vector>
#include <algorithm> // 引入 std::find

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

	// 查找值 5
	auto it = std::find(numbers.begin(), numbers.end(), 5);

	if (it != numbers.end()) {
		std::cout << "找到值 " << *it << " 在位置: " << std::distance(numbers.begin(), it) << std::endl;
	}
	else {
		std::cout << "未找到值 5" << std::endl;
	}
	system("pause");

	return 0;
}

2.4 删除操作

2.4.1 删除指定索引位置元素

在数据处理中，经常有删除指定索引位置处的元素，如下代码，将索引为2，对应的元素3删掉，后续容器中只有1、2、4、5

#include <iostream>
#include <vector>

int main() {
	std::vector<int> vec = { 1, 2, 3, 4, 5 };
	size_t index_to_erase = 2; // 假设我们要删除索引为2的元素，即3

	if (index_to_erase < vec.size()) {
		vec.erase(vec.begin() + index_to_erase);
	}

	// 打印结果
	std::cout << "Vector after erasing element at index " << index_to_erase << ": ";
	for (int num : vec) {
		std::cout << num << " ";
	}
	std::cout << std::endl;
	system("pause");

	return 0;
}

2.4.2 删除指定值元素

有时候，需要删除指定元素值，如下，对于原始容器，希望将元素值为3的所有元素删除。

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

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

	// 使用 remove 将值移动到数组开头，返回最后一个有效元素的指针
	std::vector<int>::iterator new_end = std::remove(arr.begin(), arr.end(), value_to_remove);

	// 使用 erase 移除不再使用的元素
	arr.erase(new_end, arr.end());

	// 打印结果
	std::cout << "Array after removing value " << value_to_remove << ": ";
	for (std::vector<int>::iterator it = arr.begin(); it != arr.end(); ++it) {
		std::cout << *it << " ";
	}
	std::cout << std::endl;
	system("pause");

	return 0;
}