Singly-linked list implementation with iterators

Question

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 <stdexcept>
#include <iostream>
#include <initializer_list>
#include <cstddef>
#include <iterator>
#include <utility>
#include <type_traits>

template<class T>
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<class Iterator>
    using is_correct_iterator = std::enable_if_t
    <
        std::is_same<T, typename std::iterator_traits<Iterator>::value_type>::value      &&
        std::is_base_of<std::input_iterator_tag, typename std::iterator_traits<Iterator>::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<std::forward_iterator_tag, T>
    {
    protected:
        node* _node;

        friend class slist<T>;

        //only for slist<T> 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; }
        iterator  operator++(int) { iterator temp(_node); operator++(); return temp; }

        bool operator!=(const iterator& rhs) const { return _node != rhs._node; }
        bool operator==(const iterator& rhs) const { return _node == rhs._node; }
        bool operator>(const iterator& rhs)  const { return _node > rhs._node; }
        bool operator<(const iterator& rhs)  const { return _node < rhs._node; }
        bool operator>=(const iterator& rhs) const { return _node >= rhs._node; }
        bool operator<=(const iterator& rhs) const { return _node <= rhs._node; }

        T& operator*()  { return _node->key; }
        T* operator->() { return **this; } //no idea what im doing here
    };

    class const_iterator : public iterator
    {
    private:
        friend class slist<T>;

    public:
        using iterator::iterator; //inherit them constructors

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

        T operator*()   const { return _node->key; }
        T* operator->() const { return **this; } //still no idea
    };

public:     //ACTUAL slist<T> CLASS
    //CONSTRUCTORS
    slist() : _root(nullptr), _tail(nullptr), _size(0) {}

    template<class Iterator, class = is_correct_iterator<Iterator>>
    slist(Iterator first, Iterator last) { assign(first, last); }

    slist(const std::size_t& count, const T& val) { assign(count, val); }

    slist(const std::initializer_list<T>& ilist) : slist(ilist.begin(), ilist.end()) {}

    slist& operator=(const std::initializer_list<T>& ilist)
    {
        assign(ilist.begin(), ilist.end());

        return *this;
    }

    //COPY/MOVE CONSTRUCTORS AND ASSIGNMENT
    slist(const slist& rhs)
        : _root(nullptr), _tail(nullptr), _size(0)
    {
        for (const auto& i : rhs)
            emplace_back(i);
    }

    slist(slist&& rhs)
        : _root(nullptr), _tail(nullptr), _size(0)
    {
        swap(rhs);
    }

    slist& operator=(const slist& rhs)
    {
        if (this == &rhs)
            return *this;

        clear();

        for (const auto& i : rhs)
            emplace_back(i);

        return *this;
    }

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

        _root = nullptr;
        _tail = nullptr;
        _size = 0;
        swap(rhs);

        return *this;
    }

    //DESTRUCTOR
    ~slist() { clear(); }

    //INSERT OPERATIONS
    void push_front(T& new_key)  { emplace_front(new_key); }
    void push_front(T&& new_key) { emplace_front(std::move(new_key)); }

    void push_back(T& new_key)  { emplace_back(new_key); }
    void push_back(T&& new_key) { emplace_back(std::move(new_key)); }

    template<class... Args>
    void emplace_front(Args&&... args)
    {
        _root = new node{ { std::forward<Args>(args)... }, _root };

        if (!_root->next)
            _tail = _root;

        ++_size;
    }

    template<class... Args>
    void emplace_back(Args&&... args)
    {
        node* new_node = new node{ { std::forward<Args>(args)... }, nullptr };

        if (!_tail)
        {
            _tail = new_node;
            _root = new_node;
        }
        else
        {
            _tail->next = new_node;
            _tail = _tail->next;
        }
        ++_size;
    }

    void insert_after(const iterator& it, const T& new_key) { emplace_after(it, new_key); }
    void insert_after(const iterator& it, T&& new_key)      { emplace_after(it, std::move(new_key)); }

    template<class... Args>
    void emplace_after(const iterator& it, Args&&... args)
    {
        if (!it._node)
            throw std::out_of_range("List is empty! Use emplace_back() or emplace_front() instead!");

        it._node->next = new node{ { std::forward<Args>(args)... }, it._node->next };;

        ++_size;
    }

    //ASSIGN
    void assign(const std::size_t& count, const T& val)
    {
        clear();
        for (std::size_t i = 0; i < count; ++i)
            emplace_back(val);
    }

    template<class Iterator, class = is_correct_iterator<Iterator>>
    void assign(Iterator first, Iterator last)
    {
        clear();
        for (; first != last; ++first)
            emplace_back(*first);
    }

    void assign(const std::initializer_list<T>& ilist)
    {
        clear();
        assign(ilist.begin(), ilist.end());
    }

    //DELETE OPERATIONS
    void pop_front() 
    { 
        if (!_root)
            throw std::out_of_range("Can't pop from an empty list!!");

        if (_size == 1)
        {
            _root = nullptr;
            _tail = nullptr;
        }
        else
        {
            node* temp_root = _root;
            _root = _root->next;
            delete temp_root;
        }
        --_size;
    }

    void pop_back()  //O(n)
    { 
        if (!_root)
            throw std::out_of_range("Can't pop from an empty list!!");

        if (_size == 1)
        {
            _root = nullptr;
            _tail = nullptr;
        }
        else
        {
            node* before_tail = _root;

            while (before_tail->next->next)
                before_tail = before_tail->next;

            before_tail->next = nullptr; //so _tail = nullptr

            _tail = before_tail; //last node is equal to one before last

            delete before_tail->next; //delete _tail
        }
        --_size;
    }

    void erase_after(const iterator& it)
    {
        if (!_root)
            throw std::out_of_range("Can't erase from an empty list!!");

        node* temp = it._node->next;

        it._node->next = temp->next;

        delete temp;

        --_size;
    }

    void clear() 
    {
        while (!empty())
            pop_front();
    }

    //CAPACITY FUNCTIONS
    constexpr std::size_t size()  const noexcept { return _size; }
    constexpr bool        empty() const noexcept { return !_size; }

    //ACCESS FUNCTIONS
    T& front() { return _root->key; }
    T& back()  { return _tail->key; }

    const T& front() const { return _root->key; }
    const T& back()  const { return _tail->key; }

    //ITERATORS
    iterator begin() noexcept { return iterator(_root); }
    iterator end()   noexcept { return iterator(nullptr); }

    const_iterator begin() const noexcept { return const_iterator(const_cast<node*>(_root)); }
    const_iterator end()   const noexcept { return const_iterator(nullptr); }

    const_iterator cbegin() const noexcept { return const_iterator(_root); }
    const_iterator cend()   const noexcept { return const_iterator(nullptr); }

    //INDEXING
    T& operator[](const std::size_t& index)
    {
        if (index < 0 || index >= _size)
            throw std::out_of_range("Index out of bounds!");

        if (index == 0)
            return _root->key;

        if (index == _size - 1)
            return _tail->key;

        iterator it(_root);
        std::advance(it, index);

        return *it;
    }

    //ALGORITHMS
    void swap(slist& rhs)
    {
        std::swap(_root, rhs._root);
        std::swap(_tail, rhs._tail);
        std::swap(_size, rhs._size);
    }
};

