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.get()

так теперь р указывает на голову

р = p-> следующий должен быть итерация вниз мои узлы.

Проблема заключается в том, что p->next != tail

p-> следующий указатель на следующий узел следующего независимо от р.

Я пытаюсь установить указатель на узел равным необработанному указателю узла типа (хвост).

Его рассказывают, что я не могу этого сделать.

Я считаю, что это связано с тем, что p-> не изменилось вместо указателя-владельца вместо наблюдающего, который я объявил.

Ошибки:

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

Кроме того, ваш цикл не принимая во внимание, когда список содержит только один узел в нем (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; 
}