C++11 unordered_map 时间复杂度

Question

我正在尝试找出对资源进行缓存的最佳方法。我主要是在寻找 native C/C++/C++11 解决方案(即我没有 boost 之类的选项)。

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

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;

我想知道这样做的时间复杂度，find 会触发线性时间搜索还是作为某种查找操作完成？

我的意思是如果我这样做 _object_cache["something"];在给定的示例中，它将返回对象，或者如果它不存在，它将调用默认构造函数插入一个不是我想要的对象。我觉得这有点违反直觉，我本以为它会以某种方式报告(例如返回 nullptr)value对于 key无法找回，不要猜测我想要什么。

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

这是一个好方法吗，或者有人有什么建议吗，也许可以使用查找或其他方法来了解 key 是否可用，我可能会经常访问，如果是这样的话一些时间花在搜索上我想消除它或至少尽快完成。

感谢您对此的任何投入。

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[] 的性能是一样的；平均常数，最坏情况线性(仅当无序映射中的每个键都具有相同的哈希值时)。