title: C++ check if unordered_set is subset of another unordered_set using hash function
body: <p>I know that one solution is by using includes(), but I'm trying to improve the run time using hash function.</p>
  
  <p>I'm not good with hashing in general!!</p>
  
  <p>In my code, I have struct namely <code>Sstruct</code> is defined as:</p>
  
  <pre><code> struct Sstruct {
              int V1;
              float Vs;
          };
  </code></pre>
  
  <p>I also have <code>S1</code> as <code>unordered_set</code> of type <code>Sstruct</code> has 4 integer elements, and each element associated with float values. Let S1= </p>
  
  <pre><code>S1 = { { 1, 0.933 },{ 2, 0.899 }, { 3, 0.919 }, { 4, 0.726 } }
  </code></pre>
  
  <p>and I have <code>S2</code> as <code>unordered_map</code> where its values is <code>unordered_set</code> of <code>Sstruct</code>. Let S2=</p>
  
  <pre><code>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 } }
      }
  </code></pre>
  
  <p>and I want to check if S2 is subset from S1 </p>
  
  <p><strong>this means:</strong></p>
  
  <p>I check if the first unordered_set in <code>S2</code>: { { 1, 0.933 },{ 2, 0.899 }, { 3, 0.919 }, { 4, 0.726 } }  is subset from <code>S1</code>: { { 1, 0.933 },{ 2, 0.899 }, { 3, 0.919 }, { 4, 0.726 } }</p>
  
  <p><strong>note:</strong> I only care about the integer number in the unordered_set</p>
  
  <p>then, I check if the second unordered_set in <code>S2</code> is subset from <code>S1</code>
  then, I check if the third unordered_set in <code>S2</code> is subset from <code>S1</code></p>
  
  <p>The program work okay when I declare my unordered_set as <strong>integer</strong> like:      </p>
  
  <pre><code>std::tr1::unordered_set&lt;int&gt; 
  </code></pre>
  
  <p>but it gives me error: <code>error C2338: The C++ Standard doesn't provide a hash for this type</code>, when I  declare my unordered_set as <strong>Sstruct</strong> like:      </p>
  
  <pre><code>    std::tr1::unordered_set&lt;Sstruct&gt;  
  </code></pre>
  
  <p><strong>Update:</strong></p>
  
  <p>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. </p>
  
  <p>thanks also to @pavel-minaev</p>
  
  <p>and:
  <a href="https://stackoverflow.com/questions/8157937/how-to-specialize-stdhashkeyoperator-for-user-defined-type-in-unordered">How to specialize std::hash&lt;Key&gt;::operator() for user-defined type in unordered containers?</a></p>
  
  <p>+
  <a href="https://stackoverflow.com/questions/1335739/how-to-determine-if-a-list-is-subset-of-another-list/1338515#1338515">How to determine if a list is subset of another list?</a></p>
  
  <p>This the code after updating:</p>
  
  <pre><code>#include "stdafx.h"
  #include &lt;iostream&gt; 
  #include &lt;boost/tr1/unordered_set.hpp&gt;
  #include &lt;boost/tr1/unordered_map.hpp&gt;
  
  struct Sstruct {
      int V1;
      float Vf;
  };
  
  
      bool operator==(Sstruct a, Sstruct b) { return a.V1 == b.V1; }
  
      struct MyHash {
          size_t operator()(const Sstruct&amp; x) const { return std::hash&lt;int&gt;()(x.V1); }
      };
  
      std::unordered_set&lt;Sstruct, MyHash&gt; s;
  
      std::tr1::unordered_map &lt;int, std::unordered_set&lt;Sstruct, MyHash&gt;&gt; S2;
  
  
  
      bool includes(const std::tr1::unordered_set&lt;Sstruct, MyHash&gt;&amp; S1, const std::tr1::unordered_map &lt;int, std::unordered_set&lt;Sstruct, MyHash&gt;&gt;::const_iterator&amp; iter)
  {
  
  
          for ( std::tr1::unordered_set&lt;Sstruct, MyHash&gt;::const_iterator iter2 = iter-&gt;second.begin(); iter2 != iter-&gt;second.end(); ++iter2)
  
              if (S1.find(*iter2) == S1.end())
              {
                      return false;
                  }
  
              return true;
  
  
  
  }
  
  int main()
  {
  
      std::tr1::unordered_set&lt;Sstruct, MyHash&gt; 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 &lt;int, std::unordered_set&lt;Sstruct, MyHash&gt;&gt;::const_iterator iter = S2.begin(); iter != S2.end(); ++iter)
      {
          if ((includes(S1, iter)) == true)
              std::cout &lt;&lt; "S1 is a superset of S2";
          else
              std::cout &lt;&lt; "S1 not a superset of S2";
          std::cout &lt;&lt; "\n";
      }
  
      std::cin.get();
  }
  </code></pre>