如何筛选相对于其他的向量元素？ [英] How to filter vector elements relative to other ones?

问题描述

余矢量的矢量，每个重新presenting氨基酸组（在数学意义上）。例如：

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}

将所得的载体随后将是：

The resulting vector would then be:

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

正如我开始用C ++真的没有对如何有效地做到这一点的任何线索。我发现，在其他的答案，擦除/删除成语，这似乎并不很适合来这里，除了通过传递抹去的封盖，predicate。这似乎并没有在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 ::矢量按的std ::列表这是更优化元素移除任何地方。

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 ::包括已经注意到了这一事实护理。耶！

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

谢谢大家。

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