So I recently implemented "First unique number" on Leetcode. The question, for reference, goes something like this:

You have a queue of integers, you need to retrieve the first unique integer in the queue.

Implement the FirstUnique class:

* FirstUnique(int[] nums) Initializes the object with the numbers in
the queue.
* int showFirstUnique() returns the value of the first unique integer of the queue, and returns -1 if there is no such integer.
* void add(int value) insert value to the queue.

My C++ implementation using STL uses an unordered\_map and a list. The map stores the elements of the queue as keys and stores the iterator pointing to the element in the list and a boolean indicating to indicate the removal of the value from the list when it is no longer unique. The addition and removal of elements to the list appear to be constant time operations. However, my solution is much slower compared to another solution which uses a queue and iterates through the queue (basically it appears to be O(n) compared to my O(1)).

Here is the apparently worse solution:

```
class FirstUnique {
        private:
        queue<int> q;
        unordered_map<int, int> count;
        public:
        FirstUnique(vector<int>& nums) {
            for(int num: nums){
                count[num]++;
                q.push(num);
            }
        }

        int showFirstUnique() {
            while(!q.empty() && count[q.front()] > 1){
                q.pop();
            }
            if(q.empty()){
                return -1;
            }
            else{
                return q.front();
            }
        }

        void add(int value) {
            if(++count[value] == 1){
                q.push(value);
            }
        }
    };

```

This is my solution:

```
class FirstUnique {
    public:
    unordered_map<int, pair<list<int>::iterator, bool>> hashmap;
    list<int> l;
    FirstUnique(vector<int>& nums) {
    for(auto it=nums.begin(); it!=nums.end(); it++)
        add(*it);
    }

    int showFirstUnique() {
        if (l.empty())
            return -1;
        return l.back();
    }

    void add(int value) {
        unordered_map<int, pair<list<int>::iterator, bool>>::iterator it = hashmap.find(value);
        if(it == hashmap.end())
        {
            l.push_front(value);
            hashmap[value] = make_pair(l.begin(), false) ;
        }

        else
        {
            if((it->second).second == false)
            {
                l.erase((it->second).first);
                (it->second).second = true;
            }
        } 
    }
 };

```

What I don't understand is that despite my fast solution, the runtime is much slower. The one with the queue ran in 328ms and mine ran in 532ms on Leetcode. I can understand my solution being memory heavy but can't understand why it is slower.