title: C++ STL map: is access time O(1)?
body: <p>Is key look up on <code>std::map</code> O(1)? I thought it was until I thought about it more. It is based on a tree implementation so the lookup time should be O(log N), correct?</p>
  
  <p>And, is it possible to have O(1) look up on string key, <code>std::unordered_map</code> perhaps?</p>