Эффективный способ найти пересечение двух векторов относительно двух членов векторных объектов

Question

У меня есть два вектора, содержащих объекты данных.Каждый объект данных содержит координаты и некоторые другие данные.Векторы всегда будут отсортированы (сначала для координат 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;
}

Это работает и дает мне ожидаемый результат.
В любом случае кажется действительно неэффективным обходить оба вектора.Есть ли более эффективный способ достижения того же результата?

РЕДАКТИРОВАТЬ: недостаточно получить координаты, которые представлены в обоих векторах.Мне нужен эффективный способ удаления «неправильных» объектов из обоих векторов.

Answer 1

Это мой подход в стиле стирать-удалять , повторяющийся только один раз по векторам:

#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

единственное, что нельзя сделать, это то, что это предполагает отсутствие повторяющихся координат или, более конкретно, повторение их одинаковое количество раз на обоих векторах, и «лишние» повторения будут удалены (вы можете адаптировать алгоритм, чтобы изменить это, еслиВы нуждались, хотя это сделало бы код немного более уродливым).

Answer 2

Ваши два вектора уже отсортированы - отлично!

Во-первых, если предположить функцию сравнения (с выходом 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 делай ...

Answer 3

Я думаю, что это решение является линейным и делает то, что вы хотите.

Возможное дальнейшее улучшение:

• для больших векторов с большими областями непересекающихся, оно можетСтоит кэшировать регионы, которые нужно стереть.

• Еще одна стратегия, если 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();
}

Answer 4

Может как то так?Сначала вы выбираете, какой вектор больше, а затем итерируете (в основном) по большему и проверяете внутри другого.

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;
}