API tools faq
paste
Advertisement
kutuzzzov

Урок 5 сравнение, копирование, присваивание

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