Singly-linked list implementation with iterators

Taking into account everything you guys told me last time I posted, I came up with this implementation of a singly-linked list, in which the first and last elements are known.

I tried to make the implementation as STL-friendly as possible, so I also implemented iterators. It's my first time with those, so there might be bugs that I have missed. Also the operator-> overload for the iterators... I have no idea if what I've done is correct.

I hope someone with experience in this can share some knowledge!!

PS. This is for a library I am implementing for myself, as a way of learning how to do things. That's the reason for the variables which begin with underscore _.

PPS. Performance is also of great concern!

```
#include
#include
#include
#include
#include
#include
#include

template
class slist
{
public: //TYPE ALIASES
using value_type = T;
using size_type = std::size_t;
using reference = T&;
using const_reference = const T&;
using pointer = T*;
using const_pointer = const T*;

private: //WAY TOO LONG TO HAVE IN MULTIPLE FUNCTIONS
template
using is_correct_iterator = std::enable_if_t
::value_type>::value &&
std::is_base_of::iterator_category>::value
>;

private: //PRIVATE MEMBER VARIABLES
struct node
{
T key;
node* next;
} _root, _tail;

std::size_t _size;

public: //ITERATOR CLASSES
class iterator : public std::iterator
{
protected:
node* _node;

friend class slist;

//only for slist to access
iterator(node* new_node) : _node(new_node) {}

public:
constexpr iterator() = default;
constexpr iterator(const iterator&) = default;
constexpr iterator(iterator&&) = default;

iterator& operator=(const iterator&) = default;
iterator& operator=(iterator&&) = default;

iterator& operator++() { _node = _node->next; return *this; }

Iterators

iterator looks pretty good. I'm not sure about making it default-constructible, or making iterators ordered (operator() needs to return a T*, so that's just &_node->key;. That's the one thing you're missing.

const_iterator on the other hand, isn't quite right. There are a few issues here:

• Dereferencing a const_iterator sohuld give you a const T&, and using the member access should give you a const T*. That's what const_iterator suggests - it iterates over constant members. Instead you are (a) giving back a copy on dereference and (b) still basing all of the typedefs on T, which means they're all wrong. The former is worse - that suggests that something as innocuous as std::find(list.begin(), list.end(), v) will copy every element for a const list. const_iterator should instead be a std::iterator. Rather than inheriting from iterator, consider making a class template for both iterator types and having the two main ones be aliases.

• const_iterator should be constructible from iterator. Not a deal-breaker, but it's convenient.

is_correct_iterator

I like the idea, but your condition is overly restrictive. What if I want to construct an slist from a std::vector? Or even from a std::deque? There's isn't anything about that operation that's fundamentally unsound.

So instead of requiring the same value_type and that we're only constructing from slist iterators, prefer any reasonable iterator:

template 
using is_correct_iterator = std::enable_if_t::value_type>>;

Move/Copy Assignments

Self-assignment check is a pessimization. Prefer to implement copy assignment as copy-and-swap, and move assignment as simply swap. DO NOT clear our your members first in the move assignment! This leaks all those resources. Simply:

slist& operator=(slist&& rhs) {
    swap(rhs);
    return *this;
}

Missing Deletes

In pop_front and pop_back, you're not deleteing the node in case of size one.

Supporting \$O(n)\$ operations

You currently have member functions for a few expensive operations: operator[] and pop_back. This may suggest to users that these operations aren't expensive. Note that std::list for instance does not provide operator[] for this reason. I would suggest that somebody using a singly-linked list should not be using indexing anyway, so I would omit it. If you do add it, you should have a const overload as well.

Performance

One thing to point out here. In a lot of places, you implement a lot of member functions in terms of other member functions (e.g. assign uses emplace_back, and clear uses pop_front()). This is great for writing, but could be better for performance since you don't need to do lots of checking in these cases. clear can simply loop over each node calling delete, then setting everything to nullptr. Assign can similarly do a bunch of news back-to-back-to-back without the need for a branch.

Whether or not these are worth optimizing is up to you.

StackExchange Code Review Q#112235, answer score: 6