Lista podwójnie połączona z inteligentnymi wskaźnikami: problemy z metodą wstawiania

Dec 25 2020

Próbuję zaimplementować listę podwójnie połączoną z szablonem, postępując zgodnie z książką Stroustrupa „Zasady i praktyka przy użyciu C ++”, rozdział 20.4. Zamiast surowych wskaźników chcę użyć unikalnych wskaźników . Kod jest zorganizowany w następujący sposób:

  • nagłówek Node.h, w którym zaimplementowano strukturę Node: a unique_pointerjest używany dla następnego węzła, a surowy dla poprzedniego
  • nagłówek Iterator.h, gdzie Iteratorjest zaimplementowany
  • nagłówek List.h, gdzie klasa Listjest zaimplementowana
  • main.cpp, w którym testowane są metody

Widziałem, że były inne dość podobne pytania, takie jak to, ale nie wiem, czy projekt mojej metody wstawiania: iterator insert(iterator p, const T& x)jest w porządku . W szczególności otrzymuję błąd segmentacji, gdy dzwonię auto it3 = insert(--p,4). Czy to w porządku, czy powinienem to naprawić?

Oto mój Node.h

#ifndef Node_h
#define Node_h

#include <algorithm>
#include <iostream>
#include <memory>  // std::unique_ptr
#include <utility> // std::move



namespace Node {


template <typename T>
struct Node {
    T data;
    std::unique_ptr<Node> next;
    Node* previous;
    
    Node() noexcept = default;
    explicit Node(const T& _data) : data{_data}, next{nullptr},previous{nullptr} {
        std::cout << "l-value"<<std::endl;
    }
    Node(const T& _data, Node* _next, Node* _previous): data{_data}, next{_next}, previous{_previous} {}

    explicit Node(T&& x) : data{std::move(x)} {
      std::cout << "r-value" << std::endl;
    }
    
    Node(T&& x, Node* _next, Node* _previous) : data{std::move(x)}, next{_next}, previous{_previous} {
      std::cout << "r-value" << std::endl;
    }
    
    explicit Node(const std::unique_ptr<Node> &x) : data{x->data} {
        if (x->next){
        next.reset(new Node{x->next});
        }
//        if (x->previous){
//            previous.reset(new Node{x->previous});
//        }
    }
    
    
    
    ~Node()=default;
    
    //Move semantics, Copy semantics
    
    void printNode(){
        std::cout << "Data is: " << data <<"\n";
    }
    
 };

} //end namespace

#endif /* Node_h */

Następnie mamy Iterator.h

#ifndef Iterator_h
#define Iterator_h

#include "Node.h"
#include <iterator>

template <typename T >
struct __iterator {;
    using NodeT = Node::Node<T>;
    NodeT* current;
    
//public:
    using value_type = T;
    using difference_type = std::ptrdiff_t;
    using iterator_category = std::forward_iterator_tag;
    using reference = value_type&;
    using pointer = value_type *;
    
    explicit __iterator(NodeT* p) : current{p} {}
    __iterator() noexcept=default;
    ~__iterator()=default;
    
    reference operator*() const noexcept{
        return current->data;
    }
    
    pointer operator->() const noexcept{
        return &**this;
    }
    
    __iterator& operator++() {
      current = current->next.get();
      return *this;
    }
    
    __iterator& operator--(){
        current=current->previous; //previous is just a raw pointer
        return *this;
    }
    
    
    
    friend bool operator==(__iterator &a, __iterator &b) {
      return a.current == b.current;
    }
    

    friend bool operator!=(__iterator &a, __iterator &b) { return !(a == b); }
};

#endif /* Iterator_h */

Oto nagłówek List.h

#include "Iterator.h"
#include <cassert>

template <typename T>
class List {
private:
    std::unique_ptr<Node::Node<T>> first;
    std::unique_ptr<Node::Node<T>> last;
    int _size;
public:
    
    
    using iterator = __iterator<T>;
    
    iterator begin(){return iterator{first.get()};}
    iterator end(){return iterator{nullptr};} //one past the last
    
    iterator go_to(const int n){
        assert(n>=0);
        int i=0;
        if (n < _size) {
            auto tmp{begin()};
            while (i<n) {
                ++tmp;
                ++i;
            }
            return tmp;
        }else{
            return iterator{nullptr};
        }
    }

    List() : first{nullptr}, last{nullptr},_size{0} {}
    ~List() noexcept = default;
    
    
    template <typename O>
    void push_front(O &&x) { // forwarding ref. not r-value

        first.reset(new Node::Node<T>{std::forward<O>(x),first.release(),nullptr});
        if (_size==0) {
            last.reset(nullptr);
        }
        
        ++_size;
    }
    
    template <typename O> //forward reference
    void push_back(O&& x){
        auto tmp = first.get();
        auto _node = new Node::Node<T>{std::forward<O>(x)};
        if (!tmp) {
            first.reset(_node);
            return;
        }

        while (tmp->next) {
            tmp = tmp->next.get();
        }
        tmp->next.reset(_node);
        ++_size;
    }
    
    
    iterator substitute(iterator p, const T& x){
        //_size must not be incremented!
        iterator tmp{p};
        if(tmp.current){
            *tmp = x;
            return tmp;
        }else{
            return iterator{nullptr};
        }

    }
    
