C++,快速从另一个向量唯一的向量中删除元素

Question

有两个int的未分类向量和对int,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)来存储第二个向量中的所有整数,以便更有效地查找是否应该删除第一个向量中的某个整数.

2. 优化从初始向量中删除元素的方式.

更具体地说,我会做以下事情.首先创建一个std::unordered_set并添加第二个向量中该对中第一个整数的所有整数.这给出了(预期的)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)空间的总和.

如果你被允许对第二个向量(对)进行排序,那么你也可以在O(n log n)最坏情况时间,O(log n)最坏情况空间中通过按键对向量进行排序,然后通过std::binary_search检查是否一个特定的int从第一vector应该被淘汰与否.每个二进制搜索需要O(log n)时间,因此所需的总时间为排序的O(n log n),第一个向量中每个元素的O(log n)时间(总计为O(n log n)) )和O(n)删除时间,总共给出O(n log n).

希望这可以帮助!