标签: unordered-map

我想使用的元组组成的int,char,char在我的unordered_map.我这样做:

#include <string>
#include <unordered_map>
#include <cstring>
#include <iostream>
#include <tuple>

using namespace std;

tuple <int,char,char> kk;
unordered_map<kk,int> map;

int main()
{
    map[1,"c","b"]=23;
    return 0;
}

但这给了我以下错误:

map.cpp:9:21: error: type/value mismatch at argument 1 in template parameter list     for ‘template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> class    std::unordered_map’
map.cpp:9:21: error:   expected a type, got ‘kk’
map.cpp:9:21: error: template argument 3 is invalid
map.cpp:9:21: error: template argument 4 is invalid …

我对'unordered_map'这个名字感到很困惑.该名称表明钥匙根本没有订购.但我一直认为它们是按哈希值排序的.或者是错误的(因为这个名字意味着他们没有订购)？

或者说不同:是吗？

typedef map<K, V, HashComp<K> > HashMap;

同

template<typename T>
struct HashComp {
    bool operator<(const T& v1, const T& v2) const {
        return hash<T>()(v1) < hash<T>()(v2);
    }
};

同样的

typedef unordered_map<K, V> HashMap;

？(好吧,不完全是,STL会在这里抱怨,因为可能有键k1,k2,k1 <k2和k2 <k1都没有.你需要使用multimap并覆盖等号检查.)

或者不同的是:当我遍历它们时,我可以假设密钥列表按其哈希值排序吗？

背景:我是从Java世界来的,我是C++或Qt的新手.

为了使用unordered_map,我编写了以下简单程序:

#include <QtCore/QCoreApplication>
#include <QtCore>
#include <iostream>
#include <stdio.h>
#include <string>
#include <unordered_map>

using std::string;
using std::cout;
using std::endl;
typedef std::vector<float> floatVector;

int main(int argc, char *argv[]) {
    QCoreApplication a(argc, argv);

    floatVector c(10);
    floatVector b(10);

    for (int i = 0; i < 10; i++) {
        c[i] = i + 1;
        b[i] = i * 2;
    }

    std::unordered_map<floatVector, int> map;

    map[b] = 135;
    map[c] = 40;
    map[c] = 32;

    std::cout << "b -> " << map[b] << std::endl;
    std::cout << …

我有一个C类,它有一个string* ps私有数据成员.
现在,我想要一个unordered_map<C, int>我需要自定义哈希函数的东西.

根据c ++参考,我可以这样做

namespace std {
  template<>
  class hash<C> {
  public:
    size_t operator()(const C &c) const
    {
      return std::hash<std::string>()(*c.ps);
    }
  };
}

问题是,我似乎无法operator()与C朋友交往,以便我可以访问ps.

我试过这个:

class C;
template<>
class std::hash<C>;
class C{
  //...
  friend std::hash<C>::operator ()(const C&) const; // error: Incomplete type 
};
// define hash<C> here.

但它说嵌套名称说明符中的不完整类型...

我也无法扭转这些定义,因为如果后来定义了C类,hash<C>则无法知道ps.

我在这做错了什么？如何在不ps公开的情况下解决这种情况？

我需要创建一个查找函数,其中(X,Y)对对应于特定的Z值.对此的一个主要要求是我需要尽可能接近O(1)复杂度.我的计划是使用unordered_map.

我通常不使用哈希表进行查找,因为查找时间对我来说从未如此重要.我是否认为只要我构建了没有冲突的unordered_map,我的查找时间就是O(1)？

我关心的是,如果无序地图中没有关键字,那么复杂性就会变得很复杂.例如,如果我使用unordered_map :: find():来确定我的哈希表中是否存在键,那么它将如何给我一个答案呢？它是否实际迭代所有键？

我非常感谢你的帮助.

据我所知,我正在做所有事情,我收到了错误消息:

error: 'unordered_map' does not name a type
error: 'mymap' does not name a type

在我的代码中,我有:

#include <unordered_map>

using namespace std;

//global variable
unordered_map<string,int> mymap;
mymap.reserve(7000);

void main {
  return;
}

我不知道这里可以找到什么....

编辑:当我更新我的声明时

std::tr1::unordered_map<string,int> mymap;

我能够消除第一个错误,但是当我尝试保留时,我仍然得到第二个错误消息.

EDIT2:正如下面所指出的,保留必须进入main,我需要用flag编译

-std=c++0x

但是,仍然存在与unordered_map相关的错误,即:

error: 'class std::tr1::unordered_map<std::basic_string<char>, int>' has no member named 'reserve'

环顾cppreference,我发现从"等效键" std::unordered_map 获得高效的查找功能.

我认为这意味着等效键必须具有相同的哈希值.我如何为字符串文字提供相同的哈希值,而std::hash<std::string>不是临时构造一个std::string,从而使得关于等价键的全部观点为无效？

使用std::map或时std::unordered_map,访问可能不在容器中的元素的首选方法是什么？如果有人请求许可或要求宽恕吗？为什么？

那是,

if (mymap.find(key) != mymap.end()) {
    value = mymap.at(key);
    // do stuff
}
else {
    // do something else
}

与

try {
    value = mymap.at(key);
    // do stuff
}
catch(const std::out_of_range& oor) {
    // do something else
}

我知道这个问题，但我的有点不同。

为什么rehash具有二次复杂度，但operator [](可以调用rehash) 在最坏情况下具有线性复杂度？

抱歉，但我没有 10 分来添加图像，所以如果当你看到这个问题时一切都已经解决了，这是我在 cppreference 中看到的：

rehash复杂：

平均情况下与容器的大小呈线性关系，最坏情况下呈二次方关系。

operator[]复杂：

平均情况：恒定，最坏情况：大小呈线性。

我知道为什么 rehash 的复杂度会是二次方。然而，使其成为线性并不困难。因此，任一陈述都可以为真，但不能同时为真（仅当意味着不同的大小时，但我不明白什么可以被视为大小，除了元素的数量）。

我想在VS2010 C++下的索引double处存储~3,000,000个值unsigned int.我用它std::tr1:unordered_map<unsigned int, double>来达到这个目的.不幸的是,当我尝试存储值2 ^ 21时,会抛出异常(就好像只有2 ^ 21-1的空间,即某些索引只能使用20位).我rehash在存储值之前尝试过,这也没有用.

最后,我最终得到了一些非常基本的测试程序(它表现出甚至有点不同的行为,但无论如何):

    std::tr1::unordered_map<unsigned int, float> mapOut;
    //mapOut.rehash(SOMESIZE);
    for (unsigned int i=0; i<3000000; i++)
    {
        if (i%1000==0) std::cout << i << std::endl;
        mapOut[i] = 0.0;
    }

我查了一些案例:

1)如果我根本不重新进行,则程序在输出后根据i == 32000(最终2 ^ 15)进行长时间休息,然后继续i == 262000(2 ^ 18).它永远存在(100%CPU负载,内存不增加).

2)如果我做了rehash(1000),它来到i == 65000(2 ^ 16)并永远保持(CPU负载100%,内存不增加).

3)如果我这样做rehash(3000000),循环成功完成,但程序永远不会退出 - 即,显然析构函数存在一些问题.

那里发生了什么,更重要的是:我该怎么办呢？!

非常感谢您的帮助!