标签: unordered-map

最近unordered_map在C++中的讨论使我意识到,我应该使用之前使用unordered_map过的大多数情况map,因为查找的效率(摊销的O(1)与O(log n)).大多数时候我使用的地图我使用int或std::string作为键,因此我对哈希函数的定义没有任何问题.我越是想到它,我就越发现我发现std::map在一个简单类型的情况下我找不到任何理由std::unordered_map- 我看了一下界面,并没有发现任何显着的差异会影响我的代码.

因此,这个问题-有没有使用任何真正的原因std::map在std::unordered map简单类型一样的情况下,int和std::string？

我从一个严格的编程角度问我 - 我知道它没有被完全认为是标准的,并且它可能会带来移植问题.

另外我希望正确的答案之一可能是"它对于较小的数据集更有效",因为开销较小(是真的吗？) - 因此我想将问题限制在密钥数量的情况下是非平凡的(> 1 024).

编辑: 呃,我忘记了显而易见的(感谢GMan!) - 是的,地图是当然有序的 - 我知道,我正在寻找其他原因.

我正在尝试使用自定义类作为关键字unordered_map,如下所示:

#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

class node;
class Solution;

class Node {
public:
    int a;
    int b; 
    int c;
    Node(){}
    Node(vector<int> v) {
        sort(v.begin(), v.end());
        a = v[0];       
        b = v[1];       
        c = v[2];       
    }

    bool operator==(Node i) {
        if ( i.a==this->a && i.b==this->b &&i.c==this->c ) {
            return true;
        } else {
            return false;
        }
    }
};

int main() {
    unordered_map<Node, int> m;    

    vector<int> v;
    v.push_back(3);
    v.push_back(8);
    v.push_back(9);
    Node n(v);

    m[n] = 0; …

现在std有一个真正的哈希映射unordered_map,为什么(或何时)我还想在它实际存在的系统上使用旧的mapover unordered_map？是否有任何我无法立即看到的明显情况？

为了支持用户定义的键类型std::unordered_set<Key>和std::unordered_map<Key, Value> 一个具有提供operator==(Key, Key)和散列函子:

struct X { int id; /* ... */ };
bool operator==(X a, X b) { return a.id == b.id; }

struct MyHash {
  size_t operator()(const X& x) const { return std::hash<int>()(x.id); }
};

std::unordered_set<X, MyHash> s;

std::unordered_set<X> 使用类型的默认哈希来编写会更方便X,就像编译器和库中的类型一样.咨询后

• C++标准草案N3242§20.8.12 [unord.hash]和§17.6.3.4[hash.requirements],
• Boost.Unordered
• 克++ include\c++\4.7.0\bits\functional_hash.h
• VC10 include\xfunctional
• Stack Overflow中的各种相关问题

似乎可以专门化std::hash<X>::operator():

namespace std { // argh!
  template <>
  inline size_t 
  hash<X>::operator()(const X& x) const { return …

假设我想用字符串作为键来映射数据.我应该选择哪个容器,map或者unordered_map？unordered_map占用更多内存所以让我们假设内存不是问题,关注的是速度.

unordered_map通常应该给出O(1)的平均复杂度与O(n)的最坏情况.在什么情况下它会到达O(n)？什么时候map获得更多的时间效率unordered_map？当n很小时会发生吗？

假设我将STL unordered_map与默认的haser Vs一起使用.地图.字符串是关键.

如果我要迭代元素而不是每次访问单个元素,我应该更喜欢map吗？

vector从a获取键和值的列表(作为a )的最有效方法是unordered_map什么？

具体来说,假设有问题的地图是一个unordered_map<string, double>.然后我想把键作为a vector<string>,并将值作为a vector<double>.

unordered_map<string, double> um;

vector<string> vs = um.enum_keys();
vector<double> vd = um.enum_values(); 

我可以遍历地图并收集结果,但是有更有效的方法吗？有一个方法也适用于常规地图会很好,因为我可能会切换到那个.

C++ STL unordered_map如何解决冲突？

查看http://www.cplusplus.com/reference/unordered_map/unordered_map/,它显示"唯一键容器中没有两个元素可以具有等效键."

这应该意味着容器确实解决了碰撞.但是,该页面并没有告诉我它是如何做到的.我知道一些解决冲突的方法,比如使用链表和/或探测.我想知道的是c ++ STL unordered_map如何解析它.

我在用

unordered_map<string, int>

和

unordered_map<int, int>

在每种情况下使用什么散列函数以及在每种情况下碰撞的可能性是多少？我将分别在每种情况下插入唯一字符串和唯一int作为键.

我很想知道在字符串和int键及其碰撞统计数据的情况下哈希函数的算法.

c ++ unordered_map碰撞处理,调整大小和重新散列

这是我之前提出的一个问题,我看到我对unordered_map的实现方式感到很困惑.我相信很多其他人都会和我分享这种困惑.基于我所知道的信息而不阅读标准:

每个unordered_map实现都将链表存储到存储桶数组中的外部节点...不,这对于实现最常见用途的哈希映射来说并不是最有效的方法.不幸的是,unordered_map规范中的一个小"疏忽"都需要这种行为.所需的行为是元素的迭代器在插入或删除其他元素时必须保持有效

我希望有人可以解释实现以及它如何与c ++标准定义(在性能要求方面)相对应,以及它是否真的不是实现哈希映射数据结构的最有效方法如何改进它？

我最近发现将调用C++中哈希映射的实现unordered_map.

当我抬起头,为什么他们不只是使用hash_map,我发现,显然有与实施的兼容性问题hash_map是unordered_map可以解决(更多关于它在这里).

该wiki页面没有提供更多信息,所以我想知道是否有人知道hash_map该unordered_map解决方案的一些问题.