C++ - 将原始指针分配给链表中的 unique_ptr 节点

Question

我想弄清楚如何在删除链表中的节点后将尾部原始指针更新为新尾部。 (是作业)

我已经定义了头部和尾部

    std::unique_ptr<Node> head ;
    Node* tail ;

在我从后面删除节点的函数中，我有以下实现。

int Deque::remove_back(){
if (empty()) {throw std::runtime_error(std::string("Empty"));};

std::unique_ptr<Node> old;

Node* p = head.get();

int return_value = tail->val;

while (p->next != tail)
{p = p->next)}

old = move(tail);
tail = p;

return return_value;
}

所以 tail 是一个 Node 类型的原始指针。P 是 Node 类型的原始指针。

Head 是 Node 类型的唯一指针。

我正在设置 p = head.get()

现在p指向头部

p = p->下一步应该迭代我的节点。

问题是 p->next != tail

p->next 是指向 p 之后的下一个节点的指针。

我正在尝试将指向节点的指针设置为等于类型节点(尾)的原始指针。

它告诉我我不能这样做。

我相信这是由于 p->next 没有变成拥有指针而不是我声明的观察指针。

错误:

Deque.cpp|68|error: no match for 'operator!=' (operand types are 'std::unique_ptr<Node>' and 'Node*')|

Deque.cpp|69|error: cannot convert 'std::unique_ptr<Node>' to 'Node*' in assignment|

Deque.cpp|71|error: no match for 'operator=' (operand types are 'std::unique_ptr<Node>' and 'std::remove_reference<Node*&>::type {aka Node*}')|

Answer 1

错误消息暗示 Node::next是 std::unique_ptr<Node> .您无法比较/分配 std::unique_ptr直接指向原始指针。您需要使用 std::unique_ptr::get()方法代替:

while (p->next.get() != tail) {
    p = p->next.get();
}

此外，当列表中只有 1 个节点 ( head == tail) 时，您的循环没有被考虑在内。 p->next将是 nullptr在第二次迭代和崩溃。由于您将删除列表中的最后一个节点，因此您需要重置 head至 nullptr .无论哪种方式，分配 p 时作为新的tail , 您需要重新设置 p->next至 nullptr因此它将不再指向旧节点。

试试这个:

int Deque::remove_back(){
    if (empty()) {
        throw std::runtime_error("Empty");
    }

    int return_value = tail->val;

    if (!head->next) {
        head = nullptr; // or: head.reset();
        tail = nullptr;
    }
    else {
        Node* p = head.get();
        Node *prev = p;
        while (p->next->next) {
            p = p->next.get();
            prev = p;
        }
        tail = prev;
        tail->next = nullptr; // or: tail->next.reset();
    }

    return return_value;
}

也就是说，使用 std::unique_ptr 可能会很棘手在链表实现中。如果你想自动销毁节点，你可以只使用原始指针并将列表包装在一个类中，该类在自身被销毁时销毁节点，然后 remove_back()可以销毁被移除的节点。

STL 已经有这样的类可用:std::list (双链接)和 std::forward_list (单链接)。您应该使用它们而不是手动列表实现。