981. 基于时间的键值存储

二分

class TimeMap {
public:
    unordered_map<string,vector<pair<int,string>>>hash;
    /** Initialize your data structure here. */
    TimeMap() {}
    
    void set(string key, string value, int timestamp) {
        hash[key].push_back({timestamp,value});
    }
    
    string get(string key, int timestamp) {
        if(!hash.count(key))return "";
        auto& q = hash[key];
        int l = 0, r = q.size() - 1;
        while(l < r){
            int mid = l + (r - l + 1) / 2;
            if(q[mid].first <= timestamp)l = mid;
            else r = mid - 1;
        }
        if(q[r].first > timestamp)return "";
        return q[l].second;
    }
};

/**
 * Your TimeMap object will be instantiated and called as such:
 * TimeMap* obj = new TimeMap();
 * obj->set(key,value,timestamp);
 * string param_2 = obj->get(key,timestamp);
 */