I'm trying to implement the linked list by indirect pointer, which introduced on the TED Talk.

I refer to felipec's implementation on github and made an version by raw pointer, this is the github link.

This is part of the full code, _find is a function that can find the indirect pointer of target node, which means *indirect == target node :

//...
struct Node {
    int data;
    Node *next;
    Node()
        : data(0), next(nullptr) {}
    Node(int _d, Node *_next = nullptr)
        : data(_d), next(_next) {}
    ~Node() { puts("~Node"); }
};
//...

List::Node **List::_find(const int target)
{
    Node **indirect = &head;
    while (*indirect && (*indirect)->data != target)
        indirect = &(*indirect)->next;

    return indirect;
}

I wanna make a smart pointer version of this. I use std::unique_ptr for the next pointer in Node, and std::shared_ptr for the head pointer in List.

But in the part Node **indirect = &head, I have no idea for how to design it by smart pointer, I have wrote this:

//...
struct Node {
    int data;
    std::unique_ptr<Node> next;
    Node()
        : data(0), next(nullptr) {}
    Node(int _d, std::unique_ptr<Node> &_next)
        : data(_d), next(std::move(_next)) {}
    ~Node() { puts("~Node"); }
};
//...

List::Node **List::_find(const int target)
{
    Node **indirect = &(head.get());
    while (*indirect && (*indirect)->data != target)
        indirect = &(*indirect)->next;

    return indirect;
}

Apparently, Node **indirect = &(head.get()) is not an good idea since the get function return a rvalue that it point to. But what I need is the pointer object that point to the target, the code even can't be compiled.

Thus, there is two question

1. How could I get the address of the target object in smart pointer?

2. Did I use the smart pointer in correct way? Should I change shared_ptr to unique_ptr, or just not use smart pointer for it?

Any additional supplements and recommendations are appreciated.

CodePudding user response：

How could I get the address of the target object in smart pointer?

I think you mean "the address of the pointer in the smart pointer", because the address of the target object is just what you get with .get(). std::unique_ptr does not offer any interface to access it's pointer member directly, so it is impossible.

Did I use the smart pointer in correct way? Should I change shared_ptr to unique_ptr, or just not use smart pointer for it?

Using std::unique_ptr is the correct thing to do. You don't need shared_ptr because there are never two owners of any given node.

In your first code indirect is a pointer to a raw pointer in the Node/List structure. Since you changed these to smart pointers, indirect should also become a pointer to a smart pointer:

std::unique_ptr<List::Node> *List::_find(const int target)
{
    std::unique_ptr<Node> *indirect = &head;
    while (*indirect && (*indirect)->data != target)
        indirect = &(*indirect)->next;

    return indirect;
}

Although it would be more idiomatic to return a reference instead:

std::unique_ptr<List::Node> &List::_find(const int target)
{
    std::unique_ptr<Node> *indirect = &head;
    while (*indirect && (*indirect)->data != target)
        indirect = &(*indirect)->next;

    return *indirect;
}

(I am assuming that this is a private helper function and not actually the interface of the List class, in which case there would be problems with either implementation.)