API tools faq
paste
Advertisement
RobertDeMilo

SingleLinkedList + Reverse + MergeSort

RobertDeMilo
Dec 2nd, 2023 (edited)
123
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 27.90 KB | None | 0 0
raw download clone embed print report
  1. #include <iostream>
  2. #include <algorithm>  
  3. #include <cassert>
  4. #include <cstddef>
  5. #include <iterator>
  6. #include <string>
  7. #include <utility>
  8. #include <list>
  9. #include <forward_list>
  10. using namespace std;
  11.  
  12. template <typename Type>
  13. class SingleLinkedList
  14. {
  15.     // Узел списка
  16.     struct Node {
  17.         Node() = default;
  18.         Node(const Type& val, Node* next)
  19.             : value(val)
  20.             , next(next) {
  21.         }
  22.         Type value;
  23.         Node* next = nullptr;
  24.     };
  25.  
  26.     // Шаблон класса «Базовый Итератор».
  27.        // Определяет поведение итератора на элементы односвязного списка
  28.        // ValueType — совпадает с Type (для Iterator) либо с const Type (для ConstIterator)
  29.  
  30.     template <typename ValueType>
  31.     class BasicIterator
  32.     {
  33.         // Класс списка объявляется дружественным, чтобы из методов списка
  34.         // был доступ к приватной области итератора
  35.         friend class SingleLinkedList;
  36.  
  37.         // Конвертирующий конструктор итератора из указателя на узел списка
  38.         explicit BasicIterator(Node* node)
  39.         {
  40.             /*assert(false);*/
  41.             // Реализуйте конструктор самостоятельно
  42.             node_ = node;
  43.         }
  44.  
  45.     public:
  46.         // Объявленные ниже типы сообщают стандартной библиотеке о свойствах этого итератора
  47.  
  48.         // Категория итератора — forward iterator
  49.         // (итератор, который поддерживает операции инкремента и многократное разыменование)
  50.         using iterator_category = std::forward_iterator_tag;
  51.         // Тип элементов, по которым перемещается итератор
  52.         using value_type = Type;
  53.         // Тип, используемый для хранения смещения между итераторами
  54.         using difference_type = std::ptrdiff_t;
  55.         // Тип указателя на итерируемое значение
  56.         using pointer = ValueType*;
  57.         // Тип ссылки на итерируемое значение
  58.         using reference = ValueType&;
  59.  
  60.         BasicIterator() = default;
  61.  
  62.         // Конвертирующий конструктор/конструктор копирования
  63.         // При ValueType, совпадающем с Type, играет роль копирующего конструктора
  64.         // При ValueType, совпадающем с const Type, играет роль конвертирующего конструктора
  65.  
  66.         BasicIterator(const BasicIterator<Type>& other) noexcept
  67.         {
  68.             node_ = other.node_;
  69.         }
  70.         // Чтобы компилятор не выдавал предупреждение об отсутствии оператора = при наличии
  71.         // пользовательского конструктора копирования, явно объявим оператор = и
  72.         // попросим компилятор сгенерировать его за нас
  73.         BasicIterator& operator=(const BasicIterator& rhs) = default;
  74.  
  75.         // Оператор сравнения итераторов (в роли второго аргумента выступает константный итератор)
  76.         // Два итератора равны, если они ссылаются на один и тот же элемент списка либо на end()
  77.         [[nodiscard]] bool operator==(const BasicIterator<const Type>& rhs) const noexcept {
  78.  
  79.             return node_ == rhs.node_;
  80.         }
  81.         // Оператор проверки итераторов на неравенство
  82.         // Противоположен !=
  83.         [[nodiscard]] bool operator!=(const BasicIterator<const Type>& rhs) const noexcept {
  84.             return node_ != rhs.node_;
  85.         }
  86.         // Оператор сравнения итераторов (в роли второго аргумента итератор)
  87.         // Два итератора равны, если они ссылаются на один и тот же элемент списка либо на end()
  88.         [[nodiscard]] bool operator==(const BasicIterator<Type>& rhs) const noexcept {
  89.             return node_ == rhs.node_;
  90.         }
  91.         //// Оператор проверки итераторов на неравенство
  92.         //// Противоположен !=
  93.         [[nodiscard]] bool operator!=(const BasicIterator<Type>& rhs) const noexcept {
  94.             return node_ != rhs.node_;
  95.         }
  96.         // Оператор прединкремента. После его вызова итератор указывает на следующий элемент списка
  97.         // Возвращает ссылку на самого себя
  98.         // Инкремент итератора, не указывающего на существующий элемент списка, приводит к неопределённому поведению
  99.         BasicIterator& operator++() noexcept {
  100.  
  101.             node_ = node_->next;
  102.             return *this;
  103.         }
  104.         // Оператор постинкремента. После его вызова итератор указывает на следующий элемент списка
  105.         // Возвращает прежнее значение итератора
  106.         // Инкремент итератора, не указывающего на существующий элемент списка,
  107.         // приводит к неопределённому поведению
  108.         BasicIterator operator++(int) noexcept
  109.         {
  110.             BasicIterator temp(*this);
  111.             node_ = node_->next;
  112.             return temp;
  113.         }
  114.         // Операция разыменования. Возвращает ссылку на текущий элемент
  115.         // Вызов этого оператора у итератора, не указывающего на существующий элемент списка,
  116.         // приводит к неопределённому поведению
  117.  
  118.       /*  Операции* и->для доступа к элементу списка.Возвращают ссылку и указатель на значение, хранящееся в списке,
  119.           а не на весь узел списка, задаваемый вложенной структурой Node.
  120.           Помните, итераторы должны скрывать внутреннее устройство контейнера от внешнего мира.*/
  121.  
  122.         [[nodiscard]] reference operator*() const noexcept
  123.         {
  124.  
  125.             return node_->value;
  126.         }
  127.         // Операция доступа к члену класса. Возвращает указатель на текущий элемент списка
  128.         // Вызов этого оператора у итератора, не указывающего на существующий элемент списка,
  129.         // приводит к неопределённому поведению
  130.         [[nodiscard]] pointer operator->() const noexcept
  131.         {
  132.  
  133.             return &node_->value;
  134.         }
  135.         //using pointer = ValueType*;
  136.         //// Тип ссылки на итерируемое значение
  137.         //using reference = ValueType&;
  138.  
  139.     private:
  140.         Node* node_ = nullptr;
  141.     };
  142.  
  143.  
  144. public:
  145.  
  146.     SingleLinkedList() :head_({}), size_(0)
  147.     {
  148.  
  149.     }
  150.  
  151.     SingleLinkedList(std::initializer_list<Type> values) {
  152.         // Реализуйте конструктор самостоятельно
  153.         SingleLinkedList reverse_tmp;
  154.  
  155.         for (auto it = values.begin(); it != values.end(); ++it)
  156.         {
  157.             reverse_tmp.PushFront(*it);
  158.         }
  159.  
  160.         SingleLinkedList tmp;
  161.  
  162.         for (auto it = reverse_tmp.begin(); it != reverse_tmp.end(); ++it)
  163.         {
  164.             tmp.PushFront(*it);
  165.         }
  166.  
  167.         /* скопировать внутрь tmp элементы other */
  168.  
  169.         // После того как элементы скопированы, обмениваем данные текущего списка и tmp
  170.         swap(tmp);
  171.  
  172.     }
  173.  
  174.     SingleLinkedList(const SingleLinkedList& other) {
  175.         // Сначала надо удостовериться, что текущий список пуст
  176.        // assert(size_ == 0 && head_.next_node == nullptr);
  177.  
  178.         SingleLinkedList reverse_tmp;
  179.  
  180.         for (auto it = other.begin(); it != other.end(); ++it)
  181.         {
  182.             reverse_tmp.PushFront(*it);
  183.         }
  184.  
  185.         SingleLinkedList tmp;
  186.  
  187.         for (auto it = reverse_tmp.begin(); it != reverse_tmp.end(); ++it)
  188.         {
  189.             tmp.PushFront(*it);
  190.         }
  191.  
  192.         /* скопировать внутрь tmp элементы other */
  193.  
  194.         // После того как элементы скопированы, обмениваем данные текущего списка и tmp
  195.         swap(tmp);
  196.         // Теперь tmp пуст, а текущий список содержит копию элементов other
  197.     }
  198.  
  199.     SingleLinkedList& operator=(const SingleLinkedList& rhs) {
  200.         // Реализуйте присваивание самостоятельно
  201.         if (this != &rhs)
  202.         {
  203.             SingleLinkedList temp(rhs);
  204.             temp.swap(*this);
  205.         }
  206.         return *this;
  207.     }
  208.  
  209.     // Возвращает количество элементов в списке за время O(1)
  210.     [[nodiscard]] size_t GetSize() const noexcept {
  211.         // Заглушка. Реализуйте метод самостоятельно
  212.         //assert(false);
  213.         //return 42;
  214.         return size_;
  215.     }
  216.  
  217.     // Обменивает содержимое списков за время O(1)
  218.     void swap(SingleLinkedList& other) noexcept {
  219.         // Реализуйте обмен содержимого списков самостоятельно
  220.  
  221.         std::swap(other.size_, size_);
  222.         std::swap(head_.next, other.head_.next);
  223.         /*std::swap(this->GetSize(), other.GetSize());*/
  224.     }
  225.  
  226.     // Вставляет элемент value в начало списка за время O(1)
  227.     void PushFront(const Type& value)
  228.     {
  229.         // Реализуйте метод самостоятельно
  230.          /* Node head_;*/
  231.         head_.next = new Node(value, head_.next);
  232.         ++size_;
  233.     }
  234.  
  235.     // Очищает список за время O(N)
  236.     void Clear() noexcept
  237.     {
  238.         // Реализуйте метод самостоятельно
  239.         while (head_.next != nullptr)
  240.         {
  241.             Node* temp = head_.next;
  242.             head_.next = head_.next->next;
  243.             delete temp;
  244.             --size_;
  245.         }
  246.     }
  247.  
  248.  
  249.     // Сообщает, пустой ли список за время O(1)
  250.     [[nodiscard]] bool IsEmpty() const noexcept {
  251.         // Заглушка. Реализуйте метод самостоятельно
  252.        /* assert(false);
  253.         return false;*/
  254.         if (size_ == 0)
  255.         {
  256.             return true;
  257.         }
  258.         return false;
  259.     }
  260.     ~SingleLinkedList()
  261.     {
  262.         Clear();
  263.     }
  264.  
  265.     using value_type = Type;
  266.     using reference = value_type&;
  267.     using const_reference = const value_type&;
  268.  
  269.     // Итератор, допускающий изменение элементов списка
  270.     using Iterator = BasicIterator<Type>;
  271.     // Константный итератор, предоставляющий доступ для чтения к элементам списка
  272.     using ConstIterator = BasicIterator<const Type>;
  273.  
  274.     // Возвращает итератор, ссылающийся на первый элемент
  275.     // Если список пустой, возвращённый итератор будет равен end()
  276.     [[nodiscard]] Iterator begin() noexcept {
  277.  
  278.         return Iterator(head_.next);
  279.     }
  280.     // Возвращает итератор, указывающий на позицию, следующую за последним элементом односвязного списка
  281.     // Разыменовывать этот итератор нельзя — попытка разыменования приведёт к неопределённому поведению
  282.     [[nodiscard]] Iterator end() noexcept {
  283.  
  284.         return Iterator(nullptr);
  285.     }
  286.     // Возвращает константный итератор, ссылающийся на первый элемент
  287.     // Если список пустой, возвращённый итератор будет равен end()
  288.     // Результат вызова эквивалентен вызову метода cbegin()
  289.     [[nodiscard]] ConstIterator begin() const noexcept {
  290.         return ConstIterator(head_.next);
  291.     }
  292.     // Возвращает константный итератор, указывающий на позицию, следующую за последним элементом односвязного списка
  293.     // Разыменовывать этот итератор нельзя — попытка разыменования приведёт к неопределённому поведению
  294.     // Результат вызова эквивалентен вызову метода cend()
  295.     [[nodiscard]] ConstIterator end() const noexcept {
  296.         return ConstIterator(nullptr);
  297.     }
  298.     // Возвращает константный итератор, ссылающийся на первый элемент
  299.     // Если список пустой, возвращённый итератор будет равен cend()
  300.     [[nodiscard]] ConstIterator cbegin() const noexcept {
  301.         return ConstIterator(head_.next);
  302.     }
  303.  
  304.     // Возвращает константный итератор, указывающий на позицию, следующую за последним элементом односвязного списка
  305.     // Разыменовывать этот итератор нельзя — попытка разыменования приведёт к неопределённому поведению
  306.     [[nodiscard]] ConstIterator cend() const noexcept {
  307.         return ConstIterator(nullptr);
  308.     }
  309.  
  310.     // Возвращает итератор, указывающий на позицию перед первым элементом односвязного списка.
  311.    // Разыменовывать этот итератор нельзя - попытка разыменования приведёт к неопределённому поведению
  312.     [[nodiscard]] Iterator before_begin() noexcept {
  313.         // Реализуйте самостоятельно
  314.         return Iterator(&head_);
  315.     }
  316.  
  317.     // Возвращает константный итератор, указывающий на позицию перед первым элементом односвязного списка.
  318.     // Разыменовывать этот итератор нельзя - попытка разыменования приведёт к неопределённому поведению
  319.     [[nodiscard]] ConstIterator cbefore_begin() const noexcept {
  320.         //Реализуйте самостоятельно
  321.         return ConstIterator{ const_cast<Node*>(&head_) };
  322.     }
  323.  
  324.     //// Возвращает константный итератор, указывающий на позицию перед первым элементом односвязного списка.
  325.     //// Разыменовывать этот итератор нельзя - попытка разыменования приведёт к неопределённому поведению
  326.     [[nodiscard]] ConstIterator before_begin() const noexcept {
  327.         //Реализуйте самостоятельно
  328.         return cbefore_begin();
  329.     }
  330.  
  331.     void PopFront() noexcept {
  332.         // Реализуйте метод самостоятельно
  333.  
  334.         Node* temp = head_.next;
  335.         head_.next = head_.next->next;
  336.         delete temp;
  337.         --size_;
  338.     }
  339.  
  340.     /*Вставляет элемент value после элемента, на который указывает pos.
  341.     Возвращает итератор на вставленный элемент
  342.     Если при создании элемента будет выброшено исключение, список останется в прежнем состоянии */
  343.  
  344.     Iterator InsertAfter(ConstIterator pos, const Type& value) {
  345.         // Заглушка. Реализуйте метод самостоятельно
  346.  
  347.         pos.node_->next = new Node(value, pos.node_->next);
  348.         ++size_;
  349.         return Iterator(pos.node_->next);
  350.     }
  351.  
  352.     /*Удаляет элемент, следующий за pos.
  353.       Возвращает итератор на элемент, следующий за удалённым*/
  354.  
  355.     Iterator EraseAfter(ConstIterator pos) noexcept {
  356.         // Заглушка. Реализуйте метод самостоятельно
  357.  
  358.         auto to_return = pos.node_->next->next;
  359.         auto to_delete = pos.node_->next;
  360.         pos.node_->next = pos.node_->next->next;
  361.         delete to_delete;
  362.         --size_;
  363.         return Iterator(to_return);
  364.     }
  365.  
  366.     Node* merge(Node* head_one, Node* head_two)
  367.     {
  368.         Node* head_three = nullptr;
  369.  
  370.         if (head_one == nullptr)
  371.         {
  372.             return head_two;
  373.         }
  374.         if (head_two == nullptr)
  375.         {
  376.             return head_one;
  377.         }
  378.         if (head_one->value < head_two->value)
  379.         {
  380.             head_three = head_one;
  381.             head_three->next = merge(head_one->next, head_two);
  382.         }
  383.         else
  384.         {
  385.             head_three = head_two;
  386.             head_three->next = merge(head_one, head_two->next);
  387.         }
  388.  
  389.         return head_three;
  390.     }
  391.  
  392.     Node* mergesort(Node* head)
  393.     {
  394.         Node* head_one;
  395.         Node* head_two;
  396.  
  397.         if ((head == nullptr) || (head->next == nullptr))
  398.         {
  399.             return head;
  400.         }
  401.  
  402.         head_one = head;
  403.         head_two = head->next;
  404.  
  405.         while ((head_two != nullptr) && (head_two->next != nullptr))
  406.         {
  407.             head = head->next;
  408.             head_two = head_two->next->next;
  409.         }
  410.  
  411.         head_two = head->next;
  412.         head->next = nullptr;
  413.  
  414.         return merge(mergesort(head_one), mergesort(head_two));
  415.     }
  416.  
  417.     void mergesort()
  418.     {
  419.         head_.next = mergesort(head_.next);
  420.     }
  421.  
  422.     void Reverse()
  423.     {
  424.         Node* temp = head_.next; // текущий узел
  425.         Node* prev = nullptr;    // предыдущий узел
  426.         Node* nexto;             // следующий узел
  427.  
  428.         while (temp != nullptr)
  429.         {
  430.             nexto = temp->next; // 250 (запоминаем значение слеующего узла) для того чтобы разрушить связь
  431.  
  432.             if (nexto == nullptr)
  433.             {
  434.                 head_.next = temp;
  435.             }
  436.  
  437.             temp->next = prev; //разрушали связь между узлами, (разворачиваем узлы) где было 250 сейчас nullptr
  438.  
  439.             prev = temp; // на след. итерации пред узлом будет текущий
  440.  
  441.             temp = nexto; // переходим на след итерацию
  442.         }
  443.     }
  444.  
  445. private:
  446.     // Фиктивный узел, используется для вставки "перед первым элементом"
  447.     Node head_;
  448.     size_t size_;
  449. };
  450.  
  451. template <typename Type>
  452. void swap(SingleLinkedList<Type>& lhs, SingleLinkedList<Type>& rhs) noexcept {
  453.     // Реализуйте обмен самостоятельно
  454.  
  455.     lhs.swap(rhs);
  456. }
  457.  
  458. template <typename Type>
  459. bool operator==(const SingleLinkedList<Type>& lhs, const SingleLinkedList<Type>& rhs) {
  460.  
  461.     if (lhs.GetSize() != rhs.GetSize())
  462.     {
  463.         return false;
  464.     }
  465.     return equal(lhs.begin(), lhs.begin(), rhs.begin());
  466. }
  467.  
  468. template <typename Type>
  469. bool operator!=(const SingleLinkedList<Type>& lhs, const SingleLinkedList<Type>& rhs) {
  470.  
  471.     return !(lhs == rhs);
  472. }
  473.  
  474. template <typename Type>
  475. bool operator<(const SingleLinkedList<Type>& lhs, const SingleLinkedList<Type>& rhs) {
  476.     // Заглушка. Реализуйте сравнение самостоятельно
  477.     return lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
  478. }
  479.  
  480. template <typename Type>
  481. bool operator<=(const SingleLinkedList<Type>& lhs, const SingleLinkedList<Type>& rhs) {
  482.     // Заглушка. Реализуйте сравнение самостоятельно
  483.     return (lhs < rhs) || (lhs == rhs);
  484. }
  485.  
  486. template <typename Type>
  487. bool operator>(const SingleLinkedList<Type>& lhs, const SingleLinkedList<Type>& rhs) {
  488.     // Заглушка. Реализуйте сравнение самостоятельно
  489.     return !(lhs < rhs);
  490. }
  491.  
  492. template <typename Type>
  493. bool operator>=(const SingleLinkedList<Type>& lhs, const SingleLinkedList<Type>& rhs) {
  494.     // Заглушка. Реализуйте сравнение самостоятельно
  495.     return (lhs > rhs) || (lhs == rhs);
  496. }
  497.  
  498. // Эта функция проверяет работу класса SingleLinkedList
  499. void Test4() {
  500.     struct DeletionSpy {
  501.         ~DeletionSpy() {
  502.             if (deletion_counter_ptr) {
  503.                 ++(*deletion_counter_ptr);
  504.             }
  505.         }
  506.         int* deletion_counter_ptr = nullptr;
  507.     };
  508.  
  509.     // Проверка PopFront
  510.     {
  511.         SingleLinkedList<int> numbers{ 3, 14, 15, 92, 6 };
  512.         numbers.PopFront();
  513.         assert((numbers == SingleLinkedList<int>{14, 15, 92, 6}));
  514.  
  515.         SingleLinkedList<DeletionSpy> list;
  516.         list.PushFront(DeletionSpy{});
  517.         int deletion_counter = 0;
  518.         list.begin()->deletion_counter_ptr = &deletion_counter;
  519.         assert(deletion_counter == 0);
  520.         list.PopFront();
  521.         assert(deletion_counter == 1);
  522.     }
  523.  
  524.     // Доступ к позиции, предшествующей begin
  525.     {
  526.         SingleLinkedList<int> empty_list;
  527.         const auto& const_empty_list = empty_list;
  528.         assert(empty_list.before_begin() == empty_list.cbefore_begin());
  529.         assert(++empty_list.before_begin() == empty_list.begin());
  530.         assert(++empty_list.cbefore_begin() == const_empty_list.begin());
  531.  
  532.         SingleLinkedList<int> numbers{ 1, 2, 3, 4 };
  533.         const auto& const_numbers = numbers;
  534.         assert(numbers.before_begin() == numbers.cbefore_begin());
  535.         assert(++numbers.before_begin() == numbers.begin());
  536.         assert(++numbers.cbefore_begin() == const_numbers.begin());
  537.     }
  538.  
  539.     // Вставка элемента после указанной позиции
  540.     {  // Вставка в пустой список
  541.         {
  542.             SingleLinkedList<int> lst;
  543.             const auto inserted_item_pos = lst.InsertAfter(lst.before_begin(), 123);
  544.             assert((lst == SingleLinkedList<int>{123}));
  545.             assert(inserted_item_pos == lst.begin());
  546.             assert(*inserted_item_pos == 123);
  547.         }
  548.  
  549.         // Вставка в непустой список
  550.         {
  551.             SingleLinkedList<int> lst{ 1, 2, 3 };
  552.             auto inserted_item_pos = lst.InsertAfter(lst.before_begin(), 123);
  553.  
  554.             assert(inserted_item_pos == lst.begin());
  555.             assert(inserted_item_pos != lst.end());
  556.             assert(*inserted_item_pos == 123);
  557.             assert((lst == SingleLinkedList<int>{123, 1, 2, 3}));
  558.  
  559.             inserted_item_pos = lst.InsertAfter(lst.begin(), 555);
  560.             assert(++SingleLinkedList<int>::Iterator(lst.begin()) == inserted_item_pos);
  561.             assert(*inserted_item_pos == 555);
  562.             assert((lst == SingleLinkedList<int>{123, 555, 1, 2, 3}));
  563.         };
  564.     }
  565.  
  566.     // Вспомогательный класс, бросающий исключение после создания N-копии
  567.     struct ThrowOnCopy {
  568.         ThrowOnCopy() = default;
  569.         explicit ThrowOnCopy(int& copy_counter) noexcept
  570.             : countdown_ptr(&copy_counter) {
  571.         }
  572.         ThrowOnCopy(const ThrowOnCopy& other)
  573.             : countdown_ptr(other.countdown_ptr)  //
  574.         {
  575.             if (countdown_ptr) {
  576.                 if (*countdown_ptr == 0) {
  577.                     throw std::bad_alloc();
  578.                 }
  579.                 else {
  580.                     --(*countdown_ptr);
  581.                 }
  582.             }
  583.         }
  584.         // Присваивание элементов этого типа не требуется
  585.         ThrowOnCopy& operator=(const ThrowOnCopy& rhs) = delete;
  586.         // Адрес счётчика обратного отсчёта. Если не равен nullptr, то уменьшается при каждом копировании.
  587.         // Как только обнулится, конструктор копирования выбросит исключение
  588.         int* countdown_ptr = nullptr;
  589.     };
  590.  
  591.     // Проверка обеспечения строгой гарантии безопасности исключений
  592.     {
  593.         bool exception_was_thrown = false;
  594.         for (int max_copy_counter = 10; max_copy_counter >= 0; --max_copy_counter) {
  595.             SingleLinkedList<ThrowOnCopy> list{ ThrowOnCopy{}, ThrowOnCopy{}, ThrowOnCopy{} };
  596.             try {
  597.                 int copy_counter = max_copy_counter;
  598.                 list.InsertAfter(list.cbegin(), ThrowOnCopy(copy_counter));
  599.                 assert(list.GetSize() == 4u);
  600.             }
  601.             catch (const std::bad_alloc&) {
  602.                 exception_was_thrown = true;
  603.                 assert(list.GetSize() == 3u);
  604.                 break;
  605.             }
  606.         }
  607.         assert(exception_was_thrown);
  608.     }
  609.  
  610.     // Удаление элементов после указанной позиции
  611.     {
  612.         {
  613.             SingleLinkedList<int> lst{ 1, 2, 3, 4 };
  614.             const auto& const_lst = lst;
  615.             const auto item_after_erased = lst.EraseAfter(const_lst.cbefore_begin());
  616.             assert((lst == SingleLinkedList<int>{2, 3, 4}));
  617.             assert(item_after_erased == lst.begin());
  618.         }
  619.         {
  620.             SingleLinkedList<int> lst{ 1, 2, 3, 4 };
  621.             const auto item_after_erased = lst.EraseAfter(lst.cbegin());
  622.             assert((lst == SingleLinkedList<int>{1, 3, 4}));
  623.             assert(item_after_erased == (++lst.begin()));
  624.         }
  625.         {
  626.             SingleLinkedList<int> lst{ 1, 2, 3, 4 };
  627.             const auto item_after_erased = lst.EraseAfter(++(++lst.cbegin()));
  628.             assert((lst == SingleLinkedList<int>{1, 2, 3}));
  629.             assert(item_after_erased == lst.end());
  630.         }
  631.         {
  632.             SingleLinkedList<DeletionSpy> list{ DeletionSpy{}, DeletionSpy{}, DeletionSpy{} };
  633.             auto after_begin = ++list.begin();
  634.             int deletion_counter = 0;
  635.             after_begin->deletion_counter_ptr = &deletion_counter;
  636.             assert(deletion_counter == 0u);
  637.             list.EraseAfter(list.cbegin());
  638.             assert(deletion_counter == 1u);
  639.         }
  640.     }
  641. }
  642.  
  643. int main() {
  644.     //Test4();
  645.  
  646.     SingleLinkedList <int> sll = { 1,2,3,4,5 };
  647.     sll.Reverse();
  648.     sll.mergesort();
  649.     sll.Reverse();
  650.     for (auto el : sll)
  651.     {
  652.         cout << el << " ";
  653.     }
  654. }
  655.  
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!