Modern C++ singly linked list

Question

This is a rather minimal (though fully functional) implementation of a singly linked list. It supports \$\mathcal{O}(1)\$ front insertion and deletions, as well as \$\mathcal{O}(1)\$ random insertions and deletions via iterator.

The goal was a clean and simple implementation that can be used effectively with standard algorithms and provides a strong exception guarantee as far as possible.

Please tell if I've overlooked any major functionality that cannot be easily done with the provided methods.

forward_list.hpp

#pragma once

#include <memory>
#include <type_traits>
#include <iterator>
#include <stdexcept>
#include <utility>
#include <cstddef>

template<typename T>
class forward_list
{
public:
    using value_type = T;
    using reference = T&;
    using const_reference = const T&;
    using pointer = T*;
    using const_pointer = const T*;

    using size_type = std::ptrdiff_t;
    using difference_type = std::ptrdiff_t;

    class iterator;
    class const_iterator;

private:
    struct node_type
    {
        value_type data;
        std::unique_ptr<node_type> next;

        template<typename... Args, typename = std::enable_if_t<std::is_constructible_v<T, Args&&...>>>
        explicit node_type(std::unique_ptr<node_type>&& next, Args&&... args) noexcept(std::is_nothrow_constructible_v<T, Args&&...>)
            : data{ std::forward<Args>(args)... }, next{ std::move(next) } {}
    };

    std::unique_ptr<node_type> head = nullptr;
    size_type length = 0;

public:
    forward_list() = default;
    forward_list(const forward_list& other);
    forward_list(forward_list&& other) noexcept;

    forward_list(std::initializer_list<T> il);

    template<typename Iter>
    forward_list(Iter first, Iter last);

    ~forward_list() noexcept(std::is_nothrow_destructible_v<T>);

    forward_list& operator=(const forward_list& other) &;
    forward_list& operator=(forward_list&& other) & noexcept(std::is_nothrow_destructible_v<T>);

    reference front();
    const_reference front() const;

    void push_front(const T& value);
    void push_front(T&& value);
    void pop_front() noexcept(std::is_nothrow_destructible_v<T>);

    template<typename... Args>
    void emplace_front(Args&&... args);

    iterator insert_after(const_iterator pos, const T& value);
    iterator insert_after(const_iterator pos, T&& value);
    iterator erase_after(const_iterator pos) noexcept(std::is_nothrow_destructible_v<T>);

    template<typename... Args>
    iterator emplace_after(const_iterator pos, Args&&... args);

    void clear() noexcept(std::is_nothrow_destructible_v<T>);
    void swap(forward_list& other) noexcept;
    size_type size() const noexcept;
    bool empty() const noexcept;

    iterator begin() noexcept;
    const_iterator begin() const noexcept;
    const_iterator cbegin() const noexcept;

    iterator end() noexcept;
    const_iterator end() const noexcept;
    const_iterator cend() const noexcept;

    iterator before_begin() noexcept;
    const_iterator before_begin() const noexcept;
    const_iterator cbefore_begin() const noexcept;
};

template<typename T>
class forward_list<T>::iterator
{
    node_type* node = nullptr;
    bool before_begin = false;

public:
    friend class forward_list<T>;
    friend class const_iterator;

    using value_type = typename forward_list<T>::value_type;
    using pointer = typename forward_list<T>::pointer;
    using reference = typename forward_list<T>::reference;
    using difference_type = typename forward_list<T>::difference_type;
    using iterator_category = std::forward_iterator_tag;

    iterator() = default;
    iterator(node_type* node, bool before_begin = false) noexcept;

    iterator& operator++();
    iterator operator++(int);

    reference operator*() const;
    pointer operator->() const;

    bool operator==(iterator other) const noexcept;
    bool operator!=(iterator other) const noexcept;
};

template<typename T>
class forward_list<T>::const_iterator
{
    node_type* node = nullptr;
    bool before_begin = false;

public:
    friend class forward_list<T>;

    using value_type = typename forward_list<T>::value_type;
    using pointer = typename forward_list<T>::const_pointer;
    using reference = typename forward_list<T>::const_reference;
    using difference_type = typename forward_list<T>::difference_type;
    using iterator_category = std::forward_iterator_tag;

