set_intersection for two different types of sets

Question

Is there any way to do std::set_intersection on two different types of sets?

I have two sets:

std::set<X1> l_set1;
std::set<X2> l_set2;

I'm able to define some comparator for them that checks if X1 and X2 are equal.

struct sample_comparer
{
    bool operator()(const &X1 p_left, const &X2 p_right)
    {
        return p_left == p_right;
    }
};

Now, I try to do a set intersection on those two sets:

std::set<X1> l_intersect;
std::set_intersection(l_set1.begin(), l_set1.end(), l_set2.begin(), l_set2.end(),
                      std::inserter(l_intersect, l_intersect.begin()), sample_comparer());

Unfortunately, I can't force this code to work. I'm not even sure if this is possible, but from the description of set_intersection I know that I can use two different iterators.

I tried to search for some code samples that do what I want, but didn't found any? Could someone present me a working code sample for my problem?

Update: the error is:

error: stl_function.h:227: no match for 'operator<' in '__x < __y'

Thanks in advance!

Vedda

"Unfortunately, I can't force this code to work." What compiler errors do you get? – Rectangular

Your sample comparer doesn't do the right thing. It needs to be a less than, imposing a strict weak ordering on the compared elements. – Shockley

Did you try providing a overloaded < operator bool operator<(X1,X2) – Saltandpepper

besides that, you need a comparator for both directiony x1 < x2 and x2 < x1 – Embed

Answer 1

The comment by PlasmaHH is likely the problem.

The way functions like set_intersection work is they first do: a < b and then b < a

As a result ample_comparer needs to be able to compare both ways:

struct sample_comparer
{
    bool operator()(const &X1 p_left, const &X2 p_right)
    {
        return p_left == p_right;
    }
    bool operator()(const &X2 p_left, const &X1 p_right)
    {
        return p_left == p_right;
    }
};

The following doesn't actually do anything sensible - but it does compile cleanly:

struct A
{
  struct Compare { bool operator () (A const &, A const &) { return false;}  };
};

struct B
{
  struct Compare { bool operator () (B const &, B const &) { return false; } };
};

typedef std::set<A, A::Compare> S1;
typedef std::set<B, B::Compare> S2;

class IntersectionCompare
{
public:
  bool operator ()(S1::value_type, S2::value_type) { return false; } 
  bool operator ()(S2::value_type, S1::value_type) { return false; } 
};

void bar (S1 & s1, S2 & s2)
{
  S1 result;
  std::set_intersection (s1.begin ()
      , s1.end ()
      , s2.begin ()
      , s2.end ()
      , std :: insert_iterator< S1 > (result, result.end ())
      , IntersectionCompare ());
}

Eberhart

Answer 2

It won't work as both inputs must be assignable to the output iterator type. You might add some implicit conversion operators to X1, X2 which converts between them to get that working.

Serval

For set_intersection the output range just needs to allow conversions from one of the inputs (although it isn't specified which one). Something like set_union or set_difference requires conversions from both types. – Eberhart

Answer 3

I don't think it is possible as it is, (at least without user-defined conversion). From the section "Requirements on types" in documentation: InputIterator1 and InputIterator2 have the same value type.

Homeland

Thanks for the answer and thanks for pointing the solution in the docs – Vedda

Why would the function allow for two different input iterator types if the value needed to be identical? – Eberhart

Answer 4

First of all according to the docs set_intersection is using a operator<. And second you can make a third struct that will extract from the type the fields you will use to do compare

std::set<X1> l_set1;
std::set<X2> l_set2;
struct XCompare
{        
    int value;
    XCompare(const X1& x)
    {
        value = x.value;
    }

    XCompare(const X2& x)
    {
        value = x.value;
    }
}

std::set_intersection(...,...,[](const XCompare& c1, const XCompare& c2){ 
... }  )

You can go down this path and create a custom wrapper that can do anything unless your two types can compare

template<typename T1, typename T2>
struct ValueWrapper
{
    T1 const* v1 = nullptr;
    T2 const* v2 = nullptr;

    ValueWrapper(const T1& value)
    {
        v1 = &value;
    }

    ValueWrapper(const T2& value)
    {
        v2 = &value;
    }

    bool operator<(const ValueWrapper& other)
    {
        if (v1 != nullptr)
        {
             if (other.v1 != nullptr)
             { 
                 return *v1 < *(other.v2)
             }

... } }

template<typename T1, typename T2>
struct ValueWrapperComparator
{
     bool operator()(ValueWrapper<T1,T2> v1, ValueWrapper<T1,T2> v2)
     {
         return v1 < v2;
     }
}

Something like that. I didn't test it and it won't compile but you get the point. Maybe something similiar is hidden something similiar somewhere in the STL libraries

Edit: Btw i think you can use some kind of variant type (boost::variant or std::variant) I think it does this already...

Kitchenware