C++ Связанный список с помощью интеллектуальных указателей

Question

Я использовал только необработанные указатели для связанного списка с шаблонами. Например, данные элемента, Node<T>* head;, и когда я вставляю узел, одна из строк будет head = new Node<T>(data);.

Однако теперь мне нужно использовать интеллектуальный указатель, и я не уверен, как изменить его, чтобы использовать интеллектуальные указатели. Изменены ли данные членов на shared_ptr<Node<T>> head;, а другая строка изменится на
head = shared_ptr<Node<T>>(new <Node<T>>(data));?

Answer 1

Вам не нужно использовать интеллектуальный указатель для связанного списка, потому что это утверждение не имеет смысла. Вы делаете не используйте интеллектуальные указатели для низкоуровневых структур данных. Вы используете интеллектуальные указатели для высокоуровневой программной логики.

Что касается структуры данных низкого уровня обеспокоена, вы используете стандартный класс контейнера из стандартной библиотеки C++, как std::list^[*], который решает все проблемы управления памятью в любом случае, без использования каких-либо интеллектуальных указателей внутренне.

Если вы действительно очень нужен свой узкоспециализированный/оптимизированный пользовательский класс контейнера, поскольку вся стандартная библиотека С ++ непригоден для ваших требований и вам необходимо замену для std::list, std::vector, std::unordered_map и другие оптимизированы, проверены, документированные и безопасные контейнеры –, которые я очень сомневаюсь! –, тогда вам все равно нужно управлять памятью вручную, потому что точка такого специализированного класса почти наверняка будет нуждаться в таких методах, как пулы памяти, копирование на запись или даже сборка мусора, все из которых конфликтуют с типичными интеллектуальными указателями довольно упрощенная логика удаления.

По словам Herb Sutter:

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

Что-то вдоль этих линий также выражается в Herb Sutter's and Bjarne Stroustrup's C++ Core Guidelines:

Эта проблема не может быть решена (в масштабе), превращая все владеющие указателей на unique_ptrs и shared_ptrs, отчасти потому, что нам нужно/использовать владеющие «исходными указателями», а также простые указатели в реализации нашего основного ресурса обрабатывают. Например, общие векторы имеют один владеющий указатель и два указателя, не принадлежащие владельцу.

Дать класс связного списка в C++ сырьём указателей может быть полезным академической упражнения. Написание класса связанных списков на C++ с помощью интеллектуальных указателей - бессмысленное академическое упражнение. Использование любой из этих двух самодельных вещей в производственном коде почти автоматически ошибочно.

---

^[*]Или просто std::vector, потому что из-за тайника местности, что почти всегда будет лучшим выбором в любом случае.

Answer 2

Я бы посмотрел интерфейс std :: list, который является реализацией связанных списков C++. Кажется, что вы неправильно подходите к шаблону вашего списка Linked list. В идеале ваш связанный список не должен заботиться о семантике владения (то есть, будет ли он создан с помощью raw ptrs, интеллектуальных указателей или переменных, выделенных стеком). Ниже приведен пример семантики собственности с контейнерами STL. Тем не менее, есть лучшие примеры STL и права собственности из более авторитетных источников.

#include <iostream> 
#include <list> 
#include <memory> 

using namespace std; 

int main() 
{ 

    // Unique ownership. 
    unique_ptr<int> int_ptr = make_unique<int>(5); 

    { 
     // list of uniquely owned integers. 
     list<unique_ptr<int>> list_unique_integers; 

     // Transfer of ownership from my parent stack frame to the 
     // unique_ptr list. 
     list_unique_integers.push_back(move(int_ptr)); 

    } // list is destroyed and the integers it owns. 

    // Accessing the integer here is not a good idea. 
    // cout << *int_ptr << endl; 
    // You can make a new one though. 
    int_ptr.reset(new int(6)); 

    // Shared ownership. 
    // Create a pointer we intend to share. 
    shared_ptr<int> a_shared_int = make_shared<int>(5); 

    { 
     // A list that shares ownership of integers with anyone that has 
     // copied the shared pointer. 
     list<shared_ptr<int>> list_shared_integers; 

     list_shared_integers.push_back(a_shared_int); 

     // Editing and reading obviously works. 
     const shared_ptr<int> a_ref_to_int = list_shared_integers.back(); 
     (*a_ref_to_int)++; 
     cout << *a_ref_to_int << endl; 

    } // list_shared_integers goes out of scope, but the integer is not as a 
    // "reference" to it still exists. 

    // a_shared_int is still accessible. 
    (*a_shared_int)++; 
    cout << (*a_shared_int) << endl; 

} // now the integer is deallocated because the shared_ptr goes 
// out of scope. 

