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 删除算法

STL 删除算法是 C++ 标准库中的一类算法，它们用于从容器中删除元素。常用的删除算法包括 remove、remove_if、unique 等。
删除算法广泛应用于容器中元素的移除、重复元素的去重等操作。

算法名称	功能描述	时间复杂度	空间复杂度	适用场景
remove	删除容器中指定值的元素（逻辑删除，需要容器的内部函数erase）	O(n)	O(1)	删除容器中的指定值元素
remove_if	删除容器中满足条件的元素（逻辑删除，需要 erase）	O(n)	O(1)	根据条件删除容器中的元素
unique	删除相邻重复的元素（逻辑删除，需要 erase）	O(n)	O(1)	删除相邻重复的元素（去重）
erase	直接删除容器中指定值的元素（C++20）	O(n)	O(1)	简化版的删除指定值元素
erase_if	直接删除容器中满足条件的元素（C++20）	O(n)	O(1)	根据条件直接删除容器中的元素

（1）remove

• 功能：将容器中所有等于指定值的元素移除，并返回指向新序列的末尾后一位置的迭代器。
  注意，remove 并不会真正删除元素，而是将这些元素“移动”到容器末尾，并返回一个新的逻辑结束位置。要实际删除这些元素，还需要配合 erase 方法使用。
• 时间复杂度：O(n)，其中 n 是容器中的元素数量。
• 空间复杂度：O(1)，原地操作。

示例：

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>int main() {vector<int> vec = { 1, 2, 3, 2, 4 };// 删除所有值为 2 的元素vec.erase(remove(vec.begin(), vec.end(), 2), vec.end());cout << "删除后: ";for (int val : vec){cout << val << " ";}cout << endl;system("pause");return 0;
}

注意：

• remove适用于，当需要从容器中删除指定值的元素时。

（2）remove_if

• 功能：根据指定的条件删除容器中的元素。该算法将所有满足条件的元素移除，并返回指向新序列的末尾后一位置的迭代器。
  与 remove 类似，remove_if 不会真正删除元素，需要配合 erase 使用。
• 时间复杂度：O(n)，其中 n 是容器中的元素数量。
• 空间复杂度：O(1)，原地操作。

示例：

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>bool is_even(int n)
{return n % 2 == 0;
}int main() {vector<int> vec = { 1, 2, 3, 4, 5 };// 删除所有偶数元素vec.erase(remove_if(vec.begin(), vec.end(), is_even), vec.end());cout << "在 remove_if删除后: ";for (int val : vec) {cout << val << " ";}cout << endl;system("pause");return 0;
}

注意：

• remove_if适用于，当需要根据条件删除容器中的元素时。

（3） unique

• 功能：删除容器中的相邻重复元素，只保留一个重复元素，返回指向去重后的末尾的迭代器（即末尾元素的后一位置）。
  注意，unique 只去除相邻的重复元素，如果容器中的元素不相邻，则不做任何操作。unique 通常与 erase 配合使用来移除元素。
• 时间复杂度：O(n)，其中 n 是容器中的元素数量。
• 空间复杂度：O(1)，原地操作。

示例：

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>int main() {vector<int> vec = { 1, 1, 2, 2, 3, 3, 4 };// 去除相邻重复的元素vec.erase(unique(vec.begin(), vec.end()), vec.end());cout << "在 unique去重后: ";for (int val : vec){cout << val << " ";}cout << endl;system("pause");return 0;
}

注意：

• unique适用于，当需要删除相邻重复元素时。

（4）erase（C++20）

• 功能：从容器中直接删除元素，简化了 remove 和 erase 的组合使用，适用于标准容器（如 vector, deque, list 等）。
• 时间复杂度：O(n)，其中 n 是容器中的元素数量。
• 空间复杂度：O(1)。

示例：

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>int main() {vector<int> vec = { 1, 2, 3, 2, 4 };// C++20 中直接使用 erase 删除值为 2 的元素erase(vec, 2);cout << "After erase: ";for (int val : vec){cout << val << " ";}cout << endl;system("pause");return 0;
}

注意：

• erase用于直接删除容器中的元素。

（5）erase_if（C++20）

• 功能：根据指定条件直接删除满足条件的元素，简化了 remove_if 和 erase 的组合使用。
• 时间复杂度：O(n)，其中 n 是容器中的元素数量。
• 空间复杂度：O(1)。

示例：

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>bool is_even(int n) 
{return n % 2 == 0;
}int main() {vector<int> vec = { 1, 2, 3, 4, 5 };// C++20 中直接使用 erase_if 删除偶数元素erase_if(vec, is_even);cout << "erase_if后: ";for (int val : vec){cout << val << " ";}cout << endl;system("pause");return 0;
}

注意：

• erase_if用于根据条件直接删除容器中的元素。