Hashed Array, a set type data structure which has O(1) insertion, O(1) removal, and O(1) uniformly randomly retrieval.
#include <iostream> | |
#include <vector> | |
#include <map> | |
#include <cmath> | |
using namespace std; | |
// Hashed array | |
template <class T> | |
class HashedArray | |
{ | |
public: | |
void insert(T x); | |
void remove(T x); | |
T getRandom(); | |
int size(); | |
void print(); | |
private: | |
vector<T> a; | |
map<T, int> h; | |
}; | |
template <class T> | |
void HashedArray<T>::insert(T x) | |
{ | |
int i = a.size(); | |
a.push_back(x); | |
h[x] = i; | |
} | |
template <class T> | |
void HashedArray<T>::remove(T x) | |
{ | |
if(h.find(x) == h.end()) return; | |
int m = a.size()-1; | |
T d = a[m]; | |
int i = h[x]; | |
a[i] = d; | |
h[d] = i; | |
a.erase(a.end()-1); | |
h.erase(x); | |
} | |
template <class T> | |
T HashedArray<T>::getRandom() | |
{ | |
int r = rand() % a.size(); | |
return a[r]; | |
} | |
template <class T> | |
int HashedArray<T>::size() | |
{ | |
return a.size(); | |
} | |
template <class T> | |
void HashedArray<T>::print() | |
{ | |
for (int i=0; i<a.size(); i++) | |
cout << a[i] << " "; | |
cout << endl; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment