c++ - 找到两个 vector 相对于 vector 对象的两个成员的交集的有效方法

Question

我有两个 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 中删除“错误”对象的有效方法。

Answer 1

您的两个 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 做的...