C++ Lista połączona za pomocą inteligentnych wskaźników

Question

Używałem tylko surowych wskaźników dla połączonych list z szablonami. Na przykład dane elementu, Node<T>* head; i kiedy wstawiam węzeł do jednej z linii, będzie head = new Node<T>(data);.

Jednak teraz potrzebuję inteligentnego wskaźnika i nie jestem pewien, jak to zmienić, by używać inteligentnych wskaźników. Czy dane członków zostaną zmienione na shared_ptr<Node<T>> head;, a druga linia zostanie zmieniona na
head = shared_ptr<Node<T>>(new <Node<T>>(data));?

Answer 1

Nie musisz "używać" inteligentnego wskaźnika dla połączonej listy, ponieważ to stwierdzenie nie ma sensu. Robisz nie używać inteligentnych wskaźników dla struktur danych niskiego poziomu. Używasz inteligentnych wskaźników dla logiki programu wysokiego poziomu.

Jeśli chodzi o struktury danych niskopoziomowe są zainteresowane, użyć standardowej klasy kontenera z C++ biblioteki standardowej, jak std::list^[*], który rozwiązuje wszystkie problemy zarządzania pamięcią i tak, bez użycia żadnych inteligentne kursory wewnętrznie.

Jeśli naprawdę bardzo trzeba własną wysoce specjalistycznego/zoptymalizowany niestandardowej klasy pojemnika, ponieważ cała C++ biblioteki standardowej nie nadaje się do wymagań i trzeba wymiany dla std::list, std::vector, std::unordered_map i inne optymalizowane, testowane udokumentowane i bezpieczne pojemniki –, które bardzo wątpię! –, to musisz ręcznie zarządzać pamięcią, ponieważ punkt takiej specjalistycznej klasy prawie na pewno będzie potrzebował takich technik, jak pule pamięci, kopiowanie przy zapisie, a nawet wyrzucanie śmieci, z których wszystkie kolidują z typowymi inteligentnymi wskaźnikami. raczej uproszczona logika usuwania.

W słowach Herb Sutter:

Nigdy nie używaj posiadanie surowych wskaźników i usuwać wyjątkiem rzadkich przypadków, kiedy realizacji własną strukturę danych niskopoziomowe (a nawet wtedy zachować że dobrze zamknięty wewnątrz granica klasy).

Coś wzdłuż tych linii jest również wyrażone w Herb Sutter's and Bjarne Stroustrup's C++ Core Guidelines:

Ten problem nie może być rozwiązany (w skali) poprzez przekształcenie wszystkie będące właścicielami wskaźniki do unique_ptrs i shared_ptrs, częściowo dlatego musimy/używać posiadanie "surowych wskaźników" oraz prostych wskaźników w implementacji naszego podstawowego zasobu obsługuje. Na przykład, powszechne implementacje wektora mają jeden wskaźnik i dwa wskaźniki nie będące właścicielami.

Pisanie klasy linkowane listy w C++ z surowych wskaźników może być użytecznym akademicki ćwiczenia. Pisanie klasy z listą dołączy w C++ za pomocą inteligentnych wskaźników jest bezsensownym ćwiczeniem akademickim. Używanie dowolnych z tych dwóch samodzielnie stworzonych rzeczy w kodzie produkcyjnym jest prawie automatycznie błędne.

---

^[*]Albo po prostu std::vector, ponieważ ze względu na cache miejscowości, które prawie zawsze będzie lepszym wyborem i tak.

Answer 2

Spojrzałbym na interfejs std :: list, który jest implementacją C++ połączonych list. Wygląda na to, że podchodzisz do templatowania swojej klasy listy powiązanej źle. Najlepiej jest, jeśli twoja połączona lista nie powinna przejmować się semantyką własności (tj. Czy jest tworzona z surowymi pikselami, inteligentnymi wskaźnikami lub zmiennymi przydzielonymi do stosu). Poniżej przedstawiono przykład własnościowych semicryków z kontenerami STL. Istnieją jednak lepsze przykłady STL i prawa własności z bardziej autorytatywnych źródeł.

