381 Insert Delete GetRandom O(1) - Duplicates allowed

class RandomizedCollection {
public:
    unordered_map<int, unordered_set<int>> vals;
    vector<int> val_array;
    /** Initialize your data structure here. */
    RandomizedCollection() {
    }

    /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
    bool insert(int val) {
        bool res = true;
        if ( vals.find(val) != vals.end() ) res = false;
        val_array.push_back(val);
        vals[val].insert(int(val_array.size())-1);
        return res;
    }

    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    bool remove(int val) {
      if ( vals.find(val) == vals.end() ) return false;
      int n = val_array.size();
      int i = *(vals[val].begin());
      if ( val_array[n-1] == val ) {
        val_array.erase(val_array.begin() + n-1);
        vals[val].erase(vals[val].find(n-1));
        if ( vals[val].empty() ) vals.erase(vals.find(val));
        return true;
      }
      int last = val_array[n-1];
      val_array[i] = last;
      auto it = vals[last].find(n-1);
      vals[last].erase(it);
      vals[last].insert(i);
      val_array.erase(val_array.begin() + n-1);
      vals[val].erase(vals[val].find(i));
      if ( vals[val].empty() ) vals.erase(vals.find(val));
      return true;
    }

    /** Get a random element from the collection. */
    int getRandom() {
        int n = val_array.size();
        if ( n == 0 ) return -1;
        return val_array[random()%n];
    }
};

/**
 * Your RandomizedCollection object will be instantiated and called as such:
 * RandomizedCollection obj = new RandomizedCollection();
 * bool param_1 = obj.insert(val);
 * bool param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */