C++ solution with unordered_multimap

  • 3
    class RandomizedCollection {
        unordered_multimap<int, int> Map;
        typedef unordered_multimap<int,int>::iterator Itr;
        vector<Itr> Vec;
        /** Initialize your data structure here. */
        RandomizedCollection() {
        /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
        bool insert(int val) {
            bool ret = Map.count(val) == 0;
            auto it = Map.insert({val,-1});
            it->second = Vec.size();  //change the -1 to the index in the vector
            return true;
        /** Removes a value from the set. Returns true if the set contained the specified element. */
        bool remove(int val) {
            if(Vec.empty()) return false;
            auto it = Map.find(val); if(it == Map.end() ) return false;
            int index = it->second;
            (Vec.back())->second = index;  //change the object inside the Map
            swap(Vec[Vec.size()-1], Vec[index]);  //move the object to be removed to the back of vector
            return true;
        /** Get a random element from the set. */
        int getRandom() {
            int random = std::rand();
            random %= Vec.size();
            return Vec[random]->first; //First is the value! Don't be careless!
     * 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();

  • 2

    I think save the iterator is unsafe.
    When you change the Map (like insert, erase), the iterator you saved might be invalid.

  • 1

    This solution has bug because I was using it.
    When you do
    Map.find(Vec.back())->second = index;
    Actually you are not sure if the element you changed is really Vec.back or its identical key element.

  • 0

    @ChenLiangyuX you are right, invalidation will happen when excessive insertions come in and thus trigger a rehash.
    this solution is better:


Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.