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 };
    } */
}
  • 1
    That's a lot of minimal code. – yuri Aug 10 at 16:31
  • 1
    @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 at 16:45
up vote 4 down vote accepted

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 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 at 10:50

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!" };
}

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.