使用智能指针的通用双向链表

Question

我正在尝试使用智能指针实现通用双链表。目前我正在尝试编写 push_back 函数，但出现此错误：

1>------ Build started: Project: LinkedList, Configuration: Debug Win32 ------
1>main.cpp
1>c:\dev\linkedlist\linkedlist\doublelinkedlist.h(155): error C2679: binary '=': no operator found which takes a right-hand operand of type 'DoubleLinkedList<int>::Node *' (or there is no acceptable conversion)
1>c:\program files (x86)\microsoft visual studio17\community\vc\tools\msvc.14.26428\include\memory(2309): note: could be 'std::unique_ptr<DoubleLinkedList<int>::Node,std::default_delete<_Ty>> &std::unique_ptr<_Ty,std::default_delete<_Ty>>::operator =(const std::unique_ptr<_Ty,std::default_delete<_Ty>> &)'
1>        with
1>        [
1>            _Ty=DoubleLinkedList<int>::Node
1>        ]
1>c:\program files (x86)\microsoft visual studio17\community\vc\tools\msvc.14.26428\include\memory(2247): note: or       'std::unique_ptr<DoubleLinkedList<int>::Node,std::default_delete<_Ty>> &std::unique_ptr<_Ty,std::default_delete<_Ty>>::operator =(std::unique_ptr<_Ty,std::default_delete<_Ty>> &&) noexcept'
1>        with
1>        [
1>            _Ty=DoubleLinkedList<int>::Node
1>        ]
1>c:\program files (x86)\microsoft visual studio17\community\vc\tools\msvc.14.26428\include\memory(2173): note: or       'std::unique_ptr<DoubleLinkedList<int>::Node,std::default_delete<_Ty>> &std::unique_ptr<_Ty,std::default_delete<_Ty>>::operator =(std::nullptr_t) noexcept'
1>        with
1>        [
1>            _Ty=DoubleLinkedList<int>::Node
1>        ]
1>c:\dev\linkedlist\linkedlist\doublelinkedlist.h(155): note: while trying to match the argument list '(std::unique_ptr<DoubleLinkedList<int>::Node,std::default_delete<_Ty>>, DoubleLinkedList<int>::Node *)'
1>        with
1>        [
1>            _Ty=DoubleLinkedList<int>::Node
1>        ]
1>c:\dev\linkedlist\linkedlist\doublelinkedlist.h(153): note: while compiling class template member function 'void DoubleLinkedList<int>::push_back(T &&)'
1>        with
1>        [
1>            T=int
1>        ]
1>c:\dev\linkedlist\linkedlist\main.cpp(97): note: see reference to function template instantiation 'void DoubleLinkedList<int>::push_back(T &&)' being compiled
1>        with
1>        [
1>            T=int
1>        ]
1>c:\dev\linkedlist\linkedlist\main.cpp(96): note: see reference to class template instantiation 'DoubleLinkedList<int>' being compiled
1>c:\dev\linkedlist\linkedlist\doublelinkedlist.h(159): error C2679: binary '=': no operator found which takes a right-hand operand of type 'DoubleLinkedList<int>::Node *' (or there is no acceptable conversion)
1>c:\program files (x86)\microsoft visual studio17\community\vc\tools\msvc.14.26428\include\memory(2309): note: could be 'std::unique_ptr<DoubleLinkedList<int>::Node,std::default_delete<_Ty>> &std::unique_ptr<_Ty,std::default_delete<_Ty>>::operator =(const std::unique_ptr<_Ty,std::default_delete<_Ty>> &)'
1>        with
1>        [
1>            _Ty=DoubleLinkedList<int>::Node
1>        ]
1>c:\program files (x86)\microsoft visual studio17\community\vc\tools\msvc.14.26428\include\memory(2247): note: or       'std::unique_ptr<DoubleLinkedList<int>::Node,std::default_delete<_Ty>> &std::unique_ptr<_Ty,std::default_delete<_Ty>>::operator =(std::unique_ptr<_Ty,std::default_delete<_Ty>> &&) noexcept'
1>        with
1>        [
1>            _Ty=DoubleLinkedList<int>::Node
1>        ]
1>c:\program files (x86)\microsoft visual studio17\community\vc\tools\msvc.14.26428\include\memory(2173): note: or       'std::unique_ptr<DoubleLinkedList<int>::Node,std::default_delete<_Ty>> &std::unique_ptr<_Ty,std::default_delete<_Ty>>::operator =(std::nullptr_t) noexcept'
1>        with
1>        [
1>            _Ty=DoubleLinkedList<int>::Node
1>        ]
1>c:\dev\linkedlist\linkedlist\doublelinkedlist.h(159): note: while trying to match the argument list '(std::unique_ptr<DoubleLinkedList<int>::Node,std::default_delete<_Ty>>, DoubleLinkedList<int>::Node *)'
1>        with
1>        [
1>            _Ty=DoubleLinkedList<int>::Node
1>        ]
1>c:\dev\linkedlist\linkedlist\doublelinkedlist.h(163): error C2065: 'newnode': undeclared identifier
1>c:\dev\linkedlist\linkedlist\doublelinkedlist.h(164): error C2679: binary '=': no operator found which takes a right-hand operand of type 'DoubleLinkedList<int>::Node *' (or there is no acceptable conversion)
1>c:\program files (x86)\microsoft visual studio17\community\vc\tools\msvc.14.26428\include\memory(2309): note: could be 'std::unique_ptr<DoubleLinkedList<int>::Node,std::default_delete<_Ty>> &std::unique_ptr<_Ty,std::default_delete<_Ty>>::operator =(const std::unique_ptr<_Ty,std::default_delete<_Ty>> &)'
1>        with
1>        [
1>            _Ty=DoubleLinkedList<int>::Node
1>        ]
1>c:\program files (x86)\microsoft visual studio17\community\vc\tools\msvc.14.26428\include\memory(2247): note: or       'std::unique_ptr<DoubleLinkedList<int>::Node,std::default_delete<_Ty>> &std::unique_ptr<_Ty,std::default_delete<_Ty>>::operator =(std::unique_ptr<_Ty,std::default_delete<_Ty>> &&) noexcept'
1>        with
1>        [
1>            _Ty=DoubleLinkedList<int>::Node
1>        ]
1>c:\program files (x86)\microsoft visual studio17\community\vc\tools\msvc.14.26428\include\memory(2173): note: or       'std::unique_ptr<DoubleLinkedList<int>::Node,std::default_delete<_Ty>> &std::unique_ptr<_Ty,std::default_delete<_Ty>>::operator =(std::nullptr_t) noexcept'
1>        with
1>        [
1>            _Ty=DoubleLinkedList<int>::Node
1>        ]
1>c:\dev\linkedlist\linkedlist\doublelinkedlist.h(164): note: while trying to match the argument list '(std::unique_ptr<DoubleLinkedList<int>::Node,std::default_delete<_Ty>>, DoubleLinkedList<int>::Node *)'
1>        with
1>        [
1>            _Ty=DoubleLinkedList<int>::Node
1>        ]
1>Done building project "LinkedList.vcxproj" -- FAILED.
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========

