C++

Forum

 
error with unordered_map + hash functiom

phoenixm (5)
First, I just learn hashing
Second, I wrote the following code to: Whether unordered_set is subset of another unordered_set or not using hash function:

Example:
Let S1=
std::tr1::unordered_set<Sstruct, MyHash> S1{ { 1, 0.9, 0.1 }, { 2, 0.8, 0.2 }, { 3, 0.9, 0.01 }, { 4, 0.7, 0.5 } };

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

S2[0].insert({ { 1, 0.933, 0.02 }, { 2, 0.899, 0.3 }, { 3, 0.919, 0.4 } });
S2[1].insert({ { 3, 0.865, 0.1 }, { 4, 0.933, 0.2 }, { 5, 0.919, 0.3 } });

and I want to check if S2[0] is a subset of S1, then if S2[1] is a subset of S1

This the code for that, and it works 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
 
    #include "stdafx.h"
    #include <iostream> 
    #include <boost/tr1/unordered_set.hpp>
    #include <boost/tr1/unordered_map.hpp>
    
    struct Sstruct {
    	int Iv;
    	float Fv1;
    	float Fv2;
    };
    
    
    bool operator==(Sstruct a, Sstruct b) { return a.Iv == b.Iv; }
    
    struct MyHash {
    	size_t operator()(const Sstruct& x) const { return std::hash<int>()(x.Iv); }
    };
    
    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, 0.1 }, { 2, 0.8, 0.2 }, { 3, 0.9, 0.01 }, { 4, 0.7, 0.5 } };
    	std::tr1::unordered_map <int, std::unordered_set<Sstruct, MyHash>> S2;
    
    	S2[0].insert({ { 1, 0.933, 0.02 }, { 2, 0.899, 0.3 }, { 3, 0.919, 0.4 } }); //  S2 is a subset of S1
    	S2[1].insert({ { 3, 0.865, 0.1 }, { 4, 0.933, 0.2 }, { 5, 0.919, 0.3 } }); // S2 is not a subset of S1
    
    
    	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 << "S2 is a subset of S1";
    		else
    			std::cout << "S2 is not a subset of S1";
    		std::cout << "\n";
    	}
    
    	std::cin.get();
    }


Then, I want to edit my code, instead of printing **"S2 is a not subset of S1"**, I want save the result in new `unordered_map` contains:

key: unordered_set of type integer contains `(S1.begin()->Iv, S1.end()->Iv)`
value: three values:

1- summation of `S1` first float value `Fv1`

2- average of `S1` second float value `Fv2`

3- product of (1) and (2)

Note in my program, every time I read different unordered_set `S1`, but here just to Focus on the problem, I initialize one unordered_set `S1`

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
 
    int main()
    {  	
   
    	std::tr1::unordered_set<Sstruct, MyHash> S1{ { 1, 0.9, 0.1 }, { 2, 0.8, 0.2 }, { 3, 0.9, 0.01 }, { 4, 0.7, 0.5 } };
    
    	std::tr1::unordered_map <int, std::unordered_set<Sstruct, MyHash>> S2;
    	
    	S2[0].insert( { { 1, 0.933, 0.02 }, { 2, 0.899, 0.3 }, { 3, 0.919, 0.4 }}); //  S2 is a subset of S1
    	S2[1].insert({ { 3, 0.865, 0.1 }, { 4, 0.933, 0.2 }, { 5, 0.919, 0.3 } }); // S2 is not a subset of S1
    
    	
    	
    	typedef std::pair<float, float > comp;
    	typedef std::pair<float, comp> comp2;
    
    	std::tr1::unordered_map <std::unordered_set<int>, comp2 >  totalval;
    	comp2 p2;
    	
   
    			for (std::tr1::unordered_map <int, std::unordered_set<Sstruct, MyHash>>::const_iterator iter = S2.begin(); iter != S2.end(); ++iter)
    		{
    			if ((includes(S1, iter)) == false)
    			{
    				float fv1 = 1;
    				float fv2 = 0;
    				float fv3 = 1;
    				std::tr1::unordered_set<Sstruct> ::iterator it = S1.begin();
    
    
    				while (it != S1.end())
    				{ // if S2 is not a subset of S1
    					fv1 *= it->Fv1;
    					fv2 += it->Fv2;
    					++it;
    				}
    				fv2 = fv2 / S1.size();
    
    				std::tr1::unordered_set<int> S3(S1.begin()->Iv, S1.end()->Iv);
    				totalval[S3].first += fv1;
    				fv3 = fv2 * totalval[S3].first;
                                totalval[S3].second.first = fv2;
				totalval[S3].second.second =  fv3;
    			}
    			else
    				std::cout << "S2 is a subset of S1";
    
    		}
    			
    	
    	std::cin.get();
    }


