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

所以尾巴是类型节点的原始指针。 P是Node类型的原始指针。

Head是Node类型的唯一指针。

我设置P = head.get（）

所以现在p指向头

P = P->接下来应该被遍历了我的节点。

的问题是，p->next != tail

对 - >下是一个指向下列任何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（单链接）。您应该使用它们而不是手动列表实现。

Answer 2

当只有一个元素时，你的函数有问题。你需要一个条件（使用代码复制）或使其稍微复杂一点：

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

    Node *newtail = nullptr; 
    std::unique_ptr<Node> *curr = &head; 
    while(curr->get() != tail) { 
     newtail = curr->get(); 
     curr = &(*curr)->next; 
    } 

    tail = newtail; 
    std::unique_ptr<Node> tmp = std::move(*curr); 

    return tmp->val; 
}