5
\$\begingroup\$

Below you can find a straightforward implementation of a double linked list, similar to std::list, making use of AAA (Almost Always Auto).

The purpose of this code ain't to reinvent std::list, instead, I wanted an easy to understand code containing sufficient complexity, so you can focus on the coding style.

Any feedback is welcome.

#include <utility>
#include <memory>

/// Double linked list implementation
template<typename T>
class List final {
    struct List_node;

    List_node *_start{nullptr};  ///< The first node of the list
    size_t     _size{0};         ///< Amount of elements in the list

    struct List_node final {
        template<typename ... TArgs>
        inline List_node(TArgs &&...args) : _value{std::forward<TArgs>(args)...} {}

        List_node *_next{nullptr};  ///< Next element, nullptr if the last one
        List_node *_prev{nullptr};  ///< Prev element, nullptr if the first one
        T          _value;          ///< Value as provided by user
    };

    /// Insert @p instance inbetween @prev and @next.
    /// \warning will update _start if needed.
    inline auto insert_inbetween(List_node *prev, List_node *next, std::unique_ptr<List_node> &&instance)
    {
        auto *node = instance.get();

        node->_prev = prev;
        node->_next = next;

        if (next)
            next->_prev = node;

        if (prev)
            prev->_next = instance.release();
        else
            _start = instance.release();

        ++_size;

        return List_iterator<T>{node};
    }

    inline auto push_front(std::unique_ptr<List_node> &&node)
    {
        return insert_inbetween(nullptr, _start, std::move(node));
    }

    inline auto push_back(std::unique_ptr<List_node> &&node)
    {
        if (!_start)
            return push_front(std::move(node));

        auto prev = _start;
        for (; prev->next; prev = prev->next)
            ;
        return insert_inbetween(prev, nullptr, std::move(node));
    }

public:
    /// Iterator implementation for this class
    template<typename TRef>
    class List_iterator final {
        static_assert(std::is_same_v<std::decay_t<TRef>, std::decay_t<T>>, "Only T and const T allowed");

        List_node *_node{nullptr};

        friend class List;
        List_iterator(List_node *node) :_node{node} {}

    public:
        inline TRef &operator*() const { return _node->_value; }
        inline TRef *operator->() const { return &(*this); }
        inline auto &operator++() { _node = _node->_next; return *this; }
        inline auto &operator--() { _node = _node->_prev; return *this; }
        inline auto &operator--(int) { auto current = *this; _node = _node->_prev; return current; }

        inline auto operator==(List_iterator rhs) const { return _node == rhs._node; }
        inline auto operator!=(List_iterator rhs) const { return !(*this == rhs); }

        operator List_iterator<const TRef>() { return List_iterator<const TRef>{_node}; }
    };

    auto begin() { return List_iterator<T>{_start};}
    auto end() { return List_iterator<T>{nullptr};}
    auto begin() const { return List_iterator<const T>{_start};}
    auto end() const { return List_iterator<const T>{nullptr};}
    auto cbegin() const { return begin();}
    auto cend() const { return end();}

    auto empty() const { return !_start; }
    auto size() const { return _size; }

    auto &front() const { return *begin(); }

    template<typename ... TArgs>
    inline auto emplace_front(TArgs &&...args) { push_front(std::make_unique<List_node>(std::forward<TArgs>(args)...)); }
    auto push_front(const T &v) { return emplace_front(v); }
    auto push_front(T &&v) { return emplace_front(std::move(v)); }

    template<typename ... TArgs>
    inline auto emplace_back(TArgs &&...args) { push_back(std::make_unique<List_node>(std::forward<TArgs>(args)...)); }
    auto push_back(const T &v) { return emplace_back(v); }
    auto push_back(T &&v) { return emplace_back(std::move(v)); }

    auto insert(List_iterator<T> prev, T &&v) { return insert_inbetween(prev._node, prev._node->_next, std::make_unique<List_node>(std::move(v))); }
    auto insert(List_iterator<T> prev, const T &v) { return insert_inbetween(prev._node, prev._node->_next, std::make_unique<List_node>(v)); }

    auto erase(List_iterator<T> it)
    {
        auto node = std::unique_ptr<List_node>{it._node};
        auto *prev = node->_prev;
        auto *next = node->_next;

        if (prev)
            prev->_next = next;
        else
            _start = next;

        if (next)
            next->_prev = prev;

        --_size;
        return List_iterator<T>{next};        
    }

