Как использовать stdext :: hash_map, где ключ является пользовательским объектом?

Question

Использование 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> & 'from' const MyKeyObject 'c: \ program files \ microsoft визуальная студия 8 \ vc \ include \ функционал 143

Ошибка 2, ошибка C2784: 'bool std :: operator <(const станд :: basic_string <_Elem, _Traits, _Alloc> &, const _Elem *) ': не смог вывести шаблонный аргумент для 'const станд :: basic_string <_Elem, _Traits, _Alloc> & 'from' const Tasking :: MyKeyObject 'c: \ program файлы \ Microsoft Visual Studio 8 \ vc \ include \ функциональный 143

Ошибка 3, ошибка C2784: 'bool std :: operator <(const _Elem *, const станд :: basic_string <_Elem, _Traits, _Alloc> &) ': не удалось вывести шаблон аргумент для 'const _Elem *' из 'const MyDataObject' c: \ program файлы \ Microsoft Visual Studio 8 \ vc \ include \ function 143

...

Если я установлю ключ к чему-то простому, например, к int, все будет хорошо.

Что я делаю не так ?! Может быть, мне нужно что-то сделать с шаблонами?

Есть ли лучший (более быстрый?) Способ доступа к данным с использованием подобного пользовательского ключевого объекта?

Answer 1

Чтобы использовать хеш-таблицу, вам нужно указать хеш-функцию. Вам необходимо создать объект функции, который представляет функцию, которая принимает объект MyKeyObject и возвращает size_t. Затем вы передаете функтор в качестве второго аргумента после начального размера:

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

Кроме того, вы можете написать свою хеш-функцию как специализацию шаблона функтора hash<T> для вашего типа; таким образом вам не нужно передавать пользовательскую хеш-функцию.

Я не знаю, почему вы получаете именно эти ошибки. Возможно, он пытается использовать ваш объект в качестве хэш-кода или что-то еще? В любом случае это не должно работать без хэш-функции. Хеш-функции предопределены для целочисленных типов и строк.

Answer 2

Попробуйте следующее, сработало для меня в VS 2005. Это решение как для встроенного типа hash_map VS2005 в пространстве имен stdext, так и для повышения 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;
}

Answer 3

<ссылка удалена> четко объясняет, как использовать hash_map и создать собственную хеш-функцию.

(редактировать: ссылка удалена. Теперь указывает на страницу со спамом)

Answer 4

Я наткнулся на этот очень старый вопрос, пытаясь найти тот же ответ, и найти существующие ответы не очень полезными. В настоящее время мы используем unordered_map, если нам нужна хеш-карта, и лучший способ сделать ваш класс MyKeyObject пригодным для использования в качестве ключа в hash_map в целом - это определить хеш-функцию для класса и указать стандартной библиотеке использовать эта хеш-функция для карт. Это означает, что мы можем создать экземпляр шаблона карты, не всегда предоставляя хеш-функцию.

Страница википедии *1006* на «Неупорядоченные ассоциативные контейнеры в 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)

Answer 5

Я использую его для отображения структуры данных вершин.

#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 *, а затем создаю строку со вторым параметром, который имеет размер, размер важен, поскольку данные памяти могут содержать нулевые символы. Мне не нужно никаких дополнительных сравнений, хэширующих функций ...