6
\$\begingroup\$

As an exercise to familiarise myself with smart pointers, I implemented a template linked list class in C++, closely following the very good tutorial at: https://solarianprogrammer.com/2019/02/22/cpp-17-implementing-singly-linked-list-smart-pointers/, which I duly acknowledge and from which I borrow freely.

The code seems to be working as expected, so far, and I feel that I have a better understanding of how to use unique_ptrs for ownership. However, I have taken a shortcut in my code for popping an element from the front of the list, which is also used in the clean() member function (see code below). In particular, when popping an element or iteratively deleting nodes, I have noticed that some people use an intermediary unique pointer to take ownership of the node to be deleted, as in the following:

/**
 * Pop the top element off the list
 * 
 */
template <typename T>
void LinkedList<T>::pop() {
    if (ptrHead == nullptr) {
        return;
    }

    // can we safely avoid the ptrDetached intermediary?
    std::unique_ptr<Node> ptrDetached = std::move(ptrHead);
    ptrHead = std::move(ptrDetached->ptrNext);
}

However, it appears to me that the allocation of a ptrDetached is unnecessary, and one can instead use:

template <typename T>
void LinkedList<T>::pop() {
    if (ptrHead == nullptr) {
        return;
    }

    ptrHead = std::move(ptrHead->ptrNext);
}

This second version of the code seems to be working [Linux, g++ (Debian 9.2.1-22) 9.2.1 20200104], but I am concerned that I might be making some naive assumptions about unique_ptr's move constructor that might come back to bite me. Is there anything wrong with the second approach?

