C++ 中从 unordered_multiset 中擦除满足给定条件的元素

引言

unordered_multiset 是 C++ 标准库 的一部分，定义在 <unordered_set> 头文件中。它是一个关联容器，允许存储具有相同值的多个元素，并且这些元素不按特定顺序排列。与通常实现为二叉搜索树的 std::set 或 std::multiset 不同，unordered_multiset 使用哈希表实现，为 插入、 删除和查找提供了平均常数时间复杂度。

unordered_multiset 的特性

基于哈希表： 元素根据其哈希值存储在桶中，这使得 插入和查找 具有快速的平均时间复杂度。

多元素： 它可以存储具有相同值的多个元素（即允许重复）。

无序： 元素不按任何特定顺序存储。

用例

根据特定条件删除元素是在处理 unordered_multiset 等容器时常见的操作。例如，您可能希望删除所有满足特定谓词的元素，例如所有偶数或所有特定长度的字符串。

要根据条件从 unordered_multiset 中删除元素，您可以使用标准库算法和容器的成员函数相结合的方式。

迭代容器： 使用迭代器遍历 unordered_multiset。

检查条件： 对于每个元素，检查它是否满足给定的 条件。

删除元素： 如果满足条件，则从容器中删除该元素。

方法一：使用迭代器进行迭代删除

此方法涉及手动遍历 unordered_multiset 并删除满足特定条件的元素。关键在于在删除元素时正确处理迭代器，以确保它们在整个操作过程中保持有效。

模板参数

该函数使用模板参数来处理不同类型的 unordered_multiset，适应各种元素类型、哈希函数和相等运算符。

谓词灵活性

谓词可以是 lambda 函数、函数指针或函数对象，从而在定义 元素移除 的条件方面提供了灵活性。

迭代器管理

该函数仔细管理迭代器，以确保在每次删除操作后它仍然有效。erase 方法 返回指向下一个元素的迭代器，从而避免了失效问题。

程序

输出

After removing even numbers: 9 7 5 3 1 
After removing short strings: grape, cherry banana apple 
After removing people older than 30: David (25) Bob (25) Alice (30)

解释

提供的代码演示了如何使用迭代器进行迭代删除的方法，根据特定条件从 unordered_multiset 中 删除元素。它展示了三个示例：删除偶数整数、删除 短字符串 和删除代表超过特定年龄的人的自定义对象。关键函数是 erase_if，它遍历 容器 并删除满足给定谓词的元素。

• 模板函数 erase_if

erase_if 函数是模板化的，可以接受具有特定元素类型、哈希函数和键相等函数的 unordered_multiset。

该函数使用 迭代器 遍历容器。对于每个元素，它会检查 谓词（用户定义的条件）是否返回 true。如果为 true，它会删除该元素并更新迭代器到 下一个有效位置。如果为 false，它只需将迭代器递增到下一个元素。这确保了即使在删除元素时，迭代也能保持有效且高效。

• 删除偶数整数

创建了一个整数的 unordered_multiset。lambda 函数 is_even 用于检查整数是否为偶数。调用 erase_if 函数，传入整数集和 is_even 谓词。打印剩余元素，只显示奇数。

• 删除短字符串

初始化了一个字符串的 unordered_multiset。lambda 函数 is_short 用于确定字符串长度是否小于五个字符。调用 erase_if 函数，传入字符串集和 is_short 谓词。输出显示了长度为五或更多字符的 字符串，已删除 较短的字符串。

• 删除自定义对象

name 和 age 属性以及相等运算符定义了一个 person 结构体。提供了自定义哈希函数 PersonHash，用于 哈希 Person 对象，基于它们的 name 和 age。创建了一个 Person 对象的 unordered_multiset。

lambda 函数 is_older_than_30 用于检查 person 的 age 是否大于 30。使用 erase_if 函数从集合中删除年龄大于 30 的 person。打印剩余元素，显示年龄 30 岁或更小的 person。

复杂度分析

时间复杂度

遍历容器

erase_if 函数中的主要操作是遍历 unordered_multiset 的元素。此迭代的时间复杂度为 O(n)，其中 n 是容器中的元素数量。这是因为每个元素都只被访问一次。

谓词评估

