6

我正在尝试使用std::set_intersection在具有共同绑定“名称”字段的两种完全不同类型的数据结构之间查找共同元素。

我在这里查看了以下输入链接描述，但它似乎迫使我在我试图避免的 2 种不同结构类型之间进行自定义转换（因为这些类型来自第 3 方）

下面的代码片段显示了我想要实现的目标。

// common field used for set intersection
typedef struct StructA {
    std::string mCommonField;
    float mFloatValue;
} StructA;

typedef struct StructB {
    std::string mCommonField;
    int mValue1;
    short mValue2;
} StructB;

// initially unsorted list
std::vector<StructA> aStructs = {{"hello", 1.0f}, {"goodbye", 2.0f}, {"foo", 3.0f}};
// initially unsorted list
std::vector<StructB> bStructs = {{"hello", 1, 2}, {"goodbye", 3, 4}, {"bar", 5, 6}};
// sorting both sets before calling std::intersection
std::sort(aStructs.begin(), aStructs.end(),
    [](const StructA& lhs, const StructA& rhs) {
        return lhs.mCommonField < rhs.mCommonField;
    });
std::sort(bStructs.begin(), bStructs.end(),
    [](const StructB& lhs, const StructB& rhs) {
    return lhs.mCommonField < rhs.mCommonField;
});

std::vector<StructA> intersection;
std::set_intersection(
    aStructs.begin(), aStructs.end(),
    bStructs.begin(), bStructs.end(),
    std::back_inserter(intersection),
    [](const StructA& lhs, const StructB& rhs){
        return lhs.mCommonField < rhs.mCommonField;
    });

我正在使用 Visual Studio 2013 来编译上面的代码，但是上面的代码会吐出大量错误，如下所示。通读std::set_intersection我在将兼容的StrictWeakOrdering comp最后一个参数放在一起时遇到问题。理想情况下，我希望将其实现为一次性 lambda。 

template <class InputIterator1, class InputIterator2, class OutputIterator,
          class StrictWeakOrdering>
OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1,
                                InputIterator2 first2, InputIterator2 last2,
                                OutputIterator result, 
                                StrictWeakOrdering comp);

1>C:\Program Files (x86)\Microsoft Visual Studio 12.0\VC\include\algorithm(3591): 错误 C2664: 'bool (__vectorcall *)(const main::StructA &,const main::StructB &)' : 无法将参数 1 从 'main::StructB' 转换为 'const main::StructA &' 1>
原因：无法从 'main::StructB' 转换为 'const main::StructA' 1> 没有用户定义的转换可以执行此转换的可用运算符，或者无法调用该运算符 1>
C:\Program Files (x86)\Microsoft Visual Studio 12.0\VC\include\algorithm(3625) ：请参阅对函数模板实例化的参考 '_OutIt std:: _Set_intersection<_InIt1,_InIt2,_OutIt,_Pr>(_InIt1,_InIt1,_InIt2,_InIt2,_OutIt,_Pr)' 正在编译 1> 与 1> [ 1>
_OutIt=std::back_insert_iterator>> 1> , _InIt1=main::StructA * 1> ,
_InIt2=main::StructB * 1> , _Pr=main:: 1> ] 1> C:\Program Files (x86)\ Microsoft Visual Studio 12.0\VC\include\algorithm(3654) ：请参阅正在编译的函数模板实例化 '_OutIt std::_Set_intersection2(_InIt1,_InIt1,_InIt2,_InIt2,_OutIt,_Pr,std::true_type)' 的参考 1> 1> [ 1>
_OutIt=std::back_insert_iterator>> 1> , _Pr=main:: 1> , _InIt1=main::StructA * 1> ,
_InIt2=main::StructB * 1> ] 1> ....\src\dlf\main.cpp(111) : 参见函数模板实例化 '_OutIt std::set_intersection>>,std::_Vector_iterator>>, std::back_insert_iterator>>,main::>(_InIt1,_InIt1,_InIt2,_InIt2,_OutIt,_Pr)' 正在编译 1> 与 1> [ 1>
_OutIt=std::back_insert_iterator>> 1> , _Ty=main: :StructA 1> ,
_InIt1=std::_Vector_iterator>> 1> ,
_InIt2=std::_Vector_iterator>> 1> , _Pr=main:: 1> ]

我还尝试使用自定义比较器结构进行比较，但错误更加令人困惑：

struct comparator {
    bool operator()(const StructA& lhs, const StructB& rhs) const {
        return lhs.mCommonField < rhs.mCommonField;
    }
    bool operator()(const StructB& lhs, const StructA& rhs) const {
        return lhs.mCommonField < rhs.mCommonField;
    }
};

std::vector<StructA> intersection;
std::set_intersection(
    aStructs.begin(), aStructs.end(),
    bStructs.begin(), bStructs.end(),
    std::back_inserter(intersection),
    comparator());

这导致以下详细错误输出。我希望避免自定义结构（因为我尝试使用的实际结构来自第 3 方）以将转换器从 StructA 转换为 StructB，反之亦然，有什么办法可以避免这种情况，只需要一些简单的 lambda实现两个相对简单的结构与一个公共字段之间的简单绑定？
提前致谢。

