title: C++ std::unordered_map complexity
body: <p>I've read a lot about <a href="http://www.cplusplus.com/reference/unordered_map/unordered_map/" rel="noreferrer">unordered_map</a> <em>(c++11)</em> <strong>time-complexity</strong> here at stackoverflow, but I haven't found the answer for my question.</p>
  
  <p>Let's assume indexing by integer (just for example):</p>
  
  <p>Insert/at functions work constantly (in average time), so this example would take O(1)</p>
  
  <pre><code>std::unordered_map&lt;int, int&gt; mymap = {
              { 1, 1},
              { 100, 2},
              { 100000, 3 }
  };
  </code></pre>
  
  <p><strong>What I am curious about is how long does it take to iterate through all (unsorted) values stored in map - e.g.</strong></p>
  
  <pre><code>for ( auto it = mymap.begin(); it != mymap.end(); ++it ) { ... }
  </code></pre>
  
  <p>Can I assume that each stored value is accessed only once (or twice or constant-times)? That would imply that iterate through all values is in N-valued map O(N). The other possibility is that my example with keys {1,10,100000} could take up to 1000000 iteration (if represented by array)</p>
  
  <p>Is there any other container, that can be iterated linearly and value accessed by given key constantly?</p>
  
  <p><strong>What I would really need is</strong> (pseudocode)</p>
  
  <pre><code>myStructure.add(key, value) // O(1)
  value = myStructure.at(key) // O(1)
  for (auto key : mySructure) {...} // O(1) for each key/value pair = O(N) for N values
  </code></pre>
  
  <p>Is std::unordered_map the structure I need?</p>
  
  <p>Integer indexing is sufficient, average complexity as well.</p>