API tools faq
paste
35657

Untitled

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