set_difference для пользовательской структуры

Question

Я пытаюсь найти разницу между следующими двумя наборами:

A = {(0,0), (0,1), (1,0), (1,1), (2,2)}

B = {(0,0), (0,1), (1,0), (1,1)}

Ожидаемый ответ:

A - B = {(2,2)}

Я попробовал следующий код.Но я застрял не в состоянии скомпилировать.Кто-нибудь может указать на ошибку, которую я делаю?

#include <vector>
#include <algorithm>
#include <iostream>
#include <utility>

using namespace std;

class compare
{
  public:
    bool operator()(const pair <int, int> elem1, const pair <int, int> elem2)
    {
      return ((elem1.first == elem2.first) && 
          (elem1.second == elem2.second));
    }
};

int main()
{
  vector < pair<int, int> > v, va, vb;
  va.push_back(make_pair(0,0));
  va.push_back(make_pair(0,1));
  va.push_back(make_pair(1,0));
  va.push_back(make_pair(1,1));
  va.push_back(make_pair(2,2));

  vb.push_back(make_pair(0,0));
  vb.push_back(make_pair(0,1));
  vb.push_back(make_pair(1,0));
  vb.push_back(make_pair(1,1));


  vector < pair<int, int> >::iterator it, result;
  result = set_difference (va.begin(), va.end(),
      vb.begin(), vb.end(), 
      inserter(v, v.end()), 
      compare());

  // for (it = v.begin( ) ; it != result; it++)
  //   cout << "(" << it->first << it->second << ")" << ", ";
  // cout << endl;

  return 0;
}

РЕДАКТИРОВАТЬ: сообщение об ошибке компиляции выглядит следующим образом:

set_difference.cc: In function `int main()':
set_difference.cc:36: error: no match for 'operator=' in 'result = std::set_difference [with _InputIterator1 = __gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >, _InputIterator2 = __gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >, _OutputIterator = std::insert_iterator<std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >, _Compare = compare]((&va)->std::vector<_Tp, _Alloc>::begin [with _Tp = std::pair<int, int>, _Alloc = std::allocator<std::pair<int, int> >](), (&va)->std::vector<_Tp, _Alloc>::end [with _Tp = std::pair<int, int>, _Alloc = std::allocator<std::pair<int, int> >](), (&vb)->std::vector<_Tp, _Alloc>::begin [with _Tp = std::pair<int, int>, _Alloc = std::allocator<std::pair<int, int> >](), (&vb)->std::vector<_Tp, _Alloc>::end [with _Tp = std::pair<int, int>, _Alloc = std::allocator<std::pair<int, int> >](), std::inserter [with _Container = std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >, _Iterator = __gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >](((std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >&)(&v)), (&v)->std::vector<_Tp, _Alloc>::end [with _Tp = std::pair<int, int>, _Alloc = std::allocator<std::pair<int, int> >]()), (compare(), compare()))'
/usr/lib/gcc/x86_64-redhat-linux/3.4.6/../../../../include/c++/3.4.6/bits/stl_iterator.h:587: note: candidates are: __gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >& __gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >::operator=(const __gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >&)

Answer 1

(Это относится к правильности алгоритмов, а не к проблемам компиляции.)

Прочитайте документацию : два входных диапазона уже имеютдля сортировки .

Вы также должны предоставить выходной итератор для результата.

Так сделайте это:

std::sort(va.begin(), va.end(), compare());
std::sort(vb.begin(), vb.end(), compare());

set_difference(va.begin(), va.end(), vb.begin(), vb.end(),
               std::back_inserter(v), compare());

Ваша compare функция также должна определять строгий, слабый порядок , а не сравнение на равенство.

Кстати, std::pair<S, T> и std::tuple<T...> уже поставляются со встроенным лексикографическим сравнениемпоэтому вам обычно не нужно определять собственное сравнение, если вы не хотите чего-то экзотического: std::sort(va.begin(), va.end()); и т. д.

Answer 2

ОК, теперь с опубликованным сообщением об ошибке ясно, в чем проблема: set_difference возвращает выходной итератор, который в данном случае представляет собой insert_iterator (созданный вашим вызовом inserter).Вы пытаетесь присвоить его result, который является векторным итератором.Это несоответствие типов.

Самое простое решение - просто пропустить это назначение и итератор result, потому что этот итератор все равно не нужен;результаты были записаны в v.

Answer 3

Ваше ожидание неверно: A - B - это набор элементов в A, также не найденный в B, который в вашем случае является пустым набором, потому что каждый элемент в A также находится в B. B - A даст результат вы ожидаете.