linked list implementation attempt

Question

The following is my attempt at writing a linked list that attempts to emulate the behavior of std::list. Any feedback would be appreciated.

#pragma once

#include <algorithm>
#include <cstddef>
#include <initializer_list>
#include <iterator>
#include <stdexcept>
#include <utility>

//a list is composed of links that contain pointers to previous
//and successive links
template<typename T>
struct Link {
    T val;
    Link<T>* prev;
    Link<T>* succ;

    void swap(Link* other)
    {
        using std::swap;
        swap(val, other->val);
        std::swap(prev, other->prev);
        std::swap(succ, other->succ);
    }

    Link(const T& v = T{}, Link<T>* p = nullptr, Link<T>* s = nullptr)
        :val{ v }, prev{ p }, succ{ s } {
    }
};

template<typename T>
void hook(Link<T>* a, Link<T>* b)
{
    a->succ = b;
    b->prev = a;
}

template<typename T>
struct List_iterator {
private:
    //mutable so we can increment a const_iterator
    mutable Link<T>* curr;
public:
    //List is a friend so that it can access curr without curr being public
    template<typename T>
    friend class List;

    explicit List_iterator(Link<T>* link) :curr{ link } {}

    T& operator*() { return curr->val; }
    const T& operator*() const { return curr->val; }

    Link<T>* operator->() { return curr; }
    Link<T>* const operator->() const { return curr; }

    //increment and decrement operators are overloaded so that
    //pre- and post- increments and decrements are possible

    List_iterator& operator++() 
    {
        if (!curr) throw std::runtime_error("Cannot increment null iterator\n");
        curr = curr->succ; return *this;
    }

    List_iterator operator++(int)
    {
        if (!curr) throw std::runtime_error("Cannot increment null iterator\n");
        auto temp = *this;
        operator++();
        return temp;
    }

    const List_iterator& operator++() const
    {
        if (!curr) throw std::runtime_error("Cannot increment null iterator\n");
        curr = curr->succ; return *this;
    }

    const List_iterator operator++(int) const
    {
        if (!curr) throw std::runtime_error("Cannot increment null iterator\n");
        auto temp = *this;
        operator++();
        return temp;
    }

    List_iterator& operator--() 
    {
        if (!curr) throw std::runtime_error("Cannot decrement null iterator\n");
        curr = curr->prev; return *this;
    }

    List_iterator operator--(int)
    {
        if (!curr) throw std::runtime_error("Cannot decrement null iterator\n");
        auto temp = *this;
        operator--();
        return temp;
    }

    const List_iterator& operator--() const
    {
        if (!curr) throw std::runtime_error("Cannot decrement null iterator\n");
        curr = curr->prev; return *this;
    }

    const List_iterator operator--(int) const
    {
        if (!curr) throw std::runtime_error("Cannot decrement null iterator\n");
        auto temp = *this;
        operator--();
        return temp;
    }

    //had to define an advance b/c std::advance wouldn't work
    //even after adding an iterator tag
    void advance(std::size_t n) const;

    bool operator==(const List_iterator& other) const  { return curr == other.curr; }
    bool operator!=(const List_iterator& other) const  { return curr != other.curr; }

    explicit operator bool() const { return curr; }
};

template<typename T>
void List_iterator<T>::advance(std::size_t n) const
{
    while (n--) operator++(); 
}

template<typename T>
class List;

template<typename T>
void merge(List<T>& sub_a, List<T>& sub_b, List<T>& list);

template<typename T>
void sort_helper(List<T>& list);

template<typename T>
class List {
    Link<T>* first;
    Link<T>* last;
    std::size_t sz;

    void cleanup();
    List_iterator<T> insert_first_element(Link<T>* new_link);
    void insert_back_unchecked(Link<T>* new_link);
    void insert_front_unchecked(Link<T>* new_link);
    List_iterator<T> insert_unchecked(const List_iterator<T> pos, Link<T>* new_link);
public:
    using size_type = std::size_t;
    using iterator = List_iterator<T>;
    using const_iterator = const List_iterator<T>;

    //all ctors must call default ctor first so conditions 
    //are set for insertion and deletion functions
    List() : first{ new Link<T>{} }, last{ first }, sz{ 0 } {}

    List(std::initializer_list<T>lst)
        :List(lst.begin(), lst.end()) {}

    //Initialize list w/ values in range [f, l)
    template<typename In>
    List(In f, In l);

