0

我必须研究哈希图的实现。我研究过它会根据模板中提到的顺序对元素进行排序。示例代码是:

#include <hash_map>
#include <iostream>
using namespace std;

int main()
{
    typedef pair <int, int> Int_Pair;

    hash_map <int, int>::iterator hmp1_Iter;

    hash_map <int, int , hash_compare <int, less<int> > > hmp1;                 
    hmp1.insert(Int_Pair(1, 13));
    hmp1.insert(Int_Pair(3, 51));
    hmp1.insert(Int_Pair(7, 22));
    hmp1.insert(Int_Pair(2, 31));

    cout<<"\nOperation1: hash_map<int, int, \nhash_compare<int, less<int> > > hmp1\n";
    cout<<"Operation2: hmp1.insert(Int_Pair(1, 13))...\n";
    cout<<"hmp1 data: ";
    for(hmp1_Iter = hmp1.begin(); hmp1_Iter != hmp1.end(); hmp1_Iter++)
    cout<<hmp1_Iter->first<<":"<<hmp1_Iter->second<<" ";
    cout<<endl;

    return 0;

}

代码的预期结果是: 1:13 2:31 3:51 7:22 但它给出的是 1:31 3:51 7:22 2:31 。但是应该按升序排列关键元素。请解释为什么会这样?

4

2 回答 2

2

std::hash_map是一个无序的关联容器,通常用哈希表实现(键的哈希值作为链表数组中的索引)

如果您需要“有序哈希映射”,您可以使用std::map. 它通常是一棵红黑树,其关键元素可以按升序迭代。

std::hash_map插入和删除应该比std::map.

于 2013-04-08T12:23:00.380 回答
1

来自 MSDN 网站上的hash_map 类

受控序列中元素的实际顺序取决于散列函数、排序函数以及存储在容器对象中的散列表的当前大小。您无法确定哈希表的当前大小,因此通常无法预测受控序列中元素的顺序。

简单地说,hash_map 中元素的顺序永远不能保证是有序的,任何它们看起来是有序的情况都只是巧合。

为了更清楚地说明这一点,MSDN 网站指出

此 API 已过时。替代方案是 unordered_map 类。

提供更多证据表明 hash_map 从不打算为其元素提供任何顺序。

于 2013-04-08T12:49:43.957 回答