std::set_union 的替代方案，带有用于从交集合并元素的附加谓词参数

Question

给定两个已排序的容器和 std::set_union，我们可以提供一个谓词来确定两个元素何时相等。我想提供一个额外的谓词，它将合并相等的元素（容器的交集）并将结果插入输出容器。

请在下面的 'Expected output' 部分中注意 set_union 和 unknown_func 的向量有何不同。

是否有一种算法可以模拟下面 'Expected output' 描述的行为？如果只有更复杂的方法可以实现这种行为，您能否建议我可以从哪里开始这样做？最终解决方案最好只使用 std/stl 库提供的功能。

示例代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

struct CustomStruct{
    CustomStruct(const int f1, const int f2) : field_1(f1), field_2(f2) {}
    int field_1;
    int field_2;
};

void print_vector(const std::string& str, const std::vector<CustomStruct>& vec){
    std::cout << str << std::endl;
    for (const auto& val: vec){
        std::cout<< val.field_1 << ", " << val.field_2 << std::endl;
    }
}


int main()
{
    std::vector<CustomStruct> vec_a;
    std::vector<CustomStruct> vec_b;
    std::vector<CustomStruct> vec_set_union;
    std::vector<CustomStruct> vec_unknown_func;

    for (int i = 0; i < 4; ++i){ vec_a.emplace_back(i, 2); }
    for (int i = 2; i < 4; ++i){ vec_b.emplace_back(i, 3); }
    
    print_vector("VEC_A", vec_a);
    print_vector("VEC_B", vec_b);
    
    const auto compare = [](const CustomStruct& lhs, const CustomStruct& rhs){
        return lhs.field_1 < rhs.field_1;
    };
    std::set_union(vec_a.begin(), vec_a.end(),
                   vec_b.begin(), vec_b.end(),           
                   std::back_inserter(vec_set_union),
                   compare
   );
   
    print_vector("VEC_SET_UNION", vec_set_union);
    
    const auto merge_duplicate = [](const CustomStruct& lhs, const CustomStruct& rhs){
        return CustomStruct(lhs.field_1, lhs.field_2 + (rhs.field_2*rhs.field_2));
    };
    // std::unknown_func(vec_a.begin(), vec_a.end(),
    //                                     vec_b.begin(), vec_b.end(),           
    //                                     std::back_inserter(vec_unknown_func),
    //                                     compare,
    //                                     merge_duplicate
    // );
    
    // THE COMMENTED CODE ABOVE WOULD NEED TO ALLOW 'VEC_UNKNOWN_FUNC' to have
    // the 'Expected output' supplied as part of this question
    
    print_vector("VEC_UNKNOWN_FUNC", vec_unknown_func);
}

预期输出

VEC_A
0, 2
1, 2
2, 2
3, 2
VEC_B
2, 3
3, 3
VEC_SET_UNION
0, 2
1, 2
2, 2
3, 2
VEC_UNKNOWN_FUNC
0, 2
1, 2
2, 11
3, 11

感谢您抽出时间，如果我可以提供进一步的说明，请告诉我。

Answer 1

正如@Useless 在评论中建议的那样，要在 <algorithm> 上做额外的事情，您应该根据该算法编写一些东西。

改编自possible implementation：

template<class InputIt1, class InputIt2,
         class OutputIt, class Compare,
         class BinaryOp>
OutputIt set_union_transform(InputIt1 first1, InputIt1 last1,
                   InputIt2 first2, InputIt2 last2,
                   OutputIt d_first, Compare comp,
                   BinaryOp binary_op)
{
    for (; first1 != last1; ++d_first) {
        if (first2 == last2)
            return std::copy(first1, last1, d_first);
        if (comp(*first2, *first1)) {
            *d_first = *first2++;
        } else if (comp(*first1, *first2)) {
            *d_first = *first1++;
        } else {
            *d_first = binary_op(*first1++, *first2++);
        }
    }
    return std::copy(first2, last2, d_first);
}

Answer 2

只是敲击键盘，但我想你想要这样的东西：

std::vector<CustomStruct> vec_set_intersection1;
std::vector<CustomStruct> vec_set_intersection2;

// Find the duplicate objects in the first vector
std::set_intersection(vec_a.begin(), vec_a.end(),
    vec_b.begin(), vec_b.end(),           
    std::back_inserter(vec_set_intersection1),
    compare);

// Find the duplicate objects in the second vector
std::set_intersection(vec_b.begin(), vec_b.end(),
    vec_a.begin(), vec_a.end(),           
    std::back_inserter(vec_set_intersection2),
    compare);

// Apply the transformation
std::transform(vec_set_intersection1.begin(), vec_set_intersection1.end(),
    vec_set_intersection2.begin(), vec_set_intersection2.end(),
    std::back_inserter(vec_unknown_func),
    merge_duplicate);

std::set_union 的替代方案，带有用于从交集合并元素的附加谓词参数

Alternative to std::set_union with additional predicate parameter for merging elements from the intersection

c++

stl

std

c++14