API tools faq
paste
Advertisement
kutuzzzov

Урок 9 Исправляем список

kutuzzzov
Dec 20th, 2022
2,663
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 19.52 KB | None | 0 0
raw download clone embed print report
  1. // main.cpp
  2.  
  3. #include "list.h"
  4.  
  5. #include <cassert>
  6. #include <vector>
  7.  
  8. using namespace std;
  9.  
  10. // функция возвращает функциональный объект,
  11. // выполняющий вставку в выбранный список
  12. template <class Type>
  13. auto MakeInsertingFunction(vector<SingleLinkedList<Type>>& lists, const int& x) {
  14.     return [&](const Type& value) {
  15.         lists.at(x).PushFront(value);
  16.     };
  17. }
  18.  
  19. template <class T>
  20. void InsertRange(int from, int to, T push_function) {
  21.     for (int i = from; i < to; ++i) {
  22.         push_function(i);
  23.     }
  24. }
  25.  
  26. int main() {
  27.     // main тестирует вектор, в нём нет ошибок.
  28.     // не меняйте код этой функции
  29.     // помимо этих тестов, список должен проходить все обычные тесты списка.
  30.     // Ищите ошибки в коде списка и
  31.     // других функциях этого файла
  32.  
  33.     vector<SingleLinkedList<int>> lists_a(10);
  34.  
  35.     auto push_to_2a = MakeInsertingFunction(lists_a, 2);
  36.     auto push_to_5a = MakeInsertingFunction(lists_a, 5);
  37.     auto push_to_7a = MakeInsertingFunction(lists_a, 7);
  38.  
  39.     InsertRange(10, 12, push_to_2a);
  40.     InsertRange(12, 14, push_to_5a);
  41.     InsertRange(14, 16, push_to_7a);
  42.  
  43.     assert(lists_a[2] == SingleLinkedList<int>({11, 10}));
  44.     assert(lists_a[5] == SingleLinkedList<int>({13, 12}));
  45.     assert(lists_a[7] == SingleLinkedList<int>({15, 14}));
  46.  
  47.     vector<SingleLinkedList<int>> lists_b = lists_a;
  48.  
  49.     auto push_to_2b = MakeInsertingFunction(lists_b, 2);
  50.     auto push_to_5b = MakeInsertingFunction(lists_b, 5);
  51.     auto push_to_7b = MakeInsertingFunction(lists_b, 7);
  52.  
  53.     InsertRange(20, 22, push_to_2b);
  54.     InsertRange(22, 24, push_to_5b);
  55.     InsertRange(24, 26, push_to_7b);
  56.  
  57.     assert(lists_b[2] == SingleLinkedList<int>({21, 20, 11, 10}));
  58.     assert(lists_b[5] == SingleLinkedList<int>({23, 22, 13, 12}));
  59.     assert(lists_b[7] == SingleLinkedList<int>({25, 24, 15, 14}));
  60.  
  61.     lists_a[2].PopFront();
  62.     lists_a[5].InsertAfter(lists_a[5].begin(), 100);
  63.     lists_b[5].EraseAfter(next(lists_b[5].begin()));
  64.     lists_b[7].Clear();
  65.  
  66.     assert(lists_a[2] == SingleLinkedList<int>({10}));
  67.     assert(lists_a[5] == SingleLinkedList<int>({13, 100, 12}));
  68.     assert(lists_b[5] == SingleLinkedList<int>({23, 22, 12}));
  69.     assert(lists_b[7] == SingleLinkedList<int>());
  70. }
  71.  
  72. // list.h
  73.  
  74. #pragma once
  75.  
  76. #include <cassert>
  77. #include <cstddef>
  78. #include <iterator>
  79.  
  80. template <typename Type>
  81. class SingleLinkedList {
  82.     // Узел списка
  83.     struct Node {
  84.         Node() = default;
  85.         Node(const Type& val, Node* next)
  86.             : value(val)
  87.             , next_node(next) {
  88.         }
  89.         Type value{};
  90.         Node* next_node = nullptr;
  91.     };
  92.  
  93.     // Шаблон класса Базовый Итератор.
  94.     // Определяет поведение итератора на элементы односвязного списка
  95.     // ValueType - совпадает с Type (для Iterator) либо с const Type (для ConstIterator)
  96.     template <typename ValueType>
  97.     class BasicIterator {
  98.         // Класс списка объявляется дружественным, чтобы из методов списка
  99.         // был доступ к приватной области итератора
  100.         friend class SingleLinkedList;
  101.  
  102.         // Конвертирующий конструктор итератора из указателя на узел списка
  103.         explicit BasicIterator(Node* node) {
  104.             node_ = node;
  105.         }
  106.  
  107.     public:
  108.         // Объявленные ниже типы сообщают стандартной библиотеке о свойствах этого итератора
  109.  
  110.         // Категория итератора - forward iterator
  111.         // (итератор, который поддерживает операции инкремента и многократное разыменование)
  112.         using iterator_category = std::forward_iterator_tag;
  113.         // Тип элементов, по которым перемещается итератор
  114.         using value_type = Type;
  115.         // Тип, используемый для хранения смещения между итераторами
  116.         using difference_type = std::ptrdiff_t;
  117.         // Тип указателя на итерируемое значение
  118.         using pointer = ValueType*;
  119.         // Тип ссылки на итерируемое значение
  120.         using reference = ValueType&;
  121.  
  122.         BasicIterator() = default;
  123.  
  124.         // Конвертирующий конструктор/конструктор копирования
  125.         // При ValueType, совпадающем с Type, играет роль копирующего конструктора
  126.         // При ValueType, совпадающем с const Type, играет роль конвертирующего конструктора
  127.         BasicIterator(const BasicIterator<Type>& other) noexcept {
  128.             node_ = other.node_;
  129.         }
  130.  
  131.         // Чтобы компилятор не выдавал предупреждение об отсутствии оператора = при наличии
  132.         // пользовательского конструктора копирования, явно объявим оператор = и
  133.         // попросим компилятор сгенерировать его за нас.
  134.         BasicIterator& operator=(const BasicIterator& rhs) = default;
  135.  
  136.         // Оператор сравнения итераторов (в роли второго аргумента выступает константный итератор)
  137.         // Два итератора равны, если они ссылаются на один и тот же элемент списка, либо на end()
  138.         [[nodiscard]] bool operator==(const BasicIterator<const Type>& rhs) const noexcept {
  139.             return this->node_ == rhs.node_;
  140.         }
  141.  
  142.         // Оператор проверки итераторов на неравенство
  143.         // Противоположен !=
  144.         [[nodiscard]] bool operator!=(const BasicIterator<const Type>& rhs) const noexcept {
  145.             return this->node_ != rhs.node_;
  146.         }
  147.  
  148.         // Оператор сравнения итераторов (в роли второго аргумента итератор)
  149.         // Два итератора равны, если они ссылаются на один и тот же элемент списка, либо на end()
  150.         [[nodiscard]] bool operator==(const BasicIterator<Type>& rhs) const noexcept {
  151.             return this->node_ == rhs.node_;
  152.         }
  153.  
  154.         // Оператор проверки итераторов на неравенство
  155.         // Противоположен !=
  156.         [[nodiscard]] bool operator!=(const BasicIterator<Type>& rhs) const noexcept {
  157.             return this->node_ != rhs.node_;
  158.         }
  159.  
  160.         // Оператор прединкремента. После его вызова итератор указывает на следующий элемент списка
  161.         // Возвращает ссылку на самого себя
  162.         // Инкремент итератора, не указывающего на существующий элемент списка, приводит к неопределённому поведению
  163.         BasicIterator& operator++() noexcept {
  164.             assert(node_ != nullptr);
  165.             node_ = node_->next_node;
  166.             return *this;
  167.         }
  168.        
  169.         // Оператор постинкремента. После его вызова итератор указывает на следующий элемент списка.
  170.         // Возвращает прежнее значение итератора
  171.         // Инкремент итератора, не указывающего на существующий элемент списка,
  172.         // приводит к неопределённому поведению
  173.         BasicIterator operator++(int) noexcept {
  174.             assert(node_ != nullptr);
  175.             auto old_value(*this);
  176.             node_ = node_->next_node;
  177.             return old_value;
  178.         }
  179.  
  180.         // Операция разыменования. Возвращает ссылку на текущий элемент
  181.         // Вызов этого оператора у итератора, не указывающего на существующий элемент списка,
  182.         // приводит к неопределённому поведению
  183.         [[nodiscard]] reference operator*() const noexcept {
  184.             assert(node_ != nullptr);
  185.             return node_->value;
  186.         }
  187.  
  188.         // Операция доступа к члену класса. Возвращает указатель на текущий элемент списка.
  189.         // Вызов этого оператора у итератора, не указывающего на существующий элемент списка,
  190.         // приводит к неопределённому поведению
  191.         [[nodiscard]] pointer operator->() const noexcept {
  192.             assert(node_ != nullptr);
  193.             return &node_->value;
  194.         }
  195.  
  196.     private:
  197.         Node* node_ = nullptr;
  198.     };
  199.  
  200. public:
  201.     SingleLinkedList() {
  202.     }
  203.  
  204.     // Возвращает количество элементов в списке за время O(1)
  205.     [[nodiscard]] size_t GetSize() const noexcept {
  206.         return size_;
  207.     }
  208.  
  209.     // Сообщает, пустой ли список за время O(1)
  210.     [[nodiscard]] bool IsEmpty() const noexcept {
  211.         return !(size_ != 0);
  212.     }
  213.  
  214.     // Вставляет элемент value в начало списка за время O(1)
  215.     void PushFront(const Type& value) {
  216.         head_.next_node = new Node(value, head_.next_node);
  217.         ++size_;
  218.     }
  219.  
  220.     // Очищает список за время O(N)
  221.     void Clear() noexcept {
  222.         while (head_.next_node != nullptr) {
  223.             Node* new_head = head_.next_node->next_node;
  224.             delete head_.next_node;
  225.             head_.next_node = new_head;
  226.         }
  227.         size_ = 0;
  228.     }
  229.  
  230.     ~SingleLinkedList() {
  231.         Clear();
  232.     }
  233.  
  234.     using value_type = Type;
  235.     using reference = value_type&;
  236.     using const_reference = const value_type&;
  237.  
  238.     // Итератор, допускающий изменение элементов списка
  239.     using Iterator = BasicIterator<Type>;
  240.     // Константный итератор, предоставляющий доступ для чтения к элементам списка
  241.     using ConstIterator = BasicIterator<const Type>;
  242.  
  243.     // Возвращает итератор, ссылающийся на первый элемент
  244.     // Если список пустой, возвращённый итератор будет равен end()
  245.     [[nodiscard]] Iterator begin() noexcept {
  246.         return Iterator{ head_.next_node };
  247.     }
  248.  
  249.     // Возвращает итератор, указывающий на позицию, следующую за последним элементом односвязного списка
  250.     // Разыменовывать этот итератор нельзя - попытка разыменования приведёт к неопределённому поведению
  251.     [[nodiscard]] Iterator end() noexcept {
  252.         return Iterator{ nullptr };
  253.     }
  254.  
  255.     // Возвращает константный итератор, ссылающийся на первый элемент
  256.     // Если список пустой, возвращённый итератор будет равен end()
  257.     // Результат вызова эквивалентен вызову метода cbegin()
  258.     [[nodiscard]] ConstIterator begin() const noexcept {
  259.         return cbegin();
  260.     }
  261.    
  262.     // Возвращает константный итератор, указывающий на позицию, следующую за последним элементом односвязного списка
  263.     // Разыменовывать этот итератор нельзя - попытка разыменования приведёт к неопределённому поведению
  264.     // Результат вызова эквивалентен вызову метода cend()
  265.     [[nodiscard]] ConstIterator end() const noexcept {
  266.         return ConstIterator{ nullptr };
  267.     }
  268.  
  269.     // Возвращает константный итератор, ссылающийся на первый элемент
  270.     // Если список пустой, возвращённый итератор будет равен cend()
  271.     [[nodiscard]] ConstIterator cbegin() const noexcept {
  272.         return ConstIterator{ head_.next_node };
  273.     }
  274.  
  275.     // Возвращает константный итератор, указывающий на позицию, следующую за последним элементом односвязного списка
  276.     // Разыменовывать этот итератор нельзя - попытка разыменования приведёт к неопределённому поведению
  277.     [[nodiscard]] ConstIterator cend() const noexcept {
  278.         return ConstIterator{ nullptr };
  279.     }
  280.  
  281.     SingleLinkedList(std::initializer_list<Type> values) {
  282.     // используем шаблонный метод реализации
  283.         Assign(values.begin(), values.end());
  284.     }
  285.  
  286.     SingleLinkedList(const SingleLinkedList& other) {
  287.     // используем шаблонный метод реализации
  288.         Assign(other.begin(), other.end());
  289.     }
  290.  
  291.     SingleLinkedList& operator=(const SingleLinkedList& rhs) {
  292.         if (this != &rhs) {
  293.             if (rhs.IsEmpty()) {
  294.                 Clear();
  295.             } else {
  296.                 auto rhs_copy(rhs);
  297.                 swap(rhs_copy);
  298.             }
  299.         }
  300.         return *this;
  301.     }
  302.  
  303.     // Обменивает содержимое списков за время O(1)
  304.     void swap(SingleLinkedList& other) noexcept {
  305.         std::swap(other.head_.next_node, head_.next_node);
  306.         std::swap(other.size_, size_);
  307.     }
  308.  
  309.     // Возвращает итератор, указывающий на позицию перед первым элементом односвязного списка.
  310.     // Разыменовывать этот итератор нельзя - попытка разыменования приведёт к неопределённому поведению
  311.     [[nodiscard]] Iterator before_begin() noexcept {
  312.         return Iterator{ &head_ };
  313.     }
  314.  
  315.     // Возвращает константный итератор, указывающий на позицию перед первым элементом односвязного списка.
  316.     // Разыменовывать этот итератор нельзя - попытка разыменования приведёт к неопределённому поведению
  317.     [[nodiscard]] ConstIterator cbefore_begin() const noexcept {
  318.         return ConstIterator{ const_cast<Node*>(&head_) };
  319.     }
  320.  
  321.     // Возвращает константный итератор, указывающий на позицию перед первым элементом односвязного списка.
  322.     // Разыменовывать этот итератор нельзя - попытка разыменования приведёт к неопределённому поведению
  323.     [[nodiscard]] ConstIterator before_begin() const noexcept {
  324.         return cbefore_begin();
  325.     }
  326.  
  327.     /*
  328.      * Вставляет элемент value после элемента, на который указывает pos.
  329.      * Возвращает итератор на вставленный элемент
  330.      * Если при создании элемента будет выброшено исключение, список останется в прежнем состоянии
  331.      */
  332.     Iterator InsertAfter(ConstIterator pos, const Type& value) {
  333.         assert(pos.node_ != nullptr);
  334.        
  335.         pos.node_->next_node = new Node(value, pos.node_->next_node);
  336.         ++size_;
  337.         return Iterator{ pos.node_->next_node };
  338.     }
  339.    
  340.     void PopFront() noexcept {
  341.         assert(!IsEmpty());
  342.        
  343.         Node* new_head = head_.next_node->next_node;
  344.         delete head_.next_node;
  345.         head_.next_node = new_head;
  346.         --size_;
  347.     }
  348.  
  349.     /*
  350.      * Удаляет элемент, следующий за pos.
  351.      * Возвращает итератор на элемент, следующий за удалённым
  352.      */
  353.     Iterator EraseAfter(ConstIterator pos) noexcept {
  354.         assert(!IsEmpty());
  355.        
  356.         Node* temp = pos.node_->next_node->next_node;
  357.         delete pos.node_->next_node;
  358.         pos.node_->next_node = temp;
  359.         --size_;
  360.  
  361.         return Iterator{ pos.node_->next_node };
  362.     }
  363.  
  364. private:
  365.     // Фиктивный узел, используется для вставки "перед первым элементом"
  366.     Node head_;
  367.     size_t size_ = 0;
  368.    
  369.     template <typename InputIterator>
  370.     void Assign(InputIterator from, InputIterator to) {
  371.         SingleLinkedList<Type> tmp;
  372.    
  373.         Node** node_ptr = &tmp.head_.next_node;
  374.         while (from != to) {
  375.             assert(*node_ptr == nullptr);
  376.        
  377.             *node_ptr = new Node(*from, nullptr);
  378.             ++tmp.size_;
  379.        
  380.             node_ptr = &((*node_ptr)->next_node);
  381.        
  382.             ++from;
  383.         }
  384.         swap(tmp);
  385.     }
  386. };
  387.  
  388. template <typename Type>
  389. void swap(SingleLinkedList<Type>& lhs, SingleLinkedList<Type>& rhs) noexcept {
  390.     lhs.swap(rhs);
  391. }
  392.  
  393. template <typename Type>
  394. bool operator==(const SingleLinkedList<Type>& lhs, const SingleLinkedList<Type>& rhs) {
  395.     return (&lhs == &rhs)  // Оптимизация сравнения списка с собой
  396.         || (lhs.GetSize() == rhs.GetSize()
  397.             && std::equal(lhs.begin(), lhs.end(), rhs.begin()));  // может бросить исключение
  398. }
  399.  
  400. template <typename Type>
  401. bool operator!=(const SingleLinkedList<Type>& lhs, const SingleLinkedList<Type>& rhs) {
  402.     return !(lhs == rhs);  // может бросить исключение
  403. }
  404.  
  405. template <typename Type>
  406. bool operator<(const SingleLinkedList<Type>& lhs, const SingleLinkedList<Type>& rhs) {
  407.     return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());  // может бросить исключение
  408. }
  409.  
  410. template <typename Type>
  411. bool operator<=(const SingleLinkedList<Type>& lhs, const SingleLinkedList<Type>& rhs) {
  412.     return !(rhs < lhs);  // Может бросить исключение
  413. }
  414.  
  415. template <typename Type>
  416. bool operator>(const SingleLinkedList<Type>& lhs, const SingleLinkedList<Type>& rhs) {
  417.     return (rhs < lhs);  // Может бросить исключение
  418. }
  419.  
  420. template <typename Type>
  421. bool operator>=(const SingleLinkedList<Type>& lhs, const SingleLinkedList<Type>& rhs) {
  422.     return !(lhs < rhs);  // Может бросить исключение
  423. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!