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

OK，現在用錯誤信息發佈很清楚是什麼問題： set_difference返回輸出迭代器，在這種情況下是insert_iterator（由你的電話構造inserter）。您嘗試將其分配給result這是一個向量迭代器。這是一種類型不匹配。

最簡單的解決方案就是省略那個賦值和迭代器result，因爲你不需要迭代器;結果已寫入v。

Answer 2

閱讀documentation ：兩個輸入範圍已經必須分類。

您還必須爲結果提供輸出迭代器。

所以做到這一點：

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 3

你的期望是錯誤的：A - B是A中的元素集合，在B中也不存在，在你的情況下是空集合，因爲A中的每個元素都在B中找到。B - A會給出你期望的結果。