c++ - 比较 vector 并删除所有元素都已在另一个 vector 中的 vector

Question

我使用 vector 的 vector 来存储 id-numbers，我想比较所有这些并删除其中所有值都已经在另一个元素中的元素。

假设我的 vector 中有 4 个这样的元素

[[1, 2, 3, 4], [1, 2, 3], [3], [1,2,3,5]]

在此示例中，应删除第二个和第三个元素。

解决这个问题最快的算法是什么？

Answer 1

这是一种可能的解决方案。

#include <vector>
#include <map>
#include <iostream>
#include <algorithm>

typedef std::vector<int> VI;
typedef std::vector<std::vector<int>> VVI;

VVI DeleteDups(VVI vvi) {
  std::map<int,int> map;

  for(auto const& vi : vvi)
    for(auto const& i : vi)
      ++map[i];

  vvi.erase(
    std::remove_if(begin(vvi), end(vvi),
      [&map](const VI& vi)->bool {
        for(int i : vi)
          if(map[i] == 1) return false;
        return true;
      }),
    end(vvi));
  return vvi;
}

void Dump(const VVI& vvi) {
  std::cout << "[";
  for(auto const& vi : vvi) {
    std::cout << "[";
    for(int i : vi)
      std::cout << i << ", ";
    std::cout << "], ";
  }
  std::cout << "]\n";
}

int main () {
  Dump(DeleteDups({ {1,2,3,4}, {1,2,3}, {3}, {1,2,3,5} }));
}