This is the error I got:

error C2338: The C++ Standard doesn't provide a hash for this type. 1> c:\program files (x86)\microsoft visual studio
12.0\vc\include\type_traits(572) : see reference to class template instantiation 'std::hash<_Kty>' being compiled 1> with 1> [ 1>
_Kty=std::unordered_set<int,std::hash<int>,std::equal_to<int>,std::allocator<int>> 1> ] 1> c:\program files (x86)\microsoft visual studio 12.0\vc\include\xhash(196) : see reference to class template instantiation 'std::is_empty<_Hasher>' being compiled 1> with 1> [ 1>
_Hasher=std::hash<std::unordered_set<int,std::hash<int>,std::equal_to<int>,std::allocator<int>>> 1> ] 1> c:\program files (x86)\microsoft visual studio 12.0\vc\include\xhash(220) : see reference to class template instantiation 'std::_Hash_oper2<false,_Hasher,_Keyeq>' being compiled 1> with 1> [ 1>
_Hasher=std::hash<std::unordered_set<int,std::hash<int>,std::equal_to<int>,std::allocator<int>>> 1> ,
_Keyeq=std::equal_to<std::unordered_set<int,std::hash<int>,std::equal_to<int>,std::allocator<int>>> 1> ] 1> c:\program files (x86)\microsoft visual studio 12.0\vc\include\unordered_map(23) : see reference to class template instantiation 'std::_Uhash_compare<_Kty,_Hasher,_Keyeq>' being compiled 1> with 1> [ 1>
_Kty=std::unordered_set<int,std::hash<int>,std::equal_to<int>,std::allocator<int>> 1> ,
_Hasher=std::hash<std::unordered_set<int,std::hash<int>,std::equal_to<int>,std::allocator<int>>> 1> ,
_Keyeq=std::equal_to<std::unordered_set<int,std::hash<int>,std::equal_to<int>,std::allocator<int>>> 1> ] 1> c:\program files (x86)\microsoft visual studio 12.0\vc\include\xhash(255) : see reference to class template instantiation 'std::_Umap_traits<_Kty,_Ty,std::_Uhash_compare<_Kty,_Hasher,_Keyeq>,_Alloc,false>' being compiled 1> with 1> [ 1>
_Kty=std::unordered_set<int,std::hash<int>,std::equal_to<int>,std::allocator<int>> 1> , _Ty=comp2 1> ,
_Hasher=std::hash<std::unordered_set<int,std::hash<int>,std::equal_to<int>,std::allocator<int>>> 1> ,
_Keyeq=std::equal_to<std::unordered_set<int,std::hash<int>,std::equal_to<int>,std::allocator<int>>> 1> , _Alloc=std::allocator<std::pair<const std::unordered_set<int,std::hash<int>,std::equal_to<int>,std::allocator<int>>,comp2>> 1> ] 1> c:\program files (x86)\microsoft visual studio 12.0\vc\include\unordered_map(81) : see reference to class template instantiation 'std::_Hash<std::_Umap_traits<_Kty,_Ty,std::_Uhash_compare<_Kty,_Hasher,_Keyeq>,_Alloc,false>>' being compiled 1> with 1> [ 1>
_Kty=std::unordered_set<int,std::hash<int>,std::equal_to<int>,std::allocator<int>> 1> , _Ty=comp2 1> ,
_Hasher=std::hash<std::unordered_set<int,std::hash<int>,std::equal_to<int>,std::allocator<int>>> 1> ,
_Keyeq=std::equal_to<std::unordered_set<int,std::hash<int>,std::equal_to<int>,std::allocator<int>>> 1> , _Alloc=std::allocator<std::pair<const std::unordered_set<int,std::hash<int>,std::equal_to<int>,std::allocator<int>>,comp2>> 1> ] 1> c:\users\documents\visual studio 2013\projects\hashtables_set-superset\hashtables_set-superset\hashtables_set-superset.cpp(52) : see reference to class template instantiation 'std::unordered_map<std::unordered_set<int,std::hash<int>,std::equal_to<_Kty>,std::allocator<_Kty>>,comp2,std::hash<std::unordered_set<_Kty,std::hash<int>,std::equal_to<_Kty>,std::allocator<_Kty>>>,std::equal_to<std::unordered_set<_Kty,std::hash<int>,std::equal_to<_Kty>,std::allocator<_Kty>>>,std::allocator<std::pair<const std::unordered_set<_Kty,std::hash<int>,std::equal_to<_Kty>,std::allocator<_Kty>>,_Ty>>>' being compiled 1> with 1> [ 1> _Kty=int 1> , _Ty=comp2 1> ]
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========



