Design a data structure that supports insert , delete , search and getRandom in constant time | C ++ program to design a DS that supports following operations in Theta ( n ) timea ) Insertb ) Deletec ) Searchd ) getRandom ; class to represent the required data structure ; A resizable array ; A hash where keys are array elements and values are indexes in arr [ ] ; A Theta ( 1 ) function to add an element to MyDS data structure ; If element is already present , then nothing to do ; Else put element at the end of arr [ ] ; and hashmap also ; function to remove a number to DS in O ( 1 ) ; element not found then return ; remove element from map ; swap with last element in arr ; then remove element at back ; Update hash table for new index of last element ; Returns a random element from myStructure ; Find a random index from 0 to size - 1 ; Return element at randomly picked index ; Returns index of element if element is present , otherwise null ; Driver main
#include <bits/stdc++.h> NEW_LINE using namespace std ; class myStructure { vector < int > arr ; map < int , int > Map ; public : void add ( int x ) { if ( Map . find ( x ) != Map . end ( ) ) return ; int index = arr . size ( ) ; arr . push_back ( x ) ; Map . insert ( std :: pair < int , int > ( x , index ) ) ; } void remove ( int x ) { if ( Map . find ( x ) == Map . end ( ) ) return ; int index = Map . at ( x ) ; Map . erase ( x ) ; int last = arr . size ( ) - 1 ; swap ( arr [ index ] , arr [ last ] ) ; arr . pop_back ( ) ; Map . at ( arr [ index ] ) = index ; } int getRandom ( ) { srand ( time ( NULL ) ) ; int random_index = rand ( ) % arr . size ( ) ; return arr . at ( random_index ) ; } int search ( int x ) { if ( Map . find ( x ) != Map . end ( ) ) return Map . at ( x ) ; return -1 ; } } ; int main ( ) { myStructure ds ; ds . add ( 10 ) ; ds . add ( 20 ) ; ds . add ( 30 ) ; ds . add ( 40 ) ; cout << ds . search ( 30 ) << endl ; ds . remove ( 20 ) ; ds . add ( 50 ) ; cout << ds . search ( 50 ) << endl ; cout << ds . getRandom ( ) << endl ; }