//This code is created for a challenge to create our own map. Read first comment of this code to get entire description of the challenge. /* Suggestions are most welcome....! Feel free to give feedback. */ //1. special thanks to Anthony for helping on mymap[key] = value syntax as below: //https://www.sololearn.com/Discuss/2396475/?ref=app //Implement Your Own Map #include using namespace std; template struct node { T key; U value; node* left; node* right; node(T key,U value); }; template node::node(T key,U value) : key (key),value(value),left(nullptr),right(nullptr) {} template struct BST { node* root; BST(); node* insert(T,U); node* insert(node*,T,U); node* search(T); node* search(node*,T); node* findNodeWidMinValue(node*); node* erase(node*,T); node* erase(T); auto operator[](const T& key)->decltype(node{key,declval()}.value)&; }; template auto BST::operator[](const T& key)->decltype(node{key,declval()}.value)& { //return value if key is found //else add the key and default //value to the map auto res=(this->search(key)); if(res) return res->value; else return (this->insert(key,U{}))->value; } template BST::BST() : root(nullptr){} template node* BST::insert(node* ptr,T key,U value) { node* newnode = new node(key,value); if (ptr==nullptr) ptr = newnode; else if(ptr->key==key) ptr->value = value; else if(key < ptr->key) ptr->left = insert(ptr->left,key,value); else if(key > ptr->key) ptr->right = insert(ptr->right,key,value); return ptr; } template node* BST::insert(T key,U value) { root = insert(root,key,value); return root; } template node* BST::search(node* ptr,T key) { if(ptr==nullptr || key == ptr->key) return ptr; if(key > ptr->key) { return search(ptr->right,key); } return search(ptr->left,key); } template node* BST::search(T key) { return search(root,key); } template node* BST::findNodeWidMinValue(node* ptr) { node* cur = ptr; while(cur && cur->left!=nullptr) cur = cur->left; return cur; } template node* BST::erase(node* ptr,T key) { if(ptr==nullptr) return ptr; if(key > ptr->key) { ptr->right = erase(ptr->right,key); } else if (key < ptr->key) { ptr->left = erase(ptr->left,key); } else //key is matched and we need to delete this node now { if(ptr==nullptr || ptr->left==nullptr) { node* tmp = ptr->right; delete ptr; return tmp; } else if(ptr->right==nullptr) { node* tmp = ptr->left; delete ptr; return tmp; } node* tmp = findNodeWidMinValue(ptr->right); ptr->key = tmp->key; ptr->right = erase(ptr->right,tmp->key); } return ptr; } template node* BST::erase(T key) { root = erase(root,key); return root; } template using mymap = BST; int main() { //search data int tosearch; node* pdata; mymap obj; obj.insert(1,"Mr. a"); obj.insert(2,"Mrs. b"); //obj.insert(1,"Mr. A"); obj[1] = "Mr. A"; obj.insert(3,"Miss. c"); tosearch = 1; pdata = obj.search(tosearch); if(pdata==nullptr) cout << "search completed : " << tosearch << " is not found\n"; else cout << "search completed : " << tosearch << " " << pdata->value << "\n"; obj.erase(10); obj.erase(1); tosearch = 1; pdata = obj.search(tosearch); if(pdata==nullptr) cout << "search completed : " << tosearch << " is not found\n"; else cout << "search completed : " << tosearch << " " << pdata->value << "\n"; tosearch = 3; pdata = obj.search(tosearch); if(pdata==nullptr) cout << "search completed : " << tosearch << " is not found\n"; else cout << "search completed : " << tosearch << " " << pdata->value << "\n"; tosearch = 9; pdata = obj.search(tosearch); if(pdata==nullptr) cout << "search completed : " << tosearch << " is not found\n"; else cout << "search completed : " << tosearch << " " << pdata->value << "\n"; return 0; }

Challenge [Own Map]