C++11 unordered_map time complexity

Question

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).

What I am doing when retrieving from the cache is something like this:

Object *ResourceManager::object_named(const char *name) {
    if (_object_cache.find(name) == _object_cache.end()) {
        _object_cache[name] = new Object();
    }
    return _object_cache[name];
}

Where _object_cache is defined something like: std::unordered_map <std::string, Object *> _object_cache;

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?

I mean if I do _object_cache["something"]; 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 nullptr for example) that a value for the key couldn't be retrieved, not second-guess what I wanted.

But again, if I do a find 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)?

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.

Thankful for any input on this.

Answer 1

The default constructor (triggered by _object_cache["something"]) is what you want; the default constructor for a pointer type (e.g. Object *) gives nullptr (8.5p6b1, footnote 103).

So:

auto &ptr = _object_cache[name];
if (!ptr) ptr = new Object;
return ptr;

You use a reference into the unordered map (auto &ptr) as your local variable so that you assign into the map and set your return value in the same operation. In C++03 or if you want to be explicit, write Object *&ptr (a reference to a pointer).

Note that you should probably be using unique_ptr rather than a raw pointer to ensure that your cache manages ownership.

By the way, find has the same performance as operator[]; average constant, worst-case linear (only if every key in the unordered map has the same hash).