Напиши код на C++. Самостоятельно реализовать основные методы класса multimap, не…
- User
Напиши код на C++. Самостоятельно реализовать основные методы класса multimap, не используя стандартный класс. В реализации должны присутствовать такие методы как: find(), count() и оператор индексирования [].
- Assistant
#include
using namespace std;
struct node{ int key,val; node *left,*right; };
class multimap{ private: node *root; int num_items;
node* insert(node* root, int key, int val){ // вставить элемент if(root == NULL){ node *new_node = new node; new_node->left = new_node->right = NULL; new_node->key = key; new_node->val = val; num_items++; return new_node; } if(key == root->key){ // если ключи совпали, добавляем элемент в конец списка значениями по ключу node *temp = root; while(temp->right != NULL){ temp = temp->right; } node *new_node = new node; new_node->left = temp; new_node->right = NULL; new_node->key = key; new_node->val = val; temp->right = new_node; num_items++; return root; } if(key < root->key){ root->left = insert(root->left,key,val); }else{ root->right = insert(root->right,key,val); } return root; } node* remove(node* root, int key, int val){ // удалить элемент if(root == NULL){ return root; } if(key == root->key){ // удаление элемента по значению if(root->val == val){ if(root->left == NULL && root->right == NULL){ delete root; root = NULL; }else if(root->left == NULL){ // если есть только правое поддерево node *temp = root->right; delete root; root = temp; }else if(root->right == NULL){ // если есть только левое поддерево node *temp = root->left; delete root; root = temp; }else{ // если есть оба поддерева node *temp = find_max(root->left); // ищем максимальный элемент в левом поддереве root->key = temp->key; // копируем его ключ и значение в удаляемый элемент root->val = temp->val; root->left = remove(root->left,temp->key,temp->val); // удаляем найденный элемент из левого поддерева } num_items--; }else{ // удаление значения по ключу node *temp = root->right; while(temp != NULL){ // ищем нужное значение if(temp->val == val){ temp->left->right = temp->right; // удаляем его из списка if(temp->right != NULL){ // если не последний элемент списка temp->right->left = temp->left; } node *deleted_node = temp; temp = temp->right; // переходим к следующему элементу списка delete deleted_node; // удаляем найденный элемент num_items--; }else{ temp = temp->right; } } } }else if(key < root->key){ root->left = remove(root->left,key,val); }else{ root->right = remove(root->right,key,val); } return root; } node* find(node* root, int key){ // найти элемент по ключу if(root == NULL){ return NULL; } if(key == root->key){ return root; } if(key < root->key){ return find(root->left,key); }else{ return find(root->right,key); } } int count(node* root, int key){ // посчитать количество значений по ключу if(root == NULL){ return 0; } if(key == root->key){ int count = 0; node *temp = root; while(temp != NULL){ // ищем последний элемент списка значений count++; temp = temp->right; } return count; } if(key < root->key){ return count(root->left,key); }else{ return count(root->right,key); } } node* find_max(node* root){ // найти максимальный элемент в дереве while(root->right != NULL){ root = root->right; } return root; } public: multimap(){ root = NULL; num_items = 0; } void insert(int key, int val){ // вставить элемент root = insert(root,key,val); } void remove(int key, int val){ // удалить элемент root = remove(root,key,val); } node* find(int key){ // найти элемент по ключу return find(root,key); } int count(int key){ // посчитать количество значений по ключу return count(root,key); } int operator[](int key){ // значение по ключу node *temp = find(root,key); if(temp == NULL){ insert(key,0); // если ключ отсутствует, добавляем элемент со значением по умолчанию 0 temp = find(root,key); } return temp->val; } int size(){ // размер контейнера return num_items; }};
int main(){ multimap my_map; my_map.insert(1,101); my_map.insert(2,102); my_map.insert(1,103); my_map.insert(3,104); my_map.insert(1,105); cout << "Count of 1: " << my_map.count(1) << endl; cout << "Count of 2: " << my_map.count(2) << endl; cout << "Count of 3: " << my_map.count(3) << endl; my_map.remove(1,102); my_map.remove(2,102); my_map.remove(3,102); cout << "Size: " << my_map.size() << endl; cout << "Value of 1: " << my_map[1] << endl; cout << "Value of 2: " << my_map[2] << endl; cout << "Value of 3: " << my_map[3] << endl; return 0; }
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.