title: Collisions in unordered_multimap when iterating through bucket via local_it
body: <p>In the code below, I have a number of strings (DNA sequences)
  that I am storing in a vector. I have a <code>struct</code>, <code>read_tag</code> that I use to identify each string; <code>read_tag.read_id</code> is the string identifier. I take 30 character substrings of each string and use it as a key in an  <code>unordered_multimap</code> with the <code>read_tag</code> as a value; the aim is to group strings that share a 30 character sequence. Naturally, identical string will hash to the same value, and end up in the same bucket in the multi map. Offset is used to give the "shift" from index zero of the 30 character tag. </p>
  
  <p>However, when I run this code, iterating through each bucket; I find that there are multiple different sequences in the same bucket. I thought collisions were resolved in <code>unordered_mutlimap</code>, and therefore in a bucket, their should just be one key (string). I understand that collision can happen, but I thought that either chaining, probing etc was implemented in <code>unordered_mutlimap</code>. 
  You should be able to run and check output to see where I am getting confused. </p>
  
  <p>I also <code>std::hash</code> the each key, one in a bucket, and I find that the keys in the "collisions" have a different hash value. </p>
  
  <p>So, it's as if collisions are happening, resulting in values with diff. keys in the same bucket, but in contradiction, the keys hashed to different vals.
  Is their a way to avoid this, and differentiate values based on keys within buckets?
  Or do I need to do implement this? </p>
  
  <pre><code>#include &lt;iostream&gt;                                                                                   
  #include &lt;string&gt;                                                                                     
  #include &lt;unordered_map&gt;                                                                              
  #include &lt;vector&gt;                                                                                     
  #include &lt;functional&gt;                                                                                 
  
  using namespace std;                                                                                  
  
  
  int main() {                                                                                          
  
  
    vector&lt;string&gt;  reads;                                                                              
  
    reads.push_back("CCAGCTGCTCTCACCCTGGGCAGGGTCCCTGCACACACTGTATCTTTTGAGGTCCCTTCAGGACCCCGGTTTGCTGCCTC");
    reads.push_back("CCAGCTGCTCTCACCCTGGGCAGGGTCCCTGCACACACTGTATCTTTTGAGGTCCCTTCAGGACCCCGGTTTGCTGCCTC");
    reads.push_back("GGCAGGGTCATACCCGATTAACTTGTTATAGAGTATGGGGCATCAACTTGGGCAGCAATGGGGAACGGTGTCTCTGGAAG");
    reads.push_back("CCAGCTGCTCTCACCCTGGGCAGGGTCCCTGCACACACTGTATCTTTTGAGGTCCCTTCAGGACCCCGGTTTGCTGCCTC");
    reads.push_back("GGCAGGGTCATACCCGATTAACTTGTTATAGAGTATGGGGCATCAACTTGGGCAGCAATGGGGAACGGTGTCTCTGGAAG");
    reads.push_back("GGCAGGGTCATACCCGATTAACTTGTTATAGAGTATGGGGCATCAACTTGGGCAGCAATGGGGAACGGTGTCTCTGGAAG");
    reads.push_back("GGCAGGGTCATACCCGATTAACTTGTTATAGAGTATGGGGCATCAACTTGGGCAGCAATGGGGAACGGTGTCTCTGGAAG");
    reads.push_back("CCGGGCGTGGTGGCGTGCACCTGTAATCCCAGCTACTTGGGATGTTCAGGCAGGAGACTCGCTTGATCCCCGGGGACGGA");
    reads.push_back("CCGGGCGTGGTGGCGTGCACCTGTAATCCCAGCTACTTGGGATGTTCAGGCAGGAGACTCGCTTGATCCCCGGGGACGGA");
    reads.push_back("CCGGGCGTGGTGGCGTGCACCTGTAATCCCAGCTACTTGGGATGTTCAGGCAGGAGACTCGCTTGATCCCCGGGGACGGA");
    reads.push_back("CCGGGCGTGGTGGCGTGCACCTGTAATCCCAGCTACTTGGGATGTTCAGGCAGGAGACTCGCTTGATCCCCGGGGACGGA");
    reads.push_back("CCAGCTGCTCTCACCCTGGGCAGGGTCCCTGCACACACTGTATCTTTTGAGGTCCCTTCAGGACCCCGGTTTGCTGCCTC");
  
    struct read_tag{                                                                                    
      unsigned int read_id;    // unique string identifier                                                                          
      int offset;              // shift of 30 character substring represented by tag                                                                                                                                            
    };                                                                                                  
  
    unordered_multimap&lt;string, read_tag&gt; mutation_grouper;                                              
  
    for(int read_id=0; read_id &lt; reads.size(); read_id++) {                                             
      string read = reads[read_id];                                                                                              
      for(int i=0; i &lt; read.size()-30; i++) {                                                                                                                            
        string sub_read = read.substr(i, 30);                                                           
        read_tag next_tag;                                                                              
        pair&lt;string, read_tag&gt; key_val;                                                                 
  
        next_tag.read_id = read_id;                                                                     
        next_tag.offset = i;                                                                                                                                             
  
        key_val.first = sub_read;                                                                       
        key_val.second = next_tag;                                                                      
  
        mutation_grouper.insert(key_val);                                                               
      }                                                                                                 
    }                                                                                                   
  
    cout &lt;&lt; "mutation_grouper buckets" &lt;&lt; endl;                                                         
    std::hash&lt;std::string&gt; hash_er;                                                                     
  
    for(unsigned int bucket = 0;  bucket &lt; mutation_grouper.bucket_count(); bucket++) {
  
      cout &lt;&lt; "Bucket: " &lt;&lt; bucket &lt;&lt; endl;                                                    
      for( auto local_it = mutation_grouper.begin(bucket);                                     
       local_it != mutation_grouper.end(bucket); ++local_it) {                             
  
        cout &lt;&lt; local_it-&gt;first &lt;&lt; " : " &lt;&lt; local_it-&gt;second.read_id                           
        &lt;&lt; ", " &lt;&lt; local_it-&gt;second.offset &lt;&lt; ", " &lt;&lt; endl;                                               
  
        cout &lt;&lt; "hash value: " &lt;&lt; local_it-&gt;first &lt;&lt;"::: " &lt;&lt; hash_er(local_it-&gt;first) &lt;&lt; endl;
  
       }                                                                                        
       cout &lt;&lt; endl &lt;&lt; endl;                                                                    
     }                                                                                          
   }     
  </code></pre>