#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. 

Dobrym ćwiczeniem zrozumieć własności, przydział pamięci/dealokacji i wspólnych wskaźników jest zrobić tutorial, w którym zaimplementować własną inteligentne kursory. Wtedy zrozumiesz dokładnie, jak używać inteligentnych wskaźników, a będziesz miał jedną z tych xen momentów, gdy zdasz sobie sprawę, jak prawie wszystko w C++ wraca do RAII (własność zasobów).

Wracam do sedna Twojego pytania. Jeśli chcesz trzymać się węzłów typu T, nie owijaj węzła w inteligentny wskaźnik. Węzeł destruktora musi usunąć bazowy surowy wskaźnik. Surowy wskaźnik może wskazywać na sam wskaźnik inteligentny określony jako T. Gdy wywoływany jest destruktor klasy "LinkedList", iteruje on przez wszystkie węzły z węzłem :: next i wywołuje delete node; po uzyskaniu wskaźnika do następnego węzła.

Można utworzyć listę, w której węzły są inteligentnymi wskaźnikami ... ale jest to bardzo wyspecjalizowana lista połączona, prawdopodobnie o nazwie SharedLinkedList lub UniqueLinkedList z bardzo różnymi semantami do tworzenia obiektów, popping itp. Tak jak przykład, UniqueLinkedList przesuń węzeł w wartości zwracanej po wywołaniu wartości dla osoby wywołującej. Wykonanie metaprogramowania dla tego problemu wymagałoby zastosowania częściowej specjalizacji dla różnych typów T. Przykład: coś takiego:

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; 
}; 

Teraz możesz rozpocząć wdrażanie własnego STL! Możesz już dostrzec potencjalne problemy, o których mowa w komentarzach do twojego pytania z tym podejściem. Jeśli węzły mają shared_ptr next, spowoduje to wywołanie destruktora tego węzła, który wywoła następny współdzielony destruktor węzła i tak dalej (możliwe jest przepełnienie stosu z powodu rekurencji). Dlatego nie dbam zbytnio o to podejście.

Answer 3

Istnieją dwa alternatywne rozwiązania o utworzenie wzmocnionej listy smart-pointer:

1. Korzystanie 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 
   

   To byłby mój pierwszy wybór. Unikalny wskaźnik _next dba o to, że nie ma wycieków pamięci, podczas gdy _prev jest wskaźnikiem obserwacji. Kopiowanie i takie rzeczy muszą jednak być definiowane i wdrażane ręcznie.

2. Korzystanie 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 
   

   Jest to bezpieczniejsza alternatywa, ale mniej wydajnych niż z unikalnym-pointer. Co więcej, można go kopiować według projektu.

W obu pomysł jest taki, że jeden węzeł posiada pełną listę pozostałych. Teraz, gdy węzeł wykracza poza zakres, nie ma niebezpieczeństwa, że ​​pozostała lista stanie się wyciekiem pamięci, ponieważ węzły są iteracyjnie niszczone (począwszy od ostatniego).

Wskaźnik w obu opcjach jest tylko wskaźnikiem obserwacji: jego zadaniem nie jest utrzymanie przy życiu poprzednich węzłów, a jedynie podanie linku do ich odwiedzenia. Zwykle wystarczająca jest Node * (--notacja: obserwując wskaźnik oznacza, że ​​nigdy nie robisz żadnych informacji związanych z pamięcią, takich jak new, delete na wskaźniku).

Jeśli potrzebujesz większego bezpieczeństwa, możesz również użyć do tego celu std::weak_ptr. zapobiega to od rzeczy jak

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 

Korzystanie z weak_ptr można lock() go iw ten sposób Chack czy _prev jest nadal ważny.