    iterator insert(iterator position,const T& value) {
        auto newNode = new Node::Node<T>(value, position.current->next.get(), position.current);
        std::cout << position.current << std::endl;
        if (position.current == last.get() ) {
            last.reset(newNode);
        }
        
        position.current->next.release(); //otherwise: "pointer being freed was not allocated"
        position.current->next.reset(newNode); //set next of previous node to newNode
        ++_size;
        return position;
    }
    

    

    
    friend std::ostream& operator<<(std::ostream& os, List& l){
        auto itStop = l.end();
        os << "The list has " << l._size << " elements"<<"\n";
        for (auto it = l.begin(); it!=itStop; ++it) {
            os<< *it << " ";
        }
        return os;
    }
    
};

Na koniec mamy plik main.cpp z testami:

#include "List.h"

int main() {

    
    List<int> l{};

    int i=8;
    l.push_front(i); //l-value
    l.push_back(4); //r-value
    l.push_back(i+2); //r-value
    l.push_back(95); //r-value
    l.push_front(29); //l-value
    l.push_front(i*i); //r-value
    std::cout << "My list so far: " << l<<std::endl;

    auto p{l.go_to(3)};
    auto itt = l.substitute(p, 29);
    std::cout << "My list after substitution: \t" << l<<std::endl;

    auto pp{l.go_to(2)};
    auto it2 = l.insert(pp,98);
    std::cout << "My list after insertion: \t" << l<<std::endl;
    auto it3= l.insert(--pp,998);
    std::cout << "My list after insertion: \t" << l<<std::endl;
    
    return 0;
}

EDYCJA :

Poprawiona wersja push_front:

template <typename O>
void push_front(O&& x) {
    auto node = std::make_unique<Node::Node<T>>(std::forward<O>(x));
    std::swap(node, first);  
    first->next = std::move(node);
    if (_size == 0) {
        assert(!last);
        assert(!first->next);
        last = first.get();
    }else{
first->next->previous = first.get()
}
    ++_size;
}

Odpowiedzi

7 ruds Dec 26 2020 at 02:44

Masz wiele problemów z zarządzaniem pamięcią na tej połączonej liście. Kluczową rzeczą do zapamiętania jest to, że unique_ptrwskazuje na własność obiektu. Zastosowanie release, resetoraz w mniejszym stopniu getsą zapach kod: nie zawsze jest źle, ale często wskazanie, że klasa jest używana nieprawidłowo. Zwykle swapzamiast tego powinieneś użyć i przenieść przypisanie. Wywołam je podczas przeglądania plików.

Krótka uwaga: nie testowałem ani nawet nie skompilowałem następującego kodu; może zawierać błędy.

Node.h

To jest w większości w porządku. Konstruktor "copy" ( Node(std::unique_ptr<Node>&)) prawdopodobnie powinien zostać po prostu usunięty. Kopiowanie węzła i wszystkich jego potomków nie ma sensu. Nawet jeśli chciałeś takiego zachowania, ta implementacja jest błędna. Usuwa wszystkie poprzednie linki, dzięki czemu masz listę pojedynczo połączoną, która udaje listę podwójnie połączoną.

Iterator.h

Twoja klasa iteratora nie jest całkiem poprawna. Nie działa jako enditerator. W szczególności --l.end()wykazuje niezdefiniowane zachowanie, ponieważ odwołuje się do pustego wskaźnika. W praktyce klasy iteratorów zwykle wymagają odwołania do kolekcji, z której pochodzą.

Ponadto ten iterator nie spełnia wymagań iteratora dwukierunkowego (wiem, że oznaczyłeś to jako iterator do przodu, ale również nie spełnia tych wymagań). W szczególności narusza:

  • „wartości typu spełnia Swapable”; Jestem trochę zardzewiały, ale jestem prawie pewien, że twój destruktor zadeklarowany przez użytkownika zapobiega generowaniu niejawnie zadeklarowanego konstruktora przenoszenia i operatora przypisania przenoszenia; musisz dostarczyć te funkcje (np. używając = default) lub swapfunkcję.
  • Nie obsługuje operatorów zwiększania i zmniejszania przyrostka.

List.h

List::lasttak naprawdę nie jest poprawnie zaimplementowany. O ile mogę się zorientować, nigdy nie jest ustawiony na nic innego niż nullptrkod, jaki jest. W każdym razie nie powinno to być a unique_ptr, ponieważ wszystko, na co wskazuje, jest już własnością innego unique_ptr.

Więc przejdźmy lastdo Node::Node<T>*. Mamy następujące niezmienniki, które są prawdziwe przed i po każdym wyjść funkcyjnych członkiem: if _size == 0, first==last==nullptr. Inaczej,

  • first wskazuje na pierwszy węzeł na liście
  • first->previous == nullptr
  • Biorąc pod uwagę osiągalny węzeł n, n->nextma wartość null lubn->next.get() == n->next->previous
  • lastwskazuje ostatni osiągalny węzeł na liście. last.nextjest null.
  • _size węzły są osiągalne.

