title: C++ Unordered Map Constant Time Access?
body: <p>I am researching the C++ unordered_map container type. I am just verifying something I read from the C++ website on element access with <a href="http://www.cplusplus.com/reference/unordered_map/unordered_map/operator[]/" rel="nofollow">operator[]</a>.</p>
  
  <p>It says that the time complexity is usually constant, but worst case is linear time. Since my application must guarantee constant time access to elements inside of this map, I wanted to verify my understanding of this container.</p>
  
  <p>Whenever my application accesses elements inside of this unordered_map, the object it is looking for is guaranteed to exist, so the container will never try to add in a missing element. Since I am only doing <strong>look ups</strong>, does that mean that the unordered_map will always give me <strong>constant time access</strong>? The <strong>linear time</strong> case is only for certain cases where an <strong>insertion</strong> will occur, is that correct?</p>
  
  <p>Edit: The elements inside of the unordered_map are guaranteed to be unique. They hold the addresses of several unique objects existing in memory.</p>