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 (“”).

class TimeMap {
    unordered_map<string, map<int, string>> m;
public:
    /** Initialize your data structure here. */
    TimeMap() {}

    void set(string key, string value, int timestamp) {
        m[key][timestamp] = value;
    }

    string get(string key, int timestamp) {
        auto res = m[key].upper_bound(timestamp);
        return res == m[key].begin() ? "" : prev(res)->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);
 */