

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

**HashList.h**

[code]

    #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;
        }
    
    };
    
[/code]

**main.cpp**

[code]

    #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;
    }
    
[/code]


CC BY-SA 4.0
2021-10-28T09:38:40.160
83303
2021-10-28T13:41:05.147
2021-10-28T09:49:06.190
2238
45177
question
c++
ハッシュテーブルのメモリーの解放のやり方


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

[code]

    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);
    
    }
    
[/code]


CC BY-SA 4.0
2021-10-28T09:58:35.210
83305
2021-10-28T12:53:16.763
2021-10-28T12:53:16.763
40660
40660
83303
answer


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

  * 各要素に `delete array[i]`
  * `delete[] array`

の両方が必要です。

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

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


CC BY-SA 4.0
2021-10-28T12:57:24.653
83309
2021-10-28T13:41:05.147
2021-10-28T13:41:05.147
3475
3475
83303
answer