LeetCode 432. 全 O(1) 的数据结构（设计题）*

class node
{
public:
    int val;
    unordered_set<string> s;
    node(int v)
    {
        val = v;
    }
};
class AllOne {
    unordered_map<string, list<node>::iterator> m;
    list<node> l;
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) {
        auto it = m.find(key);
        if(it == m.end())
        {
            if(l.empty() || l.front().val > 1)
                l.push_front(node(1));//没有val为1的，新建
            l.begin()->s.insert(key);
            m[key] = l.begin();
        }
        else
        {
            auto iter = it->second;//迭代器位置
            int num = iter->val;//当前数字
            iter->s.erase(key);//原位置处删除
            auto olditer = iter;
            auto newiter = ++iter;
            num++;
            if(newiter != l.end() && newiter->val == num)
            {	//新位置数字刚好是+1以后的
                newiter->s.insert(key);
                m[key] = newiter;
            }
            else
            {	//新开辟节点
                auto temp = l.insert(newiter,node(num));//新节点之前插入
                temp->s.insert(key);//返回的当前节点存入字符串
                m[key] = temp;
            }
            if(olditer->s.empty())
                l.erase(olditer);//原来节点为空要删除
        }
    }
    
    /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
    void dec(string key) {
        auto it = m.find(key);
        if(it == m.end()) return;
        auto iter = it->second;
        int num = iter->val;
        iter->s.erase(key);
        auto olditer = iter;
        auto newiter = --iter;
        num--;
        if(num == 0)
            m.erase(key);
        else if(olditer != l.begin() && newiter->val == num)
        {	//前面还有节点，且数字吻合
            newiter->s.insert(key);
            m[key] = newiter;
        }
        else
        {	//前面数字不符合，在老节点前插入
            auto temp = l.insert(olditer,node(num));
            temp->s.insert(key);
            m[key] = temp;
        }
        if(olditer->s.empty())
            l.erase(olditer);
    }
    
    /** Returns one of the keys with maximal value. */
    string getMaxKey() {
        if(l.empty()) return "";
        return *(l.back().s.begin());
    }
    
    /** Returns one of the keys with Minimal value. */
    string getMinKey() {
        if(l.empty()) return "";
            return *(l.front().s.begin());
    }
};