Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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;
- };
- template <typename ValueType>
- class BasicIterator {
- friend class SingleLinkedList;
- explicit BasicIterator(Node* node) {
- // assert(false);
- 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;
- BasicIterator(const BasicIterator<Type>& other) noexcept
- {
- // assert(false);
- // Реализуйте конструктор самостоятельно
- node_=other.node_;
- }
- // Чтобы компилятор не выдавал предупреждение об отсутствии оператора = при наличии
- // пользовательского конструктора копирования, явно объявим оператор = и
- // попросим компилятор сгенерировать его за нас
- BasicIterator& operator=(const BasicIterator& rhs) = default;
- // Оператор сравнения итераторов (в роли второго аргумента выступает константный итератор)
- // Два итератора равны, если они ссылаются на один и тот же элемент списка либо на end()
- [[nodiscard]] bool operator==(const BasicIterator<const Type>& rhs) const noexcept {
- // assert(false);
- // Заглушка. Реализуйте оператор самостоятельно
- return node_ == rhs.node_;
- }
- // Оператор проверки итераторов на неравенство
- // Противоположен !=
- [[nodiscard]] bool operator!=(const BasicIterator<const Type>& rhs) const noexcept {
- // assert(false);
- // Заглушка. Реализуйте оператор самостоятельно
- return node_ != rhs.node_;
- }
- // Оператор сравнения итераторов (в роли второго аргумента итератор)
- // Два итератора равны, если они ссылаются на один и тот же элемент списка либо на end()
- [[nodiscard]] bool operator==(const BasicIterator<Type>& rhs) const noexcept {
- // assert(false);
- // Заглушка. Реализуйте оператор самостоятельно
- return node_ == rhs.node_;
- }
- // Оператор проверки итераторов на неравенство
- // Противоположен !=
- [[nodiscard]] bool operator!=(const BasicIterator<Type>& rhs) const noexcept {
- // assert(false);
- // Заглушка. Реализуйте оператор самостоятельно
- return node_ != rhs.node_;
- }
- BasicIterator& operator++() noexcept {
- // assert(false);
- // Заглушка. Реализуйте оператор самостоятельно
- if(node_){
- node_=node_->next_node;
- }
- return *this;
- }
- BasicIterator operator++(int) noexcept {
- // assert(false);
- // Заглушка. Реализуйте оператор самостоятельно
- auto old_value(*this);
- ++(*this);
- return old_value;
- }
- [[nodiscard]] reference operator*() const noexcept {
- // assert(false);
- // Не реализовано
- // Заглушка. Реализуйте оператор самостоятельно
- return node_->value;
- }
- [[nodiscard]] pointer operator->() const noexcept {
- // assert(false);
- // Заглушка. Реализуйте оператор самостоятельно
- 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>;
- // Возвращает итератор, ссылающийся на первый элемент
- // Если список пустой, возвращённый итератор будет равен end()
- [[nodiscard]] Iterator begin() noexcept {
- //assert(false);
- // Реализуйте самостоятельно
- return Iterator{head_.next_node};
- }
- // Возвращает итератор, указывающий на позицию, следующую за последним элементом односвязного списка
- // Разыменовывать этот итератор нельзя — попытка разыменования приведёт к неопределённому поведению
- [[nodiscard]] Iterator end() noexcept {
- //assert(false);
- // Реализуйте самостоятельно
- Node * curr=&head_;
- while(curr){
- curr=curr->next_node;
- }
- return Iterator{curr};
- }
- // Возвращает константный итератор, ссылающийся на первый элемент
- // Если список пустой, возвращённый итератор будет равен end()
- // Результат вызова эквивалентен вызову метода cbegin()
- [[nodiscard]] ConstIterator begin() const noexcept {
- // assert(false);
- // Реализуйте самостоятельно
- return Iterator{head_.next_node};
- }
- // Возвращает константный итератор, указывающий на позицию, следующую за последним элементом односвязного списка
- // Разыменовывать этот итератор нельзя — попытка разыменования приведёт к неопределённому поведению
- // Результат вызова эквивалентен вызову метода cend()
- [[nodiscard]] ConstIterator end() const noexcept {
- // assert(false);
- // Реализуйте самостоятельно
- BasicIterator<const Type> it;
- while(it.node_){
- ++it;
- }
- return it;
- }
- // Возвращает константный итератор, ссылающийся на первый элемент
- // Если список пустой, возвращённый итератор будет равен cend()
- [[nodiscard]] ConstIterator cbegin() const noexcept {
- // assert(false);
- // Реализуйте самостоятельно
- return {head_.next_node};
- }
- // Возвращает константный итератор, указывающий на позицию, следующую за последним элементом односвязного списка
- // Разыменовывать этот итератор нельзя — попытка разыменования приведёт к неопределённому поведению
- [[nodiscard]] ConstIterator cend() const noexcept {
- // assert(false);
- // Реализуйте самостоятельно
- BasicIterator<const Type> it;
- while(it.node_){
- ++it;
- }
- return it;
- }
- SingleLinkedList() {
- size_=0;
- }
- SingleLinkedList(const std::initializer_list<Type>& items)
- {
- size_ = 0;
- SingleLinkedList reversed;
- for(Type item: items) {
- reversed.PushFront(item);
- }
- for(Type item: reversed) {
- PushFront(item);
- }
- }
- SingleLinkedList(const SingleLinkedList& other) {
- if(size_ == 0 && head_.next_node == nullptr) {
- SingleLinkedList tmp;
- SingleLinkedList reversed;
- for(auto item: other) {
- reversed.PushFront(item);
- }
- for(auto item: reversed) {
- tmp.PushFront(item);
- }
- swap(tmp);
- }
- }
- SingleLinkedList& operator=(const SingleLinkedList& rhs){
- SingleLinkedList rhs_copy(rhs);
- if(this->head_.next_node!=rhs_copy.head_.next_node){
- swap(rhs_copy);
- }
- return *this;
- }
- ~SingleLinkedList(){
- Clear();
- }
- void PushFront(const Type& value){
- head_.next_node = new Node(value, head_.next_node);
- ++size_;
- }
- void Clear(){
- while(head_.next_node) {
- Node* next_node_new = head_.next_node->next_node;
- delete head_.next_node;
- head_.next_node = next_node_new;
- --size_;
- }
- }
- // Возвращает количество элементов в списке за время O(1)
- [[nodiscard]] size_t GetSize() const noexcept {
- // Заглушка. Реализуйте метод самостоятельно
- //assert(false);
- //return 42;
- return size_;
- }
- // Сообщает, пустой ли список за время O(1)
- [[nodiscard]] bool IsEmpty() const noexcept {
- // Заглушка. Реализуйте метод самостоятельно
- //assert(false);
- //return false;
- return size_==0;
- }
- [[nodiscard]] bool operator==(const SingleLinkedList<Type>& rhs) const noexcept {
- return std::equal(begin(),end(), rhs.begin());
- }
- [[nodiscard]] bool operator!=(const SingleLinkedList<Type>& rhs) const noexcept {
- return !(*this==rhs);
- }
- [[nodiscard]] bool operator<(const SingleLinkedList<Type>& rhs) const noexcept {
- return std::lexicographical_compare(
- begin(), end(),
- rhs.begin(), rhs.end()
- );
- }
- [[nodiscard]] bool operator<=(const SingleLinkedList<Type>& rhs) const noexcept {
- return (*this<rhs) || (*this==rhs);
- }
- [[nodiscard]] bool operator>(const SingleLinkedList<Type>& rhs) const noexcept {
- return (rhs<*this);
- }
- [[nodiscard]] bool operator>=(const SingleLinkedList<Type>& rhs) const noexcept {
- return (*this>rhs) || (*this==rhs);
- }
- void swap(SingleLinkedList& other) noexcept {
- std::swap(head_.next_node, other.head_.next_node);
- std::swap(size_, other.size_);
- }
- void PopFront() noexcept {
- Node* ptr = head_.next_node;
- if(!ptr){
- return;
- }
- head_.next_node = head_.next_node->next_node;
- delete ptr;
- }
- void EraseAfter(const BasicIterator<Type>& before) noexcept {
- Node* tmp = before.node_->next_node;
- if(!tmp){
- return;
- }
- before.node_->next_node=before.node_->next_node->next_node;
- delete tmp;
- }
- Iterator InsertAfter(
- const BasicIterator<Type>& before,
- Type value
- )
- {
- Node* ptr_new = new Node(
- value,
- before.node_->next_node
- );
- before.node_->next_node = ptr_new;
- return {ptr_new};
- }
- [[nodiscard]] Iterator before_begin() noexcept {
- return {head_};
- }
- [[nodiscard]] Iterator cbefore_begin() const noexcept {
- return {head_};
- }
- [[nodiscard]] ConstIterator before_begin() const noexcept {
- return {head_};
- }
- private:
- // Фиктивный узел, используется для вставки "перед первым элементом"
- Node head_;
- size_t size_=0;
- };
- template <typename Type>
- void swap(SingleLinkedList<Type>& lhs, SingleLinkedList<Type>& rhs) noexcept {
- lhs.swap(rhs);
- }
- 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());
- }
- }
- // Эта функция тестирует работу SingleLinkedList
- void Test2() {
- // Итерирование по пустому списку
- {
- SingleLinkedList<int> list;
- // Константная ссылка для доступа к константным версиям begin()/end()
- const auto& const_list = list;
- // Итераторы begin и end у пустого диапазона равны друг другу
- assert(list.begin() == list.end());
- assert(const_list.begin() == const_list.end());
- assert(list.cbegin() == list.cend());
- assert(list.cbegin() == const_list.begin());
- assert(list.cend() == const_list.end());
- }
- // Итерирование по непустому списку
- {
- SingleLinkedList<int> list;
- const auto& const_list = list;
- list.PushFront(1);
- assert(list.GetSize() == 1u);
- assert(!list.IsEmpty());
- assert(const_list.begin() != const_list.end());
- assert(const_list.cbegin() != const_list.cend());
- assert(list.begin() != list.end());
- assert(const_list.begin() == const_list.cbegin());
- assert(*list.cbegin() == 1);
- *list.begin() = -1;
- assert(*list.cbegin() == -1);
- const auto old_begin = list.cbegin();
- list.PushFront(2);
- assert(list.GetSize() == 2);
- const auto new_begin = list.cbegin();
- assert(new_begin != old_begin);
- // Проверка прединкремента
- {
- auto new_begin_copy(new_begin);
- assert((++(new_begin_copy)) == old_begin);
- }
- // Проверка постинкремента
- {
- auto new_begin_copy(new_begin);
- assert(((new_begin_copy)++) == new_begin);
- assert(new_begin_copy == old_begin);
- }
- // Итератор, указывающий на позицию после последнего элемента, равен итератору end()
- {
- auto old_begin_copy(old_begin);
- assert((++old_begin_copy) == list.end());
- }
- }
- // Преобразование итераторов
- {
- SingleLinkedList<int> list;
- list.PushFront(1);
- // Конструирование ConstIterator из Iterator
- SingleLinkedList<int>::ConstIterator const_it(list.begin());
- assert(const_it == list.cbegin());
- assert(*const_it == *list.cbegin());
- SingleLinkedList<int>::ConstIterator const_it1;
- // Присваивание ConstIterator'у значения Iterator
- const_it1 = list.begin();
- assert(const_it1 == const_it);
- }
- // Проверка оператора ->
- {
- using namespace std;
- SingleLinkedList<std::string> string_list;
- string_list.PushFront("one"s);
- assert(string_list.cbegin()->length() == 3u);
- string_list.begin()->push_back('!');
- assert(*string_list.begin() == "one!"s);
- }
- }
- // Эта функция проверяет работу класса SingleLinkedList
- void Test3() {
- // Проверка списков на равенство и неравенство
- {
- SingleLinkedList<int> list_1;
- list_1.PushFront(1);
- list_1.PushFront(2);
- SingleLinkedList<int> list_2;
- list_2.PushFront(1);
- list_2.PushFront(2);
- list_2.PushFront(3);
- SingleLinkedList<int> list_1_copy;
- list_1_copy.PushFront(1);
- list_1_copy.PushFront(2);
- SingleLinkedList<int> empty_list;
- SingleLinkedList<int> another_empty_list;
- // Список равен самому себе
- assert(list_1 == list_1);
- assert(empty_list == empty_list);
- // Списки с одинаковым содержимым равны, а с разным - не равны
- assert(list_1 == list_1_copy);
- assert(list_1 != list_2);
- assert(list_2 != list_1);
- assert(empty_list == another_empty_list);
- }
- // Обмен содержимого списков
- {
- SingleLinkedList<int> first;
- first.PushFront(1);
- first.PushFront(2);
- SingleLinkedList<int> second;
- second.PushFront(10);
- second.PushFront(11);
- second.PushFront(15);
- const auto old_first_begin = first.begin();
- const auto old_second_begin = second.begin();
- const auto old_first_size = first.GetSize();
- const auto old_second_size = second.GetSize();
- first.swap(second);
- assert(second.begin() == old_first_begin);
- assert(first.begin() == old_second_begin);
- assert(second.GetSize() == old_first_size);
- assert(first.GetSize() == old_second_size);
- // Обмен при помощи функции swap
- {
- using std::swap;
- // В отсутствие пользовательской перегрузки будет вызвана функция std::swap, которая
- // выполнит обмен через создание временной копии
- swap(first, second);
- // Убеждаемся, что используется не std::swap, а пользовательская перегрузка
- // Если бы обмен был выполнен с созданием временной копии,
- // то итератор first.begin() не будет равен ранее сохранённому значению,
- // так как копия будет хранить свои узлы по иным адресам
- assert(first.begin() == old_first_begin);
- assert(second.begin() == old_second_begin);
- assert(first.GetSize() == old_first_size);
- assert(second.GetSize() == old_second_size);
- }
- }
- // Инициализация списка при помощи std::initializer_list
- {
- SingleLinkedList<int> list{1, 2, 3, 4, 5};
- assert(list.GetSize() == 5);
- assert(!list.IsEmpty());
- assert(std::equal(list.begin(), list.end(), std::begin({1, 2, 3, 4, 5})));
- }
- // Лексикографическое сравнение списков
- {
- using IntList = SingleLinkedList<int>;
- assert((IntList{1, 2, 3} < IntList{1, 2, 3, 1}));
- assert((IntList{1, 2, 3} <= IntList{1, 2, 3}));
- assert((IntList{1, 2, 4} > IntList{1, 2, 3}));
- assert((IntList{1, 2, 3} >= IntList{1, 2, 3}));
- }
- // Копирование списков
- {
- const SingleLinkedList<int> empty_list{};
- // Копирование пустого списка
- {
- auto list_copy(empty_list);
- assert(list_copy.IsEmpty());
- }
- SingleLinkedList<int> non_empty_list{1, 2, 3, 4};
- // Копирование непустого списка
- {
- auto list_copy(non_empty_list);
- assert(non_empty_list.begin() != list_copy.begin());
- assert(list_copy == non_empty_list);
- }
- }
- // Присваивание списков
- {
- const SingleLinkedList<int> source_list{1, 2, 3, 4};
- SingleLinkedList<int> receiver{5, 4, 3, 2, 1};
- receiver = source_list;
- assert(receiver.begin() != source_list.begin());
- assert(receiver == source_list);
- }
- // Вспомогательный класс, бросающий исключение после создания N-копии
- struct ThrowOnCopy {
- ThrowOnCopy() = default;
- explicit ThrowOnCopy(int& copy_counter) noexcept
- : countdown_ptr(©_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;
- };
- // Безопасное присваивание списков
- {
- SingleLinkedList<ThrowOnCopy> src_list;
- src_list.PushFront(ThrowOnCopy{});
- src_list.PushFront(ThrowOnCopy{});
- auto thrower = src_list.begin();
- src_list.PushFront(ThrowOnCopy{});
- int copy_counter = 0; // при первом же копировании будет выброшего исключение
- thrower->countdown_ptr = ©_counter;
- SingleLinkedList<ThrowOnCopy> dst_list;
- dst_list.PushFront(ThrowOnCopy{});
- int dst_counter = 10;
- dst_list.begin()->countdown_ptr = &dst_counter;
- dst_list.PushFront(ThrowOnCopy{});
- try {
- dst_list = src_list;
- // Ожидается исключение при присваивании
- assert(false);
- } catch (const std::bad_alloc&) {
- // Проверяем, что состояние списка-приёмника не изменилось
- // при выбрасывании исключений
- assert(dst_list.GetSize() == 2);
- auto it = dst_list.begin();
- assert(it != dst_list.end());
- assert(it->countdown_ptr == nullptr);
- ++it;
- assert(it != dst_list.end());
- assert(it->countdown_ptr == &dst_counter);
- assert(dst_counter == 10);
- } catch (...) {
- // Других типов исключений не ожидается
- assert(false);
- }
- }
- }
- // Эта функция проверяет работу класса SingleLinkedList
- void Test4() {
- struct DeletionSpy {
- ~DeletionSpy() {
- if (deletion_counter_ptr) {
- ++(*deletion_counter_ptr);
- }
- }
- int* deletion_counter_ptr = nullptr;
- };
- // Проверка PopFront
- {
- SingleLinkedList<int> numbers{3, 14, 15, 92, 6};
- numbers.PopFront();
- assert((numbers == SingleLinkedList<int>{14, 15, 92, 6}));
- SingleLinkedList<DeletionSpy> list;
- list.PushFront(DeletionSpy{});
- int deletion_counter = 0;
- list.begin()->deletion_counter_ptr = &deletion_counter;
- assert(deletion_counter == 0);
- list.PopFront();
- assert(deletion_counter == 1);
- }
- // Доступ к позиции, предшествующей begin
- {
- SingleLinkedList<int> empty_list;
- const auto& const_empty_list = empty_list;
- assert(empty_list.before_begin() == empty_list.cbefore_begin());
- assert(++empty_list.before_begin() == empty_list.begin());
- assert(++empty_list.cbefore_begin() == const_empty_list.begin());
- SingleLinkedList<int> numbers{1, 2, 3, 4};
- const auto& const_numbers = numbers;
- assert(numbers.before_begin() == numbers.cbefore_begin());
- assert(++numbers.before_begin() == numbers.begin());
- assert(++numbers.cbefore_begin() == const_numbers.begin());
- }
- // Вставка элемента после указанной позиции
- { // Вставка в пустой список
- {
- SingleLinkedList<int> lst;
- const auto inserted_item_pos = lst.InsertAfter(lst.before_begin(), 123);
- assert((lst == SingleLinkedList<int>{123}));
- assert(inserted_item_pos == lst.begin());
- assert(*inserted_item_pos == 123);
- }
- // Вставка в непустой список
- {
- SingleLinkedList<int> lst{1, 2, 3};
- auto inserted_item_pos = lst.InsertAfter(lst.before_begin(), 123);
- assert(inserted_item_pos == lst.begin());
- assert(inserted_item_pos != lst.end());
- assert(*inserted_item_pos == 123);
- assert((lst == SingleLinkedList<int>{123, 1, 2, 3}));
- inserted_item_pos = lst.InsertAfter(lst.begin(), 555);
- assert(++SingleLinkedList<int>::Iterator(lst.begin()) == inserted_item_pos);
- assert(*inserted_item_pos == 555);
- assert((lst == SingleLinkedList<int>{123, 555, 1, 2, 3}));
- };
- }
- // Вспомогательный класс, бросающий исключение после создания N-копии
- struct ThrowOnCopy {
- ThrowOnCopy() = default;
- explicit ThrowOnCopy(int& copy_counter) noexcept
- : countdown_ptr(©_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 = 10; max_copy_counter >= 0; --max_copy_counter) {
- SingleLinkedList<ThrowOnCopy> list{ThrowOnCopy{}, ThrowOnCopy{}, ThrowOnCopy{}};
- try {
- int copy_counter = max_copy_counter;
- list.InsertAfter(list.cbegin(), ThrowOnCopy(copy_counter));
- assert(list.GetSize() == 4u);
- } catch (const std::bad_alloc&) {
- exception_was_thrown = true;
- assert(list.GetSize() == 3u);
- break;
- }
- }
- assert(exception_was_thrown);
- }
- // Удаление элементов после указанной позиции
- {
- {
- SingleLinkedList<int> lst{1, 2, 3, 4};
- const auto& const_lst = lst;
- const auto item_after_erased = lst.EraseAfter(const_lst.cbefore_begin());
- assert((lst == SingleLinkedList<int>{2, 3, 4}));
- assert(item_after_erased == lst.begin());
- }
- {
- SingleLinkedList<int> lst{1, 2, 3, 4};
- const auto item_after_erased = lst.EraseAfter(lst.cbegin());
- assert((lst == SingleLinkedList<int>{1, 3, 4}));
- assert(item_after_erased == (++lst.begin()));
- }
- {
- SingleLinkedList<int> lst{1, 2, 3, 4};
- const auto item_after_erased = lst.EraseAfter(++(++lst.cbegin()));
- assert((lst == SingleLinkedList<int>{1, 2, 3}));
- assert(item_after_erased == lst.end());
- }
- {
- SingleLinkedList<DeletionSpy> list{DeletionSpy{}, DeletionSpy{}, DeletionSpy{}};
- auto after_begin = ++list.begin();
- int deletion_counter = 0;
- after_begin->deletion_counter_ptr = &deletion_counter;
- assert(deletion_counter == 0u);
- list.EraseAfter(list.cbegin());
- assert(deletion_counter == 1u);
- }
- }
- }
- int main() {
- Test4();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement