2

ハッシュテーブルのプログラムを作ったのですが、メモリーの解放のやり方が間違っていると指摘を受けました。一応、メモリーの解放以外はうまくいっているつもりです。~HashListとaddItemでメモリーがうまく解放されていないみたいです。~HashListでは、デストラクタを呼ばず、listを開放して、そしてarrayを開放しろと指摘されました。そして、addItemでは、arrayのサイズを変更するif(counter > arraySize*2)の部分では古いリストを開放しろと指摘を受けました。~HashListでは、delete [] array; とやったところそれも違うとゆわれました。自分の中ではarrayを開放すればそこに紐づけているlistも解放されると思ったのですが、違うみたいです。おそらく、同じような問題だとはおもうのですが、Listの解放の仕方が分かっていません。この二つの解放についての問題がとける方よろしくお願いします。

HashList.h

#include <iostream>
#include <sstream>

using std::string;

class Link
{
private:
    string value;
    Link* next;
public:
    Link(string value, Link* next = nullptr){this->value = value; this->next = next;}
    ~Link(){}
    string getValue(){return value;}
    Link* getNext(){return next;}
    void setNext(Link* next){this->next = next;}
};

class List
{
private:
    Link* head;
public:
    List(){head = nullptr;}
    List::~List()
    {
        while(head != nullptr)
        {
            removeHead();
        }
    }

    void removeHead()
    {
        //create a new link to remove later
        Link* temp = head;

        //head move one step forward
        head = head->getNext();

        //delete the old link
        delete temp;
    }
    void addHead(string value)
    {
        Link* temp = new Link(value, head);
        head = temp;
    }
    Link* getHead(){return head;}

};


class HashList {
private:
    int arraySize;
    List** array;
    int counter = 0;
public:
    HashList(){
        arraySize = 7;
        array = new List*[arraySize];
        for(int i = 0; i < arraySize; i++)
        {
            array[i] = new List;
        }
    }

    HashList(int size)
    {
        if(size < 7)
        {
            size = 7;
        }
        arraySize = size;

        array = new List*[arraySize];
        for(int i = 0; i < arraySize; i++)
        {
            array[i] = new List;
        }
    }

    ~HashList()
    {
        for(int i = 0; i < arraySize; i++)
        {
            array[i]->~List();
        }
    }

    int hash(string value)
    {
        int hashValue = 0;

        //figure out the index
        for(int i = 0; i < value.length(); i++)
        {
            hashValue *= 128;
            hashValue += value[i];
            hashValue %= arraySize;
        }

        //return the index
        return hashValue;
    }


    void addItem(string value)
    {
        counter++;
        if(counter > arraySize*2)
        {
            int oldSize = arraySize;
            arraySize = closePrime(oldSize);
            List** newArray = new List*[arraySize];
            for(int i = 0; i < arraySize; i++)
            {
                newArray[i] = new List;
            }

            for(int i = 0; i < oldSize; i++)
            {
                Link* temp = array[i]->getHead();
                while(temp != nullptr)
                {
                    newArray[hash(temp->getValue())]->addHead(temp->getValue());
                    temp = temp->getNext();
                }
            }

            delete [] array;

            array = newArray;
        }

        array[hash(value)]->addHead(value);

    }

    string displayTable()
    {
        std::stringstream ss;
        string output;

        for(int i = 0; i < arraySize; i++)
        {
            Link* temp = array[i]->getHead();

            if(temp == nullptr)
            {
                ss << "_empty_";
            }

            while(temp != nullptr)
            {
                ss << temp->getValue() << " ";
                temp = temp->getNext();
            }

            ss << "\n";

        }

        output = ss.str();

        return output;
    }

    bool ifPrime(int value)
    {
        int remain = 0;
        for(int i = 2; i < value; i++)
        {
            if(value % i == 0)
            {
                remain++;
            }
        }
        if(remain == 0)
        {
            return true;
        }
        return false;
    }

    int closePrime(int value)
    {
        int prime;
        bool find = false;
        int diff = 1;
        value = value * 2;
        while(!find)
        {
            if(ifPrime(value+diff) == true)
            {
                find = true;
                prime = value + diff;
            }
            else if(ifPrime(value-diff) == true)
            {
                find = true;
                prime = value - diff;
            }
            else
            {
                diff++;
            }
        }
        std::cout << "prime is " << prime << std::endl;
        return prime;
    }

};

main.cpp

#include <iostream>
#include "HashList.h"

using namespace std;

int main() {
    HashList test;

    test.addItem("Hello");
    test.addItem("Helloa");
    test.addItem("Hellob");
    test.addItem("Helloc");
    test.addItem("Hellod");
    test.addItem("Helloe");
    test.addItem("Hellof");

    test.addItem("Hellog");
    test.addItem("Helloh");
    test.addItem("Helloi");
    test.addItem("Helloj");
    test.addItem("Hellok");
    test.addItem("Hellol");
    test.addItem("Hellom");

    test.addItem("Hellon");
    cout << test.displayTable() << endl;


    return 0;
}

2 件の回答 2

0

arrayのタイプはList**ですので、なかみはそれぞれList*でした。そのList*達も一つずつ解放しなければなりません。

void addItem(string value)
{
    counter++;
    if(counter > arraySize*2)
    {
        int oldSize = arraySize;
        arraySize = closePrime(oldSize);
        List** newArray = new List*[arraySize];
        for(int i = 0; i < arraySize; i++)
        {
            newArray[i] = new List;
        }

        for(int i = 0; i < oldSize; i++)
        {
            Link* temp = array[i]->getHead();
            while(temp != nullptr)
            {
                newArray[hash(temp->getValue())]->addHead(temp->getValue());
                temp = temp->getNext();
            }
        }
        
        /************ここが必要*****************/
        for(int i = 0; i < oldSize; i++)
        {
            delete array[i];
        }
        /***************************************/
        delete [] array;

        array = newArray;
    }

    array[hash(value)]->addHead(value);

}
3
  • for(int i = 0; i < arraySize; i++) { array[i]->~List(); }これではList*を開放していることにはなりませんか? Commented 2021年10月28日 11:58
  • そのコードは~HashList()の中にあるので、HashListdeleteする時点しか実行されていません。HashList自体は存続する場合List** arrayだけをdeleteすると、~HashList()は実行されないので、arrayの中身を一つずつdeleteするしかありません。
    – Ricky Mo
    Commented 2021年10月28日 12:49
  • なるほど、つまり、ChainHashデストラクタも同じようにfor(int i = 0; i < oldSize; i++) { delete array[i]; }とdelete [] array; が必要になるってことですね。 Commented 2021年10月28日 13:44
0

array の各要素は new List で確保されていますから、array を開放するには、

  • 各要素に delete array[i]
  • delete[] array

の両方が必要です。

配列をdelete[]すると、各要素もデストラクトされますが、ただのポインタをデストラクトしても何も起きません。ここで自動的にListを開放するためには、arrayList* ではなく std::unique_ptr<List>List の配列にします。

さいきんのC++では、そもそもnew delete を避けるのが堅実な書き方です。arraynew deleteを避けるために、arrayの型は std::vector<List> にすると間違いが減ると思います。

1
  • シンプルでとても分かりやすいです。やはり自分のやり方では2段階で解放してあげないといけないのですね。 Commented 2021年10月28日 13:45

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。