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不清楚哈希函数

回答

相关问题