    const_iterator() = default;
    const_iterator(node_type* node, bool before_begin = false) noexcept;
    const_iterator(iterator other) noexcept;

    const_iterator& operator++();
    const_iterator operator++(int);

    reference operator*() const;
    pointer operator->() const;

    bool operator==(const_iterator other) const noexcept;
    bool operator!=(const_iterator other) const noexcept;
};

/// FORWARD_LIST IMPLEMENTATION ///////////////////////////////////////////////////

template<typename T>
forward_list<T>::forward_list(const forward_list& other) : forward_list{ other.begin(), other.end() } {}

template<typename T>
forward_list<T>::forward_list(forward_list&& other) noexcept : head{ std::move(other.head) }, length{ other.length }
{
    other.length = 0;
}

template<typename T>
forward_list<T>::forward_list(std::initializer_list<T> il) : forward_list{ il.begin(), il.end() } {}

template<typename T>
template<typename Iter>
forward_list<T>::forward_list(Iter first, Iter last)
{
    static_assert(std::is_copy_constructible_v<T>, "T must be copy constructible!");

    auto insert_pos = before_begin();

    for(auto it = first; it != last; ++it)
    {
        insert_pos = insert_after(insert_pos, *it);
    }
}


template<typename T>
forward_list<T>::~forward_list() noexcept(std::is_nothrow_destructible_v<T>)
{
    clear();
}

template<typename T>
forward_list<T>& forward_list<T>::operator=(const forward_list& other) &
{
    static_assert(std::is_copy_constructible_v<T>, "T must be copy constructible");

    auto copy = forward_list{ other };
    swap(copy);
    return *this;
}

template<typename T>
forward_list<T>& forward_list<T>::operator=(forward_list&& other) & noexcept(std::is_nothrow_destructible_v<T>)
{
    auto temp = forward_list{ std::move(other) };
    swap(temp);
    return *this;
}


template<typename T>
typename forward_list<T>::reference forward_list<T>::front()
{
    if (!head) throw std::range_error{ "list is empty!" };
    return head->data;
}

template<typename T>
typename forward_list<T>::const_reference forward_list<T>::front() const
{
    if (!head) throw std::range_error{ "list is empty!" };
    return head->data;
}

template<typename T>
void forward_list<T>::push_front(const T& value)
{
    emplace_front(value);
}

template<typename T>
void forward_list<T>::push_front(T&& value)
{
    emplace_front(std::move(value));
}

template<typename T>
void forward_list<T>::pop_front() noexcept(std::is_nothrow_destructible_v<T>)
{
    if(head)
    {
        head = std::move(head->next);
        --length;
    }
}

template<typename T>
template<typename ... Args>
void forward_list<T>::emplace_front(Args&&... args)
{
    static_assert(std::is_constructible_v<T>, "T cannot be constructed using the passed arguments");

    head = std::make_unique<node_type>(std::move(head), std::forward<Args>(args)...);
    ++length;
}

template<typename T>
typename forward_list<T>::iterator forward_list<T>::insert_after(const_iterator pos, const T& value)
{
    return emplace_after(pos, value);
}

template<typename T>
typename  forward_list<T>::iterator forward_list<T>::insert_after(const_iterator pos, T&& value)
{
    return emplace_after(pos, std::move(value));
}

template<typename T>
typename forward_list<T>::iterator forward_list<T>::erase_after(const_iterator pos) noexcept(std::is_nothrow_destructible_v<T>)
{
    if(pos.before_begin)
    {
        pop_front();
        return begin();
    }

    if (pos.node && pos.node->next)
    {
        pos.node->next = std::move(pos.node->next->next);
        --length;
        return { pos.node->next.get() };
    }

    return end();
}


template<typename T>
template<typename ... Args>
typename forward_list<T>::iterator forward_list<T>::emplace_after(const_iterator pos, Args&&... args)
{
    if(pos.before_begin)
    {
        emplace_front(std::forward<Args>(args)...);
        return begin();
    }

    pos.node->next = std::make_unique<node_type>(std::move(pos.node->next), std::forward<Args>(args)...);
    ++length;

    return { pos.node->next.get() };
}

