c++ - C++ 11 unordered_map时间复杂度

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

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

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，而不是second测我想要的东西。

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

这是一个好方法吗，还是有人提出一些建议，也许可以使用查找或某种方式来知道 key 是否可用，我可能会经常访问并且是否有一段时间花了很多时间搜索我想消除它，或者至少尽快完成它。

感谢您对此的任何投入。

最佳答案

您想要的是默认的构造函数(由_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[]相同的性能；平均常数，最坏情况下的线性(仅当无序映射中的每个键具有相同的哈希值时)。

关于c++ - C++ 11 unordered_map时间复杂度，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/21281227/