C ++, память и массивы.Создание собственной хэш-карты для упражнений.Неожиданные данные остались в памяти? - PullRequest
Новая
       32

C ++, память и массивы.Создание собственной хэш-карты для упражнений.Неожиданные данные остались в памяти?

0 голосов
/ 25 декабря 2011

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

template<class T>
class HashMap
{
public:
  HashMap();
  virtual ~HashMap();
  void add(T value);
  T get(T *value);
private:
  int hash(T *data);
  T _hashes[26]; //I want a fixed size here
};

template<class T>
HashMap<T>::HashMap()
{
  for(int i = 0; i < 26; i++)
    this->_hashes[i] = T();
}

template<class T>
HashMap<T>::~HashMap()
{
  //Don't really have anything to delete here?
}

template<class T>
int HashMap<T>::hash(T *dat)
{
  //Super simple, just to try things out
  return (long int) dat % 26;
}

template<class T>
T HashMap<T>::get(T *val)
{
  int idx = this->hash(val);
  cout << idx << endl;
  //Probably somewhere here i get my problem
  if(this->_hashes[idx])
    return this->_hashes[idx];
  return T();
}

template<class T>
void HashMap<T>::add(T val)
{
  //Should probably do some check if there's already an element here.
  this->_hashes[this->hash(&val)] = val;
}

Проблема, с которой я сталкиваюсь, заключается в том, что это нормально компилируется, но когда я делаю что-то подобное в моем файле main.cpp: 

HashMap<char> a = HashMap<char>();
a.add('h');
a.add('c');
a.add('g');
char *b = new char {'c'};
cout << a.get(b) << endl;
delete b;

Обычно он возвращаетid, то есть: 

4

и пустая строка, которая является просто пустым символом.(выходные данные функции находятся в методе get ()), но иногда мне будет показано что-то вроде этого: 

18
g

вместо 18 и пустой строки.У меня вопрос, почему это происходит и как я могу это предотвратить?Это как-то связано с тем, что память не «обнуляется», когда она удаляется, а просто свободна для других программ, и тогда я неправильно инициализирую ее?Кроме того, если у вас есть время, пожалуйста, укажите на какие-либо ошибки или не очень хорошо делать что-то в коде.

Если будет интересно, я использую GCC Debian 4.4.5-8 для компиляции и компиляции с помощью g ++-g file.cpp -o file

Спасибо за любую помощь!

Ответы [ 2 ]

3 голосов
/ 25 декабря 2011

Поведение, которое вы видите, нормальное: если вы get значение, которое вы указали в своем хеше, оно будет отображаться вашим main. Что дает вам удивительные результаты, так это ваша хеш-функция: 

return (long int) dat % 26;

Это хэширует указатель dat , а не T, на который указывает dat. Попробуйте с: 

return *dat % 26;

(или просто используйте стандартный std::set.)

Еще одна проблема с вашим кодом: 

T _hashes[26]; //I want a fixed size here   (a

и 

this->_hashes = new T[26];                   (b

несовместимы. Либо используйте фиксированный массив (a), и вам не нужно его выделять (b), либо используйте простой указатель (T *_hashes) и выполняйте (b) - я удивлен, что ваш компилятор принимает то, что у вас есть. Если вы используете (а), вам ничего не нужно в деструкторе. Если вы используете (b), вам нужно delete [] в вашем деструкторе.

Передача T* в наборе, но T в наборе тоже немного странно.

1 голос
/ 25 декабря 2011

Вот более идиоматическая реализация c ++: 

#include <array>
#include <iostream>
#define MAGIC_NUMBER 26 //rename this to something else preferably

template<class T>
class HashMap
{
    public:
        HashMap();
        virtual ~HashMap(){};
        void add(T value);
        T get(T *value);//potentially confusing that add and get take different types
    private:
        int hash(T *data);
        std::array<T, MAGIC_NUMBER>  _hashes; //I want a fixed size here
};

template<class T>
HashMap<T>::HashMap()
{
    std::fill(_hashes.begin(),_hashes.end(), T());
}

template<class T>
int HashMap<T>::hash(T *dat)
{
    //Super simple, just to try things out
    return (static_cast<int>(*dat)) % MAGIC_NUMBER;//prefer using c++ casts
}

template<class T>
T HashMap<T>::get(T *val) //this is strange, you pass in a pointer and get a non-pointer
{
  int idx = this->hash(val);
  std::cout << idx << std::endl;
  if(this->_hashes[idx])
    return this->_hashes[idx];
  return T();
}

template<class T>
void HashMap<T>::add(T val)
{
  //Should probably do some check if there's already an element here.
  this->_hashes[this->hash(&val)] = val;
}

int main(void){
    HashMap<char> a = HashMap<char>();
    a.add('h');
    a.add('c');
    a.add('g');
    char *b = new char {'c'};
    std::cout << a.get(b) << std::endl;
    delete b;
}

Обратите внимание, что вам нужно будет скомпилировать функции c ++ 0x или c ++ 11, чтобы получить использование класса std :: array.Одним из основных преимуществ этого класса массивов является то, что вы получаете больше безопасности при распределении памяти, чем простой массив в стиле c.

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

Также как примечание по стандартам кодирования, если вы используете префиксные переменные-члены, это немного тавтологично, чтобы также использоватьthis-> чтобы получить к ним доступ.

...