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

Question

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

a tail in a single-linked list is only useful for fast inserts at the end of the list, but is otherwise useless since you can't use it for fast removals at the end of the list. — Remy Lebeau
– Remy Lebeau, Commented Oct 19, 2016 at 22:19

Remy Lebeau · Accepted Answer · 2016-10-19 22:23:11Z

4

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.

edited Oct 19, 2016 at 22:23

answered Oct 19, 2016 at 21:29

Remy Lebeau

610k36 gold badges516 silver badges875 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

TigerCode Over a year ago

Its for homework and as such there's a lot of restrictions to make me consider the why's and hows of implementation for using smart pointers.

Slava Over a year ago

"you are not resetting p->next to nullptr" It will be fixed when OP will realize that he cannot assign raw pointer to std::unique_ptr. I think it makes sense to use std::unique_ptr if used properly.

TigerCode Over a year ago

std::unique_ptr<Node> old; and Node* Tail can't be moved into one another. If I get() tail then it should work.

Remy Lebeau Over a year ago

@Slava: a std::unique_ptr can be reset to nullptr using the reset() method or operator=. However, a proper use of smart pointers in a linked-list implementation would be to use std::shared_ptr instead of std::unique_ptr for the individual nodes, and then make tail and p be std::weak_ptr instead of raw pointers.

Slava Over a year ago

@RemyLebeau it will work just fine with std::unique_ptr and raw pointer or experimental observer_ptr, just logic need to be fixed

|

Slava · Accepted Answer · 2016-10-19 22:11:00Z

1

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

edited Oct 19, 2016 at 22:11

answered Oct 19, 2016 at 22:00

Slava

44.5k2 gold badges54 silver badges100 bronze badges

1 Comment

Remy Lebeau Over a year ago

I like your loop better than mine.

Collectives™ on Stack Overflow

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

2 Answers 2

6 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

6 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related