Loki Astari · Accepted Answer · 2015-11-30 08:23:22Z

Bugs:

Iterators comparison are meaningless.

    bool operator>(const iterator& rhs)  const { return _node > rhs._node; }
    bool operator<(const iterator& rhs)  const { return _node < rhs._node; }
    bool operator>=(const iterator& rhs) const { return _node >= rhs._node; }
    bool operator<=(const iterator& rhs) const { return _node <= rhs._node; }

The node is a random place in memory it has no relationship to the order in the list. Giving your iterator this ability will result in it being misused.

The operator->() should return the same as operator*() (but a pointer rather than a reference).

For integer types (of T) this will make no sense (but will generate a compiler error). But when T is an object type it allows accesses to the members of that object.

    T& operator*()  { return _node->key; }
    T* operator->() { return &_node->key; }

Your move assignment operator leaks

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

    _root = nullptr;   // What happens to the nodes that were here!!!!
    _tail = nullptr;
    _size = 0;
    swap(rhs);

    return *this;
}

Making the code better.

The only difference between iterator/const_iterator is the type returned by operator-> and operator* (one is T and one is T const). So you can create a base iterator type then specialize for const and not const versions.

 template<typename IT>
 struct iterator_base
 {
       .....
       IT& operator*() {return  _node->key;}
       IT* operator*() {reutrn &_node->key;}
 };
 using iterator       = iterator_base<T>;
 using const_iterator = iterator_base<T const>;

The best way to implement the assignment operator is the copy/swap idiom. This makes sure that if there is an issue during the copy you get correct rollback thus giving your object the strong exception guarantee.

slist& operator=(const slist& rhs)
{
    if (this == &rhs)
        return *this;

    clear();
    // You clear the current content (and thus destroy it).
    // This is fine if everything works. But if it does not all work you
    // should roll the object back to the original state (to get the strong
    // exception guarantee). 

    for (const auto& i : rhs)
        emplace_back(i);

    return *this;
}