这是我要实现的功能：

template <class T>
void DoubleLinkedList<T>::push_back(T &&thedata) {
    std::unique_ptr<Node> newNode = std::make_unique<Node>(std::move(thedata));
    newNode->previous = std::move(tail.get());

    if (!head) {
        head = std::move(newNode);
        tail = head.get();
    }

    else {
        tail->next = std::move(newnode);
        tail = tail->next.get();
    }
}

错误发生在 newNode->previous = std::move(tail.get()); 和 tail = tail->next.get();。我不知道如何解决此问题以确保我正在为双链表创建正确的链接。

这是我初始化尾部和头部的 class 的样子：

class DoubleLinkedList {
private:

    struct Node {
        T data;
        std::unique_ptr<Node> next = nullptr;
        std::unique_ptr<Node> previous = nullptr;

    };
    std::unique_ptr<Node> head = nullptr;
    std::unique_ptr<Node> tail = nullptr;
};

这是我尝试使用 push_back 函数时的情形：

#include <iostream>
#include <iterator>
#include <memory>
#include <utility>
#include <stdexcept>
#include <iosfwd>
#include <stdexcept>
#include <ostream>
#include "DoubleLinkedList.h"

int main(int argc, const char * argv[]) {


     ///////////////////////////////////////////////////////////////////////
     ///////////////////////////// Double Linked List //////////////////////
     ///////////////////////////////////////////////////////////////////////
     DoubleLinkedList<int> obj;
     obj.push_back(2);
     obj.push_back(4);
     obj.push_back(6);
     obj.push_back(8);
     obj.push_back(10);
     std::cout<<"\n--------------------------------------------------\n";
     std::cout<<"---------------displaying all nodes---------------";
     std::cout<<"\n--------------------------------------------------\n";
     std::cout << obj << "\n";


    std::cin.get();
}

Answer 1

正如 Jarod42 重申的那样，使用 shared_ptr 并使结构节点可访问。试试这个：

template <class T>
struct Node {
    Node(T val):data(val){}
    T data;
    std::shared_ptr<Node> next = nullptr;
    std::weak_ptr<Node> previous ; //weak_ptr to avoid cyclic reference

};

template <class T>
class DoubleLinkedList {
public:
    void push_back(T thedata);

    std::shared_ptr<Node<T>> head = nullptr;
    std::shared_ptr<Node<T>> tail = nullptr;
};

template <class T>
std::ostream& operator<<(std::ostream& os, DoubleLinkedList<T>& obj) {
    std::shared_ptr<Node<T>> node = obj.head;
    while (node!= nullptr) {
        os << node->data << std::endl;
        node = node->next;
    }
    return os;
}

template <class T>
void DoubleLinkedList<T>::push_back(T thedata) {
    std::shared_ptr<Node<T>> newNode = std::make_shared<Node<T>>(thedata);
    newNode->previous = tail;

    if (!head) {
        head = newNode;
        tail = head;
    }

    else {
        tail->next = newNode;
        tail = tail->next;
    }
}

int main()
{
    DoubleLinkedList<int> obj;
    obj.push_back(2);
    obj.push_back(4);
    obj.push_back(6);
    obj.push_back(8);
    obj.push_back(10);
    std::cout << "\n--------------------------------------------------\n";
    std::cout << "---------------displaying all nodes---------------";
    std::cout << "\n--------------------------------------------------\n";
    std::cout << obj << "\n";

    std::cin.get();
    return 0;
}

Answer 2

由于循环，双向链表不是智能指针的理想选择（至少对于内部 front/back 链接而言）。节点不拥有彼此，并且因为没有所有权或层次关系，所以无法进行引用计数或类似的递减，以便在不再需要列表时可以回收内存。

但是，您可以想象对一个方向的链接使用拥有指针（唯一的或共享的），而对另一个方向的链接使用 weak_ptrs 来避免这些问题。这将建立一个明确的 parent/child 关系并允许内存管理正常工作。

话虽如此，列表的客户当然可能希望使用智能指针来保存他们插入到列表中的项目。我只是不会在列表内部使用它们。

使用智能指针的通用双向链表

Generic double linkled list using smart pointers

c++

smart-pointers

vector