如何相对于其他矢量元素过滤？

问题描述

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.

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

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

感谢大家。

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