Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- template <typename T>
- class Vector {
- public:
- Vector() : size_(0), capacity_(4), arr_(new T[4]) {}
- explicit Vector(const int vector_capacity) : size_(0), capacity_(vector_capacity), arr_(new T[vector_capacity]) {}
- Vector(const Vector& other) : size_(other.size_), capacity_(other.capacity_), arr_(new T[capacity_]) {
- for (int i = 0; i < size_; i++) {
- arr_[i] = other.arr_[i];
- }
- total_number_elements_ += size_;
- } // конструктор копирования
- Vector(const initializer_list<T>& list) : size_(list.size()), capacity_(list.size()), arr_(new T[list.size()]) {
- int i = 0;
- for (const T& element : list) {
- arr_[i] = element;
- i++;
- }
- }
- Vector& operator=(const Vector& other) {
- if (&other != this) { // проверка на самоприсваивание
- total_number_elements_ += other.size_ - size_; // общее количество увеличивается (уменьшается) на разность элементов
- size_ = other.size_;
- capacity_ = other.capacity_;
- delete[] arr_;
- arr_ = new T[capacity_];
- for (int i = 0; i < size_; i++) {
- arr_[i] = other.arr_[i];
- }
- }
- return *this;
- } // копирующий оператор присваивания =
- Vector(Vector&& other) : size_(other.size_), capacity_(other.capacity_), arr_(other.arr_) {
- other.arr_ = nullptr;
- other.size_ = 0;
- other.capacity_ = 0;
- } // конструктор перемещения
- Vector& operator=(Vector&& other) {
- if (&other != this) {
- total_number_elements_ += other.size_ - size_; // общее количество увеличивается (уменьшается) на разность элементов
- size_ = other.size_;
- capacity_ = other.capacity_;
- delete[] arr_;
- arr_ = other.arr_;
- other.arr_ = nullptr;
- other.size_ = 0;
- other.capacity_ = 0;
- }
- return *this;
- } // перемещающий оператор присваивания =
- void push_back(const T& value) {
- check_capacity();
- arr_[size_] = value;
- size_++;
- total_number_elements_++;
- }
- void pop_back() {
- if (size_ > 0) {
- size_--;
- }
- total_number_elements_--;
- }
- void insert(const int index, const T& value) {
- if (index < 0 || index > size_) {
- cout << "Некорректный индекс" << endl;
- return;
- }
- check_capacity();
- for (int i = size_; i > index; i--) {
- arr_[i] = arr_[i - 1];
- }
- arr_[index] = value;
- size_++;
- total_number_elements_++;
- }
- void erase(const int index) {
- if (index < 0 || index >= size_) {
- cout << "Некорректный индекс" << endl;
- return;
- }
- for (int i = index; i < size_ - 1; i++) {
- arr_[i] = arr_[i + 1];
- }
- size_--;
- total_number_elements_--;
- }
- T& operator[](const int index) {
- if (index < 0 || index >= size_) {
- cout << "Некорректный индекс" << endl;
- }
- return arr_[index];
- }
- const T& operator[](const int index) const {
- if (index < 0 || index >= size_) {
- cout << "Некорректный индекс" << endl;
- }
- return arr_[index];
- }
- int size() const {
- return size_;
- }
- int capacity() const {
- return capacity_;
- }
- bool operator==(const Vector& right) const {
- if (right.size_ != size_) {
- return false;
- }
- for (int i = 0; i < size_; i++) {
- if (arr_[i] != right.arr_[i])
- return false;
- }
- return true;
- }
- bool operator!=(const Vector& right) const {
- return !(*this == right);
- }
- void print() const {
- for (int i = 0; i < size_; i++) {
- cout << arr_[i] << " ";
- }
- cout << endl;
- }
- static int get_total_number_elements() {
- return total_number_elements_;
- }
- ~Vector() {
- delete[] arr_;
- total_number_elements_ -= size_;
- }
- private:
- void check_capacity() {
- if (size_ == capacity_) {
- int* temp = new int[capacity_ * 2];
- for (int i = 0; i < size_; i++) {
- temp[i] = arr_[i];
- }
- delete[] arr_;
- arr_ = temp;
- capacity_ *= 2;
- }
- }
- int size_; // текущее количество элементов
- int capacity_; // емкость хранилища
- T* arr_; // хранилище
- static int total_number_elements_; // общее количество элементов по всем векторам
- };
- template <typename T>
- int Vector<T>::total_number_elements_ = 0;
- template <typename T>
- class List {
- public:
- List() : size_(0), head_(nullptr), last_(nullptr) {}
- List(const List& other) : size_(0), head_(nullptr), last_(nullptr) {
- Node* temp = other.last_;
- while (temp != nullptr) {
- push_front(temp->value);
- temp = temp->prev;
- }
- }
- List(List&& other) : size_(other.size_), head_(other.head_), last_(other.last_) {
- other.head_ = other.last_ = nullptr;
- }
- List& operator=(const List& other) {
- if (this != &other) {
- clear();
- Node* temp = other.last_;
- while (temp != nullptr) {
- push_front(temp->value);
- temp = temp->prev;
- }
- }
- return *this;
- }
- List& operator=(List&& other) {
- if (this != &other) {
- clear();
- size_ = other.size_;
- head_ = other.head_;
- last_ = other.last_;
- other.head_ = other.last_ = nullptr;
- }
- return *this;
- }
- void push_front(const T& value) {
- if (size_ == 0) {
- last_ = head_ = new Node{ value, nullptr, nullptr };
- size_++;
- return;
- }
- Node* temp = new Node{ value, head_, nullptr };
- head_->prev = temp;
- head_ = temp;
- size_++;
- }
- void push_back(const T& value) {
- if (size_ == 0) {
- last_ = head_ = new Node{ value, nullptr, nullptr };
- size_++;
- return;
- }
- Node* temp = new Node{ value, nullptr, last_ };
- last_->next = temp;
- last_ = temp;
- size_++;
- }
- void pop_front() {
- if (size_ > 0) {
- if (size_ == 1) {
- delete head_;
- last_ = head_ = nullptr;
- size_--;
- return;
- }
- Node* temp = head_;
- head_ = head_->next;
- delete temp;
- head_->prev = nullptr;
- size_--;
- }
- }
- void pop_back() {
- if (size_ > 0) {
- if (size_ == 1) {
- delete head_;
- last_ = head_ = nullptr;
- size_--;
- return;
- }
- Node* temp = last_;
- last_ = last_->prev;
- delete temp;
- last_->next = nullptr;
- size_--;
- }
- }
- void insert(const int index, const T& value) {
- if (index == 0) {
- push_front(value);
- return;
- }
- if (index == size_) {
- push_back(value);
- return;
- }
- if (index > 0 && index < size_) {
- Node* temp = head_;
- for (int i = 0; i < index - 1; i++) {
- temp = temp->next;
- }
- Node* buf = new Node{ value, temp->next, temp };
- temp->next->prev = buf;
- temp->next = buf;
- size_++;
- }
- }
- void erase(const int index) {
- if (index == 0) {
- pop_front();
- return;
- }
- if (index == size_ - 1) {
- pop_back();
- return;
- }
- if (index > 0 && index < size_ - 1) {
- Node* temp = head_;
- for (int i = 0; i < index - 1; i++) {
- temp = temp->next;
- }
- Node* buf = temp->next->next;
- delete temp->next;
- temp->next = buf;
- buf->prev = temp;
- size_--;
- }
- }
- T& operator[] (const int index) {
- if (index >= 0 && index < size_) {
- Node* temp = head_;
- for (int i = 0; i < index; i++) {
- temp = temp->next;
- }
- return temp->value;
- }
- }
- const T& operator[] (const int index) const {
- if (index >= 0 && index < size_) {
- Node* temp = head_;
- for (int i = 0; i < index; i++) {
- temp = temp->next;
- }
- return temp->value;
- }
- }
- bool operator==(const List& other) const {
- if (size_ != other.size_) {
- return false;
- }
- Node* temp = head_;
- Node* other_temp = other.head_;
- while (temp != nullptr) {
- if (temp->value != other_temp->value) {
- return false;
- }
- temp = temp->next;
- other_temp = other_temp->next;
- }
- return true;
- }
- bool operator!=(const List& other) const {
- return !(*this == other);
- }
- int find(const T& value) const {
- int index = 0;
- Node* temp = head_;
- while (temp != nullptr && temp->value != value) {
- temp = temp->next;
- index++;
- }
- if (temp != nullptr) {
- return index;
- }
- return -1;
- }
- T& front() {
- if (head_ != nullptr) {
- return head_->value;
- }
- }
- const T& front() const {
- if (head_ != nullptr) {
- return head_->value;
- }
- }
- T& back() {
- if (last_ != nullptr) {
- return last_->value;
- }
- }
- const T& back() const {
- if (last_ != nullptr) {
- return last_->value;
- }
- }
- void print() {
- Node* temp = head_;
- while (temp != nullptr) {
- cout << temp->value << " ";
- temp = temp->next;
- }
- cout << endl;
- }
- int size() const {
- return size_;
- }
- void clear() {
- while (head_ != nullptr) {
- pop_front();
- }
- }
- ~List() {
- clear();
- }
- private:
- struct Node { // двусвязный список состоит из узлов
- T value; // узел хранит информативную часть
- Node* next; // указатель на следующий узел в списке
- Node* prev; // указатель на предыдущий узел
- };
- int size_;
- Node* head_;
- Node* last_;
- };
- template<typename T>
- class Set {
- public:
- struct Node {
- T value;
- Node* left;
- Node* right;
- Node* parent;
- };
- Set() : root_(nullptr), size_(0) {}
- Set(const initializer_list<T>& list) : root_(nullptr), size_(0) {
- for (const T& element : list) {
- insert(element);
- }
- }
- Set(const Set& other) : root_(copy(other.root_, nullptr)), size_(other.size_) {}
- Set(Set&& other) : root_(other.root_), size_(other.size_) {
- other.root_ = nullptr;
- }
- Set& operator=(const Set& other) {
- if (this != &other) {
- clear();
- size_ = other.size_;
- root_ = copy(other.root_, nullptr);
- }
- return *this;
- }
- Set& operator=(Set&& other) {
- if (this != &other) {
- clear();
- size_ = other.size_;
- root_ = other.root_;
- other.root_ = nullptr;
- }
- return *this;
- }
- void insert(const T& val) {
- if (root_ == nullptr) {
- root_ = new Node{ val, nullptr, nullptr, nullptr };
- size_++;
- return;
- }
- Node* parent = nullptr;
- Node* node = root_;
- while (node != nullptr && node->value != val) {
- parent = node;
- node = node->value > val ? node->left : node->right;
- }
- if (node == nullptr) {
- node = new Node{ val, nullptr, nullptr, parent };
- parent->value > val ? parent->left = node : parent->right = node;
- size_++;
- }
- }
- void erase(const T& val) {
- Node* parent = nullptr;
- Node* node = root_;
- while (node != nullptr && node->value != val) {
- parent = node;
- node = node->value > val ? node->left : node->right;
- }
- if (node != nullptr) {
- if (node->left == nullptr && node->right == nullptr) {
- if (node == root_) {
- root_ = nullptr;
- }
- else {
- node == parent->right ? parent->right = nullptr : parent->left = nullptr;
- }
- delete node;
- }
- else if (node->left == nullptr) {
- node->right->parent = node->parent;
- if (node == root_) {
- root_ = node->right;
- }
- else {
- node == parent->right ? parent->right = node->right : parent->left = node->right;
- }
- delete node;
- }
- else if (node->right == nullptr) {
- node->left->parent = node->parent;
- if (node == root_) {
- root_ = node->left;
- }
- else {
- node == parent->right ? parent->right = node->left : parent->left = node->left;
- }
- delete node;
- }
- else {
- Node* temp = min(node->right);
- node->value = temp->value;
- if (temp->right != nullptr) {
- temp->right->parent = temp->parent;
- }
- temp == temp->parent->right ? temp->parent->right = temp->right : temp->parent->left = temp->right;
- delete temp;
- }
- size_--;
- }
- }
- Node* min(Node* node) {
- if (node != nullptr) {
- while (node->left != nullptr) {
- node = node->left;
- }
- }
- return node;
- }
- Node* max(Node* node) {
- if (node != nullptr) {
- while (node->right != nullptr) {
- node = node->right;
- }
- }
- return node;
- }
- void print() {
- print(root_);
- cout << endl;
- }
- int size() const {
- return size_;
- }
- void clear() {
- clear(root_);
- root_ = nullptr;
- size_ = 0;
- }
- Node* find(const T& val) {
- Node* node = root_;
- while (node != nullptr && node->value != val) {
- node = node->value > val ? node->left : node->right;
- }
- return node;
- }
- Node* begin() {
- return min(root_);
- }
- Node* end() {
- return max(root_);
- }
- bool operator==(const Set& other) {
- return size_ == other.size_ ? compare(min(root_), min(other.root_)) : false;
- }
- bool operator!=(const Set& other) {
- return !(*this == other);
- }
- ~Set() {
- clear(root_);
- }
- private:
- // вариант сравнения деревьев на случай разной топологии но одинакового размера
- bool compare(Node* a, Node* b) {
- if (a == nullptr && b == nullptr) {
- return true;
- }
- return a->value == b->value && compare(next(a), next(b));
- }
- Node* next(Node* node) {
- if (node != nullptr) {
- if (node->right != nullptr) {
- return min(node->right);
- }
- Node* temp = node->parent;
- while (temp != nullptr && node->value > temp->value) {
- temp = temp->parent;
- }
- return temp;
- }
- return node;
- }
- Node* prev(Node* node) {
- if (node != nullptr) {
- if (node->left != nullptr) {
- return max(node->left);
- }
- Node* temp = node->parent;
- while (temp != nullptr && node->value < temp->value) {
- temp = temp->parent;
- }
- return temp;
- }
- return node;
- }
- Node* copy(Node* node, Node* parent) {
- if (node == nullptr) {
- return nullptr;
- }
- Node* temp = new Node{ node->value, nullptr, nullptr, parent };
- temp->left = copy(node->left, temp);
- temp->right = copy(node->right, temp);
- return temp;
- }
- void clear(Node* node) {
- if (node != nullptr) {
- clear(node->left);
- clear(node->right);
- delete node;
- }
- }
- void print(Node* node) {
- if (node != nullptr) {
- print(node->left);
- cout << node->value << " ";
- // раскомментировать для проверки построения дерева
- /* cout << " value " << node->value << " ";
- if (node->parent) {
- cout << " parent " << node->parent->value;
- }
- else {
- cout << '\t';
- }
- if (node->left) {
- cout << " left " << node->left->value;
- }
- else {
- cout << '\t';
- }
- if (node->right) {
- cout << " right " << node->right->value;
- }
- else {
- cout << '\t';
- }
- cout << " " << node << endl;*/
- print(node->right);
- }
- }
- Node* root_;
- int size_;
- };
- int main() {
- setlocale(LC_ALL, "ru");
- // проверить функционал каждого класса
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement