C++ 11 unordered_map时间复杂度

Question

我正在试图找出为资源进行缓存的最佳方法.我主要是寻找原生的C/C++/C++ 11解决方案(即我没有提升和喜欢的选项).

从缓存中检索时我正在做的是这样的:

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

在哪里_object_cache定义如下:std::unordered_map <std::string, Object *> _object_cache;

我想知道的是关于这样做的时间复杂性,是否找到触发线性时间搜索或者它是否作为某种查找操作完成？

我的意思是如果我_object_cache["something"];在给定的例子上做它将返回对象或如果它不存在它将调用默认构造函数插入一个不是我想要的对象.我觉得这有点违反直觉的,我本来期望它以某种方式来报告(返回nullptr为例),一个value为key无法检索,而不是第二个猜测我想要的东西.

但是,再次,如果我find在键上执行操作,是否会触发一个大搜索,实际上它将以线性时间运行(因为找不到键会查看每个键)？

这是一个很好的方法吗,或者是否有人有一些建议,也许有可能使用查找或某些东西来知道密钥是否可用,我可以经常访问,如果是这样的话,有时候是花在搜索上我想消除它,或者至少尽可能快地消除它.

感谢任何关于此的输入.

Answer 1

默认构造函数（由 触发_object_cache["something"]）就是你想要的；指针类型的默认构造函数（例如Object *）给出nullptr（8.5p6b1，脚注 103）。

所以：

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

您可以使用对无序映射 ( ) 的引用auto &ptr作为局部变量，以便在同一操作中分配给映射并设置返回值。在C++03中或者如果你想明确的话，写成Object *&ptr（对指针的引用）。

请注意，您可能应该使用unique_ptr而不是原始指针来确保您的缓存管理所有权。

顺便说一下，find具有与 相同的性能operator[]；平均常数，最坏情况线性（仅当无序映射中的每个键具有相同的哈希值时）。