Удаление указателей из связанного списка в C++

Question

Я написал эту хэш-карту (это было частью телефонного интервью), где я делаю new Node(key, value) когда я положил элемент. Я хочу убедиться, что я очищаюсь, когда сама hashmap выходит из области видимости.

Я что-то здесь пропустил? Есть ли способ проверить, есть ли утечка памяти?

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() в конце (так как я уже освободил все узлы в списке)?

Answer 1

Похоже на то put строит Node положить в хэш-таблицу, связывая key а также value, Там не было необходимости использовать list<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 *>Затем вы должны также реализовать конструктор копирования и оператор присваивания ( правило трех).

Answer 2

Посмотрел, бросил свой код и заметил, что вы используете некоторые служебные конструкции.

Эти два фрагмента эквивалентны

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

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

Answer 3

Уборка в порядке. Незначительная точка:

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

лучше использовать префиксный инкремент по соображениям производительности. Форма postfix должна выдавать состояние итератора перед приращением. Этот объект будет немедленно отброшен. Компилятор может оптимизировать, но это зависит.

Answer 4

Лучший способ проверить, нет ли утечки памяти, - это использовать классы интеллектуальных указателей, которые не могут просочиться. shared_ptr<Node> или же unique_ptr<Node> может сделать здесь, первый для копируемой карты, второй для не копируемой.

Но в случае, если вам нужно использовать необработанные указатели (домашнее задание?), Есть вещи, которые отсутствуют: конструктор копирования и оператор присваивания. Если они не отключены или не реализованы, при копировании этого HashMap появятся висячие указатели (после уничтожения одной из карт).