스마트 포인터가있는 이중 연결 목록 : 삽입 방법 문제

Dec 25 2020

Stroustrup의 저서 "Principles and Practice using C ++", Chapter 20.4에 따라 Templated Double Linked List를 구현하려고합니다. 원시 포인터 대신 고유 포인터 를 사용하고 싶습니다 . 코드는 다음과 같이 구성됩니다.

구조체 Node가 구현 된 헤더 Node.h : a unique_pointer는 다음 노드에 사용되고 원시 노드는 이전 노드에 사용됩니다.
Iterator이 구현 된 헤더 Iterator.h
클래스 List가 구현 된 헤더 List.h
메서드가 테스트되는 main.cpp

나는 이것 과 같은 다른 꽤 비슷한 질문 이 있다는 것을 보았지만 내 삽입 방법의 디자인 iterator insert(iterator p, const T& x)이 괜찮은지 모르겠습니다 . 특히를 호출하면 세그멘테이션 오류가 발생합니다 auto it3 = insert(--p,4). 괜찮습니까, 아니면 수정해야합니까?

여기 내 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 */

그런 다음 여기에 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 */

다음은 헤더 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;
    }
    
};

마지막으로 테스트가 포함 된 main.cpp 파일이 있습니다.

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

수정 :

수정 된 버전 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;
}

답변

7 ruds Dec 26 2020 at 02:44

이 연결 목록에서 메모리 관리에 많은 문제가 있습니다. 기억해야 할 핵심 unique_ptr은 객체의 소유권 을 나타냅니다. 의 사용 release, reset그리고 조금 적게 get항상 잘못 아니지만, 종종 클래스가 잘못 사용되고 있다는 표시 : 코드 냄새입니다. 일반적으로 swap대신 사용 및 이동 할당 을 사용해야합니다 . 파일을 살펴볼 때 이것을 불러내겠습니다.

참고 : 다음 코드를 테스트하거나 컴파일하지 않았습니다. 약간의 오류가있을 수 있습니다.

Node.h

이것은 대부분 괜찮습니다. "복사"생성자 ( Node(std::unique_ptr<Node>&))는 아마도 제거되어야합니다. 노드와 모든 하위 항목을 복사하는 것은 실제로 의미가 없습니다. 해당 동작을 원하더라도이 구현은 버그가 있습니다. 이전 링크를 모두 제거하므로 이중 연결 목록 인 것처럼 가장하는 단일 연결 목록이 있습니다.

Iterator.h

반복기 클래스가 옳지 않습니다. end반복자 로 작동하지 않습니다 . 특히, --l.end()null 포인터를 역 참조하기 때문에 정의되지 않은 동작을 나타냅니다. 실제로 반복기 클래스는 자신이 가져온 컬렉션에 대한 참조를 필요로하는 경향이 있습니다.

또한이 반복기는 양방향 반복기 의 요구 사항을 충족하지 않습니다 (이를 순방향 반복기로 표시했지만 해당 요구 사항도 충족하지 않습니다). 특히 다음을 위반합니다.

"그것은 Swappable을 만족하는 유형의 lvalue"; 나는 여기서 약간 녹슬었지만 사용자가 선언 한 소멸자가 암시 적으로 선언 된 이동 생성자와 이동 할당 연산자가 생성되는 것을 방지한다고 확신합니다. 이러한 기능 (예 : 사용 = default) 또는 기능을 제공해야합니다 swap.
접미사 증가 및 감소 연산자는 지원하지 않습니다.

List.h

List::last실제로 올바르게 구현되지 않았습니다. 내가 알아낼 수있는 한, 그것은 실제로 nullptr코드가 아닌 다른 어떤 것으로도 설정되지 않았습니다 . 어떤 경우에는, 이것은해야 하지 일 unique_ptr이미 다른 소유하고 가리키는 것도 있기 때문에 unique_ptr.

하자의 변화에 따라서 lastA와 Node::Node<T>*. 경우 : 우리는 전에 각 멤버 함수 종료 후 해당 다음과 같은 불변이 _size == 0, first==last==nullptr. 그렇지 않으면,

first 목록의 첫 번째 노드를 가리 킵니다.
first->previous == nullptr
도달 가능한 노드 감안할 때 n, n->next널 (null) 또는n->next.get() == n->next->previous
last목록에서 마지막으로 연결할 수있는 노드를 가리 킵니다. last.nextnull입니다.
_size 노드에 도달 할 수 있습니다.

이러한 불변성이 참으로 유지되도록 멤버 함수를 작성해야합니다.

go_to일반적으로 std::next시작 반복자에 적용 하여 달성됩니다 . 목록의 끝을지나 가려고 할 때 행동에 차이가 있습니다. 사용 std::next하면이 경우 정의되지 않은 동작이 발생합니다. 현재 동작을 원한다면 다음과 같이 구현할 수 있습니다.

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

를 사용 unique_ptr하여 메모리를 관리하는 경우 일반적으로 new. 대신 std::make_uniqueC ++ 14 이상을 사용 하는 경우 사용 하십시오 (그리고 make_uniqueC ++ 11로 직접 작성 ). 이를 통해 코드의 예외 안전성을 향상시킬 수 있습니다. 이것을 시도하십시오 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;
}

여기서 노드는 예외 안전 방식으로 생성됩니다. first우리가 그것을 해제하지 않기 때문에 누출의 기회가 없습니다 ( first할당이 실패하거나 Node의 생성자가 던져졌을 때 ( T의 이동 생성자가 던지기 때문에) 코드가 누출 될 것입니다 ). swap및 move던지지 않음 작업 이라고 가정하면 push_front성공하고 새 요소가 처음에 삽입되었거나 할당이 실패하고 push_frontthrow되며 데이터 구조가 변경되지 않았습니다.

에 관해서는 push_back사용하지 않는 경우, last여기있는 이유가 없다 last전혀.

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

다시 말하지만, 새 노드를 구성하는 동안 던지더라도 클래스의 불변성이 유지되는지 확인합니다.

substitute합리적인 기능 이라고 생각하지 않습니다 . 목록의 사용자는 작성 *it = x;해야하며 반복기가 유효한지 여부를 알아야합니다.

에 대한 일반적인 의미 는 반복자가 전달 된 insert직후가 아니라 바로 전에 값을 삽입하는 것입니다. 이것은 insert목록의 어느 위치 에나 삽입 할 수 있으며, 반복자로 전달 insert될 때 의미있는 의미가 있음을 의미 end()합니다.

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

이동 `class Node`및 `struct __iterator`로`class List`

Node::Node<T>코드 내부 를 보는 것은 매우 이상합니다 . A Node는 구현 세부 사항 List이므로 내부에 선언해야합니다 class List. 동일은 간다 __iterator. 예를 들면 :

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() {...};
    ...
};

이 모든 기능이 namespaces 또는 __접두사 ( 피해야 함 ) 를 도입하지 않아도되는 방법과이를 통해 명시 적으로 작성해야하는 횟수를 줄이는 방법에 주목 하십시오 <T>. 물론, 이제 모든 것이 내부 List.h에서 선언되어야 하지만, 나는 그것을 단점으로 보지 않습니다.

스마트 포인터가있는 이중 연결 목록 : 삽입 방법 문제

답변

Node.h

Iterator.h

List.h

이동 class Node및 struct __iterator로class List

이동 `class Node`및 `struct __iterator`로`class List`