3

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

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

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

例如，这里：

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

结果向量将是：

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

当我开始使用 C++ 时，我真的不知道如何有效地做到这一点。我在这里的其他答案中发现了擦除/删除习语，这在这里似乎不太合适，除非通过将擦除闭包作为谓词传递。这在 C++ 中似乎并不习惯。

请注意，保持原始顺序无关紧要，每个集合中值的顺序也无关紧要。

4

1 回答 1

1

鉴于我到目前为止所学到的知识，感谢您非常有用的评论，我想出的解决方案是：

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，std::list它对任何地方的元素删除都进行了优化。

这似乎按预期工作，尽管我需要更多测试来证明这一点。下一步将使用比 更有效的比较函数includes，这将考虑到每个向量都是按词法排序的事实（程序保证）。我明天试试这个。

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

谢谢大家。

于 2013-09-24T17:30:07.103 回答