C ++中基于时间的键值存储

假设我们必须创建一个名为TimeMap的基于时间的键值存储类，该类支持两种操作。

• set（string key，string value，int timestamp）：这将存储键和值以及给定的时间戳。

• get（string key，int timestamp）：这将返回一个值，使得先前调用过set(key,value,timestamp_prev)，且timestamp_prev <= timestamp。

现在，如果有多个这样的值，它必须返回timestamp_prev值最大的值。如果没有这样的值，则返回空字符串（“”）。因此，如果我们像下面这样调用函数-

set（“ foo”，“ bar”，1），get（“ foo”，1），get（“ foo”，3），set（“ foo”，“ bar2”，4），set（“ foo”， 4），set（“ foo”，5），则输出为：[null，“ bar”，“ bar”，null，“ bar2”，“ bar2]

为了解决这个问题，我们将遵循以下步骤-

• 定义映射m

• 该set()方法会像

• 将（时间戳，值）插入m [key]

• 该get()方法将如下工作

• 中：=低+（高–低）/ 2

• 如果v [mid]的键<=时间戳，则

• 否则高：=中– 1

• ret：= v [mid]的值并设置为低：= mid + 1

• ret：=一个空字符串

• v：= m [key]

• 低：= 0，高：= v – 1的大小

• 而低<=高

• 返回ret

让我们看下面的实现以更好地理解-

示例

#include <bits/stdc++.h>
using namespace std;
class TimeMap {
   public:
   /** Initialize your data structure here. */
   unordered_map <string, vector < pair <int, string> > > m;
   TimeMap() {
      m.clear();
   }
   void set(string key, string value, int timestamp) {
      m[key].push_back({timestamp, value});
   }
   string get(string key, int timestamp) {
      string ret = "";
      vector <pair <int, string> >& v = m[key];
      int low = 0;
      int high = v.size() - 1;
      while(low <= high){
         int mid = low + (high - low) / 2;
         if(v[mid].first <= timestamp){
            ret = v[mid].second;
            low = mid + 1;
         }else{
            high = mid - 1;
         }
      }
      return ret;
   }
};
main(){
   TimeMap ob;
   (ob.set("foo","bar",1));
   cout << (ob.get("foo", 1)) << endl;
   cout << (ob.get("foo", 3)) << endl;
   (ob.set("foo","bar2",4));
   cout << (ob.get("foo", 4)) << endl;
   cout << (ob.get("foo", 5)) << endl;
}

输入值

Initialize it then call set and get methods as follows:
set("foo","bar",1))
get("foo", 1))
get("foo", 3))
set("foo","bar2",4))
get("foo", 4))
get("foo", 5))

输出结果

bar
bar
bar2
bar2