Someone please help me with my C++, using vector and unordered_map


  • 0
    N

    It cannot pass compiler in the remove part,
    at this line:

    vector<int>::iterator it = *(ac[val].begin());
    

    Below is complete code:

    class RandomizedCollection {
    private:
        vector<int> boxes;
        unordered_map<int, unordered_set<vector<int>::iterator> > ac;   //accelration
    public:
        /** Initialize your data structure here. */
        RandomizedCollection() {
            boxes.clear();
            ac.clear();
            srand(time(NULL));
        }
    
        /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
        bool insert(int val) {
            boxes.push_back(val);
    
            if (ac.find(val) == ac.end()) {
                unordered_set<vector<int>::iterator> tempSet;
    
                tempSet.insert(boxes.begin() + boxes.size() - 1);
                ac.insert(make_pair(val, tempSet));
            } else {
                ac[val].insert(boxes.begin() + boxes.size() - 1);
            }
        }
    
        /** Removes a value from the collection. Returns true if the collection contained the specified element. */
        bool remove(int val) {
            if (ac.find(val) == ac.end())
                return false;
            vector<int>::iterator it = *(ac[val].begin());
            boxes.erase(it);
            ac[val].erase(it);
    
            if (ac[val].empty())
                ac.erase(val);
            return true;
        }
    
        /** Get a random element from the collection. */
        int getRandom() {
            int n = rand() % boxes.size();
            return boxes[n];
        }
    };
    
    

  • 0
    N

    Ok, I think the problem is that can I define:

    unordered_map<int, unordered_set<vector<int>::iterator> > ac;
    
    

  • 0
    N

    Ok, I finally find unordered_set need hash, and it cannot be directly applied to the iterator element inside.

    If I change to the set, it can pass, but the complexity will be a little bit worse.


Log in to reply
 

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