    List(const List& other)
        :List(other.begin(), other.end()) {}
    List& operator=(const List& other);

    List(List&& other) noexcept;
    List& operator=(List&& other) noexcept;

    ~List() { cleanup(); }

    bool empty() const noexcept { return sz == 0; }

    void clear() noexcept
    {
        if (sz == 0) return;
        List temp;
        swap(temp);
    }

    void swap(List& other) noexcept
    {
        std::swap(first, other.first);
        std::swap(last, other.last);
        std::swap(sz, other.sz);
    }

    size_type size() const noexcept { return sz; }
    iterator begin() noexcept { return iterator(first); }
    iterator end() noexcept { return iterator(last); }
    const_iterator begin() const noexcept { return const_iterator(first); }
    const_iterator end() const noexcept { return const_iterator(last); }
    const_iterator cbegin() const noexcept { return const_iterator(first); }
    const_iterator cend() const noexcept { return const_iterator(last); }
    iterator insert(const_iterator p, const T& v);
    iterator erase(iterator p);
    T& front() { return first->val; }
    T& back() { return last->prev->val; }
    const T& front() const { return first->val; }
    const T& back() const { return last->prev->val; }
    void push_back(const T& v);
    void push_front(const T& v);

    template<typename... U>
    iterator emplace(const_iterator pos, U&&... args);

    template<typename... U>
    void emplace_back(U&&... args);

    template<typename... U>
    void emplace_front(U&&... args);
    void resize(size_type new_size, T val = T{});
    //transfer elements from one list to another
    void splice(const_iterator pos, List& other);
    void splice(const_iterator pos, List&& other) { splice(pos, other); }
    void reverse() noexcept;
    //remove consecutive duplicate elements
    void unique();

    bool operator==(const List& other);
    bool operator!=(const List& other) { return !(*this == other); }

    void remove(const T& value);

    template<typename Pred>
    void remove_if(Pred pred);

    //uses a merge sort
    void sort() { sort_helper(*this); }
};

template<typename T>
template<typename In>
List<T>::List(In f, In l)
    :List()
{
    while (f != l) { push_back(*f++); }
}

template<typename T>
typename List<T> & List<T>::operator=(const List & other)
{
    List<T> temp{ other };
    swap(temp);
    return *this;
}

template<typename T>
List<T>::List(List && other) noexcept
    :first{ other.first }, last{ other.last }, sz{ other.sz }
{
    other.first = other.last = nullptr;
    other.sz = 0;
}

template<typename T>
typename List<T> & List<T>::operator=(List && other) noexcept
{
    swap(other);
    return *this;
}

template<typename T>
void List<T>::cleanup()
{
    Link<T>* link;
    while (first)
    {
        link = first;
        first = first->succ;
        delete link;
    }
}

template<typename T>
typename List<T>::iterator List<T>::insert_first_element(Link<T>* new_link)
{
    first = new_link;
    hook(new_link, last);
    ++sz;
    return iterator(first);
}

template<typename T>
void List<T>::insert_back_unchecked(Link<T>* new_link)
{
    hook(last->prev, new_link);
    hook(new_link, last);
    ++sz;
}

template<typename T>
void List<T>::insert_front_unchecked(Link<T>* new_link)
{
    hook(new_link, first);
    first = new_link;
    ++sz;
}

template<typename T>
List_iterator<T> List<T>::insert_unchecked(const_iterator pos, Link<T>* new_link)
{
    if (pos == begin()) insert_front_unchecked(new_link);
    else {
        hook(pos.curr->prev, new_link);
        hook(new_link, pos.curr);
        ++sz;
    }
    return iterator(new_link);
}

template<typename T>
void sort_helper(List<T> & list)
{
    if (list.size() < 2) return;

    auto iter_split = list.begin();
    iter_split.advance(list.size() / 2);
    List<T> a{ list.begin(), iter_split };
    List<T> b{ iter_split, list.end() };
    sort_helper(a);
    sort_helper(b);
    merge(a, b, list);
}

//inserts a Link with value v before p
//undefined behaviour if an invalid iterator is specified
template<typename T>
inline typename List<T>::iterator List<T>::insert(const_iterator p, const T & v)
{
    Link<T>* new_link = new Link<T>{ v };
    if (empty()) { return insert_first_element(new_link); }
    else return insert_unchecked(p, new_link);
}

