2

私はこのハッシュ マップを書きました (これは電話インタビューの演習の一部でした) new Node(key, value)。ハッシュマップ自体が範囲外になったときにクリーンアップしていることを確認したい.

ここで何か見逃しましたか？メモリリークがあるかどうかを確認する方法はありますか?

class HashMap {
private:
    list<Node*> data[SIZE];

public:
    ~HashMap();
    Node* get(int key);
    void put(int key, int value);

    int hashFn(int val){ return val % 13; }
};

HashMap::~HashMap(){
    for(int i = 0; i < SIZE; ++i){
        list<Node*>& val = data[i];
        for(list<Node*>::iterator it = val.begin(); it != val.end(); it++){
            Node* n = *it;
            delete n;
        }
    }
}

好奇心のために: 完全なコードはこちら: http://rextester.com/EHPCYW12862

編集：

また、最後にlist.clear () を呼び出す必要がありますか (リスト内のすべてのノードの割り当てを既に解除しているため)。

4

4 に答える 4

1

コードを投げてみると、いくつかのオーバーヘッド構造を使用していることに気付きました。

これら 2 つのスニペットは同等です

Node ** d = &(*it); 
if((*d)->key == key){
    return *d;
}

if((*it)->key == key){
    return (*it);
}
于 2012-08-10T07:29:33.920 に答える
1

と を関連付けて、ハッシュテーブルに入れる をput構築しているようです。を使用する必要はありませんでした。代わりに使用する方がクリーンでした。Nodekeyvaluelist<Node *>list<Node>

list<Node> data[SIZE];
//...
data[bucket].push_front(Node(key, value));

次に、デストラクタの実装を回避できた可能性があります。

関数getは引き続きポインターを返すことができます。

Node* HashMap::get(int key){
    //...
    list<Node>::iterator it = data[bucket].begin();
    //...
            if (it->key == key) return &*it;
    //...
    return NULL;
}

で実装を残す場合はlist<Node *>、コピー コンストラクターと代入演算子も実装する必要があります ( 3 つのルール)。

于 2012-08-10T07:10:34.963 に答える
1

クリーンアップは問題ありません。マイナーポイント：

   for(list<Node*>::iterator it = val.begin(); it != val.end(); ++it)

パフォーマンス上の理由から、プレフィックス付きの増分を使用することをお勧めします。後置形式は、インクリメントの前に反復子の状態を提供する必要があります。このオブジェクトはすぐに破棄されます。コンパイラは最適化するかもしれませんが、依存します。

于 2012-08-10T07:11:48.737 に答える
1

メモリ リークがないかどうかを確認する最善の方法は、リークできないスマート ポインター クラスを使用することです。shared_ptr<Node>またはunique_ptr<Node>、ここで行うこともできます。1 つ目はコピー可能なマップ用、2 つ目はコピー不可能なマップ用です。

しかし、生のポインターを使用する必要がある場合 (宿題?) には、不足しているものがいくつかあります: コピー コンストラクターと代入演算子です。それらが無効化または実装されていない場合、この HashMap をコピーすると、ダングリング ポインターが生成されます (マップの 1 つが破棄された後)。

于 2012-08-10T07:07:11.343 に答える