MiiNiPaa (8886)
Global: Is there any reason to use old non-standard implementation of unordered containers instead of standard?

Line 16: standard does not provide hasing function for containers. And key in key-value pair is constant, so you cannot do lines 39 and 42 too

Line 19: first Sstruct does not have std::hash specialization and second you are declaring iterator of incompatible with S1 type.


phoenixm (5)

Thanks,
Could you please explain to me, what do you mean by:
old non-standard implementation of unordered containers


I'm really confused, I'm learning STL, and I read that using has function will improve the run time. I already did use the built-in includes(), but the run time wasn't good, so I moved to hashing and I couldn't get it correctly.

I'm stuck in this point from last week, I really appreciate any help

MiiNiPaa (8886)
before C++11 standard was approved, there was test implementations of some features. They were implemented in std::tr1:: namespace. They could not use all features of new language standard, so they were somewhat lacking.
After C++11 was made official, standard implementations were created. You can see what was included in C++11 and learn more there: http://en.cppreference.com/w/ (look for C++11 mark)
phoenixm (5)

Thanks

I'm still stuck with defining
totalval
even though I redefine it like:
1
2
3
4
5
6
7
8
9
10
11
 
typedef std::unordered_set<int> LS3;
typedef std::unordered_map <LS3, float>  CandidateList;

typedef std::pair<float, float> CandidateInfo;
struct MyHash2 {
    size_t operator()(const CandidateInfo &a) const
    {
        return hash<float>()(a.first) ^ hash<float>()(a.second);
    }
};
std::unordered_map<CandidateList, CandidateInfo, MyHash2> totalval;


Still receiving: C2338: The C++ Standard doesn't provide a hash for this type.

and I'm really don't know what to do!!!!


also, I re-implement my program using stranded implementation, thank to you, and the program works.
I did two methods, with hashing, and the built-in
includes()

But I notice that there is no really big different with the run time, so I start wondering, if what I did was the idea of hashing!!

could you please look at it?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
 
#include <iostream> 
#include <unordered_set>
#include <unordered_map>
#include <iomanip>
#include <algorithm>
#include <functional>

struct Sstruct {
	int Iv;
	float Fv1;
	float Fv2;
};


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

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


bool IsIn(const std::unordered_set<int>& S1, const std::unordered_map <int, std::unordered_set<int>>::const_iterator& iter)
{
	for (std::unordered_set<int>::const_iterator iter2 = iter->second.begin(); iter2 != iter->second.end(); ++iter2)

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

	return true;

}

