понедельник, июня 04, 2012

Статья Hash Functions for C++ Unordered Containers

И еще одна интересная проблема из переписки. С ней сталкиваются все, кто более-менее серьезно пытается использовать хэш-контейнеры в С++. Итак, вы пытаетесь положить свой класс в, скажем, unordered_map. И получаете сообщение об ошибке примерно такого вида:


cannot convert from 'const Name' to 'size_t'
Это крайне невразумительное сообщение об ошибке означает, что вы должны определить хэш-функцию для своего класса, чтобы можно было его использовать с данным контейнером.
О том как это сделать есть хорошая подробная статья Hash Functions for C++ Unordered Containers.
Пример оттуда с самым простым способом определить хэш-функцию


//
// This program uses a simple user-defined function
// to provide a hash function for use in unordered_map
//
// Compile this example with Visual Studio 2010
// or g++ 4.5 using -std=c++0x
//
#include <iostream>
#include <unordered_map>
#include <string>
#include <functional>

using namespace std;

typedef pair<string,string> Name;

size_t name_hash( const Name & name )
{
    return hash<string>()(name.first) ^ hash<string>()(name.second);
}

int main(int argc, char* argv[])
{
 unordered_map<Name,int,decltype(&name_hash)> ids(100, name_hash );
 ids[Name("Mark", "Nelson")] = 40561;
 ids[Name("Andrew","Binstock")] = 40562;
 for ( auto ii = ids.begin() ; ii != ids.end() ; ii++ )
     cout << ii->first.first
          << " "
          << ii->first.second
          << " : "
          << ii->second
          << endl;
 return 0;
}

8 коммент.:

declonter комментирует...

Алёна, браузер пожрал угловые скобки и прочие спецсимволы. Попробуйте использовать это: http://www.ph4.ru/spravka_codes.ph4

Alena комментирует...

declonter

Алёна, браузер пожрал угловые скобки и прочие спецсимволы.

Угу, спасибо, поправила

sinsi комментирует...

unordered_map

ошибка - должно быть Name.

А сообщение об ошибке совершенно стандартное и понятное. И очень часто проще (и, соответственно, лучше) добавить эту конвертацию прямо в класс, а не загромождать все конструирование его отдельных экземпляров.

soonts комментирует...

Мне больше нравится как это в ATL коллекциях реализовано. См. CAtlMap и CElementTraits. Ты ж вроде в MS трудишься, зачем тебе там STL-коллекции?

Анонимный комментирует...

кажд[ый/ая] использует то что хочет. точка

Alena комментирует...

soonts

Ты ж вроде в MS трудишься, зачем тебе там STL-коллекции?

Я еще и на C# пишу в основном. Это не повод не расширять кругозор :-)

Анонимный комментирует...

Я нашел еще очень интересный сайт где можно научится программировать на Symbian С++. Есть еще много информации сам там учусь и книг много на сайте debugni.ru

Анонимный комментирует...

Громоздкое:
unordered_map ids(100, name_hash );
легко меняется на:
unordered_map ids(100);
если name_hash не свободная функция, а функтор.

–SM