trjhtr

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 *_startnullptr; ///< The first node of the list
 size_t _size0; ///< Amount of elements in the list

 struct List_node final 
 template<typename ... TArgs>
 inline List_node(TArgs &&...args) : _valuestd::forward<TArgs>(args)... 

 List_node *_nextnullptr; ///< Next element, nullptr if the last one
 List_node *_prevnullptr; ///< 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 *_nodenullptr;

 friend class List;
 List_iterator(List_node *node) :_nodenode 

 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()); 
;

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 *_startnullptr; ///< The first node of the list
size_t _size0; ///< 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 *_startnullptr;
size_t _size0;

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 *_startnullptr;

// This is very C++ like
List_node* _startnullptr;

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.