对于每个元素，都会评估谓词。如果谓词函数是 O(1)（这对于检查数字是否为偶数或字符串长度是否低于某个阈值等简单条件通常是如此），则总体时间复杂度保持 O(n)。如果谓词函数更复杂，则需要考虑其复杂度，但对于示例中提供的典型用例，谓词评估 不会显著影响整体复杂度。

删除操作

由于内部使用的哈希表结构，unordered_multiset 中的删除操作平均时间复杂度为 O(1)。这假设哈希函数良好且冲突较少。在最坏的情况下，当许多元素哈希到同一个桶（导致冲突）时，每次删除操作的复杂度可能会下降到 O(n)。但是，使用设计良好的哈希函数和元素的合理分布，平均复杂度为 O(1)。

将这些操作结合起来，erase_if 函数的总体平均时间复杂度保持为 O(n)，因为

遍历所有元素： O(n)

谓词评估： O(n)（如果每次评估都是 O(1)）

删除操作： O(n) * O(1) = 平均 O(n)

空间复杂度

容器存储

unordered_multiset 的主要空间复杂度为 O(n)，其中 n 是容器中存储的元素数量。这个空间是存储元素本身和底层哈希表结构所必需的。

erase_if 中的额外空间

erase_if 函数 本身不使用与输入大小成比例的任何额外空间。该函数使用恒定的额外空间 (O(1)) 用于迭代器和任何临时变量。没有创建依赖于输入大小的额外数据结构。

哈希表开销

在内部，unordered_multiset 维护一个带有桶的哈希表。此结构的存储复杂度也为 O(n)，同时考虑了元素和桶。确切的开销取决于负载因子以及哈希表在 添加或删除 元素时的行为。

特定示例分析

删除偶数整数

时间复杂度： O(n) 用于迭代和检查每个整数。

空间复杂度： O(n) 用于存储整数。

删除短字符串

时间复杂度： O(n) 用于迭代和检查每个字符串的长度。

空间复杂度： O(n) 用于存储字符串。

删除自定义对象

时间复杂度： O(n) 用于迭代和检查每个人的年龄。

空间复杂度： O(n) 用于存储自定义对象和哈希表开销。

方法二：使用 remove_if 算法和 Erase-Remove Idiom

在 C++ 中，使用 remove_if 算法和 erase-remove idiom 是从支持随机访问迭代器的容器（如 std::vector）中删除元素的常用技术。但是，std::unordered_multiset 不直接支持此功能，因为它不提供随机访问迭代器，并且其元素不存储在连续的内存块中。尽管存在此限制，我们仍然可以通过手动遍历容器并删除满足 给定条件 的元素来改编 erase-remove idiom 以适用于 std::unordered_multiset。

在 std::vector 等标准容器中，erase-remove idiom 的工作方式如下：

remove_if 算法

此算法将范围 [first, last) 中的 元素 重新排序，使得不满足给定谓词的元素被移到范围的开头。该算法返回一个指向范围新逻辑末尾（已删除元素开始处）的 迭代器。

erase 方法

然后使用容器的 erase 方法删除由 remove_if 逻辑删除的元素。

在 std::unordered_multiset 等容器中，我们没有随机访问迭代器的便利，因此我们需要调整方法。

程序

输出

Original integer set: 10 9 8 7 6 5 4 3 2 1 
After removing even numbers: 9 7 5 3 1 
Original string set: grape fig date cherry banana apple 
After removing short strings: grape cherry banana apple 
Original person set: David (25) Charlie (35) Bob (25) Eve (40) Alice (30) 
After removing people older than 30: David (25) Bob (25) Alice (30) 
Original float set: 7.2 5.6 8.9 4.1 6.8 3.7 2.3 1.5 
After removing floats greater than 4.0: 3.7 2.3 1.5 

解释

• 模板函数 erase_if

该函数旨在根据给定的条件（谓词）删除 unordered_multiset 中的元素。

模板参数

T：unordered_multiset 中元素的类型。

Hash：unordered_multiset 使用的哈希函数。

KeyEqual：unordered_multiset 使用的相等比较函数。

Predicate：将用于检查每个元素条件的谓词函数的类型。

• 函数参数

container： 一个对 unordered_multiset 的引用，将从中删除元素。

