的hash_map，在地圖的哈希函數的複合鍵

我有一個工作的std ::地圖類，這是有點慢，所以我想嘗試的其它數據的hash_map，在地圖的哈希函數的複合鍵

我的關鍵是像

typedef struct { 
    char * name; 
    int offset; 
}position;

的複合數據類型

而爲的std ::地圖我用下面的部分排序功能

struct cmp_position { 
    bool operator()(const position& first,const position& second) { 
    int tmp = std::strcmp(first.name, second.name); 
    if(tmp!=0) 
     return tmp<0; 
    else 
     return first.offset<second.offset; 
    } 
};

我的地圖定義是

typedef std::map<position,int,cmp_position> myMap;

我一直在尋找的__gcc_ext ::的hash_map這是需要可能僅僅是

struct positionEq 
{ 
    bool operator()(const position& s1, const position & s2) const 
    { 
    return strcmp(s1.name, s2.name) == 0 && (s1.offset==s2.offset) ; 
    } 
};

這應該工作的平等的功能，但我對自己的複合類型的哈希函數有麻煩。我想我可以做類似

position s; 
char buf[100]; 
snprintf(buf,100,"%s:%d\n",s.name,s.offset);

，但我有膠合一起的問題。

其實地圖和哈希映射可能有點矯枉過正，因爲我沒有使用鍵的值，我只是使用我的地圖來檢查存在。

這是我的意圖不使用std :: strings。

感謝

編輯：

在上面的例子中，我試圖用一個std ::集而不是的std ::地圖，和std ::一套既填充一貫慢，查找條目。儘管整體比較如下表所示，但它使用的內存少得多。我試圖運行每組10次

  Set  map 
size 1.8gig  3.1gig 
pop <15sec  <14sec 
find <12sec  <9sec

我使用的數據集與多於34mio條目，和填充數據結構後，我試圖查找所有34個MIO元素。我猜測的結論是，除了保存內存之外，std :: set更差。

來源

2011-06-17 monkeyking

請定義「有點慢」。什麼是慢？插入？尋找？穿越？ – sbi

學習unordered_map比hash_map更好。兩者都是散列表，但unordered_map是（或很快將是）標準。 – Steve314

如果你不需要值，可以使用'set/hash_set/unordered_set' –

您是否嘗試過使用存儲散列值爲name（例如使用boost::hash_value）的密鑰結構 - 以便比較關鍵對象將只是兩個數字比較，這應該相當快。

嘗試使用unordered_set進行測試。 boost::multi_index_container聲稱要優於std::set，並且在某些情況下，您可以看到這是否會加快速度（請參閱我的回答here以瞭解其使用示例）。

來源

2011-06-18 00:43:02 Node

的hash_map，在地圖的哈希函數的複合鍵

回答

相關問題