2

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?

user3100212
  • 101
  • 1
  • 5
  • 4
    `node_unique u2{2, std::move(u1)};` would be sufficient. – Jarod42 Apr 27 '22 at 15:08
  • 1
    And directly: `node_unique u3{3, std::make_unique(2, std::make_unique(1, nullptr))};`. – Jarod42 Apr 27 '22 at 15:10
  • 3
    FYI, using smart pointers in linked lists is generally not a good idea. For one thing, the nodes will destroy themselves recursively, and a recursive destruction can lead to a stack overflow at runtime for a long list. Iterative loops are better for linked lists. Not that you can't use an iterative loop to destroy nodes with smart pointers, but it will be a little more work, and you basically end up losing the benefit of using smart pointers. – Remy Lebeau Apr 27 '22 at 15:49
  • 1
    @RemyLebeau `nodes with smart pointers, but it will be a little more work` Only marginally. But it's indeed important to not use the implicit destructor. `and you basically end up losing the benefit of using smart pointers.` Not all of the benefits. – eerorika Apr 27 '22 at 16:53
  • @eerorika "*Not all of the benefits*" - pretty much, yes. The only reason to use a smart pointer is automatic destruction, but if you have to free the nodes manually anyway and can't use automatic destruction, there is really no reason to use smart pointers. – Remy Lebeau Apr 27 '22 at 17:29
  • 1
    @RemyLebeau Other benefits that aren't lost: Implicit move and assignment are correct and don't need to be re-implemented. Easier to implement copy constructor and assignment exception safely. – eerorika Apr 27 '22 at 18:24
  • 2
    I'm on the side of raw pointers in data structures where it makes sense, and I think they make a lot more sense in something like a linked list. The ownership that's intended just doesn't play well; like the hoops you have to jump through to ensure a node doesn't nuke itself and take the whole list with it. This debate is also a bit moot since you should just use `std::forward_list` or `std::list` anyway. – sweenish Apr 27 '22 at 18:30

1 Answers1

5

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.

user3100212
  • 101
  • 1
  • 5
eerorika
  • 232,697
  • 12
  • 197
  • 326