C++ check if unordered_set is subset of another unordered_set using hash function

Question

I know that one solution is by using includes(), but I'm trying to improve the run time using hash function.

I'm not good with hashing in general!!

In my code, I have struct namely Sstruct is defined as:

 struct Sstruct {
            int V1;
            float Vs;
        };

I also have S1 as unordered_set of type Sstruct has 4 integer elements, and each element associated with float values. Let S1=

S1 = { { 1, 0.933 },{ 2, 0.899 }, { 3, 0.919 }, { 4, 0.726 } }

and I have S2 as unordered_map where its values is unordered_set of Sstruct. Let S2=

S2 ={ 
     { { 1, 0.933 },{ 2, 0.899 }, { 3, 0.919 }, { 4, 0.726 } },
     { { 2, 0.906 },{ 3, 0.994 }, { 4, 0.726 } },
     { { 3, 0.865 },{ 4, 0.933 }, { 5, 0.919 } }
    }

and I want to check if S2 is subset from S1

this means:

I check if the first unordered_set in S2: { { 1, 0.933 },{ 2, 0.899 }, { 3, 0.919 }, { 4, 0.726 } } is subset from S1: { { 1, 0.933 },{ 2, 0.899 }, { 3, 0.919 }, { 4, 0.726 } }

note: I only care about the integer number in the unordered_set

then, I check if the second unordered_set in S2 is subset from S1 then, I check if the third unordered_set in S2 is subset from S1

The program work okay when I declare my unordered_set as integer like:

std::tr1::unordered_set<int>

but it gives me error: error C2338: The C++ Standard doesn't provide a hash for this type, when I declare my unordered_set as Sstruct like:

    std::tr1::unordered_set<Sstruct>

Update:

I solved the errors thanks to @praetorian for telling me that I have to use a specialization of std::hash for my struct, I spent many hours reading about it, I'm not saying I become full understand the whole hashing idea but I'm in the process.

thanks also to @pavel-minaev

and: How to specialize std::hash<Key>::operator() for user-defined type in unordered containers?

+ How to determine if a list is subset of another list?

This the code after updating:

#include "stdafx.h"
#include <iostream> 
#include <boost/tr1/unordered_set.hpp>
#include <boost/tr1/unordered_map.hpp>

struct Sstruct {
    int V1;
    float Vf;
};


    bool operator==(Sstruct a, Sstruct b) { return a.V1 == b.V1; }

    struct MyHash {
        size_t operator()(const Sstruct& x) const { return std::hash<int>()(x.V1); }
    };

    std::unordered_set<Sstruct, MyHash> s;

    std::tr1::unordered_map <int, std::unordered_set<Sstruct, MyHash>> S2;



    bool includes(const std::tr1::unordered_set<Sstruct, MyHash>& S1, const std::tr1::unordered_map <int, std::unordered_set<Sstruct, MyHash>>::const_iterator& iter)
{


        for ( std::tr1::unordered_set<Sstruct, MyHash>::const_iterator iter2 = iter->second.begin(); iter2 != iter->second.end(); ++iter2)

            if (S1.find(*iter2) == S1.end())
            {
                    return false;
                }

            return true;



}

int main()
{

    std::tr1::unordered_set<Sstruct, MyHash> S1{ { 1, 0.9 }, { 2, 0.8 }, { 3, 0.9 }, { 4, 0.7 } };

    S2[0].insert( { { 1, 0.933 }, { 2, 0.899 }, { 3, 0.919 }, { 4, 0.726 } });
    S2[1].insert({ { 2, 0.906 }, { 3, 0.994 }, { 4, 0.726 } });
    S2[2].insert({ { 3, 0.865 }, { 4, 0.933 }, { 5, 0.919 } });


    for (std::tr1::unordered_map <int, std::unordered_set<Sstruct, MyHash>>::const_iterator iter = S2.begin(); iter != S2.end(); ++iter)
    {
        if ((includes(S1, iter)) == true)
            std::cout << "S1 is a superset of S2";
        else
            std::cout << "S1 not a superset of S2";
        std::cout << "\n";
    }

    std::cin.get();
}

You should really think about adding some `typedef`s instead of those long long type names. I'm having a hard time keeping all that straight in my head. Anyway, you'll need a specialization of `std::hash` for `Sstruct` (or provide as custom hash functor as template argument), take a look at `boost::hash::combine` for how to get this done easily. — Praetorian, Jun 11 '14 at 20:29
I don't even know what you are trying to do here. How exactly could things like `S2.insert(inner1.begin(), inner1.end());` ever work, for starters? — T.C., Jun 11 '14 at 20:38
@t-c I wrote this small program as part of another large one. I just want to focus on the problem. in my original program, S2 is increased in loop, every loop I insert different unordered_set with different size, let simplify that by the following example, let S2 at the first time has 2 sets with size one, S2[0]={1}, S2[1]={5}, when the first round finished, I check if S2[0]={1} is in S1, then I check if S2[2]={5} is in S1. At the second round, S2[3]={1, 2}, S2[4]={1,4}, S2[5]={5,4}, I again check if these unordered_set is in S1 — phoenix, Jun 11 '14 at 22:00
@quantdev actually, if I hide entire code expect this line: `std::tr1::unordered_set`, I still get the first error, `error C2338: The C++ Standard doesn't provide a hash for this type.` When I click on the this error it opens: xstddef standard header, and point to the line: `// TEMPLATE STRUCT hash template struct hash : public _Bitwise_hash<_Kty> { // hash functor for enums static const bool _Value = __is_enum(_Kty); static_assert(_Value, "The C++ Standard doesn't provide a hash for this type."); };` — phoenix, Jun 11 '14 at 22:24
If you want to use `unordered_set` for your type, then your type needs to be hashable. So yes, you will need to specialize `std::hash` for your type (or explicitly provide a different hasher as template type parameter to `unordered_set`). — Pavel Minaev, Jun 12 '14 at 19:17

C++ check if unordered_set is subset of another unordered_set using hash function

0 Answers0