6

使用 STL C++ hash_map...

class MyKeyObject
{
    std::string str1;
    std::string str2;

    bool operator==(...) { this.str1 == that.str1 ... }
};

class MyData
{
    std::string data1;
    int data2;
    std::string etcetc;
};

像这样...

MyKeyObject a = MyKeyObject(...);
MyData b = MyData(...);

stdext::hash_map <MyKeyObject, MyData> _myDataHashMap;
_myDataHashMap[ a ] = b;

我收到一大堆错误。这是前三个...

错误 1 ​​错误 C2784: 'bool std::operator <(const std::_Tree<_Traits> &,const std::_Tree<_Traits> &)' : 无法推断出 'const std::_Tree<_Traits> 的模板参数&' 来自 'const MyKeyObject' c:\program files\microsoft visual studio 8\vc\include\functional 143

错误 2 错误 C2784: 'bool std::operator <(const std::basic_string<_Elem,_Traits,_Alloc> &,const _Elem *)' : 无法推断 'const std::basic_string<_Elem,_Traits, _Alloc> &' 来自 'const Tasking::MyKeyObject' c:\program files\microsoft visual studio 8\vc\include\functional 143

错误 3 错误 C2784: 'bool std::operator <(const _Elem *,const std::basic_string<_Elem,_Traits,_Alloc> &)' : 无法从 'const MyDataObject' c 推导出 'const _Elem *' 的模板参数:\程序文件\微软视觉工作室 8\vc\include\functional 143

...

如果我将键设置为像 int 这样简单的东西，一切都很好。

我究竟做错了什么？！也许我需要用模板做点什么？

有没有更好（更快？）的方式来使用这样的自定义键对象访问数据？

4

4 回答 4

3

要使用哈希表，您需要指定一个哈希函数。您需要创建一个函数对象，该对象表示一个函数，该函数接受一个MyKeyObject对象并返回一个size_t. 然后将仿函数作为初始大小之后的第二个参数传递：

hash_map <MyKeyObject, MyData> _myDataHashMap(initial_size, YourHashFunctor());

或者，您可以将散列函数编写hash<T>为您的类型的函子的模板特化；这样您就不需要传入自定义哈希函数。

我不知道您为什么会特别收到这些错误。也许它正在尝试将您的对象用作哈希码或其他东西？无论如何，如果没有散列函数，它就不应该工作。哈希函数是为整数类型和字符串预定义的。

于 2009-06-30T08:21:53.917 回答
2

尝试以下，在 VS 2005 中为我工作。这是一个解决方案，适用于 stdext 命名空间中的 VS2005 内置 hash_map 类型以及 boost unordered_map（首选）。删除你不使用的。

#include <boost/unordered_map.hpp>
#include <hash_map>

class HashKey
{
public:
    HashKey(const std::string& key)
    {
        _key=key;
    }
    HashKey(const char* key)
    {
        _key=key;
    }

    // for boost and stdext
    size_t hash() const
    {
        // your own hash function here
        size_t h = 0;
        std::string::const_iterator p, p_end;
        for(p = _key.begin(), p_end = _key.end(); p != p_end; ++p)
        {
            h = 31 * h + (*p);
        }
        return h;
    }
    // for boost
    bool operator==(const HashKey& other) const
    {
        return _key == other._key;
    }

    std::string _key;
};

// for boost
namespace boost
{
    template<>
    class hash<HashKey>
    {
    public :
        std::size_t operator()(const HashKey &mc) const
        {
            return mc.hash();
        }
    };
}

// for stdext
namespace stdext
{
    template<>
    class hash_compare<HashKey>
    {
    public :
        static const size_t bucket_size = 4;
        static const size_t min_buckets = 8;

        size_t operator()(const HashKey &mc) const
        {
            return mc.hash();
        }

        bool operator()(const HashKey &mc1, const HashKey &mc2) const
        {
            return (mc1._key < mc2._key);
        }
    };
}

