Skip to content

Instantly share code, notes, and snippets.

@oir oir/HashedArray.cpp
Created May 17, 2013

Embed
What would you like to do?
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
You can’t perform that action at this time.