algorithm

<algorithm> 提供了大量通用算法，用于排序、查找、遍历、重排、统计等场景。

这些算法通过迭代器工作，因此可以复用到 vector、list、deque、数组等多种容器上。

头文件与思想

#include <algorithm>

算法库强调“算法与容器分离”：

1. 容器负责存数据。
2. 算法负责处理数据。
3. 两者通过迭代器协作。

常见算法分类

分类	常见算法
查找	find, count, binary_search
排序	sort, stable_sort, partial_sort
重排	reverse, rotate, random_shuffle
最值	min_element, max_element
拷贝	copy, swap
范围比较	equal, lexicographical_compare

遍历与查找

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

int main() {
	std::vector<int> nums;
	nums.push_back(3);
	nums.push_back(1);
	nums.push_back(4);
	nums.push_back(1);

	std::vector<int>::iterator it = std::find(nums.begin(), nums.end(), 4);
	if (it != nums.end()) {
		std::cout << "found 4" << '\n';
	}

	std::cout << "count(1) = " << std::count(nums.begin(), nums.end(), 1) << '\n';
	return 0;
}

排序与二分

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

int main() {
	std::vector<int> nums;
	nums.push_back(5);
	nums.push_back(2);
	nums.push_back(9);
	nums.push_back(1);

	std::sort(nums.begin(), nums.end());

	bool ok = std::binary_search(nums.begin(), nums.end(), 2);
	std::cout << (ok ? "yes" : "no") << '\n';

	return 0;
}

二分相关算法要求区间已按同一规则排序。

自定义比较器

#include <algorithm>
#include <vector>

struct Greater {
	bool operator()(int a, int b) const {
		return a > b;
	}
};

int main() {
	std::vector<int> nums;
	nums.push_back(1);
	nums.push_back(3);
	nums.push_back(2);

	std::sort(nums.begin(), nums.end(), Greater());
	return 0;
}

与容器成员函数的关系

不是所有容器都适合所有算法：

1. std::sort 需要随机访问迭代器，不能直接用于 list。
2. list 有自己的成员函数 list::sort()。
3. 关联容器（如 set、map）元素有序且键只读，很多“改值重排”算法不适用。

使用注意

1. 算法通常操作半开区间 [first, last)。
2. 写算法时先确认迭代器类别是否满足要求。
3. 对有序算法（binary_search, lower_bound 等）必须先保证排序前提。