list

#include <cassert>
#include <cstddef>
#include <string>
#include <utility>
#include <iostream>

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;
    };
    // Шаблон класса «Базовый Итератор».
    // Определяет поведение итератора на элементы односвязного списка
    // ValueType — совпадает с Type (для Iterator) либо с const Type (для ConstIterator)
    template <typename ValueType>
    class BasicIterator {
        // Класс списка объявляется дружественным, чтобы из методов списка
        // был доступ к приватной области итератора
        friend class SingleLinkedList;

        // Конвертирующий конструктор итератора из указателя на узел списка
        explicit BasicIterator(Node* node):node_(node) {
        }

    public:
        // Объявленные ниже типы сообщают стандартной библиотеке о свойствах этого итератора

        // Категория итератора — forward iterator
        // (итератор, который поддерживает операции инкремента и многократное разыменование)
        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;

        // Конвертирующий конструктор/конструктор копирования
        // При ValueType, совпадающем с Type, играет роль копирующего конструктора
        // При ValueType, совпадающем с const Type, играет роль конвертирующего конструктора
        BasicIterator(const BasicIterator<Type>& other) noexcept {
            node_ = (Node*)other.node_;
        }

        // Чтобы компилятор не выдавал предупреждение об отсутствии оператора = при наличии
        // пользовательского конструктора копирования, явно объявим оператор = и
        // попросим компилятор сгенерировать его за нас
        BasicIterator& operator=(const BasicIterator& rhs) = default;

        // Оператор сравнения итераторов (в роли второго аргумента выступает константный итератор)
        // Два итератора равны, если они ссылаются на один и тот же элемент списка либо на end()
        [[nodiscard]] bool operator==(const BasicIterator<const Type>& rhs) const noexcept {
            return node_ == (Node*)rhs.node_;
        }

        // Оператор проверки итераторов на неравенство
        // Противоположен !=
        [[nodiscard]] bool operator!=(const BasicIterator<const Type>& rhs) const noexcept {
            return node_ != (Node*)rhs.node_;
        }

        // Оператор сравнения итераторов (в роли второго аргумента итератор)
        // Два итератора равны, если они ссылаются на один и тот же элемент списка либо на end()
        [[nodiscard]] bool operator==(const BasicIterator<Type>& rhs) const noexcept {
            return node_ == (Node*)rhs.node_;
        }

        // Оператор проверки итераторов на неравенство
        // Противоположен !=
        [[nodiscard]] bool operator!=(const BasicIterator<Type>& rhs) const noexcept {
            return node_ != (Node*)rhs.node_;
        }

        // Оператор прединкремента. После его вызова итератор указывает на следующий элемент списка
        // Возвращает ссылку на самого себя
        // Инкремент итератора, не указывающего на существующий элемент списка, приводит к неопределённому поведению
        BasicIterator& operator++() noexcept {
            node_ = node_->next_node;
            return *this;
        }

        // Оператор постинкремента. После его вызова итератор указывает на следующий элемент списка
        // Возвращает прежнее значение итератора
        // Инкремент итератора, не указывающего на существующий элемент списка,
        // приводит к неопределённому поведению
        BasicIterator operator++(int) noexcept {
            BasicIterator temp;
            temp.node_ = node_;
            ++this->node_;
            return temp;
        }

        // Операция разыменования. Возвращает ссылку на текущий элемент
        // Вызов этого оператора у итератора, не указывающего на существующий элемент списка,
        // приводит к неопределённому поведению
        [[nodiscard]] reference operator*() const noexcept {
            return node_->value;
        }

        // Операция доступа к члену класса. Возвращает указатель на текущий элемент списка
        // Вызов этого оператора у итератора, не указывающего на существующий элемент списка,
        // приводит к неопределённому поведению
        [[nodiscard]] pointer operator->() const noexcept {
            return &node_->value;
        }

    private:
        Node* node_ = nullptr;
    };

