Skip to content
The Chat Archive
gpt-3.5-turbo-0301· OpenAI WildChat-4.8M (AI2)

Напиши код на C++. Самостоятельно реализовать основные методы класса multimap, не…

  1. User

    Напиши код на C++. Самостоятельно реализовать основные методы класса multimap, не используя стандартный класс. В реализации должны присутствовать такие методы как: find(), count() и оператор индексирования [].

  2. 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; }

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.