'Basic forward list using unique_ptrs

As an exercise in learning C++, I want to build my own forward list using raw pointers and using unique_ptrs. Using raw pointers, I have:

struct node_raw {
    node_raw(int data_, node_raw *next_) : data(data_), next(next_) {}
    int data;
    node_raw *next;
};

Then I can write this

int main() {
    node_raw r1{1, nullptr};
    node_raw r2{2, &r1};
    node_raw r3{3, &r2};
}

to get a forward list: r3 -> r2 -> r1.

Now I want to do the same using unique_ptrs.

struct node_unique {
    node_unique(int data_, std::unique_ptr<node_unique> next_) 
        : data(data_), next(std::move(next_)) {}
    int data;
    std::unique_ptr<node_unique> next;
};

This is what I have so far for client code:

int main() {
    node_unique u1{1, nullptr};
    node_unique u2{2, std::make_unique<node_unique>(std::move(u1))};
    node_unique u3{3, std::make_unique<node_unique>(std::move(u2))};
}

This gives u3.next->data = 2, so it seems to work. But is it right? Why do I need std::move twice to make a new node? Is it now invalid to query u1.data because it has been moved from? Basically, what is the canonical way to implement a minimal forward list using unique_ptrs?



Solution 1:[1]

Why do I need std::move twice to make a new node?

You cannot copy node_unique because it has implicitly deleted copy constructor because of std::unique_ptr member.

Is it now invalid to query u1.data because it has been moved from?

No. The implicitly generated move constructor will copy the member. It's not invalid to read the int member that was copied from.

But is it right?

There isn't a huge problem1 with the node class itself, but the way that you're using it may potentially be misleading. u1 and u2 aren't part of the list whose root is u3. The list nodes are shallow copies of the moved-from u1 and u2.

You don't necessarily need the variables; since the list elements will be dynamic, you can create them directly:

node_unique root (
    3,
    std::make_unique<node_unique>(
        2,
        std::make_unique<node_unique>(
            1,
            nullptr
        )
    )
);

Basically, what is the canonical way to implement a minimal forward list using unique_ptrs?

"Minimal" is relative to what your requirements are. You could make it more minimal by removing the constructor to make the node an aggregate.

I wouldn't say that there is a "canonical" way to implement a forward list, but it would be expected to meet the concept of a Container. That would however be less minimal.


1 Except for the fact that destructor has linear recursion depth which will cause stack overflow with moderately sized lists as pointed out by Remy Lebeau.

You should implement a custom destructor that destroys the nodes iteratively. This requires a bit of thought to prevent the smart pointer destructors from delving into recursion.

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 user3100212