template<typename T>
typename List<T>::iterator List<T>::erase(iterator p)
{
    if (empty() || p == end()) return end();

    auto ret_val = p.curr->succ;
    if (p.curr->prev) hook(p.curr->prev, ret_val);
    else {
        first = ret_val;
        first->prev = nullptr;
    }

    delete p.curr;
    --sz;
    return iterator(ret_val);
}

template<typename T>
inline void List<T>::push_back(const T & v)
{
    Link<T>* new_link = new Link<T>{ v };
    if (empty()) insert_first_element(new_link);
    else insert_back_unchecked(new_link);
}

template<typename T>
inline void List<T>::push_front(const T & v)
{
    Link<T>* new_link = new Link<T>{ v };
    if (empty()) insert_first_element(new_link);
    else insert_front_unchecked(new_link);
}

template<typename T>
void List<T>::resize(size_type new_size, T val)
{
    //store old sz b/c erase will decrement sz so the loop will execute less times than it should
    const auto old_sz = sz;
    for (auto i = new_size; i < old_sz; ++i) erase(--end());
    for (auto i = sz; i < new_size; ++i) push_back(val);
}

template<typename T>
void List<T>::splice(const_iterator pos, List & other)
{
    if (other.sz == 0) return;
    if (pos.curr->prev) hook(pos.curr->prev, other.first);
    else first = other.first;
    hook(other.last->prev, pos.curr);
    other.first = other.last = nullptr;
    sz += other.sz;
    other.sz = 0;
}

template<typename T>
void List<T>::reverse() noexcept
{
    using std::swap;
    auto b = begin();
    auto e = end();
    while (b != e && b != --e) { swap(*b++, *e); }
}

template<typename T>
void List<T>::unique()
{
    auto iter = end();
    while (iter != begin())
    {
        if (*iter == iter.curr->prev->val) {
            iter = iterator(erase(iter).curr->prev);
        }
        else --iter;
    }
}

template<typename T>
bool List<T>::operator==(const List & other)
{
    if (sz != other.sz) return false;
    auto m_begin = begin();
    auto o_begin = other.begin();
    while (m_begin != end())
    {
        if (*m_begin++ != *o_begin++) return false;
    }
    return true;
}

template<typename T>
void List<T>::remove(const T& value)
{
    auto iter = begin();
    while (iter != end())
    {
        if (*iter == value) iter = erase(iter);
        else ++iter;
    }
}

template<typename T>
void merge(List<T> & a, List<T> & b, List<T> & list)
{
    auto a_iter = a.begin();
    auto b_iter = b.begin();
    auto list_iter = list.begin();
    while (a_iter != a.end() && b_iter != b.end())
    {
        if (*a_iter <= *b_iter)
        {
            *list_iter = *a_iter;
            ++a_iter;
        }
        else
        {
            *list_iter = *b_iter;
            ++b_iter;
        }
        ++list_iter;
    }
    while (a_iter != a.end()) { *list_iter++ = *a_iter++; }
    while (b_iter != b.end()) { *list_iter++ = *b_iter++; }
}

template<typename T>
template<typename ...U>
inline typename List<T>::iterator List<T>::emplace(const_iterator pos, U && ...args)
{
    Link<T>* new_link = new Link<T>{ T( std::forward<U>(args)... ), pos.curr->prev, pos.curr };
    if (empty()) { return insert_first_element(new_link); }
    else return insert_unchecked(pos, new_link);
}

template<typename T>
template<typename ...U>
inline void List<T>::emplace_back(U && ...args)
{
    Link<T>* new_link = new Link<T>{ T( std::forward<U>(args)...) };
    if (empty()) insert_first_element(new_link);
    else insert_back_unchecked(new_link);
}

template<typename T>
template<typename ...U>
inline void List<T>::emplace_front(U && ...args)
{
    Link<T>* new_link = new Link<T>{ T(std::forward<U>(args)...) };
    if (empty()) insert_first_element(new_link);
    else insert_front_unchecked(new_link);
}

template<typename T>
template<typename Pred>
void List<T>::remove_if(Pred pred)
{
    auto iter = begin();
    while (iter != end())
    {
        if (pred(*iter)) iter = erase(iter);
        else ++iter;
    }
}

Answer 1