template<typename T>
void forward_list<T>::clear() noexcept(std::is_nothrow_destructible_v<T>)
{
    while (head) head = std::move(head->next);
    length = 0;
}

template<typename T>
void forward_list<T>::swap(forward_list& other) noexcept
{
    using std::swap;
    swap(head, other.head);
    swap(length, other.length);
}

template<typename T>
typename forward_list<T>::size_type forward_list<T>::size() const noexcept
{
    return length;
}

template<typename T>
bool forward_list<T>::empty() const noexcept
{
    return head == nullptr;
}


template<typename T>
typename forward_list<T>::iterator forward_list<T>::begin() noexcept
{
    return { head.get() };
}

template<typename T>
typename forward_list<T>::const_iterator forward_list<T>::begin() const noexcept
{
    return { head.get() };
}

template<typename T>
typename forward_list<T>::const_iterator forward_list<T>::cbegin() const noexcept
{
    return begin();
}


template<typename T>
typename forward_list<T>::iterator forward_list<T>::end() noexcept
{
    return {};
}

template<typename T>
typename forward_list<T>::const_iterator forward_list<T>::end() const noexcept
{
    return {};
}

template<typename T>
typename forward_list<T>::const_iterator forward_list<T>::cend() const noexcept
{
    return end();
}

template<typename T>
typename forward_list<T>::iterator forward_list<T>::before_begin() noexcept
{
    return { head.get(), true };
}

template<typename T>
typename forward_list<T>::const_iterator forward_list<T>::before_begin() const noexcept
{
    return { head.get(), true };
}

template<typename T>
typename forward_list<T>::const_iterator forward_list<T>::cbefore_begin() const noexcept
{
    return before_begin();
}

/// ITERATOR IMPLEMENTATION ///////////////////////////////////////////////////////

template<typename T>
forward_list<T>::iterator::iterator(node_type* node, bool before_begin) noexcept : node{ node }, before_begin{ before_begin } {}

template<typename T>
typename forward_list<T>::iterator& forward_list<T>::iterator::operator++()
{
    if (before_begin) before_begin = false;
    else node = node->next.get();

    return *this;
}

template<typename T>
typename forward_list<T>::iterator forward_list<T>::iterator::operator++(int)
{
    auto copy = *this;
    ++*this;
    return copy;
}

template<typename T>
typename forward_list<T>::iterator::reference forward_list<T>::iterator::operator*() const
{
    return node->data;
}

template<typename T>
typename forward_list<T>::iterator::pointer forward_list<T>::iterator::operator->() const
{
    return &node->data;
}

template<typename T>
bool forward_list<T>::iterator::operator==(iterator other) const noexcept
{
    return node == other.node && before_begin == other.before_begin;
}

template<typename T>
bool forward_list<T>::iterator::operator!=(iterator other) const noexcept
{
    return !(*this == other);
}

/// CONST_ITERATOR IMPLEMENTATION /////////////////////////////////////////////////

template<typename T>
forward_list<T>::const_iterator::const_iterator(node_type* node, bool before_begin) noexcept : node{ node }, before_begin{ before_begin } {}

template<typename T>
forward_list<T>::const_iterator::const_iterator(iterator other) noexcept : node{ other.node }, before_begin{ other.before_begin } {}


template<typename T>
typename forward_list<T>::const_iterator& forward_list<T>::const_iterator::operator++()
{
    if (before_begin) before_begin = false;
    else node = node->next.get();

    return *this;
}

template<typename T>
typename forward_list<T>::const_iterator forward_list<T>::const_iterator::operator++(int)
{
    auto copy = *this;
    ++*this;
    return copy;
}

template<typename T>
typename forward_list<T>::const_iterator::reference forward_list<T>::const_iterator::operator*() const
{
    return node->data;
}

template<typename T>
typename forward_list<T>::const_iterator::pointer forward_list<T>::const_iterator::operator->() const
{
    return &node->data;
}

template<typename T>
bool forward_list<T>::const_iterator::operator==(const_iterator other) const noexcept
{
    return node == other.node && before_begin == other.before_begin;
}

