與`std :: set_intersection`相似，但產生相同元素對

Question

我給出了兩個按某些條件排序的容器（例如，按照其ID號排序的人員）。

我希望通過相同的標準找到兩個容器共有的所有元素，並且我希望訪問被認爲相等的兩個元素。

我想過執行合併，然後手動掃描相同的相鄰元素。但也許有一個更優雅的算法？

struct Employee 
{ 
    int id; 
    int salary; 

    Employee(int id, int salary); 
}; 

struct ById 
{ 
    bool operator()(const Employee& left, const Employee& right) { 
     return left.id < right.id; 
    } 
}; 

std::vector<Employee> first = { Employee(10, 1000), 
           Employee(12, 1000), 
           Employee(31, 10000) }; // Note: sorted by Id 
std::vector<Employee> second = { Employee(1, 1500), 
           Employee(10, 2000), 
           Employee(31, 12000) }; // Note: sorted by Id 

// prints the following: 
// [id: 10, salary: 1000], [id: 10, salary: 2000] // id 10 exists in both containers 
// [id: 31, salary: 10000], [id: 31, salary: 12000] // id 31 exists in both containers 
MySetIntersection(// <--- I WANT TO KNOW HOW TO IMPLEMENT THIS 
    begin(first), end(first), 
    begin(second), end(second), 
    ById(), 
    [] (const Person& left, const Person& right) { 
     std::cout << "[" << left << "], [" << right << "]" std::endl; 
    } 
); 

Answer 1

看起來馬薩在我測試的時候打敗了我，但我會張貼反正顯示它的比較功能。

template<typename InputIt1, typename InputIt2, typename Compare, typename Func> 
void MySetIntersection(InputIt1 first1, InputIt1 last1, 
    InputIt2 first2, InputIt2 last2, 
    Compare comp, Func func) 
{ 
    while (first1 != last1 && first2 != last2) { 
     if (comp(*first1, *first2)) 
      ++first1; 
     else if (comp(*first2, *first1)) 
      ++first2; 
     else 
      func(*first1++, *first2++); 
    } 
} 

Answer 2

你到目前爲止試過了什麼？這似乎是一個相當簡單的算法：

template<typename ForwardIterator1, typename ForwardIterator2, typename Func> 
    void for_each_intersecting(ForwardIterator1 begin1, ForwardIterator1 end1, ForwardIterator2 begin2, ForwardIterator2 end2, Func what) { 
     while((begin1 != end1) && (begin2 != end2)) { 
      if(*begin1 < *begin2) 
      ++begin1; 
      else if(*begin2 < *begin1) 
      ++begin2; 
      else 
      what(*begin1++, *begin2++); 
     } 
    } 

（live at coliru）

如果你真的不想要測試等方面的算法，您可以使用intermetdiate載體std::adjacent_find，如：

#include <iostream> 
#include <algorithm> 
#include <functional> 

struct employee { int id, salary; }; 

int main() { 
    std::vector<employee> v1 { { 1, 1500 }, { 10, 2000 }, { 15, 2500 }, { 16, 1000 } }; 
    std::vector<employee> v2 { { 10, 1500 }, { 13, 2000 }, { 15, 500 }, { 19, 1300 } }; 
    std::vector<employee> v3; v3.reserve(v1.size()+v2.size()); 
    std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(v3), [](const employee& e1, const employee& e2) { return e1.id < e2.id; }); 
    for(auto a = v3.begin(), e = v3.end(); (a = std::adjacent_find(a, e, [](const employee& e1, const employee& e2) { return e1.id == e2.id; })) != e; ++a) { 
     std::cout << a->id << ' ' << a->salary << ' '; 
     ++a; 
     std::cout << a->id << ' ' << a->salary << '\n'; 
    } 
} 

但要注意，這可能會是比較慢（且佔用更多的內存），比原來的答案...

或者，沒有lambda表達式：

#include <iostream> 
#include <algorithm> 
#include <functional> 

struct employee { 
    int id, salary; 
    bool operator<(const employee& e) { return id < e.id; } 
    bool operator==(const employee& e) { return id == e.id; } 
}; 

int main() { 
    std::vector<employee> v1 { { 1, 1500 }, { 10, 2000 }, { 15, 2500 }, { 16, 1000 } }; 
    std::vector<employee> v2 { { 10, 1500 }, { 13, 2000 }, { 15, 500 }, { 19, 1300 } }; 
    std::vector<employee> v3; v3.reserve(v1.size()+v2.size()); 
    std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(v3)); 
    for(auto a = v3.begin(), e = v3.end(); (a = std::adjacent_find(a, e)) != e; ++a) { 
     std::cout << a->id << ' ' << a->salary << ' '; 
     ++a; 
     std::cout << a->id << ' ' << a->salary << '\n'; 
    } 
}