unable to apply std::set_intersection on different types of structs with a common field

Question

I am trying to use use std::set_intersection to find common elements between 2 completely different types of data structures that have a common binding 'name' field.

I looked at the following enter link description here but it seems to force me down the route to do a custom conversion between the 2 different struct types which I was trying to avoid (as these types are from a 3rd party)

The code snippet below shows what I am trying to achieve.

// 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;
    });

I am using Visual Studio 2013 to compile the above, however the above code spits out a plethora of errors as shown below. Reading through the std::set_intersection I am having a problem putting together a compatible StrictWeakOrdering comp last argument. I would ideally like to implement this as a one off 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): error C2664: 'bool (__vectorcall *)(const main::StructA &,const main::StructB &)' : cannot convert argument 1 from 'main::StructB' to 'const main::StructA &' 1>
Reason: cannot convert from 'main::StructB' to 'const main::StructA' 1> No user-defined-conversion operator available that can perform this conversion, or the operator cannot be called 1>
C:\Program Files (x86)\Microsoft Visual Studio 12.0\VC\include\algorithm(3625) : see reference to function template instantiation '_OutIt std::_Set_intersection<_InIt1,_InIt2,_OutIt,_Pr>(_InIt1,_InIt1,_InIt2,_InIt2,_OutIt,_Pr)' being compiled 1> with 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) : see reference to function template instantiation '_OutIt std::_Set_intersection2(_InIt1,_InIt1,_InIt2,_InIt2,_OutIt,_Pr,std::true_type)' being compiled 1> with 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) : see reference to function template instantiation '_OutIt std::set_intersection>>,std::_Vector_iterator>>,std::back_insert_iterator>>,main::>(_InIt1,_InIt1,_InIt2,_InIt2,_OutIt,_Pr)' being compiled 1> with 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> ]

I also tried to use a custom comparator struct to do the comparison, but the errors were even more confusing as per:

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());

which resulted in the following verbose error output. I was hoping to avoid customizing the structures (as the actual ones I am trying to use are from a 3rd party) to have converters from StructA to StructB and vise-versa, is there any way I can avoid that and just have some simple lambda to achieve a simple binding between 2 relatively simple structs with a common field?
Thanks in advance.

1>C:\Program Files (x86)\Microsoft Visual Studio 12.0\VC\include\xutility(521): error C2664: 'bool main::comparator::operator ()(const main::StructA &,const main::StructB &) const' : cannot convert argument 1 from 'main::StructA' to 'const main::StructB &' 1> Reason: cannot convert from 'main::StructA' to 'const main::StructB' 1> No user-defined-conversion operator available that can perform this conversion, or the operator cannot be called 1> C:\Program Files (x86)\Microsoft Visual Studio 12.0\VC\include\xutility(625) : see reference to function template instantiation 'bool std::_Debug_lt_pred<_Pr,main::StructA&,main::StructA&>(_Pr,_Ty1,_Ty2,std::_Dbfile_t,std::_Dbline_t)' being compiled 1> with 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) : see reference to function template instantiation 'void std::_Debug_order2<_InIt,_Pr>(_FwdIt,_FwdIt,_Pr,std::_Dbfile_t,std::_Dbline_t,std::forward_iterator_tag)' being compiled 1> with 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) : see reference to function template instantiation 'void std::_Debug_order<_InIt1,_Pr>(_InIt,_InIt,_Pr,std::_Dbfile_t,std::_Dbline_t)' being compiled 1> with 1> [ 1>
_InIt1=std::_Vector_iterator>> 1> , _Pr=main::comparator 1> ,
_InIt=std::_Vector_iterator>> 1> ] 1> ....\src\dlf\main.cpp(118) : see reference to function template instantiation '_OutIt std::set_intersection>>,std::_Vector_iterator>>,std::back_insert_iterator>>,main::comparator>(_InIt1,_InIt1,_InIt2,_InIt2,_OutIt,_Pr)' being compiled 1> with 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' : cannot convert argument 1 from 'main::StructA' to 'const main::StructB &' 1> Reason: cannot convert from 'main::StructA' to 'const main::StructB' 1> No user-defined-conversion operator available that can perform this conversion, or the operator cannot be called 1>C:\Program Files (x86)\Microsoft Visual Studio 12.0\VC\include\xutility(521): error C2664: 'bool main::comparator::operator ()(const main::StructA &,const main::StructB &) const' : cannot convert argument 2 from 'main::StructB' to 'const main::StructA &' 1> Reason: cannot convert from 'main::StructB' to 'const main::StructA' 1> No user-defined-conversion operator available that can perform this conversion, or the operator cannot be called 1> C:\Program Files (x86)\Microsoft Visual Studio 12.0\VC\include\xutility(625) : see reference to function template instantiation 'bool std::_Debug_lt_pred<_Pr,main::StructB&,main::StructB&>(_Pr,_Ty1,_Ty2,std::_Dbfile_t,std::_Dbline_t)' being compiled 1> with 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) : see reference to function template instantiation 'void std::_Debug_order2<_InIt,_Pr>(_FwdIt,_FwdIt,_Pr,std::_Dbfile_t,std::_Dbline_t,std::forward_iterator_tag)' being compiled 1> with 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) : see reference to function template instantiation 'void std::_Debug_order<_InIt2,_Pr>(_InIt,_InIt,_Pr,std::_Dbfile_t,std::_Dbline_t)' being compiled 1> with 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' : cannot convert argument 2 from 'main::StructB' to 'const main::StructA &' 1> Reason: cannot convert from 'main::StructB' to 'const main::StructA' 1> No user-defined-conversion operator available that can perform this conversion, or the operator cannot be called

