我有两个 vector 保存数据对象。每个数据对象都包含坐标和一些其他数据。 vector 将始终被排序(首先是 x 坐标,然后是 y 坐标)。我试图从两个 vector 中删除所有对象,这些对象的坐标在两个 vector 中都找不到。这是我目前正在做的 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;
}
它有效并为我提供了预期的输出。
无论如何,必须循环遍历这两个 vector 似乎真的很低效。是否有更有效的方法来实现相同的输出?
编辑:获取两个 vector 中表示的坐标是不够的。我需要的是一种从两个 vector 中删除“错误”对象的有效方法。
最佳答案
您的两个 vector 已经排序 - 完美!
首先,假设一个比较函数(对于即将到来的 C++20,这将得到 spaceship 运算符...):
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());
在两个 vector 中都是线性的...
该算法只是将要保留的元素移到前面,最后删除所有过期的元素——类似于 std::remove_if
做的...
关于c++ - 找到两个 vector 相对于 vector 对象的两个成员的交集的有效方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54707288/