stdext :: hash_map不清楚哈希函數

#include <iostream> 
#include <hash_map> 

using namespace stdext; 
using namespace std; 

class CompareStdString 
{ 
public: 
bool operator()(const string & str1, const string & str2) const 
    { 
     return str1.compare(str2) < 0; 
    } 
}; 
int main() 
{ 
    hash_map<string, int, hash_compare<string, CompareStdString> > Map; 
    Map.insert(make_pair("one", 1)); 
    Map.insert(make_pair("two", 2)); 
    Map.insert(make_pair("three", 3)); 
    Map.insert(make_pair("four", 4)); 
    Map.insert(make_pair("five", 5)); 
    hash_map<string, int, hash_compare<string, CompareStdString> > :: iterator i; 
    for (i = Map.begin(); i != Map.end(); ++i) 
    { 
     i -> first; // they are ordered as three, five, two, four, one 
    } 
    return 0; 
}

我想使用hash_map保持std :: string作爲一個鍵。但是，當我插入下一對訂單是困惑。爲什麼訂單不匹配插入訂單？我應該如何得到一個二三四五的訂單？stdext :: hash_map不清楚哈希函數

來源

2013-07-08 user2560991

這引發了一個問題，爲什麼你不使用'std :: unordered_map' ... – PlasmaHH

我認爲'std :: map '會爲你想要的值排序而不需要額外的工作。 – andre

@andre'std :: map'也不使用插入順序（至少不是默認情況下，並不容易獲得比較器）。 –

爲什麼訂單不匹配插入訂單？

這是因爲，stdext::hash_map（與平臺無關的標準庫版本std::unordered_map從C++ 11）不維護/保證它的元素，甚至沒有插入順序的合理命令。這是因爲它是一個散列容器，其中各個元素的位置基於它們的散列值和容器的大小。因此，您無法使用此類容器爲您的數據維持合理的訂單。

你可以用什麼來保證你的元素保證順序是一個很好的舊std::map。但是這也不是通過插入順序來排序元素，而是通過比較謂詞（它可以被配置爲尊重插入時間，但是這將是非常不直觀的並且不是那麼容易）引發的順序。

對於任何你不會繞過你自己的東西（或搜索其他庫，不知道增強是否有類似的東西）。例如，將所有元素添加到線性std::vector/std::list以進行插入順序迭代，並在必要時爲O（1）/ O（log n）檢索指定一個額外的std::(unordered_)map指向該向量/列表。

來源

2013-07-08 14:27:39

謝謝你的連接！這真的有助於理解這件事。 – user2560991

@ user2560991：歡迎使用StackOverflow。如果它回答你的問題，一定要投票並「接受」答覆。 –

stdext :: hash_map不清楚哈希函數

回答

相關問題