# 981. Time Based Key-Value Store

Create a timebased key-value store class `TimeMap`, that supports two operations.

1\. `set(string key, string value, int timestamp)`

* Stores the `key` and `value`, along with the given `timestamp`.

2\. `get(string key, int timestamp)`

* Returns a value such that `set(key, value, timestamp_prev)` was called previously, with `timestamp_prev <= timestamp`.
* If there are multiple such values, it returns the one with the largest `timestamp_prev`.
* If there are no values, it returns the empty string (`""`).

**Example 1:**

```
Input: inputs = ["TimeMap","set","get","get","set","get","get"], inputs = [[],["foo","bar",1],["foo",1],["foo",3],["foo","bar2",4],["foo",4],["foo",5]]
Output: [null,null,"bar","bar",null,"bar2","bar2"]
Explanation:   
TimeMap kv;   
kv.set("foo", "bar", 1); // store the key "foo" and value "bar" along with timestamp = 1   
kv.get("foo", 1);  // output "bar"   
kv.get("foo", 3); // output "bar" since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 ie "bar"   
kv.set("foo", "bar2", 4);   
kv.get("foo", 4); // output "bar2"   
kv.get("foo", 5); //output "bar2"   

```

**Example 2:**

```
Input: inputs = ["TimeMap","set","set","get","get","get","get","get"], inputs = [[],["love","high",10],["love","low",20],["love",5],["love",10],["love",15],["love",20],["love",25]]
Output: [null,null,null,"","high","high","low","low"]
```

**Note:**

1. All key/value strings are lowercase.
2. All key/value strings have length in the range `[1, 100]`
3. The `timestamps` for all `TimeMap.set` operations are strictly increasing.
4. `1 <= timestamp <= 10^7`
5. `TimeMap.set` and `TimeMap.get` functions will be called a total of `120000` times (combined) per test case.

```cpp
class TimeMap {
public:
    /** Initialize your data structure here. */
    TimeMap() {
        
    }
    
    void set(string key, string value, int timestamp) {
        mp[key][timestamp] = value;
    }
    
    string get(string key, int timestamp) {
        auto it = mp[key].upper_bound(timestamp);
        return it == mp[key].begin() ? "" : prev(it)->second;
    }
private:
    unordered_map<string, map<int, string> > mp; // key -> <timestamp, value>
};
```

```cpp
class TimeMap {
public:
    /** Initialize your data structure here. */
    TimeMap() {
        
    }
    
    void set(string key, string value, int timestamp) {
        mp[key].push_back({timestamp, value});
    }
    
    string get(string key, int timestamp) {
        auto it = upper_bound(mp[key].begin(), mp[key].end(), pair<int, string>(timestamp, ""), [](
            const pair<int, string>& a, const pair<int, string>& b) { return a.first < b.first; });
        return it == mp[key].begin() ? "" : prev(it)->second;
    }
private:
    unordered_map<string, vector<pair<int, string> > > mp; // key -> <timestamp, value>
};
```

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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/design/981.-time-based-key-value-store.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.