Страниц: [1]
  Печать  
Автор Тема: Проблема с hash_map  (Прочитано 5116 раз)
SunQNX
Участник
*
Offline Offline

Сообщений: 8


Просмотр профиля
« : Ноября 28, 2013, 03:39:35 pm »

Приветствую всех участников форума!
Помогите решить проблему с использованием hash_map в QNX 6.4.x.
При объявлении
std::hash_map<int, std::string> _container;
_container[0] = "string 1";
_container[1] = "string 2";
проблем с компиляцией и заполнением контейнера не возникает.
Стоит поменять типы данных местами
std::hash_map<std::string, int> _container; (В идеале нужен std::hash_map<std::string, my_class>)
_container["string 1"] = 0;
_container["string 2"] = 1;
код перестает даже собираться.
Насколько мне удалось понять из книги (Страуструп), надо самому определять функцию хэширования (хотя
про string в качестве key, говорится, что такая хэш-функция уже реализована в stl).
А вот как переопределить для hash_map функцию хэширования я пока так и не разобрался.
Может кто-то сталкивался и решил такую задачу?
Записан
lastcross
Full Member
***
Offline Offline

Сообщений: 237


Просмотр профиля
« Ответ #1 : Ноября 28, 2013, 07:14:38 pm »

хотя
про string в качестве key, говорится, что такая хэш-функция уже реализована в stl ...

Нет такого контейнера в стандарте, по крайней мере мне с таким именем он мне неизвестен. Вне стандарта - существуют, а следовательно нет требования к интерфейсу и реализации данного контейнера (то есть у каждой библиотеки она своя). Если нужен стандартный (C++11) и близкий к Вашему ожидаемому hash_map посмотрите на это .

Для начала определитесь - каким стандартом вы пользуетесь или какой именно реализацией hash_map решили воспользоватся.

Как правила подобные hash_map контейнеры содержат шаблонный параметр который можно задать при создании объекта, тип которого и будет содержать хэш-функцию
« Последнее редактирование: Ноября 28, 2013, 07:18:48 pm от lastcross » Записан
SunQNX
Участник
*
Offline Offline

Сообщений: 8


Просмотр профиля
« Ответ #2 : Ноября 28, 2013, 07:43:15 pm »

"std::hash_set и std::hash_map давно были нестандартным расширением STL, по факту реализованным в большинстве компиляторов. В C++11 они стали стандартом, под именами unordered_set и unordered_map." (Википедия)

В QNX6, в include есть только реализация hash_map. unordered_map по мануалам не упоминается. Но судя по всему это одно и тоже.
Записан
lastcross
Full Member
***
Offline Offline

Сообщений: 237


Просмотр профиля
« Ответ #3 : Ноября 30, 2013, 04:28:56 am »

"std::hash_set и std::hash_map давно были нестандартным расширением STL, по факту реализованным в большинстве компиляторов. В C++11 они стали стандартом, под именами unordered_set и unordered_map." (Википедия)

В QNX6, в include есть только реализация hash_map. unordered_map по мануалам не упоминается. Но судя по всему это одно и тоже.

Я знаю что такое hash_map =) . Уточнение требовало какой именно реализацией hash_map вы воспользовались (вдруг Вы stl-port себе прикрутили Smiley - кто ж знает ). А также намек на то, что hash_map никогда не входил в стандарт , а следовательно утверждение
Цитировать
хотя про string в качестве key, говорится, что такая хэш-функция уже реализована в stl

не совсем верно (хотя для unordered_map какие-то реализованы, но это же С++11, да и вы не его юзаете).

По вашему вопросу соответственно идем по этой ссылке

Как вариант, можно определить свой класс по аналогии с hash_compare и вскормить его как параметр при создании объекта
Код:

//...
class CStringHasher
  : public std::hash_compare<std::string>
{
  size_t operator()(const std::string & _Key) const
  {
      size_t hash = 1315423911;

      for(std::size_t i = 0; i < _Key.length(); i++)
      {
          hash ^= ((hash << 5) + _Key[i] + (hash >> 2));
      }

      return (hash & 0x7FFFFFFF);   
  }

};

// Где-то в коде

  typedef std::has_map<std::string, int, CStringHasher> CHashedMyContainer;

Другие варианты хэш-функций для строк можно например посмотреть по этой ссылке . Да и вообще не так и сложно гуглится.

З.Ы.: не проверял и не компилил - так как qnx нет под рукой, так что возможны очепятки =)
« Последнее редактирование: Ноября 30, 2013, 04:41:10 am от lastcross » Записан
SunQNX
Участник
*
Offline Offline