template<typename T>
bool forward_list<T>::const_iterator::operator!=(const_iterator other) const noexcept
{
    return !(*this == other);
}

/// FREE FUNCTIONS IMPLEMENTATION /////////////////////////////////////////////////

template<typename T>
void swap(forward_list<T>& lhs, forward_list<T>& rhs) noexcept
{
    lhs.swap(rhs);
}

unittests.cpp (using the Catch2 testing framework)

#include "forward_list.hpp"

#define CATCH_CONFIG_MAIN
#include "catch.hpp"

#include <algorithm>
#include <mutex>

TEST_CASE("Using an empty forward_list", "[forward_list]")
{
    auto list = forward_list<int>{};

    REQUIRE(list.size() == 0);
    REQUIRE(list.empty());
    REQUIRE(list.begin() == list.end());

    SECTION("Adding an element at the front sets up invariants")
    {
        constexpr auto value = 1234;

        list.push_front(value);

        REQUIRE(!list.empty());
        REQUIRE(list.front() == value);
        REQUIRE(list.size() == 1);
        REQUIRE(list.begin() != list.end());
        REQUIRE(++list.begin() == list.end());
    }

    SECTION("Adding multiple elements increases size correctly")
    {
        constexpr auto value = 1234;

        for(auto i = 0; i < 10; ++i)
        {
            list.push_front(i);
            REQUIRE(list.size() == i + 1);
            REQUIRE(std::distance(list.begin(), list.end()) == i + 1);
        }
    }

    SECTION("pop_front on empty list does nothing")
    {
        list.pop_front();

        REQUIRE(list.size() == 0);
        REQUIRE(list.empty());
        REQUIRE(list.begin() == list.end());
    }

    SECTION("front on empty list throws")
    {
        REQUIRE_THROWS(list.front());
    }
}

TEST_CASE("Using a forward list with multiple elements", "[forward_list]")
{
    static auto init_values = std::vector<int>{ 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };

    auto list = forward_list<int>{ 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };

    REQUIRE(list.size() == init_values.size());
    REQUIRE(!list.empty());
    REQUIRE(std::distance(list.begin(), list.end()) == init_values.size());
    REQUIRE(std::equal(list.begin(), list.end(), init_values.begin()));

    SECTION("Can find elements with std::find")
    {
        auto found = std::find(std::begin(list), std::end(list), 5);

        REQUIRE(found != std::end(list));
        REQUIRE(*found == 5);
    }

    SECTION("Insert new value after iterator position")
    {
        static auto expected = std::vector<int>{ 9, 8, 7, 6, 5, 11, 4, 3, 2, 1, 0 };

        const auto iter = std::find(std::begin(list), std::end(list), 5);
        REQUIRE(iter != std::end(list));

        auto inserted = list.insert_after(iter, 11);

        REQUIRE(inserted != std::end(list));
        REQUIRE(*inserted == 11);
        REQUIRE(std::equal(std::begin(list), std::end(list), std::begin(expected)));
    }

    SECTION("Insertion handles before_begin() iterator correctly")
    {
        list.insert_after(list.before_begin(), 12);
        REQUIRE(list.front() == 12);
    }

    SECTION("pop_front removes front node")
    {
        list.pop_front();

        REQUIRE(list.front() == 8);
        REQUIRE(list.size() == 9);
    }

    SECTION("erase_after removes element")
    {
        static auto expected = std::vector<int>{ 9, 8, 7, 6, 5, 4, 2, 1, 0 };

        auto iter = std::find(list.begin(), list.end(), 4);
        auto after_removed = list.erase_after(iter);

        REQUIRE(list.size() == init_values.size() - 1);
        REQUIRE(after_removed != list.end());
        REQUIRE(*after_removed == 2);
        REQUIRE(std::equal(list.begin(), list.end(), expected.begin()));
    }

    SECTION("erase_after handles before_begin() iterator correctly")
    {
        static auto expected = std::vector<int>{ 8, 7, 6, 5, 4, 3, 2, 1, 0 };

        auto after_removed = list.erase_after(list.before_begin());

        REQUIRE(list.size() == init_values.size() - 1);
        REQUIRE(after_removed == list.begin());
        REQUIRE(std::equal(list.begin(), list.end(), expected.begin()));
        REQUIRE(list.front() == expected.front());
    }

    SECTION("clear removes all nodes")
    {
        list.clear();

        REQUIRE(list.size() == 0);
        REQUIRE(list.empty());
        REQUIRE(list.begin() == list.end());
    }

    SECTION("copy construction")
    {
        auto second_list = list;

        REQUIRE(list.size() == init_values.size());
        REQUIRE(std::equal(list.begin(), list.end(), init_values.begin()));
        REQUIRE(second_list.size() == list.size());
        REQUIRE(std::equal(second_list.begin(), second_list.end(), list.begin()));
    }

    SECTION("copy assignment")
    {
        auto second_list = forward_list<int>{};

        second_list = list;

        REQUIRE(list.size() == init_values.size());
        REQUIRE(std::equal(list.begin(), list.end(), init_values.begin()));
        REQUIRE(second_list.size() == list.size());
        REQUIRE(std::equal(second_list.begin(), second_list.end(), list.begin()));
    }

    SECTION("move construction leaves original list in empty state")
    {
        auto second_list = forward_list<int>{ std::move(list) };

        REQUIRE(list.empty());
        REQUIRE(second_list.size() == init_values.size());
        REQUIRE(std::equal(second_list.begin(), second_list.end(), init_values.begin()));
    }

    SECTION("move assignment leaves original list in empty state")
    {
        auto second_list = forward_list<int>{ 11, 12, 13 };

        second_list = std::move(list);

        REQUIRE(list.empty());
        REQUIRE(second_list.size() == init_values.size());
        REQUIRE(std::equal(second_list.begin(), second_list.end(), init_values.begin()));
    }

    SECTION("swap exchanges states")
    {
        static auto second_list_values = std::vector<int>{ 1, 2, 3 };

        auto second_list = forward_list<int>{ second_list_values.begin(), second_list_values.end() };

        swap(list, second_list);

        REQUIRE(list.size() == second_list_values.size());
        REQUIRE(std::equal(list.begin(), list.end(), second_list_values.begin()));

        REQUIRE(second_list.size() == init_values.size());
        REQUIRE(std::equal(second_list.begin(), second_list.end(), init_values.begin()));
    }
}