An easy way to implement the assignment operator is:

slist& operator=(slist rhs)  // Pass by value generates an implicit copy.
{
    rhs.swap(*this);
    return *this;
}                            // destructor of parameter rhs cleans up the
                             // old content.

The same technique can be used for the assignment using the initializer_list.

slist& operator=(const std::initializer_list<T>& ilist)
{
    assign(ilist.begin(), ilist.end());
    // The problem here
    // Is that the first part of assign is to clear the current content.
    // This is fine if everything works. But if it does not all work you
    // should roll the object back to the original state (to get the strong
    // exception guarantee). 

    return *this;
}

An easy way to implement the assignment operator is to use the constructor then swap again.

slist& operator=(const std::initializer_list<T>& ilist)
{
    slist tmp(ilist);
    tmp.swap(*this);
    return *this;
}

The move operator should be exception safe (otherwise it does not help having a move operator when using standard containers).

As a result you should mark the move constructor and move assignment as noexcept.

slist(slist&& rhs)  noexcept                    // mark as no-except
    : _root(nullptr), _tail(nullptr), _size(0)
{
    swap(rhs);
}

The standard containers try and provide the strong exception guarantee. For example on a vector resize once we have a new storage area the vector will try an move the elements from the old storage area to the new storage area, but it can only do that if the move constructor provides a no throw guarantee otherwise it must fall back to using the copy constructor (because that allows rollback).

Move Assignment can be done in the same way:

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

Also the swap operator should also be marked noexcept. It is usually used by the move operators (so if these are noexcept so does swap).

void swap(slist& rhs)  noexcept
{
    // This is the one time where using actually comes in useful.
    using std::swap;

    // Now the swap used will be either be found by argument dependent
    // lookup if that fails it will use the swap in the current scope.
    // which will be `std::swap()` because we just added the using 
    // declaration.
    swap(_root, rhs._root);
    swap(_tail, rhs._tail);
    swap(_size, rhs._size);

    // Even though you don't currently have any types here to be swapped.
    // you should still do it this way for when there are future enhancement
    // to the class that may be a type.
}

Thanks for the input! I like the idea about the iterators! But STL iterators allow you to construct a const_iterator from an iterator, as: std::list<int>::const_iterator i = mylist.begin();, but not the other way around. How would I go about doing that with this approach? — Ivaylo Valchev
– Ivaylo Valchev, Commented Nov 30, 2015 at 17:52
@DeiDei: That's true and I had not thought about that honestly. — Loki Astari
– Loki Astari, Commented Nov 30, 2015 at 17:58
@DeiDei You make iterator_base<X> constructible from iterator_base<Y> if X is constructible from Y. — Barry
– Barry, Commented Nov 30, 2015 at 19:27

Barry · Accepted Answer · 2015-11-29 17:37:53Z

Iterators

iterator looks pretty good. I'm not sure about making it default-constructible, or making iterators ordered (operator<, etc.). Maybe just remove those. 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<T>. const_iterator should instead be a std::iterator<std::forward_iterator_tag, const T>. 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<int> from a std::vector<int>? Or even from a std::deque<int16_t>? 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 <class Iterator>
using is_correct_iterator = std::enable_if_t<
    std::is_constructible<T, typename std::iterator_traits<Iterator>::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.

Thanks for your review! But I don't understand why the move assignment should be done that way. That would just swap the contents of the two objects. If I do a = std::move(b);, b will hold the contents of a, and the other way around, instead of being b being empty. — Ivaylo Valchev
– Ivaylo Valchev, Commented Nov 29, 2015 at 18:09
Is it okay that iterator_traits weren't defined here? Is deriving form std::iterator enough? — Russell Greene
– Russell Greene, Commented Nov 29, 2015 at 18:29
@DeiDei There's no requirement that b be empty. Simply that a efficiently gets the contents of b (accomplished by swap) and that the old contents of a get correctly destroyed (accomplished by the eventual destructor of b). — Barry
– Barry, Commented Nov 29, 2015 at 18:36
@RussellGreene std::iterator_traits by default uses member typedefs. And std::iterator simply provides a bunch of typedefs. — Barry
– Barry, Commented Nov 29, 2015 at 18:37
@Barry Aah. Only ever used the boost iterator library, which makes everything so easy! — Russell Greene
– Russell Greene, Commented Nov 29, 2015 at 18:39

Stack Exchange Network

Singly-linked list implementation with iterators

2 Answers 2

Bugs:

Making the code better.

You must log in to answer this question.

Hot Network Questions

Singly-linked list implementation with iterators

2 Answers 2

Bugs:

Making the code better.

You must log in to answer this question.

Related

Hot Network Questions