我有两个持有数据对象的向量。每个数据对象都保存坐标和一些其他数据。将始终对矢量进行排序（首先是x坐标，然后是y坐标）。我试图删除两个矢量中具有坐标无法在两个矢量中找到的所有对象。这是我目前正在做的MWE：
#include <iostream>
#include <vector>
#include <algorithm>
struct foo{
foo()=default;
foo(int x, int y, double data):x(x),y(y),data(data){}
int x;
int y;
double data;
};
int main()
{
std::vector<foo> vec1=std::vector<foo>(7);
std::vector<foo> vec2=std::vector<foo>(4);
vec1={foo(1,1,0.),foo(1,2,0.),foo(2,1,0.),foo(2,2,0.),foo(2,3,0.),foo(3,1,0.),foo(3,2,0.)};
vec2={foo(1,2,0.),foo(1,3,0.),foo(2,1,0.),foo(3,1,0.)};
for(auto it1=vec1.begin(); it1!=vec1.end();){
auto cur_element=*it1;
auto intersec = std::find_if(vec2.begin(),vec2.end(),[cur_element]
(foo & comp_element)->bool{
return((cur_element.x==comp_element.x) && (cur_element.y==comp_element.y));
});
if(intersec==vec2.end()) it1=vec1.erase(it1);
else ++it1;
}
for(auto it2=vec2.begin(); it2!=vec2.end();){
auto cur_element=*it2;
auto intersec = std::find_if(vec1.begin(),vec1.end(),[cur_element]
(foo & comp_element)->bool{
return((cur_element.x==comp_element.x) && (cur_element.y==comp_element.y));
});
if(intersec==vec1.end()) it2=vec2.erase(it2);
else ++it2;
}
std::cout<<"vec1:\n";
for(auto i: vec1) std::cout<<i.x<<" "<<i.y<<"\n";
std::cout<<"\nvec2:\n";
for(auto i: vec2) std::cout<<i.x<<" "<<i.y<<"\n";
return 0;
}
它工作，并给我预期的输出。 无论如何，不得不循环遍历两个向量。有没有更有效的方法来实现相同的输出？
编辑：获取两个向量中表示的坐标是不够的。我需要的是从两个向量中删除“错误”对象的有效方法。
你的两个载体已经分类 - 完美！
首先，假设一个比较函数（即将推出的C ++ 20，这将得到太空船运营商......）：
int compare(foo const& l, foo const& r)
{
return l.x != r.x ? l.x - r.x : l.y - r.y;
}
现在您可以在算法中使用它：
auto i1 = v1.begin();
auto i2 = v2.begin();
auto end1 = i1;
auto end2 = i2;
while(i1 != v1.end() && i2 != v2.end())
{
int cmp = compare(*i1, *i2);
if(cmp < 0)
{
// skip element
++i1;
}
else if(cmp > 0)
{
++i2;
}
else
{
// matching element found, keep in both vectors...
if(i1 != end1)
*end1 = std::move(*i1);
++i1;
++end1;
if(i2 != end2)
*end2 = std::move(*i2);
++i2;
++end2;
// if you can rely on move (or fallback copy) assignment
// checking for self assignment, the following simpler
// alternative can be used instead:
//*end1++ = std::move(*i1++);
//*end2++ = std::move(*i2++);
}
}
v1.erase(end1, v1.end());
v2.erase(end2, v2.end());
两个向量中的线性......
该算法只是将元素移动到前面，最后丢弃所有过期的元素 - 就像std::remove_if那样......
我认为这个解决方案是线性的，可以满足您的需求。
可能进一步增强：
data移动便宜，另一种策略是有条件地从输入向量和交换构建输出向量struct foo_less
{
bool operator()(foo const&l, foo const& r) const
{
return std::tie(l.x, l.y) < std::tie(r.x, r.y);
}
};
void remove_non_matching(std::vector<foo>& l, std::vector<foo>& r)
{
constexpr auto less = foo_less();
assert(std::is_sorted(l.begin(), l.end(), less));
assert(std::is_sorted(r.begin(), r.end(), less));
auto lcurrent = l.begin(), rcurrent = r.begin();
while (lcurrent != l.end() && rcurrent != r.end())
{
if (less(*lcurrent, *rcurrent))
lcurrent = l.erase(lcurrent);
else if(less(*rcurrent, *lcurrent))
rcurrent = r.erase(rcurrent);
else
{
++lcurrent;
++rcurrent;
}
}
l.erase(lcurrent, l.end());
r.erase(rcurrent, r.end());
}
替代方法将花费更多内存，但理论上更有效：
void remove_non_matching_alt(std::vector<foo>& l, std::vector<foo>& r)
{
constexpr auto less = foo_less();
assert(std::is_sorted(l.begin(), l.end(), less));
assert(std::is_sorted(r.begin(), r.end(), less));
auto lresult = std::vector<foo>(), rresult = std::vector<foo>();
auto sz = std::min(l.size(), r.size());
lresult.reserve(sz);
rresult.reserve(sz);
auto lcurrent = l.begin(), rcurrent = r.begin();
while (lcurrent != l.end() && rcurrent != r.end())
{
if (less(*lcurrent, *rcurrent))
++lcurrent;
else if(less(*rcurrent, *lcurrent))
++rcurrent;
else
{
lresult.push_back(std::move(*lcurrent++));
rresult.push_back(std::move(*rcurrent++));
}
}
l.swap(lresult);
r.swap(rresult);
}
类似但使用thread_local持久性缓存来避免不必要的内存分配：
void remove_non_matching_alt_faster(std::vector<foo>& l, std::vector<foo>& r)
{
constexpr auto less = foo_less();
assert(std::is_sorted(l.begin(), l.end(), less));
assert(std::is_sorted(r.begin(), r.end(), less));
// optimisation - minimise memory allocations on subsequent calls while maintaining
// thread-safety
static thread_local auto lresult = std::vector<foo>(), rresult = std::vector<foo>();
auto sz = std::min(l.size(), r.size());
lresult.reserve(sz);
rresult.reserve(sz);
auto lcurrent = l.begin(), rcurrent = r.begin();
while (lcurrent != l.end() && rcurrent != r.end())
{
if (less(*lcurrent, *rcurrent))
++lcurrent;
else if(less(*rcurrent, *lcurrent))
++rcurrent;
else
{
lresult.push_back(std::move(*lcurrent++));
rresult.push_back(std::move(*rcurrent++));
}
}
l.swap(lresult);
r.swap(rresult);
// ensure destructors of discarded 'data' are called and prep for next call
lresult.clear();
rresult.clear();
}
这是我的方法，以erase–remove idiom样式，只迭代一次向量：
#include <iostream>
#include <vector>
#include <iterator>
#include <utility>
struct foo
{
foo() = default;
foo(int x, int y, double data) : x(x), y(y), data(data) {}
int x;
int y;
double data;
};
// Maybe better as overloaded operators
int compare_foo(const foo& foo1, const foo& foo2)
{
if (foo1.x < foo2.x) return -1;
if (foo1.x > foo2.x) return +1;
if (foo1.y < foo2.y) return -1;
if (foo1.y > foo2.y) return +1;
return 0;
}
std::tuple<std::vector<foo>::iterator, std::vector<foo>::iterator>
remove_difference(std::vector<foo>& vec1, std::vector<foo>& vec2)
{
typedef std::vector<foo>::iterator iterator;
iterator it1 = vec1.begin();
size_t shift1 = 0;
iterator it2 = vec2.begin();
size_t shift2 = 0;
while (it1 != vec1.end() && it2 != vec2.end())
{
int cmp = compare_foo(*it1, *it2);
if (cmp < 0)
{
++it1;
shift1++;
}
else if (cmp > 0)
{
++it2;
shift2++;
}
else
{
std::iter_swap(it1, std::prev(it1, shift1));
++it1;
std::iter_swap(it2, std::prev(it2, shift2));
++it2;
}
}
return std::make_tuple(std::prev(it1, shift1), std::prev(it2, shift2));
}
int main()
{
std::vector<foo> vec1=std::vector<foo>(7);
std::vector<foo> vec2=std::vector<foo>(4);
vec1={foo(1,1,0.),foo(1,2,0.),foo(2,1,0.),foo(2,2,0.),foo(2,3,0.),foo(3,1,0.),foo(3,2,0.)};
vec2={foo(1,2,0.),foo(1,3,0.),foo(2,1,0.),foo(3,1,0.)};
auto remove_iters = remove_difference(vec1, vec2);
vec1.erase(std::get<0>(remove_iters), vec1.end());
vec2.erase(std::get<1>(remove_iters), vec2.end());
std::cout<<"vec1:\n";
for(auto i: vec1) std::cout<<i.x<<" "<<i.y<<"\n";
std::cout<<"\nvec2:\n";
for(auto i: vec2) std::cout<<i.x<<" "<<i.y<<"\n";
return 0;
}
输出：
vec1:
1 2
2 1
3 1
vec2:
1 2
2 1
3 1
唯一没有的是，这假设没有重复的坐标，或者更具体地说，它们在两个向量上重复相同的次数，并且“额外的”重复将被删除（你可以调整算法来改变它如果你需要，虽然它会使代码有点丑陋）。
也许是这样的？首先选择哪个矢量较大然后迭代（主要）在较大的矢量上并检查另一个矢量。
int main()
{
std::vector<foo> vec1=std::vector<foo>(7);
std::vector<foo> vec2=std::vector<foo>(4);
vec1={foo(1,1,0.),foo(1,2,0.),foo(2,1,0.),foo(2,2,0.),foo(2,3,0.),foo(3,1,0.),foo(3,2,0.)};
vec2={foo(1,2,0.),foo(1,3,0.),foo(2,1,0.),foo(3,1,0.)};
std::vector<foo>::iterator it_begin;
std::vector<foo>::iterator it_end;
std::vector<foo>* main;
std::vector<foo>* other;
if( vec1.size() > vec2.size() ) {
it_begin = vec1.begin();
it_end = vec1.end();
main = &vec1;
other = &vec2;
}
else {
it_begin = vec2.begin();
it_end = vec2.end();
main = &vec2;
other = &vec1;
}
std::vector<foo> new_vec;
for( it_begin; it_begin != it_end; ++it_begin ) {
auto cur_element = *it_begin;
auto intersec = std::find_if( other->begin(),other->end(),[cur_element]
(foo & comp_element)->bool{
return( (cur_element.x==comp_element.x ) && ( cur_element.y==comp_element.y ) );
});
if( intersec != other->end() )
{
new_vec.push_back( cur_element );
}
}
vec1 = new_vec;
vec2 = new_vec;
std::cout<<"vec1:\n";
for(auto i: vec1) std::cout<<i.x<<" "<<i.y<<"\n";
std::cout<<"\nvec2:\n";
for(auto i: vec2) std::cout<<i.x<<" "<<i.y<<"\n";
return 0;
}