Braxton

Answer 1

Thanks to the expressiveness of C++, there are a few ways you can solve this problem. The following is by no means an exhaustive list.

1. Implicitly convert both types to a wrapper struct for comparison

If you're attached to using lambdas, define a type that can be implicitly constructed from both StructA and StructB and wraps the fields used for comparison. This can allow for additional logic to be performed to the fields in the constructor before comparison. For example:

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

Then your comparison lambda can be written

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

and used like

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
                      );

Live example on Coliru Viewer.

2. Use a comparator with templated operator().

Instead of using a lambda, define a functor with a templated operator().

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

Then, it's as easy as:

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{}
                      );

Just note that as there is a template in the comparator, it must be declared outside of function scope. Live example on Coliru Viewer.

3. Wait for C++14

And with generic lambdas added to C++14, you can use the following with a conformant compiler:

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);

Again, live example on Coliru Viewer.

---

Also, C-style struct typedefs are unnecessary in C++ (and arguably unclear most places in C), so anywhere you have

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

you can replace it with

struct Foo {
    // ...
};

without any other changes required of your code.

Sardonyx

Thanks, great answer. It would have been nice to have the whole comparator embedded in a lambda rather than an external templatized comparator - but I am not sure if that is possible. Thanks again – Braxton

That can still be accomplished by creating a type that can be implicitly converted to from both. Here's (yet another) live example. I'll add that to my answer. – Sardonyx

Thanks again, Unfortunately, I'm using VS 2013 with update 2 CTP, so I don't have the indicated C++14 auto types yet. Also, I think I might have oversimplified the concocted example I threw together earlier, as the common field types are different types (one is a boost path and the other is a std::string - path is convertible to std::string though. This does not work with the template comparator{} - I should have stated this in my example. Do you know of a decltype meta programming technique which I could use to modify the comparator? I think its possible but the syntax baffles me. – Braxton

No need for metaprogramming. The first solution can be easily adapted to using boost::filesystem::path. All I had to change was the implicit constructor for Common from StructA. Check out line 29 in this live example. – Sardonyx

A common struct it shall be! Thanks again! – Braxton

Although I got the common struct approach to work (thanks to your help), Do you know how to implement the same solution via Meta-programming? I can see a situation where the meta-programming approach might be extremely useful - specifically if I different types of structs with dramatically different common fields – Braxton

What kind of interface do you have in mind for a meta-programming solution? Do you have an example? I think a wrapping structure approach could be extended to every type you could need. You could also add templated constructors to it if you want to avoid naming the specific type. – Sardonyx

Answer 2

use std::copy_if and lambda that searches inside vectorB using std::binary_search be sure to sort using the same predicate you will give to binary_search

this solves similar problem: elegant way to remove all elements of a vector that are contained in another vector?

Formenti

Answer 3

set_intersection isn't magic, if you have sorted vectors it is very easy to roll your own, roughly like this:

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;
    }
}

Cassino