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

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

  1. User

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

  2. Assistant

    #include #include using namespace std;

    // Класс узла (для дерева) template <typename Key, typename Value> class Node { public: Key key; Value value; vector vals; // для хранения нескольких значений с одинаковыми ключами Node* left; Node* right;

    Node(Key k, Value v) {
        key = k;
        value = v;
        left = nullptr;
        right = nullptr;
    }
    
    ~Node() {}
    

    };

    // Класс дерева template <typename Key, typename Value> class Multimap { private: Node<Key, Value>* root;

    Node<Key, Value>* insert(Node<Key, Value>* node, Key key, Value val) {
        if (node == nullptr) {
            return new Node<Key, Value>(key, val);
        }
        if (key < node->key) {
            node->left = insert(node->left, key, val);
        } else if (key > node->key) {
            node->right = insert(node->right, key, val);
        } else {
            node->vals.push_back(val); // если есть элемент с таким ключом, добавляем его значение в список значений
        }
        return node;
    }
    
    vector<Value> find(Node<Key, Value>* node, Key key) {
        vector<Value> res;
        if (node == nullptr) {
            return res;
        }
        if (key < node->key) {
            return find(node->left, key);
        }
        if (key > node->key) {
            return find(node->right, key);
        }
        res = node->vals;
        return res;
    }
    
    int count(Node<Key, Value>* node, Key key) {
        int res = 0;
        if (node == nullptr) {
            return res;
        }
        if (key < node->key) {
            return count(node->left, key);
        }
        if (key > node->key) {
            return count(node->right, key);
        }
        res = node->vals.size();
        return res;
    }
    

    public: Multimap() { root = nullptr; }

    ~Multimap() {}
    
    void insert(Key key, Value val) {
        root = insert(root, key, val);
    }
    
    vector<Value> find(Key key) {
        vector<Value> res = find(root, key);
        return res;
    }
    
    int count(Key key) {
        int res = count(root, key);
        return res;
    }
    
    vector<Value>& operator[](Key key) {
        return find(root, key);
    }
    

    };

    int main() { Multimap<int, int> mm; mm.insert(1, 1); mm.insert(2, 2); mm.insert(2, 3); mm.insert(3, 4); mm.insert(3, 5); mm.insert(3, 6);

    vector<int> vals = mm.find(2);
    for (int val : vals) {
        cout << val << " ";
    }
    cout << endl;
    
    int cnt = mm.count(3);
    cout << cnt << endl;
    
    mm[2].push_back(4);
    vals = mm.find(2);
    for (int val : vals) {
        cout << val << " ";
    }
    cout << endl;
    return 0;
    

    }

  3. User

    Исправь ошибки в данном коде (функция vector& operator[](Key key))

  4. Assistant

    template <typename Key, typename Value> class Multimap { private: Node<Key, Value>* root;

        Node<Key, Value>* insert(Node<Key, Value>* node, Key key, Value val) {
            if (node == nullptr) {
                return new Node<Key, Value>(key, val);
            }
            if (key < node->key) {
                node->left = insert(node->left, key, val);
            } else if (key > node->key) {
                node->right = insert(node->right, key, val);
            } else {
                node->vals.push_back(val);
            }
            return node;
        }
        
        vector<Value>& find(Node<Key, Value>* node, Key key) {
            if (node == nullptr) {
                node = insert(node, key, Value());
            }
            if (key < node->key) {
                return find(node->left, key);
            }
            if (key > node->key) {
                return find(node->right, key);
            }
            return node->vals;
        }
        
        int count(Node<Key, Value>* node, Key key) {
            if (node == nullptr) {
                return 0;
            }
            if (key < node->key) {
                return count(node->left, key);
            }
            if (key > node->key) {
                return count(node->right, key);
            }
            return node->vals.size();
        }
    
    public:
        Multimap() {
            root = nullptr;
        }
        
        ~Multimap() {}
        
        void insert(Key key, Value val) {
            root = insert(root, key, val);
        }
        
        vector<Value>& operator[](Key key) {
            return find(root, key);
        }
        
        int count(Key key) {
            return count(root, key);
        }
    

    };

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