时间戳

首页 > 解决方案 > 找到两个向量相对于向量对象的两个成员的交集的有效方法

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

问题描述

我有两个保存数据对象的向量。每个数据对象都保存坐标和其他一些数据。向量总是会被排序（首先是 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++c++11vectorintersection

解决方案

你的两个向量已经排序——完美！

首先，假设有一个比较函数（使用即将推出的 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做的那样......

推荐阅读