0
\$\begingroup\$

As an example code I've given here, I have the feeling the use of std::shared_ptr is wrong and should be replaced using a std::unique_ptr because there's no real shared ownership semantics, besides of temporary needs.

How could that code be refactored correctly, e.g. using std::unique_ptr instead?

#include <memory>
#include <iostream>

template<typename T>
class LinkedList {
private:
    template<typename U = T>
    struct Node {
        U data;
        std::shared_ptr<Node<U>> next;
    };
    std::shared_ptr<Node<T>> head;
public:
    Node<T> const* insert(int position, T data) {
        if(position < 0) {
            throw std::invalid_argument("Parameter 'position' must be greater or equal to 0.");
        }

        std::shared_ptr<Node<T>> node = head;
        int i = 0;
        for(;node && node->next && i < position; node = node->next, ++i);

        if(i != position) { // position is a value beyond the list positions
            throw std::out_of_range("Parameter 'position' is out of range of the linked list.");
        }

        std::shared_ptr<Node<T>> newNode = std::make_shared<Node<T>>();
        newNode->data = data;
        newNode->next = node ? node->next : nullptr;
        if(node) {
            node->next = newNode;
        }
        else {
            head = newNode;
        }
        return newNode.get();
   }
   // Other linked list operations ...
};

int main() {
    LinkedList<int> ll;
    auto newNode = ll.insert(0,5);
    std::cout << newNode->data << std::endl;
}

I thought the move constructor of std::unique_ptr should cover all assignments of std::unique_ptr<Node<T>> variables well, but obviously it doesn't out of the box.


See the working code to play with here please.


I well know this question is kind of borderline here, since I'm asking how to rewrite that code properly regarding the constraints I'm setting up.

Though I don't get in which direction I have to go with that, as all my attempts are failing so far. I think there must be an appropriate solution just using a std::unique_ptr.

\$\endgroup\$
  • \$\begingroup\$ Regarding the DV. Yeehaw, I'm breaking the rules :-P. Feel free to edit my questions wording to get it on-topic please. \$\endgroup\$ – πάντα ῥεῖ Jan 20 '17 at 23:19
2
\$\begingroup\$

Yes, you can and should use unique_ptr. Several places will need to change of course:

Iterating through the nodes can use raw pointers:

    auto node = head.get();
    int i = 0;
    for(;node && node->next && i < position; node = node->next.get(), ++i);

    if(i != position) { // position is a value beyond the list positions
        throw std::out_of_range("Parameter 'position' is out of range of the linked list.");
    }

Use unique_ptr instead of shared_ptr:

    auto newNode = std::make_unique<Node<T>>();
    newNode->data = data;
    if(node) {

unique_ptr can't be copied, only moved:

        newNode->next = std::move(node->next);
        node->next = std::move(newNode);
        return node->next.get();
    }
    else {
        head = std::move(newNode);
        return head.get();
    }

Note that at the end, newNode has been moved from and is an empty state. You can no longer return newNode.get(). What was in newNode either ended up in some node's next or head by the end of the function.

\$\endgroup\$
  • \$\begingroup\$ That looks promising, I just avoided to use get() to refer to the raw pointers currently. \$\endgroup\$ – πάντα ῥεῖ Jan 20 '17 at 22:29
  • \$\begingroup\$ @πάνταῥεῖ raw pointers shouldn't be avoided as long as they don't own anything. Only unique_ptr and shared_ptr should own memory, but raw pointers can safely be used to access them. \$\endgroup\$ – David Jan 20 '17 at 22:31
  • \$\begingroup\$ std::weak_ptr's to clarify semantics may be? \$\endgroup\$ – πάντα ῥεῖ Jan 20 '17 at 22:32
  • \$\begingroup\$ @πάνταῥεῖ weak_ptr only relates to shared_ptr. The sort-of-equivalent of weak_ptr to unique_ptr is a raw pointer. \$\endgroup\$ – David Jan 20 '17 at 22:33
  • \$\begingroup\$ Well, I see. THX for your answer. \$\endgroup\$ – πάντα ῥεῖ Jan 20 '17 at 22:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.