C++ solution with unordered_multimap


  • 3
    Q
    
    class RandomizedCollection {
        unordered_multimap<int, int> Map;
        typedef unordered_multimap<int,int>::iterator Itr;
        vector<Itr> Vec;
    public:
        /** Initialize your data structure here. */
        RandomizedCollection() {
            std::srand(std::time(0));
            std::srand(std::time(0));
        }
        
        /** 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
            Vec.push_back(it);
            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
            Vec.pop_back();
            Map.erase(it);
            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
    C

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


  • 1
    C

    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
    Q

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

    https://discuss.leetcode.com/topic/54381/c-128m-solution-real-o-1-solution


Log in to reply
 

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