title: How can I hash a std::unordered_map::const_iterator?
body: <p>Do you remember my prior question: <a href="https://stackoverflow.com/questions/42023755/what-is-causing-data-race-in-stdasync-here">What is causing data race in <code>std::async</code> here?</a><br>
  Even though I successfully parallelized this program, it <strong>still</strong> ran too slowly to be practical.<br>
  So I tried to improve the data structure representing a Conway's Game of Life pattern.<br>
  Brief explanation of the new structure:</p>
  
  <pre><code>class pattern {
      // NDos::Lifecell represents a cell by x and y coordinates.
      // NDos::Lifecell is equality comparable, and has std::hash specialization.
  private:
      std::unordered_map&lt;NDos::Lifecell, std::pair&lt;int, bool&gt;&gt; cells_coor;
      std::unordered_set&lt;decltype(cells_coor)::const_iterator&gt; cells_neigh[9];
      std::unordered_set&lt;decltype(cells_coor)::const_iterator&gt; cells_onoff[2];
  public:
      void insert(int x, int y) {
          // if coordinate (x,y) isn't already ON,
          // turns it ON and increases the neighbor's neighbor count by 1.
      }
      void erase(int x, int y) {
          // if coordinate (x,y) isn't already OFF,
          // turns it OFF and decreases the neighbor's neighbor count by 1.
      }
      pattern generate(NDos::Liferule rule) {
          // this advances the generation by 1, according to the rule.
          // (For example here, B3/S23)
          pattern result;
          // inserts every ON cell with 3 neighbors to result.
          // inserts every OFF cell with 2 or 3 neighbors to result.
          return result;
      }
      // etc...
  };
  </code></pre>
  
  <p>In brief, <code>pattern</code> contains the cells. It contains every ON cells, and every OFF cells that has 1 or more ON neighbor cells. It can also contain spare OFF cells.<br>
  <code>cells_coor</code> directly stores the cells, by using their coordinates as keys, and maps them to their number of ON neighbor cells (stored as <code>int</code>) and whether they are ON (stored as <code>bool</code>).</p>
  
  <p><code>cells_neigh</code> and <code>cells_onoff</code> indirectly stores the cells, by the iterators to them as keys.<br>
  The number of ON neighbor of a cell is always 0 or greater and 8 or less, so <code>cells_neigh</code> is a size 9 array.<br>
  <code>cells_neigh[0]</code> stores the cells with 0 ON neighbor cells, <code>cells_neigh[1]</code> stores the cells with 1 ON neighbor cell, and so on.<br>
  Likewise, a cell is always either OFF or ON, so <code>cells_onoff</code> is a size 2 array.<br>
  <code>cells_onoff[false]</code> stores the OFF cells, and <code>cells_onoff[true]</code> stores the ON cells.<br>
  Cells must be inserted to or erased from all of <code>cells_coor</code>, <code>cells_neigh</code> and <code>cells_onoff</code>. In other words, if a cell is inserted to or erased from one of them, it must be so also for the others. Because of this, the elements of <code>cells_neigh</code> and <code>cells_onoff</code> is <code>std::unordered_set</code> storing the iterators to the actual cells, enabling fast access to the cells by a neighbor count or OFF/ON state.</p>
  
  <p>If this structure works, the insertion function will have average time complexity of <code>O(1)</code>, the erasure also <code>O(1)</code>, and the generation <code>O(cells_coor.size())</code>, which are great improval of time complexity from the prior structure.</p>
  
  <p>But as you see, there is a problem: <strong>How can I hash a <code>std::unordered_map::const_iterator</code>?</strong><br>
  <code>std::hash</code> prohibits a specialization for them, so I have to make a custom one.<br>
  Taking their address won't work, as they are usually acquired as rvalues or temporaries.<br>
  Dereferencing them also won't work, as there are multiple cells that have 0 ON neighbor cells, or multiple cells that is OFF, etc.<br>
  So what can I do? If I can't do anything, <code>cells_neigh</code> and <code>cells_onoff</code> will be <code>std::vector</code> or something, sharply degrading the time complexity.</p>