3
\$\begingroup\$

I've only ever written C++98 code, because that's what I learned and at work we are limited to C++98 due to the fact that we sell source code to customers who are reluctant to upgrade their toolchains.

Therefore, I decided to learn modern C++ in my own time. As a first exercise I decided to implement a linked list using as many modern features of C++ that I'm aware of. The code passes my unit tests and valgrind says I have no memory leaks, but I would like a review of my code, because I would like to know if I wrote "good" modern C++.

I would really appreciate if someone could please review the code:

#include <memory>

using std::shared_ptr;

namespace ds {

        class NullNextException : public std::exception { };

        template <class T>
        class Node {

        public:
                Node(T _value, shared_ptr< Node<T> > _next = nullptr) noexcept :
                        value(_value),
                        next(_next) {

                }

                Node(const Node<T> &) = delete;
                Node<T> &operator = (const Node<T> &) = delete;

                const T &get() const noexcept {
                        return value;
                }

                const Node<T> &get_next() const {
                        if (next == nullptr) {
                                throw NullNextException();
                        }
                        return *next;
                }

                const shared_ptr< Node<T> > &get_next_ptr() const noexcept {
                        return next;
                }

                bool end() const noexcept {
                        return (next == nullptr);
                }

                void set(T &_value) noexcept {
                        value = _value;
                }

                void set_next(shared_ptr< Node<T> > _next) noexcept {
                        next = _next;
                }

        private:
                T value;
                shared_ptr< Node<T> > next;
        };

        class EmptyListException : public std::exception { };
        class OutOfBoundsException : public std::exception { };

        template <class T>
        class List {

        public:
                List() noexcept :
                        front(nullptr),
                        n_nodes(0) {

                }

                List(const List<T> &) = delete;
                List<T> &operator = (const List<T> &) = delete;

                void insert_front(T &value) {
                        auto node = shared_ptr< Node<T> >(new Node<T>(value, front));
                        front = std::move(node);
                        n_nodes++;
                }

                void insert_back(T &value) {
                        if (front == nullptr) {
                                insert_front(value);
                                return;
                        }

                        auto node = shared_ptr< Node<T> >(new Node<T>(value));
                        auto back = front;
                        while (!back->end()) {
                                back = back->get_next_ptr();
                        }
                        back->set_next(node);
                        n_nodes++;
                }

                T pop_front() {
                        if (front == nullptr) {
                                throw EmptyListException();
                        }

                        T retval = std::move(front->get());
                        front = std::move(front->get_next_ptr());
                        n_nodes--;
                        return std::move(retval);
                }

                T pop_back() {
                        if (front == nullptr) {
                                throw EmptyListException();
                        }

                        auto penult = front;
                        auto back = front;
                        if (!back->end()) {
                                back = back->get_next_ptr();
                        }

                        while (!back->end()) {
                                penult = back;
                                back = back->get_next_ptr();
                        }

                        T retval = std::move(back->get());

                        if (back == front) {
                                front = nullptr;
                        }
                        else {
                                penult->set_next(nullptr);
                        }

                        n_nodes--;
                        return std::move(retval);
                }

                const T &nth(size_t n) const {
                        if (n >= size()) {
                                throw OutOfBoundsException();
                        }

                        auto ith = front;
                        for (size_t ii = 0; ii < n; ++ii) {
                                ith = ith->get_next_ptr();
                        }
                        return ith->get();
                }

                size_t size() const noexcept {
                        return n_nodes;
                }

        private:
                shared_ptr< Node<T> > front;

                size_t n_nodes;
        };

}
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Let me just say "thank you!" for using valgrind and running unit tests before posting code here. I wish everyone did! \$\endgroup\$ Commented Oct 2, 2017 at 10:57

1 Answer 1

Reset to default
2
\$\begingroup\$

Before I write anything about your code, let me just say I find your interest in sharpening your skills commendable. Now on to the review!

Encapsulation

Your Node class template is an implementation detail, is it not? So placing it in the ds namespace where the public interface of the linked list is supposed to be is a break in encapsulation. I would suggest to either move it into List, or into a detail namespace if you intend to reuse it.

namespace ds {
  namespace detail {
    template <class T> class Node {/* As before /*};
  }
}

This is a common idiom for isolating implementation details from user code. And even though it's not an access specifier like private, it sends a clear message that this should not be touched or used for risk of nasal demonsTM. I call it the responsible adult approach. And it works quite well in libraries like boost.

Identifiers

The identifier ds is kinda lackluster. What does it mean? You should give namespaces long and meaningful names. They are there to avoid collisions. If a client wants to shorten it. They can use a namespace alias.

Namesapce Pollution

You have a using declaration at global scope in a header. While it isn't as bad as a using directive, it's still namespace pollution. You shouldn't introduce identifiers into the global namespace of clients. Especially those that are implementation details. Either move it into one of your namespaces (detail comes to mind). Or write std::shared_ptr (honestly, it's not that much to type).

Unnecessary Overhead

Speaking of std::shared_ptr. Why are you using it? Do you expect a node to be under shared ownership? I would say not, so why pull in the overhead of keeping a track of sharing.

A node will always have a unique owner. And there's another smart pointer in the standard library to model just that, the aptly named std::unique_ptr. Best part is, that it's likely to have no overhead compared to a raw pointer.

noexcept correctness

You mark certain things as noexcept, such as the node c'tor, for instance. But are you sure this isn't lying to the compiler? There's a template parameter there (T), and you copy construct it. It may throw, that isn't unheard of. A class like std::vector may throw while copying. So you shouldn't just assume it's noexecpt. Instead, make the specification depend on the specification that is given to T's copy c'tor. Use the noexcept operator:

Node(T _value, shared_ptr< Node<T> > _next = nullptr) noexcept(noexcept(T(_value)))

Const correctness

You insert copies of T into the list, and that's fine. But by this very virtue, you aren't modifying the parameter you are given. So it should be a reference to constant object.

insert_front(T const &value)

Use of auto

Nothing much to say here. You use it judiciously and I think that should at least be mentioned. :)

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.