C++，从另一个 vector 唯一的 vector 中快速删除元素

Question

有 2 个未排序的 int vector 和对 int vector ，int

std::vector <int> v1;
std::vector <std::pair<int, float> > v2;

包含数百万个项目。

如何尽快从 v1 中删除 v2.first 独有的此类项目(即不包含在 v2.first 中)？

例子:

v1:  5 3 2 4 7 8
v2: {2,8} {7,10} {5,0} {8,9}
----------------------------
v1: 3 4

Answer 1

我会使用两个技巧来尽快完成此操作:

1. 使用某种关联容器(可能是 std::unordered_set)将所有整数存储在第二个 vector 中，以显着提高查找是否存在某个整数的效率应该删除第一个 vector 。

2. 优化从初始 vector 中删除元素的方式。

更具体地说，我将执行以下操作。首先创建一个 std::unordered_set 并将来自第二个 vector 的对中的第一个整数的所有整数相加。这给了(预期的)O(1) 查找时间来检查集合中是否存在特定的 int。

既然您已完成该操作，请使用 std::remove_if 算法从哈希表中存在的原始 vector 中删除所有内容。您可以使用 lambda 来执行此操作:

std::unordered_set<int> toRemove = /* ... */
v1.erase(std::remove_if(v1.begin(), v1.end(), [&toRemove] (int x) -> bool {
    return toRemove.find(x) != toRemove.end();
}, v1.end());

将所有内容存储在 unordered_set 中的第一步预计需要 O(n) 时间。第二步通过将所有删除聚集到最后并使查找花费很少的时间来完成预期的 O(n) 工作。这给出了整个过程的总预期 O(n) 时间，O(n) 空间。

如果允许您对第二个 vector (对)进行排序，那么您也可以在 O(n log n) 最坏情况时间、O(log n) 最坏情况空间中通过按键，然后使用 std::binary_search 检查第一个 vector 中的特定 int 是否应该被删除。每个二进制搜索都需要 O(log n) 时间，因此排序所需的总时间为 O(n log n)，第一个 vector 中每个元素的 O(log n) 时间(总共为 O(n log n) ), 和 O(n) 的删除时间，总共 O(n log n)。

希望这对您有所帮助!