C++ 11 unordered_map时间复杂度

我想弄清楚为资源做缓存的最佳方法。我主要在寻找原生的C/C++/C++ 11解决方案（即我没有提升和类似的选项）。C++ 11 unordered_map时间复杂度

从缓存中检索，当我在做什么是这样的：

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），key的value无法检索，而不是我猜想的。

但是，如果我在键上做了find，它是否会触发一个实际上会以线性时间运行的大型搜索（因为找不到键会看到每个键）？

这是一个好办法做到这一点，或有没有人有一些建议，也许有可能使用起来一看什么的知道，如果关键是可用，我可以访问频繁，如果是这样的话我花了一些时间去搜索，我想消除它，或者至少尽快完成。

感谢您对此的任何意见。

来源

2014-01-22 qrikko

默认构造函数（由_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[]具有相同的性能;平均常数，最坏情况线性（仅当无序映射中的每个键具有相同散列时）。

来源

2014-01-22 11:12:41 ecatmur

感谢您的回答（实际上我收到的所有答案），我特别喜欢简洁的解释。我觉得我更好地理解了我的问题的答案，我也喜欢关于使用'unique_ptr'的说明，这非常合理。 – qrikko

这是我怎么会这样写：

auto it = _object_cache.find(name); 
return it != _object_cache.end() 
     ? it->second 
     : _object_cache.emplace(name, new Object).first->second;

来源

2014-01-22 11:17:30

的find上的std :: unordered_map的复杂度为O（1）（不变），特别是与具有良好的散列领先的std :: string键碰撞率非常低。即使方法的名称是find，但它不会像您指出的那样执行线性扫描。

如果你想做某种缓存，这个容器肯定是一个好的开始。

来源

2014-01-22 11:23:11

“特意”是什么意思？ “这是恒定的，但用弦乐更加稳定”？ –

@KerrekSB你看过整个答案吗？我会为你重复这一点：“特别使用具有很好的散列的std :: string键导致非常低的碰撞率”。我试图说std :: string通过std :: hash <>有一个很好的内置哈希，而当你有自己的对象作为key时，你必须自己实现哈希，这可能不是最优的。 –

请注意，cache通常不仅是一个快速的O(1)访问，但也是一个数据结构。 std::unordered_map会在添加更多元素时动态增加其大小。当资源有限时（例如，将大量文件从磁盘读取到内存中），您需要一个有限且快速的数据结构来提高系统的响应速度。

相反，cache将每当size()达到capacity()，通过更换价值最小的元件使用驱逐策略。

您可以在std::unordered_map之上实施cache。然后可以通过重新定义insert()成员来实施驱逐策略。如果您想要寻找一个N（对于小型和固定的N）关联缓存（即一个项目最多可以替换N其他项），则可以使用bucket()接口来替换其中一个存储条目。

对于全关联缓存（即任何项目可以代替任何其他项目），你可以通过添加std::list作为辅助数据结构使用最近最少使用驱逐策略：

using key_tracker_type = std::list<K>; 
using key_to_value_type = std::unordered_map< 
    K,std::pair<V,typename key_tracker_type::iterator> 
>;

通过包装这两个cache类中的结构，您可以定义insert()以在容量满时触发替换。当发生这种情况时，您最近最近使用的项目为pop_front()，当前项目为push_back()。

在Tim Day's blog there is an extensive example与完整的源代码，实现上述缓存数据结构。它的实现也可以使用Boost.Bimap或Boost.MultiIndex高效地完成。

来源

2014-01-22 12:16:53 TemplateRex

map/unordered_map的插入/ emplace接口足以满足您的需求：查找位置，并在必要时插入。由于这里的映射值是指针，ekatmur的反应非常理想。如果你的价值观是在地图上，而不是指针完全成熟的对象，你可以使用这样的事情：

Object& ResourceManager::object_named(const char *name, const Object& initialValue) { 
    return _object_cache.emplace(name, initialValue).first->second; 
}

值name和initialValue弥补参数的键值对需要被插入，如果没有与name相同的值。 emplace返回一对，second表示是否插入了任何内容（name中的密钥是新密钥） - 我们在这里不关心;并且first是指向（可能是新创建的）键值对条目的迭代器，其键值等于值name。因此，如果密钥已经存在，则取消引用first会为该密钥提供原始的Ojbect，该密钥尚未被initialValue覆盖;否则，使用name的值新插入密钥，并从initialValue和first复制的项值部分指向该密钥。

ekatmur的反应是相同的：

Object& ResourceManager::object_named(const char *name) { 
    bool res; 
    auto iter = _object_cache.end(); 
    std::tie(iter, res) = _object_cache.emplace(name, nullptr); 
    if (res) { 
     iter->second = new Object(); // we inserted a null pointer - now replace it 
    } 
    return iter->second; 
}

，但一个事实，即通过operator[]创建的默认构造的指针值是零，以决定是否要分配一个新的Object需要利润。它更简洁，更易于阅读。

来源

2014-02-04 10:54:31 TonyB

C++ 11 unordered_map时间复杂度

回答

相关问题