fork download
copy 
  1. #include <iostream>
  2. #include <unordered_map>
  3. #include<vector>
  4. #include<stdlib.h>
  5. #include<time.h>
  6.  
  7. using namespace std;
  8.  
  9. class MyDS
  10. {
  11. 	private:
  12. 	std::unordered_map<int,int> ht;
  13. 	std::vector<int> vec;
  14.  
  15. 	public:
  16. 	void add(int num);
  17. 	void remove(int num);
  18. 	int getRandom();
  19. 	int search(int num);
  20. 	void traverse();
  21. };
  22.  
  23.     void MyDS::add(int num)
  24. 	{
  25. 		cout<<"In add"<<endl;
  26. 		if(ht.find(num)==ht.end())
  27. 		{
  28. 			vec.push_back(num);
  29. 			int sz = vec.size();
  30. 			ht.insert(pair<int,int>(num,sz-1));
  31. 		}
  32. 		else
  33. 		   return;
  34. 	}
  35.  
  36. 	void MyDS::remove(int num)
  37. 	{
  38. 		if(ht.find(num)!=ht.end())
  39. 		{
  40. 			int indx = ht.find(num)->second; 
  41. 			int sz = vec.size();
  42. 			vec[indx] = vec[sz-1];
  43. 			vec.erase(vec.begin() + sz-2);
  44. 			ht.erase(ht.find(num)->first);
  45. 		}
  46. 		else
  47. 			return;
  48. 	}
  49.  
  50. 	int MyDS::getRandom()
  51. 	{
  52. 		srand (time(NULL));
  53. 		int rnum = rand();
  54. 		int indx = rnum%(vec.size());
  55. 		return vec[indx];
  56. 	}
  57.  
  58. 	int MyDS:: search(int num)
  59. 	{
  60. 		if(ht.find(num)!=ht.end())
  61. 		{
  62. 			return ht.find(num)->second;
  63. 		}
  64. 		else
  65. 			return -1;
  66. 	}
  67.  
  68. 	void MyDS:: traverse()
  69. 	{
  70. 		for(int i=0;i<vec.size();i++)
  71. 			cout<<" "+vec[i];
  72. 		cout<<endl;
  73. 	}
  74.  
  75. int main() {
  76.         MyDS ds;
  77.         ds.add(10);
  78.         ds.add(20);
  79.         ds.add(30);
  80.         ds.add(40);
  81.         ds.traverse();
  82.         cout<<ds.search(30)<<endl;
  83.         ds.remove(20);
  84.         ds.add(50);
  85.         ds.traverse();
  86.         cout<<ds.search(50)<<endl;
  87.         cout<<ds.getRandom()<<endl;
  88. 	return 0;
  89. }
Success #stdin #stdout 0s 3232KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
In add
In add
In add
In add
����|
2
In add
����|����|���
3
40
https://ideone.com/8UqWW6
data-structure-that-supports-insert-delete-search-and-getrandom-in-constant-time
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!