public:


    SingleLinkedList() :size_(0) {}
    ~SingleLinkedList() {
        Clear();
    }
    // Возвращает количество элементов в списке за время O(1)
    [[nodiscard]] size_t GetSize() const noexcept {
        return size_;
    }

    // Сообщает, пустой ли список за время O(1)
    [[nodiscard]] bool IsEmpty() const noexcept {

        return !(bool)size_;
    }

    // Вставляет элемент value в начало списка за время O(1)
    void PushFront(const Type& value) {
        Node* n = new Node(value, head_.next_node);
        head_.next_node = n;
        size_++;
    }

    // Очищает список за время O(N)
    void Clear() noexcept {
        while (head_.next_node != nullptr) {
            Node* temp = head_.next_node;
            head_.next_node = temp->next_node;
            delete temp;
        }
        size_ = 0;
    }

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

    // Итератор, допускающий изменение элементов списка
    using Iterator = BasicIterator<Type>;
    // Константный итератор, предоставляющий доступ для чтения к элементам списка
    using ConstIterator = BasicIterator<const Type>;

    // Возвращает итератор, ссылающийся на первый элемент
    // Если список пустой, возвращённый итератор будет равен end()
    [[nodiscard]] Iterator begin() noexcept {
        if (size_ == 0)
            return end();
        return Iterator(head_.next_node);
    }

    // Возвращает итератор, указывающий на позицию, следующую за последним элементом односвязного списка
    // Разыменовывать этот итератор нельзя — попытка разыменования приведёт к неопределённому поведению
    [[nodiscard]] Iterator end() noexcept {
        if (size_ > 0) {
            Iterator it(head_.next_node);
            while (it.node_ != nullptr)
                ++it;
            return it;
        }
        else {
            return Iterator();
        }
    }

    // Возвращает константный итератор, ссылающийся на первый элемент
    // Если список пустой, возвращённый итератор будет равен end()
    // Результат вызова эквивалентен вызову метода cbegin()
    [[nodiscard]] ConstIterator begin() const noexcept {
        if (size_ == 0)
            return end();
        return Iterator(head_.next_node);
    }

    // Возвращает константный итератор, указывающий на позицию, следующую за последним элементом односвязного списка
    // Разыменовывать этот итератор нельзя — попытка разыменования приведёт к неопределённому поведению
    // Результат вызова эквивалентен вызову метода cend()
    [[nodiscard]] ConstIterator end() const noexcept {
        auto it = begin();
        while (it.node_ != nullptr)
            ++it;
        return ++it;
    }

    // Возвращает константный итератор, ссылающийся на первый элемент
    // Если список пустой, возвращённый итератор будет равен cend()
    [[nodiscard]] ConstIterator cbegin() const noexcept {
        if (size_ == 0)
            return end();
        return ConstIterator(head_.next_node);
    }

    [[nodiscard]] ConstIterator cend() const noexcept {
        auto it = begin();
        while (it.node_ != nullptr)
            ++it;
        return ++it;
    }

    private:
        // Фиктивный узел, используется для вставки "перед первым элементом"
        Node head_;
        size_t size_;
};

    // Эта функция тестирует работу SingleLinkedList
    void Test1() {
        // Шпион, следящий за своим удалением
        struct DeletionSpy {
            DeletionSpy() = default;
            explicit DeletionSpy(int& instance_counter) noexcept
                : instance_counter_ptr_(&instance_counter)  //
            {
                OnAddInstance();
            }
            DeletionSpy(const DeletionSpy& other) noexcept
                : instance_counter_ptr_(other.instance_counter_ptr_)  //
            {
                OnAddInstance();
            }
            DeletionSpy& operator=(const DeletionSpy& rhs) noexcept {
                if (this != &rhs) {
                    auto rhs_copy(rhs);
                    std::swap(instance_counter_ptr_, rhs_copy.instance_counter_ptr_);
                }
                return *this;
            }
            ~DeletionSpy() {
                OnDeleteInstance();
            }

        private:
            void OnAddInstance() noexcept {
                if (instance_counter_ptr_) {
                    ++(*instance_counter_ptr_);
                }
            }
            void OnDeleteInstance() noexcept {
                if (instance_counter_ptr_) {
                    assert(*instance_counter_ptr_ != 0);
                    --(*instance_counter_ptr_);
                }
            }

            int* instance_counter_ptr_ = nullptr;
        };

        // Проверка вставки в начало
        {
            SingleLinkedList<int> l;
            assert(l.IsEmpty());
            assert(l.GetSize() == 0u);

            l.PushFront(0);
            l.PushFront(1);
            assert(l.GetSize() == 2);
            assert(!l.IsEmpty());

            l.Clear();
            assert(l.GetSize() == 0);
            assert(l.IsEmpty());
        }

        // Проверка фактического удаления элементов
        {
            int item0_counter = 0;
            int item1_counter = 0;
            int item2_counter = 0;
            {
                SingleLinkedList<DeletionSpy> list;
                list.PushFront(DeletionSpy{ item0_counter });
                list.PushFront(DeletionSpy{ item1_counter });
                list.PushFront(DeletionSpy{ item2_counter });

                assert(item0_counter == 1);
                assert(item1_counter == 1);
                assert(item2_counter == 1);
                list.Clear();
                assert(item0_counter == 0);
                assert(item1_counter == 0);
                assert(item2_counter == 0);

                list.PushFront(DeletionSpy{ item0_counter });
                list.PushFront(DeletionSpy{ item1_counter });
                list.PushFront(DeletionSpy{ item2_counter });
                assert(item0_counter == 1);
                assert(item1_counter == 1);
                assert(item2_counter == 1);
            }
            assert(item0_counter == 0);
            assert(item1_counter == 0);
            assert(item2_counter == 0);
        }

        // Вспомогательный класс, бросающий исключение после создания N-копии
        struct ThrowOnCopy {
            ThrowOnCopy() = default;
            explicit ThrowOnCopy(int& copy_counter) noexcept
                : countdown_ptr(&copy_counter) {
            }
            ThrowOnCopy(const ThrowOnCopy& other)
                : countdown_ptr(other.countdown_ptr)  //
            {
                if (countdown_ptr) {
                    if (*countdown_ptr == 0) {
                        throw std::bad_alloc();
                    }
                    else {
                        --(*countdown_ptr);
                    }
                }
            }
            // Присваивание элементов этого типа не требуется
            ThrowOnCopy& operator=(const ThrowOnCopy& rhs) = delete;
            // Адрес счётчика обратного отсчёта. Если не равен nullptr, то уменьшается при каждом копировании.
            // Как только обнулится, конструктор копирования выбросит исключение
            int* countdown_ptr = nullptr;
        };

        {
            bool exception_was_thrown = false;
            // Последовательно уменьшаем счётчик копирований до нуля, пока не будет выброшено исключение
            for (int max_copy_counter = 5; max_copy_counter >= 0; --max_copy_counter) {
                // Создаём непустой список
                SingleLinkedList<ThrowOnCopy> list;
                list.PushFront(ThrowOnCopy{});
                try {
                    int copy_counter = max_copy_counter;
                    list.PushFront(ThrowOnCopy(copy_counter));
                    // Если метод не выбросил исключение, список должен перейти в новое состояние
                    assert(list.GetSize() == 2);
                }
                catch (const std::bad_alloc&) {
                    exception_was_thrown = true;
                    // После выбрасывания исключения состояние списка должно остаться прежним
                    assert(list.GetSize() == 1);
                    break;
                }
            }
            assert(exception_was_thrown);
        }
    }

    void Test0() {
        using namespace std;
        {
            const SingleLinkedList<int> empty_int_list;
            assert(empty_int_list.GetSize() == 0u);
            assert(empty_int_list.IsEmpty());
        }

        {
            const SingleLinkedList<string> empty_string_list;
            assert(empty_string_list.GetSize() == 0u);
            assert(empty_string_list.IsEmpty());
        }
    }

    int main() {
        Test0();
        Test1();
        SingleLinkedList<int> list;
        list.PushFront(5);

        for (int el : list) {
            std::cout << el << ' ';
        }
    }