现代C++单链表

Question

这是一个非常小的(虽然功能齐全)的单链接列表实现。它支持\\mathcal{O}(1)\\前面插入和删除，以及\\mathcal{O}(1)通过迭代器进行的随机插入和删除。

目标是一个干净而简单的实现，可以有效地与标准算法一起使用，并尽可能提供强大的异常保证。

请告诉我是否忽略了使用所提供的方法无法轻松完成的任何主要功能。

forward_list.hpp

#pragma once

#include 
#include 
#include 
#include 
#include 
#include 

template
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 next;

        template>>
        explicit node_type(std::unique_ptr&& next, Args&&... args) noexcept(std::is_nothrow_constructible_v)
            : data{ std::forward(args)... }, next{ std::move(next) } {}
    };

    std::unique_ptr 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 il);

    template
    forward_list(Iter first, Iter last);

    ~forward_list() noexcept(std::is_nothrow_destructible_v);

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

    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);

    template
    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);

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

    void clear() noexcept(std::is_nothrow_destructible_v);
    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
class forward_list::iterator
{
    node_type* node = nullptr;
    bool before_begin = false;

public:
    friend class forward_list;
    friend class const_iterator;

    using value_type = typename forward_list::value_type;
    using pointer = typename forward_list::pointer;
    using reference = typename forward_list::reference;
    using difference_type = typename forward_list::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
class forward_list::const_iterator
{
    node_type* node = nullptr;
    bool before_begin = false;

public:
    friend class forward_list;

    using value_type = typename forward_list::value_type;
    using pointer = typename forward_list::const_pointer;
    using reference = typename forward_list::const_reference;
    using difference_type = typename forward_list::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
forward_list::forward_list(const forward_list& other) : forward_list{ other.begin(), other.end() } {}

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

template
forward_list::forward_list(std::initializer_list il) : forward_list{ il.begin(), il.end() } {}

template
template
forward_list::forward_list(Iter first, Iter last)
{
    static_assert(std::is_copy_constructible_v, "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
forward_list::~forward_list() noexcept(std::is_nothrow_destructible_v)
{
    clear();
}

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

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

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


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

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

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

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

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

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

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

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

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

template
typename forward_list::iterator forward_list::erase_after(const_iterator pos) noexcept(std::is_nothrow_destructible_v)
{
    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
template
typename forward_list::iterator forward_list::emplace_after(const_iterator pos, Args&&... args)
{
    if(pos.before_begin)
    {
        emplace_front(std::forward(args)...);
        return begin();
    }

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

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

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

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

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

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


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

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

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


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

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

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

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

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

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

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

template
forward_list::iterator::iterator(node_type* node, bool before_begin) noexcept : node{ node }, before_begin{ before_begin } {}

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

    return *this;
}

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

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

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

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

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

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

template
forward_list::const_iterator::const_iterator(node_type* node, bool before_begin) noexcept : node{ node }, before_begin{ before_begin } {}

template
forward_list::const_iterator::const_iterator(iterator other) noexcept : node{ other.node }, before_begin{ other.before_begin } {}


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

    return *this;
}

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

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

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

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

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

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

template
void swap(forward_list& lhs, forward_list& rhs) noexcept
{
    lhs.swap(rhs);
}

unittests.cpp (使用Catch2 2测试框架)

#include "forward_list.hpp"

#define CATCH_CONFIG_MAIN
#include "catch.hpp"

#include 
#include 

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

    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{ 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };

    auto list = forward_list{ 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{ 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{ 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{ 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{};

        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{ 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{ 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{ 1, 2, 3 };

        auto second_list = forward_list{ 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{};

    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{ list };
    } */
}

Answer 1

一般都是很好的代码。尽管您声称它是“最小的”，但唯一似乎缺少的是用户指定的分配。

充分利用noexcept和const。

有一个通过使迭代器本身成为一个模板来减少重复的参数，这样迭代器的一致性就在模板参数中：

template
class forward_list
{
public:
    template
    class iterator_impl;
    using iterator = iterator_impl;
    using const_iterator = iterator_impl;
}

template
template
class forward_list::iterator_impl
{
    node_type* node = nullptr;
    bool before_begin = false;

public:
    friend class forward_list;

    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>>
    iterator_impl(iterator_impl other) noexcept
        : node{other.node}, before_begin{other.before_begin} {}
    template>>
    iterator_impl& operator=(iterator_impl 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
template
forward_list::iterator_impl::iterator_impl(node_type* node, bool before_begin) noexcept : node{ node }, before_begin{ before_begin } {}

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

    return *this;
}

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

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

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

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

template
template
bool forward_list::iterator_impl::operator!=(iterator_impl other) const noexcept
{
    return !(*this == other);
}

Answer 2

在emplace_after中有一个bug，在取消引用之前，该实现从不检查pos.node是否不是nullptr，而且通常不处理后期迭代器的情况。

这个问题可以这样解决：

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

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

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

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