TEST_CASE("Can use non.movable and non-copyable types", "[forward_list]")
{
    auto list = forward_list<std::mutex>{};

    REQUIRE(list.empty());
    REQUIRE(list.size() == 0);
    REQUIRE(list.begin() == list.end());

    SECTION("Can use emplace_front")
    {
        list.emplace_front();

        REQUIRE(!list.empty());
        REQUIRE(list.size() == 1);
    }

    SECTION("Can use emplace_after")
    {
        list.emplace_front();
        list.emplace_after(list.begin());

        REQUIRE(list.size() == 2);
    }

    SECTION("Can use -> on iterators")
    {
        list.emplace_front();
        auto iter = list.begin();

        REQUIRE(iter != list.end());

        iter->lock();
        iter->unlock();
    }

    // Fails to compile, as expected:
    /* SECTION("Copy doesn't work")
    {
        auto copy = forward_list<std::mutex>{ list };
    } */
}

@yuri: Well, I'm not reimplementing the whole std::forward_list... Also, it would be quite a lot shorter if I merged function declaration and function definitions, though that would make it harder to get a general view of the API. Other than that, it only does the bare minimum to get a singly linked list that works for all types (plus 3 fancy constructors, I guess). — hoffmale, Aug 10, 2018 at 16:45

Toby Speight · Accepted Answer · 2018-08-10 11:15:19Z

Generally excellent code. Although you claim it's "minimal", the only non-trivial thing that seems to be missing is user-specified allocation.

Good use of noexcept and const throughout.

There's an argument for reducing duplication by making the iterator itself be a template, so that the constness of the iterant is in the template argument:

template<typename T>
class forward_list
{
public:
    template<typename S = T>
    class iterator_impl;
    using iterator = iterator_impl<T>;
    using const_iterator = iterator_impl<const T>;
}