Musimy napisać nasze funkcje składowe, aby te niezmienniki pozostały prawdziwe.

go_tozwykle można osiągnąć poprzez zastosowanie się std::nextdo iteratora początkowego. To ma różnicę w zachowaniu, kiedy próbujesz przekroczyć koniec listy; użycie std::nextspowodowałoby w tym przypadku niezdefiniowane zachowanie. Jeśli chcesz mieć obecne zachowanie, możesz zaimplementować je za pomocą czegoś takiego jak

iterator go_to(const int n) const {
    if (n >= _size) {
        return end();
    } else {
        return std::next(begin(), n);
    }
}

Kiedy używasz unique_ptrdo zarządzania pamięcią, generalnie nie powinieneś używać new. Zamiast tego użyj, std::make_uniquejeśli używasz C ++ 14 lub nowszego (i napisz własne make_uniquew C ++ 11). Pozwala to poprawić bezpieczeństwo wyjątków w Twoim kodzie. Wypróbuj to dla push_front:

template <typename O>
void push_front(O&& x) {
    auto node = std::make_unique<Node::Node<T>>(std::forward<O>(x));
    swap(node, first);  // assuming you implement swap or add a "using std::swap;" on the previous line
    first->next = std::move(node);
    if (_size == 0) {
        assert(!last);
        assert(!first->next);
        last = first.get();
    }
    ++_size;
}

Tutaj węzeł jest tworzony w sposób bezpieczny dla wyjątków. Nie ma szans na wyciek first, ponieważ go nie udostępniamy (twój kod wyciekłby, firstgdyby alokacja się nie powiodła lub jeśli Nodekonstruktor wyrzucił (z powodu Twyrzucenia konstruktora przeniesienia)). Zakładając, że twoje operacje swapi movenie są rzucane, albo się push_frontpowiedzie, a nowy element został wstawiony na początku, albo alokacja nie powiedzie się, push_frontzgłasza się, a struktura danych nie została zmieniona.

Jeśli push_backnie używasz lasttutaj, nie ma powodu, aby lastw ogóle mieć .

template <typename O>
void push_back(O&& x) {
    auto node = std::make_unique<Node::Node<T>>(std::forward<O>(x));
    if (_size == 0) {
        assert(!last);
        assert(!first);
        first = std::move(node);
        last = node.get();
        _size = 1;
        return;
    }
    assert(!last->next);
    node->previous = last;
    last->next = std::move(node);
    last = last->next.get();
    ++_size;
}

Ponownie zapewniamy, że niezmienniki klasy są zachowane, nawet jeśli rzucimy podczas konstruowania nowego węzła.

Myślę, że nie substitutejest to rozsądna funkcja. Użytkownik listy powinien napisać *it = x;i powinien wiedzieć, czy jego iterator jest prawidłowy, czy nie.

Normalna semantyka dla insertto wstawianie wartości tuż przed przekazanym iteratorem, a nie tuż po. Pozwala to insertna wstawianie w dowolnym miejscu listy i oznacza, że insertma sensowną semantykę, gdy end()jest przekazywana jako iterator.

iterator insert(iterator it, const T& value) {
    auto node = std::make_unique<Node::Node<T>>(value);
    auto prev = it.current ? it.current->previous : last;
    auto ptr = prev ? &first : &prev->next;
    swap(*ptr, node);
    (*ptr)->next = std::move(node);
    (*ptr)->previous = prev;
    ++_size;
    if (!last) last = first.get();
    return iterator(ptr->get());
}
4 G.Sliepen Dec 26 2020 at 02:48

Przenieś się class Nodei struct __iteratordoclass List

Widok Node::Node<T>wewnątrz kodu jest bardzo dziwny . A Nodejest szczegółem implementacji twojego List, więc powinien być zadeklarowany w środku class List. To samo dotyczy __iterator. Na przykład:

template<typename T>
class List {
    class Node {
        T data;
        std::unique_ptr<Node> next;
        Node *previous;
    };
    
    std::unique_ptr<Node> first;
    std::unique_ptr<Node> last;
    ...

public:
    class iterator {
         Node *current;

    public:
         using value_type = T;
         ...
    };

    iterator begin() {...};
    ...
};

Zwróć uwagę, jak to wszystko pozwala uniknąć konieczności wprowadzania namespaces lub __przedrostków ( których powinieneś unikać ), aby je ukryć, i jak to zmniejsza liczbę przypadków, w których musisz jawnie pisać <T>. Oczywiście teraz wszystko musi być zadeklarowane w środku List.h, ale nie uważam tego za wadę.

1 theProgrammer Dec 25 2020 at 21:39

Myślę, że powinieneś postępować zgodnie ze standardem C ++ insertdla kontenerów , na przykład przekazując a begini enditerator

template<typename T>
void insert(Iterator begin, Iterator begin2, Iterator end2);
void insert(Iterator begin, T value);