1>C:\Program Files (x86)\Microsoft Visual Studio 12.0\VC\include\xutility(521): 错误 C2664: 'bool main::comparator::operator ()(const main::StructA &,const main: :StructB &) const' : 无法将参数 1 从 'main::StructA' 转换为 'const main::StructB &' 1> 原因：无法从 'main::StructA' 转换为 'const main::StructB' 1>没有可以执行此转换的用户定义转换运算符，或者无法调用该运算符 1> C:\Program Files (x86)\Microsoft Visual Studio 12.0\VC\include\xutility(625) ：请参阅函数模板的参考实例化 'bool std::_Debug_lt_pred<_Pr,main::StructA&,main::StructA&>(_Pr,_Ty1,_Ty2,std::_Dbfile_t,std::_Dbline_t)' 正在编译 1> 和 1>[1>
_Pr=main::comparator 1> , _Ty1=main::StructA & 1> , _Ty2=main::StructA & 1> ] 1> C:\Program Files (x86)\Microsoft Visual Studio 12.0\VC\include\xutility (636) : 请参阅对函数模板实例化 'void std::_Debug_order2<_InIt,_Pr>(_FwdIt,_FwdIt,_Pr,std::_Dbfile_t,std::_Dbline_t,std::forward_iterator_tag)' 的引用 1> 与 1 > [ 1>
_InIt=std::_Vector_iterator>> 1> , _Pr=main::comparator 1> ,
_FwdIt=std::_Vector_iterator>> 1> ] 1> C:\Program Files (x86)\Microsoft Visual Studio 12.0\VC\include\algorithm(3649) ：参见函数模板实例化的参考 'void std::_Debug_order<_InIt1 ,_Pr>(_InIt,_InIt,_Pr,std::_Dbfile_t,std::_Dbline_t)' 正在编译 1> 1> [ 1>
_InIt1=std::_Vector_iterator>> 1> , _Pr=main::comparator 1> ,
_InIt=std::_Vector_iterator>> 1> ] 1> ....\src\dlf\main.cpp(118) : 参见函数模板实例化 '_OutIt std::set_intersection>>,std::_Vector_iterator> >,std::back_insert_iterator>>,main::comparator>(_InIt1,_InIt1,_InIt2,_InIt2,_OutIt,_Pr)' 正在编译 1> 和 1>[1>
_OutIt=std::back_insert_iterator>> 1> , _Ty=main::StructA 1> ,
_InIt1=std::_Vector_iterator>> 1> ,
_InIt2=std::_Vector_iterator>> 1> , _Pr=main::comparator 1> ] 1>C:\Program Files (x86)\Microsoft Visual Studio 12.0\VC\include\xutility(523): error C2664: 'bool main::comparator::operator ()(const main::StructA &,const main::StructB &) const' : 无法将参数 1 从 'main::StructA' 转换为 'const main::StructB &' 1> 原因: 无法从 'main::StructA' 转换为 'const main::StructB' 1> 没有可以执行此转换的用户定义转换运算符，或者无法调用该运算符 1>C:\Program Files (x86) \Microsoft Visual Studio 12.0\VC\include\xutility(521): 错误 C2664: 'bool main::comparator::operator ()(const main::StructA &,const main::StructB &) const'：无法将参数 2 从 'main::StructB' 转换为 'const main::StructA &' 1> 原因：无法从 'main::StructB' 转换为 'const main::StructA' 1> 没有用户定义的转换运算符可以执行此转换的可用，或者无法调用运算符 1> C:\Program Files (x86)\Microsoft Visual Studio 12.0\VC\include\xutility(625) ：请参阅对函数模板实例化的参考 'bool std::_Debug_lt_pred <_Pr,main::StructB&,main::StructB&>(_Pr,_Ty1,_Ty2,std::_Dbfile_t,std::_Dbline_t)' 正在编译 1> 和 1> [ 1>没有可以执行此转换的用户定义转换运算符，或者无法调用该运算符 1> C:\Program Files (x86)\Microsoft Visual Studio 12.0\VC\include\xutility(625) ：请参阅函数模板的参考实例化 'bool std::_Debug_lt_pred<_Pr,main::StructB&,main::StructB&>(_Pr,_Ty1,_Ty2,std::_Dbfile_t,std::_Dbline_t)' 正在编译 1> 和 1> [ 1>没有可以执行此转换的用户定义转换运算符，或者无法调用该运算符 1> C:\Program Files (x86)\Microsoft Visual Studio 12.0\VC\include\xutility(625) ：请参阅函数模板的参考实例化 'bool std::_Debug_lt_pred<_Pr,main::StructB&,main::StructB&>(_Pr,_Ty1,_Ty2,std::_Dbfile_t,std::_Dbline_t)' 正在编译 1> 和 1> [ 1>_Dbline_t)' 正在编译 1> 与 1> [ 1>_Dbline_t)' 正在编译 1> 与 1> [ 1>
_Pr=main::comparator 1> , _Ty1=main::StructB & 1> , _Ty2=main::StructB & 1> ] 1> C:\Program Files (x86)\Microsoft Visual Studio 12.0\VC\include\xutility (636) : 请参阅对函数模板实例化 'void std::_Debug_order2<_InIt,_Pr>(_FwdIt,_FwdIt,_Pr,std::_Dbfile_t,std::_Dbline_t,std::forward_iterator_tag)' 的引用 1> 与 1 > [ 1>
_InIt=std::_Vector_iterator>> 1> , _Pr=main::comparator 1> ,
_FwdIt=std::_Vector_iterator>> 1> ] 1> C:\Program Files (x86)\Microsoft Visual Studio 12.0\VC\include\algorithm(3650) ：参见函数模板实例化参考 'void std::_Debug_order<_InIt2 ,_Pr>(_InIt,_InIt,_Pr,std::_Dbfile_t,std::_Dbline_t)' 正在编译 1> 1> [ 1>
_InIt2=std::_Vector_iterator>> 1> , _Pr=main::comparator 1> ,
_InIt=std::_Vector_iterator>> 1> ] 1>C:\Program Files (x86)\Microsoft Visual Studio 12.0\VC\include\xutility(523): error C2664: 'bool main::comparator::operator () (const main::StructA &,const main::StructB &) const' : 无法将参数 2 从 'main::StructB' 转换为 'const main::StructA &' 1> 原因：无法从 'main::StructB 转换' to 'const main::StructA' 1> 没有可以执行此转换的用户定义转换运算符，或者无法调用该运算符

4

3 回答 3

14

由于 C++ 的表现力，有几种方法可以解决这个问题。以下绝不是详尽的清单。

1. 将两种类型隐式转换为包装结构以进行比较

如果您喜欢使用 lambda，请定义一个可以从两者隐式构造的类型，StructA并StructB包装用于比较的字段。这可以允许在比较之前对构造函数中的字段执行附加逻辑。例如：

struct Common {
    std::string const& mCommonField;
    Common(StructA const& sa) : mCommonField{sa.mCommonField} {};
    Common(StructB const& sb) : mCommonField{sb.mCommonField} {};
};

那么你的比较 lambda 可以写成

auto cmp = [](Common const& lhs, Common const& rhs) {
    return lhs.mCommonField < rhs.mCommonField;
};

并像使用

std::sort(aStructs.begin(), aStructs.end(), cmp);
std::sort(bStructs.begin(), bStructs.end(), cmp);
// ...
std::set_intersection(aStructs.begin(), aStructs.end(),
                      bStructs.begin(), bStructs.end(),
                      std::back_inserter(intersection),
                      cmp
                      );

Coliru Viewer上的实时示例。

2. 使用带有模板的比较器operator()。

不要使用 lambda，而是使用模板定义一个仿函数operator()。

struct comparator
{
    template<typename T, typename U>
    bool operator()(T const& lhs, U const& rhs) const {
        return lhs.mCommonField < rhs.mCommonField;
    }
};

然后，它很简单：

std::sort(aStructs.begin(), aStructs.end(), comparator{});
std::sort(bStructs.begin(), bStructs.end(), comparator{});
// ...
std::set_intersection(aStructs.begin(), aStructs.end(),
                      bStructs.begin(), bStructs.end(),
                      std::back_inserter(intersection),
                      comparator{}
                      );

请注意，由于比较器中有一个模板，因此必须在函数范围之外声明它。Coliru Viewer上的实时示例。

3. 等待 C++14

并且在 C++14 中添加了通用 lambda，您可以将以下内容与一致的编译器一起使用：

auto cmp = [](auto lhs, auto rhs) { return lhs.mCommonField < rhs.mCommonField; };
// ...
std::sort(aStructs.begin(), aStructs.end(), cmp);
std::sort(bStructs.begin(), bStructs.end(), cmp);
// ...
std::set_intersection(aStructs.begin(), aStructs.end(),
                      bStructs.begin(), bStructs.end(),
                      std::back_inserter(intersection),
                      cmp);

同样，Coliru Viewer上的实时示例。

此外，C 风格的结构类型定义在 C++ 中是不必要的（并且可以说在 C 中的大多数地方都不清楚），所以无论你有什么地方

typedef struct Foo {
    // ...
} Foo;

你可以用

struct Foo {
    // ...
};

无需对您的代码进行任何其他更改。

于 2014-03-17T14:58:27.790 回答
0

使用 std::copy_if 和 lambda 在 vectorB 内搜索 使用 std::binary_search 确保使用与 binary_search 相同的谓词进行排序

这解决了类似的问题： 删除包含在另一个向量中的向量的所有元素的优雅方法？

于 2014-03-17T17:38:15.943 回答
-2

set_intersection不是魔术，如果你有排序的向量很容易自己滚动，大致如下：

auto ta = aStructs.begin();
auto tb = bStructs.begin();
while( ta != aStructs.end() && tb != bStructs.end() ){
    if( ta->mCommonField < tb->mCommonField ){
        ++ta;
    } else if( tb->mCommonField < ta->mCommonField ){
        ++tb;
    } else {
        std::cout << "found common: " << ta->mCommonField << std::endl;
        ++ta;
        ++tb;
    }
}
于 2014-03-17T14:48:16.297 回答