Найти ключ в Stl Hash_map - PullRequest
Новая
       25

Найти ключ в Stl Hash_map

0 голосов
/ 10 декабря 2010

Я новичок в c ++ и имею некоторые проблемы с хэш-таблицей. Мне нужна структура хэш-таблицы для моей программы. сначала я использую boost unordered_map. в нем есть все, что мне нужно, но это делает мою программу такой медленной. тогда я хочу проверить stl hash_map, но я не могу сделать все, что мне нужно. это мой первый код (это пример) 

#include <hash_map>
using namespace std;

struct eqstr
{
  bool operator()(int s1, int s2) const
  {
    return s1==s2;
  }
};
typedef stdext::hash_map< int, int, stdext::hash_compare< int, eqstr > > HashTable;

int main()
{
  HashTable a;
  a.insert( std::pair<int,int>( 1, 1 ) );
  a.insert( std::pair<int,int>( 2, 2 ) );
  a.insert( std::pair<int,int>( 4, 4 ) );
//next i want to change value of key 2 to 20
  a[2] =  20;
//this code only insert pair<2,20> into a, buy when I use boost unordered_map this code                         modify previous key of 2  
//next I try this code for delete 2 and insert new one
  a.erase(2);//this code does work nothing !!!
//next I try to find 2 and delete it
  HashTable::iterator i;
  i = a.find(2);//this code return end, and does not work!!!
  a.erase(i);//cause error
//but when I write this code, it works!!!
  i=a.begin();
  a.erase(i);
//and finally i write this code
  for (i = a.begin(); i!=a.end(); ++i)
  {
    if (i->first == 2 )
      break;
  }
  if (i!= a.end())
    a.erase(i);
//and this code work

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

Ответы [ 2 ]

1 голос
/ 10 декабря 2010

Вы можете посмотреть на: http://msdn.microsoft.com/en-us/library/525kffzd(VS.71).aspx

Я думаю, что stdext::hash_compare< int, eqstr > вызывает проблемы здесь. Попробуйте стереть это.

Другая реализация хэш-карты - std::tr1::unordered_map. Но я думаю, что производительность реализации различных хэш-карт будет одинаковой. Не могли бы вы подробнее рассказать о том, насколько медленным был boost :: unordered_map? Как ты это использовал? Для чего?

0 голосов
/ 10 декабря 2010

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

Первое, что вам нужно рассмотреть, это то, что вам действительно нужно сделать, и сколько производительности вам действительно нужно, а затем определить, может ли что-то готовое выполнить это или вам нужно написать что-то свое.

Если вы, например, никогда не удаляете элементы, а просто пишете один раз, а затем постоянно ищите, то вы можете часто перефразировать, чтобы уменьшить коллизии для фактического набора, который вы получаете: дольше во время установки, но быстрее при поиске.

Проблема в написании вашего собственного файла возникнет, если вы удалите элементы, потому что недостаточно «обнулить» запись, так как другой, возможно, перешагнул через вашу, как часть курса на столкновение, и теперь, если вы посмотрите этот элемент вверх сдастся как "не найден", как только он достигнет вашего нуля.

...