Can anyone offer some advice on best practice here? Is my short cut above generally safe? My header file for the complete LinkedList follows (it's a work in progress). Suggestions for improvement would be very welcome.

Thanks in advance and my apologies if there is something I have overlooked (this is my first post).

/* 
 * File:   LinkedList.h
 */

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

#include <iostream>
#include <memory>
#include <exception>


template <typename T>
class LinkedList {
    template <typename U>
    friend std::ostream& operator<<(std::ostream&, const LinkedList<U>&);
public:        
    // default constructor
    LinkedList() : ptrHead{nullptr} {}

    // copy constructor: duplicate a list object
    LinkedList(LinkedList&);

    // move constructor
    LinkedList(LinkedList&&);

    // destructor
    ~LinkedList();

    // TODO: Add overloaded assignment and move assignment operators
    // For now, just delete them.
    const LinkedList& operator=(const LinkedList&) = delete;
    const LinkedList& operator=(const LinkedList&&) noexcept = delete;

    // utility methods
    void push(const T&);   
    void pop();
    T peek() const;
    void clean();
    void print(std::ostream&) const;

private:
    // basic node structure
    struct Node {
        // constructor
        explicit Node(const T& data) : element{data}, ptrNext{nullptr} {}
        // destructor (only for testing deallocation)
        ~Node() {
            std::cout << "Destroying Node with data " << element << std::endl;
        }

        T element;
        std::unique_ptr<Node> ptrNext;
    };

    std::unique_ptr<Node> ptrHead;  // head of the list
};


/////////////////////////////////////////////////////////////////////////////
// Implementation of Linked List

/**
 * Copy constructor
 * 
 * @param list
 */
template <typename T>
LinkedList<T>::LinkedList(LinkedList& list) {
    // the new head of list
    std::unique_ptr<Node> ptrNewHead{nullptr};

    // raw pointer cursor for traversing the new (copied) list
    Node* ptrCurrNode{nullptr};

    // raw pointer for traversing the list to be copied
    Node* ptrCursor{list.ptrHead.get()};

    while (ptrCursor) {
        // allocate a new node, copying the element of the current node
        std::unique_ptr<Node> 
            ptrTemp{std::make_unique<Node>(ptrCursor->element)};

        // add it to the new list, as appropriate
        if (ptrNewHead == nullptr) {
            ptrNewHead = std::move(ptrTemp);
            ptrCurrNode = ptrNewHead.get();
        } else {
            ptrCurrNode->ptrNext = std::move(ptrTemp);
            ptrCurrNode = ptrCurrNode->ptrNext.get();    
        }

        ptrCursor = ptrCursor->ptrNext.get();    
    }

    ptrHead = std::move(ptrNewHead);
}

/**
 * Copy move constructor
 * 
 * @param list
 */
template <typename T>
LinkedList<T>::LinkedList(LinkedList&& list) {
    ptrHead = std::move(list.ptrHead);
}

// TODO: Add overloaded assignment and move assignment operators

/**
 * Destructor
 * 
 */
template <typename T>
LinkedList<T>::~LinkedList() {
    clean();
}

/**
 * Push a T value onto the list
 * 
 * @param data
 */
template <typename T>
void LinkedList<T>::push(const T& data) {
    std::unique_ptr<Node> ptrTemp{std::make_unique<Node>(data)};
    ptrTemp->ptrNext = std::move(ptrHead);
    ptrHead = std::move(ptrTemp);
}

/**
 * Pop the top element off the list
 * 
 */
template <typename T>
void LinkedList<T>::pop() {
    if (ptrHead == nullptr) {
        return;
    }

    // can we safely avoid the ptrDetached intermediary?
    // std::unique_ptr<Node> ptrDetached = std::move(ptrHead);
    // ptrHead = std::move(ptrDetached->ptrNext);

    ptrHead = std::move(ptrHead->ptrNext);
}

/**
 * Peek at the value of the top element.
 * 
 * Throws an exception if the list is empty.
 * 
 * @return 
 */
template <typename T>
T LinkedList<T>::peek() const {
    if (ptrHead == nullptr) {
        throw std::out_of_range{"Empty list: Attempt to dereference a NULL pointer"};
    }        
    return ptrHead->element;
}

/**
 * Clean the list
 * 
 */
template <typename T>
void LinkedList<T>::clean() {
    while (ptrHead) {
        // can we safely avoid the ptrDetached intermediary?
        // std::unique_ptr<Node> ptrDetached = std::move(ptrHead);
        // ptrHead = std::move(ptrDetached->ptrNext);
        ptrHead = std::move(ptrHead->ptrNext);
    }
}

/**
 * Print the list on ostream os
 * 
 * @param os
 */
template <typename T>
void LinkedList<T>::print(std::ostream& os) const {
    Node* ptrCursor{ptrHead.get()}; // raw pointer for iteration

    while(ptrCursor) {
        os << ptrCursor->element << " -> ";
        ptrCursor = ptrCursor->ptrNext.get();
    }
    os << "NULL" << std::endl;
}


/**
 * Overloaded operator << for the LinkedList
 */
template <typename T>
std::ostream& operator<<(std::ostream& os, const LinkedList<T>& list) {
    list.print(os);
    return os;
}

#endif /* LINKEDLIST_H */
\$\endgroup\$
0

1 Answer 1

5
\$\begingroup\$

Overall

Good.

Personally I don't like building containers using smart pointers. Containers and smart pointers are the techniques we use to manage memory for objects (singular or plural respectively). As such they should both manage their own memories correctly.

But other people do it (use smart pointers) so I don't see it as a big deal; but I think you will learn more from implementing the container as the class that handles memory management.

Overview

You should put your stuff inside its own namespace.

Code Review

Not very unique.

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

If you add your own namespace to that guard it may become unique.


A friend template for a different type?

class LinkedList {
    template <typename U>
    friend std::ostream& operator<<(std::ostream&, const LinkedList<U>&);

You can simplify this to:

class LinkedList {
    friend std::ostream& operator<<(std::ostream&, LinkedList const&);

Even though print() is a public method and thus does not need a fiend to call it. I still would encourage this as a friend operator because it declares the tight coupling of the interface.


Nice use of the initializer list here.

    LinkedList() : ptrHead{nullptr} {}

Curious why you don't use it in the Copy Cosntrctor body!
I'll get to that below.


Normally you would pass the list by const reference.

    LinkedList(LinkedList&);

Here you could make a mistake in your copy constructor and accidently modify the input list.


Move constructors are usually noexcept safe.

    LinkedList(LinkedList&&);

This provides the standard library the opportunity to add optimizations when using its containers. If you can safely move objects without the chance of exception then the move constructor can be used. If the move constructor is not exception safe them you can not always provide the Strong Exception Guarantee and thus must use a technique that uses copying rather than moving. Thus if you can guarantee exception safe moves you should let the compiler know with noexcept.


Seriously that comment does my no good.

    // destructor
    ~LinkedList();

That is a bad comment. Because comments need to be maintained with the code (comments like code rote over time). So you be careful to avoid usless coments as they take effort to maintain (and people will put as little effort into maintenance as they can). As a result comments and code can drift apart over time and cause confusion.


    // TODO: Add overloaded assignment and move assignment operators
    // For now, just delete them.
    const LinkedList& operator=(const LinkedList&) = delete;
    const LinkedList& operator=(const LinkedList&&) noexcept = delete;

These are both exceptionally easy to implement if you have a swap() noexcept method.

Note 1: Assignment operators don't usually return const references.
Note 2: The move assignment operator does not take a const input. Moving the source into the destination will modify it.

    LinkedList const& operator=(LinkedList const& input) {
         LinkedList  copy(input);
         swap(copy);
         return *this;
    }
    LinkedList& operator=(LinkedList&& input) noexcept {
         clean();
         swap(input);
         return *this;
    }

You have a move constructor.
Why don't you have a move push()?

    void push(const T&);   

Nice.

    void pop();

Clea separation of the pop from the peek().


Why are you returning by value?

    T peek() const;

You should return a const reference to the object. This will prevent an extra copy (which is important if T is expensive to copy). But you can also provide a normal reference (if your class needs it) that would allow you to modify the object in place inside the list.

    T const& peek() const;
    T&       peek();          // Optional.

template <typename T>
LinkedList<T>::LinkedList(LinkedList& list) {

Why not use the initializer list to do this.

    // the new head of list
    std::unique_ptr<Node> ptrNewHead{nullptr};

Which of course is the default action of the unique_ptr default constructor. So this operation is already done by this point in the constructor.


I am going to mention comments again.

    // raw pointer cursor for traversing the new (copied) list
    Node* ptrCurrNode{nullptr};

    // raw pointer for traversing the list to be copied
    Node* ptrCursor{list.ptrHead.get()};

These comments are not useful. They do not tell me more than I can already understand from simply reading the code. Infact your code could be made more readable by removing the comments and using better variable names.

Comments should not be used for describing the code (the code does that very well). Also because of comment rote over time the code and comments can easily become disjoint. As such if a maintainer comes across code that has a comment that does not mach the comment do they fix the comment or do they fix the code. If they are good they have to do one which means they have to do research. It is better to write better "Self documenting code" so the code describes what it does.

Your comments should describe WHY or an overall ALGORITHM or some particularly OBSCURE point that code can not describe. DO NOT simply convert your code into English and call it a comment.


So above you ask why people assigned this to a temporary.

void LinkedList<T>::pop() {

    ....     
    ptrHead = std::move(ptrHead->ptrNext);
}

The question you have to ask yourself.

Q: Does the std::unique_ptr assignment operator call the destruct on the object it contains before or after it assigns the new value?

Let us imagine two different version of the assignment operator.

 oldValue = internalPtr;
 internalPtr = newValue;
 delete oldValue;

or

 delete internalValue;
 internalValue = newValue;

How do those different implementations affect your code?
What grantees does the standard provide?


No need to use std::endl here.

    os << "NULL" << std::endl;

Prefer to use "\n". This is exactly the same except it does not force a flush of the stream. The main problem with people timing C++ streams is that they always manually flush them (like this) then complain they are not as fast a C streams. If you don't manually flush them (especially since the stream knows when to flush itself very efficiently) the C++ streams are comparable to C streams.


\$\endgroup\$
2
  • \$\begingroup\$ thank you very much for the careful and informative review. All points you raise are valid and I shall take heed of them in the refactoring. \$\endgroup\$ Commented Jan 28, 2020 at 9:44
  • \$\begingroup\$ you mentioned memory management in your preamble. I have read your nice tutorial on dynamically resized vectors and learned much about memory management and placement new. Can you recommend a resource, web or otherwise, that does similar for lists? \$\endgroup\$ Commented Jan 28, 2020 at 9:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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