Question

How to create a data structure that supports insert, remove, print and get random element in C++

Answer 1

#include <iostream>
#include <vector>
#include <map>

class Program {
public:
    std::vector<int> vec;
    std::map<int,int> mp;
    
    Program() {}
    
    bool insert(int val) {
        if (mp.find(val) == mp.end()){
            vec.push_back(val);
            mp.insert({val, vec.size() - 1});
            
            return true;
        }
        
        return false;
    }
    
    bool remove(int val) {
        if (mp.find(val) != mp.end()){
            int last = vec.back();
            
            mp[last] = mp[val];
            vec[mp[val]] = last;
            vec.pop_back();
            mp.erase(val);
            
            return true;
        }
        
        return false;
    }
    
    int getRandom() {
        int rnd = rand() % vec.size();

        return vec[rnd];
    }
    
    void print() {
        for (auto const &n: vec) {
            std::cout << n << " ";
        }
    }
};

int main()
{
    Program *p = new Program();
    
    srand(time(NULL));
    
    p->insert(6);
    p->insert(9);
    p->insert(8);
    p->insert(2);
    p->insert(1);
    
    std::cout << p->getRandom() << "\n";
    
    p->remove(2);
    
    p->print();
    
    delete p;
}




/*
run:

8
6 9 8 1

*/

 

70+ SQL courses for beginners and professionals

Answer 2

#include <iostream>
#include <vector>

class Program {
public:
    std::vector<int> vec;
    
    Program() {}
    
    void insert(int val) {
        vec.push_back(val);
    }
    
    void remove(int index) {
        int last = vec.back();

        vec[index] = last;
        vec.pop_back();
    }
    
    int getRandom() {
        int rnd = rand() % vec.size();

        return vec[rnd];
    }
    
    void print() {
        for (auto const &n: vec) {
            std::cout << n << " ";
        }
    }
};

int main()
{
    Program *p = new Program();
    
    srand(time(NULL));
    
    p->insert(6);
    p->insert(9);
    p->insert(8);
    p->insert(2);
    p->insert(1);
    
    std::cout << p->getRandom() << "\n";
    
    p->remove(2);
    
    p->print();
    
    delete p;
}




/*
run:

8
6 9 1 2 

*/

 

70+ SQL courses for beginners and professionals