Сообщений: 8


Просмотр профиля
« Ответ #4 : Декабря 03, 2013, 07:11:40 pm »

Попробовал приведенную вами реализацию и ...
Видимо я что-то не догоняю. Компилятор ругается.
Код:
class CStringHasher : public std::hash_compare<std::string> {
 size_t operator()(const std::string & _Key) const {
  size_t hash = 1315423911;
  for( std::size_t i = 0; i < _Key.length(); i++ ) {
   hash ^= ((hash << 5) + _Key[i] + (hash >> 2));
  }
  return (hash & 0x7FFFFFFF);
 }
};

typedef std::has_map <std::string, int, CStringHasher> CHashedMyContainer;

int
main( int argc, char *argv[] ) {
 std::cout << "Welcome to the QNX Momentics IDE" << std::endl;
 return EXIT_SUCCESS;
}
Получаю ошибку: test.cc:17: error: expected initializer before '<' token
Убираю typedef, объявляя напрямую std::has_map <std::string, int, CStringHasher> CHashedMyContainer;
компилятор выдает: test.cc:17: error: expected constructor, destructor, or type conversion before '<' token
Сломал голову, хотя сама идея с наследованием стандартного класса вроде логична.
Хоть в настоящее время и отпала актуальность в hash_map, но на будущее хотелось бы разобраться.
Записан
denmor86
Участник
*
Offline Offline

Сообщений: 35


Просмотр профиля
« Ответ #5 : Декабря 03, 2013, 08:33:37 pm »

где то я читал что не рекомендуется наследоваться от стандартного класса.
Записан
lastcross
Full Member
***
Offline Offline

Сообщений: 237


Просмотр профиля
« Ответ #6 : Декабря 04, 2013, 12:25:28 pm »

где то я читал что не рекомендуется наследоваться от стандартного класса.

Вряд ли - или наследоваться от hash_compare (ограничения реализации hash_map) или писать полностью самому (без наследования). Другое наследование избыточно.

По поводу Вашей ошибки:

Попробуйте добавить public Smiley который я забыл указать
Код:
//....
class CStringHasher : public std::hash_compare<std::string> {

public: <-- иначе не доступны элементы класса извне

 size_t operator()(const std::string & _Key) const {
// ....

А также:
  • Предоставляйте ВЕСЬ код, так как ошибки компиляции с шаблонами иногда бывают весьма забавными, а поиск неоднозначен
  • Убедитесь что определение hash_map и hash_compare которых вы инклудите находятся в тех именных пространствах что и используемые в вашем коде(std??).

Т.е. возможно я не угадал и в вашем случае используется какая-то другая реализация hash_map - очевидно там может отсутствовать hash_compare или иметь совсем другой способ(интерфейс) задания хэш-функций для объектов. Возможно hash_compare не принадлежит пространству std (это вполне может быть - хотя судя из документации которую я видел он вроде как в std)


например, что выдаст такой код?
Код:

#include <string>
#include <hash_map>

// хэшер через наследование
class CStringHasher : public std::hash_compare<std::string> {

public:
 size_t operator()(const std::string & _Key) const {
  size_t hash = 1315423911;
  for( std::size_t i = 0; i < _Key.length(); i++ ) {
   hash ^= ((hash << 5) + _Key[i] + (hash >> 2));
  }
  return (hash & 0x7FFFFFFF);
 }
};

// хэшер без наследования
template<class Key,
    class Pr = std::less<Key> >
    class CSimpleStringHasher {
    Pr comp;
public:
    const size_t bucket_size = 4;
    const size_t min_buckets = 8;
    CSimpleStringHasher (){}

    CSimpleStringHasher (Pr pred)
      : comp(pred)
    {}   

    size_t operator()(const Key& Key) const
    {
        size_t hash = 1315423911;
        for( std::size_t i = 0; i < Key.length(); i++ ) {
           hash ^= ((hash << 5) + Key[i] + (hash >> 2));
        }
        return (hash & 0x7FFFFFFF);
    }

    bool operator()(const Key& keyval1,
        const Key& keyval2) const
    {
        return comp(keyval1, keyval2);
    }
};

typedef std::has_map <std::string, int, CStringHasher> CHashedString;

typedef CSimpleStringHasher<std::string> CMySimpleStringHasher;
typedef std::has_map <std::string, int, CMySimpleStringHasher > CHashedSimpleSting;


int
main( int argc, char *argv[] ) {
 std::cout << "Welcome to the QNX Momentics IDE" << std::endl;
 return EXIT_SUCCESS;
}
Записан
SunQNX
Участник
*
Offline Offline

Сообщений: 8


Просмотр профиля
« Ответ #7 : Декабря 06, 2013, 05:41:23 pm »

Добавление public не изменило ситуацию.
Код был приведен весь. Не включены только include:
Код:
#include <cstdlib>
#include <iostream>
#include <hash_map>
#include <string>
Классы  hash_map и hash_compare находятся в пространстве std. Помимо этого присутствует hash_map в пространстве stlport. (Если судить по коду #include, то именно stlport и является базой в QNX для hash_map и hash_multimap)

Приведенный вами код, после небольших правок для компиляции, приобрел вид:
Код:
#include <cstdlib>
#include <iostream>
#include <string>
#include <hash_map>

// хэшер через наследование
class CStringHasher : public std::hash_compare<std::string> {

public:
 std::size_t operator()(const std::string & _Key) const {
  std::size_t hash = 1315423911;
  for( std::size_t i = 0; i < _Key.length(); i++ ) {
   hash ^= ((hash << 5) + _Key[i] + (hash >> 2));
  }
  return (hash & 0x7FFFFFFF);
 }
};

// хэшер без наследования
template<class Key,
    class Pr = std::less<Key> >
    class CSimpleStringHasher {
    Pr comp;
public:
    const static std::size_t bucket_size = 4;
    const static std::size_t min_buckets = 8;
    CSimpleStringHasher (){}

    CSimpleStringHasher (Pr pred)
      : comp(pred)
    {}

    std::size_t operator()(const Key& _Key) const
    {
    std::size_t hash = 1315423911;
        for( std::size_t i = 0; i < _Key.length(); i++ ) {
           hash ^= ((hash << 5) + _Key[i] + (hash >> 2));
        }
        return (hash & 0x7FFFFFFF);
    }

    bool operator()(const Key& keyval1,
        const Key& keyval2) const
    {
        return comp(keyval1, keyval2);
    }
};

typedef std::has_map <std::string, int, CStringHasher> CHashedString; // line 49

typedef CSimpleStringHasher<std::string> CMySimpleStringHasher;
typedef std::has_map <std::string, int, CMySimpleStringHasher > CHashedSimpleSting; // line 52


int
main( int argc, char *argv[] ) {
 std::cout << "Welcome to the QNX Momentics IDE" << std::endl;
 return EXIT_SUCCESS;
}

Компилятор как и ранее выдает ошибки:
.../test.cc:49: error: expected initializer before '<' token
.../test.cc:52: error: expected initializer before '<' token
А вот на CSimpleStringHasher<std::string> не ругается.
Записан
lastcross
Full Member
***
Offline Offline

Сообщений: 237


Просмотр профиля
« Ответ #8 : Декабря 07, 2013, 06:42:29 am »

Добавление public не изменило ситуацию.
Это ожидалось =) - но без паблика все равно бы не заработало.

Цитировать
Классы  hash_map и hash_compare находятся в пространстве std. Помимо этого присутствует hash_map в пространстве stlport. (Если судить по коду #include, то именно stlport и является базой в QNX для hash_map и hash_multimap)

Ну это говорит скорее о том что доступны оба варианта hash_map в проекте и при том из разных библиотек. По идее разные неймспейсы должны исключать коллизии, но видимо что-то пошло не так =) (при этом странно что пространство имен  у вас stlport для STLPorta - то что я вижу своими глазами, там может быть stlpmtx_std, stlp_std, stlpxmtx_std или stlpx_std в зависимости от сборки или же std. Но возможно у вас не последний STLPort). И это несколько странно (одновременно видеть одним проектом две реализации stl).
Думаю проблема в этом.

У себя проверил на hash_map STLPort-а (правда винда и студия). С CMySimpleStringHasher и CHashedSimpleSting - все компилится и собирается. Разумеется для hash_map из STLPort-а будет непонятен CStringHasher и CHashedString, из-за отсутствие там hash_compare (у STLPort-а другой подход (контракт), тип реализующий хэш-функцию и тип реализующий эквивалентность в случае коллизий - задаются раздельно, в отличии указанной ранее мной ссылке в которой для этих целей нужно передать в качестве аргумента шаблона только один тип реализующий все сразу).

Для начала исключите из проекта одну из реализаций stl
« Последнее редактирование: Декабря 07, 2013, 06:44:23 am от lastcross » Записан
Страниц: [1]
  Печать  
 
Перейти в: