Hashed Array, a set type data structure which has O(1) insertion, O(1) removal, and O(1) uniformly randomly retrieval.

HashedArray.cpp

#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;
}