int _tmain(int argc, _TCHAR* argv[])
{
    {
        stdext::hash_map<HashKey, int> test;
        test["one"] = 1;
        test["two"] = 2;
    }

    {
        boost::unordered_map<HashKey, int> test(8); // optional default initial bucket count 8
        test["one"] = 1;
        test["two"] = 2;
    }

    return 0;
}
于 2010-03-09T22:10:54.357 回答
0

我用它来映射顶点数据的结构。

#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <boost/unordered_map.hpp>



struct VERTEX
{
float x,y,z;
};

typedef boost::unordered_map<std::string, unsigned int> map;

int main()
{
VERTEX v1,v2,v3;

v1.x = 5.0; v1.y = 2.0; v1.z = 2.33333336;
v2.x = 5.0; v2.y = 2.0; v2.z = 2.32333336;
v3.x = 5.0; v3.y = 2.0; v3.z = 2.33333336;

unsigned int vertexSize = sizeof( VERTEX );
char * v1c = new char[vertexSize];
char * v2c = new char[vertexSize];
char * v3c = new char[vertexSize];

memcpy( v1c, &v1, vertexSize );memcpy( v2c, &v2, vertexSize );memcpy( v3c, &v3, vertexSize );
map mymap;

std::string aaa( v1c, vertexSize );
std::string bbb( v2c, vertexSize );
std::string ccc( v3c, vertexSize );

mymap[ aaa ] = 1;
mymap[ bbb ] = 2;

unsigned int a = mymap[ aaa ];
unsigned int b = mymap[ bbb ];
unsigned int c = mymap[ ccc ];


return 0;
}

这只是一个小例子，我如何使用自定义类型。我只是将 struct 的部分内存复制到 char* 中，然后使用第二个参数创建字符串，即大小，大小很重要，因为内存数据可以包含空字符。我不需要任何额外的比较，散列函数......

于 2013-01-18T16:02:59.643 回答
0

我在尝试找到相同的答案时遇到了这个非常古老的问题，并且发现现有的答案并没有真正的帮助。现在，unordered_map如果我们想要一个哈希映射，我们就使用它，而使您的MyKeyObject类可用作 hash_map 中的键的最佳方法通常是为该类定义一个哈希函数，并告诉标准库将此哈希函数用于映射。这意味着我们可以在不总是提供散列函数的情况下实例化地图模板。

关于“C++ 中的无序关联容器”的维基百科页面提供了一个易于理解的示例，我将其简化了一点并将其应用于您的案例。首先，我们将定义一个简单的散列函数作为成员方法：

#include <functional>
class MyKeyObject {
private:
    std::string str1;
    std::string str2;

public:
    inline size_t hash() const {
        return std::hash<std::string>()(str1) ^ std::hash<std::string>()(str2);
    }

    inline bool operator==(const MyKeyObject& other) const {
        return str1 == other.str1 && str2 == other.str2;
    }
};

为了制作散列函数，我们将所有包含对象的散列异或在一起。这是使用std::hash必须用子类型实例化的模板来完成的。请注意，我们不能将其用作 unordered_map 的第三个模板参数。还要注意 const-equals 运算符。

现在我们必须告诉标准库这是用于MyKeyObject值的哈希函数：

namespace std {
    template <>
    class hash<MyKeyObject> {
    public:
        size_t operator()(const MyKeyObject &aMyKeyObject) const {
            return aMyKeyObject.hash();
        }
    };
}

这将模板特化添加到std::hash模板类，为该类提供哈希运算符MyKeyObject。该示例没有维基百科页面直接在这里定义散列，而不是调用作为对象成员的散列函数 - 但如果散列函数必须访问私有成员，那将不起作用。

现在您应该可以像这样MyKeyObject使用unordered_map：

  std::unordered_map<MyKeyObject, MyData> _myDataHashMap;

（用 clang/xcode 测试）

于 2014-07-02T22:48:36.733 回答