СПРИНТ № 8 | Санитайзеры и другие инструменты поиска ошибок | Урок 9: Исправляем список

main.cpp

#include "list.h"
#include <cassert>
#include <vector>

using namespace std;

template <class Type>
auto MakeInsertingFunction(vector<SingleLinkedList<Type>>& lists, int x) {
    return [&](const Type& value) {
        lists.at(x).PushFront(value);
        };
}

template <class T>
void InsertRange(int from, int to, T push_function) {
    for (int i = from; i < to; ++i) {
        push_function(i);
    }
}

int main() {

    vector<SingleLinkedList<int>> lists_a(10);

    auto push_to_2a = MakeInsertingFunction(lists_a, 2);
    auto push_to_5a = MakeInsertingFunction(lists_a, 5);
    auto push_to_7a = MakeInsertingFunction(lists_a, 7);

    InsertRange(10, 12, push_to_2a);
    InsertRange(12, 14, push_to_5a);
    InsertRange(14, 16, push_to_7a);

    assert(lists_a[2] == SingleLinkedList<int>({ 11, 10 }));
    assert(lists_a[5] == SingleLinkedList<int>({ 13, 12 }));
    assert(lists_a[7] == SingleLinkedList<int>({ 15, 14 }));

    vector<SingleLinkedList<int>> lists_b = lists_a;

    auto push_to_2b = MakeInsertingFunction(lists_b, 2);
    auto push_to_5b = MakeInsertingFunction(lists_b, 5);
    auto push_to_7b = MakeInsertingFunction(lists_b, 7);

    InsertRange(20, 22, push_to_2b);
    InsertRange(22, 24, push_to_5b);
    InsertRange(24, 26, push_to_7b);

    assert(lists_b[2] == SingleLinkedList<int>({ 21, 20, 11, 10 }));
    assert(lists_b[5] == SingleLinkedList<int>({ 23, 22, 13, 12 }));
    assert(lists_b[7] == SingleLinkedList<int>({ 25, 24, 15, 14 }));

    lists_a[2].PopFront();
    lists_a[5].InsertAfter(lists_a[5].begin(), 100);
    lists_b[5].EraseAfter(next(lists_b[5].begin()));
    lists_b[7].Clear();

    assert(lists_a[2] == SingleLinkedList<int>({ 10 }));
    assert(lists_a[5] == SingleLinkedList<int>({ 13, 100, 12 }));
    assert(lists_b[5] == SingleLinkedList<int>({ 23, 22, 12 }));
    assert(lists_b[7] == SingleLinkedList<int>());
}

==================================================================================================================================
list.h

#pragma once

#include <cassert>
#include <cstddef>
#include <iterator>

template <typename Type>
class SingleLinkedList {

    struct Node {
        Node() = default;
        Node(const Type& val, Node* next) : value(val), next_node(next) {}
        Type value{};
        Node* next_node = nullptr;
    };


    template <typename ValueType>
    class BasicIterator {

        friend class SingleLinkedList;

        explicit BasicIterator(Node* node) : node_(node) {}

    public:

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

        BasicIterator() = default;

        BasicIterator(const BasicIterator<Type>& other) noexcept : node_(other.node_) {}

        BasicIterator& operator=(const BasicIterator& rhs) = default;

        [[nodiscard]] bool operator==(const BasicIterator<const Type>& rhs) const noexcept {
            return this->node_ == rhs.node_;
        }

        [[nodiscard]] bool operator==(const BasicIterator<Type>& rhs) const noexcept {
            return this->node_ == rhs.node_;
        }

        [[nodiscard]] bool operator!=(const BasicIterator<const Type>& rhs) const noexcept {
            return node_ != rhs.node_;
        }

        [[nodiscard]] bool operator!=(const BasicIterator<Type>& rhs) const noexcept {
            return node_ != rhs.node_;
        }

        BasicIterator& operator++() noexcept {
            assert(node_ != nullptr);
            node_ = node_->next_node;
            return *this;
        }

        BasicIterator operator++(int) noexcept {
            auto this_copy(*this);
            ++(*this);
            return this_copy;
        }

        [[nodiscard]] reference operator*() const noexcept {
            assert(node_ != nullptr);
            return node_->value;
        }

        [[nodiscard]] pointer operator->() const noexcept {
            assert(node_ != nullptr);
            return &node_->value;
        }

    private:
        Node* node_ = nullptr;
    };

public:
    using value_type = Type;
    using reference = value_type&;
    using const_reference = const value_type&;

    using Iterator = BasicIterator<Type>;
    using ConstIterator = BasicIterator<const Type>;

