706. Design HashMap

O(n) time O(n) space
当数据量变大可以把链表改成红黑树提高性能

class MyHashMap {
public:
    /** Initialize your data structure here. */
    MyHashMap() {
        m.resize(n);
    }

    /** value will always be non-negative. */
    void put(int key, int value) {
        auto it = find(key);
        if (it != end(m[key % n])) {
            it->second = value;
        } else {
            m[key % n].emplace_back(key, value);
        }
    }

    /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
    int get(int key) {
        auto it = find(key);
        return it != end(m[key % n]) ? it->second : -1;
    }

    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    void remove(int key) {
        auto it = find(key);
        if (it != end(m[key % n])) {
            m[key % n].erase(it);
        }
    }

    list<pair<int, int>>::iterator find(int key) {
        auto& lst = m[key % n];
        auto pred = [key](const auto &p) { return key == p.first; };
        return find_if(begin(lst), end(lst), pred);
    }

    int n = 1001;
    vector<list<pair<int, int>>> m;
};

/**
 * Your MyHashMap object will be instantiated and called as such:
 * MyHashMap* obj = new MyHashMap();
 * obj->put(key,value);
 * int param_2 = obj->get(key);
 * obj->remove(key);
 */