write the codes in c++ please! Assignment 3 The bag data structure is a data str
ID: 3729723 • Letter: W
Question
write the codes in c++ please!
Assignment 3 The bag data structure is a data structure for storing the data in an unordered list. For the bag data structure, the insert function takes 0(1) and the remove function takes 0(1). However the search function for a large bag a lot of different values is O(n) Design a second bag data structure with the same specification of the first bag data structure that has a search time of O(Ig n) but the insert and remove time of O(n). This special bag data structure might be very useful in the real life. Suppose there is a list of items for sale, The users may search for specific items again and again (For multiple times) However removal and insertion to the item list may happen very infrequency This assignment is an example of a data structure with the same capabilities of the other but different performance that is designed for a different environment,Explanation / Answer
#include <iostream>
using namespace std;
#include <vector>
#include <unordered_map>
#include <stdlib.h>
template <typename T> class bucket{
int size;
std::vector<T> v;
std::unordered_map<T, int> m;
public:
bucket(){
size = 0;
std::vector<T>* v = new std::vector<T>();
std::unordered_map<T, int>* m = new std::unordered_map<T, int>();
}
void insert(const T& item){
//prevent insertion of duplicates
if(m.find(item) != m.end()){
exit(-1);
}
v.push_back(item);
m.emplace(item, size);
size++;
}
void remove(const T& item){
//exits if the item is not present in the list
if(m[item] == -1){
exit(-1);
}else if(m.find(item) == m.end()){
exit(-1);
}
int idx = m[item];
m[v.back()] = idx;
T itm = v[idx];
v.insert(v.begin()+idx, v.back());
v.erase(v.begin()+idx+1);
v.insert(v.begin()+size, itm);
v.erase(v.begin()+size);
m[item] = -1;
v.pop_back();
size--;
}
T& getRandom(){
int idx = rand()%size;
return v[idx];
}
bool lookup(const T& item){
if(m.find(item) == m.end()) return false;
return true;
}
void print(){
for(auto it = v.begin(); it != v.end(); it++){
std::cout<<*it<<" ";
}
}
};
int main() {
bucket<char>* b = new bucket<char>();
b->insert('d');
b->insert('k');
b->insert('l');
b->insert('h');
b->insert('j');
b->insert('z');
b->insert('p');
std::cout<<b->getRandom()<<std::endl;
b->print();
std::cout<<std::endl;
b->remove('h');
b->print();
return 0;
}
output
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.