C++，快速从一个向量中移除另一个向量中独有的元素

Question

C++，快速从一个向量中移除另一个向量中独有的元素

3

有两个未排序的int向量和一个pair 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

- justik

对于这些向量，是否可以对其中一个进行排序，或者它们必须保持原有的顺序？ - Matteo Italia

v1和v2中有一个比另一个大很多吗？ - Robᵩ

@ Rob：它们长度大致相同（+-30%）。 - justik

2个回答

1

假设两个容器都没有排序，而且排序实际上太昂贵或内存不足：

v1.erase(std::remove_if(v1.begin(), v1.end(), 
                        [&v2](int i) { 
                         return std::find_if(v2.begin(), v2.end(), 
                                             [](const std::pair<int, float>& p) { 
                                                return p.first == i; }) 
                                != v2.end() }), v1.end());

或者对v2按first进行排序，然后使用二分搜索。如果有足够的内存，可以使用unordered_set来对v2的first进行排序。

C++03完整版本：

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

struct find_func {
  find_func(int i) : i(i) {}

  int i;
  bool operator()(const std::pair<int, float>& p) {
    return p.first == i;
  }
};

struct remove_func {
  remove_func(std::vector< std::pair<int, float> >* v2) 
  : v2(v2) {}
  std::vector< std::pair<int, float> >* v2;
  bool operator()(int i) {
    return std::find_if(v2->begin(), v2->end(), find_func(i)) != v2->end();
  }
};


int main()
{
  // c++11 here
  std::vector<int> v1 = {5, 3, 2, 4, 7, 8};
  std::vector< std::pair<int, float> > v2 = {{2,8}, {7,10}, {5,0}, {8,9}};
  v1.erase(std::remove_if(v1.begin(), v1.end(), remove_func(&v2)), v1.end());

  // and here
  for(auto x : v1) {
    std::cout << x << std::endl;
  }

  return 0;
}

- pmr

2

这是O(n^2)的，对于数百万个项目来说会非常慢。 - interjay

@interjay，这就是为什么我说：排序太昂贵，内存稀缺。有时候，构建一个具有比普通数组更高的内存开销的数据结构是不可能的，我也提供了更快的解决方案。 - pmr

@ pmr 谢谢，有没有不用 lambda 表达式的解决方案？ - justik

@justik 只需将lambda包装在一个带有一些闭包模拟的函数对象中即可。我会处理好它的。 - pmr

很抱歉，我没有使用lambda表达式的经验 :-(。 - justik

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

有两个技巧可以尽可能快地完成这一操作：

使用某种关联容器（可能是 std::unordered_set）来存储第二个向量中的所有整数，以使查找第一个向量中应删除的整数变得更加高效。
优化从初始向量中删除元素的方式。

具体而言，我会这样做。首先创建一个 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）。

如果允许对第二个向量（也就是pairs）进行排序，则可以使用以下方法以最坏情况下O（nlog n）的时间复杂度和O（log n）的空间复杂度解决问题：首先按键对向量进行排序，然后使用std::binary_search检查第一个向量中的特定int是否应该被删除。每次二分查找的时间复杂度为O（log n），所以总体时间复杂度为O（nlog n）：排序的时间复杂度为O（nlog n），第一个向量中每个元素的时间复杂度为O（log n）（总计O（nlog n）），然后再花费O（n）的时间进行删除操作。

希望这能帮到您！