###### tags: `LeetCode` `Medium` `Binary Search`
# LeetCode #981 [Time Based Key-Value Store](https://leetcode.com/problems/time-based-key-value-store/)
### (Medium)

設計一個基於時間的鍵值數據結構，該結構可以在不同時間戳存儲對應同一個鍵的多個值，並針對特定時間戳檢索鍵對應的值。

實現 TimeMap 類：

TimeMap() 初始化數據結構對象
void set(String key, String value, int timestamp) 存儲鍵 key、值 value，以及給定的時間戳 timestamp。
String get(String key, int timestamp)
返回先前調用 set(key, value, timestamp_prev) 所存儲的值，其中 timestamp_prev <= timestamp 。

如果有多個這樣的值，則返回對應最大的  timestamp_prev 的那個值。
如果沒有值，則返回空字符串（""）。

---
首先, 儲存的資料格式為Key-value-time, 但是因為要用time來找到時間最接近的timestamp, 所以資料的儲存格式為unordered_map<key, map<timestamp, value>>。

set function:單純將(timestamp, value)存入s[key]中。

get function:首先先確定key值存在, 若不存在返回""。再來尋找timestamp值大於要求時間的value, 若找到的指標為map的begin, 則代表map中所有的timestamp皆大於指定時間, 找不到符合的資料, 因此回傳""。若不為begin, 則代表至少有一筆資料符合, 此時返回指標的前一個位置的value(也就是所有timestamp滿足條件的資料中, timestamp值最大-最新的那一筆)。

---

class TimeMap {
public:
    unordered_map<string, map<int, string>> s;
    TimeMap() {
        
    }
    
    void set(string key, string value, int timestamp) {
        s[move(key)].emplace(timestamp, move(value));
    }
    
    string get(string key, int timestamp) {
        auto m = s.find(key);
        if(m==s.end())return "";
        auto it = m->second.upper_bound(timestamp);
        if(it==m->second.begin())return "";
        return prev(it)->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);
 */