0

だから私は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と空の行の代わりに。私の質問は、なぜこれが起こるのか、そしてどうすればそれを防ぐことができるのかということです。削除されたときにメモリが「null」にならず、他のプログラムが自由に使用できるようになっていて、正しく初期化されないことと関係がありますか？また、時間があれば、コード内で間違いを指摘したり、うまくいかなかったりすることを指摘してください。

GCC Debian 4.4.5-8を使用してコンパイルし、g ++ -gfile.cpp-oファイルでコンパイルすることに関心がある場合

助けてくれてありがとう！

4

2 に答える 2

3

表示される動作は正常ですget。ハッシュに値を入力すると、によって表示されますmain。驚くべき結果をもたらしているのは、ハッシュ関数です。

return (long int) dat % 26;

これは、を指すものではなく、dat ポインタをハッシュします。試してみてください：Tdat

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）を実行します-コンパイラがあなたの持っているものを受け入れることに驚いています。（a）を使用する場合、デストラクタには何も必要ありません。（b）を使用する場合delete []は、デストラクタで使用する必要があります。

T*in getを渡すが、Tinsetも少し奇妙です。

于 2011-12-25T13:38:21.307 に答える
1

より慣用的な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;
}

std :: arrayクラスを使用するには、c++0xまたはc++11の機能を使用してコンパイルする必要があることに注意してください。配列クラスの主な利点の1つは、単なるcスタイルの配列よりもメモリ割り当ての安全性が高くなることです。

今、あなたはデザインのいくつかの要素を再考したいかもしれません。add特に、とgetは異なるタイプを持っていることは混乱を招きます。また、これは人々がハッシュマップを聞いたときに一般的に考えることではなく、この構造はセットのようなものです。

また、コーディング標準に注意してください。メンバー変数の前にプレフィックスを付ける場合は、this->それらにアクセスするためにも使用するのは少しトートロジー的です。

于 2011-12-25T14:00:07.867 に答える