title: C++11 unordered_map time complexity
body: <p>I'm trying to figure out the best way to do a cache for resources. I am mainly looking for native C/C++/C++11 solutions (i.e. I don't have boost and the likes as an option).</p>
  
  <p>What I am doing when retrieving from the cache is something like this:</p>
  
  <pre><code>Object *ResourceManager::object_named(const char *name) {
      if (_object_cache.find(name) == _object_cache.end()) {
          _object_cache[name] = new Object();
      }
      return _object_cache[name];
  }
  </code></pre>
  
  <p>Where <code>_object_cache</code> is defined something like: <code>std::unordered_map &lt;std::string, Object *&gt; _object_cache;</code></p>
  
  <p>What I am wondering is about the time complexity of doing this, does find trigger a linear-time search or is it done as some kind of a look-up operation?</p>
  
  <p>I mean if I do <code>_object_cache["something"];</code> on the given example it will either return the object or if it doesn't exist it will call the default constructor inserting an object which is not what I want. I find this a bit counter-intuitive, I would have expected it to report in some way (returning <code>nullptr</code> for example) that a <code>value</code> for the <code>key</code> couldn't be retrieved, not second-guess what I wanted.</p>
  
  <p>But again, if I do a <code>find</code> on the key, does it trigger a big search which in fact will run in linear time (since the key will not be found it will look at every key)?</p>
  
  <p>Is this a good way to do it, or does anyone have some suggestions, perhaps it's possible to use a look up or something to know if the key is available or not, I may access often and if it is the case that some time is spent searching I would like to eliminate it or at least do it as fast as possible.</p>
  
  <p>Thankful for any input on this.</p>