1. Some of your member functions should not exist. You don't want n algorithms and m containers to result in n*m implementations, because that number becomes rather big. Also people tend to forget to add all algorithms to their containers, especially when new ones appear. Instead you are supposed to implement algorithms and containers separately to only need n+m implementations. This applies does not apply to unique, remove and remove_if that have a non-member std function std::unique, std::remove and std::remove_if because the member functions are more efficient than the free standing functions. Also std::remove only moves elements while std::list::remove actually erases them.
   Unfortunately it doesn't apply to sort because std::sort requires random access iterators which you don't have.

2. Your sort implementation seems to make a lot of copies. If you can't find a clever efficient way you can just create a std::vector<T*> and std::sort that and then apply the positioning to your list.

3. I would expect a linked list to work with move-only types such as std::unique_ptr<int>, but it doesn't because you copy Ts in various functions.

4. I am getting compilation errors with both gcc and clang. It looks like you only tested with VS's compiler which tends to be a bit lenient.

5. Avoid cleanup functions. That is what the destructor is for. Also you already have clear.

6. Your List_iterator does bad things when const. For example you can do

   const List<int> l{1, 2, 3};
   auto it = l.begin();
   *it = 42;
   

   That last line should not compile, but it does. Blame the mutable that should not be there. Unfortunately you need to write 2 classes to get this right in C++, typically List_iterator and Const_list_iterator.

7. Looking at the list of things required to make a bidirectional iterator it seems like you are missing some, for example everything around std::iterator_traits which also explains

   //had to define an advance b/c std::advance wouldn't work
   //even after adding an iterator tag
   

   It is a bit annoying to do all those things from the linked documentation, especially when you realize that you need to follow more links because it says "The type It satisfies ForwardIterator" which has yet another list of requirements and that one links to more requirements. On the upside once you did all of it the standard algorithms work with your iterator and you can delete a bit of code. Also algorithms from other libraries like boost tend to work when you have standard iterators.

8. You can initialize members in the class declaration, for example

   template<class T>
   class List {
       Link<T>* first{nullptr};
       Link<T>* last{nullptr};
       std::size_t sz = 0;
   }
   

   If your constructor initializes members the class initialization is treated as not existing (so no loss in performance for double-initializing), but if you forget or leave it out you get sane defaults.

9. I would like to see Link and sort_helper in the private part of List for encapsulation. If you let users access those types they will use them which I think is not intended.

Answer 2

#pragma once is OK with me. Some people might flag it for review; I note that if it is for publication to unknown users, you should add (properly-made) guards too.

---

Link<T>* prev;
Link<T>* succ;

One of those should be a unique_ptr. I just saw a presentation from a conference video that remarked that a major standard library implementation had a memory leak (in vector I think) in case an exception was thrown during construction or assignment, sometimes. So don’t revert to old-style primitive code just because you are writing a collection!

List() : first{ new Link<T>{} }, last{ first }, sz{ 0 } {}

and here is where this will protect you from this very bug. You are not deleting the node in the case where your constructor throws an exception. In general, other things in your member-init list can throw, not just the function body!

So always have owning semantics on resources, even if you don’t rely on that for normal usage.

Link<T>* new_link = new Link<T>{ T( std::forward<U>(args)...) };

That is, you can write

auto new_link = make_unique<T>{ T( std::forward<U>(args)...) };
    ⋮
put_it_where_it_belongs (new_link.release());

and you are protected against memory leaks when the Link constructor (and its payload’s constructor contained within) throws, and for any exceptions that occur up to when you discharge responsibility for keeping it.

---

You put a lot of work into writing the iterator from scratch. Use Boost.Iterator to do most of the work for you, instead. This can be a façade around the pointer type, and you change only the category (to bidirectional) and write simple next and prev functions, and how to unbox the data from the node. All the various members and variations will be done for you automatically.

---

void swap(Link* other)

Swapping a Link with a Link* is strange. You should make that parameter a Link& instead. And mark it as noexcept if T has a no-throw swap.

---

    if (!curr) throw std::runtime_error("Cannot increment null iterator\n");

This identical line is present in many of the functions. Take a look via Compiler Explorer or your debug asm window: the throw generates a lot of code. Contrast that to the main path you want inlined, which is a simple deref and assignment.

So, make a separate raise_error member, and make it not-inline. Call that from the inlined functions. Also can use compiler-specific features to mark the test as expected vs unexpected. (Microsoft's distribution of the GSL includes a GSL_LIKELY macro for cross-platform)

---

All and all, it looks like good code, well-written. You know about current features and style, and you seem to have made a through catalog of all the members and features, not just the basics.

Just get rid of naked news, to do better than the common implementations!