Advertisement
Sivoha

Untitled

May 17th, 2022
611
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <iterator>
  3. #include <cmath>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. template <typename Type>
  9. class LinkedList {
  10. private:
  11.     typedef size_t size_type;
  12.     typedef Type value_type;
  13.     typedef value_type& reference;
  14.     typedef const value_type& const_reference;
  15.     class ListNode;
  16.  
  17.     size_type count;
  18.     ListNode* head;
  19.     ListNode* tail;
  20.  
  21. public:
  22.     class ListIterator;
  23.     class ListReverseIterator;
  24.     typedef ListIterator iterator;
  25.     typedef const ListIterator const_iterator;
  26.     typedef ListReverseIterator reverse_iterator;
  27.  
  28.     LinkedList();
  29.     LinkedList(size_type);
  30.     LinkedList(const LinkedList<Type>&);
  31.     ~LinkedList();
  32.  
  33.     LinkedList& operator = (const LinkedList<Type>&);
  34.     void copy(const LinkedList<Type>&);
  35.  
  36.     iterator begin();
  37.     iterator end();
  38.     reverse_iterator rbegin();
  39.     reverse_iterator rend();
  40.  
  41.     bool empty() const;
  42.     size_type size() const;
  43.  
  44.     reference front();
  45.     reference back();
  46.  
  47.     void assign(iterator, iterator);
  48.     void assign(size_type n, const_reference);
  49.     void pop_front();
  50.     void push_front(const_reference);
  51.     void push_back(const_reference);
  52.     void pop_back();
  53.     iterator insert(const_iterator, const_reference);
  54.     iterator insert(const_iterator, size_type, const_reference);
  55.     iterator insert(const_iterator, iterator, iterator);
  56.     iterator erase(iterator);
  57.     iterator erase(iterator, iterator);
  58.     void swap(LinkedList&);
  59.     void resize(size_type);
  60.     void clear();
  61.  
  62.     void reverse();
  63.  
  64.     void print();
  65. };
  66.  
  67. template <typename Type>
  68. class LinkedList<Type>::ListNode {
  69. private:
  70.     friend class LinkedList;
  71.     value_type value;
  72.  
  73. public:
  74.     ListNode* next;
  75.     ListNode* prev;
  76.     ListNode() : value(), prev(nullptr), next(nullptr) {}
  77.     ListNode(const_reference value) : value(value), prev(nullptr), next(nullptr) {}
  78.     ListNode(ListNode* node) : value(node->value), prev(node->prev), next(node->next) {}
  79. };
  80.  
  81. template <typename Type>
  82. class LinkedList<Type>::ListIterator {
  83. public:
  84.     typedef ptrdiff_t difference_type;
  85.     typedef typename LinkedList<Type>::value_type value_type;
  86.     typedef random_access_iterator_tag iterator_category;
  87.     typedef typename LinkedList<Type>::ListNode node;
  88.     typedef node* pointer;
  89.     typedef node& reference;
  90.  
  91.     ListIterator() : ptr(nullptr) {}
  92.     ListIterator(node* p) : ptr(p) {}
  93.     ListIterator(const_iterator& iter) : ptr(iter.ptr) {}
  94.  
  95.     iterator& operator = (node* new_ptr) {
  96.         ptr = new_ptr;
  97.         return *this;
  98.     }
  99.     iterator& operator = (const_iterator& iter) {
  100.         ptr = iter.ptr;
  101.         return *this;
  102.     }
  103.  
  104.     void swap(iterator& iter1, iterator& iter2) {
  105.         node* tmp = iter2.ptr;
  106.         iter2 = iterator(iter1.ptr);
  107.         iter1 = iterator(tmp);
  108.     }
  109.  
  110.     value_type& operator * () const {
  111.         return ptr->value;
  112.     }
  113.     value_type* operator -> () {
  114.         return *(ptr->value);
  115.     }
  116.     value_type& operator [] (difference_type num) {
  117.         node* tmp = ptr;
  118.         while (tmp->prev != nullptr) {
  119.             tmp = tmp->prev;
  120.         }
  121.         node* start = tmp;
  122.         difference_type c = 1;
  123.         while (tmp->next != nullptr) {
  124.             tmp = tmp->next;
  125.             c++;
  126.         }
  127.         if (c != 0) {
  128.             if (num >= 0) {
  129.                 num %= c;
  130.             }
  131.             else {
  132.                 num = (c - abs(num) % c) % c;
  133.             }
  134.  
  135.             for (difference_type i = 0; i < num; ++i) {
  136.                 start = start->next;
  137.             }
  138.         }
  139.         return start->value;
  140.     }
  141.  
  142.     iterator& operator ++ () {
  143.         ptr = ptr->next;
  144.         return *this;
  145.     }
  146.     iterator& operator ++ (int) {
  147.         ListIterator iter(*this);
  148.         ptr = ptr->next;
  149.         return iter;
  150.     }
  151.     iterator& operator -- () {
  152.         ptr = ptr->prev;
  153.         return *this;
  154.     }
  155.     iterator& operator -- (int) {
  156.         ListIterator iter(*this);
  157.         ptr = ptr->prev;
  158.         return iter;
  159.     }
  160.     iterator operator + (difference_type diff) {
  161.         iterator tmp = *this;
  162.         if (diff >= 0) {
  163.             for (difference_type i = 0; i < diff; ++i) {
  164.                 ptr = ptr->next;
  165.             }
  166.         }
  167.         else {
  168.             for (difference_type i = 0; i < abs(diff); ++i) {
  169.                 ptr = ptr->prev;
  170.             }
  171.         }
  172.         iterator ret = *this;
  173.         *this = tmp;
  174.         return ret;
  175.     }
  176.  
  177.     friend difference_type operator - (const iterator& iter1, const iterator& iter2) {
  178.         difference_type diff = 0;
  179.         node* tmp = iter1.ptr;
  180.         if (iter2 > iter1) {
  181.             while (tmp != iter2.ptr) {
  182.                 diff--;
  183.                 tmp = tmp->next;
  184.             }
  185.         }
  186.         else if (iter2 < iter1) {
  187.             while (tmp != iter2.ptr) {
  188.                 diff++;
  189.                 tmp = tmp->prev;
  190.             }
  191.         }
  192.         if (iter2 > iter1) {
  193.             return diff * -1;
  194.         }
  195.         else {
  196.             return diff;
  197.         }
  198.     }
  199.  
  200.     iterator operator - (difference_type diff) {
  201.         iterator tmp = *this;
  202.         if (diff >= 0) {
  203.             for (difference_type i = 0; i < diff; ++i) {
  204.                 ptr = ptr->prev;
  205.             }
  206.         }
  207.         else {
  208.             for (difference_type i = 0; i < abs(diff); ++i) {
  209.                 ptr = ptr->next;
  210.             }
  211.         }
  212.         iterator ret = *this;
  213.         *this = tmp;
  214.         return ret;
  215.     }
  216.  
  217.     iterator operator += (difference_type diff) {
  218.         if (diff >= 0) {
  219.             for (difference_type i = 0; i < diff; ++i) {
  220.                 ptr = ptr->next;
  221.             }
  222.         }
  223.         else {
  224.             for (difference_type i = 0; i < abs(diff); ++i) {
  225.                 ptr = ptr->prev;
  226.             }
  227.         }
  228.         return *this;
  229.     }
  230.     iterator operator -= (difference_type diff) {
  231.         if (diff >= 0) {
  232.             for (size_t i = 0; i < diff; ++i) {
  233.                 ptr = ptr->prev;
  234.             }
  235.         }
  236.         else {
  237.             for (size_t i = 0; i < abs(diff); ++i) {
  238.                 ptr = ptr->next;
  239.             }
  240.         }
  241.         return *this;
  242.     }
  243.  
  244.     bool operator == (iterator& iter) {
  245.         return ptr == iter.ptr;
  246.     }
  247.     friend bool operator == (const iterator& iter1, const iterator& iter2) {
  248.         return iter1.ptr == iter2.ptr;
  249.     }
  250.     bool operator != (iterator& iter) {
  251.         return ptr != iter.ptr;
  252.     }
  253.     friend bool operator != (const iterator& iter1, const iterator& iter2) {
  254.         return iter1.ptr != iter2.ptr;
  255.     }
  256.     bool operator > (iterator& iter) {
  257.         node* tmp = ptr;
  258.         while ((ptr != iter.ptr) && (ptr->next != nullptr)) {
  259.             ptr = ptr->next;
  260.         }
  261.         if ((ptr->next == nullptr) && (ptr != iter.ptr)) {
  262.             ptr = tmp;
  263.             return true;
  264.         }
  265.         ptr = tmp;
  266.         return false;
  267.     }
  268.     bool operator > (const iterator& iter) {
  269.         node* tmp = ptr;
  270.         while ((ptr != iter.ptr) && (ptr->next != nullptr)) {
  271.             ptr = ptr->next;
  272.         }
  273.         if ((ptr->next == nullptr) && (ptr != iter.ptr)) {
  274.             ptr = tmp;
  275.             return true;
  276.         }
  277.         ptr = tmp;
  278.         return false;
  279.     }
  280.     friend bool operator > (const iterator& iter1, const iterator& iter2) {
  281.         node* ptr1 = iter1.ptr;
  282.         node* ptr2 = iter2.ptr;
  283.         while ((ptr1 != ptr2) && (ptr1->next != nullptr)) {
  284.             ptr1 = ptr1->next;
  285.         }
  286.         if ((ptr1->next == nullptr) && (ptr1 != ptr2)) {
  287.             return true;
  288.         }
  289.         return false;
  290.     }
  291.  
  292.     friend bool operator >= (iterator& iter1, iterator& iter2) {
  293.         if ((iter1 == iter2) || (iter1 > iter2)) {
  294.             return true;
  295.         }
  296.         return false;
  297.     }
  298.     bool operator < (iterator& iter) {
  299.         node* tmp = ptr;
  300.         while ((ptr != iter.ptr) && (ptr->next != nullptr)) {
  301.             ptr = ptr->next;
  302.         }
  303.         if ((ptr->next == nullptr) && (ptr != iter.ptr)) {
  304.             ptr = tmp;
  305.             return false;
  306.         }
  307.         ptr = tmp;
  308.         return true;
  309.     }
  310.  
  311.     friend bool operator < (const iterator& iter1, const iterator& iter2) {
  312.         node* ptr1 = iter1.ptr;
  313.         node* ptr2 = iter2.ptr;
  314.         while ((ptr1 != ptr2) && (ptr1->next != nullptr)) {
  315.             ptr1 = ptr1->next;
  316.         }
  317.         if ((ptr1->next == nullptr) && (ptr1 != ptr2)) {
  318.             return false;
  319.         }
  320.         return true;
  321.     }
  322.  
  323.     friend bool operator <= (iterator& iter1, iterator& iter2) {
  324.         if ((iter1 == iter2) || (iter1 < iter2)) {
  325.             return true;
  326.         }
  327.         return false;
  328.     }
  329. private:
  330.     friend class LinkedList;
  331.  
  332.     node* ptr;
  333. };
  334.  
  335. template <typename Type>
  336. class LinkedList<Type>::ListReverseIterator {
  337. private:
  338.     friend class LinkedList;
  339.     typedef ptrdiff_t difference_type;
  340.     typedef typename LinkedList<Type>::value_type value_type;
  341.     typedef random_access_iterator_tag iterator_category;
  342.     typedef typename LinkedList<Type>::ListNode node;
  343.     typedef node* pointer;
  344.     typedef node& reference;
  345.  
  346.     node* ptr;
  347.  
  348. public:
  349.     ListReverseIterator() : ptr(nullptr) {}
  350.     ListReverseIterator(node* p) : ptr(p) {}
  351.     ListReverseIterator(const reverse_iterator& iter) : ptr(iter.ptr) {}
  352.  
  353.     reverse_iterator& operator = (node* new_ptr) {
  354.         ptr = new_ptr;
  355.         return *this;
  356.     }
  357.     reverse_iterator& operator = (const reverse_iterator& iter) {
  358.         ptr = iter.ptr;
  359.         return *this;
  360.     }
  361.  
  362.     value_type& operator * () const {
  363.         return ptr->value;
  364.     }
  365.     value_type* operator -> () {
  366.         return *(ptr->value);
  367.     }
  368.     value_type& operator [] (difference_type num) {
  369.         node* tmp = ptr;
  370.         while (tmp->prev != nullptr) {
  371.             tmp = tmp->prev;
  372.         }
  373.         node* start = tmp;
  374.         difference_type c = 1;
  375.         while (tmp->next != nullptr) {
  376.             tmp = tmp->next;
  377.             c++;
  378.         }
  379.         if (c != 0) {
  380.             if (num >= 0) {
  381.                 num %= c;
  382.             }
  383.             else {
  384.                 num = (c - abs(num) % c) % c;
  385.             }
  386.  
  387.             for (difference_type i = 0; i < num; ++i) {
  388.                 start = start->next;
  389.             }
  390.         }
  391.         return start->value;
  392.     }
  393.  
  394.     reverse_iterator& operator ++ () {
  395.         ptr = ptr->prev;
  396.         return *this;
  397.     }
  398.     reverse_iterator& operator ++ (int) {
  399.         ListIterator iter(*this);
  400.         ptr = ptr->prev;
  401.         return iter;
  402.     }
  403.     reverse_iterator& operator -- () {
  404.         ptr = ptr->next;
  405.         return *this;
  406.     }
  407.     reverse_iterator& operator -- (int) {
  408.         ListReverseIterator iter(*this);
  409.         ptr = ptr->next;
  410.         return iter;
  411.     }
  412.     reverse_iterator operator + (difference_type diff) {
  413.         reverse_iterator tmp = *this;
  414.         if (diff >= 0) {
  415.             for (size_t i = 0; i < diff; ++i) {
  416.                 ptr = ptr->prev;
  417.             }
  418.         }
  419.         else {
  420.             for (size_t i = 0; i < abs(diff); ++i) {
  421.                 ptr = ptr->next;
  422.             }
  423.         }
  424.         reverse_iterator ret = *this;
  425.         *this = tmp;
  426.         return ret;
  427.     }
  428.     reverse_iterator operator - (difference_type diff) {
  429.         reverse_iterator tmp = *this;
  430.         if (diff >= 0) {
  431.             for (difference_type i = 0; i < diff; ++i) {
  432.                 ptr = ptr->next;
  433.             }
  434.         }
  435.         else {
  436.             for (difference_type i = 0; i < abs(diff); ++i) {
  437.                 ptr = ptr->prev;
  438.             }
  439.         }
  440.         reverse_iterator ret = *this;
  441.         *this = tmp;
  442.         return ret;
  443.     }
  444.     reverse_iterator operator += (difference_type diff) {
  445.         if (diff >= 0) {
  446.             for (size_t i = 0; i < diff; ++i) {
  447.                 ptr = ptr->prev;
  448.             }
  449.         }
  450.         else {
  451.             for (size_t i = 0; i < abs(diff); ++i) {
  452.                 ptr = ptr->next;
  453.             }
  454.         }
  455.         return *this;
  456.     }
  457.     reverse_iterator operator -= (difference_type diff) {
  458.         if (diff >= 0) {
  459.             for (size_t i = 0; i < diff; ++i) {
  460.                 ptr = ptr->next;
  461.             }
  462.         }
  463.         else {
  464.             for (size_t i = 0; i < abs(diff); ++i) {
  465.                 ptr = ptr->prev;
  466.             }
  467.         }
  468.         return *this;
  469.     }
  470.  
  471.     friend bool operator == (reverse_iterator& iter1, reverse_iterator& iter2) {
  472.         return iter1.ptr == iter2.ptr;
  473.     }
  474.     friend bool operator != (reverse_iterator& iter1, reverse_iterator& iter2) {
  475.         return iter1.ptr != iter2.ptr;
  476.     }
  477.     bool operator > (reverse_iterator& iter) {
  478.         node* tmp = ptr;
  479.         while ((ptr != iter.ptr) && (ptr->next != nullptr)) {
  480.             ptr = ptr->next;
  481.         }
  482.         if ((ptr->next == nullptr) && (ptr != iter.ptr)) {
  483.             ptr = tmp;
  484.             return false;
  485.         }
  486.         ptr = tmp;
  487.         return true;
  488.     }
  489.     friend bool operator >= (reverse_iterator& iter1, reverse_iterator& iter2) {
  490.         if ((iter1.ptr == iter2.ptr) || (iter1.ptr > iter2.ptr)) {
  491.             return true;
  492.         }
  493.         return false;
  494.     }
  495.     bool operator < (reverse_iterator& iter) {
  496.         node* tmp = ptr;
  497.         while ((ptr != iter.ptr) && (ptr->next != nullptr)) {
  498.             ptr = ptr->next;
  499.         }
  500.         if ((ptr->next == nullptr) && (ptr != iter.ptr)) {
  501.             ptr = tmp;
  502.             return true;
  503.         }
  504.         ptr = tmp;
  505.         return false;
  506.     }
  507.     friend bool operator <= (reverse_iterator& iter1, reverse_iterator& iter2) {
  508.         if ((iter1.ptr == iter2.ptr) || (iter1.ptr < iter2.ptr)) {
  509.             return true;   
  510.         }
  511.         return false;
  512.     }
  513. };
  514.  
  515. template <typename Type>
  516. LinkedList<Type>::LinkedList() : count(0), head(nullptr), tail(nullptr) {}
  517.  
  518. template <typename Type>
  519. LinkedList<Type>::LinkedList(size_type count) : count(count), head(nullptr), tail(nullptr) {
  520.     if (count) {
  521.         ListNode* current = new ListNode;
  522.         head = current;
  523.         ListNode* previous = nullptr;
  524.         for (size_type i = 1; i < count; ++i) {
  525.             current->next = new ListNode;
  526.             current->prev = previous;
  527.             previous = current;
  528.             current = current->next;
  529.         }
  530.         tail = current;
  531.         tail->prev = previous;
  532.        
  533.     }
  534. }
  535.  
  536. template <typename Type>
  537. LinkedList<Type>::LinkedList(const LinkedList<Type>& list) : count(0), head(nullptr), tail(nullptr) {
  538.     copy(list);
  539. }
  540.  
  541. template <typename Type>
  542. LinkedList<Type>::~LinkedList() {}
  543.  
  544. template <typename Type>
  545. LinkedList<Type>& LinkedList<Type>::operator = (const LinkedList<Type>& list) {
  546.     if (this != &list) {
  547.         copy(list);
  548.     }
  549.     return *this;
  550. }
  551.  
  552. template <typename Type>
  553. void LinkedList<Type>::copy(const LinkedList<Type>& list) {
  554.     if (list.count) {
  555.         ListNode* cur1 = new ListNode(list.head);
  556.         ListNode* cur2 = list.head->next;
  557.         head = cur1;
  558.         for (size_type i = 1; i < list.count; ++i) {
  559.             cur1->next = new ListNode(cur2);
  560.             cur1 = cur1->next;
  561.             cur2 = cur2->next;
  562.         }
  563.         tail = cur1;
  564.         count = list.count;
  565.     }
  566. }
  567.  
  568. template <typename Type>
  569. typename LinkedList<Type>::iterator LinkedList<Type>::begin() {
  570.     return ListIterator(head);
  571. }
  572.  
  573. template <typename Type>
  574. typename LinkedList<Type>::reverse_iterator LinkedList<Type>::rbegin() {
  575.     return ListReverseIterator(head);
  576. }
  577.  
  578. template <typename Type>
  579. typename LinkedList<Type>::iterator LinkedList<Type>::end() {
  580.     return ListIterator(tail);
  581. }
  582.  
  583. template <typename Type>
  584. typename LinkedList<Type>::reverse_iterator LinkedList<Type>::rend() {
  585.     return ListReverseIterator(tail);
  586. }
  587.  
  588. template <typename Type>
  589. bool LinkedList<Type>::empty() const{
  590.     return count == 0;
  591. }
  592.  
  593. template <typename Type>   
  594. typename LinkedList<Type>::size_type LinkedList<Type>::size() const {
  595.     return count;
  596. }
  597.  
  598. template <typename Type>
  599. typename LinkedList<Type>::reference LinkedList<Type>::front() {
  600.     return head->value;
  601. }
  602.  
  603. template <typename Type>
  604. typename LinkedList<Type>::reference LinkedList<Type>::back() {
  605.     return tail->value;
  606. }
  607.  
  608. template <typename Type>
  609. void LinkedList<Type>::assign(iterator iter1, iterator iter2) {
  610.     this->clear();
  611.     if (iter1 == iter2) {
  612.         this->push_back(*iter1);
  613.     }
  614.     else if (iter1 < iter2) {
  615.         while (iter1 != iter2) {
  616.             this->push_back(*iter1);
  617.             ++iter1;
  618.         }
  619.         this->push_back(*iter1);
  620.     }
  621.     else {
  622.         while (iter1 != iter2) {
  623.             this->push_back(*iter1);
  624.             --iter1;
  625.         }
  626.         this->push_back(*iter1);
  627.     }
  628. }
  629.  
  630. template <typename Type>
  631. void LinkedList<Type>::assign(size_type n, const_reference value) {
  632.     this->clear();
  633.     for (size_type i = 0; i < n; ++i) {
  634.         this->push_back(value);
  635.     }
  636.  
  637. }
  638.  
  639. template <typename Type>
  640. void LinkedList<Type>::push_front(const_reference value) {
  641.     ListNode* new_head = new ListNode(value);
  642.     if (head != nullptr) {
  643.         head->prev = new_head;
  644.         new_head->next = head;
  645.         head = new_head;
  646.     }
  647.     else {
  648.         head = new_head;
  649.         tail = new_head;
  650.         head->prev = nullptr;
  651.         head->next = tail;
  652.         tail->prev = head;
  653.         tail->next = nullptr;
  654.     }
  655.     ++count;
  656. }
  657.  
  658. template <typename Type>
  659. void LinkedList<Type>::pop_front() {
  660.     ListNode* tmp = head;  
  661.     head = tmp->next;
  662.     if (head != nullptr) {
  663.         head->prev = nullptr;
  664.     }
  665.     else {
  666.         tail = nullptr;
  667.     }
  668.     delete tmp;
  669.     --count;
  670. }
  671.  
  672. template <typename Type>
  673. void LinkedList<Type>::push_back(const_reference value) {
  674.     ListNode* new_tail = new ListNode(value);
  675.     if (tail != nullptr) {
  676.         tail->next = new_tail;
  677.         new_tail->prev = tail;
  678.         new_tail->next = nullptr;
  679.         tail = new_tail;
  680.     }
  681.     else {
  682.         head = new_tail;
  683.         tail = new_tail;
  684.         head->next = tail;
  685.         tail->prev = head;
  686.         tail->next = nullptr;
  687.         head->prev = nullptr;
  688.     }
  689.     ++count;
  690. }
  691.  
  692. template <typename Type>
  693. void LinkedList<Type>::pop_back() {
  694.     ListNode* tmp = tail;
  695.     tail = tmp->prev;
  696.     if (tail != nullptr) {
  697.         tail->next = nullptr;
  698.     }
  699.     else {
  700.         head = nullptr;
  701.     }
  702.     delete tmp;
  703.     --count;
  704. }
  705.  
  706. template <typename Type>
  707. typename LinkedList<Type>::iterator LinkedList<Type>::insert(const_iterator pos, const_reference value) {
  708.     ListNode* new_node = new ListNode(value);
  709.     ListNode* tmp = pos.ptr;
  710.     if (tmp == head) {
  711.         tmp->prev = new_node;
  712.         new_node->next = tmp;
  713.         new_node->prev = nullptr;
  714.         head = new_node;
  715.     }
  716.     else {
  717.         new_node->prev = tmp->prev;
  718.         new_node->next = tmp;
  719.         tmp->prev->next = new_node;
  720.         tmp->prev = new_node;
  721.     }
  722.     ++count;
  723.     return ListIterator(new_node);
  724. }
  725.  
  726. template <typename Type>
  727. typename LinkedList<Type>::iterator LinkedList<Type>::insert(const_iterator pos, size_type n, const_reference value) {
  728.     for (size_type i = 0; i < n - 1; ++i) {
  729.         insert(pos, value);
  730.     }
  731.     return insert(pos, value);
  732. }
  733.  
  734. template <typename Type>
  735. typename LinkedList<Type>::iterator LinkedList<Type>::insert(const_iterator pos, iterator iter1, iterator iter2) {
  736.     if (iter1 == iter2) {
  737.         return this->insert(pos, iter1.ptr->value);
  738.     }
  739.     else if (iter1 < iter2) {
  740.         while (iter1 != iter2) {
  741.             this->insert(pos, iter1.ptr->value);
  742.             ++iter1;
  743.         }
  744.         return this->insert(pos, iter1.ptr->value);
  745.     }
  746.     else {
  747.         while (iter1 != iter2) {
  748.             this->insert(pos, iter1.ptr->value);
  749.             --iter1;
  750.         }
  751.         return this->insert(pos, iter1.ptr->value);
  752.     }
  753. }
  754.  
  755. template <typename Type>
  756. typename LinkedList<Type>::iterator LinkedList<Type>::erase(iterator iter) {
  757.     iterator ret = nullptr;
  758.     ListNode* tmp = iter.ptr;
  759.     if (tmp != nullptr) {
  760.         if ((tmp->next != nullptr) && (tmp->prev != nullptr)) {
  761.             iter.ptr = tmp->next;
  762.             iter.ptr->prev = tmp->prev;
  763.             tmp->prev->next = iter.ptr;
  764.             ret = iter;
  765.         }
  766.         else if (iter.ptr->next == nullptr && iter.ptr->prev == nullptr) {
  767.             head = nullptr;
  768.             tail = nullptr;
  769.         }
  770.         else if (iter.ptr->next == nullptr) {
  771.             tail = tmp->prev;
  772.             tail->next = nullptr;
  773.             ret = --iter;
  774.         }
  775.         else if (iter.ptr->prev == nullptr) {
  776.             head = tmp->next;
  777.             head->prev = nullptr;
  778.             ret = ++iter;
  779.         }
  780.         delete tmp;
  781.         --count;
  782.     }
  783.     return ret;
  784. }
  785.  
  786. template <typename Type>
  787. typename LinkedList<Type>::iterator LinkedList<Type>::erase(iterator iter1, iterator iter2) {
  788.     if (iter1 == iter2) {
  789.         return this->erase(iter1);
  790.     }
  791.     else if (iter1 < iter2) {
  792.         while (iter1 != iter2) {
  793.             iter1 = this->erase(iter1);
  794.         }
  795.         return this->erase(iter1);
  796.     }
  797.     else {
  798.         while (iter1 != iter2) {
  799.             iter1 = this->erase(iter1);
  800.         }
  801.         return this->erase(iter1);
  802.     }
  803. }
  804.  
  805. template <typename Type>
  806. void LinkedList<Type>::swap(LinkedList& list) {
  807.     ListNode* h = this->head;
  808.     head = list.head;
  809.     list.head = h;
  810.     ListNode* t = this->tail;
  811.     tail = list.tail;
  812.     list.tail = t;
  813.     size_type c = this->count;
  814.     count = list.count;
  815.     list.count = c;
  816. }
  817.  
  818. template <typename Type>
  819. void LinkedList<Type>::resize(size_type new_size) {
  820.     ListNode* current = new ListNode;
  821.     ListNode* previous = nullptr;
  822.     if (count == 0 && new_size != 0) {
  823.         head = current;
  824.         for (size_type i = 1; i < new_size; ++i) {
  825.             current->next = new ListNode;
  826.             current->prev = previous;
  827.             previous = current;
  828.             current = current->next;
  829.         }
  830.         tail = current;
  831.         tail->prev = previous;
  832.     }
  833.     else { 
  834.         if (new_size <= count) {
  835.             if (new_size == 0) {
  836.                 clear();
  837.                 return;
  838.             }
  839.             current = head;
  840.             for (size_type i = 1; i < new_size; ++i) {
  841.                 current = current->next;
  842.             }
  843.             tail = current;
  844.             current = current->next;
  845.             ListNode* temp;
  846.             for (size_type i = new_size; i < count; ++i) {
  847.                 temp = current->next;
  848.                 delete current;
  849.                 current = temp;
  850.             }
  851.             tail->next = nullptr;
  852.         }
  853.         else {
  854.             current = tail;
  855.             for (size_type i = count; i < new_size; ++i) {
  856.                 current->next = new ListNode;
  857.                 current->prev = previous;
  858.                 previous = current;
  859.                 current = current->next;
  860.             }
  861.             tail = current;
  862.         }
  863.     }
  864.     count = new_size;
  865. }
  866.  
  867. template <typename Type>
  868. void LinkedList<Type>::clear() {
  869.     while (count) {
  870.         pop_front();
  871.     }
  872.     head = nullptr;
  873.     tail = nullptr;
  874. }
  875.  
  876. template <typename Type>
  877. void LinkedList<Type>::reverse() {
  878.     ListNode* old_head = head;
  879.     ListNode* old_tail = tail;
  880.     ListNode* ptr = head;
  881.     ListNode* tmp;
  882.     while (ptr != tail) {
  883.         tmp = ptr->next;
  884.         ptr->next = ptr->prev;
  885.         ptr->prev = tmp;
  886.         ptr = tmp;
  887.     }
  888.     tmp = ptr->next;
  889.     ptr->next = ptr->prev;
  890.     ptr->prev = tmp;
  891.     head = old_tail;
  892.     tail = old_head;
  893. }
  894.  
  895. template <typename Type>
  896. void LinkedList<Type>::print() {
  897.     ListNode* current = head;
  898.     while (current != nullptr) {
  899.         cout << current->value << " ";
  900.         current = current->next;
  901.     }
  902.     cout << endl;
  903. }
  904.  
  905. int main() {
  906.     setlocale(LC_ALL, "");
  907.     cout << "Создание экземпляров с помощью конструкторов и оператора = :" << endl;
  908.     {
  909.         LinkedList<int> list1 = LinkedList<int>();
  910.         cout << "   Конструктор без параметров: "; list1.print();
  911.         LinkedList<int> list2 = LinkedList<int>(5);
  912.         cout << "   Конструктор с параметром: "; list2.print();
  913.         LinkedList<int> list3 = LinkedList<int>(list2);
  914.         cout << "   Конструктор копирования: "; list3.print();
  915.         LinkedList<int> list4 = list3;
  916.         cout << "   Оператор = : "; list3.print();
  917.         cout << endl;
  918.     }
  919.     cout << "Использование методов класса (без итераторов):" << endl;
  920.     {
  921.         cout << "Метод empty: " << endl;
  922.         LinkedList<int> list1 = LinkedList<int>(2);
  923.         cout << "   Изначальный список 1: "; list1.print();
  924.         cout << "   Результат метода list1.empty(): " << list1.empty() << endl;
  925.         LinkedList<int> list2 = LinkedList<int>();
  926.         cout << "   Изначальный список 2: "; list2.print();
  927.         cout << "   Результат метода list2.empty(): " << list2.empty() << endl;
  928.         cout << endl;
  929.     }
  930.     {
  931.         cout << "Метод size: " << endl;
  932.         LinkedList<int> list1 = LinkedList<int>(2);
  933.         cout << "   Изначальный список 1: "; list1.print();
  934.         cout << "   Результат метода list1.size(): " << list1.size() << endl;
  935.         LinkedList<int> list2 = LinkedList<int>();
  936.         cout << "   Изначальный список 2: "; list2.print();
  937.         cout << "   Результат метода list2.size(): " << list2.size() << endl;
  938.         cout << endl;
  939.     }
  940.     {
  941.         cout << "Метод front: " << endl;
  942.         LinkedList<int> list = LinkedList<int>(1);
  943.         list.push_front(5);
  944.         cout << "   Изначальный список: "; list.print();
  945.         cout << "   Результат метода front(): " << list.front() << endl;
  946.         list.front() += 5;
  947.         cout << "   Список после применения метода list.front() += 5: "; list.print();
  948.         cout << endl;
  949.     }
  950.     {
  951.         cout << "Метод back: " << endl;
  952.         LinkedList<int> list = LinkedList<int>(1);
  953.         list.push_back(7);
  954.         cout << "   Изначальный список: "; list.print();
  955.         cout << "   Результат метода back(): " << list.back() << endl;
  956.         list.back() *= 4;
  957.         cout << "   Список после применения метода list.back() *= 4: "; list.print();
  958.         cout << endl;
  959.     }
  960.     {
  961.         cout << "Метод assign:" << endl;
  962.         LinkedList<int> list = LinkedList<int>(2);
  963.         cout << "   Изначальный список: "; list.print();
  964.         list.assign(5, 42);
  965.         cout << "   Список после применения метода assign(5, 42): "; list.print();
  966.         cout << endl;
  967.     }
  968.     {
  969.         cout << "Методы push_front и push_back: " << endl;
  970.         LinkedList<int> list = LinkedList<int>(1);
  971.         cout << "   Изначальный список: "; list.print();
  972.         list.push_front(1);
  973.         cout << "   Список после применения метода push_front(1): "; list.print();
  974.         list.push_back(5);
  975.         cout << "   Список после применения метода push_back(5): "; list.print();
  976.         cout << endl;
  977.     }
  978.     {
  979.         cout << "Методы pop_front и pop_back: " << endl;
  980.         LinkedList<int> list = LinkedList<int>(2);
  981.         list.push_front(42); list.push_back(24); list.push_front(7); list.push_back(5);
  982.         cout << "   Изначальный список: "; list.print();
  983.         list.pop_front();
  984.         cout << "   Список после применения метода pop_front(): "; list.print();
  985.         list.pop_back();
  986.         cout << "   Список после применения метода pop_back(): "; list.print();
  987.         cout << endl;
  988.     }
  989.     {
  990.         cout << "Метод swap: " << endl;
  991.         LinkedList<int> list1 = LinkedList<int>();
  992.         list1.push_front(42); list1.push_back(24); list1.push_front(7); list1.push_back(5);
  993.         LinkedList<int> list2 = LinkedList<int>(5);
  994.         cout << "   Изначальный список 1: "; list1.print();
  995.         cout << "   Изначальный список 2: "; list2.print();
  996.         list2.swap(list1);
  997.         cout << "   Список 1 после применения метода list2.swap(list1): "; list1.print();
  998.         cout << "   Список 2 после применения метода list2.swap(list1): "; list2.print();
  999.         cout << endl;
  1000.     }
  1001.     {
  1002.         cout << "Метод resize: " << endl;
  1003.         LinkedList<int> list1 = LinkedList<int>(3);
  1004.         list1.push_front(42); list1.push_back(24); list1.push_front(7); list1.push_back(5);
  1005.         LinkedList<int> list2 = LinkedList<int>();
  1006.         list2.push_back(5); list2.push_back(10);
  1007.         cout << "   Изначальный список 1: "; list1.print();
  1008.         cout << "   Изначальный список 2: "; list2.print();
  1009.         list1.resize(4);
  1010.         list2.resize(10);
  1011.         cout << "   Список 1 после применения метода resize(4): "; list1.print();
  1012.         cout << "   Список 2 после применения метода resize(10): "; list2.print();
  1013.         cout << endl;
  1014.     }
  1015.     {
  1016.         cout << "Метод clear: " << endl;
  1017.         LinkedList<int> list = LinkedList<int>(2);
  1018.         list.push_front(42); list.push_back(24); list.push_front(7); list.push_back(5);
  1019.         cout << "   Изначальный список: "; list.print();
  1020.         list.clear();
  1021.         cout << "   Список после применения метода clear(): "; list.print();
  1022.         cout << endl;
  1023.     }
  1024.     {
  1025.         cout << "Метод reverse: " << endl;
  1026.         LinkedList<int> list = LinkedList<int>(2);
  1027.         list.push_front(42); list.push_back(24); list.push_front(7); list.push_back(5);
  1028.         cout << "   Изначальный список: "; list.print();
  1029.         list.reverse();
  1030.         cout << "   Список после применения метода reverse(): "; list.print();
  1031.         cout << endl;
  1032.     }
  1033.     cout << "Использование итераторов:" << endl;
  1034.     {
  1035.         LinkedList<int> list = LinkedList<int>();
  1036.         for (int i = 0; i < 5; ++i) { list.push_back(i); }
  1037.         cout << "   Изначальный список: "; list.print();
  1038.         for (LinkedList<int>::ListIterator it1 = list.begin(), it2 = list.end() + 1; it1 != it2; ++it1) { *it1 += 1; }
  1039.         cout << "   Список после цикла for (LinkedList<int>::ListIterator it1 = list.begin(), it2 = list.end() + 1; it1 != it2; ++it1) { *it1 += 1; } : "; list.print();
  1040.         for (LinkedList<int>::ListReverseIterator it1 = list.rbegin(), it2 = list.rend() - 1; it1 != it2; --it1) { *it1 += 1; }
  1041.         cout << "   Список после цикла for (LinkedList<int>::ListReverseIterator it1 = list.rbegin(), it2 = list.rend() - 1; it1 != it2; --it1) { *it1 += 1; } : "; list.print();
  1042.         cout << endl;
  1043.     }
  1044.     cout << "Некоторые операции итераторов:" << endl;
  1045.     {
  1046.         LinkedList<int> list = LinkedList<int>();
  1047.         for (int i = 0; i < 5; ++i) { list.push_back(i); }
  1048.         cout << "   Изначальный список: "; list.print();
  1049.         cout << "   Результат *(list.begin() + 2) : " << *(list.begin() + 2) << endl;
  1050.         cout << "   Результат *(list.end() - 1) : " << *(list.end() - 1) << endl;
  1051.         cout << "   Результат list.end()[1] : " << list.end()[1] << endl;
  1052.         cout << "   Результат list.end()[3] : " << list.end()[3] << endl;
  1053.         cout << "   it1 = list.begin() + 1, it2 = list.end() - 1" << endl;
  1054.         auto it1 = list.begin() + 1, it2 = list.end() - 1;
  1055.         cout << "   Результат it1 < it2 : " << (it1 < it2) << endl;
  1056.  
  1057.     }
  1058.     cout << "Методы, использующие итераторы:" << endl;
  1059.     {
  1060.         cout << "Метод assign: " << endl;
  1061.         LinkedList<int> list1 = LinkedList<int>(2);
  1062.         list1.push_front(42); list1.push_back(24); list1.push_front(7); list1.push_back(5);
  1063.         cout << "   Изначальный список 1: "; list1.print();
  1064.         LinkedList<int> list2 = LinkedList<int>(2);
  1065.         cout << "   Изначальный список 2: "; list2.print();
  1066.         list2.assign(list1.begin(), list1.end() - 2);
  1067.         cout << "   Список 2 после применения метода assign(list1.begin(), list1.end() - 2) : "; list2.print();
  1068.         cout << endl;
  1069.     }
  1070.     {
  1071.         cout << "Метод insert: " << endl;
  1072.         LinkedList<int> list1 = LinkedList<int>(2);
  1073.         list1.push_front(42); list1.push_back(24); list1.push_front(7); list1.push_back(5);
  1074.         cout << "   Изначальный список 1: "; list1.print();
  1075.         LinkedList<int> list2 = LinkedList<int>(2);
  1076.         cout << "   Изначальный список 2: "; list2.print();
  1077.         list2.insert(list2.begin() + 1, 42);
  1078.         cout << "   Список 2 после применения метода insert(list2.begin() + 1, 42) : "; list2.print();
  1079.         list2.clear(); list2.push_back(0); list2.push_back(0);
  1080.         list2.insert(list2.begin() + 1, 5, 42);
  1081.         cout << "   Список 2 после применения метода insert(list2.begin() + 1, 5, 42) : "; list2.print();
  1082.         list2.clear(); list2.push_back(0); list2.push_back(0);
  1083.         list2.insert(list2.begin() + 1, list1.begin(), list1.end());
  1084.         cout << "   Список 2 после применения метода insert(list2.begin() + 1, list1.begin(), list1.end()) : "; list2.print();
  1085.         cout << endl;
  1086.     }
  1087.     {
  1088.         cout << "Метод erase: " << endl;
  1089.         LinkedList<int> list = LinkedList<int>(2);
  1090.         list.push_front(42); list.push_back(24); list.push_front(7); list.push_back(5);
  1091.         cout << "   Изначальный список: "; list.print();
  1092.         list.erase(list.begin() + 1);
  1093.         cout << "   Список после применения метода erase(list.begin() + 1) : "; list.print();
  1094.         list.clear();  list.push_front(0); list.push_front(0); list.push_front(42); list.push_back(24); list.push_front(7); list.push_back(5);
  1095.         list.erase(list.begin() + 1, list.end() - 1);
  1096.         cout << "   Список после применения метода erase(list.begin() + 1, list.end() - 1) : "; list.print();
  1097.         cout << endl;
  1098.     }
  1099.     cout << "Использование стандартных алгоритмов:" << endl;
  1100.     {
  1101.         cout << "   Метод max_element: " << endl;
  1102.         LinkedList<int> list = LinkedList<int>(0);
  1103.         list.push_front(5); list.push_front(42); list.push_front(7); list.push_front(7); list.push_back(5); list.push_back(5); list.push_back(1);
  1104.         cout << "       Изначальный список: "; list.print();
  1105.         auto it1 = list.begin();
  1106.         auto it2 = list.end() + 1;
  1107.         auto max_elem = max_element(it1, it2);
  1108.         cout << "       Результат max_element(it1, it2) : " << *max_elem << endl;
  1109.         cout << "   Метод min_element: " << endl;
  1110.         auto min_elem = min_element(it1, it2);
  1111.         cout << "       Результат min_element(it1, it2) : " << *min_elem << endl;
  1112.         cout << "   Метод adjacent_find: " << endl;
  1113.         auto adj = adjacent_find(it1, it2);
  1114.         cout << "       Результат adjacent_find(it1, it2) : " << *adj << endl;
  1115.         sort(it1, list.end() + 1);
  1116.         list.print();
  1117.     }
  1118. }  
Advertisement
RAW Paste Data Copied
Advertisement