int main()
{



	std::unordered_set<Sstruct, MyHash> S1{ { 1, 0.9, 0.1 }, { 2, 0.8, 0.2 }, { 3, 0.9, 0.01 }, { 4, 0.7, 0.5 }, { 7, 0.7, 0.2 }, { 8, 0.1, 0.5 } };

	std::unordered_map <int, std::unordered_set<int>> S2;

	S2[0].insert({ { 1 }, { 2 }, { 3} }); //  S2 is a subset of S1
	S2[1].insert({ { 3}, { 4 }, { 5} }); // S2 is a subset of S1
	S2[3].insert({ { 2 }, { 4 } }); // S2 is  a subset of S1
	S2[4].insert({ { 3 }, { 4 }}); // S2 is  a subset of S1
	S2[5].insert({ { 3 },  { 5 } }); // S2 is a subset of S1
	S2[6].insert({ { 1 }, { 2 }, { 8 } }); //  S2 is a subset of S1
	S2[7].insert({ { 3 }, { 4 }, { 6 } }); // S2 is not a subset of S1
	S2[8].insert({ { 2 }, {7 } }); // S2 is  a subset of S1
	S2[9].insert({ { 7 }, { 8 } }); // S2 is  a subset of S1
	S2[10].insert({ { 5 }, { 6 } }); // S2 is not a subset of S1



	std::unordered_set<int > SetOne;


	for (std::unordered_set<Sstruct, MyHash> ::iterator iter = S1.begin(); iter != S1.end(); ++iter)
		SetOne.insert(iter->Iv);

	float time1, time2;

	
	time1 = (float)clock() / CLOCKS_PER_SEC;

	// method 1: using hashing
	/*for (std::unordered_map <int, std::unordered_set<int>>::const_iterator SetTwo = S2.begin(); SetTwo != S2.end(); ++SetTwo)
		{
		if ((IsIn(SetOne, SetTwo)) == true)
			std::cout << "S2 is a subset of S1";

		else
			std::cout << "S2 is not a subset of S1";

		std::cout << "\n";
	}*/

	// method 2 using STL includes()
	std::unordered_map <int, std::unordered_set<int>>::const_iterator SetTwo = S2.begin();
	while (SetTwo != S2.end())
	{
		if (std::includes(SetOne.begin(), SetOne.end(), SetTwo->second.begin(), SetTwo->second.end()))

			std::cout << "S2 is a subset of S1";

		else
			std::cout << "S2 is not a subset of S1";
		++SetTwo;
		std::cout << "\n";
	}

	time2 = (float)clock() / CLOCKS_PER_SEC;

	std::cout << "\n  Finishing Time " << time2 - time1 << " secs";
	std::cout << "\n\n";

	std::cin.get();
}


Last edited on
MiiNiPaa (8886)
Still receiving: C2338: The C++ Standard doesn't provide a hash for this type.
Keys are hashed, not values. You need to provide hashing function for CandidateList
phoenixm (5)

could you show me please how to provide hashing function for CandidateList?

I search for examples, I didn't find one like
std::unordered_map <std::unordered_set<int> , float>

even though, this try work,
1
2
3
4
 
typedef std::pair<float, float> CandidateInfo;
typedef std::unordered_set<int> LS3;
typedef std::unordered_map <LS3, std::hash<int>, float>  CandidateList;
std::unordered_map< CandidateList, std::hash<int>, CandidateInfo> Candidate;


but I couldn't deal with the container
Candidate

to insert the key CandidateList
and the value CandidateInfo
MiiNiPaa (8886)
could you show me please how to provide hashing function for CandidateList?
Point is, you should not use containers as key.
1) there is little reason to do so, as you could not change any value stored.
2) Even if you do provide hashing function, it will be slow enough to limit usefulness of unordered containers
Topic archived. No new replies allowed.