我是向量的向量，每个向量代表一个集合（在数学意义上）。例如：
{{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 ++中，这似乎并不是真正的习惯用法。
请注意，保持原始顺序并不重要，每个集合内的值顺序也不重要。
鉴于我学会为止，由于你非常有益的意见，我想出了解决的办法是：
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已经照顾到这个事实。好极了！
谢谢大家。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句