    SingleLinkedList() = default;

    SingleLinkedList(std::initializer_list<Type> values) {
        Assign(values.begin(), values.end());
    }

    SingleLinkedList(const SingleLinkedList& val) {
        Assign(val.begin(), val.end());
    }

    SingleLinkedList& operator=(const SingleLinkedList& helper) {
        if (&helper != this) {
            if(!helper.IsEmpty()){
                auto helper_copy(helper);
                swap(helper_copy);
            }else{
                Clear();
            }
        }
        return *this;
    }

    ~SingleLinkedList() {
        Clear();
    }

    [[nodiscard]] Iterator begin() noexcept {
        return Iterator{head_.next_node};
    }

    [[nodiscard]] Iterator end() noexcept {
        return Iterator{nullptr};
    }

    [[nodiscard]] ConstIterator begin() const noexcept {
        return cbegin();
    }

    [[nodiscard]] ConstIterator end() const noexcept {
        return ConstIterator{nullptr};
    }

    [[nodiscard]] ConstIterator cbegin() const noexcept {
        return ConstIterator{head_.next_node};
    }

    [[nodiscard]] ConstIterator cend() const noexcept {
        return ConstIterator{nullptr};
    }

    [[nodiscard]] Iterator before_begin() noexcept {
        return Iterator{&head_};
    }

    [[nodiscard]] ConstIterator cbefore_begin() const noexcept {
        return ConstIterator{const_cast<Node*>(&head_)};
    }

    [[nodiscard]] ConstIterator before_begin() const noexcept {
        return cbefore_begin();
    }

    [[nodiscard]] size_t GetSize() const noexcept {
        return size_;
    }

    [[nodiscard]] bool IsEmpty() const noexcept {
        return GetSize() == 0;
    }

    void PushFront(const Type& value) {
        head_.next_node = new Node(value, head_.next_node);

        ++size_;
    }

    Iterator InsertAfter(ConstIterator pos, const Type& value) {
        assert(pos.node_);

        pos.node_->next_node = new Node(value, pos.node_->next_node);

        ++size_;
        return Iterator{pos.node_->next_node};
    }

    void PopFront() noexcept {
        assert(!IsEmpty());
        --size_;
        Node* helper = head_.next_node->next_node;
        delete head_.next_node;
        head_.next_node = helper;
    }

    Iterator EraseAfter(ConstIterator pos) noexcept {
        assert(!IsEmpty());
        --size_;
        Node* helper = pos.node_->next_node->next_node;
        delete pos.node_->next_node;
        pos.node_->next_node = helper;
        return Iterator{pos.node_->next_node};
    }

    void Clear() noexcept {

        while (head_.next_node != nullptr) {
            Node* new_head = head_.next_node->next_node;
            delete head_.next_node;
            head_.next_node = new_head;
        }
        size_ = 0;
    }

    void swap(SingleLinkedList& other) noexcept {
        std::swap(head_.next_node, other.head_.next_node);
        std::swap(size_, other.size_);
    }

private:
    template <typename InputIterator>
    void Assign(InputIterator from, InputIterator to) {

        SingleLinkedList<Type> tmp;

        Node** node_ptr = &tmp.head_.next_node;
        while (from != to) {

            assert(*node_ptr == nullptr);

            *node_ptr = new Node(*from, nullptr);
            ++tmp.size_;


            node_ptr = &((*node_ptr)->next_node);

            ++from;
        }
        swap(tmp);
    }

    Node head_;
    size_t size_ = 0;
};

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

template <typename Type>
bool operator==(const SingleLinkedList<Type>& lhs, const SingleLinkedList<Type>& rhs) {
    return (&lhs == &rhs)
        || (lhs.GetSize() == rhs.GetSize()
            && std::equal(lhs.begin(), lhs.end(), rhs.begin()));
}

template <typename Type>
bool operator!=(const SingleLinkedList<Type>& lhs, const SingleLinkedList<Type>& rhs) {
    return !(lhs == rhs);
}

template <typename Type>
bool operator<(const SingleLinkedList<Type>& lhs, const SingleLinkedList<Type>& rhs) {
    return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
}

template <typename Type>
bool operator<=(const SingleLinkedList<Type>& lhs, const SingleLinkedList<Type>& rhs) {
    return !(rhs < lhs);
}

template <typename Type>
bool operator>(const SingleLinkedList<Type>& lhs, const SingleLinkedList<Type>& rhs) {
    return (rhs < lhs);
}

template <typename Type>
bool operator>=(const SingleLinkedList<Type>& lhs, const SingleLinkedList<Type>& rhs) {
    return !(lhs < rhs);
}