CODEWITHSUNDEEP
c++pointerstypeslinked-listnodes
TigerCode
TigerCode

Reputation: 355

C++ - Assignment of raw pointers to unique_ptr nodes in a Linked List

I'm trying to figure out how to update my tail raw pointer to a new tail after removing a node in my linked list. (is homework)

I've defined the head and tail as

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

and in my function for removing a node from the back I have the following implementation. 

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

So tail is a raw pointer of type Node. P is a raw pointer of type Node.

Head is a unique pointer of type Node.

I'm setting p = head.get()

so now p points to the head

p = p->next should be iterating down my nodes.

The problem is that p->next != tail

p->next is a pointer to the next node following whatever p is.

I'm trying to set a pointer to a node to be equal to a raw pointer of type node (tail).

Its telling me I can't do this.

I believe its due to p->next not changing into an owning pointer instead of the observing one I declared it to be.

Errors: 

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*}')|

Upvotes: 1

Views: 1678

Answers (2)

Remy Lebeau
Remy Lebeau

Reputation: 595971

The error messages imply that Node::next is a std::unique_ptr<Node>. You cannot compare/assign a std::unique_ptr directly to a raw pointer. You need to use the std::unique_ptr::get() method instead:

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

Also, your loop is not taking into account when the list has only 1 node in it (head == tail). p->next will be nullptr on the second iteration and crash. And since you would be removing the last node in the list, you would need to reset head to nullptr. Either way, when assigning p as the new tail, you need to reset p->next to nullptr so it will no longer be pointing at the old node.

Try this:

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

That being said, it can be tricky using std::unique_ptr in a linked-list implementation. If you want automatic destruction of nodes, you could just use raw pointers and wrap the list inside of a class that destroys the nodes when itself is destroyed, and then remove_back() can destroy the node being removed.

The STL already has such classes available: std::list (double linked) and std::forward_list (single linked). You should be using them instead of a manual list implementation.

Upvotes: 4

Slava
Slava

Reputation: 44248

You function has issue when there is only one element. You need a condition (with code duplicate) or make it little bit more complicated:

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

Upvotes: 1

Related Questions