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時間複雜度

回答

相關問題