pred： 谓词函数，对于应删除的元素返回 true，否则返回 false。

函数体

该函数使用迭代器遍历 unordered_multiset。对于每个元素，它会检查谓词。如果谓词返回 true，则使用 unordered_multiset 的 erase 方法删除该元素，该方法还会将迭代器更新到下一个元素。如果谓词返回 false，则仅将迭代器递增到下一个元素。

辅助函数 print_set

此函数是用于打印 unordered_multiset 内容的实用程序。它遍历容器并打印每个元素，后跟一个空格。

主函数

main 函数演示了 erase_if 函数在不同类型的 unordered_multiset 和各种谓词下的用法。

示例 1：从整数的 unordered_multiset 中删除偶数

创建一个整数的 unordered_multiset 并用一些值进行初始化。定义一个 lambda 函数 is_even 来检查整数是否为偶数（value % 2 == 0）。打印原始集合。调用 erase_if 函数，传入整数集和 is_even 谓词。打印修改后的集合，即 删除偶数 后的集合。

示例 2：从字符串的 unordered_multiset 中删除短字符串

创建一个字符串的 unordered_multiset 并用一些值进行初始化。定义一个 lambda 函数 is_short 来 检查 字符串的长度是否小于 5 个字符。打印原始集合。调用 erase_if 函数，传入字符串集和 is_short 谓词。打印修改后的集合，即删除短字符串后的集合。

示例 3：从 unordered_multiset 中删除自定义对象

定义一个 Person 结构体，包含 name 和 age 属性，并提供一个相等运算符。定义一个自定义哈希函数 PersonHash，用于根据 name 和 age 对 Person 对象进行哈希。创建一个 Person 对象的 unordered_multiset 并用一些值进行初始化。定义一个 lambda 函数 is_older_than_30，用于检查 person 的 age 是否大于 30。打印原始集合，显示每个 Person 的 name 和 age。调用 erase_if 函数，传入 person 集和 is_older_than_30 谓词。打印修改后的集合，即删除年龄大于 30 的 person 后的集合。

示例 4：删除大于特定阈值的浮点数

创建一个浮点数的 unordered_multiset 并用一些值进行初始化。定义一个 lambda 函数 is_greater_than_4 来检查浮点数是否 大于 4.0。打印原始集合。调用 erase_if 函数，传入 浮点数集 和 is_greater_than_4 谓词。打印修改后的集合，即删除 大于 4.0 的浮点数 后的集合。

复杂度分析

模板函数 erase_if

erase_if 函数旨在根据谓词从 std::unordered_multiset 中删除元素。在这里，我们将分析此函数的时间和空间复杂度。

时间复杂度

遍历元素

该函数使用迭代器遍历 unordered_multiset 中的每个元素。此循环以 O(n) 时间运行，其中 n 是 unordered_multiset 中的元素数量。

谓词评估

对于每个元素，都会评估谓词。假设谓词评估需要恒定时间 O(1)，则跨所有元素评估谓词的总时间为 O(n)。

删除操作

由于 std::unordered_multiset 使用哈希表，允许平均 O(1) 复杂度的插入、删除和查找操作，因此 unordered_multiset 中的删除操作具有平均时间复杂度 O(1)。在最坏的情况下，由于哈希冲突，删除操作的时间复杂度可能会下降到 O(n)，但这很少见，通常不会影响 平均情况分析。

如果我们假设 平均情况，则所有删除操作的总时间为 O(k)，其中 k 是满足谓词的元素数量。由于 k ≤ n，在平均情况下，删除操作的最坏时间复杂度仍然是 O(n)。

将这些因素结合起来，erase_if 函数的总体平均时间复杂度为 O(n)。

空间复杂度

辅助空间

erase_if 函数不使用任何随输入大小扩展的额外数据结构。它直接在给定的 unordered_multiset 上操作，并就地修改它。迭代器和谓词使用的空间是 恒定的 O(1)。

unordered_multiset 内的空间

unordered_multiset 的空间复杂度为 O(n)，因为它需要存储所有元素。这个空间不被认为是算法使用的额外空间，因为它属于输入的一部分。因此，erase_if 函数 的额外空间复杂度为 O(1)，使其成为一个就地操作。