title: How to random retrieve an element from C++ hash table in O(1)
body: <p>Is there a way to randomly retrieve an element from C++ <strong>unordered_set</strong> in O(1) average time? Instead of doing</p>
  
  <pre><code>std::unordered_set&lt;int&gt; s;
  // initialize s
  auto start = s.begin();
  for (int i = 0; i &lt; rand()%s.size()-1; ++i, ++start) {}
  int randomNumber = *start;
  </code></pre>
  
  <p><strong>Updated:</strong></p>
  
  <p>I need to fight for the post, so I add my reasons for needing the functionality of above.</p>
  
  <p>I am playing with implementing a maze generator. And somehow I need a data structure which would support:</p>
  
  <ol>
  <li>insertion / deletion in O(1)</li>
  <li>random retrieve an element from the data structure in O(1)</li>
  </ol>
  
  <p><strong>std::vector</strong> has random access, but insertion / deletion is expensive</p>
  
  <p><strong>std::list</strong> has no random access</p>
  
  <p><strong>std::set</strong> support O(logN) random access, and O(logN) insertion/ deletion, which are great, but my initialization is a sorted sequence which would easily break the balance of it.</p>
  
  <p>So I thought hash table would be the best choice, however randomly retrieval an element would be nontrivial. </p>
  
  <p>Thank you for your time.</p>