template<typename T>
template<typename S>
class forward_list<T>::iterator_impl
{
    node_type* node = nullptr;
    bool before_begin = false;

public:
    friend class forward_list<T>;

    using value_type = S;
    using pointer = S*;
    using reference = S&;
    using difference_type = std::ptrdiff_t;
    using iterator_category = std::forward_iterator_tag;

    iterator_impl() = default;
    iterator_impl(node_type* node, bool before_begin = false) noexcept;

    // allow converson from mutable iterator to const iterator
    template<typename U, typename = std::enable_if_t<std::is_assignable_v<S*&, U*>>>
    iterator_impl(iterator_impl<U> other) noexcept
        : node{other.node}, before_begin{other.before_begin} {}
    template<typename U, typename = std::enable_if_t<std::is_assignable_v<S*&, U*>>>
    iterator_impl& operator=(iterator_impl<U> other) noexcept
    { node = other.node;  before_begin = other.before_begin; return *this; }

    iterator_impl& operator++();
    iterator_impl operator++(int);

    reference operator*() const;
    pointer operator->() const;

    bool operator==(iterator_impl other) const noexcept;
    bool operator!=(iterator_impl other) const noexcept;
};

template<typename T>
template<typename S>
forward_list<T>::iterator_impl<S>::iterator_impl(node_type* node, bool before_begin) noexcept : node{ node }, before_begin{ before_begin } {}

template<typename T>
template<typename S>
auto forward_list<T>::iterator_impl<S>::operator++() -> iterator_impl&
{
    if (before_begin) before_begin = false;
    else node = node->next.get();

    return *this;
}

template<typename T>
template<typename S>
auto forward_list<T>::iterator_impl<S>::operator++(int) -> iterator_impl
{
    auto copy = *this;
    ++*this;
    return copy;
}

template<typename T>
template<typename S>
auto forward_list<T>::iterator_impl<S>::operator*() const -> reference
{
    return node->data;
}

template<typename T>
template<typename S>
auto forward_list<T>::iterator_impl<S>::operator->() const -> pointer
{
    return &node->data;
}

template<typename T>
template<typename S>
bool forward_list<T>::iterator_impl<S>::operator==(iterator_impl other) const noexcept
{
    return node == other.node && before_begin == other.before_begin;
}

template<typename T>
template<typename S>
bool forward_list<T>::iterator_impl<S>::operator!=(iterator_impl other) const noexcept
{
    return !(*this == other);
}

That's less metaprogramming constructs than I expected, nice work! The iterator_impl<U> could be taken by value instead of const& (since it's small enough), though that's a matter of preference. Also, the assignment operator is missing a return *this; — hoffmale, Aug 10, 2018 at 10:22
Thanks - edited (that shows that none of the tests exercise the assignment operator, or the compiler would have picked up the missing return *this). — Toby Speight, Aug 10, 2018 at 10:50

hoffmale · Accepted Answer · 2018-08-14 01:51:18Z

There's a bug in emplace_after, the implementation never checks if pos.node is not nullptr before dereferencing, and generally doesn't handle the after-the-end iterator case.

This could be fixed like this:

template<typename T>
template<typename... Args>
iterator forward_list<T>::emplace_after(const_iterator pos, Args&&... args)
{
    if(pos.before_begin)
    {
        emplace_front(std::forward<Args>(args)...);
        return begin();
    }

    if(pos.node)
    {
        pos.node->next = std::make_unique<node_type>(std::move(pos.node->next), std::forward<Args>(args)...);
        ++length;

        return { pos.node->next.get() };
    }

    throw std::out_of_range{ "Cannot insert after end iterator!" };
}

Stack Exchange Network

Modern C++ singly linked list

forward_list.hpp

unittests.cpp (using the Catch2 testing framework)

2 Answers 2

Your Answer

Not the answer you're looking for? Browse other questions tagged
c++
linked-list
reinventing-the-wheel
c++17
or ask your own question.

Hot Network Questions

Modern C++ singly linked list

forward_list.hpp

unittests.cpp (using the Catch2 testing framework)

2 Answers 2

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged c++linked-listreinventing-the-wheelc++17 or ask your own question.

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
c++
linked-list
reinventing-the-wheel
c++17
or ask your own question.