Использование умных указателей в двусвязных списках

Question

Вот что я знаю об умных указателях

1. shared_ptr - это умный указатель, так что несколько shared_ptr могут указывать на объект в куче. Даже если один из shared_ptr будет удален, объект в куче не будет уничтожен, если его счетчик ссылок выше нуля.
2. слабый_птр также указывает на объект в куче, но не увеличивает счетчик ссылок на этот объект
3. мы можем использовать weak_ptr для разрыва циклической ссылки

В случае двусвязных списков у нас есть два указателя для указания на предыдущий и следующий узел. Мы используем shared_ptr и weak_ptr в реализации. Почему бы нам не использовать два слабых_птр?

Answer 1

Мы могли бы использовать shared_ptr до next и weak_ptr до prev, но не два weak_ptr. Если нет shared_ptr, указывающего на узел, счетчик ссылок становится равным нулю, а weak_ptr становится nullptr.

В любом случае, использование shared_ptr для связанных списков является излишним. Поскольку только один объект владеет узлом (головой или предыдущим узлом), подойдет простой unique_ptr для next с необработанным указателем на prev.

Обратите внимание, что использование умных указателей сопряжено с риском для связанных списков. Проблема возникает, когда длинный список разрушается, он разрушается рекурсивно. Деструктор узла вызывает деструктор умного указателя, который вызывает деструктор узла. Скорее всего, stacj будет расти в O (n). Поскольку список может быть длиннее максимально возможного стека, код может исчерпать пространство стека и вызвать сбой .

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

Answer 2

Мы не используем два weak_ptr, потому что это не сработает.

Представьте список с двумя узлами. Заголовок списка - это неслабый ptr первого узла. Таким образом, первый узел остается в живых. Но какой неслабый указатель поддерживает работу второго узла?

Существует две проблемы управления временем жизни объектов. Они должны оставаться в живых достаточно долго, но не слишком долго. Это не только для C ++ или умных указателей, это основная проблема практически во всех языках программирования. Вы решаете ее, понимая проблему, над которой работаете, и выражая ее в инструментах, которые дает вам ваш язык.