如何減少C++ map/unordered_map容器中的查找分配？

假設我在我的代碼中使用了std::unordered_map<std::string, Foo>。這很好，很方便，但不幸的是，每次我想在這張地圖上進行查找（find()）時，我都得出一個std::string的實例。如何減少C++ map/unordered_map容器中的查找分配？

例如，假設我正在標記其他字符串並且想要在每個標記上調用find()。這迫使我在查看每個標記前圍繞std::string構建一個std::string，這需要一個分配器（std::allocator，相當於CRT malloc()）。這很容易比實際的查找本身慢。它也與其他線程競爭，因爲堆管理需要某種形式的同步。

幾年前我找到了Boost.intrusive庫;當時它只是一個測試版。有趣的是它有一個名爲boost::intrusive::iunordered_set的容器，它允許代碼使用任何用戶提供的類型執行查找。

我會解釋它，我想它是如何工作的：

struct immutable_string 
{ 
    const char *pf, *pl; 
    struct equals 
    { 
     bool operator()(const string& left, immutable_string& right) const 
     { 
      if (left.length() != right.pl - right.pf) 
       return false; 

      return std::equals(right.pf, right.pl, left.begin()); 
     } 
    }; 

    struct hasher 
    { 
     size_t operator()(const immutable_string& s) const 
     { 
      return boost::hash_range(s.pf, s.pl); 
     } 
    }; 

}; 

struct string_hasher 
{ 
    size_t operator()(const std::string& s) const 
    { 
     return boost::hash_range(s.begin(), s.end()); 
    } 
}; 

std::unordered_map<std::string, Foo, string_hasher> m; 
m["abc"] = Foo(123); 

immutable_string token; // token refers to a substring inside some other string 

auto it = m.find(token, immutable_string::equals(), immutable_string::hasher());

另一件事是加快「查找和插入，如果沒有找到」用例的伎倆與lower_bound()只有作品對於有序的容器。侵入式容器具有稱爲insert_check()和insert_commit()的方法，但這是針對我猜測的單獨主題。

來源

2013-02-23 yonil

使用更好的庫實現？有可能實現'std :: string'，使得小字符串不會使用任何動態內存分配... – 2013-02-23 13:48:31

如果'std :: string'太昂貴，請將自己的對象包裝在令牌中並避免堆分配。侵入式與非侵入式容器是一個正交的問題。 – 2013-02-23 13:52:29

這是一個過早的悲觀。許多'std :: string'實現通過將字符串直接存儲到自身中來避免分配小字符串。看到[這個答案]（http://stackoverflow.com/a/11639305/597607）的例子，根本沒有任何分配構造和複製一個字符串。 – 2013-02-23 14:21:42

當談到樂星，我個人使用兩個簡單的技巧：

我用StringRef（類似於LLVM的），它只是包裝一個char const*和size_t，並提供串類的操作（只有常量的操作，顯然）
我集中使用了凸點分配器（使用的腫塊遇到弦說4K）

兩個組合是非常有效的，但一個需要了解所有StringRef當池被銷燬時，進入池的點顯然無效。

來源

2013-02-23 14:51:14

從Boost 1.53開始，你可以使用'#include ' – 2013-02-23 15:36:36

@MarshallClow：很高興知道！ – 2013-02-23 15:39:26

非常好，謝謝。我目前的工作無法升級到Boost 1.53。無論如何，我正在使用'unordered_map '。從本質上講，它是唯一不需要修改容器接口的現實選擇。我的'immutable_string'真的和'StringRef'完全一樣。 – yonil 2013-02-23 17:17:33

原來boost::unordered_map（截至1.42）具有find重載需要CompatibleKey，CompatibleHash，CompatiblePredicate類型，所以它可以做什麼我問這裏。

來源

2013-03-11 11:02:00 yonil

如何減少C++ map/unordered_map容器中的查找分配？

回答

相關問題