Хорошее упражнение для понимания собственности, распределение памяти/открепления и общих указателей, чтобы сделать учебник, где реализовать свои собственные смарт-указатели. Затем вы точно поймете, как использовать интеллектуальные указатели, и у вас будет один из тех моментов xen, где вы поймете, как почти все на C++ возвращается в RAII (владение ресурсами).

Итак, вернемся к сути вашего вопроса. Если вы хотите придерживаться Узлов типа T, не переносите узел в интеллектуальный указатель. Деструктор узла должен удалить основной необработанный указатель. Необработанный указатель может указывать на сам смарт-указатель, указанный как T. Когда ваш деструктор класса «LinkedList» называется, он выполняет итерацию через все узлы с узлом Node :: next и вызывает delete node; после того, как он получил указатель на следующий узел.

Вы можете создать список, где узлы являются интеллектуальными указателями ... но это очень специализированный связанный список, который, вероятно, называется SharedLinkedList или UniqueLinkedList с очень разными семантическими свойствами для создания объекта, выскакивания и т. Д. Как пример, UniqueLinkedList переместите узел в возвращаемое значение при появлении значения вызывающему. Для выполнения метапрограммирования для этой задачи потребуется использование частичной специализации для разных типов передаваемых T. Пример: что-то вроде:

template<class T> 
struct LinkedList 
{ 
    Node<T> *head; 
}; 

// The very start of a LinkedList with shared ownership. In all your access 
// methods, etc... you will be returning copies of the appropriate pointer, 
// therefore creating another reference to the underlying data. 
template<class T> 
struct LinkedList<std::shared_ptr<T>> 
{ 
    shared_ptr<Node<T>> head; 
}; 

Теперь вы начинаете внедрять свои собственные STL! Вы уже можете увидеть потенциальные проблемы, упомянутые в комментариях к вашему вопросу при таком подходе. Если узлы имеют shared_ptr next, это приведет к вызову деструктора этого общего узла, который вызовет следующий общий деструктор узла и т. Д. (Возможен переполнение стека из-за рекурсии). Поэтому я не очень люблю этот подход.

Answer 3

Есть в основном два варианта, чтобы создать смарт-указатель расширенного списка:

1. Использование std::unique_ptr:

   template<typename T> 
   struct Node 
   { 
       Node* _prev; 
       std::unique_ptr<Node> _next; 
       T data; 
   }; 
   
   std::unique_ptr<Node<T> > root; //inside list 
   

   Это будет мой первый выбор. Уникальный указатель _next заботится о утечке памяти, тогда как _prev является указателем наблюдения. Копирование и такие вещи, однако, должны быть определены и реализованы вручную.

2. Использование shared_ptr:

   template<typename T> 
   struct Node 
   { 
       std::weak_ptr<Node> _prev; //or as well Node* 
       std::shared_ptr<Node> _next; 
       T data; 
   }; 
   
   std::shared_ptr<Node<T> > root; //inside list 
   

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

Идея состоит в том, что одному узлу принадлежит полный оставшийся список. Теперь, когда узел выходит из области видимости, нет опасности, что оставшийся список станет утечкой памяти, так как узлы итеративно уничтожаются (начиная с последнего).

Указатель _prev в обоих вариантах имеет только указатель наблюдения: задача состоит не в том, чтобы сохранить прежние узлы в живых, а только для того, чтобы предоставить ссылку для их посещения. Для этого обычно достаточно Node * (-note: наблюдающий указатель означает, что вы никогда не делаете связанных с памятью вещей, таких как new, delete на указателе).

Если вам нужна дополнительная безопасность, вы также можете использовать std::weak_ptr. это предотвращает от таких вещей, как

std::shared_ptr<Node<T> > n; 
{ 
    list<T> li; 
    //fill the list 
    n = li.root->next->next; //let's say that works for this example 
} 
n->_prev; //dangling pointer, the previous list does not exists anymore 

Используя weak_ptr, вы можете lock() его и таким образом Chack ли _prev остается в силе.