优雅的方式来删除包含在另一个向量中的矢量的所有元素? [英] elegant way to remove all elements of a vector that are contained in another vector?
问题描述
在查看一些代码时,我发现std :: set_difference
:
While looking over some code I found loopy and algorithmically slow implementation of std::set_difference :
for(int i = 0; i < a.size(); i++)
{
iter = std::find(b.begin(),b.end(),a[i]);
if(iter != b.end())
{
b.erase(iter);
}
}
排序)+ set_difference,但这需要分配新的内存(请参阅我最近的问题可以将设置差异的输出存储在第一个输入吗?为什么它不能完成inplace。)
所以我的解决方案是:
It can be easily replaced with sort(vectors are not sorted) + set_difference, but that requires allocation of new memory(see my recent Q Can output of set difference be stored in first input? why it cant be done "inplace").
So my solution would be something like:
sort(a.begin(), a.end());
for(size_t i = 0; i < b.size(); i++)
{
if (binary_search(a.begin(), a.end(), b[i]))
{
swap(b[i], b[b.size()-1]); //remove current element by swapping with last
b.pop_back(); // and removing new last by shrinking
}
}
做得更优雅?
优雅是主观的,所以在这个范围内Q被定义为更清晰的代码(理想情况下,从STL算法,但我认为它不能做),但没有内存分配和没有增加alg复杂性。
can it be done more elegantly?
elegant is subjective so within scope of this Q is defined as clearer code(ideally something from STL algorithms but I think it cant be done) but with no memory allocation and no increase in alg complexity.
推荐答案
这一个在O(N + M)中做,假设两个数组都排序。
$ b
This one does it in O(N+M), assuming both arrays are sorted.
auto ib = std::begin(two);
auto iter = std::remove_if (
std::begin(one), std::end(one),
[&ib](int x) -> bool {
while (ib != std::end(two) && *ib < x) ++ib;
return (ib != std::end(two) && *ib == x);
});
这篇关于优雅的方式来删除包含在另一个向量中的矢量的所有元素?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!