链接：981. 基于时间的键值存储

题解：

class TimeMap {
public:
    /** Initialize your data structure here. */
    TimeMap() {
        _table.clear();
    }
    
    void set(string key, string value, int timestamp) {
        _table[key].emplace_back(std::pair<int, string>(timestamp, value));
    }
    
    string get(string key, int timestamp) {
        auto ite = _table.find(key);
        if (ite == _table.end()) {
            return "";
        }
        auto& arr = ite->second;
        int left = 0;
        int right = arr.size()-1;
        while (left + 1 < right) {
            int mid = left + (right-left)/2;
            if (arr[mid].first == timestamp) {
                return arr[mid].second;
            } else if (arr[mid].first > timestamp) {
                right = mid;
            } else if (arr[mid].first < timestamp) {
                left = mid;
            }
        }
        if (arr[left].first == timestamp) {
            return arr[left].second; 
        } else if (arr[right].first == timestamp) {
            return arr[right].second;
        } else if (arr[right].first < timestamp) {
            return arr[right].second;
        } else if (arr[left].first < timestamp) {
            return arr[left].second;
        }
        return "";
    }
private:
    std::unordered_map<string, std::vector<std::pair<int, string>>> _table;
};

/**
 * 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);
 */

class TimeMap {
public:
    /** Initialize your data structure here. */
    TimeMap() {
        _table.clear();
    }
    
    void set(string key, string value, int timestamp) {
        _table[key].emplace_back(std::pair<int, string>(timestamp, value));
    }
    
    string get(string key, int timestamp) {
        auto ite = _table.find(key);
        if (ite == _table.end()) {
            return "";
        }
        std::pair<int, std::string> upper(timestamp, string({127}));
        auto entry = upper_bound(ite->second.begin(), ite->second.end(), upper);
        if (entry != ite->second.begin()) {
            return (entry-1)->second;
        }
        return "";
    }
private:
    std::unordered_map<string, std::vector<std::pair<int, string>>> _table;
};

/**
 * 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);
 */