    auto pop_front() { erase(begin()); }    
};
\$\endgroup\$
  • 1
    \$\begingroup\$ IDK, functions returning auto means that I need to read the code to know what type they return? \$\endgroup\$ – Cris Luengo Jan 7 '18 at 17:30
  • \$\begingroup\$ @CrisLuengo, or you can infer that from function name, if it is well named and doesn’t have surprises. \$\endgroup\$ – Incomputable Jan 7 '18 at 17:34
  • \$\begingroup\$ So you're relying on the documentation of the standard library? E.g. I have never used the return value of pop_front, so I don't know what it returns. The value of the deleted item (like in and old stack implementation where pop removes the item and return it)? Examine code, ah no, it returns nothing. If the function had been declared void that would have been easier... \$\endgroup\$ – Cris Luengo Jan 7 '18 at 17:41
  • \$\begingroup\$ @CrisLuengo, I'm not JVApen. If you want to, you can extend your comment into an answer. \$\endgroup\$ – Incomputable Jan 7 '18 at 18:11
  • \$\begingroup\$ @CrisLuengo It does. Although, the argument of AAA is that you don't care anyhow as your IDE will assist you when coding. \$\endgroup\$ – JVApen Jan 7 '18 at 18:30
7
\$\begingroup\$

Design

I prefer using a sentinel node in doubly linked list. This is a fake node with no data. That always exists. B?y using the sentinal you vastly reduce the complexity of your code (as you no longer need to check for nullptr as there is always one element in the list).

Code Review

Please avoid useless comments.

List_node *_start{nullptr};  ///< The first node of the list
size_t     _size{0};         ///< Amount of elements in the list

A bad comment is worse than no comment. This is because you need to maintain the comment to make sure it stays the same as the code while it is being updated. Significant time can be wasted when code is updates and a comment is not (thus confusing a subsequent maintainer).

Comments should be reserved for WHAT you are trying to do. The code should be self documenting and describe HOW. If the algorithm you are using is particularly difficult or you need to document WHY you used a particular technique then those are also good comments.

Please avoid prefix underscore

List_node *_start{nullptr};
size_t     _size{0};

The rules about prefix underscore are relatively complicated. Most people don't understand all the rules. Thus they are best avoided (even if you know all the rules).

In C++ the * and & are part of the type.

Unlike C, it is more usually to group the * with the type (rather than the variable).

// This is very C like
List_node *_start{nullptr};

// This is very C++ like
List_node* _start{nullptr};

This is because the * and the & are considered part of the type. So we group all type information together on the left.

Auto everywhere

I am happy to auto where the type does not matter (only the behavior matters). But where the type does matter then I would prefer to see explicit types.

These are fine:

auto begin() { return List_iterator<T>{_start};}
auto end() { return List_iterator<T>{nullptr};}
auto begin() const { return List_iterator<const T>{_start};}
auto end() const { return List_iterator<const T>{nullptr};}
auto cbegin() const { return begin();}
auto cend() const { return end();}

Not so sure about these (but I could live with them):

auto empty() const { return !_start; }
auto size() const { return _size; }

These I don't like:

auto push_front(const T &v) { return emplace_front(v); }
auto push_front(T &&v) { return emplace_front(std::move(v)); }

What are you returning me here?
What is the interface to the object I am getting back. Is it an iterator a reference to the object inside the container. Its not obvious to me what the behavior of the return value should be.

\$\endgroup\$
  • \$\begingroup\$ I strongly disagree with your second point - int* a; int * a; int a* are equally valid and subject to preference. Mildly disagree with your first point - a leading underscore brings a lot of problems, but also a lot of benefits. And strongly agree with the third point. Putting auto everywhere turns the code into python. \$\endgroup\$ – Vorac Jan 8 '18 at 22:06
  • 1
    \$\begingroup\$ @MiroslavVitkov: Useless comments are worse than no comments. Disagree all you like. You are still wrong. Self documenting code is the standard way of writing well maintained code. There is definitely an issue with comment wrote that happens in mature code. This is what we are trying to avoid. \$\endgroup\$ – Martin York Jan 8 '18 at 23:13
  • \$\begingroup\$ Yes. I never said they were not equivalent. What I cam saying is that stylistically C and C++ have diverged. In general C++ we place the modifier with the type. Read Stroustrops or Core Guidlines if you need to understand why. \$\endgroup\$ – Martin York Jan 8 '18 at 23:15
  • \$\begingroup\$ There are no benefits (any benefits you think can be achieved by a dozen other techniques that are just as simple). But there are a lot of pitfalls to using a leading underscore. \$\endgroup\$ – Martin York Jan 8 '18 at 23:16
  • \$\begingroup\$ Cooments: blog.codinghorror.com/code-tells-you-how-comments-tell-you-why \$\endgroup\$ – Martin York Jan 8 '18 at 23:22

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.