shushus

Спринт 8. Исправляем список.

Feb 2nd, 2023
338
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 9.18 KB | None | 0 0
  1. -----------------------------------------------------------------------
  2. main.cpp
  3. -----------------------------------------------------------------------
  4. #include "list.h"
  5.  
  6. #include <cassert>
  7. #include <vector>
  8.  
  9. using namespace std;
  10.  
  11. template <class Type>
  12. auto MakeInsertingFunction(vector<SingleLinkedList<Type>>& lists, int x) {
  13.     return [&](const Type& value) {
  14.         lists.at(x).PushFront(value);
  15.     };
  16. }
  17.  
  18. template <class T>
  19. void InsertRange(int from, int to, T push_function) {
  20.     for (int i = from; i < to; ++i) {
  21.         push_function(i);
  22.     }
  23. }
  24.  
  25. int main() {
  26.  
  27.     vector<SingleLinkedList<int>> lists_a(10);
  28.  
  29.     auto push_to_2a = MakeInsertingFunction(lists_a, 2);
  30.     auto push_to_5a = MakeInsertingFunction(lists_a, 5);
  31.     auto push_to_7a = MakeInsertingFunction(lists_a, 7);
  32.  
  33.     InsertRange(10, 12, push_to_2a);
  34.     InsertRange(12, 14, push_to_5a);
  35.     InsertRange(14, 16, push_to_7a);
  36.  
  37.     assert(lists_a[2] == SingleLinkedList<int>({11, 10}));
  38.     assert(lists_a[5] == SingleLinkedList<int>({13, 12}));
  39.     assert(lists_a[7] == SingleLinkedList<int>({15, 14}));
  40.  
  41.     vector<SingleLinkedList<int>> lists_b = lists_a;
  42.  
  43.     auto push_to_2b = MakeInsertingFunction(lists_b, 2);
  44.     auto push_to_5b = MakeInsertingFunction(lists_b, 5);
  45.     auto push_to_7b = MakeInsertingFunction(lists_b, 7);
  46.  
  47.     InsertRange(20, 22, push_to_2b);
  48.     InsertRange(22, 24, push_to_5b);
  49.     InsertRange(24, 26, push_to_7b);
  50.  
  51.     assert(lists_b[2] == SingleLinkedList<int>({21, 20, 11, 10}));
  52.     assert(lists_b[5] == SingleLinkedList<int>({23, 22, 13, 12}));
  53.     assert(lists_b[7] == SingleLinkedList<int>({25, 24, 15, 14}));
  54.  
  55.     lists_a[2].PopFront();
  56.     lists_a[5].InsertAfter(lists_a[5].begin(), 100);
  57.     lists_b[5].EraseAfter(next(lists_b[5].begin()));
  58.     lists_b[7].Clear();
  59.  
  60.     assert(lists_a[2] == SingleLinkedList<int>({10}));
  61.     assert(lists_a[5] == SingleLinkedList<int>({13, 100, 12}));
  62.     assert(lists_b[5] == SingleLinkedList<int>({23, 22, 12}));
  63.     assert(lists_b[7] == SingleLinkedList<int>());
  64. }
  65. -----------------------------------------------------------------------
  66. list.h
  67. -----------------------------------------------------------------------
  68. #pragma once
  69.  
  70. #include <cassert>
  71. #include <cstddef>
  72. #include <iterator>
  73.  
  74. template <typename Type>
  75. class SingleLinkedList {
  76.  
  77.     struct Node {
  78.         Node() = default;
  79.         Node(const Type& val, Node* next) : value(val), next_node(next) {}
  80.         Type value{};
  81.         Node* next_node = nullptr;
  82.     };
  83.  
  84.  
  85.     template <typename ValueType>
  86.     class BasicIterator {
  87.  
  88.         friend class SingleLinkedList;
  89.  
  90.         explicit BasicIterator(Node* node) : node_(node) {}
  91.  
  92.     public:
  93.  
  94.         using iterator_category = std::forward_iterator_tag;
  95.         using value_type = Type;
  96.         using difference_type = std::ptrdiff_t;
  97.         using pointer = ValueType*;
  98.         using reference = ValueType&;
  99.  
  100.         BasicIterator() = default;
  101.  
  102.         BasicIterator(const BasicIterator<Type>& other) noexcept : node_(other.node_) {}
  103.  
  104.         BasicIterator& operator=(const BasicIterator& rhs) = default;
  105.  
  106.         [[nodiscard]] bool operator==(const BasicIterator<const Type>& rhs) const noexcept {
  107.             return this->node_ == rhs.node_;
  108.         }
  109.  
  110.         [[nodiscard]] bool operator==(const BasicIterator<Type>& rhs) const noexcept {
  111.             return this->node_ == rhs.node_;
  112.         }
  113.        
  114.         [[nodiscard]] bool operator!=(const BasicIterator<const Type>& rhs) const noexcept {
  115.             return node_ != rhs.node_;
  116.         }
  117.  
  118.         [[nodiscard]] bool operator!=(const BasicIterator<Type>& rhs) const noexcept {
  119.             return node_ != rhs.node_;
  120.         }
  121.  
  122.         BasicIterator& operator++() noexcept {
  123.             assert(node_ != nullptr);
  124.             node_ = node_->next_node;
  125.             return *this;
  126.         }
  127.  
  128.         BasicIterator operator++(int) noexcept {
  129.             auto this_copy(*this);
  130.             ++(*this);
  131.             return this_copy;
  132.         }
  133.  
  134.         [[nodiscard]] reference operator*() const noexcept {
  135.             assert(node_ != nullptr);
  136.             return node_->value;
  137.         }
  138.  
  139.         [[nodiscard]] pointer operator->() const noexcept {
  140.             assert(node_ != nullptr);
  141.             return &node_->value;
  142.         }
  143.  
  144.     private:
  145.         Node* node_ = nullptr;
  146.     };
  147.  
  148. public:
  149.     using value_type = Type;
  150.     using reference = value_type&;
  151.     using const_reference = const value_type&;
  152.  
  153.     using Iterator = BasicIterator<Type>;
  154.     using ConstIterator = BasicIterator<const Type>;
  155.  
  156.     SingleLinkedList() = default;
  157.  
  158.     SingleLinkedList(std::initializer_list<Type> values) {
  159.         Assign(values.begin(), values.end());
  160.     }
  161.    
  162.     SingleLinkedList(const SingleLinkedList& val) {
  163.         Assign(val.begin(), val.end());
  164.     }
  165.    
  166.     SingleLinkedList& operator=(const SingleLinkedList& helper) {
  167.         if (&helper != this) {
  168.             if(!helper.IsEmpty()){
  169.                 auto helper_copy(helper);
  170.                 swap(helper_copy);
  171.             }else{
  172.                 Clear();
  173.             }
  174.         }
  175.         return *this;
  176.     }
  177.  
  178.     ~SingleLinkedList() {
  179.         Clear();
  180.     }
  181.  
  182.     [[nodiscard]] Iterator begin() noexcept {
  183.         return Iterator{head_.next_node};
  184.     }
  185.  
  186.     [[nodiscard]] Iterator end() noexcept {
  187.         return Iterator{nullptr};
  188.     }
  189.  
  190.     [[nodiscard]] ConstIterator begin() const noexcept {
  191.         return cbegin();
  192.     }
  193.  
  194.     [[nodiscard]] ConstIterator end() const noexcept {
  195.         return ConstIterator{nullptr};
  196.     }
  197.  
  198.     [[nodiscard]] ConstIterator cbegin() const noexcept {
  199.         return ConstIterator{head_.next_node};
  200.     }
  201.  
  202.     [[nodiscard]] ConstIterator cend() const noexcept {
  203.         return ConstIterator{nullptr};
  204.     }
  205.  
  206.     [[nodiscard]] Iterator before_begin() noexcept {
  207.         return Iterator{&head_};
  208.     }
  209.  
  210.     [[nodiscard]] ConstIterator cbefore_begin() const noexcept {
  211.         return ConstIterator{const_cast<Node*>(&head_)};
  212.     }
  213.  
  214.     [[nodiscard]] ConstIterator before_begin() const noexcept {
  215.         return cbefore_begin();
  216.     }
  217.  
  218.     [[nodiscard]] size_t GetSize() const noexcept {
  219.         return size_;
  220.     }
  221.  
  222.     [[nodiscard]] bool IsEmpty() const noexcept {
  223.         return GetSize() == 0;
  224.     }
  225.  
  226.     void PushFront(const Type& value) {
  227.         head_.next_node = new Node(value, head_.next_node);
  228.  
  229.         ++size_;
  230.     }
  231.  
  232.     Iterator InsertAfter(ConstIterator pos, const Type& value) {
  233.         assert(pos.node_);
  234.  
  235.         pos.node_->next_node = new Node(value, pos.node_->next_node);
  236.  
  237.         ++size_;
  238.         return Iterator{pos.node_->next_node};
  239.     }
  240.  
  241.     void PopFront() noexcept {
  242.         assert(!IsEmpty());
  243.         --size_;
  244.         Node* helper = head_.next_node->next_node;
  245.         delete head_.next_node;
  246.         head_.next_node = helper;
  247.     }
  248.  
  249.     Iterator EraseAfter(ConstIterator pos) noexcept {
  250.         assert(!IsEmpty());
  251.         --size_;
  252.         Node* helper = pos.node_->next_node->next_node;
  253.         delete pos.node_->next_node;
  254.         pos.node_->next_node = helper;
  255.         return Iterator{pos.node_->next_node};
  256.     }
  257.  
  258.     void Clear() noexcept {
  259.  
  260.         while (head_.next_node != nullptr) {
  261.             Node* new_head = head_.next_node->next_node;
  262.             delete head_.next_node;
  263.             head_.next_node = new_head;
  264.         }
  265.         size_ = 0;
  266.     }
  267.  
  268.     void swap(SingleLinkedList& other) noexcept {
  269.         std::swap(head_.next_node, other.head_.next_node);
  270.         std::swap(size_, other.size_);
  271.     }
  272.  
  273. private:
  274.     template <typename InputIterator>
  275.     void Assign(InputIterator from, InputIterator to) {
  276.  
  277.         SingleLinkedList<Type> tmp;
  278.  
  279.         Node** node_ptr = &tmp.head_.next_node;
  280.         while (from != to) {
  281.  
  282.             assert(*node_ptr == nullptr);
  283.  
  284.             *node_ptr = new Node(*from, nullptr);
  285.             ++tmp.size_;
  286.  
  287.  
  288.             node_ptr = &((*node_ptr)->next_node);
  289.  
  290.             ++from;
  291.         }
  292.         swap(tmp);
  293.     }
  294.  
  295.     Node head_;
  296.     size_t size_ = 0;
  297. };
  298.  
  299. template <typename Type>
  300. void swap(SingleLinkedList<Type>& lhs, SingleLinkedList<Type>& rhs) noexcept {
  301.     lhs.swap(rhs);
  302. }
  303.  
  304. template <typename Type>
  305. bool operator==(const SingleLinkedList<Type>& lhs, const SingleLinkedList<Type>& rhs) {
  306.     return (&lhs == &rhs)
  307.         || (lhs.GetSize() == rhs.GetSize()
  308.             && std::equal(lhs.begin(), lhs.end(), rhs.begin()));
  309. }
  310.  
  311. template <typename Type>
  312. bool operator!=(const SingleLinkedList<Type>& lhs, const SingleLinkedList<Type>& rhs) {
  313.     return !(lhs == rhs);
  314. }
  315.  
  316. template <typename Type>
  317. bool operator<(const SingleLinkedList<Type>& lhs, const SingleLinkedList<Type>& rhs) {
  318.     return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
  319. }
  320.  
  321. template <typename Type>
  322. bool operator<=(const SingleLinkedList<Type>& lhs, const SingleLinkedList<Type>& rhs) {
  323.     return !(rhs < lhs);
  324. }
  325.  
  326. template <typename Type>
  327. bool operator>(const SingleLinkedList<Type>& lhs, const SingleLinkedList<Type>& rhs) {
  328.     return (rhs < lhs);
  329. }
  330.  
  331. template <typename Type>
  332. bool operator>=(const SingleLinkedList<Type>& lhs, const SingleLinkedList<Type>& rhs) {
  333.     return !(lhs < rhs);
  334. }
Advertisement
Add Comment
Please, Sign In to add comment