API tools faq
paste
Advertisement
kutuzzzov

Урок 3 вставка и очистка элементов списка

kutuzzzov
Dec 12th, 2022
993
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 7.11 KB | None | 0 0
raw download clone embed print report
  1. #include <cassert>
  2. #include <cstddef>
  3. #include <string>
  4. #include <utility>
  5.  
  6. template <typename Type>
  7. class SingleLinkedList {
  8.     // Узел списка
  9.     struct Node {
  10.         Node() = default;
  11.         Node(const Type& val, Node* next)
  12.             : value(val)
  13.             , next_node(next) {
  14.         }
  15.         Type value;
  16.         Node* next_node = nullptr;
  17.     };
  18.  
  19. public:
  20.     SingleLinkedList() {
  21.     }
  22.    
  23.     // Возвращает количество элементов в списке за время O(1)
  24.     [[nodiscard]] size_t GetSize() const noexcept {
  25.         // Заглушка. Реализуйте метод самостоятельно
  26.         return size_;
  27.         //assert(false);
  28.         //return 42;
  29.     }
  30.  
  31.     // Сообщает, пустой ли список за время O(1)
  32.     [[nodiscard]] bool IsEmpty() const noexcept {
  33.         // Заглушка. Реализуйте метод самостоятельно
  34.         if (size_ != 0) {
  35.         return false;
  36.         }
  37.         return true;
  38.     }
  39.    
  40.     // Вставляет элемент value в начало списка за время O(1)
  41.     void PushFront(const Type& value) {
  42.         // Реализуйте метод самостоятельно
  43.         head_.next_node = new Node(value, head_.next_node);
  44.         ++size_;
  45.     }
  46.  
  47.     // Очищает список за время O(N)
  48.     void Clear() noexcept {
  49.         // Реализуйте метод самостоятельно
  50.         while (head_.next_node != nullptr) {
  51.             Node* new_head = head_.next_node->next_node;
  52.             delete head_.next_node;
  53.             head_.next_node = new_head;
  54.         }
  55.         size_ = 0;
  56.     }
  57.    
  58.     ~SingleLinkedList() {
  59.         Clear();
  60.     }
  61.  
  62. private:
  63.     // Фиктивный узел, используется для вставки "перед первым элементом"
  64.     Node head_;
  65.     size_t size_ = 0;
  66. };
  67.  
  68. // Эта функция тестирует работу SingleLinkedList
  69. void Test1() {
  70.     // Шпион, следящий за своим удалением
  71.     struct DeletionSpy {
  72.         DeletionSpy() = default;
  73.         explicit DeletionSpy(int& instance_counter) noexcept
  74.             : instance_counter_ptr_(&instance_counter)  //
  75.         {
  76.             OnAddInstance();
  77.         }
  78.         DeletionSpy(const DeletionSpy& other) noexcept
  79.             : instance_counter_ptr_(other.instance_counter_ptr_)  //
  80.         {
  81.             OnAddInstance();
  82.         }
  83.         DeletionSpy& operator=(const DeletionSpy& rhs) noexcept {
  84.             if (this != &rhs) {
  85.                 auto rhs_copy(rhs);
  86.                 std::swap(instance_counter_ptr_, rhs_copy.instance_counter_ptr_);
  87.             }
  88.             return *this;
  89.         }
  90.         ~DeletionSpy() {
  91.             OnDeleteInstance();
  92.         }
  93.  
  94.     private:
  95.         void OnAddInstance() noexcept {
  96.             if (instance_counter_ptr_) {
  97.                 ++(*instance_counter_ptr_);
  98.             }
  99.         }
  100.         void OnDeleteInstance() noexcept {
  101.             if (instance_counter_ptr_) {
  102.                 assert(*instance_counter_ptr_ != 0);
  103.                 --(*instance_counter_ptr_);
  104.             }
  105.         }
  106.  
  107.         int* instance_counter_ptr_ = nullptr;
  108.     };
  109.  
  110.     // Проверка вставки в начало
  111.     {
  112.         SingleLinkedList<int> l;
  113.         assert(l.IsEmpty());
  114.         assert(l.GetSize() == 0u);
  115.  
  116.         l.PushFront(0);
  117.         l.PushFront(1);
  118.         assert(l.GetSize() == 2);
  119.         assert(!l.IsEmpty());
  120.  
  121.         l.Clear();
  122.         assert(l.GetSize() == 0);
  123.         assert(l.IsEmpty());
  124.     }
  125.  
  126.     // Проверка фактического удаления элементов
  127.     {
  128.         int item0_counter = 0;
  129.         int item1_counter = 0;
  130.         int item2_counter = 0;
  131.         {
  132.             SingleLinkedList<DeletionSpy> list;
  133.             list.PushFront(DeletionSpy{item0_counter});
  134.             list.PushFront(DeletionSpy{item1_counter});
  135.             list.PushFront(DeletionSpy{item2_counter});
  136.  
  137.             assert(item0_counter == 1);
  138.             assert(item1_counter == 1);
  139.             assert(item2_counter == 1);
  140.             list.Clear();
  141.             assert(item0_counter == 0);
  142.             assert(item1_counter == 0);
  143.             assert(item2_counter == 0);
  144.  
  145.             list.PushFront(DeletionSpy{item0_counter});
  146.             list.PushFront(DeletionSpy{item1_counter});
  147.             list.PushFront(DeletionSpy{item2_counter});
  148.             assert(item0_counter == 1);
  149.             assert(item1_counter == 1);
  150.             assert(item2_counter == 1);
  151.         }
  152.         assert(item0_counter == 0);
  153.         assert(item1_counter == 0);
  154.         assert(item2_counter == 0);
  155.     }
  156.  
  157.     // Вспомогательный класс, бросающий исключение после создания N-копии
  158.     struct ThrowOnCopy {
  159.         ThrowOnCopy() = default;
  160.         explicit ThrowOnCopy(int& copy_counter) noexcept
  161.             : countdown_ptr(&copy_counter) {
  162.         }
  163.         ThrowOnCopy(const ThrowOnCopy& other)
  164.             : countdown_ptr(other.countdown_ptr)  //
  165.         {
  166.             if (countdown_ptr) {
  167.                 if (*countdown_ptr == 0) {
  168.                     throw std::bad_alloc();
  169.                 } else {
  170.                     --(*countdown_ptr);
  171.                 }
  172.             }
  173.         }
  174.         // Присваивание элементов этого типа не требуется
  175.         ThrowOnCopy& operator=(const ThrowOnCopy& rhs) = delete;
  176.         // Адрес счётчика обратного отсчёта. Если не равен nullptr, то уменьшается при каждом копировании.
  177.         // Как только обнулится, конструктор копирования выбросит исключение
  178.         int* countdown_ptr = nullptr;
  179.     };
  180.  
  181.     {
  182.         bool exception_was_thrown = false;
  183.         // Последовательно уменьшаем счётчик копирований до нуля, пока не будет выброшено исключение
  184.         for (int max_copy_counter = 5; max_copy_counter >= 0; --max_copy_counter) {
  185.             // Создаём непустой список
  186.             SingleLinkedList<ThrowOnCopy> list;
  187.             list.PushFront(ThrowOnCopy{});
  188.             try {
  189.                 int copy_counter = max_copy_counter;
  190.                 list.PushFront(ThrowOnCopy(copy_counter));
  191.                 // Если метод не выбросил исключение, список должен перейти в новое состояние
  192.                 assert(list.GetSize() == 2);
  193.             } catch (const std::bad_alloc&) {
  194.                 exception_was_thrown = true;
  195.                 // После выбрасывания исключения состояние списка должно остаться прежним
  196.                 assert(list.GetSize() == 1);
  197.                 break;
  198.             }
  199.         }
  200.         assert(exception_was_thrown);
  201.     }
  202. }
  203.  
  204. int main() {
  205.     Test1();
  206. }
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!