all one data structure

还是用list和map 太久没有用list，list的insert竟然是position前！！

list insert

Insert elements The container is extended by inserting new elements before the element at the specified position.

This effectively increases the list size by the amount of elements inserted.

Unlike other standard sequence containers, list and forward_list objects are specifically designed to be efficient inserting and removing elements in any position, even in the middle of the sequence.

The arguments determine how many elements are inserted and to which values they are initialized:

class AllOne {
public:
    /** Initialize your data structure here. */
    AllOne() {

    }

    /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
    void inc(string key) {
        if(m.find(key)==m.end()){
            if(l.front().first!=1){
                l.push_front(make_pair(1,unordered_set<string>()));
            }
            l.front().second.insert(key);
            m[key]=l.begin();
        }else{
            auto it=m[key];
            it->second.erase(key);
            if(it==prev(l.end())){
                l.push_back(make_pair(it->first+1,unordered_set<string>()));
                l.back().second.insert(key);
                m[key]=prev(l.end());
            } else {
                auto it_next=next(it);
                if(it_next->first != it->first+1){
                    it_next=l.insert(it_next, make_pair(it->first+1, unordered_set<string>()));
                }
                it_next->second.insert(key);
                m[key]=it_next;
            }
            if(it->second.size()==0)l.erase(it);
        }
    }

    /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
    void dec(string key) {
        if(m.find(key)==m.end())return;
        auto it=m[key];
        it->second.erase(key);
        if(it->first==1){
            if(it->second.size()==0)l.erase(it);
            m.erase(key);
            return;
        }

        if(it==l.begin()){
            l.push_front(make_pair(it->first-1,unordered_set<string>()));
            l.front().second.insert(key);
            m[key]=l.begin();
        }else{
            auto it_prev=prev(it);
            if(it_prev->first != it->first-1){
                it_prev=l.insert(it, make_pair(it->first-1, unordered_set<string>()));
            }
            it_prev->second.insert(key);
            m[key]=it_prev;
        }
        if(it->second.size()==0)l.erase(it);
    }

    /** Returns one of the keys with maximal value. */
    string getMaxKey() {
        if(l.empty())return "";
        unordered_set<string>& back=l.back().second;
        return *(back.begin());
    }

    /** Returns one of the keys with Minimal value. */
    string getMinKey() {
        if(l.empty())return "";
        unordered_set<string>& front=l.front().second;
        return *(front.begin());
    }
    list<pair<int,unordered_set<string>>> l;
    unordered_map<string,list<pair<int,unordered_set<string>>>::iterator> m;
};

/**
 * Your AllOne object will be instantiated and called as such:
 * AllOne obj = new AllOne();
 * obj.inc(key);
 * obj.dec(key);
 * string param_3 = obj.getMaxKey();
 * string param_4 = obj.getMinKey();
 */