Эта реализация geeksforgeeks tr ie имеет проблему с утечкой памяти? - PullRequest
Новая
       92

Эта реализация geeksforgeeks tr ie имеет проблему с утечкой памяти?

1 голос
/ 11 июля 2020

Я читаю geeksforgeeks_implementation_of_tr ie, и я обнаружил, что объекты TrieNode, созданные new, восстановлены, в основной функции есть восстановленный указатель root : 

struct TrieNode *root = getNode();

и в функции getNode() есть еще не удаленный указатель pNode, есть ли утечка памяти? Должна ли быть функция, отвечающая за разрушение дерева tr ie, составленного указателями? 

struct TrieNode *getNode(void) 
{ 
    struct TrieNode *pNode =  new TrieNode; 
    pNode->isEndOfWord = false; 
  
    for (int i = 0; i < ALPHABET_SIZE; i++) 
        pNode->children[i] = NULL; 
  
    return pNode; 
}

Ответы [ 2 ]

2 голосов
/ 11 июля 2020

Утечка или не утечка ...

Согласно Википедия , утечка происходит, когда компьютерная программа неправильно управляет выделением памяти таким образом, что память, которая не является больше не требуется, не освобождается :

  • Роль getNode() - вернуть указатель на инициализированный TrieNode. Таким образом, он ничего не утекает сам по себе: мы можем предположить, что в соответствии с его назначением соответствующий объект все еще необходим, когда функция возвращает свой указатель.

  • Контекст вызова действительно вызывает утечку памяти : как вы правильно заметили, он создает узел с getNode() и никогда не удаляет этот узел. Это плохая практика.

Но вы должны заменить этот код в его контексте: статья является учебным пособием. Он предлагает удаление как дополнительное упражнение .

Почему они не показывают удаление в учебнике

Потому что удаление TrieNode - непростая задача, если вам нужно позаботьтесь сами: удаление узла требует также найти все упомянутые узлы, которые также следует удалить. Поскольку tr ie является графом, более одного узла могут указывать на одно и то же место назначения. Таким образом, вы не можете удалить эти узлы вслепую, если не хотите рисковать UB из-за висящих указателей и двойных удалений. Вам нужно будет реализовать алгоритм маркировки или какой-то подсчет ссылок

Но не следуйте этому руководству

Эта реализация TrieNode крайне плохая: в современном C ++:

  • вы могли бы позволить конструктору инициализировать TrieNode, будь то динамически созданный узел или локальный узел.
  • вы бы использовали интеллектуальный указатель вместо необработанного указателя. Поскольку на узел по своей природе можно ссылаться несколько раз, вы бы go вместо shared_ptr
  • вы, вероятно, предпочли бы использовать vector<shared_ptr<TrieNode>> или даже map<char, shared_ptr<TrieNode>> вместо старого - массив стилей.

Но я бы все же позволил вам удалить в качестве упражнения; -)

2 голосов
/ 11 июля 2020

Эта функция подразумевает контракт, в котором вызывающая функция отвечает за удаление выделенного TrieNode. Утечка памяти происходит только в том случае, если вызывающий объект не соблюдает этот контракт.

Поскольку вы сказали, что этот TrieNode не удаляется нигде в main, вероятно, утечка. Если вы не найдете место, где эта структура удалена, есть утечка. Вот почему RAII - такая мощная концепция. Если бы существовал объект Trie, который содержал все TrieNode s и отвечал за выделение и удаление узлов, тогда вам вообще не пришлось бы беспокоиться об утечках.

Возложение на вызывающего абонента ответственности за управление выделенные ресурсы опасны. Не делайте этого.

Вы можете возразить, что эта конкретная реализация не обязательно является утечкой, если программа достаточно проста, и все, что она делает, это получает TrieNode s, что-то с ними делать и затем выйдите. В этом случае память будет освобождена ОС при выходе из программы. Но это аргумент semanti c, и предоставление примера кода, который делает это, является плохой практикой и может привести к тому, что культовые программисты автомобилей сделают это плохой практикой.

...