如何相对于其他矢量元素过滤？ [英] How to filter vector elements relative to other ones?

问题描述

I是向量的向量，每个向量表示一个集合（在数学意义上）。例如：

I a vector of vectors, each representing a a set (in the mathematical sense). For example:

{{1, 3}, {4, 9, 14}, {1, 3}, {1, 4, 8, 9, 10, 14, 16}, {1, 3, 9}, {4, 9, 17, 22}}

我想使最高效的C ++可能的函数能够过滤（如果可能的话）向量，以删除包含另一个的每个项目。

I want to make the most efficient C++ possible function capable of filtering (in place, if possible) the vector in order to remove every item that contains another.

例如：

• {1,3} 包含在 {1，3} 和 {1,3,9}


• {4，9，14} 包含在 {1,4,8,9,10,14,16}

• {1, 3} is contained by {1, 3} and {1, 3, 9}
• {4, 9, 14} is contained by {1, 4, 8, 9, 10, 14, 16}

结果向量将是：

{{1, 3}, {4, 9, 14}, {4, 9, 17, 22}}

在我开始使用C ++时，并没有真正有效的方法。我发现，在其他答案在这里，擦除/删除成语，这似乎不是非常适合这里，除了通过擦除闭包作为谓词。这在C ++中似乎并不真实。

As I'm beginning with C++ don't really have any clue of how to do this efficiently. I found, on other answers here, the erase / remove idiom, which doesn't seem to be very appropriate here, except by passing erase a closure as predicate. Which doesn't seem really idiomatic in C++.

请注意，保持原始顺序并不重要，每个集合内部的值的顺序也不重要。

Please note that keeping the original ordering doesn't matter, nor does the ordering of values inside each set.

推荐答案

鉴于我到目前为止学到的东西，感谢你有用的评论，我想出的解决方案是：

Given what I learnt so far, thanks to your very helpful comments, the solution I came up with is:

struct std::vector<size_t> colset;

bool less_colsets(const colset& a, const colset& b) {
  return a.size() < b.size();
}

void sort_colsets(std::list<colset>& l) {
  l.sort(less_colsets);
}

void strip_subsets(std::list<colset>& l) {
  sort_colsets(l);
  for (std::list<colset>::iterator i = l.begin(); i != l.end(); ++i) {
    std::list<colset>::iterator j = next(i, 1);
    while (j != l.end()) {
      if (includes((*j).begin(), (*j).end(), (*i).begin(), (*i).end())) {
        j = l.erase(j);
      }
      else {
        ++j;
      }
    }
  }
}

我替换了最外面的 std :: vector by std :: list 这是更加优化的元素删除任何地方。

Note that I replaced the outermost std::vector by std::list which is much more optimised for element removal anywhere.

这似乎工作正常，虽然我需要一些更多的测试来证明这一点。 下一步将是使用比包括更有效的比较函数，这将考虑每个向量是词法顺序的事实（程序保证） 。我会明天试试。

This seems to work as expected, though I'd need some more tests to prove this. The next step will be to use a more efficient comparison function than includes, which would take into account the fact that each vector is lexically ordered (which the program guarantees). I'll try this tomorrow.

编辑：看起来像 std :: includes 已经处理了这个事实。 YAY！

Edit: Looks like std::includes already takes care of this fact. YAY!

感谢大家。

这篇关于如何相对于其他矢量元素过滤？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！