c++：算法（Algorithms）

目录

常用 STL 算法 

1️⃣ std::sort（排序）

2️⃣ std::find（查找等于某值的元素）

3️⃣ std::count（统计出现次数）

4️⃣ std::next（获取迭代器的下一个位置） 

 5️⃣ .erase()（容器中物理删除）

 6️⃣ std::remove（逻辑删除某值）

7️⃣ std::unique（去除连续重复元素） 

8️⃣ std::accumulate（累加求和）

9️⃣ std::unique + erase（去重）

🔟 std::remove + erase（删除指定元素）

1️⃣1️⃣ std::lower_bound / upper_bound（二分查找位置）

1️⃣2️⃣ std::for_each（遍历元素）

1️⃣3️⃣ std::reverse（翻转）

1️⃣4️⃣ std::copy（拷贝）

1️⃣5️⃣ std::prev（获取迭代器的上一个位置）

一般使用的算法 

🛠️ 使用STL算法的技巧与注意事项

---

C++ STL（标准模板库）中的算法是 STL 的三大核心组成之一，另外两个是 容器 和 迭代器。STL 提供了大量的泛型算法，这些算法不依赖于特定容器，而是通过迭代器操作容器中的元素。这一设计体现了 STL 的高度抽象性和复用性。

常用 STL 算法 

1️⃣ std::sort（排序）

对支持随机访问的容器排序（如 vector, array）。

std::sort(vec.begin(), vec.end()); // 默认升序
std::sort(vec.begin(), vec.end(), std::greater<int>()); // 降序

2️⃣ std::find（查找等于某值的元素）

顺序查找容器中是否包含某个元素，返回迭代器指向第一个等于目标值的位置，找不到则返回 end()。

auto it = std::find(vec.begin(), vec.end(), 10);
if (it != vec.end()) std::cout << "Found!";

3️⃣ std::count（统计出现次数）

统计某个值在容器中出现的次数。

int cnt = std::count(vec.begin(), vec.end(), 5);

4️⃣ std::next（获取迭代器的下一个位置） 

适用于任意迭代器类型（包括 list 的 bidirectional_iterator） ，比直接 + 更通用，泛型更强

auto it = std::next(vec.begin(), 3); // 相当于 vec.begin() + 3

 5️⃣ .erase()（容器中物理删除）

成员函数，真正从容器中删除元素。 

用于配合 remove, unique 等 STL 算法。 

对于 map, set 也有 .erase(key) 版本。 

vec.erase(vec.begin() + 2); // 删除第三个元素vec.erase(vec.begin() + 1, vec.begin() + 4); // 删除索引1到3的元素（左闭右开）vec.erase(std::remove(vec.begin(), vec.end(), val), vec.end()); // 删除所有val

 6️⃣ std::remove（逻辑删除某值）

并不删除元素，而是将非目标值前移。返回新末尾位置。需结合 .erase() 实现物理删除。 

auto it = std::remove(vec.begin(), vec.end(), 3); // 将值为3的元素移动到末尾
vec.erase(it, vec.end()); // 物理删除尾部冗余

• 并不真正删除，只是将非3的元素往前挪。

• 常与 .erase() 一起使用。

• 时间复杂度：O(n)。

7️⃣ std::unique（去除连续重复元素） 

删除连续重复元素（如 1,1,2,2 → 1,2）。若容器未排序，应先 sort。 

std::sort(vec.begin(), vec.end()); // 先排序以保证重复元素相邻
auto it = std::unique(vec.begin(), vec.end());
vec.erase(it, vec.end()); // 真正删除尾部重复数据

• 只去除相邻的重复元素，所以通常要先 sort。

• 返回值是“新逻辑末尾”，你仍需用 .erase() 实际删除。

• 时间复杂度：O(n)。

8️⃣ std::accumulate（累加求和）

【需引入 <numeric>】 

计算从 begin() 到 end() 的总和，支持设置初始值和自定义运算（如乘积）。 

#include <numeric>
int sum = std::accumulate(vec.begin(), vec.end(), 0); // 初始值为 0

9️⃣ std::unique + erase（去重）

仅移除连续重复元素，常配合 sort 使用。

std::sort(vec.begin(), vec.end());
auto it = std::unique(vec.begin(), vec.end());
vec.erase(it, vec.end()); // 真正删除

🔟 std::remove + erase（删除指定元素）

排序后，unique 删除重复，erase 移除多余尾部元素。  

auto it = std::remove(vec.begin(), vec.end(), 3); // 把所有3挤到后面
vec.erase(it, vec.end()); // 真正删除

1️⃣1️⃣ std::lower_bound / upper_bound（二分查找位置）

要求容器有序！常用于二分查找、查找插入位置、区间统计等。

auto lb = std::lower_bound(vec.begin(), vec.end(), 5); // 第一个 >= 5 的位置
auto ub = std::upper_bound(vec.begin(), vec.end(), 5); // 第一个 > 5 的位置

1️⃣2️⃣ std::for_each（遍历元素）

遍历并对每个元素执行操作，推荐结合 lambda 使用，使代码更简洁。 

std::for_each(vec.begin(), vec.end(), [](int x) {std::cout << x << " ";
});

1️⃣3️⃣ std::reverse（翻转）

将容器内的元素顺序完全翻转。适合回文判断、逆序操作等场景。 

std::reverse(vec.begin(), vec.end());

1️⃣4️⃣ std::copy（拷贝）

将一个区间的元素复制到另一个容器或内存区域中，目标区间必须提前分配好空间。 

std::vector<int> dest(vec.size());
std::copy(vec.begin(), vec.end(), dest.begin());

1️⃣5️⃣ std::prev（获取迭代器的上一个位置）

auto it = std::prev(vec.end());        // 指向最后一个元素
auto it2 = std::prev(vec.end(), 3);    // 向前偏移3个位置

std::prev 返回给定迭代器前面第 n 个位置的迭代器，默认 n = 1。

适用于所有双向迭代器及以上，如 list, vector, set 等。

相比 --it 或 it - 1，它是更泛型、安全的做法，适合模板代码与泛型编程。

---

一般使用的算法 

算法	简要说明
std::find_if	查找第一个满足条件的元素
std::all_of / any_of / none_of	所有、任意、无元素满足条件（通常配合 lambda）
std::replace	替换某个值为另一个值
std::fill	填充区间为某值
std::equal	比较两个区间是否相等
std::is_sorted	判断是否有序
std::max_element / min_element	返回最大/最小元素的迭代器
std::partition	将容器按条件分区（不稳定）
std::next_permutation	得到下一个字典序排列（常用于全排列）

🛠️ 使用STL算法的技巧与注意事项

1. 熟练使用 Lambda 表达式：许多算法支持自定义的谓词（predicate），使用 lambda 表达式可以大大简化代码。

2. 理解迭代器语义：算法通过迭代器实现泛型化。你必须理解迭代器区间是 [first, last)。

3. 与容器成员函数区别：有些容器自带 sort()（如 list），而 std::sort() 只能用于 RandomAccessIterator（如 vector）。

4. 注意返回值的处理：很多算法返回的是迭代器，如 find, remove, partition。