双向链接列表std :: unique_ptr类在删除节点时无法按预期工作

固体

受到CppCon2016中Herb Sutter谈话的启发,可以在此链接中找到。
我决定使用智能指针实现视频中所示的双向链接列表。
以下实现几乎与remove()方法中的一行代码无关。
我调试了此代码,并且移除后,上一个节点未更新为null(应该是头节点)。
好像智能指针之间的所有权转移是错误的。以下是头文件和测试main()的代码:

LinkedList.h

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

#include <iostream>
#include <memory>
#include <initializer_list>

namespace DLL {
    template <typename T> class LinkedList{
        private:
            struct ListNode{
                std::unique_ptr<ListNode> next; //2 uniq_ptr can't point to one another.
                ListNode* prev = nullptr; //weakptr needs to be cast back to a shared_ptr to check its state.
                T data{}; //Initialize empty;

            ListNode(const T& element){
                this->data = element;
            }
        };
    public:
        std::unique_ptr<ListNode> head;
        ListNode* tail = nullptr;

        LinkedList(){}
        ~LinkedList(){}

        void append(const T& element){
            ListNode* curr = nullptr;
            if (head.get() == nullptr){ //If list is empty.
                head = std::make_unique<ListNode>(element);
            }
            else if(head.get() -> next.get() == nullptr){ //If list has one element
                 head.get() -> next = std::make_unique<ListNode>(element);
                 curr = head.get() -> next.get(); //Sets raw pointer to the first element.
                 curr -> prev = head.get();
                 tail = curr;
            }
            else{
                tail -> next = std::make_unique<ListNode>(element);
                curr = tail -> next.get(); //Sets raw pointer to the last element.
                curr -> prev = tail;
                tail = curr;// The new last element is the tail.
            }
        }

        int remove(const T& element){
            ListNode* curr = nullptr;
            if (head.get() == nullptr){ //If list is empty.
                return -1; //Error: Can't remove from empty list.
            }
            //List has one or more elements.
            curr = head.get();
            while(curr != nullptr){
                if(curr -> data == element){ //Found element
                    if(curr -> prev == nullptr){ //is head
                    //head.reset(head.get()->next.get()); Doesn't work
                    //Line below doesn't work too
                    head = std::move(curr->next); //Head now points to the next element
                    //New head's previous element doesn't point to nothing, as it should.
                    }
                    else if(curr -> next.get() == nullptr){ //is tail
                        tail = curr -> prev; //Reference the previous element
                        tail -> next.release(); //Release the old tail element
                        if(head.get() == tail){
                            tail = nullptr; //tail and head should not be the same.
                        } //List contains one element
                    }
                    else{//is intermediate
                        //The next node should point to the previous one
                        curr -> next -> prev = curr -> prev;
                        curr -> prev -> next = std::move(curr -> next);
                        //The prev node now points to the next one of current.
                    }
                    return 1; //Element found in list
                }
                curr = curr -> next.get(); //Traverse the next element
            }
            return 0; //Element not found in list
        }

        void print() {
            ListNode* curr = head.get(); //Start from the start of the list.
            std::cout << "[ ";
            while (curr != nullptr) {
                std::cout << curr -> data << " ";
                curr = curr -> next.get();
            }
            std::cout << "]" << std::endl;
        }
    };
}

#endif

main.cpp

int main() { //Temporary Test Main will be split from the implementation file in the future
    DLL::LinkedList <int> list; //Empty list
    list.append(1);
    list.append(4);
    list.append(5);
    list.append(6);
    list.print();
    list.remove(5);
    list.remove(1); //When 1 is removed the 4 doesn't properly update as head, meaning the previous pointer of 4 is not null
    list.remove(4);
    list.remove(6);
    list.print();
    retunn 0;
}

对于此类问题,我感到很抱歉,我进行了很多搜索,但找不到类似的内容。我已经调试了好几天,但无法解决所有权问题。我尝试包含最少的代码,以重现该错误,如果标头是长代码段,对不起。

我用g ++:g++ -std=c++14 main.cpp -o out和VS2015编译器编译。make_unique呼叫需要C ++ 14标志

瓦拉克

在您要检查迭代器的上一个指针为null的部分(基本上检查头)中,您具有以下行:

head = std::move(curr->next);

这会将标头指针移动为元素的下一个指针。但是,没有地方可以将新的头部指针的先前指针更新为null。因此该代码应为:

if(curr -> data == element){ //Found element
    if(curr -> prev == nullptr){ //is head
        head = std::move(curr->next); //Head now points to the next element
        if (head)
            head->prev = nullptr;
        else
            tail = nullptr;
    }
}

由于您正在使用std::move的对象将成为新的头部指针(这是正确的),因此基本上可以使该节点中包含的数据保持相同。在这种情况下,您需要明确-std::unique_ptr包装器对其所拥有的对象的基础实现一无所知,因此prev在这种情况下,它不知道如何更新指针。

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章

删除双向链接列表中的功能故障

Ocaml-从双向链接列表中删除中间节点

Java-从双向链接列表中删除节点

如何在Java中的双向链接列表中附加节点?

从C ++中的双向链接列表中删除公网

反向遍历双向链接列表时遇到问题

在C中的双向链接列表中删除头节点时出现问题

反向链接列表无法按预期工作

将std :: unique_ptr传递给类时出错

双向链接节点矩阵

为什么我的双向链接列表会删除以前的链接?

需要帮助:无法从双向链接列表中删除字符串:C

错误C2248:'std :: unique_ptr <_Ty> :: unique_ptr':无法访问在类'std :: unique_ptr <_Ty>'中声明的私有成员

如何在双向链接列表的第一个节点之前插入新节点?

Java排序的双向链接列表:如何在正确的位置快速插入新节点?

使用C在双向链接列表中的第N个位置插入一个节点

奇怪的错误:当未真正创建指针时,使用删除的函数'std :: unique_ptr <_Tp,_Dp> :: unique_ptr

Java中LinkedList和arrayList的双向链接列表的内部工作有什么区别

删除双向链接列表中的第一个匹配项

如何删除双向链接列表中与某个值匹配的所有项目?

双向链接列表不再双向链接

打印双向链接列表

侵入式,圆形,无分支,双向链接列表-如何使用该列表来标识节点成员字段?

无法使用带有std :: move的自定义删除器插入std :: unique_ptr

如何将类的静态方法作为 std::unique_ptr 的删除器传递?

C ++将删除的函数std :: unique_ptr与基类一起使用

声明包含std :: unique_ptr的结构的std :: vector类时出错

无法通过Diamond中的std :: unique_ptr访问最基类的受保护成员变量

带有lambda自定义删除程序的std :: unique_ptr无法编译